Đại Học Quốc Gia TP.HCM
Trường Đại Học Công Nghệ Thông Tin
TIỂU LUẬN MÔN HỌC
ĐIỆN TOÁN LƯỚI VÀ ĐÁM MÂY
SONG SONG HÓA THUẬT GIẢI ACO
GIẢI BÀI TOÁN TSP
GVHD: PGS. TS. NGUYỄN PHI KHỨ
HVTH: NGUYỄN MINH PHÁT
MSHV: CH1301047
TP. HỒ CHÍ MINH
Tháng 6/2014
TỔNG QUAN
Mục đích của bài toán tối ưu tổ hợp là tìm lời giải tốt nhất trong các lời giải có thể và
không gian tìm kiếm lời giải của bài toán là rời rạc .Nhiều bài toán tối ưu tổ hợp có độ phức tạp
tính toán cao và được phân lọai thuộc lớp NP khó .Việc tìm ra lời giải tối ưu cho các bài toán
này cho các hệ thống song song lớn nhất cũng không thể hoàn thành được trong giới hạn thời
gian cho phép vì vậy các kỹ thuật heuristic cho việc giải các bài toán tổ hợp theo hướng xấp xỉ
đã được phát triển để tìm ra các lời giải gần tối ưu (hay xấp xỉ )trong giới hạn thời gian cho
phép. Bài toán người du lịch (TSP) là một bài toán cổ điển thuộc lớp NP được nghiên cứu sâu
trong lĩnh vực tối ưu tổ hợp.
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) ,…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.

Với độ phức tạp tính toán cao của các bài toán tối ưu tổ hợp cũng như đòi hỏi về mặt thời

gian , việc giải các bài toán này yêu cầu cần phải có những siêu máy tính. Con người hy vọng sẽ
đem sức mạnh của siêu máy tính tới tất cả người dùng PC đơn lẻ trên thế giới. Để giải quyết vấn
đề này người ta đã sử dụng Điện toán lưới và Điện toán đám mây.
Trong phạm vi tiểu luận này sẽ tìm hiểu cài đặt song song hóa giải thuật ACO để giải quyết bài
toán TSP. Song song hóa các giải thuật metaheuristic phải đạt được 2 yêu cầu : đa dạng hóa để
khám phá được nhiều vùng trong không gian tìm kiếm và tăng tốc độ tìm kiếm . Nhiều mô hình
song song hoái đã được đề xuất cho nhiều metaheuristic. ACO và GA đều là các cách tiếp cận
dựa trên tập cá thể và vì vậy khá tự nhiên cho việc xử lý song song .
Tiểu luận nhằm mục đích nghiên cứu ,cài đặt thực tế giải thuật song song hóa ACO nhằm
mục đích so sánh hiệu quả của giải thuật ACO thông thường và khả năng song song hóa của các
mô hình song song cho việc tìm kiếm lời giản gần tối ưu của bài tóan TSP. Mô hình thực
nghiệm dùng MPI và một vài bài toán trong thư viện TSPLIB.
1. Bài toán TSP (Traveling Salesman Problem)
1.1 Giới thiệu bài toán

 !"#$%&'
()"*+,#$$-"./0
121'3+#$4256
)#%


Hình 1: Việc kết nối 15 thành phố lớn nhất nước Đức với lộ trình ngắn
nhất là một phép tính khá phức tạp.
""78(6(9:.;7<"./<
=>>#">?@8A9:
 2-B1%CA9:1-"8
 B881#%DBE 7###'#
F2""($/#(E"
G"BH2A1'"%I"6J
.;)E#9:1"*"#H

$8.;9879:"+KIL%
MB9N9#.##O'#!-/
#P'1P;#%86O'#.
##8BFO5'8GQR,S#$-T
24US6VEQ#W#"1--2;%
&"I./9X=>Y>Z">?"*
"12"7%D2'#F
"88[2\/6.9:]8"8'(6
F6.\Q9[59*EH%
1.2. Nhắc lại bài toán Người du lịch
&"I./9X6-./0"./.
=>?68J7./")#[
#$6]4.;#$984]8

#$4\#(^6.;#1"'_`a5
"7.]$LYbc"de""
Z>8"f6.;"$"-gh8'RXP
' i)j"9%I225"2A"
'\5#A#F"3>"$k="8
F"./J7l*"IZ@2?%I./
04B$']"88([
3`mno=omQ?6"'3,SSo
".;\$Q\,o%maV6
9O"TJ'#:3"*%
&"21#19.\B*R
X.
D"RXQ48
 27$pq=M@F#Q6r@F#
?2"B.\%--e"
2P7$

H%
1.3. Ý tưởng mô phỏng hành vi của đàn kiến thực trong tự nhiên
I3`mVm67./sCK>>"O
B$']A(E'L>="
'''\?67(EtD'4Bu=K">&9>
r)#>>?%
D:167v'4BR=929
!406.-T?$P '\R
A362'04]" l
""/ \%f']4"'>"
 '4\$.;4.6.
$/]./F8"'2).\7
01=VS@`SSw$.;?%
f'].;7h.K"(O
(276+"'981B1.;2
7'x=#>"">?././-l
T>""./2.;xF%D'x8*
"28>"/69"F84-.;x5
)#Q.6."/X
0T2.;xF"\99"k.;
x4)#Q.#$59F#$x5

8TB98!2906*k9"
.;x9kTX8"x
"/%
I3`mm`6\5'] (EP'6
"7./&QC"K""v)89OF"'=L
L"68J7eE'6LY8>?4A9:"
"./9X6B$"F'y B%"
"86$\EF"L@D8>=F

"P'E]"\#F"eE'?.;B
$3`mmU#(h8' zrrr=z>"jr>9
r>"r>>6E#ABE"7
4'\?%eE86K""Ov)89O.;E
'#A#A9:"
"22hy"7
ON%
1.4. Thuật toán đàn kiến giải bài toán
người du lịch
s10.\ "'
O6K"")89O"'"={?k2
.'x1./34'>"R
x1O7"./2Rx"1%M\"
I./9XRX"B\7$"
r9>*Q|6K""0\+=6}?"7
$9=6}?R'x2%&46Rx
+.;5"!!$"2%
Phương pháp tìm đường đi mô phỏng hành vi con kiến
D"'T'-./[Q)#]
"Q]85Q46Q"'T7
Q..;]"F# >")
"2
@~M=?F#Q ..;"'E]%
7B>l#()OO7

 "']8'X[Q]Q%
211BA.
]8'XO7Q'#>"1 "
'.;O7G>")=A
Q"2)"T23.;

7"6.B2yQ2
)#B.;72.;7\#
B?%•.58.;1E]€F&)>)$$=g">8
b>>?T.;-8%M)8=837Q'#
>" "'?_EF\R'x.;7
=>"( "'O?_EX\96
*E$11EO7 "'#("%
Kỹ thuật bánh xe xổ số
s8€F#P'89:"#.##-'
9O")6E"#W#"D77=Y>>"? F
"98=p>>L"?%D:1€F.
pMq•
`
6
,
6‚6

ƒF# 6#
`
6#
,
6‚6#)
O7Q'#>"[ .A
`
6
,
6‚6


A007`"Q1'#%s1

".' *Q2)\6.
G" Q2)#
./$G
=S6„R7H""
D8B#H" J
]8)P$=J.;#4B
!?6…]8B' 
]8TQ"#4".k2
1F88#4\T3"2%
D(-F8€F8.;7&)>)P$%
I.F86"'[Q)#64.;\3
Q'#>">"]80=3)"9l?"'
3\Q$x]8Q46'l-%
†-8.;##6-$=290?
T.;F#F"'"/ $=B./(
">"$J#6\./;#H=$Q‡q,SS?$J#
!nSS -']$.6J\./;#\#

\$4#\6x8"[9*E:1%
Y"]-"'-./'x=?
.;F#F6-lX'P9"]-89"]-
(k8 "'2%D2F#Fx6+
2.5X'.; F"%DF#F
x.
Y+J#="'-.;- -?6'
x+.;F#F>"BA
"2 7$8=59y7.F8-+4F#
F.;x=6}?T.; ./.;
7S6V"8.-%I".;8
2+=6}?J.;(:.;x Xx8

"["']6:1.;(.
"2†!$6g

9- "'A%
I/EF#Fx86+J#=8+4"
''-?6R'xT8P="
"394?.5']8'X7 "'62
15.\#871.'.\#G"
'2B]2*%I/F8F"23-
.;/$"*./;#9*EO\%
2. Điện toán lưới và điện toán đám mây
2.1 Giới thiệu Điện toán lưới ( Grid computing)
 p9"E$#6$(""6"#W#
"^681OF#;#R8F#
Xh6x8>"3ˆ26B6"6#(84
.;9X: ./9:%
sE".\=sCg?2y"#4 
28(68 'X.*"9"E#6.;
t"2u=‰>?+8(\%M-sCg#2*
3("B.;9:"/1|6l2
1"#W#9"E#3./$6A
)hBO'6lŠ8]8-("F"%

"26#(GT.;*5A#-sCg21.;)8
9O[(4E262##4"O8$.
3("%
sCg"#W#"2A3("#k.
R)h63B3.*61[2"
E$R6"#W#./9:A9:8F#
B$"(3E"\%p$../.\d>

)>9$]d>6./9:sCgk-8
8("O\98%
7 sCg9OF#;#5 Š
"A6(9:f'l9X:.\5=ipYL?6"#W#]
B./+##Xh%M\sCg6PA
9"E#21$.23("R9*E6F#
l*$A\6^l]
lŠ8O#$;#6.%
p9:6./2'8(22#
A)h".\9$8A9:JH
A)h-BE.;]8''82
T.;O#P\8".\t+u
BX.9:A(2"BE"%
‹89O.\921.E"#W#$
.;HZD">>".*F9:*3.
.;'%[]8B14H6./9:2
19494"F#A5.\x8>"4 9"E#%
g.\8BQ21']8-" #F
21#$;##J\"F('A
4 $9"E#F#%
2.2 Điện toán đám mây – Cloud computing

sE"8 ="9"#?6J7 E"8 
"6B- E" 9:BE 8( #19O
" z>>%F*<8<58$2Š9:Q
 z>> =9O".;$( 2"R8(?
..5#A# 54A"2%Œ
B-E"8673]' BEB 
.;#9.\9<9X:<6"#W#./9:8F#
9X:BE[#"2<"8<B

4#2'A6EBE26k.B
4]'54#::BE2%
>"PA ‹v8(zrrr <I2-G"2B
.;.*./O8 z>>Q.;.;.
*/586"R8(6(6
8("9"E#6#.E8(486%%%<%sE
"8EP1"RE. #4
9X:6 b>,%S )E486).\
BEPF6"2 8' 29O"z>>
1#A*4E" ./9x%M(9:69X: p"">
L##r> #*A9:9"O8'B./62
18F#[ -98Ed>6J #4  9*E .;
.*8 %
3. Giao thức truyền gói tin(MPI) và các vấn đề song song
hóa
3.1 Kiến trúc máy tính song song
C8(""2'l&\#\9x
%
C8("">"'l\#O
F#8(4O=7•"9>?xE1]8'
%C+l238F#"\ 2
8F#"\ lB]"'#6./
"'#2$"%K*E.;"P*l2
.;8"'#%
C8(""\9x6)h9x
B\!\$"%fB
\9x"#W#)h"P^E8F#9*
EE]%Y$.;)h9x"B-\9x
2\H%gh9"$.;9*E.;8]
\')h2\%

'E'#>" 8(""E89:';#
*'l\#\9x%C…l2
)h9x\l.;'$!
"'#$"%

3.2 Phân tách bài toán
&.\41''F""#(
4]8'H%Y26H.;
")hER/%M621H
`%Z9*E=K"9>"#""?%
,%ZBE=Ž"9>"#""?%
3.3 Phân tách dữ liệu
"B-#9*E8""29*E69*E
.;#42(.\)#)Q.A\)
h%C+)h2E#49*E.A\
2%)h214#"P9*E\
*"/X%
CB-""29*EQ2R1%C
F""9*E"R#W#)h4O#x;#\9*E
C#W#)h.;04Q#W#)h.\2v'l%CB-
.-9*E=Y>@Z"@C#>@K=YZCK??"2
.-.;5)hHvB-""
28%
D'.;8#x;#\F"2)h21
("\#49*E2(.\\6O"P9*EQO
E\$.;9*EH5"4#%
3.4 Phân tách công việc
D'.;#9*EB#F""
2$".-""%"./;##9*
E6#4 9*E.A\'-)hT

4*"/.$%eE3 .
-X\5$ )hF%f2/+ 
)hB.;9:%"./;#86B-#
BE8""2BEE]B-#
9*E%"""2BE6".;#
$.;\E:HBEH.;"
)h#x;#%D)hT'l2
BE.;"BE'#>"%
Y""2BE.;OE'l>@>>%
DE:.;##"2'-#::!
'-(%f'l>@>>21OE4.
1.-%
3.5 Song song hóa dữ liệu và mô hình truyền tin
MX62'#F1'.-"
"
`%Y9:B*""9*E!Q9G=K>>@>9
9@#>>?
,%82!7".E B*
./%

"    B  *  "  "  9*  E  !  Q  9G6  .  e
Z>j">Ž"=eZŽ?8i#>CZ69JE4O.;O
E""!"Q9G=2)E.
l("9JE4O?"".-9X'#
9*EE$\)h%D'#9*E6
("6"'#*)h.;"5.-
9X%IB*""9*E./.;OE'l
\^5-B\2BE 
.-9X%
"'#F826./F#-#O#9*

EBE")h#]hE"P
9*E*l%D'#F8#A#%
3.6 Tối ưu chương trình song song
C:(('.-"".;E
3OE$"\.-4O%M\:(862
$lh4]''.-""1.;
E3$21%D842
ZBE%
$12"P9*E%
RF#*"P9*E("%
3.7 Phân chia công việc
ZBEE:#BE*)h
ˆ%s8219N9OE#W#"$
.;OE5)h=9*E?%
I.25B4.//OE'-
#:"X9*EE%f2O'P\"/
OE6#OE#.##1]8'
8%
3.8 Tối thiểu hóa trao đổi dữ liệu
P/OE;(( .-"
"5-2#44"' 
.-%D2•#4"/OE
`%/("%
,%/+%
•%/"PB%
t/(u/9x1OE("9*
E%./;#h.5";'2P)hE1
]8'-BET'l""/`•P"\
/OE4O%s82y"/)
hT9x1("%

t/+u/)h9x1;9*E[)h
%"/86)hBE%
t/"P9*Eu/1)hF2%
/"P9*E2#:"N3B%sN

/41'F#"A1"P%&3B$
89*E6(!$8X/%D.
-4OB2O"P9*E*)h%K"26l
#$12/"P12E3OE.;'
$%
3.9 Giảm chồng chéo giữa trao đổi dữ liệu và tính toán:
D211/+ )h6(
9:ORW"*"P9*E("%s2E'*
'-"8BE\"2/"
P9*E1'l%
3.10 MPI
CZz.;".ŠOE B-t82u
"("""% †-(""""R$
.;'-6+'-E\9*E:%C+'
-2':6B2'"1'-21
8F#O'#"\ '-%"P9*E*
'-.;OE!826#.E98
1OEF9*E*'-%Dlh!B
-"R'-6802B4#8
)h%
gh9"('B-85*9:-2OO#P
'%M671("""21OE
B-82%"26B-8
@D21OE6['l
)h9x\'EF(8

)h%
@D"#W#]h9*E'-'"\A9:
"">"B-\9x%e*.-21
"E3)9:"%
3.11 Lịch sử phát triển MPI
CZz'0 C>>Zz>j>%s2.E
="D?"'-"="Ž"?"#W#‘"
""9>1OE"P9*E*'-%
CZz.;#13B]O"PCZzj"6
22US./9E""oSPA%DŠCZz@`
.;/x)3`mmo%
@DŠ8]8X6AO7'] '-"
8.;75Ž"aaD%.-OE 
CZz# F861"3OE%D.
-CZz9X82+;ŠCZz%
@D'OE .E9"#O)89O
#"'X 7%
@D#O CZz@`2X
%

CŠCZz@,kv.;Xy%I2"E(
\B2"ŠCZz@`6"RB:"E""
"6+;#D’’Ž"mS6O]h'-%
eE6$#OE CZzv(;##4 
ŠCZz@,.Š48 G.2%
3.12 Mục đích của MPI
C:(( CZz#.E(‘.-
R1@D.-CZz219X8.|
"%
@D"#W#O2E]"'l%

CZzk#$\A31"P9*E
6'-E1F#;##W#)h6"#W#
./9xOXy"A8%
@e+;'l""BR%
C$B2"ŠCZz@`
@D'()154.-CZz%B./6
2#:" .-T4A
EE1'.'"%
@†h'-62O8P$.;'-
.-8%
@p“+%
@M"@""=Z>z•i?%
3.13 Các đặc tính cơ bản của một chương trình MPI
C.-CZz"R.-4O2"P
9*E\B]E7".E%D8
$\#
`%f5"6]h'l"P%
,%"P*'-%
•%"P*2'-%
o%"X99*E|%
g\#4.;7154]-"P6)
X$.;)h.;9:6"2")h6)
X)h"8.-E%
CZz”z=?•5"]-""%
CZz”Ž‰>=?•'l]-""%
CZz”D"”=?•)X'-%
CZz”D"”‰>=?•)XP$'-8""•
g\#A6.;71"P9*E1@'@16
\1F9*E*)h%
CZz”Y>9=?•9*E''-%


CZz”c>=?•F9*E['-%
g\#A"#W#OE"P""*
2)h%D
CZz”&=?• 9*E['-'-%
CZz”c>9>=?•9*E['-'-
CZz”&>=?•9x1R"*8
CZz”p>=?•F9*E['-%
CZz”Y>=?•9*E''-%
g\#$x#1"l9*E#A
# ./9x%D
CZz”8#>”=?•"19*ECZz ./9x
CZz”8#>”"=?•J]-Xy19*ECZz%
4. Thuật toán bầy kiến và bầy kiến song song
&"./9X"NP-khó%D"E-'
/$.E23B/ 
"9k $#$"E-'WB
%DF")#)Q.;#11-*/$
!"F)#)Q$\/$.%C).\\E8
2#9:F">""$.!-
*X4\X$.%
4.1 Sơ đồ chung của thuật toán bầy kiến
4.1.1 Giới thiệu chung về thuật toán bầy kiến
  DF"'44.;\E5K""
O.'#F\$.P;#26
."./9X=YZ?6"./..%eE8$.;
A9:83"7vA9:2"
$./%DA9:48211'.
"F#X6BRX6X.\"8B6
%‚

 DF"'F"9O"O]48
'O%f'"1$48%Dl"'#\B
]xl1-l]%C+'
]"./T1"2l7
x%Y$.;xT32'x]%D"'
T-./9O"Fx./6Fx\-
l2).\7%KO"-'8(

-.;./0[P'RA32]85P
 -%
Y8(9:R 'O'
 f'>"./–*Lr
 f2.\F'T7.\62.\\
3'T7.%
 ./0-x=#>"">?
Hình 2
Hình 3

‹>-•(…-$"-,%
p"Keq&eqK&]Dq`6D1!*&
K=-,?%&8/l)>)W-)8*"
//qS6`6,‚pX!•S"'\[L'&6•S
"[r'K6+'981\$X/9
81'1/1E#>"">\R`%s1
l)W.;#>"">8"":"
"/=’`6’,?%
/1qS6-B2Ex"2•S'5
&6•S5K%MEO7./ lG9"26-
[+l2`n"'T'e`n"T'D=-,?
/1q`6•S"'\[L'&6l82T7

.\'D".\'e%.\'e2Ex`n9"`n"
'[&'e6.\'D2Ex•S9"`n'[&'K
`n"[K'&B]D=-,?%K"23'.\
'7./'D69"2$'"$'DT#B$
''e=,S"'D`S"'e?%.O.F8"•S"
'\[K'&%
†-T:"''T7./0
%
8lB-' 48'O%Y86
lT-1F"'%
F"$.48'=LDi?AE$"
9O"-' 48'O.;9:1]8'
        $  .  /  %F  "  48  '    -  '=LDi
>”>?44.;K""6KD"p9>)
"3`mmm%
LDi>@>6"2F#"'"
#$;#-'##$"$./%YO#$
;#8'$$… F"LDi%D"'"
\B]./7x%
DF"LDi.;9:1]8'$.P
;#y%Dy52( 
B8P"$]-]8'%DJ
-.;$X 28

8P"]-]8'6(9:"./..
98#">
eE$LDi44.;C"K""\E"F
3 -"3`mm,6.;7eE$'=LY8>68
LY?%LY'] EA.\'#F(E8(
!$.P;#K"".;.\9G5Z">"9"\O

;# L>"D""M""C>‰‰"%LY4.;#9:
""./9X=YZ?†LZ
Dk"3`mm,6XO$"445
—6K""OvB$O$..;#$5
'%
'#>"X]$'A]8'"
""O5eg=`mm,?6BOvB$
A( F'%
f1[3`mmnK""6p9>Y˜‰>v#1
RLY%K""p9>v)eE$48'=L
D""8Y8>68LDY?"Y˜‰>9e"")CL‹@CzIL
Y8>=CCLY?%#9:""./9X$)A8
B$)A"']€v%K""6p9>9Y˜‰>
k)*# LDi\-'X#."%
M"3`mmn6g%C%p9>C%K""v)E$
L@†6'#F73./"""YZ%M2.;
#9:"e7C8%
'#  26  "  3  `mmU6  "    "  B  E     -  
&)>>C%K""g%C%p9>vB$E$LD""8
Y8>%s8E$F#'7#$;##9:""
YZ%
Dk"3`mmU86%Y˜‰>e%e%e""v)E
$ C)@C  L  Y8> . s8      E  $    '  E  $
LY8>4.;E$("".%
Y26"3`mma6p%KD"C%K""v)E$
LI>%s8'#FX.\O(%M#$
x E$LI>18Bv.;B
$"3`mmV%

M"3,SS`6D%&6L%c"6C%K""v"B$E

$'\e8#>D>•LDi%Z5'#2v.;
B$"3,SSo%
e4'A48LDiF#"E#1
F"'113E3(" F"L
Y8>4%
8.;F"'6:'#>"TB
R F"'%
Sơ đồ chung của thuật toán bầy kiến
ProcedureLDi
 Initial();
  While=™sf9[?9"
  D"Y""=?•
g"Y>=?•//|h6212"B
~#9>=?•
End•
End•
"2
sf9[=AE9[?E.;F"5
'l%M\"./..-sf9[E
.;$J# F"q$J#\9"./9x
OXy"'>"./=A./
0?%
D"Y""=?)89O##21>"#.
##-'=>@>?6\"./..-2
)89O-"+'%
~#9>=?F#Fx"-'v]%
g"Y>=?-'X#.6l#-$.:%

Hình 4%YR F"48'
s2R F"48'6:'#>"T"

BF"48'""./..e"
RX+;#%
4.1.2 Nội dung thuật toán
.\29F"48'-1
'"O6)>1" 'O
%[221.14'6\F"
48'%
Đàn kiến tự nhiên: g"2PA"6+"'9
81T1.;B#>"">%s8

#.E191'"PB-'
A3%f-'A3Y-8RA36-+
"'T-./ 21[P\RA3%Dl
T"'#"PB\6/'
4.->""./0[P\RA3%
YA"8'" 'O
"]--/0[P\RA39O
80
 s./0.;)XB]B
Z>"">6"2"'9x1"P
B\%
 f981-+"'T1.;Z>"">
./2v]%
 "]-981-./6"'T.;X
.\5B#>"">v.;1./%
 C+"'981GB2B
#>"">"./%
 D./2.;#>"">\-).;7
"6.;"./2.;#>"">#-)
.;7W%

[EA'" 'Ov"/
F"48'%CB(A212F"48
'48'"1".%
Hệ thống Ant Colony – Thuật toán bầy kiếng'
"=L{L?B#H" 'O%
2$8P6Q"\'O13
(E] F"%"2"( "'
"-./9O".;BZ>"">v1
+"./%D'" '"
&"4T.;.9RX48 \
 ".;1E!BA"7%ME
"2T.-./="F#Q?H
v "%D80.;.
 B#>"">.;("+"./%
 Il4"./ +"'.;7
G%
 s./.;O79O80
 KO"B#>"">2"./1(
) "'#>".;7"./ 
"'%
 ‹    \    "  "  ./    2    .;
#>"">.;%M./2.;B
#>"">WT2).;7#%

 D"''#:E-./"\"
./ 2=HvE9[ "'?%
 C./"Q.;7/=""?"
"%D/T.;#(6"1
-#.$.21%s2/$. "%
 Y"'""/ 2-T

'F#FB#>"">"%Y$.;
 #>"">T.;("Q1-.;
#.$.$%
 D/$T2$.;#>"">\1
v.;]%I.;/RT2$
.;#>"">W%
 ‹"""'7./2#>"">
\%
 †-#"'#4\'"'7x
./=#.: /?%
Mã giả cho thuật toán Ant colony
Z">9> AntColonyAlgorithm
&`f5"BZ>"">"./
&,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?
&o DF#FB#>"">:=g"#9>?
&n End Do
&U Z(/.;=L8‰>""?
&a DF#  F  B    #>"">  "  :  =p"  
#9>?
&VEnd Do
r9Z">9>
s$\F"LDi6O:.;"8$/
-B'.\6./9:1]8'$
1%
./".\.;!F"LDi#.;
'P.9RX48 27$%&"Rl
BX.\%Y'P"9#x;#\
#9:F"LDi1%RX8"'T)8
9O/""%

Y8B-:1F"LDi%CBF"
LDi\EOE""" "'%
`ProcedureLDi”C>>
,#>>”‰"
•while =>"”>"”"”{>9?
oschedule_activities
n”>>"”9”8=?

U#>"">”>#""=?
a9>"”"=?•"#"ƒ
Vend schedule_activities
mend while
`Send Procedure
`Procedure ”>>"”9”8=?
,repeat in parallel forq`to =>”"j”?
•>d”=?
oend repeat in parallel
nend Procedure
`Procedure >d”=”9?
,‰>”=”9?
•gq#9>””>"8=?
oWhile =>”>
≠
>”>?
nZq"#>”"”#">=L6g6
Ω
?
U>)”>q##8””9>"”#"8=Z6
Ω
?

a">”"”>)”>=>)”>?
If="”>”>#@8@>#@#>"">”#9>?
V 9>#"”#>"">”"”>”>9”>9>=?
end if
mgq#9>@>”>=?
`Send while
if=">”9>8>9”#>"">”#9>?
``for >>9>9>
`,9>#"”#>"">”"”>”>9”>9>=?
`•end for
end if
`o>>>””>">=”9?
`nend Procedure
"2 : ants_generation_and_activity()  :(6
 F% :8BE(R"5"
B$"'%M\+"'"T')89O
/"".HvE9[%
I"2 :#:"
Pheromone_evaporation()g B./1
B#>"">>"/% :81'0"
-'"#W#'5B-'%
Daemon_action()g :+;B#"O'
=B25'O?%g :1QB
$4'3(E] F"%M(9: :-
':6 :5"B#>"">#'0
"-'%

4.2 Các sơ đồ thuật toán
      IF"v.;.9OB-F"
metaheuristic ACO%"B-.1]8'

"P;#$.NP-khóF3-8'nB-%
DB-8#19OB-F"LDi:1
-85#4•%,8%>"A"89:
F"48'2B#>"">>2
1#9:"l"$%"F".
8-B#>"">>Q0\B%
4.2.1 Thuật toán Ant System (AS)
s.;#15K""6C>‰‰"D""3`mm`6F"
LDi4%&42•'1LY@K>86LY@
†8    LY@D8>      5    A  F#  F  B  
Z>"">%
"2
 LY@K>8-'T#>"">"]-
)89O/=">>#@8@>##>"">#9>?6.;
#>"">1F#F!$%
 LY@†8-'T#>"">"]-
)89O/=">>#@8@>##>"">#9>?6.;
#>"">1F#F#:""$=B
>?\"./]š
}
%
 LY@D8>B#>"">T.;F#F/v
"=">9>8>9#>"">#9>?%s8B-
"']$.;".F"LY%
I.F8>"B- LY@8>-#>"">TF#F
"'"/ -%MEF#F#>"">.;'
.
 s4#>"">T.;5
!$=#>"">>#""?%


(1 ). .
rs rs
p
τ τ
¬ −
M\›""=S6`?$8 #>"">%
 '#>"+"'"T.;B
#>"">6.;#>"">8 .;/
"')89O%

, .
k
rs rs rs rs k
a S
τ τ τ
¬ + ∆ ∀ ∈
"2

( )
( ) .
k
rs k
f C S
τ
∆ =

&4LYB9:daemon action68T$
'"2 :-':13.; 

/%DJ#.-1)Xl'#>""]-)8

9O/ "'.
 
.
, ( )
,
.
0, trái l i.
k
r
rs rs
k
k
rs
ru ru
u N
s N r
p
α β
α β
τ η
τ η
∈

   
   



   
   




∈
=
∑
¹
Tóm tắt về thuật toán này như sau
`Procedure >d”=”9?
,q”9•q>>>””>•
k
S r=
•
k
L r=
owhile =>@>
≠
>”>?
nfor>
∈

k
N
=?do 
[ ] [ ]
[ ] [ ]
.
.
k
r

rs rs
k
rs
ru ru
u N
p
α β
α β
τ η
τ η
∈
=
∑
U>)”>q##8””9>"”#"8=Z6
( )
k
N r
?
aq>)”>•
,
k k
S S r=< >
V@@@
m
k k
L L r= ∪
`S>9d>
•>#>"">”>#""=?#">9>>
9
                  >#">   #>"">  >>8 >9>

( )
: 1 .
rs rs rs
a p
τ τ
= −
ƒ
`` for>>9>
rs k
a S∈
do
`,
( )
( )
rs rs k
f C S
τ τ
= +
`•end for
`o>>>””>">=”9?
`nend Procedure%
4.2.2 Thuật toán Ant Colony System(ACS)
Z1[F"LY\$E.
