紮爾庫荅．元

Ant Colony System (ACS): ACS是一種尋優演算法, 也稱 Ant Algorithm,
1992年由M. Dorigo在博士論文中提出, 它是利用螞蟻群體合作的原理來解尋優問題,
迄今已被應用來解許多困難的尋優問題(NP- Hard problems), 如 Traveling salesman problem,
quadratic assignment problem, vehicle routing problems,
job-shop scheduling problem, graph coloring problem,
packet-switched communication network problems, sequential ordering problem,
shortest common super-sequence problem,
load balancing in communication networks等。

演算法原理: 螞蟻可以由蟻穴到食物目的地找到一條最短路線, 它們用的不是視覺,
而是在走過的地方會殘留一種分泌物pheromone, 當以後的螞蟻經過時,
就有較高的機率選擇pheromone濃度高的方向, 因此隨著時間增長,
漸漸螞蟻會走同一路線(亦即最短路線)由蟻穴到食物目的地來回,
利用這種自然界的原理已有效率地解一些尋優問題(Optimization Problems)。

研究方向: 對於ACS 主題, 我們可以找出一些適當的 OR/IE 問題,
應用 ACS 原理來設計演算法, 並與其他方法做比較評估,
當然我們採用ACS 不一定要沿襲以往的方式, 主要是採用群體合作的架構,
但可考慮不同機制去導引”解”的搜尋方向,
我們也希望多瞭解一些自然界的現象(如蜜蜂、海豚等的群體生活),
以啟發我們設計新的演算法的架構。 節錄自 http://chern.ie.nthu.edu.tw/Ant_Algorithms.htm