đường đi. Với công thức trên tuyến đường của những con kiến nào mà càng tốt hơn thì nó càng được tăng cường thêm nhiều mùi. Nói tóm lại thì những cạnh mà được nhiều con kiến lựa chọn thì sẽ nhận được nhiều mùi hơn và có nhiều khả năng hơn sẽ được lựa chọn bởi các con kiến trong các vòng lặp tiếp theo của thuật toán.
Ưu điểm của AS:
Việc tìm kiếm ngẫu nhiên dựa vào trên các thông tin heuristic làm cho phép tìm kiếm linh hoạt và mềm dẻo trên không gian rộng hơn phương pháp heuristic sẵn có, do đó cho ta lời giải tốt hơn và có thể tìm được lời giải tối ưu.
Sự kết hợp với học tăng cường (reinforcement learning) trong đó những lời giải tốt hơn sẽ được sự tăng cường hơn thông qua thông tin về cường độ vệt mùi cho phép
ta từng bước thu hẹp không gian tìm kiếm và vẫn không loại bỏ các lời giải tốt, do đó nâng cao chất lượng thuật toán.
Nhược điểm của AS:
Hiệu suất của nó giảm đột ngột so với nhiều thuật toán metaheuristic khác khi mà kích thước của bài toán tăng lên. Bởi vì khi số đỉnh của đồ thị lớn thì cường độ vệt mùi trên những cạnh không thuộc lời giải tốt (hoặc ít được con kiến lựa chọn) sẽ nhanh chóng giảm dần về 0, làm cho cơ hội khám phá hay tìm kiếm ngẫu nhiên của thuật toán sẽ giảm mà đây là một trong những điểm mạnh của các thuật toán mô phỏng tiến hóa tự nhiên nên thuật toán hệ kiến AS kém hiệu quả.
2.2.2. Thuật toán Max-Min Ant System (MMAS)
MMAS và một số thuật toán khác như Elitist AS, Rank-Based AS là các thuật toán có được hiệu suất cao hơn nhiều so với thuật toán AS nhờ vào những thay đổi nhỏ trong thuật toán AS, đây được coi là các thuật toán kế thừa trực tiếp từ thuật toán AS vì chúng về cơ bản là không khác gì nhiều so với AS.
MMAS có bốn thay đổi chính đối với AS:
− MMAS chú trọng nhiều vào những hành trình tốt nhất được tìm thấy: MMAS chỉ cho phép con kiến tìm ra được hành trình tốt nhất của vòng lặp hiện tại hoặc con kiến tốt nhất từ đầu đến hiện tại được phép cập nhật mùi. Tuy nhiên việc này sẽ dẫn đến hiện tượng trì trệ, tập trung quá nhiều khi mà tất cả các con kiến đều cùng chọn một hành trình để đi, do sự tăng lên quá mức của cường độ các vệt mùi trên các cạnh tốt, mặc dù đây chưa phải hành trình tối ưu nhất.
− Để tránh hiện tượng trên một cải tiến thứ hai là MMAS giới hạn cường độ mùi trongmột khoảng cố định [τmax, τmin]. Tất cả vệt mùi trên các cạnh đều nằm trong khoảng này.
− Các vệt mùi được khởi tạo giá trị là cận trên của vệt mùi τmax, cùng với việc một tỉ lệ bay hơi mùi nhỏ sẽ làm tăng khả năng khám phá cho các con kiến ngay từ khi bắt đầu tìm kiếm.
− Trong thuật toán MMAS các vệt mùi sẽ được khởi tạo lại nếu như hệ thống rơi vào trạng thái trì trệ ở trên, hoặc không thể tìm được hành trình nào tốt hơn nữa sau một số lượng các vòng lặp liên tiếp.
a. Quy tắc cập nhật mùi
Cũng như thuật toán AS, sau khi tất cả các con kiến xây dựng xong hành trình của chúng, lượng vệt mùi bay hơi sẽ được cập nhật theo công thức như trong AS (2.))
Sau đó cường độ mùi trên mỗi cạnh có con kiến tốt nhất đi qua được cập nhật tăng một lượng theo công thức (2.5):
τij❑←τij+Δτijbest (2.)
Với Δτijbest
= 1