TẠP CHÍ KHOA HỌC VÀ CÔNG NGHỆ, ĐẠI HỌC ĐÀ NẴNG - SỐ 5(40).2010

9
ỨNG DỤNG GIẢI THUẬT META-HEURISTIC
TRONG BÀI TOÁN TÌM ĐƯỜNG ĐI NGẮN NHẤT
APPLICATION OF META-HEURISTIC ALGORITHM
FOR A SEARCH OF SHORTEST PATH Đoàn Duy Bình
Trường Đại học Sư phạm, Đại học Đà Nẵng

TÓM TẮT
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 giải các bài
toán tìm kiếm tối ưu toàn cục đã có nhiều ứng dụng thực tế như: tìm kiếm các trang web cần
tìm trên mạng, kế hoạch sắp xếp thời khóa biểu cho các y tá trong bệnh viện, tìm kiếm đường
đi tối ưu cho những ng
ười lái xe hơi… đấy là thuật toán kiến (ACS – Ant Colony Search hoặc
ACO - Ant Colony Optimization). Trong bài báo này chúng tôi giải thuật Meta-Heuristic và đặc
biệt là thuật toán kiến để thực hiện bài toán tìm kiếm. Thuật toán kiến mô phỏng hành vi của
đàn kiến trong tự nhiên nhằm tìm kiếm đường đi ngắn nhất giữa tổ kiến và nguồn thức ăn dựa
trên mật độ mùi - Pheromone mà các con kiến để lại trên đường đi.

ABSTRACT
Search problem is a problem that concerns many people, especially in the field of
global optimal search. An algorithm is considered to be a well-established theory in solving
problems of globally optimal search and it has many practical applications such as searching for
pages needed to be found on the web, planning a schedule for the nurses in hospitals, finding
an optimal way for people to drive,etc That is an ant algorithm (ACS - Ant Colony Search or
ACO - Ant Colony Optimization). In this paper, we introduce the Meta-Heuristic algorithm,

sl
llr /
=
gia  dài hai nhánh ca
cây cu,
l
l là  dài ca nhánh dài và
s
l là  dài ca nhánh ngn hn. Trong th
nghim u tiên vi cây cu có hai nhánh chiu dài bng nhau (r = 1; xem hình 1.1a). . Hình 1. Thí nghiệm chiếc cầu đôi. (a) Hai nhánh có kích thước bằng nhau,
(b) Một nhánh có kích thước gấp đôi nhánh kia
Khi bt u, trên 2 nhánh ca cây cu u cha có pheromones. Do ó, các con
kin có th chn mt trong các nhánh vi cùng mt xác sut. Tuy nhiên, do s la chn
là ngu nhiên lên sau mt thi gian s lng kin i trên nhng chi nhánh s là khác
nhau. Bi vì loài kin s gi pheromones trong khi di chuyn, dn dn s lng
pheromones trên nhng nhánh cng s khác nhau, iu này càng kích thích thêm àn
kin s la chn nhánh có lng mùi pheromones ln, và nh vy n mt thi gian nào
ó tt c àn kin s hi t v cùng mt nhánh.

s
giây, vi r=l
l
/l
s
.
Xác sut p
ia
(t) là xác xut ti im i (i  {1,2}) (xem hình 1.1b) kin chn nhánh
a (a  {s,l}), trong ó s, l là các chi nhánh ngn và dài tng ng, ti thi im t tng s
lng pheromones 
ia
(t) c thit lp trên các chi nhánh, là tng lng pheromones
mà các loài kin  li trên các chi nhánh cho n thi gian t ó.
Trong mô hình này àn kin gi li vt mùi pheromones ca h trên c hai
ng i: t t n ngun thc n và quay tr li t. S di chuyn này là mt hành vi
ng x cn thit  có c s hi t ca àn kin hng v nhánh ngn.
2. Đàn kiến nhân tạo
Qua th nghim chic cu ôi 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:
- 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.
- ây là thí 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.
3. Kiến nhân tạo và chi phí tối thiểu trên đường đi
Nhng hành vi là:
1. Gii pháp xây dng theo hng xác xut bi vt mùi pheromones, vi s cp
nht pheromones nhanh


tính xác sut chn nh j nh sau:
Trong ó
k
I
N là vùng lân cn ca kin k  nh i trong S-ACO vùng lân cn ca
nh i là tt c các nh kt ni trc tip n nh i trong  th G =(N,A), ngoi tr tt
c các nh trc (ví d, các nh trc khi di chuyn n nh i ca kin).
Đường đi về tổ và sự cập nhập vết mùi. Khi t ti nh ích, kin thc hin quá
trình quay v t trên cùng con ng n ngun thc phm. B sung tính nng này là,
trc khi bt u quá trình quay v t, kin s loi b nhng ng i ri vào tình trng
vòng lp mà nó ã gp phi trên ng i tìm n ngun thc n.
Trong thi gian quay tr v t con kin th k s  li mt lng ∆τ
k
pheromones
trên các cnh mà nó i qua. Trong ó, nu kin th k quay tr v t trên cnh (i,j), thì
giá tr
ij
τ
pheromones s thay i nh sau:

k
ijij
τττ
∆+← (1.9)
Mt khía cnh quan trng vn là s la chn ca ∆τ
k
. Trong nhng trng hp
n gin nht, giá tr ca ∆τ
k

τ
τ
α
il
N
k
i
l
ij
k
ij
p
(1.8)
TẠP CHÍ KHOA HỌC VÀ CÔNG NGHỆ, ĐẠI HỌC ĐÀ NẴNG - SỐ 5(40).2010

13
Trong ó tham s (0,1]. Sau khi s bay hi pheromones ã c áp dng cho
tt c các cnh, s lng pheromones ∆τ
k
s c thêm vào các cnh.
2. Các ACO METAHEURISTIC
2.1. Trình bày vấn đề
Chúng tôi xem xét các vn  cc tiu hoá (
Ω
,, fS ). Trong ó S là ni tp hp
các gii pháp c xét, f là mc tiêu ca chc nng quan trng, trong ó quy nh giá tr
ca chc nng ó là mt hng s ),( tsf ca mi gii pháp
Ss
∈
và )(tΩ là mt tp

ScheduleActivities
ConstructAntsSolutions
UpdatePheromones
DaemonActions % optionnal
End-ScheduleActivities
End-procedure.
TẠP CHÍ KHOA HỌC VÀ CÔNG NGHỆ, ĐẠI HỌC ĐÀ NẴNG - SỐ 5(40).2010

14
S  thut toán ACO cho bài toán TSP
ghé thm
Ghi li  dài ca cuc hành
trình và xoá danh sách
visited
Xác nh hành trình ngn
nht t trc n nay và
cp nht pheromone
S vòng lp ti
a ã c thc
hin
Kết thúc
TẠP CHÍ KHOA HỌC VÀ CÔNG NGHỆ, ĐẠI HỌC ĐÀ NẴNG - SỐ 5(40).2010

15
Mi cung (i,j) thuc A c gán mt giá tr d
ij
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 ích cui cùng ca bài toán ngi di lch chính là tìm
ra chu trình Hamilton ngn nht ca  th G có n nh vi n là s thành ph mà ngi
di lch 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 f() là nh nht. f() c tính theo công thc sau:
5.1. Giải thuật ACO cho bài toán người di 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 các thành ph.  ây bài toán tìm
ng

i
∈
TẠP CHÍ KHOA HỌC VÀ CÔNG NGHỆ, ĐẠI HỌC ĐÀ NẴNG - SỐ 5(40).2010

16
vi 
ij
=1/ d
ij
là giá tr Heuristic có th có, α và β là hai tham s quyt nh s nh hng
ln nhau ca các pheromones trên các hành trình c xây dng và các thông tin
Heuristic. N
i
k
là nhng thành ph mà con kin k có th i n, t v trí hin ti là thành
ph i ( ây là các thành ph mà con kin này cha ving thm bao gi). Vi tp lut
nh trên, kh nng la chn mt cung (i,j) t l thun vi giá tr ca các pheromones có
liên quan 
ij
và ca giá tr heuristic 
ij
.
Sau khi tt cá các hành trình c xây dng, các pheromone bt u c cp
nht. Vic cp nht c thc hin bng cách gim mt  pheromone trên tt c các
cung ca  th, sau ó thêm pheromone trên các hành trình mà con kin ã i qua. Vic
xóa các du c thc hin nh sau:
τ
ij
← (1-ρ)τ
ij

c xây dng bi con kin th k, c tính bng
tng chiu dài ca các cung thuc T
k
.

TÀI LIỆU THAM KHẢO
[1]. M. Dorigo and Thomas Stützle. Ant Colony Optimization, papes 17-20. McGraw
Hill, London, UK, 2004
[2]. M. Dorigo and Thomas St
ützle. Ant Colony Optimization, papes 70-90. McGraw
Hill, London, UK, 2004
[3]. M. Dorigo and T. Stütxle. The ant colony optimization metaheuristic:
Algorithms,
applications and advances
. Technical Report IRIDIA/2000-32, IRRIDIA,
Université Libre de Bruxelles, Belgium, 2000.