“第一性原理”在演化算法教學(xué)中的應(yīng)用研究

鄭波盡　代航

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

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

0 引 言

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

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

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

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

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

2.1 概 述

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

2.2 具體步驟

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

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

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

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

2.4 精簡后的算法形式

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

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

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

2.5 程序運行效果

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

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

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

1）理解了群體爬山的機制。

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

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

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

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

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

4 總 結(jié)

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

參考文獻：

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

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

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

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

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