|
遺傳演算法(Genetic Algorithm)：
|
|
|
1975年 John Holland提出以基因遺傳演算法來解決數學最佳化的問題，經過多年研究發展已成功應用在物理、工業工程、電腦資訊，甚至財物金融等研究及應用領域的最佳化問題求解。基因遺傳演算法主要啟發自達爾文的進化論：物競天擇、強者生存的定律；模擬生物基因(gene)有擇優(Selection)、交配(Crossover)及突變(Mutation)的能力，使產生更優秀的新生代的程序；將要解的最佳化問題轉化為染色體及基因的模型，再藉著基因擇優、交配及突變的過程去尋求最佳解。
|
|
類神經路網路(Neural Network)：
|
|
|
自從McCulloch和Pitts在1943年提出第一個神經元(Neuron)的運算模型以來，類神經網路的研究大門便從此敞開。類神經網路是由模擬人類心智和腦部活動所發展出來的一種模型。就網路的架構而言，它是由許多簡單而且相互連結的神經元所組成；就網路的功能而言它是啟發自人類腦部活動所產生出來新型態的資訊處理和計算方式。目前類神經網路的研究除了應用在影像處理、語音辨識、文字辨識、控制等領域外，應用在最佳化上也是許多學者努力研究的目標。
|
|
螞蟻演算法(Ant Algorithm)：
|
|
|
螞蟻演算法最早是由M. Dorigo於1992年他的博士論文所提出，其發展主要是起源於觀察螞蟻之移動行為，螞蟻移動時會分泌一種稱為費洛蒙(Pheromone)之荷爾蒙，螞蟻行經一路徑之機會與該路徑曾遺留之費洛蒙成正比。越多螞蟻走過一個路程則遺留之費洛蒙越多，而遺留越多費洛蒙又會吸引越多螞蟻行走該路徑。因此，當螞蟻面臨兩條路以上之抉擇時，其行走某一路線之機率與其遺留費洛蒙量有關，而越短之路線其螞蟻通過時間短，導致最短路線上遺留之費洛蒙量越多，進而誘使更多螞蟻行經最短路徑，最後所有螞蟻將往最短路徑行走。較短之路徑所需行經時間較短，容易累積較多之費洛蒙，因而吸引較多之螞蟻，最後螞蟻將沿最短路徑，而求得最佳解。蟻行演算法即在模仿螞蟻行為，以進行最佳化之搜尋工作。螞蟻演算法可應用在最短路徑、旅行推銷員問題( TSP )、生產排程、水庫最低水位...等最佳化問題上，以求得各問題之最佳解為目標。
|
|
模擬退火法(Simulated Annealing)：
|
|
|
模擬退火法最早由N.Metropolis 等人於1953 年提出，當時並沒有受到研究者的重視。一直到了1983 年由S.Kirkpatrick 等人利用他來求解組合最佳化的問題，才使得此演算法受到人們的重視而得以發揚光大。
模擬退火法的基本觀念主要來自於固體加熱至一定的溫度後會由固體結構瓦解變為液體結構，再對其降溫過程加以控制，使得分子在變回固體結構時，能重新排列成我們所預期的穩定狀態。它結合了最陡坡降法與隨機過程的方式來求得整體最小值。
|
|
禁忌搜尋演算法 (Tabu search algorithm)：
|
|
|
禁忌搜尋演算法為Glover於1986所提出來具有記憶之最佳化演算法，而由於其具有記憶之前所搜尋路徑的能力，因此可以避免陷入區域解、重覆找尋之前已搜尋過的近似最佳解，目前已被廣泛地應用於許多工程或管理領域問題，如組合最佳化問題、投資組合問題等等。
禁忌搜尋法包含了５個基本元素，分別為起始解、停止條件、禁忌名單、禁忌移動及凌駕條件。禁忌搜尋法的步驟大致如下：
|
|
|
|
(1)
|
找出任一起始解，令此起始解為目前解。
|
|
(2)
|
自目前解的鄰域中找出一最佳相鄰解。
|
|
(3)
|
檢查由目前解到最佳相鄰解的移動是否為禁忌移動；若不是禁忌移則動並記錄此移動的目標函數值，且將此移動記錄於禁忌名單中。若為禁忌移動則檢查此移動是否滿足凌駕規則，若滿足凌駕規則則取消此移動之限制狀態並回到步驟2。若無法再移動或是達到停止規則，則 結束搜尋。
|
|
|
此外尚有糢糊邏輯(Fuzzy Logic)、陡坡降法(Gradient-Based Search)、灰色理論(Grey Theory)…等無法一一介紹。
|