遺傳算法在教學中的可視化設計與實現

吳清揚

（廣東省財政職業技術學校，廣東廣州，510445）

遺傳算法在教學中的可視化設計與實現

吳清揚

（廣東省財政職業技術學校，廣東廣州，510445）

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

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

0 引言

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

1 遺傳算法思想概要

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

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

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

表1 生物進化與遺傳算法之間的對應關系

2 教學中遺傳算法的可視化設計

2.1 問題的提出

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

2.2 問題編碼的設計

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

2.3 適應函數的設計

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

2.4 選擇操作設計（評估染色體設計）

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

群體的規模為10，F(X)為染色體的二進制轉化為十進制的值，是其中第10個染色體的適應值，則第i個染色體被選中的概率見公式1。

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

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

②如果s≥R,則轉④

⑤結束。

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

2.5 交叉操作設計

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

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

2.6 變異操作設計

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

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

2.7 遺傳算法的評價方法的設計

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

2.8 遺傳算法的實現過程

圖1 求解遺傳算法流程圖

在確定了問題的編碼，適應函數的設計以及選擇、交叉、變異的規則后，整個遺傳算也就確定了，具體的實現過程如下：

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

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

4）如果算法滿足停止準則，則轉⑽；

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

9）用新群體替代舊群體，t=t+1;轉⑶；

10）進化過程中適應值最大的染色體，經解碼后作為最優解輸出；

根據遺傳算法的實現過程，得到相應的流程圖如圖1所示。

2.9 遺傳算法的可視化設計

2.9.1 染色體設計界面

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

2.9.2 染色體圖形設計方法

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

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

2.9.3 遺傳繁衍過程動畫顯示

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

2.9.4 遺傳算法性能曲線設計

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

產生隨機數時間種子的函數的設計

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

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

2.9.5 主要界面內容介紹

如圖2所示：

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

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

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

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

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

3.1 第一次測試

表2 第一次測試數據

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

表3 第二次測試數據

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

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

3.2 第二次測試

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

3.3 第三次測試

表4 第三次測試數據

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

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

3.4 實驗結果分析

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

4 小結

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

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

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

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

[3] 王小平, 曹立明.遺傳算法的理論、應用與軟件實現[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