鄭波盡　代航

摘 要：演化計(jì)算是人工智能中一個(gè)重要的分支，目前的本科教學(xué)實(shí)踐對(duì)演化算法的講授多從標(biāo)準(zhǔn)遺傳算法出發(fā)，學(xué)生普遍反映算法復(fù)雜、難懂。文章提出“第一性原理”教學(xué)方法，將演化算法歸結(jié)到最簡(jiǎn)單的狀態(tài)，再逐步推廣，最后總結(jié)提高到理論層次；以中南民族大學(xué)計(jì)算機(jī)科學(xué)學(xué)院軟件與理論教研室在演化算法的本科教學(xué)中的做法為例展示“第一性原理”教學(xué)方法，說(shuō)明該教學(xué)方法的效果。

關(guān)鍵詞：演化算法；遺傳算法；簡(jiǎn)化；優(yōu)化問(wèn)題

0 引 言

很多高校的計(jì)算機(jī)科學(xué)與技術(shù)專業(yè)、信息技術(shù)專業(yè)以及相關(guān)的本科專業(yè)都開設(shè)了人工智能的課程。AlphaGO以4：1大勝世界超一流圍棋高手李世石、AlphaGO的高級(jí)版本Master在圍棋網(wǎng)上以60：0擊敗中日韓三國(guó)頂尖高手、AlphaGO以3：0大勝當(dāng)前圍棋等級(jí)分第一人柯潔九段等事件使得人工智能[1-2]學(xué)科得到了公眾的廣泛關(guān)注。這些轟動(dòng)一時(shí)的事件也表明，人工智能正以超乎想象的速度進(jìn)入到公眾的話語(yǔ)體系中。演化計(jì)算作為人工智能的重要分支也必然會(huì)受益于公眾的支持和期許，如會(huì)有更多的學(xué)生開始學(xué)習(xí)演化算法等。

1 演化算法教學(xué)困境

目前，對(duì)于演化算法的本科教學(xué)，國(guó)內(nèi)高校普遍以John Holland提出的標(biāo)準(zhǔn)遺傳算法[3-4]作為基準(zhǔn)來(lái)開展教學(xué)。標(biāo)準(zhǔn)遺傳算法用C語(yǔ)言來(lái)寫的話，大約需要200多行代碼，這就導(dǎo)致了一個(gè)困境：如果著重于介紹標(biāo)準(zhǔn)遺傳算法的理論知識(shí)，學(xué)生難以將算法融會(huì)貫通應(yīng)用于實(shí)踐環(huán)節(jié)，體現(xiàn)在不能寫出代碼；如果強(qiáng)調(diào)實(shí)踐環(huán)節(jié)，代碼實(shí)在冗長(zhǎng)，學(xué)生普遍反映理解起來(lái)有困難。

2 “第一性原理”教學(xué)方法

演化算法的教學(xué)通常是從標(biāo)準(zhǔn)遺傳算法開始講解，該算法的復(fù)雜和難以理解使得“第一性原理”教學(xué)方法的引入成為必然。

2.1 概 述

“第一性原理”原本是物理學(xué)的概念，經(jīng)過(guò)Elon Musk的大力宣傳，被廣泛應(yīng)用于各行各業(yè)。本質(zhì)上，“第一性原理”是基于因果關(guān)系的思維方式，即首先發(fā)現(xiàn)一件事情最核心的原因，然后基于此原因一步步往外推理出想要的結(jié)果。將“第一性原理”教學(xué)方法應(yīng)用到演化算法的教學(xué)中的基本思路是：將演化算法約簡(jiǎn)到最簡(jiǎn)單的形式，在最簡(jiǎn)單的形式下教學(xué)，然后推廣到更復(fù)雜的情形。方法應(yīng)用的主要步驟是：將演化算法大幅度化簡(jiǎn)到10多行代碼的程度，從實(shí)踐環(huán)節(jié)出發(fā)來(lái)講授；再將示例算法一般化，舉一反三，把理論和實(shí)踐聯(lián)系起來(lái)，達(dá)到強(qiáng)調(diào)理論教學(xué)的目的。這種方法既有案例，又有理論，有利于本科學(xué)生加深對(duì)于演化算法機(jī)制的理解，寫出處理各種優(yōu)化問(wèn)題的演化算法。

2.2 具體步驟

“第一性原理”教學(xué)方法可以分4步進(jìn)行。第1步是約簡(jiǎn)，即將演化算法進(jìn)行簡(jiǎn)化，一直簡(jiǎn)化到一目了然的程度，簡(jiǎn)化后的演化算法被稱為最簡(jiǎn)單演化算法（the simplest evolutionary algorithm）。第2步是展現(xiàn)，即展現(xiàn)簡(jiǎn)化后的演化算法（最簡(jiǎn)單演化算法）的機(jī)理和實(shí)驗(yàn)效果，通過(guò)多個(gè)案例來(lái)加深學(xué)員的理解。第3步是推廣，即從簡(jiǎn)到繁、舉一反三，根據(jù)實(shí)驗(yàn)效果和問(wèn)題特性，對(duì)最簡(jiǎn)單演化算法進(jìn)行改進(jìn)。第4步是提高，即萬(wàn)法歸宗，將感性認(rèn)識(shí)和實(shí)踐經(jīng)驗(yàn)上升到理論層次，在以前的教學(xué)基礎(chǔ)上，總結(jié)歸納出演化算法相關(guān)理論。

2.3 與通常教學(xué)法的比較

通常的演化算法教學(xué)是從標(biāo)準(zhǔn)演化算法開始，按算法原理、思想和算法的流程依次講授；再進(jìn)一步介紹選擇算子（如輪盤賭算子、競(jìng)標(biāo)賽選擇算子等）、交叉算子、變異算子、終止條件等；最后，介紹算法在處理各種優(yōu)化問(wèn)題時(shí)的弱點(diǎn)以及對(duì)算法所做的各種改進(jìn)。實(shí)踐教學(xué)方面，則讓學(xué)生參考標(biāo)準(zhǔn)遺傳算法，針對(duì)各種優(yōu)化問(wèn)題對(duì)算法進(jìn)行修改，仿真運(yùn)行得到結(jié)果，最后對(duì)結(jié)果進(jìn)行統(tǒng)計(jì)分析。

“第一性原理”教學(xué)法有所不同，以正弦和余弦函數(shù)構(gòu)造出來(lái)的優(yōu)化函數(shù)：maxf（x）=5sin（9x）+7cos（4x），x∈[0，7]為例，闡釋第一性原理教學(xué)法的具體做法。①將演化算法寫成最簡(jiǎn)單的形式使學(xué)生容易理解算法的每一句話，最簡(jiǎn)單的演化算法是一個(gè)具體的案例，學(xué)生更容易脫離抽象的算法理論細(xì)節(jié)；②用最簡(jiǎn)單的演化算法來(lái)求解具體的優(yōu)化問(wèn)題；③繼續(xù)第一性原理教學(xué)法的第②步，對(duì)于每個(gè)優(yōu)化問(wèn)題，給出其地形圖，并仿真執(zhí)行最簡(jiǎn)單演化算法，讓學(xué)生看到每一個(gè)世代、種群在地形圖上所處的點(diǎn)，從而直觀地感受到種群在地形圖上一步一步挪動(dòng)的情景，從而理解演化算法群體爬山的機(jī)制；④切換到第③步，講授和演示最簡(jiǎn)單演化算法的早熟問(wèn)題，從而引入算法的改進(jìn)，可以使用各種變異算子；⑤繼續(xù)第③步，即進(jìn)一步講授選擇算子和交叉算子的改進(jìn)，從而可以過(guò)渡到講授標(biāo)準(zhǔn)遺傳算法的框架上；⑥進(jìn)入第④步，在學(xué)生已經(jīng)得到了大量直觀經(jīng)驗(yàn)的基礎(chǔ)上，講授演化算法的理論。

2.4 精簡(jiǎn)后的算法形式

在“第一性原理”教學(xué)方法中，最重要的步驟是將演化算法寫成最簡(jiǎn)單的形式。完整的精簡(jiǎn)后的算法以C語(yǔ)言的形式給出如下。

#include

#include

#include

#define POPSIZE 100

#define MAXGENS 2000

double f（double x） {

return 5*sin（9*x） + 7*cos（4 * x）；

}

double pop[POPSIZE]；

void initPop（） {

for （int i = 0； i

pop[i] = （double）（rand（） % 7）；

}

void main（） {

srand（（unsigned int）time（0））；

initPop（）；

for （int k = 0； k

for （int i = 0； i

double x = pop[i]+ （double） rand（） /RAND_MAX*（pop[i]-pop[（i+1）%POPSIZE]）；

if （f（x）> f（pop[i]）） pop[i] = x；

}

}

主函數(shù)的第1行代碼是常見的初始化隨機(jī)數(shù)種子函數(shù)。利用當(dāng)前的時(shí)間作為隨機(jī)數(shù)種子，使得每次產(chǎn)生出來(lái)的隨機(jī)數(shù)都不相同。主函數(shù)的第2行代碼是初始化種群，即讓種群里的每個(gè)個(gè)體都有一個(gè)可行解。主函數(shù)的第3行代碼是計(jì)算演化算法迭代的次數(shù)，即種群演化的世代數(shù)。主函數(shù)的第4行和第5行完成雙親個(gè)體的選擇以及雜交操作，在雙親個(gè)體的選擇上，本算法以個(gè)體的存儲(chǔ)位置作為選擇的標(biāo)準(zhǔn)，即輪流選擇個(gè)體作為第1個(gè)雙親個(gè)體，然后，選擇第1個(gè)雙親個(gè)體的右鄰居（在數(shù)組中的下1個(gè)個(gè)體）作為第2個(gè)雙親個(gè)體，當(dāng)數(shù)組越界時(shí)，通過(guò)模運(yùn)算將個(gè)體重定位到數(shù)組的開始位置。也就是說(shuō)，種群實(shí)際上是構(gòu)成了1個(gè)環(huán)結(jié)構(gòu)。在完成了雙親個(gè)體的選擇后，算法在第5行執(zhí)行了雜交操作。在實(shí)數(shù)編碼的演化算法中，仿射雜交算子是1個(gè)常用的算子。該算子實(shí)際上是在兩點(diǎn)連成的直線線段上，隨機(jī)地選取1個(gè)點(diǎn)。這里實(shí)現(xiàn)的正是標(biāo)準(zhǔn)的仿射雜交算子，只不過(guò)在寫法上和常用的對(duì)稱寫法不太一樣，兩種寫法在數(shù)學(xué)上是一模一樣的。主函數(shù)的第6行完成的是精英策略，即對(duì)于當(dāng)前所獲得的最優(yōu)個(gè)體，需要將其保存下來(lái)。在本算法示例中，精英策略的實(shí)現(xiàn)和雙親個(gè)體的更新合并在一起，算法又得到了化簡(jiǎn)。

從上面給出的算法C語(yǔ)言代碼來(lái)看，主函數(shù)只有7行代碼，但已經(jīng)包含了演化算法的精髓。即使將初始化種群函數(shù)initPop（）里面的代碼加進(jìn)來(lái)，也不過(guò)8行代碼。對(duì)于學(xué)生們來(lái)說(shuō)，只需要理解主函數(shù)的7～8行代碼，就可以理解演化算法，有效降低了學(xué)生對(duì)于演化算法的理解難度。

2.5 程序運(yùn)行效果

在具體的教學(xué)實(shí)踐中，用MATLAB重寫上述算法，在算法中，加入繪圖代碼。在代碼中，加入fplot（'5*sin（9*x）+7*cos（4*x）'，[0 7]）這行代碼，以繪制函數(shù)的地形圖。然后，每隔幾個(gè)世代就繪制每一個(gè)個(gè)體在地形圖中的位置。學(xué)生能夠看到種群向山峰攀爬的過(guò)程，能夠直觀地理解演化算法具有“群體爬上”的機(jī)制。如圖1（x軸是自變量的取值，y軸是函數(shù)值，藍(lán)色的線是函數(shù)的地形圖，紅點(diǎn)是每個(gè)個(gè)體）是最簡(jiǎn)單演化算法在第20世代時(shí)的運(yùn)行結(jié)果圖。

3 “第一性原理”教學(xué)效果

“第一性原理”教學(xué)方法的應(yīng)用明顯改善了演化算法理論理解困難、演化算法實(shí)踐困難等問(wèn)題。總結(jié)下來(lái)，在采用新方法以后，學(xué)生得到了較大的提高，表現(xiàn)在以下3個(gè)方面。

1）理解了群體爬山的機(jī)制。

繪圖代碼在電腦中的展現(xiàn)能夠動(dòng)態(tài)地展示不同世代各個(gè)個(gè)體的移動(dòng)位置，直觀展現(xiàn)演化算法在每個(gè)世代的效果，具體可感的圖形有利于學(xué)生理解群體爬山機(jī)制。

2）大部分學(xué)生能編寫演化優(yōu)化程序。

新教學(xué)方法的應(yīng)用促進(jìn)了學(xué)生在實(shí)踐環(huán)節(jié)的進(jìn)步。通過(guò)新方法的實(shí)施，學(xué)生基本上能在電腦上完整地完成程序編寫，即使在卷面默寫的情況下，85%左右的學(xué)生也都能夠完成程序的編寫。

3）改變了對(duì)演化算法的畏難情緒。

演化算法的約簡(jiǎn)降低了該算法理解與應(yīng)用的難度，有效地降低了學(xué)生學(xué)習(xí)該算法的畏難情緒，由“困難”到“簡(jiǎn)單”的想法有利于學(xué)生建立強(qiáng)大的自信心。

4 總 結(jié)

演化算法是人工智能領(lǐng)域一個(gè)重要的部分，通過(guò)將演化算法大幅簡(jiǎn)化到只有十幾行代碼的程度的方式，學(xué)生能夠輕易地理解算法中每一行代碼的意思和作用，提高演化算法的教學(xué)效果?！暗谝恍栽怼苯虒W(xué)方法在演化算法教學(xué)中的應(yīng)用還需要在實(shí)踐中不斷完善，以期更好地為教學(xué)服務(wù)。

參考文獻(xiàn)：

[1] 鐘義信. 高等人工智能：人工智能理論的新階段[J]. 計(jì)算機(jī)教育， 2012（18）：6-11.

[2] 謝榕， 李霞. 人工智能課程教學(xué)案例庫(kù)建設(shè)及案例教學(xué)實(shí)踐[J]. 計(jì)算機(jī)教育， 2014（19）： 92-97.

[3] Holland J. Adaptation in Natural and Artificial Systems[M]. Commonwealth of Massachusetts： The MIT Press，1975.

[4] 潘正君， 康立山， 陳毓屏. 演化計(jì)算[M]. 南寧： 廣西科學(xué)技術(shù)出版社， 1998.

（實(shí)習(xí)編輯：景貴英）