算法設(shè)計(jì)課程中的智能優(yōu)化算法教學(xué)

摘要：算法設(shè)計(jì)課程是計(jì)算機(jī)專業(yè)專科生選修課程，智能優(yōu)化算法是其中的重要內(nèi)容。針對(duì)智能優(yōu)化算法中知識(shí)點(diǎn)抽象和學(xué)生難以理解的現(xiàn)狀，提出將多種教學(xué)方法和手段運(yùn)用到實(shí)際教學(xué)中，進(jìn)一步優(yōu)化教學(xué)效果和加強(qiáng)教學(xué)改革的觀點(diǎn)。

關(guān)鍵詞：算法設(shè)計(jì)；智能優(yōu)化算法；教學(xué)方法

0 引言

培養(yǎng)高素質(zhì)和創(chuàng)新型人才是各高等學(xué)校教育改革的重點(diǎn)。專科學(xué)校在人才培養(yǎng)上以學(xué)生就業(yè)為重點(diǎn)，著重培養(yǎng)學(xué)生的一技之長(zhǎng)，學(xué)生對(duì)與專業(yè)相關(guān)的其他知識(shí)涉及不多。畢業(yè)生反饋雖然這種培養(yǎng)方式可以讓學(xué)生很快找到工作并投入到實(shí)際工作中，但是在校所學(xué)知識(shí)的單一化導(dǎo)致工作的層次較低，工作面比較窄。適當(dāng)增加和本專業(yè)相關(guān)的知識(shí)，拓寬學(xué)生的知識(shí)面，增強(qiáng)學(xué)生的就業(yè)能力，培養(yǎng)高素質(zhì)人才是學(xué)校進(jìn)行教學(xué)改革的目的。算法設(shè)計(jì)課程是計(jì)算機(jī)專業(yè)本科學(xué)生的必修課程，對(duì)于這門課程，專科學(xué)生理解起來(lái)比較困難，因此學(xué)校將其作為選修課程。這門課程的重點(diǎn)內(nèi)容是什么，講解的深度如何把握，都需要教師在實(shí)際教學(xué)過(guò)程中進(jìn)行探討。

1 選擇重點(diǎn)教學(xué)內(nèi)容

算法設(shè)計(jì)這門課程涉及的領(lǐng)域非常寬泛，通常包括的內(nèi)容有基本和經(jīng)典的算法，算法設(shè)計(jì)策略、問(wèn)題復(fù)雜性等方面的理論研究，以及近年來(lái)在并行算法、隨機(jī)算法、近似算法、加密算法、智能優(yōu)化算法、模式識(shí)別算法等算法領(lǐng)域方面的最新研究成果。

智能優(yōu)化算法是當(dāng)今算法領(lǐng)域比較熱門和應(yīng)用比較廣泛的算法之一。它又稱為現(xiàn)代啟發(fā)式算法，是一種具有全局優(yōu)化性能、通用性強(qiáng)且適合并行處理的算法。這種算法一般具有嚴(yán)密的理論依據(jù)，從理論上講可以在一定的時(shí)間內(nèi)找到最優(yōu)解或近似最優(yōu)解。智能優(yōu)化算法在實(shí)際中應(yīng)用廣泛，因此教師在算法設(shè)計(jì)課程中有必要將這部分內(nèi)容介紹給學(xué)生。

1.1 常見(jiàn)的智能優(yōu)化算法

1.1.1 遺傳算法

遺傳算法（Genetic Algorithm，GA）是一類借鑒生物界的進(jìn)化規(guī)律（適者生存，優(yōu)勝劣汰遺傳機(jī)制）演化而來(lái)的隨機(jī)化搜索方法，由美國(guó)J·Holland教授于1975年首先提出。遺傳算法已被人們廣泛地應(yīng)用于組合優(yōu)化、機(jī)器學(xué)習(xí)、信號(hào)處理、自適應(yīng)控制和人工生命等領(lǐng)域。它是現(xiàn)代有關(guān)智能計(jì)算中的關(guān)鍵技術(shù)。

1.1.2 蟻群算法

蟻群算法（Ant Colony Optimization，ACO），又稱螞蟻算法，是一種用來(lái)在圖中尋找優(yōu)化路徑的機(jī)率型算法。它由Marco Dorigo于1992年在博士論文中提出，其靈感來(lái)源于螞蟻在尋找食物過(guò)程中發(fā)現(xiàn)路徑的行為。蟻群算法是一種模擬進(jìn)化算法，初步的研究表明該算法具有許多優(yōu)良的性質(zhì)。

1.1.3 模擬退火算法

模擬退火算法（Simulated Annealing，SA）最早由Kirkpatrick等應(yīng)用于組合優(yōu)化領(lǐng)域，是基于Mente-Carlo迭代求解策略的一種隨機(jī)尋優(yōu)算法，出發(fā)點(diǎn)是基于物理中固體物質(zhì)的退火過(guò)程與一般組合優(yōu)化問(wèn)題之間的相似性。模擬退火算法從某一較高初溫出發(fā)，伴隨溫度參數(shù)的不斷下降，結(jié)合概率突跳特性在解空間中隨機(jī)尋找目標(biāo)函數(shù)的全局最優(yōu)解，即能從局部最優(yōu)解概率性地跳出并最終趨于全局最優(yōu)。模擬退火算法是一種通用的優(yōu)化算法，從理論上講具有概率的全局優(yōu)化性能，目前已在工程中得到廣泛應(yīng)用，諸如VLSI、生產(chǎn)調(diào)度、控制工程、機(jī)器學(xué)習(xí)、神經(jīng)網(wǎng)絡(luò)、信號(hào)處理等領(lǐng)域。

1.2 智能優(yōu)化算法特點(diǎn)與優(yōu)勢(shì)

遺傳算法的主要特點(diǎn)是直接對(duì)結(jié)構(gòu)對(duì)象進(jìn)行操作，不存在求導(dǎo)和函數(shù)連續(xù)性的限定，具有內(nèi)在的隱并行性和更好的全局尋優(yōu)能力。它采用概率化的尋優(yōu)方法，能自動(dòng)獲取和指導(dǎo)優(yōu)化的搜索空間，自適應(yīng)地調(diào)整搜索方向，而不需要確定的規(guī)則。

蟻群算法有別于傳統(tǒng)編程模式，優(yōu)勢(shì)在于避免編寫冗長(zhǎng)的程序，程序本身是基于一定規(guī)則的隨機(jī)運(yùn)行來(lái)尋找最佳配置。也就是說(shuō)，當(dāng)程序最開(kāi)始找到目標(biāo)的時(shí)候，路徑幾乎不可能是最優(yōu)的，甚至可能包含無(wú)數(shù)錯(cuò)誤的選擇。但是，程序可以通過(guò)螞蟻尋找食物時(shí)候的信息素原理，不斷地修正原來(lái)的路線，使整個(gè)路線越來(lái)越短，即程序執(zhí)行的時(shí)間越長(zhǎng)，所獲得的路徑就越可能接近最優(yōu)路徑。

模擬退火算法是通過(guò)賦予搜索過(guò)程一種時(shí)變且最終趨于零的概率突跳性，從而有效避免陷入局部極小并最終趨于全局最優(yōu)的串行結(jié)構(gòu)優(yōu)化算法。

這3種算法的共同特點(diǎn)是從任一解出發(fā)，按照某種機(jī)制，以一定的概率在整個(gè)求解空間中探索最優(yōu)解。由于它們可以把搜索空間擴(kuò)展到整個(gè)問(wèn)題空間，因而具有全局優(yōu)化性能。

2 采用多種教學(xué)方法

從培養(yǎng)高素質(zhì)計(jì)算機(jī)人才的需求出發(fā)，以拓寬學(xué)生知識(shí)面及提高學(xué)生實(shí)踐能力為目標(biāo)，針對(duì)智能優(yōu)化算法這部分知識(shí)內(nèi)容，授課教師可以采用多種教學(xué)方法和手段，充分發(fā)揮學(xué)生學(xué)習(xí)的潛能和積極性，改善課堂教學(xué)氣氛，提高教學(xué)效果。

2.1 案例教學(xué)

案例教學(xué)是一種通過(guò)模擬或者重現(xiàn)現(xiàn)實(shí)生活中的一些場(chǎng)景，讓學(xué)生把自己納入案例場(chǎng)景，通過(guò)討論或者研討進(jìn)行學(xué)習(xí)的一種教學(xué)方法。教學(xué)中既可以通過(guò)分析和比較，研究各種各樣的成功和失敗的案例，從中抽象出一般性的結(jié)論或原理，又可以讓學(xué)生通過(guò)自己的思考或者他人的思考拓寬自己的視野，從而豐富自己的知識(shí)。

在教學(xué)過(guò)程中，教師可以通過(guò)實(shí)際生活中的一個(gè)案例幫助學(xué)生提升對(duì)算法的學(xué)習(xí)興趣。如旅行商問(wèn)題，假設(shè)有一個(gè)旅行商人要拜訪n個(gè)城市，他必須選擇要走的路徑，限制條件是每個(gè)城市只能拜訪一次，而且最后要回到原來(lái)出發(fā)的城市。路徑的選擇目標(biāo)是要求所得的路徑長(zhǎng)度為所有路徑之中的最小值。

學(xué)生通過(guò)自己思考，再經(jīng)過(guò)小組討論，通常都會(huì)得出這樣一個(gè)最容易想到的方法：利用排列組合的方法把所有路徑都計(jì)算出來(lái)并逐一比較，選出最小路徑。教師可以根據(jù)這個(gè)結(jié)論，引導(dǎo)學(xué)生明確雖然該方法在理論上是可行的，但路徑的個(gè)數(shù)等于n！。當(dāng)城市個(gè)數(shù)較大時(shí)，該方法的求解時(shí)間是難以忍受的，甚至是不可能完成的。例如，當(dāng)包含20個(gè)城市時(shí)，20！=2432902 008 176 640 000，以每秒1億次的計(jì)算速度來(lái)估算，求解時(shí)間長(zhǎng)達(dá)700多年。因此，學(xué)生認(rèn)為旅行商問(wèn)題的全局最優(yōu)解是無(wú)法確定的，只可能得到近似最優(yōu)解。這樣，這類問(wèn)題追求的目標(biāo)就變成以盡可能短的時(shí)間求得質(zhì)量盡可能好的近似解，自然地引導(dǎo)出模擬退火算法，從而為介紹該算法作了有序的鋪墊。

2.2 多媒體演示教學(xué)

多媒體教學(xué)是指在教學(xué)過(guò)程中，根據(jù)教學(xué)目標(biāo)和教學(xué)對(duì)象的特點(diǎn)，通過(guò)教學(xué)設(shè)計(jì)合理選擇和運(yùn)用現(xiàn)代教學(xué)媒體，并與傳統(tǒng)教學(xué)手段有機(jī)組合，共同參與教學(xué)全過(guò)程，以多種媒體信息作用于學(xué)生，形成合理的教學(xué)過(guò)程結(jié)構(gòu)，達(dá)到最優(yōu)化的教學(xué)效果。

例如，教師在講解蟻群優(yōu)化算法時(shí)，學(xué)生對(duì)該算法理論知識(shí)的理解還不是很深刻，不能在頭腦里形成對(duì)該算法的形象認(rèn)知。教師可以利用多媒體課件向?qū)W生演示自然蟻群的生態(tài)行動(dòng)，加強(qiáng)學(xué)生對(duì)這種算法的理解。

2.3 網(wǎng)絡(luò)遠(yuǎn)程教學(xué)

網(wǎng)絡(luò)遠(yuǎn)程教學(xué)是一種相對(duì)于面授教育的師生分離和非面對(duì)面組織的教學(xué)活動(dòng)，它的特點(diǎn)是學(xué)生與教師分離，學(xué)習(xí)的場(chǎng)所和形式靈活多變。與面授教育相比，它的優(yōu)勢(shì)在于能夠提供更多的學(xué)習(xí)機(jī)會(huì)，提高教學(xué)質(zhì)量，降低教學(xué)成本。

針對(duì)學(xué)生在課堂上對(duì)知識(shí)點(diǎn)理解不深刻的現(xiàn)狀，教師可以通過(guò)建立網(wǎng)站或個(gè)人網(wǎng)頁(yè)設(shè)立教學(xué)園地，提供教學(xué)輔助軟件下載，設(shè)計(jì)一些有關(guān)算法的動(dòng)態(tài)演示，展示最新成果，與學(xué)生交流討論并解答學(xué)生的問(wèn)題。

3 教學(xué)實(shí)踐應(yīng)用及效果

在教學(xué)實(shí)踐中，教師可以采用一些實(shí)例說(shuō)明問(wèn)題，如在講解蟻群算法時(shí)介紹經(jīng)典的TSP源程序，在課堂上改變相應(yīng)的參數(shù)并進(jìn)行調(diào)試，同時(shí)繪制出最優(yōu)路徑上信息素的變化曲線。教師在講解過(guò)程中可以由簡(jiǎn)入深，還可以采用學(xué)校現(xiàn)有考試系統(tǒng)中的自動(dòng)組卷功能，對(duì)比介紹遺傳算法和模擬退火算法的特點(diǎn)。遺傳算法的局部搜索能力差，但對(duì)搜索過(guò)程的總體把握能力強(qiáng)；模擬退火算法具有較強(qiáng)的局部搜索能力，但對(duì)整個(gè)搜索空間的狀況掌控能力不強(qiáng)。因此，學(xué)校考試系統(tǒng)自動(dòng)組卷功能的開(kāi)發(fā)實(shí)現(xiàn)應(yīng)結(jié)合2種算法的長(zhǎng)處。教師采用對(duì)比方法進(jìn)行講解，可以使學(xué)生更容易理解2種算法的特點(diǎn)。

以上多種教學(xué)方法和實(shí)例的應(yīng)用講解，大大提高了學(xué)生對(duì)這部分知識(shí)的學(xué)習(xí)興趣，增強(qiáng)學(xué)生主動(dòng)參與課堂教學(xué)的積極性，使本來(lái)枯燥和復(fù)雜的算法問(wèn)題也變得更加直觀，有效地提高了教學(xué)效率。

4 結(jié)語(yǔ)

智能優(yōu)化算法作為專科學(xué)校計(jì)算機(jī)專業(yè)的選修課程內(nèi)容，教學(xué)內(nèi)容側(cè)重點(diǎn)需要任課教師認(rèn)真討論和挑選。針對(duì)智能優(yōu)化算法的教學(xué)方法可以采用案例教學(xué)、多媒體演示教學(xué)、網(wǎng)絡(luò)遠(yuǎn)程教學(xué)等方法，以使學(xué)生快速掌握設(shè)計(jì)思想，提高知識(shí)層次，拓寬知識(shí)面。

（編輯：宋文婷）