ĐẠI HỌC QUỐC GIA TP.HỒ CHÍ MINH
TRƯỜNG ĐẠI HỌC CÔNG NGHỆ THÔNG TIN
__
Bài thu hoạch
THUẬT TOÁN VÀ GIẢI QUYẾT VẤN ĐỀ
THUẬT TOÁN TỐI ƯU BẦY KIẾN TRONG BÀI TOÁN
NGƯỜI DU LỊCH
Giảng viên hướng dẫn: TS. Đỗ Văn Nhơn
Học viên thực hiện: Huỳnh Văn Trận
MSHV: CH1301066
Lớp: Cao Học Khóa 8
Tháng 10/2014
2
Mục Lục
CHƯƠNG 1 GIỚI THIỆU 6
CHƯƠNG 2 BÀI TOÁN 7
CHƯƠNG 3 CƠ SỞ LÝ THUYẾT 8
3.1 Các khái niệm cơ bản về đồ thị 8
3.1.1 Định nghĩa đồ thị 8
3.1.2 Các thuật ngữ cơ bản 9
3.1.3 Đường đi, chu trình và đồ thị liên thông 10
3.1.4 Chu trình Euler 12
3.1.5 Chu trình Hamilton 12
3.1.6 Đồ thị có trọng số 13
3.1.7 Các cấu trúc dữ liệu biểu diễn đồ thị 14
3.2 Khái niệm về lớp các bài toán P và NP 15
3.2.1 Khái niệm các loại thời gian tính 15
3.2.2 Bằng chứng ngắn gọn dễ kiểm tra 16
3.2.3 Khái niệm quy dẫn 16
3.2.4 Lớp bài toán P 17
3.2.5 Lớp bài toán NP 17

LỜI MỞ ĐẦU
Tìm đường đi ngắn nhất là một trong những bài toán luôn luôn thu hút giới nghiên
cứu. Làm sao có thể tìm được đường đi ngắn nhất từ 1 điểm đến 1 điểm khác một cách
ít tốn chi phí nhất trên một bản đồ có thể có những chướng ngại vật.
Hiện nay đã có rất nhiều thuật toán, công trình nghiên cứu về tìm đường đi ngắn
nhất ứng với từng hoàn cảnh khác nhau. Áp dụng tất cả những gì tự nhiên vào trong
máy tính là một trong những bước chuyển biến mang tính chất đột phá của khoa học
máy tính. Vì những gì ngoài tự nhiên thì đã tồn tại rất lâu rồi, đã được đút kết rất nhìu
kinh nghiệm, do vậy áp dụng nó vào máy tính sẽ đạt được mức độ tối ưu nhất định.
Các bài toán thực tế được nghiên cứu tìm ra những ưu điểm của nó để áp dụng vào
trong những hệ thống trên máy tính. Các hệ thống này gọi là hệ thống mô phỏng sinh
học.
Một trong những mô hình tính toán mô phỏng hoạt động sinh học ngoài đời thực
vào trong máy tính tốt nhất cho các bài toán tối ưu tổ hợp, đó chính là mô hình giải
thuật bầy kiến. Mô phỏng lối di chuyển ngoài đời thực của bầy kiến.
Trong bài báo cáo này sẽ mô phỏng cách duy chuyển, hoạt động của bầy kiến, từ
đó mô hình nên giải thuật bầy kiến. Áp dụng trong bài toán người du lịch (TSP –
Travelling Saleman Prolem).
Bài toán người du lịch là một trong những bài toán kinh điển và khó trong tin học.
Và cũng có rất nhiều giải pháp thuật toán cho bài toán này. Và trong báo cáo này sẽ
mô tả một các tiếp cần theo mô hình sinh học, tự nhiên mà cách di chuyển của đàn
kiếm sẽ áp dụng cho người du lịch.
5
CHƯƠNG 1 GIỚI THIỆU
Hệ thống tính toán phỏng sinh học được phát triển theo nguyên lý chung là dựa vào
các hiện tượng sinh học tự nhiên. Các tính toán này bao gồm lớp các thuật toán mô
phỏng sinh học (EA – Evolutionary Algorithm) trong đó chứa các giải thuật tìm kiếm
dựa trên tri thức kinh nghiệm. Các tri thức này được sử dụng để tìm kiếm các lời giải
tốt cho các bài toán khó. Các tính toán này sẽ tìm lời giải tốt hơn những lời giải đã có
trước, đặt biệt phù hợp với những bài toàn không tồn tại lời giải hiệu quả. Các giải

tiếng của Oxford. Nó nhanh chóng
trở thành bài toán khó thách thức toàn
thế giới bởi độ phức tạp thuật toán
tăng theo hàm số mũ (trong chuyên
ngành thuật toán người ta còn gọi
chúng là những bài toán NP-khó).
Người ta bắt đầu thử và công bố các
kết quả giải bài toán này trên máy tính từ năm
1954 (49 đỉnh), cho đến năm 2004 bài toán giải
được với số đỉnh lên tới 24.978, và dự báo sẽ còn tiếp tục tăng cao nữa. Bài toán có thể
phát biểu dưới ngôn ngữ đồ thị như sau :
Cho đồ thị n đỉnh đầy đủ và có trọng số G=(V-tập đỉnh,E-tập cạnh) có hoặc vô hướng.
Tìm chu trình Halmilton có trọng số là nhỏ nhất.
l
7
CHƯƠNG 3 CƠ SỞ LÝ THUYẾT
3.1 Các khái niệm cơ bản về đồ thị
3.1.1 Định nghĩa đồ thị
Trong toán học và tin học, đồ thị là đối tượng nghiên cứu cơ bản của lý thuyết đồ
thị. Một cách không chính thức, đồ thị là một tập các đối tượng gọi là đỉnh nối với
nhau bởi các cạnh. Thông thường, đồ thị được vẽ dưới dạng một tập các điểm (đỉnh,
nút) nối với nhau bởi các đoạn thẳng (cạnh). Tùy theo ứng dụng mà một số cạnh có thể
có hướng.Chúng ta phân biệt các loại đồ thị khác nhau bởi kiểu và số lượng cạnh nối
hai đỉnh nào đó của đồ thị.
Định nghĩa 1.1. Đơn đồ thị vô hướng G=(V,E) bao gồm V là tập các đỉnh, và E là
tập các cặp không có thứ tự gồm hai phần tử khác nhau của V gọi là các cạnh.
Định nghĩa 1.2. Đa đồ thị vô hướng G=(V,E) bao gồm V là tập các đỉnh, và E là
họ các cặp không có thứ tự gồm hai phần tử khác nhau của V gọi là các cạnh. Hai cạnh
e
1

thuộc với nó và sẽ kí hiệu là deg(v).
Định lý 1.1. Giả sử G=(V,E) là đồ thị vô hướng với m cạnh. Khi đó
Hệ quả 1.1. Trong đồ thị vô hướng, số đỉnh bậc lẻ(nghĩa là có bậc là số lẻ) là một
số chẵn
Định nghĩa 1.8. Nếu e=(u,v) là cung của đồ thị có hướng G thì chúng ta nói hai
đỉnh u và v là kề nhau, và nói cung (u,v) nối đỉnh u và đỉnh v hoặc cũng nói cung này
là đi ra khỏi đỉnh u và đi vào đỉnh v. Đỉnh u (v) sẽ được gọi là đỉnh đầu (cuối) của
cung (u,v)
Định nghĩa 1.9. Chúng ta gọi bán bậc ra (bán bậc vào) của đỉnh v trong đồ thị có
hướng là số cung của đồ thị đi ra khỏi nó (đi vào nó) và ký hiệu làError! Objects
cannot be created from editing field codes.
Định lý 1.2. Giả sử G=(V,E) là đồ thị có hướng. Khi đó
Tương tự như trên , chúng ta xét các thuật ngữ cơ bản cho đồ thị hỗn hợp
Quy ước. Kí hiệu với S là một tập hợp thì #(S) hay |S| là số phần tử của tập S.
Cho đồ thị hỗn hợp G =(V,E,A). Nếu e=(u,v) thuộc E, thì chúng ta nói cạnh e kề
với đỉnh u, và v. Nếu e=(u,v) thuộc A, thì chúng ta nói cung e kề với đỉnh u, và v.
Định nghĩa 1.10. Cho đồ thị hỗn hợp G=(V, E, A). Kí hiệu deg(v) là bậc của đỉnh
v trong đồ thị. Giá trị của deg(v) được tính theo công thức sau:
deg(v)= #(các cạnh kề với đỉnh v)+ # (các cung kề với đỉnh v)
Định nghĩa 1.11. Chúng ta gọi bán bậc ra( bán bậc vào) của đỉnh v trong đồ thị
hỗn hợp G là số cung của đồ thị đi ra khỏi nó (đi vào nó) và kí hiệu là indegree(v)
(outdegree(v)).
3.1.3 Đường đi, chu trình và đồ thị liên thông
Định nghĩa 1.12. Đường đi độ dài n từ đỉnh u đến đỉnh v, trong đó n là số nguyên
dương, trên đồ thị vô hướng G=(V,E) là dãy
10
x
0
,x
1,

n-1
, x
n
).
Đỉnh u gọi là đỉnh đầu, còn đỉnh v gọi là đỉnh cuối của đường đi. Đường đi có
đỉnh đầu trùng với đỉnh cuối (tức là u=v) được gọi là chu trình. Đường đi hay chu
trình được gọi là đơn nếu như không có cạnh nào bị lặp lại
Định nghĩa 1.13. Đường đi độ dài n từ đỉnh u đến đỉnh v, trong đó n là số nguyên
dương, trên đồ thị có hướng G=(V, A) là dãy
x0,x1, …,xn-1,xn
trong đó u=x0 , v= xn , (xi,xi+1)
∈
A, i = 0,1,2,…,n-1.
Đường đi nói trên còn có thể biểu diễn dưới dạng dãy các cung:
(x0, x1), (x1, x2), …, (xn-1, xn).
Đỉnh u gọi là đỉnh đầu, còn đỉnh v gọi là đỉnh cuối của đường đi. Đường đi có
đỉnh đầu trùng với đỉnh cuối (tức là u=v) được gọi là chu trình. Đường đi hay chu trình
được gọi là đơn nếu như không có cung nào bị lặp lại
Định nghĩa 1.14. Đường đi độ dài n từ đỉnh u đến đỉnh v, trong đó n là số nguyên
dương, trên đồ thị hỗn hợp G=(V, E, A) là dãy
x0,x1, …,xn-1,xn
trong đó u=x0 , v= xn , (xi,xi+1)
∈
E, hoặc (xi,xi+1)
∈
A, i = 0,1,2,…,n-1.
Đường đi nói trên còn có thể biểu diễn dưới dạng dãy các cạnh, cung:
(x0, x1), (x1, x2), …, (xn-1, xn).
Đỉnh u gọi là đỉnh đầu, còn đỉnh v gọi là đỉnh cuối của đường đi. Đường đi có
đỉnh đầu trùng với đỉnh cuối (tức là u=v) được gọi là chu trình. Đường đi hay chu trình

hỗn hợp.
3.1.5 Chu trình Hamilton
Trong toán học, ngành lý thuyết đồ thị, một đường đi Hamilton là một đường đi
trong đồ thị vô hướng đi qua tất cả các đỉnh của đồ thị, mỗi đỉnh đúng một lần. Một
Chu trình Hamilton là một đường đi Hamilton sau đi qua tất cả các đỉnh của đồ thị
thì trở về đỉnh xuất phát.
12
Một đồ thị có chu trình Hamilton được gọi là đồ thị Hamilton, đồ thị có đường đi
Hamilton được gọi là đồ thị nửa Hamilton.
Bài toán tìm đường đi và chu trình như vậy được gọi là bài toán Hamilton. Bài
toán Hamilton là NP đầy đủ.
Tên gọi đường đi và chu trình Hamilton là gọi theo tên của William Rowan
Hamilton .
3.1.5.1 Định lý Bondy-Chvátal
Cho đồ thị G có n đỉnh, bao đóng cl(G) được tạo ra từ G bằng cách bổ sung cho
mỗi cặp đỉnh không kề nhau u và v với degree(v) + degree(u) ≥ n một cạnh mới uv.
3.1.5.2 Định lý Bondy-Chvátal (1972)
Một đồ thị là Hamilton nếu và chỉ nếu bao đóng của nó là Hamilton.
Vì đồ thi đầy đủ là Hamilton, nên tất cả các đồ thị mà bao đóng là đầy đủ là
Hamilton.
3.1.5.3 Định lý Dirac (1952)
Một đơn đò thị n đỉnh (n > 2) là Hamilton nếu mọi đỉnh của nó có bậc không nhỏ
hơn n/2.
3.1.5.4 Định lý Ore (1960)
Một đồ thị có n đỉnh (n > 2) là Hamilton nếu tổng các bậc của hai đỉnh không kề
nhau đều bằng n hoặc lớn hơn.
3.1.6 Đồ thị có trọng số
Đồ thị được sử dụng để giải các bài toán trong nhiều lĩnh vực khác nhau. Chẳng
hạn, đồ thị được sử dụng để xác định các mạch vòng trong vấn đề giải tích mạch điện.
Chúng ta có thể xác định xem hai máy tính trong mạng có thể trao đổi thông tin với

thể cài đặt bằng mảng (array) hoặc danh sách liên kết động (linked list)), trong đó mỗi
phần tử ghi thông tin về một cạnh, bao gồm: cặp đỉnh mà cạnh đó nối (cặp này sẽ có
thứ tự nếu đồ thị có hướng), trọng số và các dữ liệu khác. Danh sách liên thuộc của
mỗi đỉnh sẽ chiếu tới vị trí của các cạnh tương ứng tại danh sách cạnh này.
Danh sách kề (Adjacency list) - Mỗi đỉnh của đồ thị có một danh sách các đỉnh kề
nó (nghĩa là có một cạnh nối từ đỉnh này đến mỗi đỉnh đó). Trong đồ thị vô hướng, cấu
trúc này có thể gây trùng lặp. Chẳng hạn nếu đỉnh 3 nằm trong danh sách của đỉnh 2
thì đỉnh 2 cũng phải có trong danh sách của đỉnh 3. Lập trình viên có thể chọn cách sử
dụng phần không gian thừa, hoặc có thể liệt kê các quan hệ kề cạnh chỉ một lần. Biểu
diễn dữ liệu này thuận lợi cho việc từ một đỉnh duy nhất tìm mọi đỉnh được nối với nó,
do các đỉnh này đã được liệt kê tường minh.
14
3.1.7.2 Các cấu trúc ma trận
Ma trận liên thuộc (Incidence matrix) - Đồ thị được biểu diễn bằng một ma trận
[b
ij
] kích thước p × q, trong đó p là số đỉnh và q là số cạnh, b
ij
= 1 chứa dữ liệu về quan
hệ giữa đỉnh v
i
và cạnh x
j
. Đơn giản nhất: b
ij
= 1 nếu đỉnh v
i
là một trong 2 đầu của
cạnh x
j

ra câu trả lời là ‘no’, chúng ta gọi những bộ dữ liệu này là bộ dữ liệu ‘no’.
15
3.2.2 Bằng chứng ngắn gọn dễ kiểm tra
Rất nhiều các bài toán quyết định có một đặc điểm chung, đó là để xác nhận câu
trả lời ‘yes’ đối với bộ dữ liệu vào ‘yes’ của chúng, chúng ta có thể đưa ra bằng chứng
ngắn gọn dễ kiểm tra xác nhận câu trả lời ‘yes’ cho bộ dữ liệu vào ‘yes’ đó. Tính ngắn
gọn dễ kiểm tra ám chỉ việc thời gian kiểm tra để đưa ra kết quả chỉ mất thời gian đa
thức. Ví dụ về những bài toán quyết định kiểu này rất nhiều, sau đây là một số ví dụ:
Bài toán kiểm tra tính hợp số: “Có phải số n là hợp số?”, để xác nhận câu trả lời
‘yes’ cho đầu vào n, chúng ta có thể đưa ra một ước số b (1<b<n) của n. Để kiểm tra
xem b có phải là ước số của n chúng ta có thể thực hiện phép chia n cho b sau thời
gian đa thức. Trong ví dụ này , b là bằng chứng ngắn gọn (vì b<n) và dễ kiểm tra (có
thuật toán đa thức để kiểm tra b đúng là ước số của n không).
Đối với bài toán Hamilton, để xác nhận câu trả lời là ‘yes’ cho đồ thị đã cho G,
chúng ta có thể đưa ra một chu trình Hamilton của đồ thị:
v
1
, v
2
, v
3
v
n
, v
1
Việc kiểm tra dãy đỉnh nói trên có là chu trình Hamilton của đồ thị đã cho hay
không có thể thực hiện sau thời gian đa thức. Khi đó chúng ta nói dãy đỉnh nói trên là
bằng chứng ngắn gọn dễ kiểm tra để xác nhận câu trả lời ‘yes’ của bài toán Hamilton.
Đối với bài toán về tính chấp nhận được của biểu thức Bun, để xác nhận câu trả lời
‘yes’ đối với một biểu thức đã cho, chúng ta chỉ cần đưa ra một bộ giá trị các biến số

thời gian đa thức. Trong ví dụ này dễ thấy b là bằng chứng ngắn gọn (b<n) và dễ kiểm
tra (có thuật toán thời gian tính đa thức để kiểm tra xem b có là ước số của n).
3.2.6 Lớp bài toán Co-NP.
Định nghĩa. Ta gọi Co-NP là lớp các bài toán quyết định mà để xác nhận câu trả
lời ‘no’ của nó ta có thể đưa ra bằng chứng ngắn gọn dễ kiểm tra.
Ví dụ: Bài toán kiểm tra tính nguyên tố: “Có phải n là số nguyên tố không?”, để
đưa ra bằng chứng ngắn gọn dễ kiểm tra xác nhận câu trả lời ‘no’ cho đầu vào n ta có
thể đưa ra một ước số b của n.
3.2.7 Lớp bài toán NP-đầy đủ (NP-Complete).
Định nghĩa. Một bài toán quyết định A được gọi là NP-đầy đủ (NP-Complete)
nếu như:
A là một bài toán trong NP.
Mọi bài toán trong NP đều có thể quy dẫn về A.
17
Bổ đề. Giả sử bài toán A là NP-đầy đủ, bài toán B thuộc NP, và bài toán A qui
dẫn được về bài toán B. Khi đó bài toán B cũng là NP-đầy đủ
3.2.8 Lớp bài toán NP- khó (NP-Hard).
Một cách ngắn gọn có thể hiểu bài toán NP-khó là bài toán mà không có thuật
toán thời gian tính đa thức để giải nó trừ khi P = NP, mà chỉ có các thuật toán giải
trong thời gian hàm mũ. Sau đây là định nghĩa chính thức của bài toán NP-khó.
Định nghĩa. Một bài toán A được gọi là NP- khó (NP-hard) nếu như sự tồn tại
thuật toán đa thức để giải nó kéo theo sự tồn tại thuật toán đa thức để giải mọi bài
toán trong NP.
Một số bài toán NP-khó tiêu biểu như:
Bài toán bè cực đại (MaxClique): Cho một đồ thị vô hướng G = (V, E). V là tập
các đỉnh, E là tập các cạnh tương ứng các đỉnh trong V. Cần tìm bè lớn nhất của G. Bè
là tập các đỉnh trong đồ thị mà đôi một có cạnh nốivới nhau (là một đồ thị con đầy đủ
trong đồ thị G).
Bài toán tập độc lập (Independent set): Cho đồ thị vô hướng G = (V, E) và số
nguyên K, hỏi có thể tìm được tập độc lập S với |S| ≥ K. Tập độc lập là tập các đỉnh

việc cực kì khó khăn và hiện tại chưa tồn tại thời gian tính đa thức để giải bài toán đó.
Tất nhiên có thể giải được bài toán nếu như chúng ta thực hiện chiến lược vét cạn đó là
xác định được tất cả các giá trị hàm f trên các phần tử của tập S. Tuy nhiên chiến lược
này không tốt về mặt thời gian nếu như không gian S có số phần tử là hàm mũ hoặc
giai thừa. Ví dụ nếu tập S là tập các hoán vị của 1,…n thì số phần tử của tập S đó là n!.
Con số này thực sự là lớn khủng khiếp và việc thực thi nó là bất khả thi. Khi mà việc
19
tìm các lời giải tối ưu là bất khả thi thì người ta quan tâm đến các lời giải gần tối ưu
mà chúng ta gọi đó là thuật toán xấp xỉ.
Giả sử chúng ta đang làm việc trên một bài toán tối ưu, ở đó mỗi giải pháp tiềm
năng mang một chi phí dương, và chúng ta muốn giải pháp gần tối ưu.
Giả sử rằng một bài toán cần tìm ra lời giải với chi phí là f* là giá trị tối ưu có
kích thước đầu vào n, chúng ta nói rằng một lời giải của bài toán là f là một lời giải
xấp xỉ có cận tỉ số là p(n)>1 nếu như chúng ta có:
max (f/f*, f*/f) <= p(n)
Thông thường các thuật toán xấp xỉ được áp dụng để tìm ra các lời giải có cận xấp
xỉ p(n) thường có giá trị p(n) = p là hằng số. Tuy nhiên vẫn có nhiều bài toán khó đến
mức p(n) phụ thuộc vào n. Giả sử chúng ta đang đối mặt với các yêu cầu tối ưu là cực
tiểu hoá hoặc cực đại hoá hàm chi phí f. Công việc của các nhà toán học là tìm ra
những thuật toán thời gian tính đa thức nhằm giảm giá trị của p hay p(n) đến gần giá
trị 1 càng tốt- nghĩa là giá trị chúng ta thu được rất gần giá trị tối ưu. Tất nhiên khi giá
trị f* quá lớn thì f cũng cách khá xa so với f* nhưng xét về mặt tỉ lệ thì vẫn nằm trong
cận chúng ta đang xét.
Chúng ta nói một thuật toán đối với bài toán có tỉ số là P nếu như với mọi đầu vào
sau một thời gian tính đa thức chúng ta thu được một lời giải f mà so với lời giải tối ưu
f* chúng ta có max (f/f*, f*/f) <= p.
Đối với bài toán cực tiểu hóa ta chỉ cần f/f* <= p.
Đối với bài toán cực đại hoá thì chỉ cần f*/f <= p.
Bài toán tối ưu hóa tổ hợp (Combinatorial optimization)
Bài toán tối ưu hóa tổ hợp liên quan tới việc tìm giá trị cho các biến số rời rạc như

hóa tổ hợp có thể chia 2 loại: Bài toán tĩnh và bài toán động.
Bài toán tối ưu hóa tổ hợp tĩnh (Static Combinatorial optimization):
Là bài toán tối ưu hóa tổ hợp trong đó cấu trúc (topology) và giá (cost) không
thay đổi khi bài toán đang được giải quyết. Ví dụ là bài toán người du lịch. Khi thực
hiện thuật toán để giải bài toán vị trí các thành phố, khoảng cách giữa các thành phố là
không thay đổi.
Bài toán tối ưu hóa tổ hợp động (Dynamic Combinatorial optimization):
Là bài toán tối ưu hóa tổ hợp trong đó cấu trúc (topology) và giá (cost) có thể thay
đổi khi bài toán đang được giải quyết. Ví dụ là bài toán định hướng trong mạng viễn
thông, trong đó mô hình mạng và dung lượng yêu cầu luôn thay đổi.
21
CHƯƠNG 4 THUẬT TOÁN BẦY KIẾN
4.1 Ý tưởng
Năm 1989, nhà bác học người Đan Mạnh Deneubourg và các cộng sự công bố kết
quả nghiên cứu về thí nghiệm trên đàn kiến Argentina (một loài kiến hiếm trên thế
giới), gọi là thí nghiệm “Chiếc cầu đôi” (Double Bridge Experiment).
Cụ thể, họ đã đặt một chiếc cầu đôi gồm hai nhánh (nhánh dài hơn có độ dài bằng
hai lần nhánh ngắn hơn, như hình vẽ) nối tổ của đàn kiến với nguồn thức ăn, sau đó
thả một đàn kiến và bắt đầu quan sát hoạt động của chúng trong một khoảng thời gian
đủ lớn. Kết quả là ban đầu các con kiến đi theo cả hai nhánh của chiếc cầu với số
lượng gần như ngang nhau, nhưng càng về cuối thời gian quan sát người ta nhận thấy
các con kiến có xu hướng chọn nhánh ngắn hơn để đi (80-100% số lượng). Kết quả
được các nhà sinh học lý giải như sau : Do đặc tính tự nhiên và đặc tính hóa học, mỗi
con kiến khi di chuyển luôn để lại một lượng hóa chất gọi là các vết mùi (pheromone
trail) trên đường đi và thường thì chúng sẽ đi theo con đường có lượng mùi đậm đặc
hơn. Các vết mùi này là những loại hóa chất bay hơi theo thời gian, do vậy ban đầu thì
lượng mùi ở hai nhánh là xấp sỉ như nhau, nhưng sau một khoảng thời gian nhất định
nhánh ngắn hơn sẽ có lượng mùi đậm đặc hơn so với nhánh dài hơn do cũng lượng
mùi gần xấp sỉ như nhau khi phân bố ở nhánh dài hơn mật độ phân bố mùi ở nhánh
này sẽ không dày bằng nhánh có độ dài ngắn hơn, thêm nữa cũng do lượng mùi trên

23
Ta có thể hiểu công thức trên đơn giản như sau: quyết định lựa chọn đỉnh tiếp theo để
đi của con kiến được lựa chọn ngẫu nhiên theo xác suất (tức là đỉnh nào có xác suất
cao hơn sẽ có khả năng được chọn cao hơn, nhưng không có nghĩa là các đỉnh có xác
suất thấp hơn không được chọn mà nó được chọn với cơ hội thấp hơn mà thôi). Ý
tưởng này được thể hiện qua kỹ thuật Bánh xe xổ số (Lottery Wheel) sẽ được trình bày
sau. Và xác suất này (hay khả năng chọn đỉnh tiếp theo của con kiến) tỷ lệ thuận với
nồng độ vết mùi trên cạnh được chọn (theo đặc tính của con kiến tự nhiên) và tỷ lệ
nghịch với độ dài cạnh, là những hệ số điểu khiển việc lựa chọn của con kiến nghiêng
về phía nào.
Kỹ thuật bánh xe xổ số:
Đây là kỹ thuật phổ biến hay sử dụng trong các phương pháp tìm kiếm dựa vào
xác suất, đặc biệt trong phép toán Chọn lọc (Selection) của thuật toán di truyền
(Genetic Algorithm). Cụ thể kỹ thuật như sau :
Giả sử V={v
1
,v
2
, …, v
n
} là tập các láng giềng
của u, p
1
, p
2
, …, pn là xác suất lựa chọn đỉnh
tiếp theo từ u của tương ứng v
1
,v
2

25
j) còn được tích tụ thêm một lượng mùi nhất định tùy thuộc vào từng con kiến đi
qua, cụ thể được tính như sau :
Trong đó Q là một hằng số, Lk là độ dài hành trình của con kiến thứ k.
Nhờ việc cập nhật mùi này, sau mỗi vòng lặp (hay sau mỗi lần các con kiến đi hết
hành trình), nồng độ vết mùi trên các cạnh sẽ thay đổi (hoặc giảm hoặc tăng dần) ảnh
hưởng đến quyết định chọn của các con kiến, có thể ở bước lặp này chọn một cạnh để
đi nhưng đến bước lặp khác vẫn con kiến đó lại không đi qua cạnh đó nữa. Nhờ vậy
thuật toán có khả năng tìm được lời giải tốt trong những trường hợp dữ liệu cực lớn.
4.3 Quá trình phát triển
Thuật toán Ant System (AS) là thuật toán đầu tiên trong lớp các thuật toán ACO
được đề xuất bở Dorigo trong luận án tiến sỹ của ông năm 1991. Thuật toán AS hướng
đến giải quyết bài toàn tìm đường đi tối ưu trong đồ thị. Mạc dù thật toán AS vẫn còn
thua kém các thuật toán tốt nhất trong việc giải bài toán trên, tuy nhiên ý tưởng của nó
thật sự là mới mẻ mà tỏ ra triển vọng. Về sau đã có rất nhiều nhà cải tiến thuật toán
này do chinh Dorigo đề xuất, cũng như rất nhiều các thuật toán ACO khác đều dựa
trên thật toán AS song đã khắc phụ được một số nhược điểm trong thuật toán này. Có
thể kể tên 2 cải tiến nổi trội nhất của thuật toán AS là thuật toán AXS và thuật toán
MMAS.
ACO Algorithms Tác giả
Ans System Dorigo Maniezzo, & Colorni (1991)
Elitist AS Dorigo (1992); Dorigo, Maniezz, Colorni
(1996
Ant-Q Gambardell & Dorigo (1995); Dorigo &
Gambardella (1996
Ant Colony System Dorigo & Gambardella (1996)
Max-Min AS Stutzle & Hoos (1996, 2000); Stutzle
(1999)
Rank-based AS Bullnheimer, Hartl, & Strauss
26