C best ,vớ i best hoặc là độ dài của hành trình tốt nhất tại vòng lặp hiện tại, hoặc là độ dài của hành trình tốt nhất từ khi bắt đầu tìm kiếm MMAS sẽ thực hiện cập nhật luân phiên
τij❑ ← (1−ξ)τij +ξτ0 ❑ (2.)
với ξ (0< ξ <1) là tham số bay hơi. Nhiều thực nghiệm đã tiến hành cho thấy 0.1 là giá trị tốt cho ξ.
τ0❑ là tham số khởi tạo giá trị cho các vệt mùi. τ0❑
=1/nCnn.
với n là số lượng các thành phố và Cnn là độ dài của một hành trình cho bởi phương pháp tìm kiếm láng giềng gần nhất.
Quá trình cập nhật cục bộ làm cho lượng mùi trên mỗi cạnh giảm đi một ít sau mỗi lẫn con kiến đi qua một cạnh, làm cho kiến ít bị thu hút bởi các cạnh đó hơn. Hay nói cách khác quá trình cập nhật cục bộ làm tăng khả năng khám phá các đường đi chưa được đến thăm, và trong thực nghiệm việc này không gây ra hiện tượng ứ đọng các vệt mùi như trong thuật toán MMAS.
Thêm một chú ý đáng quan trọng là trong các thuật toán AS, MMAS việc thiết lập cho các con kiến xây dựng đường đi của chúng hoặc là song song hoặc là tuần tự cho kết quả là như nhau. Tuy nhiên với ACS thì khác, do có thêm quá trình cập nhật cục bộ nên trong phần lớn các cài đặt thuật toán ACS người ta đều để cho các con kiến xây dựng các đường đi song song [6]
Thực tế kết quả thu được cho thấy thuật toán ACS và MMAS tốt hơn AS [6] [9]
2.3. THUẬT TOÁN ĐÀN KIẾN GIẢI BÀI TOÁN TSP
Thuật toán đàn kiến về sau được gọi là thuật toán ACO, ACO có thể áp dụng cho bài toán TSP dưới dạng biểu diễn bằng đồ thị G=(C,L), trong đó L là tập các cạnh kết nối đầy đủ tất cả các đỉnh của tập C. Tập giải pháp của vấn đề chính là tập các hành trình khả dụng bắt đầu từ thành phố xuất phát đến thành phố đích và ràng buộc Ω cho biết kiến chỉ xây dựng các hành trình có thể được bằng số hoán vị của các chỉ số thành phố. Điều này hoàn toàn có thể, bởi vì đồ thị có cấu trúc G là một đồ thị khép kín, bất cứ đường đi đóng nào mà đi qua
tất cả các đỉnh, mỗi đỉnh đúng một lần không lặp lại thì được xem như một hành trình khả thi [6]
Trong tất cả các thuật toán ACO áp dụng cho bài toán TSP, các tuyến đường vệt mùi đều có liên quan đến các cung, vì vậy τij biểu thị cho khả năng (mong muốn) thăm thành phố j ngay sau khi vừa thăm thành phố j. Thông tin heuristic được chọn ở đây là:
ηij = 1/ dij . ηij là mong muốn phỏng đoán (kinh nghiệm) của việc đi từ thành phố i trực tiếp đến thành phố j tỉ lệ nghịch với dij - khoảng cách giữa 2 thành phố i, j. Trong trường hợp có vài cung có dij=0 thì ηij được đặt cho một giá trị rất nhỏ. Mục đích thực hiện các đường đi vệt mùi là thu thập thành một ma trận vệt mùi mà các phần tử của nó là các τij . Việc này cũng giống như thông tin heuristic.
Hành trình của kiến được xây dựng bằng cách áp dụng các thủ tục xây dựng đơn giản sau đây cho mỗi kiến:
(1) Lựa chọn (theo một số tiêu chí) một thành phố cho kiến xuất phát.
(2) Sử dụng các giá trị vệt mùi và heuristic để xây dựng một xác suất hành trình du lịch bằng cách lặp đi lặp lại việc thêm các thành phố mà con kiến chưa đi qua, cho đến khi tất cả các thành phố đã được đi qua.
(3) Quay trở lại thành phố ban đầu.
Sau khi tất cả các con kiến này đã hoàn thành hành trình của chúng, chúng sẽ để lại một lượng vệt mùi trên hành trình mà chúng đã thực hiện.
Trong hầu hết các trường hợp, trước khi tăng vệt mùi các hành trình được xây dựng bởi kiến được cải tiến bằng cách kết hợp thêm tìm kiếm cục bộ. Ngoại trừ thuật toán hệ thuộc địa kiến ACS (ant colony system - thuật toán mà có sự bay hơi của vệt mùi trong quá trình xây dựng các hành trình) thì sự kết hợp thuật toán này được áp dụng cho hầu hết các thuật toán ACO cho bài toán TSP. Chương trình của thuật toán này như sau:
procedure ACOMetaheuristicStatic
Input: Tham số α (điều chỉnh ảnh hưởng của vệt mùi), β (điều chỉnh ảnh hưởng của thông tin heuristic), rho (tham số bay hơi), số kiến, Q (tác nhân tăng vệt mùi)
Output: Giải pháp tối ưu nhất 1. Begin