T I U HÓA K T C UỐ Ư Ế Ấ GVHD: TS VŨ TR NG VŨƯỜ
M C L CỤ Ụ
I.1: GI I THI U CHUNGỚ Ệ 2
I.2: Ý NGHĨA 3
I.2.1: Ý nghĩa khoa h c ọ3
I.2.2: Ý nghĩa th c ti n ự ễ 3
I.3: NG D NG Ứ Ụ 3
I.4: THU T TOÁN B Y KI N Ậ Ầ Ế 4
I.4.1: Gi i thi u chung v thu t toán b y ki n ớ ệ ề ậ ầ ế 4
I.4.2: S đ chung c a thu t toán b y ki n ơ ồ ủ ậ ầ ế 8
I.4.3: N i dung c a thu t toán b y ki n ộ ủ ậ ầ ế 10
I.4.3.1: Mã gi cho thu t toán ả ậ 11
I.4.3.2: Các s đ thu t toán ơ ồ ậ 12
I.4.3.2.1: Thu t toán Ant System (AS) ậ13
I.4.3.2.2: Thu t toán Ant Colony System(ACS) ậ14
I.4.3.2.3: Thu t toán Max–Min Ant System(MMAS) ậ16
I.4.3.2.4: Thu t toán Rank-Based Ant System(RBAS) ậ17
I.4.3.2.5: Thu t toán Best-Worst Ant System(BWAS) ậ18
I.5: ÁP D NG Ụ20
Nhóm: 3 Trang 1
T I U HÓA K T C UỐ Ư Ế Ấ GVHD: TS VŨ TR NG VŨƯỜ
I.1: GI I THI U CHUNGỚ Ệ
Tr c khi nói v n i dung thu t toán b y ki n ta đi tìm hi u v đàn ki nướ ề ộ ậ ầ ế ể ề ế
trong t nhiên, xem các đc đi m và cách ho t đng c a đàn ki n t nhiên. T đóự ặ ể ạ ộ ủ ế ự ừ
có th đa ra các đc đi m c n thi t, tác đng t i thu t toán b y ki n.ể ư ặ ể ầ ế ộ ớ ậ ầ ế
Hình: Đàn ki nế trong t nựhiên
Đàn ki n t nhiên: Là m t loài có t ch c cao, m i con ki n khi di chuy n sế ự ộ ổ ứ ỗ ế ể ẽ
đ l i m t l ng thông tin pheromone trên m t đt. Đây là ph ng ti n đ đánhể ạ ộ ượ ặ ấ ươ ệ ể
d u và đ đàn ki n trao đi thông tin khi tìm ki m th c ăn. Khi đi tìm ki m th c ăn:ấ ể ế ổ ế ứ ế ứ
Sau khi tìm th y ngu n th c ăn, thì m i con ki n s tìm ra đng đi c a nó đ đi tấ ồ ứ ỗ ế ẽ ườ ủ ể ừ
t t i ngu n th c ăn. Chúng s giao ti p trao đi thông tin v i nhau, sau m t th iổ ớ ồ ứ ẽ ế ổ ớ ộ ờ
gian c đàn ki n g n nh tìm ra và đi theo con đng ng n nh t t t t i ngu nả ế ầ ư ườ ắ ấ ừ ổ ớ ồ
th c ăn.ứ
Sau khi nghiên c u cho th y c ch ho t đng c a đàn ki n t nhiên trongứ ấ ơ ế ạ ộ ủ ế ự
quá trình tìm đu ng đi ng n nh t t t t i ngu n th c ăn d a trên các nguyên t cờ ắ ấ ừ ổ ớ ồ ứ ự ắ
sau:
Đng đi ng n nh t đc xác đnh thông qua các thông tin v Pheromone,ườ ắ ấ ượ ị ề
là m t lo i hóa ch t mà các con ki n dùng đ trao đi thông tin v i nhau.ộ ạ ấ ế ể ổ ớ
Khi di chuy n thì m i con ki n s đ l i m t l ng Pheromone trênể ỗ ế ẽ ể ạ ộ ượ
đng đi mà nó đã đi qua.ườ
Trong quá trình di chuy n tìm đng đi, các con ki n s đc đnh h ngể ườ ế ẽ ượ ị ướ
b i các thông tin pheromone đã đc đ l i trên đng đi.ở ượ ể ạ ườ
M i con ki n di chuy n m t cách ng u nhiên khi không có thông tin vỗ ế ể ộ ẫ ề
pheromone trên đo n đng đi.ạ ườ
Nhóm: 3 Trang 2
T I U HÓA K T C UỐ Ư Ế Ấ GVHD: TS VŨ TR NG VŨƯỜ
Các đng đi có l ng pheromone l n thì xác su t đc ch n càng cao,ườ ượ ớ ấ ượ ọ
ng c l i các đo n đng có l ng pheromone th p thì xác su t đcượ ạ ạ ườ ượ ấ ấ ượ
ch n là bé.ọ
T vi c nghiên c u c ch ho t đng c a đàn ki n t nhiên đã cho ra điừ ệ ứ ơ ế ạ ộ ủ ế ự ờ
thu t toán b y ki n. M t cách không chính th c có th nói thu t toán b y ki n làậ ầ ế ộ ứ ể ậ ầ ế
m t b y ki n nhân t o đ gi i bài toán đa ra.ộ ầ ế ạ ể ả ư
T i u đàn ki n (ACO) ố ư ế Là m t đàn ki n nhân t o (Artificial Ants) mô ph ngộ ế ạ ỏ
các ho t đng c a đàn ki n t nhiên. Trong đó ho t đng chính c a các con ki nạ ộ ủ ế ự ạ ộ ủ ế
nhân t o làạ cách tìm đng đi t t t i ngu n th c ăn c a các con ki n t nhiên.ườ ừ ổ ớ ồ ứ ủ ế ự
Đn nay nó đc c i ti n đa d ng và có nhi u ng d ng. Tr c khi gi i thi uế ượ ả ế ạ ề ứ ụ ướ ớ ệ
ph ng pháp ACO, lu n án gi i thi u ph ng th c trao đi thông tin gián ti p c aươ ậ ớ ệ ươ ứ ổ ế ủ
các con ki n và mô hình ki n nhân t o.ế ế ạ
Trên đng đi, m i con ki n đ l i m t ch t hóa h c g i là v t mùi dùng đườ ỗ ế ể ạ ộ ấ ọ ọ ế ể
đánh d u đng đi. B ng cách c m nh n v t mùi, ki n có th l n theo đng điấ ườ ằ ả ậ ế ế ể ầ ườ
đn ngu n th c ăn đc các con ki n khác khám phá theo ph ng th c ch n ng uế ồ ứ ượ ế ươ ứ ọ ẫ
nhiên có đnh h ng theo n ng đ v t mùi đ xác đnh đng đi ng n nh t t tị ướ ồ ộ ế ể ị ườ ắ ấ ừ ổ
đn ngu n th c ăn. Ngoài ra các con ki n có th trao đi thông tin có đc v iế ồ ứ ế ể ổ ượ ớ
nhau, th c hi n tính toán c n thi t, c p nh t mùi…ự ệ ầ ế ậ ậ
Nh các con ki n nhân t o này (v sau cũng g i đn gi n là ki n) Dorigoờ ế ạ ề ọ ơ ả ế
(1991) đã xây d ng h ki n (AS) gi i bài toán ng i chào hàng, hi u qu c a nó soự ệ ế ả ườ ệ ả ủ
v i các ph ng pháp mô ph ng t nhiên khác nh AS, GA đã đc ki m ch ngớ ươ ỏ ự ư ượ ể ứ
b ng th c nghi m và đc phát tri n, ng d ng phong phú v i tên g i chung làằ ự ệ ượ ể ứ ụ ớ ọ
ph ng pháp ACO.ươ
I.2: Ý NGHĨA
I.2.1: Ý nghĩa khoa h cọ
Áp d ng lý thuy t c a thu t toán đàn ki n ACO đ áp d ng trong các bàiụ ế ủ ậ ế ể ụ
toán t i u t h pố ư ổ ợ
So sánh và đánh giá hi u qu c a thu t toán di truy n và thu t toán đàn ki nệ ả ủ ậ ề ậ ế
ACO trong vi c gi i bài toán.ệ ả
I.2.2: Ý nghĩa th c ti nự ễ
Thu t toán đàn ki n có th áp d ng trong các bài toán th c t : l p l ch điậ ế ể ụ ự ế ậ ị
hành trình v i chi phí t i thi u, đnh tuy n trên m ng, cách di chuy n l p đt d mớ ố ể ị ế ạ ể ắ ặ ầ
c u qua các ch ng ng i v t ng n và nhanh nh t, ….vvầ ứ ạ ậ ắ ấ
Nhóm: 3 Trang 3
T I U HÓA K T C UỐ Ư Ế Ấ GVHD: TS VŨ TR NG VŨƯỜ
I.3: NG D NGỨ Ụ
Thu t toán ACO đc ngậ ượ ứ d ng cho m tụ ộ s l ng l n bài toán t i u tố ượ ớ ố ư ổ
h p.ợ
Nh ng ng d ng hi n nay c a ACO chia thành hai l p ng d ng: ữ ứ ụ ệ ủ ớ ứ ụ
L p ng d ng th nh t: L p bài toán t i u t h p NP-hard choớ ứ ụ ứ ấ ớ ố ư ổ ợ
cho công nghệ cũ th ng ít th c ăn. Đc tính thành công nh tườ ứ ặ ấ c a ngủ ứ
d ng ACO t i nh ng bài toán mà ụ ớ ữ ở đó ki n k t h p v i vùng tìm ki mế ế ợ ớ ế
đ có cách gi i quy t t t nh t. ể ả ế ố ấ
L p ng d ng th hai là bài toán tìm đng đi ng n nh t, đó kho ngớ ứ ụ ứ ườ ắ ấ ở ả
cách bài toán gi i quy t thay đi th i gian th c thi bài toán. Nh ng thayả ế ổ ở ờ ự ữ
đi này có th nh h ng không đi c a bài toán nh đã có s n, n u nhổ ể ả ưở ổ ủ ư ẵ ế ả
h ng b l n l n , đc tính đc coi nh chi phí c nh, thay đi theo th iưở ị ẫ ộ ặ ượ ư ạ ổ ờ
gian.
I.4: THU T TOÁN B Y KI NẬ Ầ Ế
I.4.1: G i i thi u chung v thu t toán b y ki nớ ệ ề ậ ầ ế
Các thu t toán ki n l n đu tiên đc gi i thi u b i Dorigo và các c ng sậ ế ầ ầ ượ ớ ệ ở ộ ự
nh là cách ti p c n đa tác t t i các v n đ v t i u t h p khó, nh bài toánư ế ậ ử ớ ấ ề ề ố ư ổ ợ ư
ng i du l ch (TSP), bài toán ng i đa th . Hi n nay s l ng các ng d ng càngườ ị ườ ư ư ệ ố ượ ứ ụ
ngày càng tăng và các nhà khoa h c đã ng d ng nó vào r t nhi u các v n đ t i uọ ứ ụ ấ ề ấ ề ố ư
r i r c. Các ng d ng g n đây có th k đn nh các bài toán l p l ch, tô màu đờ ạ ứ ụ ầ ể ể ế ư ậ ị ồ
th , đnh h ng trong m ng truy n thông, v.v…ị ị ướ ạ ề
Các thu t toán ki n là các thu t toán d a vào s quan sát các b y ki n th c.ậ ế ậ ự ự ầ ế ự
Ki n là lo i cá th s ng b y đàn. Chúng giao ti p v i nhau thông qua mùi màế ạ ể ố ầ ế ớ
chúng đ l i trên hành trình mà chúng đi qua. M i ki n khi đi qua m t đo n đngể ạ ỗ ế ộ ạ ườ
s đ l i trên đo n đó m t ch t mà chúng ta g i là mùi. S l ng mùi s tăng lênẽ ể ạ ạ ộ ấ ọ ố ượ ẽ
khi có nhi u ki n cùng đi qua. Các con ki n khác s tìm đng d a vào m t đ mùiề ế ế ẽ ườ ự ậ ộ
trên đng, m t đ mùi càng l n thì chúng càng có xu h ng ch n. D a vào hành viườ ậ ộ ớ ướ ọ ự
tìm ki m này mà đàn kíên tìm đc đng đi ng n nh t t t đn ngu n th c ăn vàế ượ ườ ắ ấ ừ ổ ế ồ ứ
sau đó quay tr t c a mình.ở ổ ủ
Sau đây là ví d v lu ng đi c a đàn ki n th c t :ụ ề ồ ủ ế ự ế
Nhóm: 3 Trang 4
T I U HÓA K T C UỐ Ư Ế Ấ GVHD: TS VŨ TR NG VŨƯỜ
Hình 1: Mô ph ng đng đi c a b y ki nỏ ườ ủ ầ ế
a. Ki n đi theo đng th ng gi a A và Eế ườ ẳ ữ
b. Khi có ch ng ng i v t ki n s ch n h ng đi, có hai h ng v i kh năngướ ạ ậ ế ẽ ọ ướ ướ ớ ả
ki n s ch n là nh nhau.ế ẽ ọ ư
c. Trên đng ng n h n thì nhi u mùi (pheromone) h nườ ắ ơ ề ơ
Nhóm: 3 Trang 5