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

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

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

破解未知信息

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

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

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

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

一些理論

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

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

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

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

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

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

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

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

給我看一些代碼！

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

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

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

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

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

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

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

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

calcFitness()、select()、reproduce()甚至stop()方法的實(shí)現(xiàn)是特定于我們?cè)噲D解決的問(wèn)題的。

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

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

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

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

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

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

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

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

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

結(jié)論

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

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

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

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

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

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