針對本科生的演化算法教學探討

龔文引 謝丹

摘要： 演化算法是一種自然啟發式全局優化算法，其魯棒性、高效性、全局搜索能力和隱并行性好等特點，使其成為計算機領域的一個研究熱點。為了能使本科生對演化計算方法有所了解，并對今后的工作或研究生學習有所幫助，有必要為計算機專業的本科生開設演化計算課程。文章結合在本科生教學中的心得，對如何開展本科生演化算法教學進行了探討。

關鍵詞： 演化算法； 本科生教育； 教學方法； 全局優化

中圖分類號：G728文獻標志碼：A 文章編號：1006-8228(2012)07-65-02

0 引言

20世紀80年代中期以來，演化算法(Evolutionary Algorithms)已成為計算機領域的一大研究熱點[1-2]。近30年來，在演化算法中研究學者提出了多種算法，主要包括遺傳算法(Genetic Algorithms)、演化策略(Evolution Strategies)、進化規劃(Evolutionary Programming)、遺傳編程(Genetic Programming)等[3]。

演化算法作為一種新興的優化技術，在計算機研究和應用領域受到了廣泛關注。作為一門研究型課程，結合我校計算機學院的特色，我校為計算機科學與技術專業大四學生開設了演化算法課程，筆者承擔該課程的教學研討工作。結合筆者的教學經驗，認為為本科生開設演化算法課程十分有必要，這對于培養本科生的科研素養和創新能力[4-5]具有很重要的幫助。下面將結合筆者在本科生教學中的心得，對如何開展本科生演化算法教學進行初步探討，以起到拋磚引玉作用。

1 演化算法簡介

作為一種優化算法，演化算法對所優化的問題具有廣泛的適用性，不像經典優化算法需要所優化的問題具有可導、連續、單峰等特點。近年來，演化算法已廣泛應用到各種領域，如：工程優化設計、運籌學、圖像處理、地學工程、經濟領域、電力負荷分配等[1]。

演化算法求解問題的基本思想受到生物演化的啟發，主要包括復制(reproduction)、變異(mutation)、重組(recombination)和選擇(selection)等步驟，其基本思路為：由問題的候選解組成一個群體，然后通過隨機變異，重組和選擇等算子對群體進行演化，其中隨機變異和重組算子提供了發現新解的機制，選擇算子則確定保持哪些解作為下一步搜索的基礎。演化算法的基本框架如圖1所示。

演化算法具有以下幾個優點：①以優化變量的遺傳編碼為運算、搜索對象，不僅可以用于優化數值優化問題，還可用于優化非數值優化問題；②只利用“適應值”信息，而不需利用目標函數的具體值及其他輔助信息，如連續、可導、平滑、無噪音等，從而使得演化算法可以應用于多種優化問題中；③非單點操作，使用群體搜索策略。這使得算法可以進行并行搜索，并且可以一次優化得到多個優化結果，特別適合于進行多目標優化決策；④使用隨機搜索機制。隨機搜索機制的一個優點是相應算法的健壯性(robustness) 得到增強。總的來說，演化算法具有通用、并行、穩健、簡單和全局優化能力強等突出優點。

2 針對本科生的教學

2.1 教學目的

我校計算機學院為本科生開設演化算法課程始于2003年，當時由我院已故康立山教授親自為本科生授課，效果很好，為本科生打開了學術科研之門。

演化算法是一種基于生物界“優勝劣汰”進化機制的優化算法，該算法已經成功應用于多個領域。同時，演化算法中還存在許多亟待解決的問題，以使算法的求解能力更強，魯棒性更好。本課程主要針對計算機專業和相關專業高年級本科生而開設，課程重點對演化算法的機制，不同算法的特點，以及演化算法在不同優化問題的求解進行講解，旨在增強學生對演化算法的了解，同時為今后深造或在工作中應用算法和對算法進行進一步的改進研究。

針對本科生開設演化算法課程，與針對研究生所開設的演化算法課程目的不同。對于本科生我們的目標是提高學生興趣和介紹當前演化算法的研究前沿。以期通過本課程學習，使學生對演化算法的發展概況、基本原理和應用領域有初步了解；對主要技術及應用有一定掌握；通過啟發式授課培養學生對演化算法的興趣，培養他們的知識創新和技術創新能力。為此，我校開設的演化算法課程主要包括課堂教學和實踐教學兩部分，分別為28課時和12課時。

2.2 基于實例的算法演示教學

為了能夠提高學生學習演化算法課程的興趣，并培養學生的科技創新能力，演化算法教學應以實例教學為主，通過演化算法中所涉及的針對實際問題的求解進行演示教學，給學生以直觀的感受。比如在講解函數優化問題時，可以使用VC++和Matlab混合編程設計好的演示軟件，利用Matlab軟件繪制出優化函數的3D圖形，然后動態顯示演化算法群體中的個體搜索最優解的過程，并以此講解群體初始化、父體選擇、雜交、變異、生存選擇的演化操作，使學生加深對利用演化算法求解函數優化問題的認識和理解。講解利用演化算法求解離散優化問題時，可以選擇經典TSP問題作為實例講解。教學中，以TSP的實際應用問題為例，演示演化算法在求解該類問題時的過程，比如，利用演化算法優化屬于TSP問題的動態衛星最短通訊距離問題、大規模集成電路板焊接點問題等。

2.3 教學實踐

在針對本科生進行演化算法教學時，一個必然會遇到的問題是，如何使學生能夠自己編寫演化算法的程序。這需要在實踐教學中對學生進行示例和引導[6]。實踐教學對提高本科生的實際動手能力有著極為重要的作用，不僅可以對所學的編程語言進行鞏固，同時，通過實踐編寫演化算法程序可以使學生進一步了解演化算法的機理和執行過程。

由于絕大部分本科生都是初次接觸演化算法編程，因此在實踐教學中教師有必要首先通過簡單示例編寫程序，演示演化算法程序的編寫。比如演化算法中個體結構體的定義、隨機數發生器的使用、群體初始化、個體適應值的評估、基于輪盤賭的父個體選擇、雜交算子和變異算子的實現等等，需要根據演化算法的執行流程一步一步編寫程序，示范教學。通過示例，使學生學會基本的演化算法程序的編寫，并在實驗課和課后練習以熟練編寫演化算法程序。

2.4 課程報告

作為一門研究型的課程，演化算法主要采用課程報告來檢驗學生是否達到了該門課程的基本要求，因此，每個學生必須在課程結束后提交一份課程報告（包括所實現算法的源程序）。這里所提交的課程報告與程序設計或者數據結構等課程設計的報告有所區別，所提交的課程報告必須是學生通過實踐編寫的演化算法程序，并能夠求解某一類問題，比如無約束優化問題、多目標優化問題、TSP問題等，不強調編程語言，主要看學生對演化算法流程和演化算法編程的掌握程度。

3 結束語

演化算法是人工智能研究領域一大研究熱點。對本科生進行演化算法課程教學不僅可以使學生了解當前人工智能研究領域的一些前沿方向，同時可以培養學生的研究興趣和創新能力。本文結合筆者在演化算法教學中的一些體會，探討了針對演化算法課程的教學思路，希望能起到拋磚引玉作用。

參考文獻：

[1] 潘正君,康立山,陳毓屏.演化計算[M].清華大學出版社,廣西科學技術

出版社,2000.

[2] T. B?ck, U. Hammel, and H-P. Schwefel, Evolutionary

computation:Comments on the history and current state[J]. IEEE Transactions on Evolutionary Computation,1997.1(1):3-17

[3] T. B?ck, Evolutionary Algorithms in Theory and Practice: Evolution

Strategies, Evolutionary Programming, Genetic Algorithms[M].Oxford Univ.Press,1996.

[4] 何軍輝.計算機學科本科生科研創新能力培養模式探究[J]. 計算機教

育,2011.12:1-4

[5] 黃雅萍,強莎莎,駱軼妹,馬可辛.改革計算機基礎教學,培養本科生創

新能力[J].計算機時代,2007.8:62-63

[6] 付小晶,張國印,武俊鵬.計算機專業本科生實踐創新能力培養方法

探討[J].計算機教育,2009.8:27-29