ĐỒ ÁN MÔN HỌC:
THUẬT TOÁN VÀ PHƯƠNG PHÁP
GIẢI QUYẾT VẤN ĐỀ
ĐẠI HỌC QUỐC GIA THÀNH PHỐ HỒ CHÍ MINH
TRƯỜNG ĐẠI HỌC CÔNG NGHỆ THÔNG TIN
o0o
GVHD: PGS. TS. ĐỖ VĂN NHƠN
HVTH: VŨ QUỐC HƯNG
MSHV: CH1301016
KHÓA: CH08

TP. HCM, 01/2014
Mục lục
CH1301016 - Vũ Quốc Hưng
Giới thiệu
Metaheuristic là một cách gọi chung cho các giải thuật heuristic trong việc giải
quyết các bài toán tổ hợp khó. Metaheuristic bao gồm những chiến lược khác nhau
trong việc khám phá không gian tìm kiếm bằng cách sử dụng những phương thức khác
nhau và phải đạt được sự cân bằng giữa tính đa dạng và chuyên sâu của không gian
tìm kiếm. Một cài đặt thành công của metaheuristic trong một bài toán tổ hợp phải cân
bằng giữa sự khai thác được kinh nghiệm thu thập được trong quá trình tìm kiếm để
xác định được những vùng với những lời giải có chất lượng cao gần tối ưu. Những ví dụ
của metaheuristic bao gồm giải thuật luyện thép (SA) , giải thuật di truyền (GA) , giải
thuật đàn kiến (ACO) ,…Trong đó giải thuật đàn kiến là metaheuristic dùng chiến lược
của kiến trong thế giới thực để giải bài toán tối ưu. SA xuất phát từ phương thức xác
suất và kỹ thuật luyện bao gồm việc nung và điều khiển làm nguội các kim loại để đạt
được trạng thái năng lượng nhỏ nhất .Trong khi đó giải thuật di truyền dựa trên ý
tưởng từ cơ chế di truyền trong sinh học và tiến trình tiến hóa trong cộng đồng các cá
thể của 1 loài.
Bài toán tìm kiếm được xem là bài toán được nhiều người quan tâm, đặc biệt là
tìm kiếm tối ưu toàn cục. Một thuật toán được xem là lý thuyết vững chắc trong việc

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.
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
Tr 5
Nghiên cứu thuật giải đàn kiến và ứng dụng giải quyết bài toán người đưa thư
CH1301016 - Vũ Quốc Hưng
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 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)
Tại thời điểm t=1, 30 con kiến mới đi từ A đến B, lúc này nó sẽ chọn hướng đến
C hoặc hướng đến F. Tại hướng đến F có vệt mùi 15 do 15 con kiến đi từ B đến F, tại
hướng đến C có vệt mùi 30 do 15 kiến đi từ B đến D và 15 con đi từ D đến B thông qua
C (hình 1.2 c). Do đó khả năng kiến hướng đến chọn đường đến C, do đó số kiến mong
muốn đi đến C sẽ gấp đôi số kiến đi đến F (20 con đến C và 10 con đến F). Tương tự
như vậy cho 30 con kiến mới đi từ D đến B.
Quá trình sẽ liên tục cho đến khi tất cả kiến sẽ chọn đường đi ngắn nhất.

(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)
Tr 8
Nghiên cứu thuật giải đàn kiến và ứng dụng giải quyết bài toán người đưa thư
CH1301016 - Vũ Quốc Hưng
Trong đó:
• : nồng độ vết mùi trên cạnh i,j
• : 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
• : Hệ số điều chỉnh ảnh hưởng của
• : Tập các đỉnh láng giềng của i và con kiến k chưa đi qua
Quy luật này mô phỏng hoạt động của một vòng quay xổ số nên được gọi là kỹ
thuật bánh xe xổ số.
Cho một hằng số và một số được tạo ra một cách ngẫu nhiên. Con kiến k ở
đỉnh i sẽ lựa chọn đỉnh j kế tiếp để đi theo một quy tắc lựa chọn được mô tả bởi công
thức sau:
(4)
Trong đó:

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 toán 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 về dạng phù hợp mới áp dụng thuật toán ACO để
giải. Trên đồ thị này các con kiến sẽ đi xây dựng các lời giải cho bài toán.
Sau đây là mô hình cụ thể hơn về thuật toán ACO. Mô tả về thuật toán ACO với
việc thực hiện song song hoạt động của các con kiến.
Procedure ACO_Metaheuristic
parameter_initialization
while (termination_criterion_not_satisfied)
schedule_activities
ants_generation_and_activity ( )
Tr 10
Nghiên cứu thuật giải đàn kiến và ứng dụng giải quyết bài toán người đưa thư
CH1301016 - Vũ Quốc Hưng
pheromone_evaporation ( )
daemon_actions ( ) {optional}
end schedule_activities

release_ant_resources (ant_id)
end Procedure
Tr 11
Nghiên cứu thuật giải đàn kiến và ứng dụng giải quyết bài toán người đưa thư
CH1301016 - Vũ Quốc Hưng
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ẽ tiến hành xây dựng một lời giải cho bài toán khi
chưa thỏa mãn điều kiện dừng.
Ngoài ra có hai thủ tục phụ thêm vào là:
Pheromone_evaporation(): Là tác động của môi trường để làm giảm thông
tin pheromone theo thời gian. Thủ tục này để tránh bế tắc trong tìm kiếm và cho phép
đàn kiến mở rộng không gian tìm kiếm.
Daemon_action(): Là thủ tục hỗ trợ thêm và không gặp trong thực tế (không
có ở đàn kiến tự nhiên). Là một thủ tục để điều chỉnh các thông số khi cần thiết làm
tăng tính hiệu quả của thuật toán. Ví dụ: Thủ tục tìm kiếm cục bộ, thủ tục khởi tạo lại
các thông tin pheromone khi gặp bế tắc trong tìm kiếm.
1.3. Các sơ đồ thuật toán
Nhiều thuật toán đã được đưa ra dựa trên mô hình thuật toán metaheuristic
ACO. Trong các mô hình đưa ra để giải quyết các bài toán tổ hợp tối ưu NP-khó. Các
mô hình này là phát triển dựa trên mô hình thuật toán ACO cụ thể được trình bày bên
trên. Theo các nghiên cứu cho thấy khi sử dụng thuật toán bầy kiến nói chung các
thông tin pheromone và heuristic có thể áp dụng cho các nút hoặc cạnh nối. Trong các
thuật toán đưa ra sau đây thì thông tin pheromone và heuristic chỉ gắn với các cạnh mà
thôi. Phần này chỉ đưa ra 5 mô hình thuật toán ACO phát triển từ hệ thống Ant
System. Nhưng đó chỉ là một số các dạng tiêu biểu của thuật toán ACO, còn tồn tại rất
nhiều các biến thể khác.
1.3.1. Thuật toán Ant System (AS)
Được phát triển bởi Dorigo, Maniezzo và Colorni năm 1991, là thuật toán ACO
đầu tiên. Ban đầu có 3 biến thể khác nhau là: AS-Density, AS-Quantity và AS-Cycle

≠
target_state)
for each do
next_state = apply_ant_decision_policy ( , )
r = next_state ; end while
{
the pheromone_evaporation ( ) procedure triggers and
evaporates pheromone in every edge
}
for each edge do

end for
Tr 13
Nghiên cứu thuật giải đàn kiến và ứng dụng giải quyết bài toán người đưa thư
CH1301016 - Vũ Quốc Hưng
release_ant_resources (ant_id)
end Procedure.
1.3.2. Thuật toán Ant Colony System (ACS)
Phát triển từ thuật toán AS với một số cải thiện như sau:
 Sử dụng một luật khác cho việc di chuyển, gọi là
pseudo-random proportional
rule
. Gọi k là con kiến đang đứng tại nút r. là một tham số, và một giá trị ngẫu nhiên .
Trong đó giá trị của

và là trong khoảng (0,1). Nút s tiếp theo được chọn để di chuyển
kiến k tới được chọn như sau:

end Procedure.
Và thủ tục cập nhật:
Procedure daemon_actions
for each do local_search () {optional}
best_solution ()
if (better ())

end if
for each edge do
{
the pheromone_evaporation ( ) procedure triggers and
evaporates pheromone in every edge
}

end for
end Procedure.
1.3.3. Thuật toán Max-Min Ant System (MMAS)
Được phát triển bởi Stutzle và Hooss vào năm 1996, được mở rộng lên từ hệ
thống AS. Một số đặc điểm được mở rộng từ hệ thống AS như sau.
 Giống như ACS, MMAS thực hiện offline pheromone trail update, tức là sau khi toàn bộ
kiến trong đàn hoàn thành lời giải thì việc cập nhật được tiến hành cho lời giải tối ưu.
Tr 15
Nghiên cứu thuật giải đàn kiến và ứng dụng giải quyết bài toán người đưa thư
CH1301016 - Vũ Quốc Hưng
Đầu tiên thực hiện bay hơi bớt thông tin pheromone (pheromone evaporation) trên tất
cả các cạnh.
Sau đó chỉ có các cạnh thuộc lời giải tốt nhất được cập nhật thông tin
pheromone
Thông thường trong MMAS các lời giải được tinh chỉnh bằng cách tối ưu cục bộ
(local optimizer) trước khi cập nhật thông tin pheromone.

if ()

end for
end for
if (stagnation_condition)
for each edge
rs
a
do
maxrs
τ τ
=
end if
end Procedure
1.3.4. Thuật toán Rank-Based Ant System (RBAS)
Đây cũng là một thuật toán được mở rộng phát triển từ hệ thống AS đưa ra bởi
Bullnheimer, Hartl và Strauss vào năm 1997. Thuật toán này đưa vào ý tưởng xếp hạng
cho các lời giải khi thực hiện cập nhật pheromone. Cụ thể như sau:
 Đầu tiên, m con kiến được xếp hạng theo thứ tự giảm dần dựa theo chất
lượng lời giải mà nó thu được. Ví dụ: (S
1
, S
2
, … S
m-1
, S
m
) trong đó S
1
là phương án tốt

pheromone). Bên cạnh đó trong thuật toán này còn quan tâm tới của việc tối ưu cục bộ
một cách hệ thống để nâng cao chất lượng lời giải của con kiến. Trong thuật toán
BWAS có 3 daemon action thêm vào gồm có:
 Đầu tiên, áp dụng luật có tên
best-worst pheromone update
để tăng
cường pheromone trên các đoạn đường đi qua bởi lời giải tốt nhất toàn cục (global best
solution). Thêm vào đó luật này sẽ phạt những cạnh của lời giải tồi nhất trong lần lặp .
 Áp dụng Pheromone trail mutation để đi theo các hướng khác nhau trong
quá trình tìm kiếm.
 BWAS có cơ chế khởi tạo lại thông tin pheromone khi thuật toán bị đình
trệ, bằng cách thiết lập pheromone trail cho tất cả các thành phần bằng .
Mô hình thủ tục Daemon action của thuật toán BWAS như sau:
Procedure daemon_actions
for each do local_search ()
()
if (best ())

end if
for each edge do
Tr 18
Nghiên cứu thuật giải đàn kiến và ứng dụng giải quyết bài toán người đưa thư
CH1301016 - Vũ Quốc Hưngend for for each edge and do
(1 ).

sách các điểm và khoảng cách giữa chúng , nhiệm vụ là phải tìm đường đi ngắn nhất
có thể mà chỉ thăm mỗi điểm đúng 1 lần.
Bài toán được lần đầu tiên đưa ra như một vấn đề toán học vào năm 1930 và là
một trong số những bài toán được nghiên cứu chuyên sâu trong lĩnh vực tổ hợp thời
đó. Nó được sử dụng như một sự đánh giá cho nhiều phương thức tối ưu khác nhau.
Thậm chí bài toán là thuộc lớp NP khó , một lượng rất lớn các heuristic và phương thức
tìm kiếm cụ thể đã được biết đến vì vậy một vài trường hợp của bài toán với khoảng
chục nghìn điểm đã được giải quyết.
TSP có một vài ứng dụng thậm chí trong dạng thức nguyên thuỷ của nó như lập
kế hoạch, logistic, và sản xuất các microchip. Thay đổi đi chút ít nó xuất hiện như một
bài toán con trong rất nhiều lĩnh vực như việc phân tích gen trong sinh học. Trong
những ứng dụng này, khái niệm thành phố có thể thay đổi thành khách hàng, các điểm
hàn trên bảng mạch, các mảnh DNA trong gen, và khái niệm khoảng cách có thể biểu
diễn bởi thời gian du lịch hay giá thành , hay giống như sự so sánh giữa các mảnh DNA
với nhau. Trong nhiều ứng dụng, các hạn chế truyền thống như giới hạn tài nguyên hay
giới hạn thời gian thậm chí còn làm cho bài toán trở nên khó hơn.
Trong lý thuyết của độ phức tạp tính toán, phiên bản quyết định của bài toán
TSP thuộc lớp NP-complete. Vì vậy không có gỉai thuật hiệu quả nào cho việc giải bài
toán TSP. Hay nói cách khác, giống như thời gian chạy tồi nhất cho bất ký giải thuật
nào cho bài toán TSP tăng theo hàm mũ với số lượng thành phố, vì vậy thậm chí nhiều
trường hợp với vài trăm thành phố cũng đã mất vài năm CPU để giải một cách chính
xác.
Bài toán người đưa thư (TSP) là một trong những bài toán kinh điển và được đầu
tư nghiên cứu trong một thời gian dài. Nó góp phần quan trọng vào việc nghiên cứu
giải thuật ACO: các giải thuật ACO nguyên thủy và những cải tiến của giải thuật này về
sau đều được áp dụng mô phỏng bởi bài toán người du lịch.
Tr 20
Nghiên cứu thuật giải đàn kiến và ứng dụng giải quyết bài toán người đưa thư
CH1301016 - Vũ Quốc Hưng
2.2. Phát biểu bài toán

Mỗi cung (i,j) thuộc A được gán một giá trị mô tả chiều dài của đường đi giữa
hai đỉnh i, j với i, j thuộc N. Mục đính cuối cùng của bài toán người đưa thư là tìm ra
chu trình Hamilton ngắn nhất của đồ thị G có n đỉnh với n là số điểm mà người đưa thư
phải đi qua. Như vậy kết quả tốt nhất của bài toán chính là một hoán vị của các đỉnh
{1, 2, …, n}, sao cho chiều dài ( ) là nhỏ nhất, được tính theo công thức sau:
2.4. Các bước tiến hành
Để thiết lập hành trình chuyển phát, phải tiến hành theo 3 bước:
 Bước 1: Sơ đồ thành phố hoặc một phạm vi thành phố được quét với tất cả các
thùng thư và các tuyến giữa các điểm phải được đánh dấu
 Xác định các tuyến hành trình ngắn nhất giữa tất cả các cặp đỉnh sẽ được đưa
ra. Một ma trận hai hướng có khoảng cách ngắn nhất giữa bất kỳ điểm nút này
tới các điển nút khác sẽ được tạo ra
 Bước 3: Sau khi hoàn thành bước 2 sử dụng thuật toán tối ưu để ghi lại hành
trình đi qua tất cả các điểm nút và phải mất thời gian tối thiểu để người đưa thư
quay trở lại điểm xuất phát
2.5. Sử dụng nguyên lý tham lam cho bài toán người du
lịch
Giả sử G=(X,E) là đồ thị vô hướng gồm n đỉnh với tập đỉnh X = {x
1
, x
2
, …, x
n
},
Nếu G là đồ thị Hamilton thì sẽ có chu trình Hamilton có dạng x
1
x
i1
x
i2

Nghiên cứu thuật giải đàn kiến và ứng dụng giải quyết bài toán người đưa thư
CH1301016 - Vũ Quốc Hưng
Tìm kiếm danh sách thứ tự các điểm mà người đưa thư có thể di chuyển đến từ điểm
hiện tại, rở lại điểm xuất phát sau khi đi qua tất cả các điểm còn lại mỗi điểm một lần
với khoảng cách ít nhất
c) Thuật toán
While (Chưa đi hết các đỉnh)
{
Khi đã đi đến một đỉnh, chọn đi đến đỉnh kế tiếp theo nguyên tắc, liệt
kê tất cả con đường từ đỉnh hiện tại đến những đỉnh chưa đi đến,chọn
con đường ngắn nhất.
}
d) Độ phức tạp thuật toán
Với n thành phố thì có độ phức tạp
2.6. 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
 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
Tr 23
Nghiên cứu thuật giải đàn kiến và ứng dụng giải quyết bài toán người đưa thư
CH1301016 - Vũ Quốc Hưng