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

關(guān)鍵要點(diǎn)

• 遺傳算法模擬“適者生存”等進(jìn)化過程，利用選擇、交叉和變異等機(jī)制來尋找復(fù)雜問題的最優(yōu)解。
• 在遺傳算法中，潛在的解決方案表示為染色體，其適用性通過適應(yīng)度函數(shù)進(jìn)行評估，該函數(shù)決定其被選中進(jìn)行繁殖的概率。
• 交叉過程將來自一對親本解決方案的特征組合起來以創(chuàng)建新的后代，而變異則會在后代中引入隨機(jī)變化，從而保持遺傳多樣性并潛在地發(fā)現(xiàn)新的解決方案。
• 由于遺傳算法能夠有效地探索大型、復(fù)雜的解決方案空間，因此對于傳統(tǒng)搜索和優(yōu)化方法難以解決的問題非常有效。
• 遺傳算法的實(shí)際應(yīng)用范圍從設(shè)計具有增強(qiáng)性能特征的天線到優(yōu)化網(wǎng)頁設(shè)計，這說明了它們在解決實(shí)際問題方面的多功能性和強(qiáng)大功能。

破解未知信息

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

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

有一天午餐時，他向你提出了一個挑戰(zhàn)：“我有一條信息要告訴你，親愛的醫(yī)生！我當(dāng)然不能告訴你是什么。但我告訴你，它有12個字符長。這些字符可以是任何字母、空格或標(biāo)點(diǎn)符號。我會告訴你你的猜測與實(shí)際答案的差距。你很聰明；你認(rèn)為你能解開它嗎？”

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

一些理論

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

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

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

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

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

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

不出所料，遺傳算法借鑒了大量遺傳科學(xué)的詞匯。因此，在我們進(jìn)一步討論之前，讓我們完善一些術(shù)語：

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

給我看一些代碼！

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

// ... (Candidate class and GeneticAlgorithm class code as provided in the original text) ...

我們首先定義一個Candidate數(shù)據(jù)對象，只是為了將染色體與其適應(yīng)度分?jǐn)?shù)配對。為了方便起見，還附加了一個靜態(tài)排序方法；當(dāng)我們需要查找或輸出最合適的染色體時，它會派上用場。

接下來，我們有一個GeneticAlgorithm類，它實(shí)現(xiàn)了遺傳算法本身。

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

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

像randomInt()、init()和run()這樣的方法可能被認(rèn)為是樣板。但僅僅因?yàn)橛袠影宀⒉灰馕吨粫δM產(chǎn)生實(shí)際影響。例如，遺傳算法大量使用隨機(jī)性。雖然內(nèi)置的Math.random()函數(shù)適合我們的目的，但對于其他問題，您需要更精確的隨機(jī)生成器。Crypto.getRandomValues()提供更強(qiáng)的密碼學(xué)隨機(jī)值。

性能也是一個考慮因素。我在本文中力求清晰易懂，但請記住，操作將反復(fù)進(jìn)行。您可能會發(fā)現(xiàn)自己需要微優(yōu)化循環(huán)中的代碼，使用更高效的內(nèi)存數(shù)據(jù)結(jié)構(gòu)，以及內(nèi)聯(lián)代碼而不是將其分離到函數(shù)/方法中，所有這些都與您的實(shí)現(xiàn)語言無關(guān)。

calcFitness()、select()、reproduce()甚至stop()方法的實(shí)現(xiàn)是特定于我們試圖解決的問題的。

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

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

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

我們也不限于兩個父代染色體；我們可以組合來自三個或更多候選者的基因，甚至可以基于單個候選者構(gòu)建?？紤]一個通過繪制隨機(jī)多邊形來進(jìn)化圖像的算法。在這種情況下，我們的染色體實(shí)現(xiàn)為圖像數(shù)據(jù)。在每一代中，從種群中選擇最合適的圖像作為父代，并且所有子代候選者都是通過將其自身的多邊形繪制到父代副本上來生成的。父代染色體/圖像作為基礎(chǔ)，子代染色體/圖像是父代的獨(dú)特變異/圖紙。

遺傳算法的實(shí)際應(yīng)用

遺傳算法既可以用于娛樂，也可以用于盈利。也許遺傳算法實(shí)際應(yīng)用的兩個最流行的例子是BoxCar 2D和NASA進(jìn)化出的X波段天線。

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

2006年，NASA的太空技術(shù)5號任務(wù)在太空中測試了各種新技術(shù)。其中一項(xiàng)技術(shù)是使用遺傳算法設(shè)計的新型天線。設(shè)計新型天線可能是一個非常昂貴且耗時的過程。它需要特殊的專業(yè)知識，并且當(dāng)需求發(fā)生變化或原型無法按預(yù)期執(zhí)行時，經(jīng)常會發(fā)生挫折。進(jìn)化出的天線創(chuàng)建時間更短，增益更高，功耗更低。討論設(shè)計過程的論文全文可在網(wǎng)上免費(fèi)獲得（使用進(jìn)化算法的自動化天線設(shè)計）。遺傳算法也已被用于優(yōu)化現(xiàn)有天線設(shè)計以獲得更高的性能。

遺傳算法甚至已被用于網(wǎng)頁設(shè)計！Elijah Mensch的一個高級項(xiàng)目（通過應(yīng)用交互式遺傳算法優(yōu)化網(wǎng)站設(shè)計）使用它們通過操作CSS規(guī)則并使用A/B測試對適應(yīng)度進(jìn)行評分來優(yōu)化新聞文章輪播。

結(jié)論

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

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

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

關(guān)于遺傳算法的常見問題

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

以上是遺傳算法簡介的詳細(xì)內(nèi)容。更多信息請關(guān)注PHP中文網(wǎng)其他相關(guān)文章！