基因遺傳式演算法(Genetic Algorithm,GA)

基因遺傳式演算法(Genetic Algorithm,GA)是應用相當普遍的巨集演算法。基因演算法的精神就像大自然的進化法則一樣，適者生存，不適者淘汰，如此經由數代演化後，可以得到更好的物種。而在進化的過程中，會因為突變獲得畸異度較大的品種，突變往往能對一物種的發展突破帶來全新的力量。基因演算法的骨架由選擇及複製、交配、突變、淘汰等構成。

以下簡單說明基因演算法的一些步驟與名詞:

• 染色體(Chromosome):基因演算法中所謂的染色體就是一組解，一個染色體上面有很多基因。
• 適應度函數(Fitness Function):表示染色體生存的能力，意即一組解的目標函式好壞。
• 複製及選擇(Reproduction & Selection): 複製相當於淘汰的機制，被選擇的染色體可以複製到演化池中。而如何選擇染色體相當於決定哪些染色體可以複製到演化池中。較常見的選擇法有排序選擇法、輪盤式選擇法、競爭式選擇法等。雖然選擇的方法很多，但其主要精神是能根據適應度決定哪些染色體生存下來。
• 交配(Crossover):交配是指由父代產生子代的過程。常見的交配方式有單點交配、雙點交配、基因交換。
• 突變(Mutation):突變的精神在於在世代演化之中，提供改變的力量，也就是GA跳出區域解的機制。

事實上，基因演算法的精神是最重要的，因此每個步驟都有很大的空間調整。一個較一般化的流程如下圖所示:

相關連結

簡介META-HEURISTICS(巨集啟發式演算法)

當我們需要最佳化一個複雜的問題時，有時候求得最佳解所需的計算時間非常龐大甚至於不可行。基於求解效率的考量，很多人發展啟發式演算法(Heuristic Algorithm)來求解原問題。這種啟發式演算法的求解特性通常有一個逐步尋找優良解的邏輯，而求得的解往往並非最佳解，而是近似最佳解。逐步尋找優良解的方法有時候會採用貪婪式的尋找方法(Greedy Algorithm)，之所以叫貪婪演算法，主要是因為短視近利的結果，這樣的搜尋有時會落入區域解的窠臼。若無加入適時跳出區域解的能力，就容易受到初始解好壞影響，找不到好的解。

這樣的求解過程，經由發展跟設計，具備有尋找優解及自動跳出區域解的邏輯跟機制，成為巨集啟發式演算法，這些方法具有彈性可適用在許多問題上。這類的方法通常利用收斂-跳出的邏輯，找到最後的滿意解。而這樣的方法不計其數，或者是說只要有尋優加上跳出區域解的設計，都能成為一套方法。但經過時間的檢驗，較著名的方法有基因遺傳式演算法(Genetic Algorithm,GA)、禁忌搜尋法(TABU)、螞蟻演算法(AS,ACS)、粒子群最佳化法(Particle Swam Optimization,PSO)、模擬退火法(SA)...等。

底下也將有各種Meta Hueristic的介紹：

• 基因遺傳式演算法(Genetic Algorithm,GA)
• 禁忌搜尋法(TABU)
• 螞蟻演算法(AS,ACS)
• 粒子群最佳化法(Particle Swam Optimization,PSO)
• 模擬退火法(SA)