chương 1 luận văn đã được tìm hiểu về bài toán UCTP và một số cách tiếp cận để giải bài toán, chương này luận văn sẽ tìm hiểu phương pháp tối ưu đàn kiến để giải bài toán trên. Từ kiến tự nh ên ến kiến nhân t o Những hình ảnh nhận thức đặc biệt của đàn kiến chỉ đơn giản là sự phát triển và hoàn toàn mò mẫm. Trong thực tế, một điều quan trọng trong nghiên cứu về loài kiến là hành vi liên lạc giữa các con kiến hoặc giữa các cá nhân với môi trường, được dựa trên việc sử d ng các sản ph m hóa chất của các loài kiến. Các hóa chất đó được gọi là mùi (vết mùi).
Kiến tự nhiên hi tìm đường đi, đàn kiến trao đ i thông tin gián tiếp và hoạt động theo phương thức tự t chức. Phương thức này tuy đơn giản nhưng đã giúp cho đàn kiến có thể thực hiện được những công việc phức tạp vượt xa khả năng của t ng con kiến, đặc biệt là khả năng tìm đường đi ngắn nhất t t đến nguồn thức ăn (xem hình 2. iến chịu ảnh hư ng của các vết mùi của các con kiến khác chính là ý tư ng thiết kế thuật toán ACO. Thể hiện hành vi của mỗi con kiến trong tự nhiên Để làm được điều đó, trên đường đi, mỗi con kiến để lại vết m i ng để đánh dấu đường đi.
ằng cách cảm nhận vết mùi, con kiến có thể lần theo đường đi đến 8 LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com nguồn thức ăn được các con kiến khác khám phá theo phương thức chọn ngẫu nhiên, có định hướng theo nồng độ vết mùi. Con kiến chịu ảnh hư ng của các vết mùi của các con kiến khác, đây là ý tư ng chính để thiết kế thuật toán ACO. Thí nghiệm trên cây cầu : Có nhiều thực nghiệm nghiên cứu về hành vi để lại vết m i và đi theo vết mùi của loài kiến. Thực nghiệm, được thiết kế b i Deneubourg và các đồng nghiệp [15] dùng một chiếc cầu đôi nối t t kiến tới nguồn thức ăn, như minh họa trong hình 2.
Họ đã thực nghiệm với tỉ lệ độ ài đường giữa hai nhánh khác nhau của chiếc cầu đôi, trong đó là độ dài của nhánh dài còn là độ dài của nhánh ngắn. Trong thực nghiệm thứ nhất, chiếc cầu đôi có hai nhánh bằng nhau ( hình 2. an đầu, kiến lựa chọn đường đi một cách tự o đi t t đến nguồn thức ăn, cả hai nhánh đều có kiến đi, nhưng sau một thời gian các con kiến này tập trung đi theo cùng một nhánh. Kết quả có thể được giải thích như sau an đầu không có vết mùi nào trên cả hai nhánh, o đó kiến lựa chọn nhánh bất k với xác suất như nhau.
Một cách ngẫu nhiên, sẽ có một nhánh có số lượng kiến lựa chọn nhiều hơn nhánh kia. Do kiến để lại vết mùi trong quá trình di chuyển, nhánh có nhiều kiến lựa chọn sẽ có nồng độ mùi lớn hơn nồng độ mùi của nhánhcòn lại. Nồng độ mùi trên cạnh lớn hơn sẽ ngày càng lớn hơn vì ngày càng có nhiều kiến lựa chọn. Cuối cùng, hầu như tất cả các kiến sẽ tập trung trên cùng một nhánh.Thực nghiệm này cho thấylà sự tương tác c c bộ giữa các con kiến với thông tin gián tiếp là vết m i để lại cho ph p điều chỉnh hoạt động vĩ mô của đàn kiến.2: Thực nghiệm cây cầu đôi (a) ai nhánh có độ dài bằng nhau.
(b) Hai nhánh có độ dài khác nhau. 9 LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com Trong thực nghiệm thứ hai (xem hình 2.2 b), độ dài của nhánh dài gấp đôi độ dài nhánh ngắn (tỉ lệ ). Trong trường hợp này, sau một thời gian tất cả các con kiến đều chọn đoạn đường ngắn hơn. ũng như trong thực nghiệm thứ nhất, ban đầu đàn kiến lựa chọn hai nhánh đi như nhau, một nửa số kiến đi theo nhánh ngắn và một nửa đi theo nhánh ài (mặc dù trên thực tế, do tính ngẫu nhiên có thể một nhánh nào đó được nhiều kiến lựa chọn hơn nhánh kia).
Nhưng thực nghiệm này có điểm khác biệt quan trọng với thực nghiệm thứ nhất: Những kiến lựa chọn đi theo nhánh ngắn sẽ nhanh chóng quay tr lại t và khi phải lựa chọn giữa nhánh ngắn và nhánh dài, kiến sẽ thấy nồng độ mùi trên nhánh ngắn cao hơn nồng độ m i trên nhánh ài, o đó sẽ ưu tiên lựa chọn đi theo nhánh ngắn hơn. Tuy nhiên, trong thời gian đầu không phải tất cả các kiến đều đi theo nhánh ngắn hơn.Phải mất một khoảng thời gian tiếp theo nữa bầy kiến mới lựa chọn đi theo nhánh ngắn. Điều này minh chứng bầy kiến đã sử d ng phương thức thăm , tìm đường mới. Một điểm thú vị nữa là quan sát xem sẽ xảy ra điều gì khi quá trình tìm kiếm đang hội t , lại xuất hiện một đường mới t t đến nguồn thức ăn.
Việc này được thực nghiệm như sau an đầu t t đến nguồn thức ăn chỉ có một nhánh dài và sau 30 phút, thêm một nhánh ngắn (xem hình 2. Trong trường hợp này, nhánh ngắn thường không được kiến chọn mà chúng tập trung đi trên nhánh ài. Điều này có thể giải thích như sau nồng độ vết mùi trên cạnh dài cao và sự bay hơi của vết mùi diễn ra chậm nên đại đa số các con kiến vẫn lựa chọn nhánh dài (có nồng độ vết mùi cao).Hành vi này tiếp t c được củng cố kiến chọn đi theo nhánh ài, ngay cả khi có một nhánh ngắn xuất hiện. Việc bay hơi vết m i là cơ chế tiện lợi cho việc tìm đường mới, nghĩa là việc bay hơi có thể giúp kiến uên đi đường đi tối ưu địa phương đã được tìm thấy trước đây để tìm khám phá đường đi mới, tốt hơn.
Thí nghiệm b xung ( an đầu chỉ có một nhánh và sau 30 phút thêm nhánh ngắn hơn) 10 LUAN VAN CHAT LUONG download : add luanvanchat@agmail. Kiến nhân t o (Artificial Ant) Thực nghiệm cây cầu đôi cho thấy đàn kiến tự nhiên có thể sử d ng luật di chuyển theo xác suất, dựa trên thông tin địa phương để tìm được đường đi ngắn nhất giữa hai địa điểm. Vết mùi của đàn kiến cho ph p liên tư ng tới cách học tăng cường (reinforcement learning) trong bài toán chọn tác động tối ưu[2], gợi m mô hình mô phỏng cho bài toán tìm đường đi ngắn nhất giữa hai nút (tương ứng là t và nguồn thức ăn) trên đồ thị, trong đó các tác tử (agent) là đàn kiến nhân tạo. Tuy nhiên, trong các bài toán ứng d ng các đồ thị thường phức tạp hơn.T mỗi đỉnh có thể có nhiều cạnh, nên nếu mô phỏng thực sự hành vi của đàn kiến tự nhiên nhiều con kiến sẽ đi lu n qu n và o đó hiệu quả thuật toán sẽ rất kém.
Vì vậy, người ta dùng kỹ thuật đa tác tử (multiagent) mô phỏng đàn kiến nhân tạo, trong đó mỗi con kiến nhân tạo có khả năng nhiều hơn so với kiến tự nhiên. Kiến nhân tạo (về sau trong luận án ta sẽ gọi đơn giản là kiến) có bộ nhớ riêng, có khả năng ghi nhớ các đỉnh đã thăm trong hành trình và tính được độ ài đường đi nó chọn. Ngoài ra, kiến có thể trao đ i thông tin với nhau, thực hiện tính toán cần thiết, cập nhật m i… Sử d ng mô hình kiến nhân tạo này, Dorigo (1991) [15] đã xây ựng thuật toán Hệ kiến (AS) giải bài toán người chào hàng. Hiệu quả của thuật toán so với các phương pháp mô phỏng tự nhiên khác như SA và GA đã được kiểm chứng bằng thực nghiệm.
Thuật toán này về sau được phát triển và có nhiều ứng d ng phong phú, được gọi chung làphương pháp A O. Phương h ố ưu n ến Tối ưu đàn kiến (Ant Colony Optimization - ACO) là một phương pháp metaheuristic được đề xuất b i Dorigo vào năm 1991[14] dựa trên ý tư ng mô phỏng cách tìm đường đi t t tới nguồn thức ăn và ngược lại của các con kiến tự nhiên để giải gần đúng bài toán TƯT NP-khó. Trên đường đi của mình các con kiến thực để lại một vết hóa chất được gọi là vết mùi (pheromone trail), đặc điểm sinh hóa học của vết mùi này là có khả năng ứ đọng, bay hơi và là phương tiện giao tiếp báo cho các con kiến khác thông tin về đường đi đó một cách gián tiếp. Các con kiến sẽ lựa chọn đường đi nào tồn đọng lượng m i hay có cường độ vết m i lớn nhất tại thời điểm lựa chọn để đi, nhờ cách giao tiếp mang tính gián tiếp và cộng đồng này mà đàn kiến trong tự nhiên tìm được đường đi ngắn nhất trong uá trình tìm thức ăn mang về t và ngược lại.
Sử d ng mô hình kiến nhân tạo này Dorigo (1991) [4] đã xây ựng thuật toán hệ kiến (AS) giải bài toán người chào hàng. Thuật toán này đã được chứng minh tính hiệu quả thông qua thực nghiệm so với 11 LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com các mô phỏng tự nhiên khác như SA (mô phỏng luyện kim) và GA (giải thuật di truyền). Thuật toán này về sau được phát triển và có nhiều áp d ng phong phú trong thực tế, được gọi chung là phương pháp A O. Theo ý tư ng này, các thuật toán ACO sử d ng thông tin heuristic kết hợp thông tin học tăng cường qua các vết mùi của các con kiến nhân tạo (artificial ant) để giải các bài toán tối ưu t hợp khó bằng cách đưa về bài toán tìm đường đi tối ưu trên đồ thị cấu trúc tương ứng được xây dựng t đặc điểm của t ng bài toán c thể.
Thuật toán A O đầu tiên là hệ kiến (Ant System - AS) giải bài toán Người chào hàng TSP, đến nay các thuật toán A O đã áp ng một cách phong phú để giải nhiều bài toán tối ưu t hợp khác nhau và hiệu uả n i trội của nó đã được chứng tỏ bằng thực nghiệm. Nhờ những thành uả to lớn trong việc ứng ng phương pháp tối ưu đàn kiến vào giải các bài toán tối ưu t hợp khó m ra một lĩnh vực nghiên cứu và ứng ng mới thu hút được sự uan tâm của đông đảo các nhà khoa học trên thế giới, Dorigo đã được ội đồng châu u trao giải thư ng đặc biệt Marie urie (Marie Curie Excellence Award) trao hai năm một lần giành cho năm nhà khoa học có nhiều đóng góp cho nền khoa học và công nghệ châu u vào ngày 05 11 2003.