Home » Machine Learning » Tìm kiếm trong không gian trạng thái và thuật toán Ant Colony Otimization

Tìm kiếm trong không gian trạng thái và thuật toán Ant Colony Otimization

  • Giới thiệu 

Trong loạt bài tìm kiếm trong không gian trạng thái ( về thuật toán Simulated Annealing có thể xem lại Simulated Annealing ), mình sẽ giới thiệu thêm về một giải thuật tìm kiếm cục bộ, đó là thuật toán Ant Colony Otimization. Mình vẫn tiếp tục dùng bài toán kinh điển để làm ví dụ, “Người bán hàng” – Bài toán tìm đường đi ngắn nhất đi qua tất cả các đỉnh, mỗi đỉnh đúng một lần, và trở về đỉnh xuất phát. 


  • Tổng quan

Giống như thuật toán Simulated Annealing ( tôi thép ) dựa trên việc mô phỏng ký thuật “Tôi thép”, thì thuật toán Ant Colony Otimization cũng mô phỏng hoạt động tìm đường của đàn kiến. Kiến là một sinh vật mù, việc tìm đường đến nơi có thức ăn và trở về hoàn toàn dựa trên tín hiệu của bầy đàn đánh dấu trên đường đi ( gọi là pheromone trails ). Vậy tại sao đàn kiến luôn chọn được đường đi ngắn nhất? Thực ra ngay từ đầu, đàn kiến đi lung tung khắp nơi, và mỗi bước đi, chúng đều rải pheromone trên đường đi, và trên đường từ nguồn thức ăn về tổ, chúng đi qua đi lại nhiều lần, thì những lần tiếp theo di chuyển, những con kiến có xu hướng chọn cho mình con đường nơi có nồng độ pheromone  nhiều hơn (vì đường đó ngắn hơn, nên chúng đi tới nguồn thức ăn và trở về tổ nhanh hơn), sau một khoảng thời gian di chuyển, nồng độ pheromone bay hơi dần, cuối cùng chỉ còn lại con đường ngắn nhât vì nồng pheromone  được đàn kiến rải liên tục, còn những con đường xa hơn sẽ dần bay hơi hết pheromone, và sẽ bị đàn kiến bỏ qua.
  • Mô tả chi tiết

Dựa vào hình trên, giả sử đi từ N tới F và trở về có 4 con đường kiến có thể đi (H1). Tại thời gian đầu khi t = 0, đàn kiến bắt đầu toả ra tìm đường đi từ N tới F, thì con đường nào cũng sẽ có kiến đi qua (H2), và tại mỗi đường đi, kiến đều rải pheromone, nên lượng pheromone trên mỗi con đường là bằng nhau. Tại thời điểm t = 1, Có thể thấy rõ con đường ở chính giữa là ngắn nhất, nên khi còn kiến đầu tiên tìm tới F sẽ quay về lại N đầu tiên, sau khi về N, kiến sẽ lại tiếp tục di chuyển tới F, ở thời điểm này, cả 4 con đường đã bay hơi đi mất một lượng ρ nồng độ pheromone, nhưng tại con đường ngắn nhât, con những con kiến đã hoàn thành tour của mình sẽ tiếp tục rải thêm một lượng ∆τ, trong khi ở những con đường khác, những con kiến khác vẫn chưa hoàn thành tour của mình, có thể thấy rằng lượng pheromone đang dần có sự thay đổi về trọng số. Tại thời điển t = n, khi những con kiến khác về N tiếp tục cuộc hành trình, và khi lựa chọn con đường, chúng sẽ có xu hướng chọn cho mình con đường có nồng độ pheromone cao hơn, và con đường ngắn nhât chính là con đường được đàn kiến đi qua nhiều nhất (H3).

Giống với thuật toán SA (Simulated Annealing) thì thuật toán ACO (Ant Colony Otimization) là một loạt thuật toán tối ưu hoá ngẫu nhiên tổ hợp (stochastic combinatorial optimization) _ hay có thể nói đơn giản là việc tìm ra cấu hình “chấp nhận được” bằng phương pháp “random”. Trong những bài toán này thường hay đề cập đến một hàm heuristic, hàm này như là trái tim của thuật toán, việc lựa chọn ra cấu hình tiếp theo như thế nào phụ thuộc hoàn toàn vào heuristic. 
  • Thuật toán

Mình sẽ bắt đầu mô tả thuật toán như sau:

 

Link tham khảo: [1] M. Dorigo, The Ant System: Optimization by a colony of cooperating agents ftp://iridia.ulb.ac.be/pub/mdorigo/journals/IJ.10-SMC96.pdf

 

  • Source code

Một số hàm quan trọng được biểu diễn như sau: