chương 1. Trong chương 2 chúng tôi sẽ tìm hiểu thuật toán tối ưu đàn kiến để giải bài toán này. Giới thiệu về thuật toán Bài toán tối ưu hóa tổ hợp (TƯTH) là bài toán hấp dẫn và thú vị, các bài toán này có thể đưa về bài toán tìm kiếm trên đồ thị và cho lời giải đúng hoặc gần đúng. Nhiều bài toán TƯTH thuộc lớp bài toán NP-khó và không giải được trong thời gian đa thức.
Thay vì giải quyết một cách chính xác thì người ta thường giải bài toán này bằng phương pháp gần đúng và lời giải thu được gần với lời giải tối ưu và thời gian chạy khá nhanh. Các thuật toán gần đúng này thường được gọi là các thuật toán heuristic và được áp dụng để giải các bài toán cụ thể trong thực tế. Metaheuristic là mở rộng của thuật toán heuristic tổng quát được thiết kế để giải quyết một lớp các bài toán rộng lớn. Trong đó, phương pháp tối ưu hóa đàn kiến (Ant Colony Optimization – ACO) là một phương pháp metaheuristic dựa trên ý tưởng mô phỏng hành vi của đàn kiến trong tự nhiên thông qua cách tìm đường đi của chúng từ tổ tới nguồn thức ăn dựa vào mật độ mùi (Pheromone) mà các con kiến để lại trên đường đi.
Thuật toán tối ưu đàn kiến (ACO) được giới thiệu bởi Dorigo và lần đầu tiên được ứng dụng giải bài toán phân loại các trạm làm việc vào năm 1991. Thuật toán ACO có đặc điểm là kết hợp giữa các thông tin cấu trúc của lời giải tốt trong tương lai với các thông tin của lời giải tốt đã tìm trước đó. Hiệu quả của thuật toán ACO được thể hiện khi so sánh với các thuật toán nổi tiếng như thuật toán di truyền (GA), Tabu Search, Local Search,… Người ta đã ứng dụng thành công các thuật toán tối ưu đàn kiến trong một số bài toán tối ưu tổ hợp thường gặp như: bài toán người bán hàng, bài toán tô màu trên đồ thị, bài toán lập lịch,… 2. Từ kiến tự nhiên đến kiến nhân tạo Trong quá trình tìm kiếm đường đi, các kiến thực hiện trao đổi thông tin gián tiếp thông qua phương thức tự tổ chức.
Mặc dù đơn giản nhưng phương thức này tạo điều kiện cho các kiến có thể thực hiện được các công việc phức tạp vượt quá khả năng của mỗi kiến, đặc điểm nổi bật đó là khả năng tìm đường đi ngắn nhất từ tổ kiến tới nguồn thức ăn mặc dù kiến không thể đo được độ dài đường đi. Vậy trước tiên ta xét xem các kiến tìm đường đi bằng cách nào mà có thể giải quyết được các vấn đề tối ưu hóa. LUAN VAN CHAT LUONG download : add luanvanchat@agmail. Đàn kiến tự nhiên Trong quá trình tìm kiếm đường đi, các con kiến sẽ để lại một chất hóa học trên đường gọi là vết mùi (pheromone) để đánh dấu đường đã đi.
Các kiến sẽ cảm nhận vết mùi để tìm được đường đi từ tổ tới nguồn thức ăn mà các con kiến khác đã khám phá bằng cách chọn ngẫu nhiên có định hướng thông qua nồng độ vết mùi. Các kiến chịu ảnh hưởng từ các vết mùi của các con kiến khác để lại chính là ý tưởng dùng để thiết kế thuật toán ACO. 1 Ví dụ về hoạt động của đàn kiến trong thực tế.1 biểu diễn hành trình của đàn kiến trong thực tế. Trong (hình a) đàn kiến thực hiện di chuyển từ tổ E đến nơi chứa thức ăn A và ngược lại.
Khi gặp cản trở xuất hiện trên đường tại vị trí B hoặc D (hình b), đàn kiến phải quyết định rẽ trái hoặc rẽ phải. Cách lựa chọn đường đi có ảnh hưởng từ mùi hương thu hút trên tuyến đường do các con kiến khác để lại. Nếu mùi hương thu hút từ bên phía phải lớn hơn phía trái sẽ tạo cho các kiến một động lực mạnh mẽ hơn và theo đó xác suất rẽ phải sẽ lớn hơn rẽ trái. Ban đầu, con kiến đầu đàn đi đến điểm B (hoặc D) sẽ có xác suất rẽ phải như rẽ trái (do chưa có mùi hương thu hút trước đó trên hai tuyến đường này).
Do tuyến đường B – C – D ngắn hơn tuyến đường B – H – D nên con kiến đầu đàn đi theo B – C – D sẽ đến điểm D trước con kiến đầu đàn đi theo B – H – D (hình c). Kết quả cho thấy con kiến đi từ E đến D sẽ cảm nhận thấy mùi hương trên tuyến đường D – C – B khiến cho các con kiến khác quyết định đi theo tuyến đường D – C – B – A và theo thời gian tuyến đường D – C – B sẽ được nhiều kiến lựa chọn hơn so với tuyến đường B – H – D. Có thể thấy rằng mùi hương thu hút ở tuyến đường ngắn hơn lớn hơn so với tuyến đường dài sẽ thúc đẩy các kiến chọn tuyến đường ngắn hơn để đi là nhiều hơn. LUAN VAN CHAT LUONG download : add luanvanchat@agmail.
Đàn kiến nhân tạo Từ thực nghiệm ở trên ta có thể thấy rằng đàn kiến tự nhiên có thể tìm đường đi ngắn nhất giữa hai vị trí nhờ sử dụng quy luật di chuyển theo xác xuất của thông tin địa phương. Vết mùi để lại trên đường đi của kiến cho ta liên tưởng đến cách học tăng cường trong các bài toán chọn tác động tối ưu, mô phỏng bài toán tìm đường đi ngắn nhất giữa hai điểm trên đồ thị. Trong các bài toán ứng dụng thực tế, từ mỗi đỉnh có thể có nhiều cạnh nên nhiều con kiến tự nhiên sẽ bị đi luẩn quẩn và kém hiệu quả nên người ta thường dùng đàn kiến nhân tạo. Mỗi kiến nhân tạo có nhiều khả năng hơn kiến tự nhiên.
Dưới đây sẽ trình bày một vài đặc điểm của kiến nhân tạo: Kiến nhân tạo có bộ nhớ riêng/ ký ức nhất định nên có khả năng ghi nhớ các đỉnh đã thăm trong hành trình và tính toán được độ dài đường đi nó chọn. Kiến không hoàn toàn mù, chúng có một vài tri thức nhất định nên có thể quan sát, đánh giá các thay đổi của môi trường. Kiến nhân tạo được sống trong môi trường có miền thời gian là rời rạc. 2 Ví dụ về hoạt động của đàn kiến nhân tạo.
Ý tưởng về đàn kiến nhân tạo được nêu ra là nếu tại một điểm bất kỳ, một con kiến nhân tạo sẽ thực hiện chọn điểm tiếp theo để đi từ tập các điểm thuộc các đường đi khác nhau và điểm được chọn là điểm có thể dẫn đến đường đi là ngắn nhất. Trình bày giải thuật Khi áp dụng thuật toán ACO vào các bài toán thực tế, có bốn yếu tố quan trọng quyết định hiệu quả của thuật toán: 1) Xây dựng đồ thị cấu trúc: Phụ thuộc đặc điểm của mỗi bài toán cụ thể. LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com 16 2) Xây dựng lời giải tuần tự: Phụ thuộc đặc điểm của mỗi bài toán cụ thể. 3) Xác định thông tin heuristic: có thể có hoặc không, thông tin heuristic là thông tin kinh nghiệm giúp tăng hiệu quả của thuật toán.
4) Chọn quy tắc cập nhật mùi: thể hiện chiến lược học của thuật toán. Dùng để phân biệt các thuật toán ACO. Đồ thị cấu trúc Xét bài toán tối ưu tổ hợp tổng quát Mỗi bài toán tối ưu tổ hợp tổng quát được biểu diễn dưới dạng bài toán cực tiểu hóa với một bộ ba (𝑆, 𝑓, 𝛺), trong đó S là tập hữu hạn các trạng thái (lời giải tiềm năng hay phương án), f là hàm mục tiêu xác định trên S còn Ω là tập các ràng buộc để xác định S qua các thành phần của tập hữu hạn C và các liên kết của tập này. Mỗi phương án 𝑠 ∈ 𝑆 thỏa mãn các ràng buộc Ω gọi là phương án chấp nhận được.
Mục tiêu của chúng là tìm ra phương án 𝑠 ∗ tối ưu hóa toàn cục đối với hàm mục tiêu 𝑓, nói cách khác chính là tìm phương án 𝑠 ∗ sao cho 𝑓(𝑠 ∗ ) ≤ 𝑓(𝑠) với mọi 𝑠 ∈ 𝑆. Đối với bài toán này ta có 3 cách giải quyết đó là: vét cạn, kỹ thuật ăn tham hoặc phương pháp tối ưu trong lĩnh vực NP-khó. Đặc tính của C, S, Ω như sau: 1) Ký hiệu X là tập các vectơ trong C độ dài không quá h: X = {< 𝑢0 , … , 𝑢𝑘 > : 𝑢𝑖 ∈ 𝐶, ∀𝑖 ≤ 𝑘 ≤ ℎ}. Khi đó, mỗi phương án s trong S được xác định bởi ít nhất một vectơ trong X như ở điểm 2.
2) Tồn tại tập con X* của X và ánh xạ 𝜑 từ X* lên S sao cho 𝜑 −1 (𝑠) không rỗng với ∀s ∈ S, trong đó tập X* có thể được xây dựng từ tập con C0 nào đó của C nhờ mở rộng tuần tự như ở điểm 3 dưới đây. 3) Từ C0 ta mở rộng tuần tự thành X* theo thủ tục tuần tự sau: i) Gọi x0 = < 𝑢0 > là mở rộng được với ∀𝑢0 ∈ 𝐶0. ii) Giả sử 𝑥𝑘 = < 𝑢0 , … , 𝑢𝑘 > là mở rộng được từ các ràng buộc Ω và chưa thuộc vào X*. Từ tập ràng buộc Ω, xác định tập con 𝐽(𝑥𝑘 ) của C, sao cho ∀𝑢𝑘+1 ∈ 𝐽(𝑥𝑘 ) thì 𝑥𝑘+1 =< 𝑢0 , … , 𝑢𝑘 , 𝑢𝑘+1 > là mở rộng được hoặc xk X ∗ khi J(xk ) là rỗng.
iii) ∀𝑢0 ∈ 𝐶0 thủ tục mở rộng nêu trên cho phép ta xây dựng được mọi phần tử của X*. Xây dựng đồ thị cấu trúc Mỗi bài toán TƯTH được xem như một bài toán tìm kiếm vectơ độ dài không quá ℎ trên đồ thị đầy đủ có các đỉnh được gán nhãn trong tập 𝐶. Để tìm các lời giải chấp nhận được, ta xây dựng đồ thị đầy đủ với tập đỉnh 𝑉 sao cho mỗi đỉnh của nó tương ứng với mỗi LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com 17 thành phần của 𝐶. Các lời giải chấp nhận được sẽ là các vectơ được xác định theo thủ tục tuần tự hay bước ngẫu nhiên.
Thông thường, trong các bài toán thuộc lớp NP-khó, người ta đưa ra các phương pháp heuristic để tìm lời giải đủ tốt cho bài toán. Sau đó, các thuật toán ACO sẽ kết hợp thông tin heuristic này với phương pháp học tăng cường dựa vào mô phỏng hành vi của đàn kiến, để tìm được lời giải tốt hơn. Ta xét đồ thị G = (V, E, H, τ) là đồ thị cấu trúc của bài toán tối ưu tổ hợp, trong đó V là tập đỉnh, E là tập các cạnh, H là vectơ các trọng số heuristic của cạnh và τ là vectơ biểu thị các thông tin học tăng cường 𝜏𝑖,𝑗. Từ các cạnh ta xây dựng tập X* nhờ mở rộng tập 𝐶0 theo thủ tục tuần tự.