龔文引 謝丹

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

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

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

0 引言

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

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

1 演化算法簡(jiǎn)介

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

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

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

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

2.1 教學(xué)目的

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

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

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

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

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

2.3 教學(xué)實(shí)踐

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

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

2.4 課程報(bào)告

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

3 結(jié)束語(yǔ)

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

參考文獻(xiàn)：

[1] 潘正君,康立山,陳毓屏.演化計(jì)算[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] 何軍輝.計(jì)算機(jī)學(xué)科本科生科研創(chuàng)新能力培養(yǎng)模式探究[J]. 計(jì)算機(jī)教

育,2011.12:1-4

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

新能力[J].計(jì)算機(jī)時(shí)代,2007.8:62-63

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

探討[J].計(jì)算機(jī)教育,2009.8:27-29