Báo cáo khoa học: Hệ cộng dồn mùi cải tiến trong Hệ cộng dồn mùi cải tiến

Chia sẻ: Nguyễn Phi Nhung Nhung | Ngày: | Loại File: PDF | Số trang:8

Thêm vào BST

Báo xấu

60
lượt xem 7
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

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 X ? Rn . 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...

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Báo cáo khoa học: Hệ cộng dồn mùi cải tiến trong Hệ cộng dồn mùi cải tiến

Báo cáo khoa học Hệ cộng dồn mùi cải tiến trong tối ưu hóa bầy kiến
§¹i häc N«ng nghiÖp I T¹p chÝ KHKT N«ng nghiÖp 2007: TËp V, Sè 4: 60-66 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. nhiªn míi mÎ hiÖn nay: trÝ tuÖ bÇy ®µn (swarm 1. §ÆT VÊN §Ò intelligence) (Engelbrecht A.P., 2005). Môc Trong c¸c nghiªn cøu vÒ n«ng nghiÖp vµ ®Ých cña nh÷ng m« h×nh tÝnh to¸n trÝ tuÖ bÇy sinh häc, chóng ta gÆp nhiÒu bµi to¸n tèi −u. ®µn lµ m« pháng tËp qu¸n ®¬n gi¶n vµ nh÷ng NhiÖm vô chÝnh cña c¸c bµi to¸n nµy lµ ph¶i t¸c ®éng côc bé ®èi víi m«i tr−êng xung quanh x©y dùng mét ph−¬ng ph¸p hiÖu qu¶ ®Ó t×m ra cña tõng c¸ thÓ, tõ ®ã thu ®−îc nh÷ng tËp qu¸n nh÷ng gi¶i ph¸p tèi −u nhÊt. VÊn ®Ò nµy, thùc cña bÇy ®µn phøc t¹p h¬n cã thÓ ®−îc sö dông chÊt ®−îc ®−a vÒ bµi to¸n t×m gi¸ trÞ nhá nhÊt ®Ó gi¶i quyÕt nh÷ng bµi to¸n khã trong thùc tÕ, cña mét hµm sè f ( x) trªn miÒn X ⊂ R n . 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 Trong nh÷ng n¨m gÇn ®©y, mét sè nghiªn cøu nhÊt cña bÇy kiÕn khi kiÕm ¨n. Khi ®i ®Õn (Bilchev G. and Parmee I. C., 1995; Dreo J. nguån thøc ¨n, tõng con kiÕn tiÕt ra “mïi” and Siarry P., 2002; Pourtakdoust S.H. and (pheromone) trªn ®−êng ®i vµ thÝch chän Nobahari H., 2004; Socha K., 2004; Tsutsui S., nh÷ng ®−êng ®i cã nång ®é “mïi” cao. Do ®ã, 2006; Wodrich M. and Bilchev G., 1997) ®· nh÷ng ®−êng ®i ng¾n nhÊt cã nhiÒu kh¶ n¨ng triÓn khai mét sè ph−¬ng ph¸p tiÕp cËn ph−¬ng cµng ngµy nång ®é “mïi” cµng t¨ng vµ ®−îc ph¸p tèi −u hãa bÇy kiÕn (ACO) ®Ó gi¶i bµi nhiÒu kiÕn lùa chän h¬n. to¸n tèi −u liªn tôc trªn. Ph−¬ng ph¸p ACO, vÒ nghiªn cøu thùc Ph−¬ng ph¸p ACO lµ mét ph−¬ng ph¸p nghiÖm, ®· ®−îc ¸p dông rÊt thµnh c«ng trong tÝnh to¸n hiÖu qu¶ trong lÜnh vùc tÝnh to¸n tù * Khoa C«ng nghÖ th«ng tin, §¹i häc N«ng nghiÖp I . 66
HÖ céng dån “mïi” c¶i tiÕn trong tèi −u hãa bÇy kiÕn thµnh thuËt to¸n eAPS vµo n¨m 2006 (Tsutsui nhiÒu bµi to¸n tèi −u rêi r¹c NP-khã. Tuy S., 2006). nhiªn, vÒ c¬ së lý thuyÕt to¸n häc, chØ cã mét sè thuËt to¸n trong nh÷ng nghiªn cøu ®ã ®¶m 2.1. Sù céng dån “mïi” b¶o sÏ t×m ®−îc lêi gi¶i tèi −u toµn côc (Engelbrecht A.P., 2005). Mét sè nghiªn cøu Trong thùc tÕ, sù céng dån “mïi” ®−îc thùc nghiÖm vÒ ph−¬ng ph¸p ACO cho nh÷ng sinh bëi mét sè loµi c«n trïng ®Ó chia sÎ th«ng bµi to¸n tèi −u liªn tôc còng b¾t ®Çu ®−îc c«ng tin vÒ nguån thøc ¨n, n¬i Èn nÊp an toµn, sù thu bè trong nh÷ng n¨m gÇn ®©y, trong ®ã cã hai hót giíi tÝnh hoÆc kÎ thï. Ng−êi ta ®· quan s¸t thuËt to¸n APS vµ eAPS (Tsutsui S., 2006). APS ®−îc rÊt nhiÒu chøc n¨ng cña hµnh ®éng céng vµ eAPS thay thÕ dÊu vÕt “mïi” trong ACO cæ dån “mïi” nh− ®¸nh dÊu nguån thøc ¨n, t×m ®iÓn b»ng hµm céng dån “mïi”, cßn quy luËt kiÕm n¬i Èn nÊp, kÕt b¹n hoÆc tù vÖ. Khi mét cËp nhËt hµm céng dån “mïi" hoµn toµn t−¬ng con gi¸n thÊy mét chç Èn nÊp an toµn, nã sÏ tù víi quy luËt cËp nhËt dÊu vÕt “mïi” trong tiÕt ra mét lo¹i “mïi” ®Æc biÖt trong ph©n cña ACO ®· ®−îc ¸p dông cho c¸c bµi to¸n tèi −u nã ®Ó thu hót nh÷ng con gi¸n kh¸c. Sù kh¸c rêi r¹c. Lóc nµy, hµm mËt ®é céng dån “mïi” biÖt gi÷a ACO vµ APS chÝnh lµ ë chøc n¨ng cña trë thµnh tæ hîp tuyÕn tÝnh cña nh÷ng hµm mËt “mïi” trong kh«ng gian t×m kiÕm. Trong ACO ®é ph©n phèi chuÈn nhiÒu chiÒu. APS còng nh− nång ®é “mïi” ®−îc x¸c ®Þnh lµ dÊu vÕt trªn eAPS cã thÓ gi¶i quyÕt thµnh c«ng mét sè bµi mçi ®Ønh hoÆc trªn mçi c¹nh gi÷a c¸c ®Ønh cña to¸n tèi −u liªn tôc NP-khã. Tuy nhiªn, hai ®å thÞ t×m kiÕm. Cßn trong APS, hµm mËt ®é thuËt to¸n trªn còng nh− tÊt c¶ c¸c thuËt to¸n céng dån “mïi” ®−îc x¸c ®Þnh lµ hµm mËt ®é ¸p dông ph−¬ng ph¸p ACO cho nh÷ng bµi to¸n trong kh«ng gian t×m kiÕm X ⊂ R n . Mçi vßng tèi −u liªn tôc kh¸c (Bilchev G. and Parmee I. lÆp cña APS gåm hai b−íc c¬ b¶n: C., 1995; Dreo J. and Siarry P., 2002; CËp nhËt hµm mËt ®é céng dån “mïi” Pourtakdoust S.H. and Nobahari H., 2004; Socha K., 2004; Wodrich M. and Bilchev G., Sinh ra “c¸c kiÕn” míi nhê vµo hµm mËt 1997) do qu¸ chó träng vµo t×m kiÕm “s©u” nªn ®é céng dån “mïi” t¹i thêi ®iÓm hiÖn t¹i. kh«ng ®¶m b¶o lu«n t×m ®−îc lêi gi¶i tèi −u 2.2. CËp nhËt hµm mËt ®é céng dån “mïi” toµn côc (theo c¸c tµi liÖu chóng t«i thu thËp ®−îc cho tíi nay). §Æt τ ( t , x ) lµ hµm mËt ®é (density) céng Trong bµi b¸o nµy, chóng t«i ®Ò xuÊt mét dån “mïi” trong vßng lÆp t . APS khëi líp thuËt to¸n iAPS c¶i tiÕn cña thuËt to¸n APS t¹o τ (0, x)=τ min ( 0,x ) = c . Do ®ã, m “kiÕn” cho nh÷ng bµi to¸n tèi −u liªn tôc. Líp thuËt to¸n iAPS lµ líp thuËt to¸n xÊp xØ víi thuËt míi ban ®Çu ®−îc sinh ra ngÉu nhiªn theo ph©n to¸n APS. H¬n n÷a, nhê sù c©n b»ng gi÷a t×m phèi ®Òu trªn toµn bé kh«ng gian t×m kiÕm X . kiÕm “réng” vµ t×m kiÕm “s©u” mµ líp thuËt §Ó ®¶m b¶o “kiÕn” ®−îc sinh ra nhiÒu h¬n t¹i to¸n nµy cã kh¶ n¨ng t×m kiÕm ®−îc lêi gi¶i tèi nh÷ng vÞ trÝ cã mËt ®é céng dån “mïi” cao, trong vßng lÆp t , c¸c “kiÕn” míi ®−îc sinh ra −u toµn côc tèt h¬n so víi hai thuËt to¸n APS vµ eAPS ®Æc biÖt trong nh÷ng bµi to¸n tèi −u ngÉu nhiªn theo ph©n phèi x¸c suÊt pτ (t , x) liªn tôc cã nhiÒu cùc trÞ ®Þa ph−¬ng. C¸c môc x¸c ®Þnh nh− sau: tiÕp theo cña bµi b¸o ®−îc s¾p xÕp nh− sau. τ (t, x ) Môc 2 giíi thiÖu m« h×nh c¬ b¶n hÖ céng dån pτ (t , x) = (1) ∫ τ ( t , x ) dx “mïi” APS. Trªn c¬ së môc 2, môc 3 tr×nh bµy nh÷ng c¶i tiÕn cña líp thuËt to¸n iAPS. Môc 4 X kÕt luËn bµi b¸o nµy. Sau khi ®−îc sinh ra, mçi “kiÕn” míi sÏ ph¸t ra “mïi” trong l©n cËn cña nã. §Ó ®¶m 2. M¤ H×NH C¥ B¶N HÖ CéNG DåN “MïI” b¶o nång ®é (intensity) “mïi” cµng t¨ng khi APS cµng gÇn mçi “kiÕn”, ®Æc biÖt lµ víi c¸c “kiÕn” tèt nhÊt, còng nh− ®Ó gi¶m bít nh÷ng biÕn ®æi ThuËt to¸n APS ®−îc S. Tsutsui, M. tuyÕn tÝnh trong kh«ng gian t×m kiÕm, cã thÓ Peklikan, A. Ghosh ®−a ra lÇn ®Çu tiªn vµo cËp nhËt “mïi” cho “kiÕn” xt ,r nh− sau: n¨m 2005 vµ sau ®ã, ®−îc S. Tsutsui n©ng cÊp 67
NguyÔn Hoµng Huy, NguyÔn H¶i Thanh ∆τ ' ( t , r ; xt ,r ; x ) = f ( x) cµng nhá, “kiÕn” tèt nhÊt trong m kiÕn ë C r α N ( x; xt ,r ; β 2 ∑ t ) m vßng lÆp nµy ®−îc m ®iÓm cßn kiÕn tåi nhÊt ∑ kα ®−îc 1 ®iÓm). k =1 N ( x; xt ,r ; β 2 ∑t ) lµ hµm mËt ®é ph©n (2) Trong ®ã r lµ sè ®iÓm ®¹t ®−îc cña phèi x¸c suÊt cña biÕn ngÉu nhiªn chuÈn n “kiÕn” trong vßng lÆp t (sè ®iÓm r cña “kiÕn” chiÒu: xt ,r cµng t¨ng khi gi¸ trÞ cña hµm sè ⎧1 ⎫ N ( x; xt ,r ; β 2 ∑t ) = exp ⎨− ( x − xt ,r ) ∑t−1 ( x − xt ,r ) ⎬ 1 T ( 2π ) ⎩2 ⎭ ∑t 1/ 2 1/ 2 { xt,r } m ∑ ; α , β lµ c¸c tham sè ®iÒu khiÓn lµ ma trËn hiÖp ph−¬ng sai cña mÉu t r =1 (α , β > 0 ) . C lµ tæng nång ®é “mïi” trªn toµn kh«ng gian t×m kiÕm X . Khi ®ã, céng dån mËt ®é “mïi” tiÕt ra bëi tÊt c¶ m “kiÕn” ë vßng lÆp thø t sÏ cã: m ∆τ ( t , x ) = ∑ ∆τ ' ( t ; r ; xt ,r ; x ) víi t ≥ 1 (3) vµ ®Æt ∆τ (0, x) = c (4) r =1 Víi c¸ch x©y dùng nh− trªn, thuËt to¸n APS lu«n ®¶m b¶o ∫ τ ( 0, x ) dx = ∫ τ ( 0, x ) dx = ∫ ∆τ (0, x)dx = ∫ cdx = C (5) vµ ∫ ∆τ ( t , x ) = C (6) min X X X X X §iÒu nµy rÊt quan träng trong qu¸ tr×nh t τ ( t + 1, x ) = ρ t +1τ ( 0, x ) + ∑ ρ h ∆τ (t − h, x) sinh ngÉu nhiªn “kiÕn” míi. Sù céng dån mËt h=0 ®é “mïi’ ®−îc cËp nhËt trong c«ng thøc sau: (8) τ ( t + 1, x ) = ρτ ( t , x ) + ∆τ ( t , x ) (7) §Ó thùc hiÖn qu¸ tr×nh sinh ngÉu nhiªn Trong ®ã h»ng sè ρ ( 0 ≤ ρ < 1) lµ tû lÖ “c¸c kiÕn” míi, cÇn ph¶i cã hµm mËt ®é ph©n phèi x¸c suÊt pτ ( t + 1, x ) tõ hµm mËt ®é céng bay h¬i cña “mïi”. dån “mïi” τ ( t + 1, x ) . Tõ ph−¬ng tr×nh (1), 2.3. Sinh ngÉu nhiªn “c¸c kiÕn” míi (5), (6), (8) ta cã: Tõ quy luËt cËp nhËt mËt ®é “mïi” trong ph−¬ng tr×nh (7), hµm mËt ®é céng dån “mïi” cña APS ®−îc x¸c ®Þnh bëi c«ng thøc sau: ∆τ ( t − h, x ) ρ t +1 τ ( 0, x ) ρh t pτ ( t + 1, x ) = ∑ + t +1 . . (9) t +1 ∑ρ ∑ρ C C h =0 k k k =0 t =0 XÐt hµm mËt ®é ph©n phèi x¸c suÊt f ( x) tæng qu¸t d−íi d¹ng tæ hîp tuyÕn tÝnh cña c¸c hµm mËt ®é ph©n phèi x¸c suÊt f ( x) = p1 f1 ( x ) + p2 f 2 ( x ) + .... + ps f s ( x ) . (10) 68
HÖ céng dån “mïi” c¶i tiÕn trong tèi −u hãa bÇy kiÕn t +1 s ∑ρ ∑ pi = 1 th× qu¸ tr×nh sinh ngÉu pi = ρ i k (11) Víi k =0 i =1 nhiªn “c¸c kiÕn” míi theo hµm mËt ®é ph©n vµ thµnh phÇn thø i lµ: phèi x¸c suÊt f ( x) ®−îc tiÕn hµnh nh− sau: ⎧τ (0, x) C khi i = t + 1 fi ( x ) = ⎨ (12) Chän thµnh phÇn f i ( x) víi x¸c suÊt pi . ⎩∆τ (t − i, x) C khi i ≤ t Sinh ngÉu nhiªn “c¸c kiÕn” míi theo hµm Qu¸ tr×nh sinh ngÉu nhiªn “c¸c kiÕn” míi mËt ®é ph©n phèi x¸c suÊt f i ( x) võa chän. theo thµnh phÇn cuèi cïng ft +1 ( x) lµ ®¬n gi¶n Chó ý r»ng pτ ( t + 1, x ) lµ tæ hîp tuyÕn v× ft +1 ( x) lµ hµm h»ng, nªn nã lµ hµm mËt ®é tÝnh cña t + 1 ph©n phèi chuÈn nhiÒu chiÒu vµ cña ph©n bè ®Òu trªn toµn kh«ng gian t×m mét phÇn phèi ®Òu. Do ®ã “c¸c kiÕn” míi cã kiÕm. Nh÷ng thµnh phÇn cßn l¹i f i (t ) víi thÓ ®−îc sinh ngÉu nhiªn b»ng c¸ch sö dông i ≤ t lµ tæ hîp tuyÕn tÝnh cña m thµnh phÇn: thñ tôc võa nªu trong ®ã x¸c suÊt chän thµnh phÇn thø i lµ: ∆τ ( t − i, x ) m r α .N ( x; xt −i , r ; β 2 ∑ t −i ) =∑ m (13) ∑ kα C r =1 k =1 Do ®ã, viÖc sinh ngÉu nhiªn “c¸c kiÕn” 2.4. S¬ ®å thuËt to¸n APS míi theo hµm mËt ®é ph©n phèi x¸c suÊt fi (t ) C¸c b−íc cña thuËt to¸n APS víi i ≤ t cã thÓ ®−îc lµm t−¬ng tù nh− trªn víi Khëi t¹o vßng lÆp cña APS: t := 0 . x¸c suÊt chän thµnh phÇn thø r N(x, x t-i,r ,β 2 ∑t −i ) lµ : Khëi t¹o hµm mËt ®é céng dån “mïi” τ (0, x) = c , ∆τ (0, x) = c vµ khëi t¹o sinh m ngÉu nhiªn m “kiÕn” míi P(t ) theo ph©n phèi ∑ kα pr = r α (14) ®Òu. k =1 §¸nh gi¸ P(t ) vµ ®−a ra sè ®iÓm r cña Do mçi thµnh phÇn thø r cña vÕ ph¶i mçi “kiÕn”. (13) lµ hµm mËt ®é ph©n phèi chuÈn, viÖc sinh ∑ cña m “kiÕn” P(t ) . TÝnh ma trËn “c¸c kiÕn” míi cã thÓ sinh ngÉu nhiªn nhê t ph©n ho¹ch Cholesky (Suli E. and Mayers CËp nhËt hµm mËt ®é céng dån “mïi” D.F., 2003). τ ( t + 1, x ) theo ph−¬ng tr×nh (7). Khi t ®ñ lín, viÖc tÝnh pτ ( t + 1, x ) theo L−u tr÷ m “kiÕn” vµo E (t ) . ph−¬ng tr×nh (9) ®ßi hái ph¶i l−u tr÷ mét sè ∑ l−îng lín c¸c d÷ liÖu xt − h ,r ; β 2 Sinh ngÉu nhiªn m “kiÕn” míi P(t ) theo t − h . Trong tr−êng hîp nµy, ρ ≈ 0 víi t ≥ H vµ H ®ñ hµm mËt ®é ph©n phèi x¸c suÊt x¸c ®Þnh ë t ph−¬ng tr×nh (9) ®èi víi t < H , trong ph−¬ng lín, nªn ®Ó kh¾c phôc ®iÒu ®ã thuËt to¸n APS tr×nh (15) tíi t ≥ H xÊp xØ pτ ( t + 1, x ) trong (9) bëi: Chän m “kiÕn” nh©n t¹o tèt nhÊt tõ 2m { } “kiÕn” N ( t ) + E ( t ) ®Ó sinh ra m “kiÕn’ ∆τ ( t − h, x ) ρh H −1 pτ ( t + 1, x ) = ∑ H −1 míi trong P(t + 1) . . (15) ∑ ρk C h =0 t := t + 1 k =0 69
NguyÔn Hoµng Huy, NguyÔn H¶i Thanh NÕu ®iÒu kiÖn kÕt thóc tho¶ m·n th× dõng nh− cña ph−¬ng ph¸p ACO nãi chung. H¬n thuËt to¸n, nÕu kh«ng quay l¹i b−íc 4. n÷a, vÒ mÆt thùc nghiÖm, iAPS lµ líp thuËt to¸n xÊp xØ víi thuËt to¸n APS vµ kh¸ linh ho¹t trong viÖc ®iÓu chØnh t×m kiÕm “réng” vµ t×m 3. M¤ H×NH C¥ B¶N HÖ CéNG DåN “MïI” kiÕm “s©u”. D−íi ®©y lµ nh÷ng ®iÒu chØnh cña iAPS líp thuËt to¸n iAPS so víi thuËt to¸n APS. Do hoµn toµn tËp trung vµo t×m kiÕm “s©u” nªn APS rÊt dÔ “héi tô nhanh” tíi lêi gi¶i tèi −u 3.1. CËp nhËt hµm mËt ®é céng dån “mïi” ®Þa ph−¬ng ®ñ tèt. §Ó kh¾c phôc nh÷ng nh−îc Sau khi “kiÕn” xt ,r ®−îc sinh ra iAPS cËp ®iÓm trªn cña APS, bµi b¸o nµy xin ®Ò xuÊt mét líp thuËt to¸n c¶i tiÕn cña thuËt to¸n APS, ®ã lµ nhËt “mïi” cho “kiÕn” xt ,r nh− sau: líp thuËt to¸n iAPS. Líp thuËt to¸n nµy kh«ng lµm mÊt ®i “b¶n chÊt bÇy kiÕn” cña APS còng C (1 − τ min ( t + 1, x ) ) r α ∆τ ' ( t , r ; xt ,r ; x ) = .N ( x; xt ,r ; β 2 ∑t ) (2’) m ∑k α k =1 ct τ min ( t , x ) ®−îc chän sao cho τ min ( t , x ) = khi t ≥ N ®ñ lín vµ lim ct = a > 0 . t →∞ log t Khi ®ã, céng dån mËt ®é “mïi” tiÕt ra bëi 3.2. Sinh ngÉu nhiªn “c¸c kiÕn” míi tÊt c¶ m “kiÕn” ë vßng lÆp thø t sÏ cã: Tõ quy luËt cËp nhËt mËt ®é “mïi” trong m ∆τ ( t , x ) = ∑ ∆τ ' ( t ; r ; xt ,r ; x ) ph−¬ng tr×nh (7) ta cã hµm mËt céng dån (3’) “mïi” trong iAPS lµ: r =1 §Ó ®¶m b¶o sù t×m kiÕm “réng” ta x¸c ®Þnh mËt ®é “mïi” thªm vµo kh«ng gian t×m kiÕm trong vßng lÆp thø t lµ: ∆τ ( t , x ) = ∆τ ( t , x ) + τ min ( t + 1, x ) .c (3’’) t t τ ( t + 1, x ) = ρ t +1τ ( 0, x ) + ∑ ρ h ∆τ ( t − h; x ) = ρ t +1τ ( 0, x ) + ∑ ρ h ∆τ ( t − h, x ) h=0 h=0 (8’) t +1 t t + ∑ ρ τ min ( t + 1 − h, x ) = ∑ ρ ∆τ ( t − h ) + ∑ ρ .τ min ( t + 1 − h, x ) h h h h =0 h=0 h =0 mËt ®é céng dån “mïi” τ ( t + 1, x ) . Tõ ph−¬ng §Ó thùc hiÖn qu¸ tr×nh sinh ngÉu nhiªn “c¸c kiÕn” míi trong iAPS, cÇn ph¶i cã hµm tr×nh (1), (5), (6), (8’) ta cã: mËt ®é ph©n phèi x¸c suÊt pτ ( t + 1, x ) tõ hµm ρ h (1 − τ min ( t + 1 − h, x ) ) ∆τ ( t − h, x ) t pτ ( t + 1, x ) = ∑ . C (1 − τ min ( t + 1 − h, x ) ) t +1 ∑ρ h =0 k k =0 (9’) ρ .τ min ( t + 1 − h, x ) τ ( 0, x ) t +1 h +∑ . . t +1 ∑ ρk C h =0 k =0 70
HÖ céng dån “mïi” c¶i tiÕn trong tèi −u hãa bÇy kiÕn Chó ý r»ng pτ ( t + 1, x ) lµ tæ hîp tuyÕn thñ tôc võa nªu trong ®ã x¸c suÊt chän thµnh phÇn thø i lµ: tÝnh cña t + 1 ph©n phèi chuÈn nhiÒu chiÒu vµ mét ph©n phèi ®Òu. Do ®ã, “c¸c kiÕn” míi cã thÓ ®−îc sinh ngÉu nhiªn b»ng c¸ch sö dông ρ i ⎡1 − τ min ( t + 1 − i, x ) ⎤ ⎧ ⎣ ⎦ ⎪ pi = i = 0,1, 2, ..., t t +1 ⎪ ∑ ρk ⎪ k =0 ⎪ ⎨ t +1 (1 1 ’) ∑ ρ h .τ min ( t + 1 − h, x ) ⎪ ⎪ pt +1 = h =0 t +1 ⎪ ∑ ρk ⎪ ⎩ k =0 vµ thµnh phÇn thø i lµ: ⎧τ ( 0, x ) khi i = t + 1 ⎪ ⎪C fi ( x ) = ⎨ (1 2 ’) ∆τ ( t − i, x ) ⎪ khi i ≤ t ⎪ C (1 − τ min ( t + 1 − i, x ) ) ⎩ Qu¸ tr×nh sinh ngÉu nhiªn “c¸c kiÕn” míi kiÕm. Nh÷ng thµnh phÇn cßn l¹i f i (t ) víi i ≤ t lµ tæ hîp tuyÕn tÝnh cña m thµnh phÇn: theo thµnh phÇn cuèi cïng ft +1 ( x) lµ ®¬n gi¶n v× ft +1 ( x) lµ hµm h»ng, nªn nã lµ hµm mËt ®é cña ph©n phèi ®Òu trªn toµn kh«ng gian t×m ∆τ ( t − i, x ) rα .N ( x; xt −i , r ; β 2 ∑ t −i ) m =∑ (13’) C (1 − τ min ( t + 1 − i, x ) ) m ∑k α r =1 k =1 Do ®ã, viÖc sinh ngÉu nhiªn “c¸c kiÕn” míi theo hµm mËt ®é ph©n phèi x¸c suÊt fi (t ) Khi t ®ñ lín, iAPS xÊp xØ: víi i ≤ t cã thÓ ®−îc lµm t−¬ng tù nh− trong APS. τ ( 0, x ) ρh H −1 pτ ( t + 1, x ) = ∑ H −1 τ min ( t + 1 − h, x ) . ∑ρ C h=0 k k =0 (15’) ∆τ ( t − h, x ) ρ H −1 h + ∑ H −1 ⎡1 − τ min ( t + 1 − h, x ) ⎤ . ⎣ ⎦ C ⎡1 − τ min ( t + 1 − h, x ) ⎤ ∑ρ ⎣ ⎦ h=0 k k =0 vµ b−íc sinh ngÉu nhiªn “c¸c kiÕn” míi. Trong 3.3. S¬ ®å líp thuËt to¸n iAPS iAPS, ®iÒu kiÖn kÕt thóc cã thÓ lµ: sè vßng lÆp S¬ ®å líp thuËt to¸n iAPS gåm c¸c b−íc v−ît qu¸ mét sè cho phÐp, sè vßng lÆp liªn tiÕp t−¬ng tù s¬ ®å thuËt to¸n APS. iAPS kh¸c APS mµ kh«ng c¶i thiÖn ®−îc lêi gi¶i v−ît qu¸ sè ë b−íc cËp nhËt hµm mËt ®é céng dån “mïi” lÇn cho phÐp… H¬n n÷a, trong líp thuËt to¸n 71
NguyÔn Hoµng Huy, NguyÔn H¶i Thanh AISB Workshop on Evo. Comp, p. 24 - iAPS, ngoµi c¸c ®iÒu kiÖn kÕt thóc nh− trªn cßn 39. cã bæ sung mét ®iÒu kiÖn kÕt thóc kh¸c. Do khi líp thuËt to¸n iAPS héi tô ®Õn lêi gi¶i tèi −u Dreo J., P. Siarry (2002). A new ant colony toµn côc, nång ®é “mïi” hÇu nh− tËp trung algorithm using the heterarchical xung quanh lêi gi¶i ®ã nªn thuËt to¸n iAPS cã concept aimed at optimization of thÓ kÕt thóc khi tæng nång ®é “mïi” trong mét multiminima continuous functions. Proc. l©n cËn cña lêi gi¶i tèt nhÊt v−ît qu¸ mét sè of the Third Int. Workshop on Ant cho phÐp. Algorithms, p. 216 - 221. Engelbrecht A.P. (2005). Fundamentals of 4. KÕT LUËN Computational Swarm Intelligence. John So víi hai thuËt to¸n APS vµ eAPS, líp Wiley & Sons, Chichester, p. 361-510. thuËt to¸n iAPS c©n b»ng ®−îc sù t×m kiÕm Pourtakdoust S.H., H. Nobahari (2004). An “s©u” vµ t×m kiÕm “réng” mét c¸ch hiÖu qu¶. extension of ant colony system to Do ®ã, khi ¸p dông líp thuËt to¸n iAPS, kh¶ continuous optimization problems. Proc. n¨ng t×m ®−îc lêi gi¶i tèi −u toµn côc lµ cao of Fourth Int. Workshop on Ant Colony h¬n APS vµ eAPS. Trong khi ®ã, do chØ chó Optimization and Swarm Intelligence, p. träng ®Õn kh¶ n¨ng t×m kiÕm “s©u”, nªn c¸c 294-301. thuËt to¸n APS vµ eAPS rÊt dÔ bÞ “m¾c c¹n” t¹i Socha K. (2004). ACO for continuous and lêi gi¶i tèi −u ®Þa ph−¬ng. mixed-variable optimization. Proc. of Chóng t«i ®Ò xuÊt tiÕp tôc hoµn thµnh Fourth Int. Workshop on Ant Colony nh÷ng ®Þnh lý vÒ c¬ së lý thuyÕt to¸n häc nh»m Optimization and Swarm Intellgence, p. chØ ra nh÷ng ®iÒu kiÖn lµm cho thuËt to¸n APS 25-36. vµ eAPS kh«ng héi tô tíi lêi gi¶i tèi −u toµn Suli E., D. F. Mayers (2003). An Introduction côc. §ång thêi, tiÕp tôc hoµn thµnh chøng to Numerical Analysis. Cambridge minh tÝnh héi tô cña líp thuËt to¸n iAPS còng University press, Cambridge, p. 39-91. nh− ®¸nh gi¸ vÒ ®é phøc t¹p cña líp thuËt to¸n nµy nh»m c¶i tiÕn líp thuËt to¸n iAPS cã tèc ®é Tsutsui S. (2006). An Enhanced Aggregation héi tô tèt h¬n. H¬n n÷a, còng cÇn cã nh÷ng Pheromone System for Real-Prameter nghiªn cøu tÝnh to¸n so s¸nh líp thuËt to¸n nµy Optimization in the ACO Metaphor. víi c¸c thuËt to¸n tèi −u kh¸c trªn c¸c bµi to¸n Proc. of the Fifth Int. Workshop on Ant tèi −u mÉu. Colony Optimization and Swarm Intelligence, p. 60-71. Hy väng líp thuËt to¸n iAPS sím ®−îc cµi ®Æt, khai th¸c sö dông ®Ó gi¶i quyÕt c¸c bµi Wodrich M., G.Bilchev (1997). Cooperative to¸n tèi −u trong nh÷ng lÜnh vùc kh¸c nhau distribution search: the ant’s way. trong ®ã cã c¸c bµi to¸n tin sinh häc. Control Cybernetics 3, p. 413-446. TµI LIÖU THAM KH¶O Bilchev G., I. C. Parmee (1995). The ant colony metaphor for searching continous design spaces. Proc. of the 72