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

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 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 nX 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 Hệ cộng dồn “mùi” cải tiến trong tối −u hóa bầy kiến nhiều bài toán tối −u rời rạc NP-khó. Tuy 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 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 thực nghiệm về ph−ơng pháp ACO cho những bài toán tối −u liên tục cũng bắt đầu đ−ợc công bố trong những năm gần đây, trong đó có hai thuật toán APS và eAPS (Tsutsui S., 2006). APS và eAPS thay thế dấu vết “mùi” trong ACO cổ điển bằng hàm cộng dồn “mùi”, còn quy luật cập nhật hàm cộng dồn “mùi" hoàn toàn t−ơng tự với quy luật cập nhật dấu vết “mùi” trong ACO đã đ−ợc áp dụng cho các bài toán tối −u rời rạc. Lúc này, hàm mật độ cộng dồn “mùi” trở thành tổ hợp tuyến tính của những hàm mật độ phân phối chuẩn nhiều chiều. APS cũng nh− eAPS có thể giải quyết thành công một số bài toán tối −u liên tục NP-khó. Tuy nhiên, hai thuật toán trên cũng nh− tất cả các thuật toán áp dụng ph−ơng pháp ACO cho những bài toán tối −u liên tục khác (Bilchev G. and Parmee I. C., 1995; Dreo J. and Siarry P., 2002; Pourtakdoust S.H. and Nobahari H., 2004; Socha K., 2004; Wodrich M. and Bilchev G., 1997) do quá chú trọng vào tìm kiếm “sâu” nên không đảm bảo luôn tìm đ−ợc lời giải tối −u toàn cục (theo các tài liệu chúng tôi thu thập đ−ợc cho tới nay). Trong bài báo này, chúng tôi đề xuất một lớp thuật toán iAPS cải tiến của thuật toán APS 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 toán APS. Hơn nữa, nhờ sự cân bằng giữa tìm kiếm “rộng” và tìm kiếm “sâu” mà lớp thuật toán này có khả năng tìm kiếm đ−ợc lời giải tối −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 liên tục có nhiều cực trị địa ph−ơng. Các mục tiếp theo của bài báo đ−ợc sắp xếp nh− sau. Mục 2 giới thiệu mô hình cơ bản hệ cộng dồn “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 kết luận bài báo này. 2. MÔ HìNH CƠ BảN Hệ CộNG DồN “MùI” APS Thuật toán APS đ−ợc S. Tsutsui, M. Peklikan, A. Ghosh đ−a ra lần đầu tiên vào năm 2005 và sau đó, đ−ợc S. Tsutsui nâng cấp thành thuật toán eAPS vào năm 2006 (Tsutsui S., 2006). 2.1. Sự cộng dồn “mùi” Trong thực tế, sự cộng dồn “mùi” đ−ợc sinh bởi một số loài côn trùng để chia sẻ thông tin về nguồn thức ăn, nơi ẩn nấp an toàn, sự thu hút giới tính hoặc kẻ thù. Ng−ời ta đã quan sát đ−ợc rất nhiều chức năng của hành động cộng dồn “mùi” nh− đánh dấu nguồn thức ăn, tìm kiếm nơi ẩn nấp, kết bạn hoặc tự vệ. Khi một con gián thấy một chỗ ẩn nấp an toàn, nó sẽ tiết ra một loại “mùi” đặc biệt trong phân của nó để thu hút những con gián khác. Sự khác biệt giữa ACO và APS chính là ở chức năng của “mùi” trong không gian tìm kiếm. Trong ACO nồng độ “mùi” đ−ợc xác định là dấu vết trên mỗi đỉnh hoặc trên mỗi cạnh giữa các đỉnh của đồ thị tìm kiếm. Còn trong APS, hàm mật độ cộng dồn “mùi” đ−ợc xác định là hàm mật độ trong không gian tìm kiếm nX R⊂ . Mỗi vòng lặp của APS gồm hai b−ớc cơ bản: Cập nhật hàm mật độ cộng dồn “mùi” Sinh ra “các kiến” mới nhờ vào hàm mật độ cộng dồn “mùi” tại thời điểm hiện tại. 2.2. Cập nhật hàm mật độ cộng dồn “mùi” Đặt ( ),t xτ là hàm mật độ (density) cộng dồn “mùi” trong vòng lặp t . APS khởi tạo ( )min(0, )= 0,x = cxτ τ . Do đó, “kiến” mới ban đầu đ−ợc sinh ra ngẫu nhiên theo phân phối đều trên toàn bộ không gian tìm kiếm m X . Để đảm bảo “kiến” đ−ợc sinh ra nhiều hơn tại những vị trí có mật độ cộng dồn “mùi” cao, trong vòng lặp , các “kiến” mới đ−ợc sinh ra ngẫu nhiên theo phân phối xác suất t ( , )p t xτ xác định nh− sau: ( ) ( ) , ( , ) , X t x p t x t x dxτ τ τ= ∫ (1) 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 bảo nồng độ (intensity) “mùi” càng tăng khi 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 tuyến tính trong không gian tìm kiếm, có thể cập nhật “mùi” cho “kiến” ,t rx nh− sau: 67 Nguyễn Hoàng Huy, Nguyễn Hải Thanh ( ) 2' , , 1 , ; ; ( ; ; )t r t r tm k Ct r x x r N x x k α τ α β = ∆ = ∑ ∑ (2) Trong đó là số điểm đạt đ−ợc của “kiến” trong vòng lặp (số điểm r của “kiến” r t ,t rx càng tăng khi giá trị của hàm số ( )f x càng nhỏ, “kiến” tốt nhất trong kiến ở vòng lặp này đ−ợc điểm còn kiến tồi nhất đ−ợc 1 điểm). m m 2 ,( ; ; )t r tN x x β ∑ là hàm mật độ phân phối xác suất của biến ngẫu nhiên chuẩn chiều: n ( ) ( ) ( )2 1, ,1/ 21/ 2 1 1; ; exp ( ) 22 T t r t t r t t r t N x x x x x xβ π − , ⎧ ⎫∑ = − − ∑ −⎨ ⎬⎩ ⎭∑ t∑ là ma trận hiệp ph−ơng sai của mẫu { } 1 ; ,, m rt r x α β = là các tham số điều khiển . ( ), 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ả “kiến” ở vòng lặp thứ t sẽ có: m ( ) ( )' , 1 , ; ; m t r r t x t r x xτ τ = ∆ = ∆∑ ; với (3) và đặt 1t ≥ (0, )x cτ∆ = (4) Với cách xây dựng nh− trên, thuật toán APS luôn đảm bảo ( ) ( )min 0, 0, (0, ) X X X X x dx x dx x dx cdx Cττ τ= = ∆ =∫ ∫ ∫ ∫ = (5) và ( ), X t x Cτ∆ =∫ (6) Điều này rất quan trọng trong quá trình sinh ngẫu nhiên “kiến” mới. Sự cộng dồn mật độ “mùi’ đ−ợc cập nhật trong công thức sau: ( ) ( ) (1, , ,t x t x t xττ ρτ+ = + ∆ ) )1 (7) Trong đó hằng số là tỷ lệ bay hơi của “mùi”. (0ρ ρ≤ < 2.3. Sinh ngẫu nhiên “các kiến” mới 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: ( ) ( )1 0 1, 0, ( , ) t t h h t x x t h xττ ρ τ ρ+ = + = + ∆ −∑ (8) Để thực hiện quá trình sinh ngẫu nhiên “các kiến” mới, cần phải có hàm mật độ phân phối xác suất ( )1,p t xτ + từ hàm mật độ cộng dồn “mùi” ( )1, .t xτ + Từ ph−ơng trình (1), (5), (6), (8) ta có: ( ) ( ) ( )11 1 0 0 0 , 0 1, . . h tt t t k kh k t t h x x p t x C C τ τ τρ ρ ρ ρ + + + = = = ∆ −+ = +∑∑ ∑ , (9) 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 ( ) ( ) ( )1 1 2 2( ) .... s sf x p f x p f x p f x= + + + . (10) 68 Hệ cộng dồn “mùi” cải tiến trong tối −u hóa bầy kiến Với thì quá trình sinh ngẫu nhiên “các kiến” mới theo hàm mật độ phân phối xác suất 1 1 s i i p = =∑ ( )f x đ−ợc tiến hành nh− sau: Chọn thành phần ( )if x với xác suất ip . Sinh ngẫu nhiên “các kiến” mới theo hàm mật độ phân phối xác suất ( )if x vừa chọn. Chú ý rằng ( 1, )p t xτ + là tổ hợp tuyến tính của 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 thủ tục vừa nêu trong đó xác suất chọn thành phần thứ là: 1t + i 1 0 t i i k p kρ ρ+ = = ∑ (11) và thành phần thứ là: i ( ) (0, ) 1 ( , )i x C khi i t f x t i x C khi i tτ τ = +⎧= ⎨∆ − ≤⎩ (12) Quá trình sinh ngẫu nhiên “các kiến” mới theo thành phần cuối cùng 1( )tf x+ là đơn giản vì 1( )tf x+ là hàm hằng, nên nó là hàm mật độ của phân bố đều trên toàn không gian tìm kiếm. Những thành phần còn lại ( )if t với i t≤ là tổ hợp tuyến tính của m thành phần: ( ) ( 2, 1 1 , . ; ; m t i r t im r k t i x r N x x C k α τ α β− = = ∆ − =∑∑ )−∑ (13) 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 ( )if t với có thể đ−ợc làm t−ơng tự nh− trên với xác suất chọn thành phần thứ r là : i t≤ 2 t-i,rN(x, x , )t iβ −∑ 1 m r k p r kα α = = ∑ (14) Do mỗi thành phần thứ của vế phải (13) là hàm mật độ phân phối chuẩn, việc sinh “các kiến” mới có thể sinh ngẫu nhiên nhờ phân hoạch Cholesky (Suli E. and Mayers D.F., 2003). r Khi đủ lớn, việc tính t ( 1, )p t xτ + theo 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 . Trong tr−ờng hợp này, với t và đủ lớn, nên để khắc phục điều đó thuật toán APS xấp xỉ 2 , ;t h r t hx β− ∑ − ) 0tρ ≈ H≥ H ( 1,p t xτ + trong (9) bởi: ( ) ( )1 1 0 0 , 1, . hH H kh k t h x p t x C τ τ ρ ρ − − = = ∆ −+ = ∑∑ (15) 2.4. Sơ đồ thuật toán APS Các b−ớc của thuật toán APS Khởi tạo vòng lặp của APS: . : 0t = 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 ngẫu nhiên m “kiến” mới theo phân phối đều. ( )P t Đánh giá và đ−a ra số điểm r của mỗi “kiến”. ( )P t Tính ma trận t∑ của m “kiến” . ( )P t Cập nhật hàm mật độ cộng dồn “mùi” ( )1,t xτ + theo ph−ơng trình (7). L−u trữ “kiến” vào . m ( )E t Sinh ngẫu nhiên “kiến” mới theo hàm mật độ phân phối xác suất xác định ở ph−ơng trình (9) đối với t , trong ph−ơng trình (15) tới t H m ( )P t H< ≥ Chọn “kiến” nhân tạo tốt nhất từ “kiến” m 2m ( ) ( ){ }N t E t+ để sinh ra m “kiến’ mới trong ( 1P t )+ . : 1t t= + 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 thuật toán, nếu không quay lại b−ớc 4. 3. MÔ HìNH CƠ BảN Hệ CộNG DồN “MùI” iAPS 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 địa ph−ơng đủ tốt. Để khắc phục những nh−ợc đ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à 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 nh− của ph−ơng pháp ACO nói chung. Hơn 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 kiếm “sâu”. D−ới đây là những điều chỉnh của lớp thuật toán iAPS so với thuật toán APS. 3.1. Cập nhật hàm mật độ cộng dồn “mùi” Sau khi “kiến” ,t rx đ−ợc sinh ra iAPS cập nhật “mùi” cho “kiến” ,t rx nh− sau: ( ) ( )( )min 2' , , 1 1 1, , ; ; . ( ; ; )t r t r tm k C t x r t r x x N x x k α τ α τ β = − +∆ = ∑ ∑ (2’) ( )min ,t xτ đ−ợc chọn sao cho ( )min , logt ct x t τ = khi đủ lớn và . t N≥ 0ttlimc a→∞ = > Khi đó, cộng dồn mật độ “mùi” tiết ra bởi tất cả “kiến” ở vòng lặp thứ sẽ có: m t ( ) ( )' , 1 , ; ; m t r r t x t r x xτ τ = ∆ = ∆∑ ; (3’) Để đả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ứ là: t ( ) ( ) ( )min, , 1,t x t x t x cττ τ∆ = ∆ + + . (3’’) 3.2. Sinh ngẫu nhiên “các kiến” mới Từ quy luật cập nhật mật độ “mùi” trong ph−ơng trình (7) ta có hàm mật cộng dồn “mùi” trong iAPS là: ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) 1 1 0 0 1 min min 0 0 0 1, 0, ; 0, , 1 , . 1 , t t t h t h h h t t t h h h h h h t x x t h x x t h x t h x t h t h x ττ τ τ ρ τ ρ ρ τ ρ ρ τ ρ ρ τ + + = = + = = = + = + ∆ − = + ∆ − + + − = ∆ − + + − ∑ ∑ ∑ ∑ ∑ (8’) Để 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 mật độ phân phối xác suất ( 1, )p t xτ + từ hàm mật độ cộng dồn “mùi” ( )1, .t xτ + Từ ph−ơng trình (1), (5), (6), (8’) ta có: ( ) ( )( ) ( )( )( ) ( ) ( ) min 1 0 min 0 1 min 1 0 0 1 1 , , 1, . 1 1 , . 1 , 0, . . ht t kh k ht t kh k t h x t h x p t x C t h t h x x C τ τ ρ τ τρ ρ τ τ ρ + = = + + = = − + − ∆ −+ = − + − + −+ ∑ ∑ ∑ ∑ x (9’) 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 ( 1, )p t xτ + là tổ hợp tuyến tính của 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 thủ tục vừa nêu trong đó xác suất chọn thành phần thứ là: 1t + i ( ) ( ) min 1 0 1 min 0 1 1 0 1 1 , 0,1,2,..., . 1 , i i t k k t h h t t k k t i x p i t t h x p ρ τ ρ ρ τ ρ + = + = + + = ⎧ − + −⎡ ⎤⎣ ⎦= =⎪⎪⎪⎪⎨ + −⎪⎪ =⎪⎪⎩ ∑ ∑ ∑ (11’) và thành phần thứ là: i ( ) ( ) ( ) ( )( )min 0, 1 , 1 1 , i x khi i t C f x t i x khi i t C t i x τ τ τ ⎧ = +⎪⎪= ⎨ ∆ −⎪ ≤⎪ − + −⎩ (12’) Quá trình sinh ngẫu nhiên “các kiến” mới theo thành phần cuối cùng 1( )tf x+ là đơn giản vì 1( )tf 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 kiếm. Những thành phần còn lại ( )if t với i t≤ là tổ hợp tuyến tính của m thành phần: ( ) ( )( ) ( 2,1min 1 , . ; ; 1 1 , m t i r t im r k t i x r N x x C t i x k ατ α βτ −= = ∆ − =− + − ∑∑ )−∑ (13’) 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 ( )if t với có thể đ−ợc làm t−ơng tự nh− trong APS. i t≤ Khi t đủ lớn, iAPS xấp xỉ: ( ) ( ) ( ) ( ) ( )( ) 1 min1 0 0 1 min1 0 min 0 0, 1, 1 , . , 1 1 , . 1 1 , hH H kh k hH H kh k x p t x t h x C t h x t h x C t h τ τ τρ τ ρ ρ τ τρ − − = = − − = = + = + − ∆ −+ − + −⎡ ⎤⎣ ⎦ − + − x⎡ ⎤⎣ ⎦ ∑∑ ∑∑ (15’) 3.3. Sơ đồ lớp thuật toán iAPS Sơ đồ lớp thuật toán iAPS gồm các b−ớc t−ơng tự sơ đồ thuật toán APS. iAPS khác APS ở b−ớc cập nhật hàm mật độ cộng dồn “mùi” và b−ớc sinh ngẫu nhiên “các kiến” mới. Trong iAPS, điều kiện kết thúc có thể là: số vòng lặp v−ợt quá một số cho phép, số vòng lặp liên tiếp mà không cải thiện đ−ợc lời giải v−ợt quá số 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 iAPS, ngoài các điều kiện kết thúc nh− trên còn 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 toàn cục, nồng độ “mùi” hầu nh− tập trung xung quanh lời giải đó nên thuật toán iAPS có thể kết thúc khi tổng nồng độ “mùi” trong một lân cận của lời giải tốt nhất v−ợt quá một số cho phép. 4. KếT LUậN So với hai thuật toán APS và eAPS, lớp thuật toán iAPS cân bằng đ−ợc sự tìm kiếm “sâu” và tìm kiếm “rộng” một cách hiệu quả. Do đó, khi áp dụng lớp thuật toán iAPS, khả năng tìm đ−ợc lời giải tối −u toàn cục là cao hơn APS và eAPS. Trong khi đó, do chỉ chú trọng đến khả năng tìm kiếm “sâu”, nên các thuật toán APS và eAPS rất dễ bị “mắc cạn” tại lời giải tối −u địa ph−ơng. Chúng tôi đề xuất tiếp tục hoàn thành những định lý về cơ sở lý thuyết toán học nhằm chỉ ra những điều kiện làm cho thuật toán APS và eAPS không hội tụ tới lời giải tối −u toàn cục. Đồng thời, tiếp tục hoàn thành chứng minh tính hội tụ của lớp thuật toán iAPS cũng 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 độ hội tụ tốt hơn. Hơn nữa, cũng cần có những nghiên cứu tính toán so sánh lớp thuật toán này với các thuật toán tối −u khác trên các bài toán tối −u mẫu. 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 toán tối −u trong những lĩnh vực khác nhau trong đó có các bài toán tin sinh học. 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 AISB Workshop on Evo. Comp, p. 24 - 39. Dreo J., P. Siarry (2002). A new ant colony algorithm using the heterarchical concept aimed at optimization of multiminima continuous functions. Proc. of the Third Int. Workshop on Ant Algorithms, p. 216 - 221. Engelbrecht A.P. (2005). Fundamentals of Computational Swarm Intelligence. John Wiley & Sons, Chichester, p. 361-510. Pourtakdoust S.H., H. Nobahari (2004). An extension of ant colony system to continuous optimization problems. Proc. of Fourth Int. Workshop on Ant Colony Optimization and Swarm Intelligence, p. 294-301. Socha K. (2004). ACO for continuous and mixed-variable optimization. Proc. of Fourth Int. Workshop on Ant Colony Optimization and Swarm Intellgence, p. 25-36. Suli E., D. F. Mayers (2003). An Introduction to Numerical Analysis. Cambridge University press, Cambridge, p. 39-91. Tsutsui S. (2006). An Enhanced Aggregation Pheromone System for Real-Prameter Optimization in the ACO Metaphor. Proc. of the Fifth Int. Workshop on Ant Colony Optimization and Swarm Intelligence, p. 60-71. Wodrich M., G.Bilchev (1997). Cooperative distribution search: the ant’s way. Control Cybernetics 3, p. 413-446. 72