遺傳算法在教學(xué)中的可視化設(shè)計與實現(xiàn)

吳清揚(yáng)

（廣東省財政職業(yè)技術(shù)學(xué)校，廣東廣州，510445）

遺傳算法在教學(xué)中的可視化設(shè)計與實現(xiàn)

吳清揚(yáng)

（廣東省財政職業(yè)技術(shù)學(xué)校，廣東廣州，510445）

遺傳算法、網(wǎng)絡(luò)神經(jīng)算法等智能算法（進(jìn)化算法）是一種快速、高效非精確算法，由于它突破了傳統(tǒng)的精確算法的思維，因而一直是教學(xué)上的難點(diǎn)與重點(diǎn)。文章嘗試以遺傳算法求解8位二進(jìn)制最大數(shù)為例，通過可視化的方式來展現(xiàn)遺傳算法的運(yùn)算過程，加深對遺傳算法思想的理解，達(dá)到幫助學(xué)生理解遺傳算法的目的。

遺傳算法教學(xué)選擇操作交叉操作變異操作

0 引言

近年來，隨著科技的不斷進(jìn)步，智能化已經(jīng)不可回避成為的熱點(diǎn)問題，尤其是2016年3月份阿爾法圍棋程序（AlphaGo）以4:1戰(zhàn)勝了世界圍棋冠軍李世石后，以遺傳算法、網(wǎng)絡(luò)神經(jīng)、模擬退火、禁忌搜索等為代表的智能算法已然成為學(xué)習(xí)的焦點(diǎn)與熱點(diǎn)，而由于智能算法突破了傳統(tǒng)精確算法的思維，它是通過模擬自然現(xiàn)象的方式進(jìn)行優(yōu)化處理，一直是教學(xué)上的難點(diǎn)與重點(diǎn)。本文嘗試以遺傳算法求解8位二進(jìn)制最大數(shù)為例，通過可視化的方式來展現(xiàn)遺傳算法的運(yùn)算過程，從而激發(fā)學(xué)生的學(xué)習(xí)興趣，達(dá)到幫助學(xué)生理解遺傳算法的目的。

1 遺傳算法思想概要

遺傳算法是根據(jù)達(dá)爾文進(jìn)化論的“物競天擇，適者生存”現(xiàn)象而提出的一種隨機(jī)搜索算法，該算法將優(yōu)化問題看作是自然界的進(jìn)化過程，通過模擬大自然中生物的進(jìn)化過程中的遺傳規(guī)律，來達(dá)到尋優(yōu)的目的。生物進(jìn)化與遺傳算法之間的對應(yīng)關(guān)系如表1所示。

在遺傳算法中，首先對優(yōu)化問題進(jìn)行編碼，編碼后的一個解稱為一個染色體，組成染色體的元素稱為基因。一個群體由若干個染色體組成，染色體的個數(shù)稱為群體的規(guī)模。與自然界中的生存環(huán)境相對應(yīng)，在遺傳算法中用適應(yīng)函數(shù)表示環(huán)境，它是已編碼的解的函數(shù)，是一個解適應(yīng)環(huán)境的評價。一般情況下，適應(yīng)函數(shù)值大表示染色體的適應(yīng)環(huán)境的能力強(qiáng)。適應(yīng)函數(shù)相當(dāng)于自然中環(huán)境的作用。

當(dāng)適應(yīng)函數(shù)確定后，自然選擇規(guī)律將以適應(yīng)函數(shù)值的大小來決定一個染色體繼續(xù)生存下去的概率。生存下來的染色體成為種群，它們中的部分或者全部以一定概率進(jìn)行交叉，繁衍，從而得到下一代的群體。交叉是一個生殖過程，發(fā)生在兩個染色體之間，作為雙親的兩個染色體，交換部分基因，生殖出兩個新的染色體，即問題的新解。交叉或者稱為雜交，是遺傳算法區(qū)別于其他優(yōu)化算法的最主要特征。進(jìn)行進(jìn)化的過程中，染色體的某些基因可能會發(fā)生變異，即表示染色體的編碼發(fā)生某些變化。一個群體的進(jìn)化需要染色體的多樣性，而變異對保持群體的多樣性具有一定的作用。

表1 生物進(jìn)化與遺傳算法之間的對應(yīng)關(guān)系

2 教學(xué)中遺傳算法的可視化設(shè)計

2.1 問題的提出

基于教學(xué)目的問題設(shè)計，既需要容易理解又需要有代表性，這樣才能有利于學(xué)生對遺傳算法思想的理解。本文提出了如何利用遺傳算法來求解8位二進(jìn)制數(shù)中的最大數(shù)，即任意給出10個在0-255之間的自然數(shù)，利用遺傳算法循環(huán)進(jìn)行選擇、交叉、變異運(yùn)算，求出最大的8位二進(jìn)制數(shù)（即十進(jìn)制的255），同時在這運(yùn)算的過程當(dāng)中，能夠動態(tài)的顯示出包括染色體基因，適應(yīng)值函數(shù)選擇過程和選擇結(jié)果、交叉過程、變異過程和相關(guān)結(jié)果。

2.2 問題編碼的設(shè)計

在設(shè)計遺傳算法時首先考慮的是編碼的設(shè)計問題，將問題的解以適合于遺傳算法求解的形式編碼；本文采用二進(jìn)制編碼，用二進(jìn)制值表示當(dāng)前的染色體的值，由于所求的目標(biāo)數(shù)用二進(jìn)制表示最大為八位，所以染色體的設(shè)計為8位染色體。

2.3 適應(yīng)函數(shù)的設(shè)計

直接選取問題的目標(biāo)函數(shù)作為適應(yīng)函數(shù)，在這里目標(biāo)函數(shù)為染色體與目標(biāo)最大數(shù)的差，差值越小（和目標(biāo)數(shù)越接近）適應(yīng)函數(shù)值越大，越容易被在繁殖中保存下來。

2.4 選擇操作設(shè)計（評估染色體設(shè)計）

依據(jù)適應(yīng)函數(shù)值的大小，選擇操作從規(guī)模為N的群體中隨機(jī)地選擇若干染色體構(gòu)成種群，種群的規(guī)模可以與原來的群體的規(guī)模一致，也可以不一致，為方便演示，本系統(tǒng)設(shè)計成二者的規(guī)模是一致的，即從10個原來的群體選擇10個構(gòu)成新的種群。從群體中選擇存活的染色體，這里采用“輪盤賭”的方法，方法簡述如下：

群體的規(guī)模為10，F(xiàn)(X)為染色體的二進(jìn)制轉(zhuǎn)化為十進(jìn)制的值，是其中第10個染色體的適應(yīng)值，則第i個染色體被選中的概率見公式1。

公式1 染色體的被選中概率計算公式

①R=random(0,1),s=0,i=0;

②如果s≥R,則轉(zhuǎn)④

⑤結(jié)束。

其中random(0,1)是一個產(chǎn)生在[0，1]之間均勻分布的隨機(jī)數(shù)的函數(shù)。這樣經(jīng)過10次“輪盤賭”之后，就得到了規(guī)模為10的新的種群。

2.5 交叉操作設(shè)計

雙親雙子法是遺傳算法交叉環(huán)節(jié)最常用的一種設(shè)計方法，就是當(dāng)參與交叉的兩個雙親染色體確定后，隨機(jī)產(chǎn)生一個交叉位，雙親染色體交換各自的交叉位之后的基因給對方，得到兩個子染色體。

本文設(shè)計的種群數(shù)目有10個，基因的位數(shù)8位，采用雙親雙子法交叉兩次，然后從中得出的4個染色體中，隨機(jī)的抽取2個做為下一代的新的種群。這樣的設(shè)計主要是防止染色體基因位的重復(fù)相同，使產(chǎn)生的新的染色體在基因位上進(jìn)可能少的重疊，有利于種群基因的多樣性，以便在多次交叉中尋找到目標(biāo)解。

2.6 變異操作設(shè)計

變異發(fā)生在某個染色體的某個基因上，它將可變性引入群體，增強(qiáng)了群體的多樣性，從而提供了從局部最優(yōu)中逃脫出來的一種手段。

本文問題的編碼形式采用的是二進(jìn)制數(shù)表示，所以隨機(jī)產(chǎn)生一個變異位后，被選中的基因由“0”變成“1”，或者由“1”變成“0”。在問題求解上，由于只有10個染色體，每個染色體位，所以為了更好的體現(xiàn)遺傳交叉得出最優(yōu)解的結(jié)果，應(yīng)盡量的減少變異的概率，所以設(shè)置變異的概率為1%，當(dāng)然也可以用戶自定義，以尋求相應(yīng)的速度找到目標(biāo)解。

2.7 遺傳算法的評價方法的設(shè)計

當(dāng)進(jìn)化代數(shù)趨向于無窮時，遺傳算法中找到最優(yōu)解的概率為1，但需要隨時了解算法的進(jìn)展情況，監(jiān)視算法的變化趨勢，本文使用所在的第n代中染色體的平均指標(biāo)函數(shù)的值（所有染色體轉(zhuǎn)化成十進(jìn)制的平均值）來刻畫算法的趨勢，并用隨代數(shù)變化的曲線圖表示出來。

2.8 遺傳算法的實現(xiàn)過程

圖1 求解遺傳算法流程圖

在確定了問題的編碼，適應(yīng)函數(shù)的設(shè)計以及選擇、交叉、變異的規(guī)則后，整個遺傳算也就確定了，具體的實現(xiàn)過程如下：

1）給定群體規(guī)模為10，交叉的概率為=100%（可用戶自定義）和變異概率為=1%（可用戶自定義），t=0；

2）隨機(jī)生成（用戶自定義）10個染色體作為初始群體；

4）如果算法滿足停止準(zhǔn)則，則轉(zhuǎn)⑽；

6）根據(jù)計算得到的概率值，從群體中隨機(jī)的選取10個染色體，得到新的種群；

9）用新群體替代舊群體，t=t+1;轉(zhuǎn)⑶；

10）進(jìn)化過程中適應(yīng)值最大的染色體，經(jīng)解碼后作為最優(yōu)解輸出；

根據(jù)遺傳算法的實現(xiàn)過程，得到相應(yīng)的流程圖如圖1所示。

2.9 遺傳算法的可視化設(shè)計

2.9.1 染色體設(shè)計界面

染色體用紅色表示“1”基因，用綠色表示“0”基因，即用八位的二進(jìn)制的“0”和“1”編碼來表示0-255之間的數(shù)。

2.9.2 染色體圖形設(shè)計方法

在五個面板中共保存了10個染色體的基因特征，每個染色體有8個基因，所以一個8個色塊表示染色體的八個基因。在畫圖方法上

用MFC在圖形控件上畫圖。同時在評估圖形左邊以十進(jìn)制的形式顯示當(dāng)代群體的染色體的值。

2.9.3 遺傳繁衍過程動畫顯示

運(yùn)用windows 時間消息響應(yīng)機(jī)制，在每個時間片中顯示算法關(guān)鍵節(jié)點(diǎn)的信息。如在選擇過程為10個時間片，分別選出10個新的種群；交叉過程為5個時間片，包括選中交叉的染色體，第一次交叉結(jié)果的染色體，第二次交叉結(jié)果的染色體，交叉結(jié)果選出新染色體，在交叉結(jié)果顯示新的染色體；變異過程為1個時間片，即更新變異結(jié)果。

2.9.4 遺傳算法性能曲線設(shè)計

在一個圖形控件中繪制坐標(biāo)，橫坐標(biāo)為遺傳代數(shù)，縱坐標(biāo)為當(dāng)代群體的染色體適應(yīng)函數(shù)的平均值；每代遺傳后求出當(dāng)代群體的染色體適應(yīng)函數(shù)的平均值，在畫圖上同時記錄相連兩代的平均值，在遺傳更新過程中連線表示遺傳過程中的群體的染色體適應(yīng)函數(shù)的平均值的變化，便形成了群體的染色體適應(yīng)函數(shù)的平均值的曲線。

產(chǎn)生隨機(jī)數(shù)時間種子的函數(shù)的設(shè)計

圖2 遺傳算法演示過程主界面

}采用此函數(shù)產(chǎn)生的隨機(jī)數(shù)時間種子是以納秒為單位的，極大程度上避免了產(chǎn)生重復(fù)的隨機(jī)數(shù)時間種子，是實驗設(shè)計的關(guān)鍵和重要技術(shù)。

2.9.5 主要界面內(nèi)容介紹

如圖2所示：

（1）左上角的染色體值顯示了當(dāng)代10個8位的染色體值，為了方便理解將二進(jìn)制轉(zhuǎn)化為十進(jìn)制表示，從中很容易看到每一代染色體不斷的靠近目標(biāo)解。

（2）右上角的評估染色體、選擇結(jié)果、交叉過程、交叉結(jié)果、變異結(jié)果等五個面板顯示了每一代染色體的演化過程，直至生成下一代染色體。

（3）左下角遺傳工程染色體平均性能圖譜表示的是運(yùn)算的代數(shù)與群體平均適應(yīng)值的正相關(guān)關(guān)系，即隨著運(yùn)算代數(shù)的增加，群體平均適應(yīng)值越來越接近目標(biāo)解。

（4）右下角顯示的是包括繁衍速度控制控件在內(nèi)的控件群，可以選擇開始演示算法、暫停算法、重新演示算法等操作。

3 遺傳算法可視化實驗主要測試情況

3.1 第一次測試

表2 第一次測試數(shù)據(jù)

圖3 遺傳算法第一次測試過程性能圖譜

表3 第二次測試數(shù)據(jù)

圖4 遺傳算法第二次測試過程性能圖譜

表2給出了隨機(jī)產(chǎn)生的10個染色體及計算結(jié)果。圖3為變異概率為1%遺傳過程性能圖譜，運(yùn)行了105代以后群體平均適應(yīng)值很接近目標(biāo)解，但由于陷入局部最優(yōu)，沒能找到最優(yōu)解。

3.2 第二次測試

表3給出了隨機(jī)產(chǎn)生的10個染色體及計算結(jié)果。圖4為變異概率為1%遺傳過程性能圖譜，運(yùn)行到第67代時候得到了目標(biāo)解。

3.3 第三次測試

表4 第三次測試數(shù)據(jù)

圖5 遺傳算法第三次測試過程性能圖譜

表4給出了隨機(jī)產(chǎn)生的10個染色體及計算結(jié)果。圖5所示位變異概率為10%的遺傳過程性能圖譜，運(yùn)行到第55代時候得到了目標(biāo)解。

3.4 實驗結(jié)果分析

以上三組群體的染色體都是隨機(jī)產(chǎn)生的，染色體適應(yīng)值平均分布在[0，255]之間的數(shù)，變異的概率分別為1%，1%，10%，可以看到染色體適應(yīng)函數(shù)的平均值的曲線為上升趨勢，第一組數(shù)據(jù)沒有得出目標(biāo)解；第二組數(shù)據(jù)得出目標(biāo)解，基于遺傳交叉的可能性比較大，染色體適應(yīng)函數(shù)的平均值的曲線上升的曲線也比較明顯；第三組數(shù)據(jù)變異的概率比較大（10%），得出結(jié)果基于變異的可能性比較大，但染色體適應(yīng)函數(shù)的平均值的曲線上升的曲線變化也比較大。

4 小結(jié)

該設(shè)計不但能夠動態(tài)演示遺傳算法的運(yùn)算過程，而且也展現(xiàn)了遺傳算法的不足，即在某些條件下，可能會陷入局部最優(yōu)。此外，通過不同的參數(shù)設(shè)置，比如調(diào)整變異概率，還可以對運(yùn)速性能進(jìn)行進(jìn)一步的分析。

從課堂教學(xué)效果來看，學(xué)生可以動態(tài)的觀察遺傳算法在運(yùn)算過程的選擇、交叉、變異等步驟，大大激發(fā)了學(xué)生的學(xué)習(xí)興趣，加深了對算法思想的認(rèn)識與理解，因此，遺傳算法在教學(xué)中的可視化設(shè)計是可行的。

[1] 馬永杰,云文霞.遺傳算法研究進(jìn)展[J]. 計算機(jī)應(yīng)用研究. 2012(04) .

[2] 李雅瓊.基于模糊控制的遺傳算法優(yōu)化研究[J]. 長沙大學(xué)學(xué)報. 2016(05).

[3] 王小平, 曹立明.遺傳算法的理論、應(yīng)用與軟件實現(xiàn)[M].西安:西安交通大學(xué)出版社, 2002: 28- 34.

Visualization design and implementation of the genetic algorithm forteaching demonstration

Wu Qingyang
(Guangdong Finance Institute，Guangdong,Guangzhou,510445)

Intelligence algorithms(evolution algorithms) like Genetic algorithm& neural network is a fast,high efficiency non exact algorithms.It is always the difficult&key point for the teaching demonstration as it breaks through the traditional thinking of the exact algorithm.This paper try to use genetic algorithm to solve maximum of 8 bit binary as example to present the computational procedure of genetic algorithm in a visualization way,get a deeper understanding of genetic algorithm thought & achieve the target of helping student understand the algorithm.

genetic algorithm;teaching;selection;crossover;mutation