基于Excel的遺傳算法在大學(xué)生數(shù)學(xué)建模中的應(yīng)用

顏清，苗壯，徐調(diào)斌，蔣昌猛，賴鑫生

(上饒師范學(xué)院 數(shù)學(xué)與計(jì)算機(jī)科學(xué)學(xué)院，江西 上饒 334001)

遺傳算法在工程優(yōu)化和工業(yè)控制等領(lǐng)域得到廣泛應(yīng)用。吳立華等針對某機(jī)械的懸臂結(jié)構(gòu)采用遺傳算法進(jìn)行優(yōu)化設(shè)計(jì),有較快的收斂速度和很高的計(jì)算精度,建立了單目標(biāo)非線性優(yōu)化設(shè)計(jì)數(shù)學(xué)模型,為多目標(biāo)非線性結(jié)構(gòu)優(yōu)化設(shè)計(jì)提供了強(qiáng)有力的方法和工具[1]。李月引入免疫算法來改進(jìn)遺傳算法,在TSP應(yīng)用中解決種群迭代次數(shù)過多的復(fù)雜問題中,經(jīng)過疫苗檢驗(yàn)和退火選擇降低算法的退化概率,避免了種群的退化現(xiàn)象[2]。播種機(jī)的播種質(zhì)量、播種效率和能耗由于受播種地形和地域的影響不能發(fā)揮到最佳狀態(tài)，秦華等提出了一種基于BTO模式的多目標(biāo)速度控制遺傳算法優(yōu)化模型，確定了BTO模式下播種機(jī)性能優(yōu)化的初始參數(shù)，明顯的改善了播種機(jī)的播種質(zhì)量、播種效率和播種能耗，提高了播種機(jī)的作業(yè)性能[3]。針對基本遺傳算法存在收斂速度慢、早熟等不足,王雷等提出了一種改進(jìn)自適應(yīng)遺傳算法，根據(jù)進(jìn)化過程中個體適應(yīng)度值的大小自動調(diào)節(jié)交叉概率和變異概率,使算法能夠跳出局部最優(yōu)解,移動機(jī)器人路徑規(guī)劃的仿真實(shí)驗(yàn)表明，改進(jìn)的遺傳算法有效可行，明顯提高了機(jī)器人路徑規(guī)劃的質(zhì)量[4]。每年的大學(xué)生數(shù)學(xué)建模競賽中遺傳算法也用于解決數(shù)學(xué)建模中的優(yōu)化問題。劉兆仁等利用遺傳算法對公共自行車如何在各大中型城市高效調(diào)度建立了VRP模型,采用標(biāo)準(zhǔn)算例針對算法進(jìn)行檢驗(yàn),結(jié)果表明遺傳算法能夠有效求解自行車的調(diào)度模型[5]。根據(jù)“立竿見影”和竿影日照圖的原理，于鵬等提出了一種太陽影子定位方法。他們首先結(jié)合太陽高度角、太陽赤緯角，以理論影長和實(shí)際影長的相關(guān)系數(shù)最大和其誤差平方和最小為目標(biāo)函數(shù)建立了求太陽影子定位的多目標(biāo)優(yōu)化模型，采用遺傳算法進(jìn)行求解，求解結(jié)果無論在精度還是在收斂速度上都優(yōu)于傳統(tǒng)的枚舉算法[6]。在每年一屆的大學(xué)生數(shù)學(xué)建模教學(xué)及指導(dǎo)中，如何讓大學(xué)生在一段較短時間內(nèi)較快地掌握遺傳算法是一較為棘手的問題。筆者將遺傳算法嵌入在Excel中，利用Excel表格功能、函數(shù)功能及VBA混合編程對遺傳算法的優(yōu)化過程進(jìn)行仿真，模擬遺傳算法的選擇、交叉和變異三個基本操作，充分展現(xiàn)了遺傳算法解決大學(xué)生數(shù)學(xué)建模中優(yōu)化命題的魅力，獲得了較為滿意的應(yīng)用效果，解決了大學(xué)生數(shù)學(xué)建模中的優(yōu)化問題。

1 遺傳算法的VBA優(yōu)化仿真概述

遺傳算法即模擬自然界生物群體一代一代的繁衍進(jìn)化，通過迭代操作，產(chǎn)生新一代較優(yōu)的個體作為問題的解，如同生物群體一代一代不斷繁衍、進(jìn)化，最后收斂到最適合生存環(huán)境的一代生物個體，即為問題的最優(yōu)解。問題解的優(yōu)劣通常用適宜度表達(dá)，適宜度即表示為生物群體不斷繁衍中個體對生存環(huán)境適宜性的強(qiáng)弱程度，適宜度大的個體被選擇為繁衍下一代父代的概率就大，其染色體就會在一個甚至多個下一代的基因中出現(xiàn)，這種有選擇性的將最優(yōu)染色體進(jìn)入下一代的繁衍行為，表現(xiàn)出達(dá)爾文物擇競天、適者生存、優(yōu)勝劣汰的自然界生存法則，這種最優(yōu)選擇策略在遺傳算法中起到?jīng)Q定性作用。

所謂的遺傳算法VBA優(yōu)化仿真，即在Excel表格中用一組單元格中的{0，1}二進(jìn)制串表示遺傳算法中的一個“染色體”個體，再由Excel表格功能自動仿真計(jì)算“染色體”個體的環(huán)境“適宜度”，由此再通過競爭在表格中產(chǎn)生更適應(yīng)環(huán)境的新一代仿真“染色體”個體群，一個新一代“染色體”個體即為問題的一個可行解。通過Excel表格功能與VBA混合編程，在Excel表格中生動地模擬出“染色體”的競爭過程：“染色體”個體基因如何被選擇、復(fù)制進(jìn)入下一代，如何通過交叉、變異過程產(chǎn)生更適應(yīng)環(huán)境的新一代“染色體”個體群等，如此通過一代一代進(jìn)化，最終收斂到最適應(yīng)環(huán)境的最新一代的“染色體”個體群，從而獲得問題的最優(yōu)解等過程。

2 算法過程仿真

以下通過函數(shù)f(x)=11sin(6x)+7cos(5x)為例，在數(shù)據(jù)處理的常用軟件Excel中，通過Excel的表格功能、函數(shù)功能及與自帶的VBA混合編程，即利用Excel遺傳算法求函數(shù)在x∈[0,2π]區(qū)間中最大值，闡述Excel遺傳算法的優(yōu)化仿真過程。

2.1 Excel遺傳算法VBA優(yōu)化仿真過程

2.1.1 遺傳算法的初始群體

求解的精度決定“染色體”個體的{0，1}二進(jìn)制串長度。設(shè)定求解精度x為四位小數(shù)，須將0到2π區(qū)間分為6.283 2×104等分，編碼的二進(jìn)制串至少需要16位，即32 768=215<6.283 2×104<216=65 536，即Excel遺傳算法通過16個連續(xù)單元格中的“0”或“1”的二進(jìn)制串作為“染色體”個體的遺傳編碼。20個“染色體”的群即由20行、每行16個“0”或“1”的連續(xù)單元格即可表示。利用Excel的自動計(jì)算功能，在“染色體”個體的{0，1}二進(jìn)制串之后的單元格，可以分別對“染色體”個體的“十進(jìn)制值”“實(shí)際x值”“函數(shù)f(x)值”進(jìn)行仿真計(jì)算[7]。

2.1.2 初始群體適宜值的計(jì)算與遺傳選擇

由于f(x)在x∈[0,2π]區(qū)間上有正有負(fù)，以20個“染色體”群中最大的正數(shù)與最小的負(fù)數(shù)之間的區(qū)間為1，“染色體”群中最大的正數(shù)其“區(qū)間值”為1，最小的負(fù)數(shù)其“區(qū)間值”為0。根據(jù)適者生存的生物遺傳法則，以函數(shù)值f(x)的“區(qū)間值”作為適宜值，將“染色體”群中“染色體”個體的“區(qū)間值”累加，個體的“區(qū)間值”占“區(qū)間值”總和的百分比值就是“染色體”遺傳進(jìn)入下一代的概率。根據(jù)個體的“區(qū)間值”的百分比值設(shè)計(jì)成輪盤賭(圖1)，每個個體的這個百分比值即為“輪盤比例”，在輪盤賭上根據(jù)“染色體”順序劃定確定的區(qū)域，適宜值高的“染色體”個體在輪盤賭上占有的區(qū)域就大，被選擇的機(jī)會就高，充分體現(xiàn)了適者生存的生物遺傳法則。

圖1即為初始群的Excel遺傳算法仿真計(jì)算表。圖中輪盤賭的仿真數(shù)值區(qū)域在0-1之間，刻度值與時鐘的0點(diǎn)至12點(diǎn)分度對應(yīng)，通過隨機(jī)函數(shù)每次選擇一個0-1之間的隨機(jī)數(shù)，確定選擇輪盤賭對應(yīng)區(qū)間的“染色體”，可以看出適宜度高的“染色體”由于其“輪盤比例”大而被多次選擇，一些適宜值低的“染色體”在輪盤賭中對應(yīng)區(qū)間小而難以選擇而被淘汰。適宜度最低的11號“染色體”的“輪盤比例”值為0，直接淘汰。圖1所示，由于函數(shù)f(x)的值為“適宜值”，16號“染色體”的“適宜度”最大，“輪盤比例”達(dá)9.63%，選擇次數(shù)也最多，20次的選擇中，被選擇了3次，即16號“染色體”的基因復(fù)制了3次進(jìn)入下一代“染色體”中，占比達(dá)15%；17號“染色體”的“適宜度”較大，僅次于16號“染色體”，“輪盤比例”為9.27%，也被選擇了3次。第1、3、4、5、7、9、11、18、20號“染色體”，平均“適宜度”占比小于2.61%，20次的選擇中，選擇次數(shù)均為零。注意到，圖1中最后兩列的“選擇值”數(shù)據(jù)列僅對應(yīng)于前列的選擇序號n列，其它各列對應(yīng)行數(shù)據(jù)為各“染色體”個體對應(yīng)數(shù)據(jù)。

圖1 遺傳算法的選擇與輪盤賭

圖2 遺傳算法的復(fù)制與仿真計(jì)算

2.2 遺傳算法VBA優(yōu)化仿真混合編程

2.2.1 選擇、復(fù)制確定下一代“染色體”基因

圖1、圖2是依次執(zhí)行“初始群”“選擇”和“復(fù)制”三按鈕中的VBA代碼的仿真計(jì)算結(jié)果。經(jīng)輪盤賭選擇后，通過Excel混合編程進(jìn)行復(fù)制。遺傳復(fù)制遵循“優(yōu)勝劣汰”的自然遺傳法則，可以看出,許多“染色體”在遺傳復(fù)制時未被選擇，淘汰率達(dá)45%。圖1與圖2的仿真計(jì)算顯示，個體的“適宜值”大入選概率就大，“適宜值”小的如第3、5、7、9、11、18號“染色體”，“適宜值”占比小于1.35%均被淘汰。如下為VBA混合編程完成復(fù)制操作的程序代碼。

L=0'將選擇的“染色體”{0，1}二進(jìn)制串由“Excel遺傳算法”表復(fù)制到“Excel遺傳算法1”表

For i=1 To 20

m=Sheets(“Excel遺傳算法”).Cells(i + 1, 60)

If m=0 Then GoTo 10

For n=1 To m

For j=1 To 16

Sheets(“Excel遺傳算法1”).Cells(L + 2, j + 1) = Sheets(“Excel遺傳算法”).Cells(i+1, j+1)

Next j

L=L+1

Next n

10 Next i

被選擇的“染色體”由“Excel遺傳算法1”表轉(zhuǎn)移回“Excel遺傳算法”表后完成選擇、復(fù)制

For i=1 To 20

For j=1 To 16

Sheets(“Excel遺傳算法”).Cells(i+1, j+1)=Sheets(“Excel遺傳算法1”).Cells(i+1, j+1)

Next j

Next i

從VBA程序代碼中看出，輪盤賭選擇確定了新一代“染色體”的基因，根據(jù)“初始染色體群”表(圖1)中的BH列列出對應(yīng)序號的仿真“染色體”個體的選擇次數(shù)進(jìn)行復(fù)制，得到第二代“染色體”群的基因(圖2)，其平均“適宜值”比“初始染色體群”要高出許多，整個算法的選擇、復(fù)制仿真過程躍然紙上。

2.2.2 交叉、變異產(chǎn)生新一代“染色體”個體

圖3為第七代“染色體”群經(jīng)選擇、復(fù)制后的仿真圖，圖4為經(jīng)配對完成交叉操作后的“染色體”群的仿真圖。對照圖3圖4可以看出，交叉配對產(chǎn)生了更為優(yōu)秀的個體，交叉配對前“染色體”個體“適宜值”最高為17.582 882，交叉配對后“染色體”個體“適宜值”最高為17.595 591，未選取交叉配對的3對即1、11，7、17，8、18等三對個體經(jīng)變異后競爭進(jìn)入下一代“染色體”群。更為可喜的是交叉配對前最優(yōu)秀的五個“染色體”個體，其中4個“染色體”經(jīng)交叉操作“適宜值”得到進(jìn)一步提高，未變的一個“染色體”原因是未交叉直接進(jìn)入，由此可見，交叉配對產(chǎn)生的新個體使優(yōu)秀“染色體”進(jìn)一步優(yōu)化。

圖3 新一代個體的選擇與復(fù)制

圖4 交叉、變異產(chǎn)生新一代個體仿真圖

變異概率確定為0.01，即100個長度的{0，1}二進(jìn)制串中，隨機(jī)抽取一個進(jìn)行變異，群體的{0，1}二進(jìn)制串累計(jì)為320位，共有3.2個二進(jìn)制位變異，即3個或4個二進(jìn)制位變異。變異是一個較小的擾動，只對“染色體”群帶來較小的改變。

歷經(jīng)選擇、交叉、變異等三個算子作用后，下一代仿真“染色體”群宣告誕生。結(jié)合表格計(jì)算功能的VBA混合編程可以形象地讓學(xué)生了解遺傳算法的基本思想。

2.3 遺傳算法VBA優(yōu)化仿真的終止條件

遺傳算法的終止條件通常設(shè)為兩類：(1)最大遺傳代數(shù)的設(shè)定；(2)種群中基因多樣性測度。兩個終止條件通常會結(jié)合起來運(yùn)用，若將最大遺傳代數(shù)的設(shè)定為100代，在不到100代時，計(jì)算種群中基因多樣性測度，若所有基因位相似程度急驟上升，此時收斂于概率為1的優(yōu)良個體，遺傳算法即可終止。

3 遺傳算法VBA優(yōu)化仿真的應(yīng)用

3.1 遺傳算法VBA優(yōu)化仿真輔助數(shù)學(xué)建模教學(xué)

大學(xué)生數(shù)學(xué)建模與優(yōu)化問題聯(lián)系非常密切，遺傳算法解決大學(xué)生數(shù)學(xué)建模優(yōu)化問題是較重要途徑。大學(xué)生學(xué)習(xí)遺傳算法VBA優(yōu)化仿真，很容易掌握遺傳算法的基本思想，熟悉選擇、交叉、變異等基本算子的作用，在輔助大學(xué)生數(shù)學(xué)建模及相關(guān)教學(xué)中得到應(yīng)用。

3.1.1 算法過程的仿真及其可視化

在遺傳算法VBA優(yōu)化仿真過程中，以Excel表格數(shù)據(jù)及圖形的形式揭示“染色體”在遺傳過程中的演變規(guī)律，利用Excel混合編程完成遺傳算法基本算子的操作，實(shí)現(xiàn)遺傳算法演化過程的可視化。

3.1.2 “染色體”個體的仿真

在Excel表格中，利用一組16個連續(xù)單元格表示的{0，1}二進(jìn)制串，作為仿真“染色體”個體的遺傳算法編碼。如{0，1}二進(jìn)制串“1001000101011001”，十進(jìn)制數(shù)為37 209，若用以表示x為0至6.283 2中的數(shù)，即x=0+37 209×6.283 2/(216-1)=3.567 4，f(x)的絕對值為9.798 081 7，都可以通過Excel表格直接計(jì)算得到這些結(jié)果，使算法過程直覺化、可視化，“染色體”個體仿真加深了大學(xué)生算法學(xué)習(xí)的感性認(rèn)識。

3.1.3 選擇算子中輪盤賭的仿真

根據(jù)各“染色體”適宜值設(shè)計(jì)輪盤賭，配上插圖就很直觀。圖1中看出整個輪盤賭的數(shù)值區(qū)域在0-1之間，通過隨機(jī)函數(shù)每次選擇一個0-1之間的隨機(jī)數(shù)，就可以確定每次是哪個“染色體”被選擇，也可以看出適宜值高的“染色體”往往被多次選擇并遺傳至下一代，有些適宜值低的“染色體”很難被選擇而淘汰。

3.1.4 交叉操作的可視化

選擇操作只是完成了產(chǎn)生新一代“染色體”群的第一步，接著就是交叉、變異操作。大學(xué)生可以直接從仿真表格中(圖1)看出，前面最優(yōu)秀的5個“染色體”個體，其中4個“染色體”經(jīng)交叉“適宜值”得到進(jìn)一步提高。大學(xué)生通過對照交叉前后的“染色體”，變化一目了然。由于交叉概率選擇0.7，即只有70%的“染色體”進(jìn)行交叉配對，20個“染色體”個體中有14個“染色體”個體要進(jìn)行交叉配對，最優(yōu)秀的5個“染色體”個體有一個“染色體”未交叉配對直接進(jìn)入新一代“染色體”群。由此可見，交叉配對產(chǎn)生的新個體使優(yōu)秀“染色體”進(jìn)一步得到優(yōu)化。圖5、圖6是1至60代中“染色體”群中最優(yōu)“染色體”與“染色體”平均適宜度的仿真計(jì)算結(jié)果，60代時，最優(yōu)解為17.833 39，與答案17.833 99相差極小。

圖5 1至60代中的最優(yōu)“染色體” 圖6 1至60代“染色體”平均適宜度

3.1.5 變異操作方法的多樣性

變異操作是一個較小的擾動，對“染色體”群帶來較小的改變。通過變異操作，打開了新的搜索空間，容易找出“染色體”個體{0，1}二進(jìn)制串中已經(jīng)變化的幾個位置。歷經(jīng)選擇、交叉、變異等三個算子作用后，下一代“染色體”群宣告誕生，很明顯，大學(xué)生對這一過程心領(lǐng)神會，遺傳算法的VBA優(yōu)化仿真在課堂上以過程仿真的形式講授提升了教學(xué)效果。

3.2 遺傳算法VBA優(yōu)化仿真與數(shù)學(xué)建模

課堂上遺傳算法的VBA優(yōu)化仿真形象、生動，學(xué)生容易理解，但要掌握遺傳算法的VBA優(yōu)化仿真在大學(xué)生數(shù)學(xué)建模中解決優(yōu)化命題還需要學(xué)生實(shí)踐操作，最為實(shí)用例子是選擇以往大學(xué)生數(shù)學(xué)建模中的優(yōu)化選題。

3.2.1 應(yīng)用于適應(yīng)度的變化

對于函數(shù)f(x)= 11sin(6x)+ 7cos(5x)，可以在x∈[0,2π]區(qū)間上對函數(shù)求最大值，也可以對函數(shù)求最小值，這就只要在適應(yīng)度列中作適當(dāng)改變就行。如求最小值，即在適應(yīng)度列的每行加負(fù)號即可。若函數(shù)f(x)改變了，且變量只有一個，也只要改變“適應(yīng)度”列(對應(yīng)“輪盤比例”列)的各行。

3.2.2 應(yīng)用于求解精度與變量個數(shù)的變化

遺傳算法的VBA優(yōu)化仿真程序在“染色體”個體與“染色體”群所對應(yīng)的列(圖1)中預(yù)留了32列。如要改變求解精度，可以對“染色體”個體與“染色體”群所對應(yīng)的列進(jìn)行增減。f(x) 函數(shù)關(guān)系改變，“染色體”個體與“染色體”群所對應(yīng)的列有48列，適應(yīng)有3個以內(nèi)變量且求解精度為10-4的f(x)函數(shù)。

3.2.3 應(yīng)用時克服輪盤賭的缺點(diǎn)

輪盤賭還與“賭”字有關(guān)，如圖1中所示，1、4、20號個體的“適宜度”達(dá)到5.00%以上未被選擇，而“適宜度”占比僅4.19%的15號個體被選擇2次，這也是它的缺點(diǎn)所在。因此，為避免最優(yōu)基因的流失，通常加入最優(yōu)基因保留技術(shù)。

3.2.4 避免早熟與局部尋優(yōu)問題的思考

遺傳算法VBA優(yōu)化仿真也可一代一代操作，也可連續(xù)操作直接得到結(jié)果。輔助教學(xué)時，往往采用一代一代操作，學(xué)生能清楚地了解算法的過程細(xì)節(jié)。初始群局限了最優(yōu)解的搜索空間[8]，一代一代操作容易發(fā)現(xiàn)遺傳算法的早熟與陷入局部尋優(yōu)等問題，通過對操作的調(diào)整，如選擇較好的初始群就可避免早熟與局部尋優(yōu)。變異操作確保了新一代基因的多樣性，打開了新的搜索空間，可以看出擴(kuò)大搜索空間影響收斂速度，故變異概率常取1%或以下。

4 結(jié)束語

在Excel表格中形象地完成遺傳算法的選擇、交叉、變異的過程仿真，將Excel表格自動計(jì)算功能與VBA編程相結(jié)合，算法過程形象地呈現(xiàn)在學(xué)生面前。在Excel表格中操作遺傳算法，Excel算法過程的可視化與實(shí)時動態(tài)仿真效果，使大學(xué)生對算法的原理、過程、算子、適宜度等基本要點(diǎn)了解得非常透徹，使大學(xué)生在數(shù)學(xué)建模中應(yīng)用遺傳算法的VBA優(yōu)化仿真得心應(yīng)手，揮灑自如，為遺傳算法在運(yùn)用時進(jìn)行適當(dāng)改進(jìn)打開了思路[9]，為解決數(shù)學(xué)建模中優(yōu)化命題提供了嶄新的解決方案。