Hệ cộng dồn "mùi" cải tiến trong tối ưu hóa bầy kiến

T¹p chÝ KHKT N«ng nghiÖp 2007: TËp V, Sè 4: 60-66 §¹i häc N«ng nghiÖp I

HÖ CéNG DåN “MïI” C¶I TIÕN TRONG TèI ¦U HãA BÇY KIÕN

An Improved Aggregation Pheromone System in the Ant Colony Optimization

NguyÔn Hoµng Huy*

, NguyÔn H¶i Thanh*

SUMMARY

As a bio-inspired computational paradigm, Ant colony optimization (ACO) has been

applied with great success to a large number of discrete optimization problems. However, up to

now, there are few adaptations of ACO to continuous optimization problems, whereas these

problems are frequent occurrence. Moreover, almost all of the adaptations use marginal

distribution models and the pheromone update rules used are quite different than those of the

original ACO algorithms. In some recent papers, Shigeyoshi Tsutsui and colleagues have

proposed two algorithms for continuous optimization called the Aggregation Pheromone

System (APS) and the enhanced APS (eAPS). These algorithms apply the same pheromone

update rule in a way similar to those of the original ACO algorithms, and as a result the

aggregation pheromone density eventually becomes a mixture of multivariate normal

probability density functions. However, both of the above algorithms do not guarantee to find

out a solution converging to an optimal solution. Based on an insight into the mathematical

techniques used to prove convergence of ACO algorithms on the discrete domain, we propose

an improved APS (iAPS). iAPS inherits APS’s ant-colony based approaches and allows a

stronger exploration of better solutions found and at the same time; it can prevent premature

stagnation of the search. Consequently, iAPS has a higher probability of finding out an optimal

solution. We hope iAPS will be applied for realistic optimization problems in agricultural fields.

Keywords: Aggregation pheromone system, Ant colony optimization (ACO), approximation

algorithm, metaheuristics.

1. §ÆT VÊN §Ò

Trong c¸c nghiªn cøu vÒ n«ng nghiÖp vµ

sinh häc, chóng ta gÆp nhiÒu bµi to¸n tèi −u.

NhiÖm vô chÝnh cña c¸c bµi to¸n nµy lµ ph¶i

x©y dùng mét ph−¬ng ph¸p hiÖu qu¶ ®Ó t×m ra

nh÷ng gi¶i ph¸p tèi −u nhÊt. VÊn ®Ò nµy, thùc

chÊt ®−îc ®−a vÒ bµi to¸n t×m gi¸ trÞ nhá nhÊt

cña mét hµm sè f (x) trªn miÒn n X ⊂ R .

Trong nh÷ng n¨m gÇn ®©y, mét sè nghiªn cøu

(Bilchev G. and Parmee I. C., 1995; Dreo J.

and Siarry P., 2002; Pourtakdoust S.H. and

Nobahari H., 2004; Socha K., 2004; Tsutsui S.,

2006; Wodrich M. and Bilchev G., 1997) ®·

triÓn khai mét sè ph−¬ng ph¸p tiÕp cËn ph−¬ng

ph¸p tèi −u hãa bÇy kiÕn (ACO) ®Ó gi¶i bµi

to¸n tèi −u liªn tôc trªn.

Ph−¬ng ph¸p ACO lµ mét ph−¬ng ph¸p

tÝnh to¸n hiÖu qu¶ trong lÜnh vùc tÝnh to¸n tù

nhiªn míi mÎ hiÖn nay: trÝ tuÖ bÇy ®µn (swarm

intelligence) (Engelbrecht A.P., 2005). Môc

®Ých cña nh÷ng m« h×nh tÝnh to¸n trÝ tuÖ bÇy

®µn lµ m« pháng tËp qu¸n ®¬n gi¶n vµ nh÷ng

t¸c ®éng côc bé ®èi víi m«i tr−êng xung quanh

cña tõng c¸ thÓ, tõ ®ã thu ®−îc nh÷ng tËp qu¸n

cña bÇy ®µn phøc t¹p h¬n cã thÓ ®−îc sö dông

®Ó gi¶i quyÕt nh÷ng bµi to¸n khã trong thùc tÕ,

chñ yÕu lµ nh÷ng bµi to¸n tèi −u. Ph−¬ng ph¸p

ACO m« pháng tËp qu¸n t×m ®−êng ®i ng¾n

nhÊt cña bÇy kiÕn khi kiÕm ¨n. Khi ®i ®Õn

nguån thøc ¨n, tõng con kiÕn tiÕt ra “mïi”

(pheromone) trªn ®−êng ®i vµ thÝch chän

nh÷ng ®−êng ®i cã nång ®é “mïi” cao. Do ®ã,

nh÷ng ®−êng ®i ng¾n nhÊt cã nhiÒu kh¶ n¨ng

cµng ngµy nång ®é “mïi” cµng t¨ng vµ ®−îc

nhiÒu kiÕn lùa chän h¬n.

Ph−¬ng ph¸p ACO, vÒ nghiªn cøu thùc

nghiÖm, ®· ®−îc ¸p dông rÊt thµnh c«ng trong

*

Khoa C«ng nghÖ th«ng tin, §¹i häc N«ng nghiÖp I .

66