ĐẠI HỌC QUỐC GIA TP.HCM
TRƯỜNG ĐẠI HỌC CÔNG NGHỆ THÔNG TIN
BÀI THU HOẠCH MÔN
THUẬT TOÁN VÀ PHƯƠNG PHÁP GIẢI QUYẾT VẤN
ĐỀ
ĐỀ TÀI
GIẢI THUẬT TỐI ƯU HÓA ĐÀN KIẾN VÀ
ỨNG DỤNG TRONG BÀI TOÁN NGƯỜI
DU LỊCH
GVHD: PGS.TS. Đỗ Văn Nhơn
HVTH: Võ Tấn Lực
MSSV: CH1301098
TP. Hồ Chí Minh, ngày 10 tháng 10 năm 2014
class="bi x0 y0 w1 h1"
Thuật toán & PP giải quyết vấn đề PGS.TS Đỗ Văn Nhơn
LỜI MỞ ĐẦU
Bài toán Người du lịch, tìm đường đi ngắn nhất cho người du
lịch xuất phát từ một thành phố, đi qua lần lượt tất cả các thành phố
duy nhất một lần và quay về thành phố ban đầu với chi phí rẻ nhất,
được phát biểu vào thế kỷ 17 bởi hai nhà toán học vương quốc Anh
là Sir William Rowan Hamilton và Thomas Penyngton Kirkman, và
được ghi trong cuốn giáo trình Lý thuyết đồ thị nổ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 giải tăng theo hàm số mũ (trong chuyên ngành
thuật giải người ta còn gọi chúng là những bài toán NP-khó). Các nhà
khoa học đã tìm rất nhiều thuật giải để cho ra kết quả của bài toán
như thuật giải tham lam, thuật toán nhánh cận, thuật giải Heuristic,
Meta-Heuristic,…
Trong nội dung đồ án này chỉ xin đề cập đến một thuật giải
metaheutistic – tối ưu hóa đàn kiến (Ant Colony System Algorithm)
và chương trình trực quan hóa các bước thực hiện của thuật giải.

cũng có thể được củng cố nếu những con kiến khác tiếp tục đi trên
con đường đó lần nữa. Dần dần, các con kiến theo sau sẽ lựa chọn
đường đi với lượng mùi dày đặc hơn, và chúng sẽ làm gia tăng nồng
độ mùi hơn nữa trên những đường đi nhiều. Các đường đi với nồng
độ mùi ít hơn sẽ bị loại bỏ và cuối cùng, tất cả đàn kiến sẽ cùng kéo
về một đường đi có khuynh hướng trở thành đường đi ngắn nhất từ
tổ đến nguồn thức ăn của chúng.
HVTH : CH1301098 – Võ Tấn Lực Trang 5/20
Thuật toán & PP giải quyết vấn đề PGS.TS Đỗ Văn Nhơn
Hình 1.1: Luồng đi của đàn kiến thực tế
a) Đường đi từ tổ đến nguồn thức ăn
b) Khi có vật cản kiến sẽ chọn 2 đường đi
c) Đường đi ngắn hơn thì sẽ có nhiều mùi hơn
Hình 1.2 bên dưới giải thích tình huống bầy kiến trong hình 1.1
b) như sau
Hình 1.2: Sơ đồ giải thích tình huống bầy
Giả sử khoảng cách DF=BF=DB qua C và = 1, C là điểm nằm
giữa B và D(hình 1.2 a). Bây giờ chúng ta xem xét điều gì xảy ra tại
những khoảng thời gian rời rạc: t=0, 1, 2… Giả định rằng 30 con kiến
mới đi từ A đến B, 30 con từ E đến D, mỗi kiến di chuyển với tốc độ
một đơn vị thời gian và khi di chuyển kiến để tại thời điểm t một vệt
pheromone với nồng độ là 1. Để đơn giản chúng ta xét lượng
HVTH : CH1301098 – Võ Tấn Lực Trang 6/20
Thuật toán & PP giải quyết vấn đề PGS.TS Đỗ Văn Nhơn
pheromone bay hơi hoàn toàn và liên tục trong khoảng thời gian
(t+1, t+2).
Tại thời điểm t=0, thì không có vệt mùi nào trên cạnh và có 30
kiến ở B, 30 ở D. Việc lựa chọn đường đi của chúng ta ngẫu nhiên do
đó, trung bình từ mỗi nút có 15 con kiến sẽ đi đến F và 15 con sẽ đi
đến C (hình 1.2 b)

HVTH : CH1301098 – Võ Tấn Lực Trang 7/20
Thuật toán & PP giải quyết vấn đề PGS.TS Đỗ Văn Nhơn
Hình 1.3: Sơ đồ chung của thuật giải bầy kiến
1.2. Hệ thống Ant Colony - Đàn kiến nhân tạo
Để bắt chước hành vi của các con kiến thực, Dorigo xây dựng
các con kiến nhân tạo cũng có đặc trưng sản sinh ra vết mùi để lại
trên đường đi và khả năng lần vết theo nồng độ mùi để lựa chọn con
đường có nồng độ mùi cao hơn để đi. Gắn với mỗi cạnh (i,j) nồng độ
vết mùi và thông số heuristic trên cạnh đó.
Ban đầu, nồng độ mùi trên mỗi cạnh (i,j) được khởi tạo bằng
một hằng số c, hoặc được xác định theo công thức:
(1)
Trong đó:
• : nồng độ vết mùi trên cạnh i,j
HVTH : CH1301098 – Võ Tấn Lực Trang 8/20
Thuật toán & PP giải quyết vấn đề PGS.TS Đỗ Văn Nhơn
• : số lượng kiến
• : chiều dài hành trình cho bởi phương pháp tìm kiếm gần nhất
Tại đỉnh i, một con kiến k sẽ chọn đỉnh j chưa được đi qua trong
tập láng giềng của i theo quy luật phân bố xác suất được xác định
theo công thức sau:
(2)
Trong đó:
• : xác xuất con kiến k lựa chọn cạnh i,j
• : hệ số điều chỉnh ảnh hưởng của
• : thông tin heuristic giúp đánh giá chính xác sự lựa chọn của
con kiến khi quyết định đi từ đỉnh i đến j; được xác định theo
công thức:
(3)
o : Khoảng cách giữa đỉnh i và đỉnh j

Qua thực nghiệm trên cho thấy rõ ràng có khả năng xây dựng
được tối ưu hóa đàn kiến: Thông tin để tìm ra con đường ngắn nhất
giữa 2 điểm có thể dữa vào quy tắc xác xuất. Có 2 khía cạnh bất
đồng quan trọng sau:
 Phạm vi xem xét các hành vi của hệ thống là trung bình, và không
phải những hành vi ứng xử tuân theo biến thiên ngẫu nhiên của đàn
kiến là duy nhất.
 Thực nghiệm trên những thời gian không liên tục, trong khi trước đó
mô hình xét trong một thời gian liên tục
Mã giả cho thuật giải Ant Colony
Procedure AntColonyAlgorithm
Khởi tạo các thông tin Pheromone cho các đường đi
Do while (
Chưa thỏa mãn điều kiện dừng
)
Do until (
Mỗi Ant hoàn thành một đường đi
)
Cập nhật thông tin pheromone cục bộ (Local trail update)
End Do
Phân tích các lời giải thu được (Analyze solution)
Cập nhật thông tin pheromone toàn cục (Global trail update)
End Do
End Procedure
Đối với thuật giải ACO, sự hội tụ được đảm bảo tuy nhiên tốc
độ và thời gian thì không biết trước, thường sử dụng để giải quyết
các vấn đề tối thiểu về giá thành.
Thường các bài toán trước khi được giải bằng thuật toán ACO
phải được biến đổi đưa về dạng đồ thị đầy đủ có trọng số. Bao gồm
các nút và các cung không định hướng. Sau khi đi biến đổi bài toán

target_state)
P = compute_transition_probabilities
(A , L ,
Ω
)
next_state =
apply_ant_decision_policy (P ,
Ω
)
move_to_next_state (next_state)
If (on_line_step-by-step-
pheromone_update)
deposit_pheromone_on_the_visit
ed_edge ( )
HVTH : CH1301098 – Võ Tấn Lực Trang 11/20
Thuật toán & PP giải quyết vấn đề PGS.TS Đỗ Văn Nhơn
end if
L = update-internal_state ( )
end while
if (online_delayed_pheromone_update)
for each visited edge
deposit_pheromone_on_the_visited_e
dge ( )
end for
end if
release_ant_resources (ant_id)
end Procedure
Trong đó thủ tục ants_generation_and_activity() là thủ tục
chính, cơ bản của giải thuật. Thủ tục này công việc chính gồm: Tạo
và khởi tạo các thông số cho đàn kiến. Với mỗi con kiến trong đàn sẽ

thông tin Pheromone.
Trong đó:
 AS-Density: Thì đàn kiến sẽ đặt thêm pheromone trong quá
trình xây dựng lời giải (online step-by-step pheromone update),
lượng pheromone để cập nhật là một hằng số.
 AS-Quantity: Thì đàn kiến sẽ đặt thêm pheromone trong quá
trình xây dựng lời giải (online step-by-step pheromone update),
lượng pheromone để cập nhật là phụ thuộc vào độ mong muốn
(thông tin heuristic) với đoạn đường đi qua ηij.
 AS-Cycle: Thông tin pheromone sẽ được cập nhật khi lời giải
đã hoàn thành (online delayed pheromone update). Đây là mô hình
cho kết quả tốt nhất và được coi như là thuật giải AS.
Như vậy theo mô hình của AS-cycle thì pheromone sẽ cập nhật
khi tất cả con kiến hoàn thành lời giải của mình.Việc cập nhật
pheromone được tiến hành như sau:
 Đầu tiên tất cả pheromone trên các cung sẽ được giảm đi
bởi một hằng số (pheromone evaporation).
Với trong khoảng (0,1) là tốc độ bay hơi của pherromone.
 Tiếp theo mỗi con kiến trong đàn sẽ đặt thêm một lượng
thông tin pheromone, lượng pheromone này là hàm của chất lượng
lời giải mà con kiến xây dựng.
Trong đó:
Ban đầu AS không sử dụng daemon action, tuy nhiên sẽ càng
tốt hơn nếu thêm vào đó một thủ tục tìm kiếm cục bộ để làm tăng
chất lượng của lời giải. Còn phương trình để xác định nút tiếp theo
trong quá trình xây dựng lời giải của con kiến như sau:
Thuật giải này được tóm tắt như sau:
Procedure new_ant (ant_id)
HVTH : CH1301098 – Võ Tấn Lực Trang 13/20
Thuật toán & PP giải quyết vấn đề PGS.TS Đỗ Văn Nhơn

 Có Daemon action, thực hiện việc cập nhật pheromone chỉ duy nhất
với lời giải . Cập nhật theo công thức như sau:
HVTH : CH1301098 – Võ Tấn Lực Trang 14/20
Thuật toán & PP giải quyết vấn đề PGS.TS Đỗ Văn Nhơn
 Áp dụng online step-by-step pheromone update
Trong đó là một tham số để giảm pheromone thứ hai sau . Còn
được chọn là một tham số rất bé (như là ngưỡng dưới của
pheromone).
Thuật giải được tóm tắt như sau:
Procedure new_ant (ant_id)
k = ant_id ; r = generate_initial_state;;
while (current-state target_state)
for each do compute
q = generate_random_value_in_[0, 1]
If ()
Next_state = max
else
for each do

next_state = apply_ant_decision_policy ()
end if
r = next_state ; end while

release_ant_resources (ant_id)
end Procedure.
Và thủ tục cập nhật:
Procedure daemon_actions

 Một cải tiến quan trọng trong hệ thống MMAS là việc thêm vào giới
hạn cận trên và dưới của thông tin Pheromone (và ), điều đó giúp
tránh hội tụ tại điểm tối ưu cục bộ. Khởi tạo tất cả thông số
Pheromone giá trị cận trên để ưu tiên việc khai phá không gian tìm
kiếm. Cận trên thường được chọn là giá trị lớn nhất mà Pheromone
có thể đạt được ở vòng lặp cuối cùng.
Trong đó S là lời giải tối ưu, bởi vì lời giải tối ưu không biết
trước nên thông thường được thay thế bởi trong tính toán.
HVTH : CH1301098 – Võ Tấn Lực Trang 16/20
Thuật toán & PP giải quyết vấn đề PGS.TS Đỗ Văn Nhơn
Cách chọn cận dưới , thông thường người ta chọn để thỏa mãn
theo tỷ lệ giữa cận trên và cận dưới .
Do đó tính . Tỉ lệ này phải chọn không nên quá cao, bởi vì khi
đó xác suất để chọn đường đi có mức độ Pheromone thấp là quá
nhỏ. Mặt khác nếu chọn tỉ lệ này quá lớn thì xác suất chọn đường đi
co Pheromone cao là gần với xác suất chọn đường đi có mức độ
Pheromone thấp.
 Khi khởi tạo thông tin pheromone cho các thành phần thì tất cả nhận
giá trị lớn nhất có thể của Pheromone là nhằm tăng cường việc khai
phá không gian tìm kiếm. Một chú ý trong hệ thống MMAS là khi xảy
ra hội tụ cục bộ thì có cơ chế khởi tạo lại thông tin pheromone cho
các nút và giá trị để khởi tạo lại là .
Hàm cập nhật Daemon action của thuật giải MMAS như sau:
Procedure daemon_actions
for each do local_search ()
best_solution ()
if (best (,))
=
end if
= decision (,)

, S
m
)
trong đó S
1
là phương án tốt nhất.
 Pheromone chỉ được đặt thêm trên các cung của б -1 con
kiến có lời giải tốt nhất. Lượng pheromone cũng phụ thuộc trực tiếp
vào thứ hạng sắp xếp của con kiến.
 Các đoạn đường đi của lời giải tốt nhất được nhận thêm một
lượng pheromone phụ thuộc vào chất lượng lời giải.
Các công thức như sau:
Trong đó
Và
Thuật giải được tóm tắt như sau:
Procedure daemon_actions
for each do local_search () {optional}
rank () in decreasing order of solution quality into
if (best ())
=
end if
for to do
for each edge do

end for
end for
for each edge do

end for
end Procedure


for each edge and do
(1 ).
rs rs
p
τ τ
= −
end for

for each nút / component do
HVTH : CH1301098 – Võ Tấn Lực Trang 19/20
Thuật toán & PP giải quyết vấn đề PGS.TS Đỗ Văn Nhơn
z = generate_random_value_in_[0,1]
if ()
s = generate_random_value_in_[1,…, 1]
a = generate_random_value_in_[0,1]
if ()

else

end if
end if
end for
if (stagnation_condition)
for each do
end if
end Procedure
HVTH : CH1301098 – Võ Tấn Lực Trang 20/20
Thuật toán & PP giải quyết vấn đề PGS.TS Đỗ Văn Nhơn
II. ỨNG DỤNG CỦA THUẬT GIẢI ĐÀN KIẾN

Độ dài đường đi Sum = ?
Đường đi theo thứ tự các đỉnh như thế nào ? ( x, …., x)
// Mảng các đỉnh đi qua\
II.3.Thiết kế thuật giải
Chúng ta sẽ áp dụng giải thuật ACO cho bài toán người du lịch.
Việc xây dựng một đồ thị G=(C,L) tương ứng với việc xây dựng đồ thị
G(N, A) ở trên với C= N và L = A. Trong đó tập hợp các đường đi của
đồ thị tương ứng với tập hợp các hành trình từng phần có thể có và
giá trị nhằm ràng buộc rằng con kiến chỉ tìm những đường đi tương
ứng với các hoán vị của thành phố. Ở đây bài toán tìm đường đi
ngắn nhất qua tất cả các đỉnh của đồ thị mỗi đỉnh một lần có mối
liên hệ mật thiết với bài toán tìm đường đi ngắn nhất của con kiến.
a) Một số quy tắc của giải thuật ACO cho bài toán TSP
 Phải đến mỗi điểm đúng một lần
 Một điểm xa xôi có ít cơ hội được lựa chọn
 Đường đi đến điểm nào có độ pheromone cao hơn sẽ được
HVTH : CH1301098 – Võ Tấn Lực Trang 21/20
Thuật toán & PP giải quyết vấn đề PGS.TS Đỗ Văn Nhơn
 Sau mỗi hành trình thì gắn pheromone trên đoạn đường đã
đi qua
 Sau mỗi lần lặp, cường độ pheromone trên những con đường
sẽ bay hơi
Hình 2.2: Sơ đồ thuật giải ACO cho bài toán TSP
b) Thuật giải
Procedure ACOMetaheuristicStatic
Set parameters, initialize pheromone trails
While (termination condition not met) do
ConstructAntsSolutions
ApplyLocalSearch % tùy chọn
UpdatePheromones

hệ trục tọa độ 2D.
Hình 3.1. Thử nghiệm chương trình với thành phố Qatar có 20 điểm
cần đến
Hình 3.2. Thử nghiệm chương trình với đất nước Uruguay với 734
điểm cần đến
IV. TÀI LIỆU THAM KHẢO
HVTH : CH1301098 – Võ Tấn Lực Trang 25/20