遺傳演算法

遺傳演算法是一類自適應的隨機最佳化 演算法，涉及搜尋和最佳化。遺傳演算法最早由霍蘭德 (Holland) 於 1975 年使用。

基本思想是嘗試模擬自然選擇的簡單圖景，以找到一個好的演算法。第一步是變異或隨機改變給定的樣本程式集合。第二步是選擇步驟，通常透過針對適應度函式進行衡量來完成。重複此過程，直到找到合適的解決方案。

有許多不同型別的遺傳演算法。涉及變異的步驟取決於樣本程式的表示方式，以及程式設計師是否包含各種交叉技術。適應度測試也取決於程式設計師。

與梯度流最佳化類似，該過程可能陷入適應度函式的區域性最大值。遺傳演算法的一個優點是它不需要適應度函式非常平滑，因為執行的是隨機搜尋而不是沿著最小阻力路徑。但是，要獲得成功，可修改引數與適應度之間需要存在某種良好的關係。一般來說，會遇到計算不可約性。

霍蘭德建立了一個電子生物體作為二進位制字串（“染色體”），然後使用遺傳和進化原理，透過與適應度成比例的選擇進行繁殖（包括隨機交叉和變異），以有效地搜尋巨大的解空間。所謂的遺傳程式語言應用相同的原理，使用表示式樹而不是位串作為“染色體”。