Việc kết nối một tập điểm cho trước với chi phí tối thiểu được xem như một
trong những bài toán quan trọng nhất của thiết kế mạng truyền thông. Mạng truyền
thông có thể được mô hình hóa bởi đồ thị vô hướng, liên thông và có trọng số. Do
vậy, từ những năm 70 của thế kỷ trước, bài toán Cây Steiner (Steiner Tree Problem
– STP) trong đồ thị hay bài toán Cây Steiner nhỏ nhất (Steiner Minimal Trees
Problem – SMT) là bài toán tối ưu tổ hợp, đã được các nhà khoa học quan tâm
nghiên cứu để áp dụng cho thiết kế hệ thống mạng và nhiều ứng dụng quan trọng
khác trong khoa học và kỹ thuật. Phần lớn các bài toán tối ưu là bài toán thuộc lớp
NP-hard, không thể giải trong thời gian đa thức. Chỉ với bài toán quy mô nhỏ thì có
thể giải bằng các phương pháp toán chính xác. Các bài toán khác được giải quyết
bằng phương pháp xấp xỉ để tạo ra một giải pháp đủ tốt trong một thời gian hợp lý,
đó là phương pháp heuristic và metaheuristic.
Ứng dụng bài toán Cây Steiner trong khoa học kỹ thuật nói chung đã được
nghiên cứu và công bố trong nhiều công trình [9][17][20][27][37][59][64]. Tuy
nhiên, do bản chất đây là bài toán tối ưu thuộc lớp NP-hard nên cho đến nay, bài
toán vẫn tiếp tục được nghiên cứu nhằm tìm lời giải tối ưu hơn cho các ứng dụng
thực tế, đặc biệt là ứng dụng trong thiết kế hệ thống mạng.
Mô hình toán học của bài toán Cây Steiner nhỏ nhất có thể phát biểu như sau [14]:
Cho G = (V(G), E(G)) là một đơn đồ thị vô hướng liên thông, có trọng số
không âm trên cạnh, trong đó V(G) là tập gồm n đỉnh, E(G) là tập gồm m cạnh, w(e)
là trọng số của cạnh e với e  E(G). Cho L là tập con các đỉnh của V(G), cây T đi
qua tất cả các đỉnh trong L được gọi là Cây Steiner của L. Chi phí của cây T, ký hiệu
là C(T), là tổng trọng số của các cạnh thuộc cây T. Bài toán tìm Cây Steiner có chi
phí nhỏ nhất được gọi là bài toán Cây Steiner nhỏ nhất.
Trong trường hợp tổng quát, bài toán SMT đã được chứng minh thuộc lớp bài
toán NP-hard [14][52][80]. Bài toán SMT có nhiều ứng dụng quan trọng trong một
số lĩnh vực khoa học và kỹ thuật, cụ thể như: Bài toán thiết kế mạng truyền thông
[13], bài toán thiết kế vi mạch cỡ cực lớn VLSI (Very large scale integrated), tin
sinh học [19][26], các bài toán liên quan đến hệ thống mạng với chi phí nhỏ nhất
[13][19][32][34],
Bài toán SMT vẫn thu hút được sự nghiên cứu của nhiều nhà khoa học trong
hàng chục năm qua. Hiện nay, đã có hàng loạt thuật toán giải bài toán SMT được đề
xuất và có thể chia chúng thành các hướng tiếp cận sau: Các thuật toán rút gọn đồ
thị, các thuật toán cận tỉ lệ, các thuật toán tìm lời giải đúng, các thuật toán heuristic
và metaheuristic. Trong khi thuật toán heuristic được áp dụng hiệu quả cho bài toán
cụ thể, thì thuật toán metaheuristic được xem như khung thuật toán tổng quát có thể
áp dụng cho nhiều bài toán tối ưu. Cho đến hiện tại, hướng tiếp cận metaheuristic
cho chất lượng lời giải tốt nhất trong số các thuật toán giải gần đúng.