AITerms 登入
最佳化機器學習模型訓練

基因演算法(Genetic Algorithm)是什麼?

基因演算法是一種模擬生物進化過程的優化算法,通過選擇、交叉和突變等操作,逐步演化出更優的解,用於解決複雜的搜索和優化問題。

完整定義

基因演算法是一種基於自然選擇和遺傳學原理的優化算法。它模擬生物進化過程,通過選擇、交叉和突變等操作,逐步演化出更優的解。基因演算法適用於解決複雜的、非線性的、多峰值的搜索和優化問題,例如函數優化、組合優化、機器學習模型參數優化等。

白話說明

你有沒有想過,解題不是一次算到底,而是像演化一樣慢慢挑出更好的解?

你可以把基因演算法想成模仿生物演化,先產生很多候選解,再用選擇、交叉和突變去逼近更好的答案。

它重要,是因為有些優化問題太複雜,不適合直接暴力搜尋,這時就需要這種能自己試探、自己演化的方法。

記住這句

選好的、混新的、再小改,就是基因演算法的核心。

比喻:基因演算法就像大自然中的「適者生存」法則 -- 它從一群隨機解中挑選表現好的,讓它們「交配」產生新解,再「突變」一點點,不斷進化直到找到最佳答案。

容易混淆

基因演算法 vs 窮舉法

窮舉法把所有可能都試過。

基因演算法只保留和繁殖較好的候選解。

基因演算法 vs 集成學習

集成學習是把多個模型結合起來。

基因演算法是用來搜尋解的優化方法,不是在直接組模型。

實際案例

超參數調校

想找學習率、層數和正則化組合時,可以用它在大量候選設定裡慢慢演化。

排程最佳化

在工廠排班或路徑安排上,當搜尋空間太大,基因演算法常能找出不錯的近似解。

演算法與應用

它通常經過族群初始化、適應度評估、選擇、交叉與突變,再反覆迭代。

優點是搜尋範圍廣,缺點是參數不好調,也不保證一定找到全域最佳。

五個步驟

基因演算法(Genetic Algorithm, GA)模仿天擇,用一群候選解不斷演化來逼近好答案。流程固定是五步,循環執行。

第一步,編碼與初始化。 把問題的解編成一串「基因」(常用二進位串、整數串或實數向量),隨機產生一群個體當作第一代。

第二步,評估適應度。 用適應度函數(fitness function)算每個個體有多好。這一步是整個演算法的核心,適應度函數設計錯了,後面再怎麼演化都沒用。

第三步,選擇。 依適應度挑出要繁衍的個體。常見做法有輪盤法(適應度越高被選中機率越大)與競賽選擇(隨機抓幾個比一比,贏的出線)。競賽選擇比較不容易被少數超強個體壟斷。

第四步,交配(crossover)。 把兩個父代的基因片段交換,產生子代。這是 GA 產生新解的主要方式。

第五步,突變(mutation)。 以很低的機率隨機改動某些基因。這是避免整群卡在局部最優的唯一手段。

幾個關鍵參數

菁英保留(elitism)幾乎一定要開。沒有它,這一代最好的解可能在交配與突變後消失,導致整體表現上下震盪不收斂。

最常見的失敗模式是早熟收斂(premature convergence):族群很快變得同質化,所有個體長得幾乎一樣,交配產生不出新東西,只剩突變在推進,效率極低。對策是加大族群、提高突變率,或用小生境(niching)等機制維持多樣性。

參數
族群大小
常見範圍
50 到 200
影響
太小容易早熟收斂,太大則每代計算成本高
參數
交配率
常見範圍
0.6 到 0.9
影響
主要的搜尋動力
參數
突變率
常見範圍
0.001 到 0.05
影響
太低會卡住,太高會退化成隨機搜尋
參數
菁英保留數
常見範圍
1 到 5
影響
保證最好的個體不會在演化中被弄丟

什麼時候值得用

值得: 搜尋空間離散或不連續、目標函數不可微、有多個彼此衝突的目標(多目標最佳化用 NSGA-II 這類 GA 變體很成熟)、只要「夠好」不需要「最佳」。排班、路徑規劃、參數組合最佳化都是典型場景。

不值得: 問題可微就直接用梯度法,快很多。有現成的專用演算法(例如線性規劃)就用專用的。每次評估適應度都很昂貴時,貝氏最佳化通常比 GA 更省評估次數。

GA 不保證找到最佳解,也沒有收斂速度的理論保證。它的價值在於「什麼問題都能套」,不在於效率。

情境判斷

Q1:如果問題空間很大又沒有明確梯度,基因演算法有機會派上用場嗎?

有,這正是它常被拿來解的類型。

Q2:如果你只想快速得到精確到小數點後很多位的最優解,基因演算法一定最合適嗎?

不一定,它比較擅長找不錯的近似解,不是每次都要追求數學上的精確最優。

常見問題

相關術語

本頁內容有提到,或屬於同一組主題的術語

來源

這個術語目前沒有標註外部來源。

其他格式:Markdown 版本