“第一性原理”在演化算法教學中的應用研究

鄭波盡　代航

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

關鍵詞：演化算法；遺傳算法；簡化；優化問題

0 引 言

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

1 演化算法教學困境

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

2 “第一性原理”教學方法

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

2.1 概 述

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

2.2 具體步驟

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

2.3 與通常教學法的比較

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

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

2.4 精簡后的算法形式

在“第一性原理”教學方法中，最重要的步驟是將演化算法寫成最簡單的形式。完整的精簡后的算法以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；

}

}

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

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

2.5 程序運行效果

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

3 “第一性原理”教學效果

“第一性原理”教學方法的應用明顯改善了演化算法理論理解困難、演化算法實踐困難等問題?？偨Y下來，在采用新方法以后，學生得到了較大的提高，表現在以下3個方面。

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

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

2）大部分學生能編寫演化優化程序。

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

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

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

4 總 結

演化算法是人工智能領域一個重要的部分，通過將演化算法大幅簡化到只有十幾行代碼的程度的方式，學生能夠輕易地理解算法中每一行代碼的意思和作用，提高演化算法的教學效果。“第一性原理”教學方法在演化算法教學中的應用還需要在實踐中不斷完善，以期更好地為教學服務。

參考文獻：

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

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

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

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

（實習編輯：景貴英）