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

吳清揚

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

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

吳清揚

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

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

遺傳算法教學選擇操作交叉操作變異操作

0 引言

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

1 遺傳算法思想概要

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

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

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

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

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

2.1 問題的提出

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

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

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

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

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

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

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

群體的規(guī)模為10，F(xiàn)(X)為染色體的二進制轉(zhuǎ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]之間均勻分布的隨機數(shù)的函數(shù)。這樣經(jīng)過10次“輪盤賭”之后，就得到了規(guī)模為10的新的種群。

2.5 交叉操作設(shè)計

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

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

2.6 變異操作設(shè)計

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

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

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

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

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

圖1 求解遺傳算法流程圖

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

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

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

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

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

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

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

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

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

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

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

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

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

用MFC在圖形控件上畫圖。同時在評估圖形左邊以十進制的形式顯示當代群體的染色體的值。

2.9.3 遺傳繁衍過程動畫顯示

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

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

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

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

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

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

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

如圖2所示：

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

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

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

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

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

3.1 第一次測試

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

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

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

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

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

3.2 第二次測試

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

3.3 第三次測試

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

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

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

3.4 實驗結(jié)果分析

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

4 小結(jié)

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

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

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

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

[3] 王小平, 曹立明.遺傳算法的理論、應(yīng)用與軟件實現(xiàn)[M].西安:西安交通大學出版社, 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