詳解R語言中的遺傳算法

文 | 張丹(Conan)

 

前言

 

人類總是在生活中摸索規(guī)律，把規(guī)律總結(jié)為經(jīng)驗，再把經(jīng)驗傳給后人，讓后人發(fā)現(xiàn)更多的規(guī)規(guī)律，每一次知識的傳遞都是一次進化的過程，最終會形成了人類的智慧。自然界規(guī)律，讓人類適者生存地活了下來，聰明的科學家又把生物進化的規(guī)律，總結(jié)成遺傳算法，擴展到了更廣的領(lǐng)域中。

 

本文將帶你走進遺傳算法的世界。

 

目錄

 

遺傳算法介紹

遺傳算法原理

遺傳算法R語言實現(xiàn)

 

1. 遺傳算法介紹

 

遺傳算法是一種解決最優(yōu)化的搜索算法，是進化算法的一種。進化算法最初借鑒了達爾文的進化論和孟德爾的遺傳學說，從生物進化的一些現(xiàn)象發(fā)展起來，這些現(xiàn)象包括遺傳、基因突變、自然選擇和雜交等。遺傳算法通過模仿自然界生物進化機制，發(fā)展出了隨機全局搜索和優(yōu)化的方法。遺傳算法其本質(zhì)是一種高效、并行、全局搜索的方法，它能在搜索過程中自動獲取和積累有關(guān)搜索空間的知識，并自適應(yīng)的控制搜索過程，計算出全局最優(yōu)解。

 

遺傳算法的操作使用適者生存的原則，在潛在的種群中逐次產(chǎn)生一個近似最優(yōu)解的方案，在每一代中，根據(jù)個體在問題域中的適應(yīng)度值和從自然遺傳學中借鑒來的再造方法進行個體選擇，產(chǎn)生一個新的近似解。這個過程會導致種群中個體的進化，得到的新個體比原來個體更能適應(yīng)環(huán)境，就像自然界中的改造一樣。

 

如果從生物進化的角度，我們可以這樣理解。在一個種群中，個體數(shù)量已經(jīng)有一定規(guī)模，為了進化發(fā)展，通過選擇和繁殖產(chǎn)生下一代的個體，其中繁殖過程包括交配和突變。根據(jù)適者生存的原則，選擇過程會根據(jù)新個體的適應(yīng)度進行保留或淘汰，但也不是完全以適應(yīng)度高低作為導向，如果單純選擇適應(yīng)度高的個體可能會產(chǎn)生局部最優(yōu)的種群，而非全局最優(yōu)，這個種群將不會再進化，稱為早熟。之后，通過繁殖過程，讓個體兩兩交配產(chǎn)生下一代新個體，上一代個體中優(yōu)秀的基因會保留給下一代，而劣制的基因?qū)⒈粋€體另一半的基因所代替。最后，通過小概率事件發(fā)生基因突變，通過突變產(chǎn)生新的下一代個體，實現(xiàn)種群的變異進化。

 

經(jīng)過這一系列的選擇、交配和突變的過程，產(chǎn)生的新一代個體將不同于初始的一代，并一代一代向增加整體適應(yīng)度的方向發(fā)展，因為最好的個體總是更多的被選擇去產(chǎn)生下一代，而適應(yīng)度低的個體逐漸被淘汰掉。這樣的過程不斷的重復(fù)：每個個體被評價，計算出適應(yīng)度，兩個個體交配，然后突變，產(chǎn)生第三代。周而復(fù)始，直到終止條件滿足為止。

 

遺傳算法需要注意的問題：

 

遺傳算法在適應(yīng)度函數(shù)選擇不當?shù)那闆r下有可能收斂于局部最優(yōu)，而不能達到全局最優(yōu)。

 

初始種群的數(shù)量很重要，如果初始種群數(shù)量過多，算法會占用大量系統(tǒng)資源；如果初始種群數(shù)量過少，算法很可能忽略掉最優(yōu)解。

 

對于每個解，一般根據(jù)實際情況進行編碼，這樣有利于編寫變異函數(shù)和適應(yīng)度函數(shù)。

 

在編碼過的遺傳算法中，每次變異的編碼長度也影響到遺傳算法的效率。如果變異代碼長度過長，變異的多樣性會受到限制；如果變異代碼過短，變異的效率會非常低下，選擇適當?shù)淖儺愰L度是提高效率的關(guān)鍵。

 

變異率是一個重要的參數(shù)。

 

對于動態(tài)數(shù)據(jù)，用遺傳算法求最優(yōu)解比較困難，因為染色體種群很可能過早地收斂，而對以后變化了的數(shù)據(jù)不再產(chǎn)生變化。對于這個問題，研究者提出了一些方法增加基因的多樣性，從而防止過早的收斂。其中一種是所謂觸發(fā)式超級變異，就是當染色體群體的質(zhì)量下降（彼此的區(qū)別減少）時增加變異概率；另一種叫隨機外來染色體，是偶爾加入一些全新的隨機生成的染色體個體，從而增加染色體多樣性。

 

選擇過程很重要，但交叉和變異的重要性存在爭議。一種觀點認為交叉比變異更重要，因為變異僅僅是保證不丟失某些可能的解；而另一種觀點則認為交叉過程的作用只不過是在種群中推廣變異過程所造成的更新，對于初期的種群來說，交叉幾乎等效于一個非常大的變異率，而這么大的變異很可能影響進化過程。

 

遺傳算法很快就能找到良好的解，即使是在很復(fù)雜的解空間中。

 

遺傳算法并不一定總是最好的優(yōu)化策略，優(yōu)化問題要具體情況具體分析。所以在使用遺傳算法的同時，也可以嘗試其他算法，互相補充，甚至根本不用遺傳算法。

 

遺傳算法不能解決那些“大海撈針”的問題，所謂“大海撈針”問題就是沒有一個確切的適應(yīng)度函數(shù)表征個體好壞的問題，使得算法的進化失去導向。

 

對于任何一個具體的優(yōu)化問題，調(diào)節(jié)遺傳算法的參數(shù)可能會有利于更好的更快的收斂，這些參數(shù)包括個體數(shù)目、交叉率和變異率。例如太大的變異率會導致丟失最優(yōu)解，而過小的變異率會導致算法過早的收斂于局部最優(yōu)點。對于這些參數(shù)的選擇，現(xiàn)在還沒有實用的上下限。

 

適應(yīng)度函數(shù)對于算法的速度和效果也很重要。

 

遺傳算法的應(yīng)用領(lǐng)域包括計算機自動設(shè)計、生產(chǎn)調(diào)度、電路設(shè)計、游戲設(shè)計、機器人學習、模糊控制、時間表安排，神經(jīng)網(wǎng)絡(luò)訓練等。然而，我準備把遺傳算法到金融領(lǐng)域，比如回測系統(tǒng)的參數(shù)尋優(yōu)方案，我會在以后的文章中，介紹有關(guān)金融解決方案。

 

2. 遺傳算法原理

 

在遺傳算法里，優(yōu)化問題的解是被稱為個體，它表示為一個變量序列，叫做染色體或者基因串。染色體一般被表達為簡單的字符串或數(shù)字串，也有其他表示法，這一過程稱為編碼。首先要創(chuàng)建種群，算法隨機生成一定數(shù)量的個體，有時候也可以人工干預(yù)這個過程進行，以提高初始種群的質(zhì)量。在每一代中，每一個個體都被評價，并通過計算適應(yīng)度函數(shù)得到一個適應(yīng)度數(shù)值。種群中的個體被按照適應(yīng)度排序，適應(yīng)度高的在前面。

 

接下來，是產(chǎn)生下一代個體的種群，通過選擇過程和繁殖過程完成。

 

選擇過程，是根據(jù)新個體的適應(yīng)度進行的，但同時并不意味著完全的以適應(yīng)度高低作為導向，因為單純選擇適應(yīng)度高的個體將可能導致算法快速收斂到局部最優(yōu)解而非全局最優(yōu)解，我們稱之為早熟。作為折中，遺傳算法依據(jù)原則：適應(yīng)度越高，被選擇的機會越高，而適應(yīng)度低的，被選擇的機會就低。初始的數(shù)據(jù)可以通過這樣的選擇過程組成一個相對優(yōu)化的群體。

 

繁殖過程，表示被選擇的個體進入交配過程，包括交配(crossover)和突變(mutation)，交配對應(yīng)算法中的交叉操作。一般的遺傳算法都有一個交配概率，范圍一般是0.6~1，這個交配概率反映兩個被選中的個體進行交配的概率。

 

例如，交配概率為0.8，則80%的“夫妻”個體會生育后代。每兩個個體通過交配產(chǎn)生兩個新個體，代替原來的“老”個體，而不交配的個體則保持不變。交配過程，父母的染色體相互交換，從而產(chǎn)生兩個新的染色體，第一個個體前半段是父親的染色體，后半段是母親的，第二個個體則正好相反。不過這里指的半段並不是真正的一半，這個位置叫做交配點，也是隨機產(chǎn)生的，可以是染色體的任意位置。

 

突變過程，表示通過突變產(chǎn)生新的下一代個體。一般遺傳算法都有一個固定的突變常數(shù)，又稱為變異概率，通常是0.1或者更小，這代表變異發(fā)生的概率。根據(jù)這個概率，新個體的染色體隨機的突變，通常就是改變?nèi)旧w的一個字節(jié)（0變到1，或者1變到0）。

 

遺傳算法實現(xiàn)將不斷的重復(fù)這個過程：每個個體被評價，計算出適應(yīng)度，兩個個體交配，然后突變，產(chǎn)生下一代，直到終止條件滿足為止。一般終止條件有以下幾種：

 

進化次數(shù)限制

計算耗費的資源限制，如計算時間、計算占用的CPU，內(nèi)存等

個體已經(jīng)滿足最優(yōu)值的條件，即最優(yōu)值已經(jīng)找到

當適應(yīng)度已經(jīng)達到飽和，繼續(xù)進化不會產(chǎn)生適應(yīng)度更好的個體

人為干預(yù)

 

算法實現(xiàn)原理：

1. 創(chuàng)建初始種群

2. 循環(huán)：產(chǎn)生下一代

3. 評價種群中的個體適應(yīng)度

4. 定義選擇的適應(yīng)度函數(shù)

5. 改變該種群（交配和變異）

6. 返回第二步

7. 滿足終止條件結(jié)束

 

3. 遺傳算法R語言實現(xiàn)

 

本節(jié)的系統(tǒng)環(huán)境

 

Win7 64bit

R： 3.1.1 x86_64-w64-mingw32/x64 (64-bit)

 

 

一個典型的遺傳算法要求：一個基因表示的求解域， 一個適應(yīng)度函數(shù)來評價解決方案。

 

遺傳算法的參數(shù)通常包括以下幾個：

 

種群規(guī)模(Population)，即種群中染色體個體的數(shù)目。

染色體的基因個數(shù)(Size)，即變量的數(shù)目。

交配概率(Crossover)，用于控制交叉計算的使用頻率。交叉操作可以加快收斂，使解達到最有希望的最優(yōu)解區(qū)域，因此一般取較大的交叉概率，但交叉概率太高也可能導致過早收斂。

變異概率(Mutation)，用于控制變異計算的使用頻率，決定了遺傳算法的局部搜索能力。

中止條件(Termination)，結(jié)束的標志。

在R語言中，有一些現(xiàn)成的第三方包已經(jīng)實現(xiàn)的遺傳算法，我們可以直接進行使用。

mcga包，多變量的遺傳算法，用于求解多維函數(shù)的最小值。

genalg包，多變量的遺傳算法，用于求解多維函數(shù)的最小值。

rgenoud包，復(fù)雜的遺傳算法，將遺傳算法和衍生的擬牛頓算法結(jié)合起來，可以求解復(fù)雜函數(shù)的最優(yōu)化化問題。

gafit包，利用遺傳算法求解一維函數(shù)的最小值。不支持R 3.1.1的版本。

GALGO包，利用遺傳算法求解多維函數(shù)的最優(yōu)化解。不支持R 3.1.1的版本。

 

本文將介紹mcga包和genalg包的遺傳算法的使用。

 

3.1 mcga包

 

我們使用mcga包的mcga()函數(shù)，可以實現(xiàn)多變量的遺傳算法。

 

mcga包是一個遺傳算法快速的工具包，主要解決實值優(yōu)化的問題。它使用的變量值表示基因序列，而不是字節(jié)碼，因此不需要編解碼的處理。mcga實現(xiàn)了遺傳算法的交配和突變的操作，并且可以進行大范圍和高精度的搜索空間的計算，算法的主要缺點是使用了256位的一元字母表。

 

首先，安裝mcga包。

 

查看一下mcga()函數(shù)的定義。

 

參數(shù)說明：

popsize，個體數(shù)量，即染色體數(shù)目

chsize，基因數(shù)量，限參數(shù)的數(shù)量

crossprob，交配概率，默認為1.0

mutateprob，突變概率，默認為0.01

elitism，精英數(shù)量，直接復(fù)制到下一代的染色體數(shù)目，默認為1

minval，隨機生成初始種群的下邊界值

maxval，隨機生成初始種群的上邊界值

maxiter，繁殖次數(shù)，即循環(huán)次數(shù)，默認為10

evalFunc，適應(yīng)度函數(shù)，用于給個體進行評價

 

接下來，我們給定一個優(yōu)化的問題，通過mcga()函數(shù)，計算最優(yōu)化的解。

 

題目1：設(shè)fx=(x1-5)^2 + (x2-55)^2 +(x3-555)^2 +(x4-5555)^2 +(x5-55555)^2，計算fx的最小值，其中x1，x2，x3，x4，x5為5個不同的變量。

 

從直觀上看，如果想得到fx的最小值，其實當x1=5，x2=55，x3=555，x4=5555，x5=55555時，fx=0為最小值。如果使用窮舉法，通過循環(huán)的方法找到這5個變量，估計會很費時的，我就不做測試了。下面我們看一下遺傳算法的運行情況。

 

我們得到的最優(yōu)化的結(jié)果為x1=5.000317， x2=54.997099， x3=554.999873， x4=5555.003120， x5=55554.218695，和我們預(yù)期的結(jié)果非常接近，而且耗時只有3.6秒。這個結(jié)果是非常令人滿意地，不是么！如果使用窮舉法，時間復(fù)雜度為O(n^5)，估計沒有5分鐘肯定算不出來。

 

當然，算法執(zhí)行時間和精度，都是通過參數(shù)進行配置的。如果增大個體數(shù)目或循環(huán)次數(shù)，一方面會增加算法的計算時間，另一方面結(jié)果也可能變得更精準。所以，在實際的使用過程中，需要根據(jù)一定的經(jīng)驗調(diào)整這幾個參數(shù)。

 

3.2 genalg包

 

我們使用genalg包的rbga()函數(shù)，也可以實現(xiàn)多變量的遺傳算法。

 

genalg包不僅實現(xiàn)了遺傳算法，還提供了遺傳算法的數(shù)據(jù)可視化，給用戶更直觀的角度理解算法。默認圖顯示的最小和平均評價值，表示遺傳算法的計算進度。直方圖顯出了基因選擇的頻率，即基因在當前個體中被選擇的次數(shù)。參數(shù)圖表示評價函數(shù)和變量值，非常方便地看到評價函數(shù)和變量值的相關(guān)關(guān)系。

 

首先，安裝genalg包。

 

查看一下rbga()函數(shù)的定義。

 

參數(shù)說明：

stringMin，設(shè)置每個基因的最小值

stringMax，設(shè)置每個基因的最大值

suggestions，建議染色體的可選列表

popSize，個體數(shù)量，即染色體數(shù)目，默認為200

iters，迭代次數(shù)，默認為100

 

mutationChance，突變機會，默認為1/(size+1)，它影響收斂速度和搜索空間的探測，低機率導致更快收斂，高機率增加了搜索空間的跨度。

 

elitism，精英數(shù)量，默認為20%，直接復(fù)制到下一代的染色體數(shù)目

monitorFunc，監(jiān)控函數(shù)，每產(chǎn)生一代后運行

evalFunc，適應(yīng)度函數(shù)，用于給個體進行評價

showSettings，打印設(shè)置，默認為false

verbose，打印算法運行日志，默認為false

 

接下來，我們給定一個優(yōu)化的問題，通過rbga()函數(shù)，計算最優(yōu)化的解。

 

題目2：設(shè)fx=abs(x1-sqrt(exp(1)))+abs(x2-log(pi))，計算fx的最小值，其中x1，x2為2個不同的變量。

 

從直觀上看，如果想得到fx的最小值，其實當x1=sqrt(exp(1))=1.648721， x2=log(pi)=1.14473時，fx=0為最小值。同樣地，如果使用窮舉法，通過循環(huán)的方法找到這2個變量，估計會很費時的，我也不做測試了。下面我們看一下rbga()函數(shù)的遺傳算法的運行情況。

 

程序運行截圖

 

 

需要注意的是，程序在要命令行界面運行，如果在RStudio中運行，會出現(xiàn)下面的錯誤提示。

 

我們迭代1000次后，查看計算結(jié)果。

 

我們得到的最優(yōu)化的結(jié)果為x1=1.650571， x2=1.145784，非常接近最終的結(jié)果。另外，我們可以通過genalg包的可視化功能，看到迭代過程的每次的計算結(jié)果。下面截圖分為對應(yīng)1次迭代，10次迭代，200次迭代和1000次迭代的計算結(jié)果。從圖中可以看出，隨著迭代次數(shù)的增加，優(yōu)選出的結(jié)果集變得越來越少，而且越來越精準。

 

 

默認圖輸出，用于描述遺傳過程的進展，X軸為迭代次數(shù)，Y軸評價值，評價值越接近于0越好。在1000迭代1000次后，基本找到了精確的結(jié)果。

 

> plot(m2)

 

 

直方圖輸出，用于描述對染色體的基因選擇頻率，即一個基因在染色體中的當前人口被選擇的次數(shù)。當x1在1.65區(qū)域時，被選擇超過80次；當x2在1.146區(qū)域時，被選擇超過了80次。通過直方圖，我們可以理解為更優(yōu)秀的基因被留給了后代。

 

> plot(m2，type='hist')

 

 

參數(shù)圖輸出，用于描述評價函數(shù)和變量的值的相關(guān)關(guān)系。對于x1，評價值越小，變量值越準確，但相關(guān)關(guān)系不明顯。對于x2，看不出相關(guān)關(guān)系。

 

> plot(m2，type='vars')

 

 

對比mcga包和genalg包，mcga包適合計算大范圍取值空間的最優(yōu)解，而用genalg包對于大范圍取值空間的計算就表現(xiàn)就不太好了。從另一個方面講，genalg包提供了可視化工具，可以讓我們直觀的看遺傳算法的收斂過程，對于算法的理解和調(diào)優(yōu)是非常有幫助的。

 

在掌握了遺傳算法后，我們就可以快度地處理一些優(yōu)化的問題了，比如接下來我會介紹的金融回測系統(tǒng)的參數(shù)尋優(yōu)方案。讓我們遠離窮舉法，珍惜CPU的每一秒時間。

 

來自粉絲日志