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

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

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

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

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

相關連結