Ứng dụng giải thuật tối ưu bầy đàn vào bài toán cực tiểu hóa độ trễ

c s dng thut toán ti ưu by ñàn ñ gii quyt bài toán 
cc tiu hóa ñ tr vi mc ñích tăng cht lưng li gii. 
2. GII THUT TI ƯU HÓA BY ĐÀN 
 Particle Swarm Optimization (PSO) là mt kĩ thut ti ưu hóa da trên vic chn ra 
ngu nhiên mt qun th và sau ñó tin hóa các cá th qua nhiu th h ñ ñt ñưc nghim 
ti ưu. PSO ñưc ñ xut bi James Kennedy và Russell Eberhart [5] vào năm 1995. T 
ñó, PSO ngày càng ph bin ñi vi các nhà nghiên cu và hc viên, nó tr thành mt k 
thut mnh m và hiu qu ñ gii quyt các vn ñ ti ưu khó khăn 
 Ý tưng chính ca PSO xut phát t tình hung trong t nhiên. Gi s có mt ñàn 
chim ñang tìm kim thc ăn trong mt vùng nào ñó. Ban ñu tt c các con chim không 
bit thc ăn  ñâu. Tuy nhiên chúng s dn bit thc ăn cách chúng bao xa sau bao nhiêu 
ln bay ñi bay li. Bi l, mun tìm thy thc ăn nhanh nht tt hơn c là theo sau nhng 
con chim gn thc ăn nht. Nghĩa là sau khi bit ñưc thc ăn gn con chim nào thì c by 
s xích li gn con chim y. PSO phng theo kch bn này và s dng ñ gii các bài toán 
ti ưu. 
 Trong PSO thì mi gii pháp ca bài toán chính là mt con chim trong ý tưng trên, 
ñưc gi là particle. Mi particle có mt giá tr thích nghi (fitness value), ñưc ñánh giá 
bng hàm ño ñ thích nghi (fitness function), và mt vn tc ñ ñnh hưng vic di chuyn 
(bayflying) ñ tìm kim. Các particle s duyt không gian tìm kim (không gian nghim 
ca bài toán) bng cách xích li gn các particle có ñiu kin tt nht hin thi (current 
optimum particles). 
 Trong mt tp các cá th chn ra ngu nhiên (còn gi là by ñàn), mi cá th s bng 
cách di chuyn ti v trí khác trong không gian tìm kim cho ñn khi tìm ñưc v trí tt 
nht. Khái nim v s thay ñi v trí y ñưc khái quát trong hình sau: 
TẠP CHÍ KHOA HỌC −−− SỐ 18/2017 17 
 K
 Trong ñó: − Xi : V trí cá th th i ti th h th K 
 K+1
 − Xi : V trí cá th th i ti th h th K+1 
 K
 − Vi : Vn tc cá th th i ti th h th K 
 K+1
 − Vi : Vn tc cá th th i ti th h th K +1 
 Pbest
 − Vi : Vn tc theo Pbest 
 Gbest
 − Vi : Vn tc theo Gbest 
 − P : V trí tt nht ca cá th th i trong th h 
 best i
 − G : V trí tt nht ca cá th trong c qun th 
 best i
 Như th PSO ñưc khi to bi mt nhóm ngu nhiên các cá th và tìm kim gii 
pháp ti ưu bng vic thay ñi v trí các cá th ñ chúng có th tin li gn nhng cá th ti 
ưu hơn. Quá trình c lp ñi lp li cho ñn khi s thay ñi ca các cá th là không ñáng k. 
Trong mi vòng lp (mt th h), mt cá th particle ñưc cp nht bi hai giá tr: 
 − Giá tr th nht : Pbest là cá th tt nht ñt ñưc ti thi ñim hin ti hay là cá th 
có fitness value tt nht trong th h hin ti 
 − Giá tr th hai : G best là cá th tt nht ñt ñưc trong các cá th ti ưu ca mi ln 
lp. Đây có th coi là cá th có ñ thích nghi cao nht trong toàn không gian tìm kim. 
 − Khi mt cá th có ñ thích nghi tt nht so vi nhng cá th lân cn thì có th coi 
ñây là ti ưu cc b gi là L best 
 Trong nguyên bn do Eberhart và Kennedy ñưa ra, các phn t trong PSO s duyt 
không gian bài toán bng cách theo sau các phn t có ñiu kin tt nht hin thi (ñ 
thích nghi ln nht). C th là sau mi khong thi gian ri rc, vn tc và v trí ca mi 
phn t ñưc cp nht theo các công thc: 
 V[] = v[] + c 1 * rand()*(pbest[] – present[]) + C 2 * ran()*(gbest[] – present[]) (1) 
 Present[] = present[] + v[] (2) 
18 TRƯỜNG ĐẠI HỌC THỦ ĐÔ H NỘI 
 Trong ñó: 
 − V[] : vecto mô t vn tc dch chuyn ca cá th 
 − Present[]: là vecto mô t cá th hin ti 
 − Rand() tr v kt qu là 0 hoc 1. Nghĩa là cá th chn ngu nhiên dch chuyn theo 
Pbest hay G best . 
 − C1 và C 2 là tham s gia tc hay là tham s hc. Nó có ý nghĩa ñ tăng nhanh quá 
trình dch chuyn. Vic la chn giá tr cho 2 tham s này cũng cn cn trng ñ tránh gia 
tc nhanh quá s làm quá trình la chn cá th tt b rơi vào best cc b. 
 Gi mã ca thut toán PSO ñưc mô t như dưi ñây: 
 1 Khi to particle; //Khi to qun th 
 2 Do 
 3 ForEach particle 
 4 Tính FitnessValue() 
 5 If Particle.FitnessValue < Pbest.FitnessValue then 
 6 Pbest = Particle; 
 7 EndIf 
 8 If Pbest<Gbest then Gbest = Pbest; 
 9 Endif 
 10 EndFor 
 11 ForEach particle 
 12 Tính vn tc dch chuyn theo công thc (1) 
 13 Dch chuyn Particle theo công thc (2) 
 14 EndFor 
 15 While Điu kin dng chưa tha mãn; 
 Trên ñây là thut toán PSO nguyên bn [4] còn có tên là ti ưu toàn cc trong ñó vn 
tc dch chuyn mi phn t s ph thuc trên hai yu t: v trí phn t tt nht trong th 
h hin ti Pbest và v trí phn t tt nht tng ñt ñưc trong các th h t trưc ti gi 
Gbest. Sau này có thêm mt s ci tin vi ñ xut ñưa thêm yu t cc b là ngoài hai yu 
t Pbest và Gbest thì s dch chuyn ca cá th s ph thuc thêm bi mt yu t là v trí 
tt nht lân cn nó gi là Lbest. Khi ñó vecto vn tc s ñưc tính theo công thc sau: 
 v[] = v[] + c1.rand(). (pbest[]  present[]) + c2.rand() * (gbest[]  present[]) 
 + c3.rand() * (lbest[]  present[]) (1’) 
 Mt ñ xut ci tin khác cũng rt trin vng ñó là s dch chuyn ca phn t ngoài 
hai yu t Pbest và Gbest thì còn thêm mt yu t th ba ñó là vecto dch chuyn ca cá 
th ñó  th h trưc. Quá trình ñưc khái quát qua hình sau: 
TẠP CHÍ KHOA HỌC −−− SỐ 18/2017 19 
 Khi ñó công thc tính vn tc s ñưc vit li là: 
 v[] = v[] + c1.rand(). (pbest[]  present[]) + c2.rand() * (gbest[]  present[]) 
 + c3.rand() * (forward[]  present[]) (1’’) 
 Gii thut PSO có th ñưc xem như là mt tp hp các vectơ có qu ño dao ñng 
xung quanh mt khu vc ñưc xác ñnh bi tng v trí ca cá th tt nht trưc ñó và v trí 
tt nht ca mt s cá th khác. Gbest giúp by hi t nhanh, tt c các cá th ñưc thu hút 
ñng thi. Tuy nhiên, nu Gbest không phi là cá th tt nht, thì ñàn không th khám phá 
khu vc khác, do ñó, by ñàn có th b mc kt và thut toán hi t sm. 
3. THUT TOÁN PSO Đ XUT 
 
 Ý tưng 
 Chúng tôi ñ xut s dng thut toán ti ưu by ñàn có ci tin ñ gii quyt bài toán 
cc tiu hóa ñ tr (Minimum Latency Problem – MLP). Chúng ta s bt ñu bng vic 
khi to mt tp các phương án(by ñàn) mà mi phương án th hin mt. Theo quá trình 
ca thut toán PSO, ta dch chuyn by ñàn qua nhiu vòng lp ri tìm ra phương án tt 
nht chp nhn ñưc. 
 
 Thut toán 
 −−− Lưc ñ thut toán 
 Thut toán PSO phi xác ñnh các th tc chính sau ñây: Khi to by ñàn, la chn 
Pbest, cp nht cho Gbest, xác ñnh vectơ dch chuyn cho mi cá th da trên tiêu chí ñã 
chn, dch chuyn cá th theo vectơ. Quá trình lp li cho ñn khi tha mãn ñiu kin dng 
ca thut toán. Trong bài báo này chúng tôi ñ xut ñiu kin dng ca thut toán là sau 10 
vòng lp mà Pbest và Gbest không thay ñi nhiu. 
20 TRƯỜNG ĐẠI HỌC THỦ ĐÔ H NỘI 
 − Khi to qun th 
 Vì ñ th ñã cho là ñ th ñy ñ và yêu cu là ñưng ñi ñơn xut phát t mt ñnh s 
bt kì cho trưc ñi qua các ñnh ca ñ th nên ta s mã hóa mt phương án là mi cá th là 
mt chui hoán v 1. . . Trong ñó 1..n là ch s các ñnh trong ñ th INPUT và mi chui 
TẠP CHÍ KHOA HỌC −−− SỐ 18/2017 21 
s bt ñu bng ñnh s. S lưng ti ña các phương án trong không gian nghim ca bài 
toán là (n1)!. Đ thích nghi ca cá th s ñưc tính là t l nghch vi ñ tr ca chui 
hoán v ñã khi to. Như vy cá th nào càng có ñ thích nghi càng cao thì s càng gn vi 
nghim ca bài toán. 
 S lưng hay kích thưc ban ñu ca qun th là m, ñóng vai trò quan trng trong gii 
thut vì kích thưc qun th quyt ñnh s hi t nhanh hay chm ca gii thut, và kh 
năng thoát ra kh nhng cc tr ña phương ca qun th. Kích thưc qun th nh thì gii 
thut s hi t nhanh nhưng thưng s cho ra kt qu là các cc tr ña phương ch không 
phi là cc tr toàn cc. Vì vi s lưng cá th ít thì qun th d mc vào nhng cc tr ña 
phương và khó thoát ra ñưc. Tuy nhiên, s lưng cá th quá ln li làm thut toán tn 
nhiu thi gian, hi t chm. Vi bài toán cc tiu hóa ñ tr, chúng tôi chn s lưng cá 
th là m=30. 
 V phương pháp khi to qun th cũng có nhiu cách khác nhau. Phương pháp ñơn 
gin nht là random(). Như th ta s có 30 chui hoán v 1. . . 
 −−− Xác ñnh Pbest và Gbest 
 Xác ñnh Pbest th hin qua gi mã sau: 
 1 DelayNode(i) 
 2 Begin 
 3 For j = 1 to i1 do 
 4 Begin 
 5 DelayNode = DelayNode + Distance(j,j+1) 
 6 End ; 
 7 Return DelayNode; 
 8 END ; 
 9 
 10       
 11 
 Tính FitnessValue 
 ForEach Particle 
 Begin 
 DelayPath(Particle); 
 If Particle.DelayPath()< Pbest.DelayPath() then 
 Pbest = Particle; 
 END ; 
 If Pbest < Gbest then Gbest = Pbest 
 Xác ñnh Pbest và Gbest 
22 TRƯỜNG ĐẠI HỌC THỦ ĐÔ H NỘI 
 − Tính vectơ vn tc và dch chuyn cá th 
 Như ñã trình bày thì PSO hin nay có mt s ci tin so vi phiên bn gc [4]. Đ ci 
tin trong vic tính toán vectơ vn tc, cn da trên ba yu t: 
 + V trí phn t Gbest: Đi din cho v trí ti ưu c by ñàn 
 + V trí phn t Pbest: ñi din cho s dch chuyn by ñàn thi ñim hin ti 
 + Vectơ dch chuyn t vòng lp trưc 
 Vn ñ là ta s tính vectơ dch chuyn cho tng yu t như th nào. Trong bài báo này, 
chúng tôi tính vectơ dch chuyn bng cách da trên các khong cách t mi ñnh ti ñnh 
xut phát. Theo ñ xut này chúng ta so khp tng cp ñnh ca hai cá th. Mi ñnh cách 
ñnh xut phát vi khong cách là bao nhiêu thì ly hiu làm h s cho vectơ dch chuyn. 
Nghĩa là s dng chính khong cách t các ñnh ti ñnh A làm vectơ ñi din. 
 Gi s ta ñang xét phn t X có vectơ cùng tên ñang cn dch chuyn v phía Pbest và 
Gbest cùng vi mt vectơ dch chuyn ca X t vòng lp trưc. 
 Sau cùng ta tính vectơ dch chuyn ca X ti vòng lp này theo công thc (1) vi h s 
C1 = C 2 = C 3 = 2; 
 Sau khi có ñưc vectơ dch chuyn, ta dch chuyn phn t X thc cht là ñi v trí các 
ñnh trong chui hoán v sao cho nó tip cn càng gn vi mc tiêu càng tt. Do ñó ñ dch 
chuyn cá th hin ti ta xét tng giá tr tương ng trên vectơ. 
 Vectơ dch chuyn có n giá tr ñu tiên luôn là 0 (vì ñnh xut phát là c ñnh). S ñnh 
cn chn còn li là n – 1 ñnh. Chúng ta có chin lưc như sau: Chn ñnh tương ng trong 
s ñnh còn li mà có khong cách ti ñnh xut phát gn nht vi giá tr tương ng trong 
vectơ dch chuyn. 
4. THC NGHIM 
 
 B d liu kim th 
 D liu kim th ñưc ly t thư vin d liu chun ñã ñưc s dng rng rãi trong 
các bài toán ti ưu. D liu chúng tôi chn ñ kim th cho ñ xut trong công trình này là 
b TSPLIB [12]. Đây là b d liu kim th cho bài toán ngưi bán hàng nhưng tha mãn 
ñiu kin ñu vào cho bài toán MLP. Đây là mt thư mc các tp d liu. Mi tp lưu tr 
ta ñ các ñnh. Mt tp cùng tên vi ñuôi m rng tour cha chui ñnh là ñưng ñi ngn 
nht mà ti thi ñim hin ti ñã tìm ñưc. Da theo chui ñnh này chúng ta cũng có th 
tính ra tng ñ tr ca hành trình. Đây là ñi trng ñ ta ñánh giá hiu qu ca thut toán. 
 B d liu khá phong phú nên chúng tôi chn ra mt s tp d liu ñi din có kích 
thưc không quá ln (s ñnh 50100) và ñ phân b ñu. 
TẠP CHÍ KHOA HỌC −−− SỐ 18/2017 23 
 
 Kt qu thc nghim 
 D liu chn th nghim và kt qu th nghim th hin dưi bng sau, trong ñó, kt 
qu bng thut toán GA ñưc ly t [1,2 ]. OPT và BestSol ln lưt là ñ tr cc tiu ca 
b d liu chun và ñ tr cc tiu ñưc gii bng các thut toán GA và PSO. T là thi 
gian chy ca thut toán tính bng phút. 
 GA PSO 
 Tp d liu OPT 
 BestSol T 
 eil51 6140 6140 2,5 6232 1,6 
 eil76 5894 5894 2,6 6002 1,7 
 st70 7801 7801 2,5 8235 2,4 
 kroA100 239680 241012 2,6 242302 2,5 
5. KT LUN VÀ HƯNG NGHIÊN CU TIP THEO 
 Bài toán MLP là mt bài toán thuc lp NP khó ñang ñưc quan tâm gii quyt. 
Hưng tip cn gii bài toán theo thut toán ti ưu by ñàn có kt qu khá kh quan. Mc 
dù kt qu thc nghim còn thp có th do thut toán ñ xut theo mô hình c ñin có th 
b rơi vào cc tr ña phương và by ñàn không th thoát ra ñưc. Trong nhng bài báo tip 
theo, chúng tôi s tip tc ci thin kt qu bng cách khc phc s hi t sm và nâng cao 
cht lưng li gii. 
 TÀI LIU THAM KHO 
1. Ban Hà Bng, Nguyn Đc Nghĩa (2009), “Gii thut di truyn gii bài toán cc tiu hóa ñ 
 tr”, Tp chí Khoa hc và Công ngh các trưng Kĩ thut, S 71. 
2. Ban Hà Bng, Nguyn Đc Nghĩa (2013), “Thut toán di truyn lai ghép thut toán ñàn kin 
 gii bài toán cc tiu hóa ñ tr”, Tp chí Tin hc và Điu khin hc, S 3, T.29. 
3. Nguyn Gia Như (2014), Mt s thut toán tin hóa gii bài toán ti ưu trong mng máy tính 
 Lun án Tin sĩ Toán hc, Trưng Đi hc Khoa hc T nhiên – Đi hc Quc gia Hà Ni. 
4. Y. Shi & R. Eberhart (1998), “A modified particle swarm optimizer”, IEEE 1998 International 
 Conference . 
5. Yuhui Shi and Russhell C.Eberhart (1998), “Parameter Selection In Particle Swarm 
 Optimization”, SpringerVerlag London, UK. 
6. James Kennedy and Russell Eberhart (1995), “Particle Swarm Optimization”, IEEE 
 International Conference on Neural Network . 
24 TRƯỜNG ĐẠI HỌC THỦ ĐÔ H NỘI 
7. Rene Sitter (2002), “The Minimum Latency Problem Is NPHard for Weighted Trees”, Integer 
 Programming and Combinatorial Optimization . 
8. Michel Goemans Jon Kleinberg (1998), “An improved approximation ratio for the minimum 
 latency problem”, Mathematical Programming, Vol.82. 
9. R. Bellman (2003), “Dynamic Programming”, Dover Publications Inc . 
10. G. L. Nemhauser and L. A. Wolsey (1998), “Interger and Combinatorial Optimization”, 
 WileyInterscience. 
11. F. Rossi, P. Van Beek, and T. Walsh (2006), “Eds. Handbook of Constraint Programming”, 
 Elsevier. 
12. V. Vazirani (2001), “Approximation Algorithms”, Springer publisher .Https://www.iwr.uni
 heidelberg.de/groups/comopt/software/TSPLIB95/ 
 APPLYING PARTICLE SWARM OPTIMIZATION 
 FOR MINIMUM LATENCY PROBLEM 
 Abstract: Minimum Latency Problem – MLP is one of the class of combinational 
 optimization problems that has many practical applications. In the general case, the MLP 
 is proved to be NPhard. In fact, there are many the approaches to solve the problem. 
 One of them is using metaheuristic. This algorithms imitate follow a action of some 
 swarm in the nature. In this paper, we propose are apply algorithm particle swarm 
 optimization for solve MLP with a lager size. The results show that is an efficient 
 approaches for minimum latency problems. 
 Keywords: Minimum latency problems, Particle Swarm Optimization, meta – heuristic, 
 GA – Genetic Algorithm.