針對本科生的演化算法教學(xué)探討

龔文引 謝丹

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

關(guān)鍵詞： 演化算法； 本科生教育； 教學(xué)方法； 全局優(yōu)化

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

0 引言

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

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

1 演化算法簡介

作為一種優(yōu)化算法，演化算法對所優(yōu)化的問題具有廣泛的適用性，不像經(jīng)典優(yōu)化算法需要所優(yōu)化的問題具有可導(dǎo)、連續(xù)、單峰等特點。近年來，演化算法已廣泛應(yīng)用到各種領(lǐng)域，如：工程優(yōu)化設(shè)計、運籌學(xué)、圖像處理、地學(xué)工程、經(jīng)濟領(lǐng)域、電力負(fù)荷分配等[1]。

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

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

2 針對本科生的教學(xué)

2.1 教學(xué)目的

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

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

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

2.2 基于實例的算法演示教學(xué)

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

2.3 教學(xué)實踐

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

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

2.4 課程報告

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

3 結(jié)束語

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

參考文獻：

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

出版社,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] 何軍輝.計算機學(xué)科本科生科研創(chuàng)新能力培養(yǎng)模式探究[J]. 計算機教

育,2011.12:1-4

[5] 黃雅萍,強莎莎,駱軼妹,馬可辛.改革計算機基礎(chǔ)教學(xué),培養(yǎng)本科生創(chuàng)

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

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

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