遺傳算法簡介

遺傳算法是一種通過模擬自然進化過程（如“適者生存”、染色體交叉和變異）來尋找問題最佳解決方案的程序。本文將簡要介紹遺傳算法的編寫方法，討論編寫自己的算法時需要考慮的一些重要因素，並提供一些遺傳算法實際應用的示例。

關鍵要點

• 遺傳算法模擬“適者生存”等進化過程，利用選擇、交叉和變異等機制來尋找複雜問題的最優解。
• 在遺傳算法中，潛在的解決方案表示為染色體，其適用性通過適應度函數進行評估，該函數決定其被選中進行繁殖的概率。
• 交叉過程將來自一對親本解決方案的特徵組合起來以創建新的後代，而變異則會在後代中引入隨機變化，從而保持遺傳多樣性並潛在地發現新的解決方案。
• 由於遺傳算法能夠有效地探索大型、複雜的解決方案空間，因此對於傳統搜索和優化方法難以解決的問題非常有效。
• 遺傳算法的實際應用範圍從設計具有增強性能特徵的天線到優化網頁設計，這說明了它們在解決實際問題方面的多功能性和強大功能。

破解未知信息

時間是2369年，人類已經遍布星辰大海。你是一位年輕而聰明的醫生，駐紮在一個繁忙的深空星際基地，那裡熙攘著星際旅行者、商人，以及偶爾出現的亡命之徒。你到達後不久，基地的一個店主對你產生了興趣。他聲稱自己只是一個簡單的裁縫，但謠言說他是為一個特別邪惡的政權工作的秘密特工。

你們開始每週一起共進午餐，討論從政治到詩歌的各種話題。即使過了幾個月，你仍然不確定他是在表達浪漫情愫還是在套取秘密（你當然沒有任何秘密）。也許兩者兼而有之。

有一天午餐時，他向你提出了一個挑戰：“我有一條信息要告訴你，親愛的醫生！我當然不能告訴你是什麼。但我告訴你，它有12個字符長。這些字符可以是任何字母、空格或標點符號。我會告訴你你的猜測與實際答案的差距。你很聰明；你認為你能解開它嗎？”

你回到醫療艙的辦公室，仍然想著他剛才說的話。突然，你之前在附近電腦上運行的一個基因測序模擬實驗給了你一個主意。你不是密碼破譯專家，但也許你可以利用你在遺傳學方面的專業知識來破譯他的信息！

一些理論

正如我在開頭提到的，遺傳算法是一種使用模擬驅動進化的操作來搜索解決方案的程序。經過多次迭代，算法從一組可能的解決方案中選擇最佳候選者（猜測），將它們重新組合，並檢查哪些組合使它更接近解決方案。較差的候選者將被丟棄。

在上面的場景中，秘密信息中的任何字符都可以是A-Z、空格或基本標點符號。假設這給了我們以下32個字符的“字母表”：ABCDEFGHIJKLMNOPQRSTUVWXYZ -.,!?這意味著有32¹²（大約1.15×10¹⁸）種可能的信息，但其中只有一個是正確的。檢查每種可能性需要花費太長時間。相反，遺傳算法將隨機選擇12個字符，並要求裁縫/間諜對結果與他的信息有多接近進行評分。這比暴力搜索更有效，因為分數讓我們能夠微調未來的候選者。反饋使我們能夠衡量每次猜測的適應度，並有望避免在死胡同浪費時間。

假設我們做了三個猜測：HOMLK?WSRZDJ、BGK KA!QTPXC和XELPOCV.XLF!。第一個候選者的分數為248.2，第二個為632.5，第三個為219.5。分數的計算方式取決於具體情況，我們稍後會討論，但現在讓我們假設它是基於候選者和目標信息之間的偏差：完美的分數是0（即沒有偏差；候選者和目標相同），而較高的分數意味著偏差越大。得分248.2和219.5的猜測比得分635.5的猜測更接近秘密信息的內容。

未來的猜測是通過組合最佳嘗試進行的。組合候選者的方法有很多，但現在我們考慮一種簡單的交叉方法：新猜測中的每個字符都有50-50的概率從第一個或第二個父代候選者中復制。如果我們採用HOMLK?WSRZDJ和XELPOCV.XLF!這兩個猜測，那麼我們後代候選者的第一個字符有50%的概率是H，50%的概率是X，第二個字符將是O或E ，依此類推。後代可能是HELLO?W.RLD!。

通過交叉生成新的候選者

然而，如果我們只使用父代候選者的值，則在多次迭代中可能會出現一個問題：缺乏多樣性。如果我們有一個候選者由全部A組成，另一個由全部B組成，那麼僅通過交叉生成的任何後代都將僅由A和B組成。如果解決方案包含C，我們就會很不幸。

為了減輕這種風險並在仍然縮小解決方案範圍的同時保持多樣性，我們可以引入微小的變化。與其直接進行50-50的分割，我們允許一個小的概率來代替字母表中的任意值。通過這種變異，後代可能會變成HELLO WORLD!。

變異使事情保持新鮮！

不出所料，遺傳算法借鑒了大量遺傳科學的詞彙。因此，在我們進一步討論之前，讓我們完善一些術語：

• 等位基因：遺傳字母表中的一個成員。等位基因的定義取決於算法。例如，0和1可能是用於處理二進制數據的遺傳算法的等位基因，用於處理代碼的算法可以使用函數指針等。在我們的秘密信息場景中，等位基因是字母表中的字母、空格和各種標點符號。
• 染色體：給定的等位基因序列；候選解決方案；“猜測”。在我們的場景中，HOMLK?WSRZDJ、XELPOCV.XLF!和HELLO WORLD!都是染色體。
• 基因：染色體中特定位置的等位基因。對於染色體HOMLK?WSRZDJ，第一個基因是H，第二個基因是O，第三個基因是M，依此類推。
• 種群：作為問題解決方案提出的一個或多個候選染色體的集合。
• 世代：算法特定迭代期間的種群。一代中的候選者提供基因來產生下一代的種群。
• 適應度：評估候選者與所需解決方案接近程度的度量。適應性強的染色體更有可能將其基因傳遞給未來的候選者，而適應性較弱的染色體更有可能被丟棄。
• 選擇：選擇一些候選者進行繁殖（用於創建新的候選染色體）並丟棄其他候選者的過程。存在多種選擇策略，它們對選擇較弱候選者的容忍度各不相同。
• 繁殖：將一個或多個候選者的基因組合起來以產生新的候選者的過程。供體染色體稱為父代，產生的染色體稱為後代。
• 變異：在後代中隨機引入異常基因，以防止在許多世代中失去遺傳多樣性。

給我看一些代碼！

我懷疑，鑑於高級概述和術語列表，您可能現在很想看到一些代碼。因此，讓我們來看一些解決我們的秘密信息問題的JavaScript代碼。在閱讀過程中，我邀請您思考哪些方法可能被認為是“樣板代碼”，以及哪些方法的實現更緊密地與我們試圖解決的問題相關聯：

<code class="language-javascript">// ... (Candidate class and GeneticAlgorithm class code as provided in the original text) ...</code>

我們首先定義一個Candidate數據對象，只是為了將染色體與其適應度分數配對。為了方便起見，還附加了一個靜態排序方法；當我們需要查找或輸出最合適的染色體時，它會派上用場。

接下來，我們有一個GeneticAlgorithm類，它實現了遺傳算法本身。

構造函數採用解決模擬所需各種參數的對象。它提供了一種指定遺傳字母表、目標消息以及其他參數的方法，這些參數用於定義模擬將在其下運行的約束。在上面的示例中，我們期望每一代都有100個候選者的種群。從中，只有40個染色體將被選中進行繁殖。我們有3%的概率引入變異，並且在發生變異時，我們將最多改變兩個基因。 maxGenerations值用作保護措施；如果我們在100萬代後沒有收斂到一個解決方案，我們將無論如何終止腳本。

值得一提的是，運行算法時提供的種群、選擇大小和最大世代數相當小。更複雜的問題可能需要更大的搜索空間，這反過來會增加算法的內存使用量以及運行所需的時間。但是，強烈建議使用較小的變異參數。如果它們變得太大，我們將失去基於適應度繁殖候選者的任何好處，並且模擬開始變成隨機搜索。

像randomInt()、init()和run()這樣的方法可能被認為是樣板。但僅僅因為有樣板並不意味著它不會對模擬產生實際影響。例如，遺傳算法大量使用隨機性。雖然內置的Math.random()函數適合我們的目的，但對於其他問題，您需要更精確的隨機生成器。 Crypto.getRandomValues()提供更強的密碼學隨機值。

性能也是一個考慮因素。我在本文中力求清晰易懂，但請記住，操作將反復進行。您可能會發現自己需要微優化循環中的代碼，使用更高效的內存數據結構，以及內聯代碼而不是將其分離到函數/方法中，所有這些都與您的實現語言無關。

calcFitness()、select()、reproduce()甚至stop()方法的實現是特定於我們試圖解決的問題的。

calcFitness()返回一個值，該值根據某些期望標準衡量染色體的適應度——在我們的例子中，它是它與秘密消息匹配的程度。計算適應度幾乎總是依賴於具體情況；我們的實現使用每個基因的ASCII值計算均方誤差，但其他指標可能更合適。例如，我可以計算兩個值之間的漢明距離或萊文斯坦距離，甚至可以結合多個測量值。最終，重要的是適應度函數要根據手頭的問題返回有用的測量值，而不僅僅是布爾“適合”/“不適合”。

select()方法演示了一種精英選擇策略——僅選擇整個種群中最合適的候選者進行繁殖。正如我前面提到的，還存在其他策略，例如錦標賽選擇，它從種群中各個候選者的集合中選擇最合適的候選者，以及玻爾茲曼選擇，它對選擇候選者施加越來越大的壓力。這些不同方法的目的是確保染色體有機會傳遞可能在以後被證明有益的基因，即使它可能並不立即顯而易見。這些和其他選擇策略的深入描述以及示例實現很容易在網上找到。

說明各種選擇策略

組合基因的方法也有很多。我們的代碼使用均勻交叉創建後代，其中每個基因都有相同的概率從一個父代中選擇。其他策略可能偏向於一個父代的基因而不是另一個父代。另一種流行的策略是k點交叉，其中染色體在k個點處分割，產生k 1個片段，這些片段組合起來產生後代。交叉點可以是固定的，也可以是隨機選擇的。

說明k點交叉策略

我們也不限於兩個父代染色體；我們可以組合來自三個或更多候選者的基因，甚至可以基於單個候選者構建。考慮一個通過繪製隨機多邊形來進化圖像的算法。在這種情況下，我們的染色體實現為圖像數據。在每一代中，從種群中選擇最合適的圖像作為父代，並且所有子代候選者都是通過將其自身的多邊形繪製到父代副本上來生成的。父代染色體/圖像作為基礎，子代染色體/圖像是父代的獨特變異/圖紙。

遺傳算法的實際應用

遺傳算法既可以用於娛樂，也可以用於盈利。也許遺傳算法實際應用的兩個最流行的例子是BoxCar 2D和NASA進化出的X波段天線。

BoxCar 2D是一個使用遺傳算法來進化能夠穿越模擬地形的最佳“汽車”的模擬。汽車由八個隨機向量構成一個多邊形，並將車輪連接到隨機點。該項目的網站可以在boxcar2d.com上找到，該網站在其關於頁面上簡要介紹了該算法，並提供了一個排行榜，展示了一些最佳設計。不幸的是，該網站使用Flash，現在可能對許多人來說無法訪問——在這種情況下，如果您好奇，可以在YouTube上找到各種屏幕錄製。您可能還想查看Rafael Matsunaga使用HTML5技術編寫的類似（優秀）模擬，可在rednuht.org/genetic_cars_2上找到。

BoxCar 2D中進化出的汽車，圖片來自BoxCar 2D排行榜

2006年，NASA的太空技術5號任務在太空中測試了各種新技術。其中一項技術是使用遺傳算法設計的新型天線。設計新型天線可能是一個非常昂貴且耗時的過程。它需要特殊的專業知識，並且當需求發生變化或原型無法按預期執行時，經常會發生挫折。進化出的天線創建時間更短，增益更高，功耗更低。討論設計過程的論文全文可在網上免費獲得（使用進化算法的自動化天線設計）。遺傳算法也已被用於優化現有天線設計以獲得更高的性能。

它們類別中最好的進化天線，圖片來自自動化天線設計論文

遺傳算法甚至已被用於網頁設計！ Elijah Mensch的一個高級項目（通過應用交互式遺傳算法優化網站設計）使用它們通過操作CSS規則並使用A/B測試對適應度進行評分來優化新聞文章輪播。

第1代和第9代的最佳佈局，圖片來自優化網站設計論文

結論

到目前為止，您應該對遺傳算法是什麼有了基本的了解，並且對它們的詞彙足夠熟悉，可以解讀您在自己的研究中可能遇到的任何資源。但是，理解理論和術語只是工作的一半。如果您計劃編寫自己的遺傳算法，您還必須了解您的特定問題。在開始之前，以下是一些需要自問的重要問題：

• 我如何將我的問題表示為染色體？我的有效等位基因是什麼？
• 我知道目標是什麼嗎？也就是說，我在尋找什麼？是特定值還是任何適應度超過某個閾值的解決方案？
• 我如何量化候選者的適應度？
• 我如何組合和變異候選者以產生新的候選解決方案？

我希望我還幫助您了解程序如何從自然中汲取靈感——不僅在形式上，而且在過程和功能上。請隨時在論壇中分享您自己的想法。

關於遺傳算法的常見問題

• 什麼是遺傳算法（GA）？遺傳算法是一種啟發式搜索和優化技術，其靈感來自自然選擇過程。它用於通過模擬進化的原理來尋找優化和搜索問題的近似解。
• 遺傳算法是如何工作的？遺傳算法通過在連續幾代中進化候選解決方案的種群來工作。該過程包括選擇、交叉（重組）、變異和評估種群中的個體，旨在迭代地提高解決方案的質量。
• 遺傳算法適用於哪些類型的問題？遺傳算法用途廣泛，可以應用於各種優化和搜索問題，包括但不限於調度、路由、機器學習和函數優化。
• 如何為遺傳算法選擇參數？種群大小、變異率和交叉率等參數取決於特定問題和解決方案空間的特徵。實驗和調整是為給定問題找到最佳參數值的常用做法。
• 適應度函數在遺傳算法中的作用是什麼？適應度函數量化了個體解決方案在給定問題中的執行情況。它指導選擇過程，有利於對優化目標有積極貢獻的解決方案。

以上是遺傳算法簡介的詳細內容。更多資訊請關注PHP中文網其他相關文章！