Bài viết sưu tầm

Có nhiều phương pháp tiếp cận để giải bài toán người bán hàng tuy nhiên có hai giải thuật phổ biến dùng để giải bài toán này là giải thuật di truyền và giải thuật đàn kiến (Ant Colony).

2.2.1 Giải thuật di  truyền

            Giải thuật di truyền thường dùng để giải cho nhiều lớp bài toán và giải thuật này cũng có thể dùng để giải cho bài toán người bán hàng, tuy nhiên khi sử dụng giải thuật này và triển khai trên máy tính thì thời gian chạy chương trình khá lâu vì việc biểu diễn nhiễm sắc thể cho n thành phố mà người bán hàng đi qua là khá khó khăn, vì ta có n thành phố, nếu dùng chuỗi nhị phân để biểu diễn nhiễm sắc thể cho n thành phố đó thì ta tốn là n*log₂(n) bit với mỗi thành phố ta cần biểu diễn log₂(n) bit. Từ đó không gian tìm kiếm rất rộng và phức tạp nên bắt buộc người lập trình phải áp dụng thuật toán Greedy(thuật toán tham lam) nhiều lần vì vậy chương trình chạy khá chậm.

2.2.2. Giải thuật AntColony

            Bài toán người bán hàng hoàn toàn có thể giải bằng giải thuật AntColony, thuật toán này có thể áp dụng cho nhiều lớp bài toán. Để có thể hiểu hơn về thuật toán này chúng ta có thể tìm hiểu đặc điểm hoạt động trong tự nhiên của đàn kiến và từ đó có thể hiểu hơn về thuật toán AntColony.

Hình 1: Sơ đồ hoạt động của các con kiến

 Quy luật di chuyển của đàn kiến trong tự nhiên là: Kiến là loài vật có tổ chức cao, cho nên mỗi khi di chuyển chúng thường để lại mùi riêng của nó để các con kiến trong đàn có thể nhận diện ra lối di chuyển của chúng, mùi của kiến để lại trên đường đi đó thì ta thường gọi là pheromone. Đây là yếu tố giúp đàn kiến đánh dấu và trao đổi thông tin với nhau khi chúng đi tìm nguồn thức ăn. Khi tìm thấy nguồn thức ăn, mỗi con kiến sẽ di chuyển từ tổ tới nơi có nguồn thức ăn theo đường đi đã tìm thấy. Vì từ tổ kiến đến nơi có thức ăn sẽ có nhiều đường đi. Vì thế ban đầu các chú kiến sẽ đi ngẫu nhiên theo các con đường từ điểm xuất phát đến đích. Tuy nhiên trong quá trình di chuyển chúng sẽ trao đổi thông tin với nhau, và sau một thời gian nhất định các chú kiến trong đàn sẽ tìm ra và di chuyển theo con đường ngắn nhất từ tổ tới nguồn thức ăn. Sau khi quan sát và nghiên cứu hoạt động của đàn kiến trong tự nhiên, chúng ta nhận thấy rằng quá trình tìm đuờng đi ngắn nhất từ tổ tới nguồn thức ăn dựa trên các quy luật sau:

· Dùng phoremone để trao đổi thông tin với nhau trong quá trình di chuyển nhằm mục đích tìm được đường đi ngắn nhất từ tổ đến nguồn thức ăn. Mỗi khi di chuyển chúng để lại một lượng thông tin mùi (phoremone) của chúng trên đường chúng đi qua.

· Khi tiến hành tìm đường đi, các con kiến đi sau sẽ xác định hướng đi bởi các thông tin mùi (pheromone) đã được để lại trên đường đi bởi các con kiến di chuyển trước đó

. · Các con kiến sẽ di chuyển một cách ngẫu nhiên khi không có mùi để lại trên đường đi. Lượng mùi để lại cũng bi bay hơi theo thời gian.

 · Các đường đi có lượng thông tin mùi (pheomone) để lại càng nhiều thì xác suất được các con kiến chọn càng cao. Ngược lại các đoạn đường có lượng thông tin mùi (pheromone) càng thấp thì xác suất được chọn càng thấp.

 Từ việc quan sát cơ chế hoạt động của đàn kiến trong tự nhiên mà thuật toán AntColony đã ra đời.

Thuật toán AntColony mô phỏng hoạt động của đàn kiến nhân tạo như sau: Thuật toán sử dụng một đàn kiến nhân tạo (Artificial Ants) để mô phỏng lại các hoạt động trong tự nhiên của đàn kiến. Và có một số điều chỉnh về mặt hoạt động so với đàn kiến tự nhiên nhằm tăng tính hiệu quả của thuật toán. Trong giải thuật này chủ yếu mô tả hoạt động tìm đường đi ngắn nhất của các con kiến nhân tạo dựa vào lượng mùi để lại trong quá trình di chuyển của đàn kiến. Cụ thể về hoạt động của đàn kiến nhân tạo được trình bày như sau:

Cho một đồ thị đầy đủ gồm các đỉnh và cạnh trong đó đỉnh là nơi kiến sẽ đi qua và các cạnh là các đoạn đường. Nút ban đầu cho đường đi của mỗi con kiến được chọn một cách ngẫu nhiên và thông tin mùi (pheromone) được tính toán và đặt trên mỗi đoạn đường. Mỗi con kiến sẽ chọn đường đi theo các nguyên tắc:

+ Dựa vào thông tin mùi để lại có trên các đoạn đường để tính xác suất chọn đoạn đường tiếp theo và làm đường đi cho con kiến.

 + Đường đi có nhiều lượng mùi (pheromone) nhiều hơn thì sẽ được gán một xác suất lớn hơn. Ngược lại các đoạn đường đi có lượng thông tin mùi thấp hơn sẽ có xác suất được chọn thấp hơn. Con kiến sẽ tìm đường đi cho tới khi hoàn thành một đường đi của nó (thỏa mãn điều kiện dừng của con kiến). 

+ Một đường đi đầy đủ và hoàn chỉnh được gọi là một lời giải đúng cho bài toán đặt ra. Các đường đi tìm được sẽ được phân tích, so sánh và đánh giá để tìm phương án tối ưu nhất có thể. Đó là lời giải tối ưu của bài toán.

+ Sau khi con tất cả kiến trong đàn hoàn thành việc tìm đường đi của nó, ta sẽ tiến hành cập nhật thông tin mùi cho các cung. Số lượng của mùi sẽ được tính toán và điều chỉnh để tìm được phương án tối ưu tốt hơn.

· Các lời giải có đường đi ngắn hơn sẽ có khối lượng pheromone lớn hơn để đặt trên các cung đã được đi qua. Ngược lại, các lời giải cho đường đi dài hơn sẽ có khối lượng pheromone bé hơn.

· Con kiến sẽ chọn đường đi có lượng mùi lớn hơn và xác suất chọn đường đi đó cũng cao hơn. Quá trình này được lặp đi đi lặp lại cho đến khi hầu hết các con kiến trong đàn kiến nhân tạo chọn cùng một đường đi, và đây chính là lời giải của bài toán.

Giải Thuật:

Khởi tạo thông tin pheromone

Khi chưa gặp điều kiện dừng, lặp:

XÂY DỰNG GIẢI PHÁP

+ Chọn con kiến k trong số m con,chọn ngẫu nhiên thành phố i với xác suất p0i.

+ Duyệt qua các thành phố j thuộc S dựa trên xác suất pij.

CẬP NHẬT MÙI

+ Bay hơi mùi các thành phố không nằm trong hành trình tốt nhất.

+ Gia tăng mùi cho các thành phố nằm trong hành trình tốt nhất.