計(jì)算機(jī)仿真在運(yùn)籌學(xué)優(yōu)化算法教學(xué)中的應(yīng)用
——以偏粒子群算法為例

李 鋒

(華南理工大學(xué)工商管理學(xué)院，廣州510640)

0 引言

運(yùn)籌學(xué)(operations research)的應(yīng)用數(shù)學(xué)天性，要求工商管理學(xué)院的學(xué)生通過(guò)課程學(xué)習(xí)，能夠靈活地應(yīng)用理論知識(shí)完成對(duì)實(shí)際問(wèn)題的分析、建模和求解。在這個(gè)問(wèn)題求解的規(guī)范流程中，分析和建模對(duì)學(xué)生的知識(shí)點(diǎn)掌握和靈活應(yīng)用有著較高的要求，而問(wèn)題求解則要求學(xué)生能夠熟練應(yīng)用專業(yè)工具軟件實(shí)現(xiàn)二次編程、計(jì)算求解和參數(shù)分析。如果教師在教學(xué)或?qū)W生在學(xué)習(xí)過(guò)程中過(guò)于強(qiáng)調(diào)理論學(xué)習(xí)而忽視工具求解，勢(shì)必造成學(xué)生“至多”能夠建立應(yīng)用問(wèn)題的數(shù)學(xué)模型，但對(duì)如何解決問(wèn)題一籌莫展。長(zhǎng)此以往，勢(shì)必削弱學(xué)生解決實(shí)際問(wèn)題的能力，最終影響課程所要求的教學(xué)目標(biāo)和能力培養(yǎng)。

以運(yùn)籌學(xué)課程中的整數(shù)規(guī)劃(整數(shù)線性規(guī)劃)為例，雖然現(xiàn)實(shí)世界中的眾多應(yīng)用問(wèn)題(如路徑規(guī)劃、生產(chǎn)調(diào)度、資源配置等)都是典型的整數(shù)規(guī)劃問(wèn)題并可以建立其整數(shù)規(guī)劃模型，但是運(yùn)籌學(xué)理論教學(xué)中講授的分支定界法、割平面法在實(shí)際問(wèn)題求解中過(guò)于繁瑣而失去其求解意義［1］。就研究領(lǐng)域而言，現(xiàn)實(shí)世界中的整數(shù)規(guī)劃問(wèn)題絕大多數(shù)都是非確定性多項(xiàng)式難問(wèn)題(Non-deter ministic Polynomial Hard，NP-Hard)，其計(jì)算求解的時(shí)間消耗與問(wèn)題模型的規(guī)模呈現(xiàn)指數(shù)形式相關(guān)性。而運(yùn)籌學(xué)教學(xué)中常見(jiàn)的小工具-Excel軟件中可以加載的“規(guī)劃求解”工具在面對(duì)多約束條件的整數(shù)規(guī)劃問(wèn)題就顯得無(wú)能為力了。這勢(shì)必要求運(yùn)籌學(xué)課程教學(xué)中必須增加對(duì)優(yōu)化算法，特別是求解復(fù)雜問(wèn)題的智能優(yōu)化算法和工具的講授。

在此運(yùn)籌學(xué)教學(xué)的趨勢(shì)和方向引導(dǎo)下，基于復(fù)雜數(shù)學(xué)理論支撐的智能優(yōu)化算法的講授成為運(yùn)籌學(xué)教學(xué)和實(shí)踐中的難點(diǎn)問(wèn)題。一方面，智能優(yōu)化算法的數(shù)學(xué)理論涉及內(nèi)容較多，課程講授的難度較大，也比較枯燥;另一方面，管理工程學(xué)科的知識(shí)體系設(shè)計(jì)也并不要求學(xué)生掌握這部分理論基礎(chǔ)內(nèi)容，更傾向于“僅”要求學(xué)生會(huì)使用主流的工具軟件實(shí)現(xiàn)算法計(jì)算和結(jié)果展示。因此，如何將優(yōu)化算法講得深入淺出，既能夠介紹優(yōu)化算法的基本和核心，又能夠幫助學(xué)生有效的應(yīng)用這些算法，成為當(dāng)前運(yùn)籌學(xué)教學(xué)的一個(gè)關(guān)鍵問(wèn)題和通識(shí)問(wèn)題。本文正是在此大環(huán)境下，結(jié)合10多年來(lái)運(yùn)籌學(xué)教學(xué)實(shí)踐，呈現(xiàn)出自己的教學(xué)經(jīng)驗(yàn)。

1 國(guó)內(nèi)外研究現(xiàn)狀

運(yùn)籌學(xué)課程特點(diǎn)，強(qiáng)調(diào)教學(xué)中理論聯(lián)系實(shí)際，因此該領(lǐng)域國(guó)內(nèi)外專家都在探索除傳統(tǒng)數(shù)學(xué)建模和問(wèn)題求解以外的其他各種形式的教學(xué)和教輔。本文主要以運(yùn)營(yíng)管理領(lǐng)域中最具盛名的運(yùn)籌學(xué)和管理科學(xué)協(xié)會(huì)(Institute for Operations Research and the Management Sciences，INFORMS)對(duì)于運(yùn)籌學(xué)教學(xué)、教改探索和實(shí)踐為標(biāo)桿，論述當(dāng)前相關(guān)課程學(xué)習(xí)中的先進(jìn)理念和方法。

隨著運(yùn)籌學(xué)課程的重要性被逐步挖掘，特別是供應(yīng)鏈管理、物流管理等應(yīng)用實(shí)踐的推動(dòng)，領(lǐng)域內(nèi)對(duì)于運(yùn)籌學(xué)課程建設(shè)和開(kāi)發(fā)不斷重視。當(dāng)前，運(yùn)籌學(xué)課程教學(xué)已經(jīng)從早期的多媒體教學(xué)和案例教學(xué)，已經(jīng)逐步向課堂游戲和計(jì)算機(jī)仿真等交互性更強(qiáng)教學(xué)方式轉(zhuǎn)化。例如，早期教學(xué)中提出通過(guò)課件中字體變化、有意識(shí)地“筆誤”來(lái)吸引學(xué)生注意力［2］;通過(guò)課堂中的小錄像來(lái)幫助學(xué)生掌握知識(shí)點(diǎn)［3］;通過(guò)案例形式的實(shí)際應(yīng)用問(wèn)題逐步加深學(xué)習(xí)包括線性規(guī)劃、整數(shù)規(guī)劃以及指派問(wèn)題的問(wèn)題建模和求解［4-5］;強(qiáng)調(diào)結(jié)合工具軟件設(shè)計(jì)計(jì)算結(jié)果的直觀表現(xiàn)［6］等。當(dāng)前則更強(qiáng)調(diào)實(shí)際問(wèn)題的多領(lǐng)域交叉，通過(guò)仿真、游戲等方式調(diào)動(dòng)學(xué)生的積極性，培養(yǎng)學(xué)生的綜合能力。例如，通過(guò)課堂游戲形式模擬生產(chǎn)制造、服務(wù)企業(yè)的運(yùn)營(yíng)管理，融合運(yùn)籌學(xué)各個(gè)定量分析知識(shí)點(diǎn)［7-8］;文獻(xiàn)［9］中更是強(qiáng)調(diào)了課堂游戲前的組織、游戲后的總結(jié)的重要性。其中，目標(biāo)于解決實(shí)際應(yīng)用問(wèn)題的“高級(jí)”運(yùn)籌學(xué)知識(shí)點(diǎn)-優(yōu)化算法、優(yōu)化工具的學(xué)習(xí)成為領(lǐng)域?qū)＜抑攸c(diǎn)關(guān)注的問(wèn)題之一。而相應(yīng)的案例教學(xué)、工具軟件使用、計(jì)算機(jī)仿真以及課堂游戲等教學(xué)方式和手段不斷在探索。例如，文獻(xiàn)［10］中強(qiáng)調(diào)了優(yōu)化算法和工具的應(yīng)用和實(shí)踐導(dǎo)向，將傳統(tǒng)的課程筆試考核改為問(wèn)題求解考察。

除此之外，在計(jì)算機(jī)仿真研究領(lǐng)域，專家也同樣認(rèn)識(shí)到計(jì)算機(jī)仿真在教學(xué)中的重要作用。早在20年前就開(kāi)始建立了一個(gè)仿真教育(Simulation Education/Simulation in Education)分枝，專門研究如何更加可視化、友好性的講授專業(yè)知識(shí)和問(wèn)題。例如，文獻(xiàn)［11］中介紹了3D實(shí)體模型仿真在精益制造課程教學(xué)中的應(yīng)用，文獻(xiàn)［12］中介紹了供應(yīng)鏈管理課程中(含物流管理課程)的仿真教學(xué)，文獻(xiàn)［13］中則是討論了仿真和游戲教學(xué)在運(yùn)營(yíng)管理課程中的應(yīng)用和推廣，并詳細(xì)描述了教師在仿真游戲教學(xué)中的職責(zé)和引導(dǎo)。在國(guó)內(nèi)，教育專家也討論了仿真在內(nèi)的信息技術(shù)對(duì)于傳統(tǒng)課程教學(xué)的促進(jìn)作用［14］，強(qiáng)調(diào)教學(xué)方法和手段的多樣化［15］等。

在該領(lǐng)域發(fā)展趨勢(shì)影響下，結(jié)合前期教學(xué)工作和教研項(xiàng)目積累，本文嘗試將計(jì)算機(jī)仿真技術(shù)引入到優(yōu)化算法的教學(xué)開(kāi)發(fā)中，幫助學(xué)生快速地掌握高級(jí)的優(yōu)化算法原理計(jì)算步驟。下面給出了一個(gè)典型的智能優(yōu)化算法-偏粒子群算法的計(jì)算機(jī)仿真描述和可視化教學(xué)。

2 優(yōu)化算法中偏粒子群算法

偏粒子群算法(Particle Swarm Optimization，PSO)是智能優(yōu)化算法的一種，相對(duì)于復(fù)雜優(yōu)化問(wèn)題的精確求解算法，其能夠以較高的計(jì)算效率求得研究問(wèn)題的次優(yōu)解，甚至是最優(yōu)解。在眾多的智能優(yōu)化算法中，偏粒子群算法的算法思路相對(duì)直觀，計(jì)算步驟相對(duì)簡(jiǎn)單，求解能力突出［16］。例如，遺傳算法中研究問(wèn)題的編碼，以及交叉和變異操作較為復(fù)雜［17］，禁忌算法、螞蟻算法中的概率同樣難以解釋［18］。而源于仿真模擬鳥(niǎo)群飛行的偏粒子群算法則是假定每個(gè)粒子僅根據(jù)鳥(niǎo)群整體的最佳解和自身歷史最佳解調(diào)整參數(shù)變化速度和變化方向，并以此不斷逼近最優(yōu)解。因此，偏粒子群算法適合作為本科學(xué)生，特別是工商管理學(xué)院學(xué)生的運(yùn)籌學(xué)課程教學(xué)。

2.1 偏粒子群算法的步驟

類似其他智能優(yōu)化算法，偏粒子群算法的提出也是源于模擬生物世界中鳥(niǎo)群捕食的群體行為。

假定在給定的一個(gè)空間領(lǐng)域中，只有一個(gè)位置有食物。而在此空間中，一群鳥(niǎo)都在隨機(jī)的飛行，并在飛行的過(guò)程中不斷的交流對(duì)于食物位置的信息:當(dāng)一只鳥(niǎo)更接近于食物時(shí)，它會(huì)將自己的位置廣播給其他所有鳥(niǎo);而其他的鳥(niǎo)都將根據(jù)該位置信息調(diào)整自己的飛行方向和飛行速度，朝著這個(gè)位置飛去。最終，所有鳥(niǎo)都將聚集在食物所在的位置。

偏粒子群算法在此鳥(niǎo)群覓食的思路下，將一個(gè)復(fù)雜問(wèn)題的求極值看作是一群鳥(niǎo)的覓食過(guò)程。其中，將研究問(wèn)題的可行域類比為鳥(niǎo)群飛行的空間，目標(biāo)函數(shù)的極值點(diǎn)看作為“食物”的位置。在該空間中，每個(gè)獨(dú)自搜索最優(yōu)解的“粒子”都類比為一只鳥(niǎo)。在搜索過(guò)程中，每個(gè)粒子都不斷調(diào)整決策變量的取值和變化量，即鳥(niǎo)飛行的方向和速度。更重要的是，在搜索過(guò)程中，所有粒子都將同步更新/共享已知搜索范圍內(nèi)的最優(yōu)解。而這種信息共享機(jī)制，正是包括偏粒子群算法、螞蟻算法、遺傳算法等群體智能算法(Swarm Intelligence)的關(guān)鍵。

以一個(gè)二維變量的優(yōu)化問(wèn)題為例:

偏粒子群算法求解該最大化問(wèn)題，可以簡(jiǎn)單分為兩步，第1步為初始化。在此步驟中，為粒子群中的每個(gè)粒子隨機(jī)生成其在可行域中的位置，以及位置變化的速度，即:

式中:PositionX(i)定義了第i個(gè)粒子在X方向上的坐標(biāo);VelocityX(i)為其在X方向上的移動(dòng)速度，sx為速度上限值。類似，PositionY(i)，VelocityY(i)，sy分別定義了第i個(gè)粒子在Y方向上的坐標(biāo)、移動(dòng)速度和速度上限值。

接著，計(jì)算粒子所處位置的目標(biāo)函數(shù)，即適應(yīng)度函數(shù)值。

此時(shí)，初始化粒子的當(dāng)前個(gè)人最優(yōu)解以及目標(biāo)函數(shù)值為:

隨后，確定當(dāng)前所有粒子中的最優(yōu)目標(biāo)函數(shù)值，以及相應(yīng)的位置坐標(biāo):

算法的第2步為粒子的迭代搜索過(guò)程。具體來(lái)說(shuō)，粒子將根據(jù)共享的群體最優(yōu)解信息，以及自身當(dāng)前狀態(tài)和速度調(diào)整自己的速度，并隨即更新自己的位置。具體來(lái)說(shuō)，每個(gè)粒子將根據(jù)當(dāng)前自己的速度(具有一定的慣性)，自己最優(yōu)解的位置偏好和群體最優(yōu)解的位置偏好計(jì)算飛行速度:

式中:velocityInertia定義了粒子的速度慣性;personalBestWeight為其對(duì)自己已知最優(yōu)解的偏好權(quán)重，globalBestWeight為其對(duì)群體最優(yōu)解的偏好權(quán)重。

在計(jì)算得到粒子的速度后，可以得到單位時(shí)間間隔之后位置為:

接著，根據(jù)式(3)重新計(jì)算粒子在新位置上的目標(biāo)函數(shù)值。并在此基礎(chǔ)上，更新每個(gè)粒子的當(dāng)前最優(yōu)解和群體的最優(yōu)解。

粒子群算法將重復(fù)第2步所示的計(jì)算，直到找到最優(yōu)解。

2.2 偏粒子群算法求解過(guò)程的仿真建模

以偏粒子群算法為代表的群體智能算法由于涉及多個(gè)獨(dú)立決策對(duì)象的決策過(guò)程，以及對(duì)象之間的信息交互，更加適合于與其有天然聯(lián)系的多智能體建模與仿真;實(shí)現(xiàn)其問(wèn)題求解過(guò)程。

在多智能體建模方法下，每一個(gè)粒子都將被設(shè)置為一個(gè)獨(dú)立決策的智能體對(duì)象。它紀(jì)錄了自己的搜索軌跡和搜索結(jié)果，同時(shí)還不斷與其他粒子交換信息。具體來(lái)說(shuō)，每個(gè)粒子的靜態(tài)屬性和動(dòng)態(tài)行為方法如圖1所示。

在每個(gè)偏粒子群算法的迭代步驟中，每個(gè)“粒子”智能體的計(jì)算過(guò)程如圖2所示。

由圖2可見(jiàn)，偏粒子群算法中每個(gè)粒子的行為相對(duì)簡(jiǎn)單，僅僅是根據(jù)群體最優(yōu)解和自己的最優(yōu)解進(jìn)行應(yīng)激式的調(diào)整。但是，通過(guò)粒子群之間關(guān)于群體最優(yōu)解的信息交互，使得粒子群能夠?qū)崿F(xiàn)復(fù)雜優(yōu)化問(wèn)題的計(jì)算求解。而這一點(diǎn)也正是群體智能算法的魅力所在。

3 偏粒子群算法的仿真課件開(kāi)發(fā)

3.1 復(fù)雜優(yōu)化問(wèn)題實(shí)例

為了課堂演示偏粒子群算法的算法能力，在教學(xué)中考慮以下兩個(gè)問(wèn)題。第1個(gè)問(wèn)題為確定、連續(xù)性問(wèn)題:

第2個(gè)問(wèn)題在第1個(gè)問(wèn)題基礎(chǔ)上，增加了隨機(jī)性因素ρ(服從標(biāo)準(zhǔn)0-1均勻分布)，即:

無(wú)論是第1個(gè)問(wèn)題還是第2個(gè)問(wèn)題，都可以得到相同的最優(yōu)解和取值:

但是，相比于第1個(gè)問(wèn)題，第2個(gè)問(wèn)題存在若干個(gè)局部最小值，使得算法搜索起來(lái)更加吃力。

3.2 多智能體仿真的代碼開(kāi)發(fā)

為使課堂教學(xué)中仿真及算法演示更加直觀，選擇了界面友好性更好的Netlogo 6.0.1作為多智能體仿真 二 次 開(kāi) 發(fā) 平 臺(tái) (http://ccl.northwestern.edu/netlogo/)。

相比于Swarm、Repast等多智能體建模與仿真工具，Netlogo軟件平臺(tái)開(kāi)發(fā)更加簡(jiǎn)單和智能。以式(12)所示的第2個(gè)優(yōu)化問(wèn)題為例，其在Netlogo軟件平臺(tái)下，只需要如下一行代碼就可以實(shí)現(xiàn)。

為了增強(qiáng)問(wèn)題求解空間的可視性，采用不同灰度來(lái)顯示不同位置的目標(biāo)函數(shù)值/Fitness值。

如圖3(a)所示，圖中顏色越深則該位置的函數(shù)取值就越大，其也越接近原點(diǎn)(0，0)。而圖3(b)則顯示出，平面上多處顏色較黑，即干擾偏粒子群算法求得全局最優(yōu)解的局部最優(yōu)解較多。

圖3 Netlogo軟件平臺(tái)上的問(wèn)題可行域空間

3.3 仿真課件的主要內(nèi)容

在仿真程序開(kāi)發(fā)的基礎(chǔ)上，設(shè)計(jì)智能優(yōu)化算法課堂教學(xué)信息如下(2學(xué)時(shí)):

(1)教學(xué)目標(biāo)。在工商管理學(xué)院的《運(yùn)籌學(xué)》本科教學(xué)中，介紹常見(jiàn)用于解決復(fù)雜應(yīng)用問(wèn)題的智能優(yōu)化算法。教學(xué)目的包括介紹具體智能優(yōu)化算法的算法思路、計(jì)算步驟和結(jié)果解釋，以及介紹智能優(yōu)化算法在運(yùn)籌學(xué)應(yīng)用領(lǐng)域的適用性。

(2)教學(xué)內(nèi)容1。在實(shí)際課堂教學(xué)及演示中，通過(guò)研究問(wèn)題1的求解過(guò)程可視化和計(jì)算機(jī)仿真，介紹偏粒子群算法的計(jì)算過(guò)程，如圖4所示，t為計(jì)算仿真中向前推進(jìn)的時(shí)鐘值，以滴答(tick)為單位。

如圖4(a)所示，在初始化階段，總共有10個(gè)粒子(紅色標(biāo)示點(diǎn))被隨機(jī)的放置在問(wèn)題求解的二位空間上。在計(jì)算過(guò)程中，紅色的軌跡線不斷給出10個(gè)粒子在每次迭代(即仿真時(shí)鐘t+1)中的位置更新。最終，如圖4(i)所示，最終粒子匯集到了中心點(diǎn)，即搜索到應(yīng)用問(wèn)題1的最優(yōu)解處，此時(shí)計(jì)算結(jié)束。

圖4 應(yīng)用問(wèn)題1的求解過(guò)程可視化(部分)

圖5給出了計(jì)算過(guò)程中，偏粒子群全局最優(yōu)解的變化過(guò)程(式(5))。由圖5可見(jiàn)，全局最優(yōu)解很快就收斂到應(yīng)用問(wèn)題最優(yōu)解(原點(diǎn)，即目標(biāo)函數(shù)為0)的位置。

圖5 應(yīng)用問(wèn)題1中GlobalBestFitness的變化過(guò)程

如圖6所示，在仿真演示過(guò)程中，教師還可以通過(guò)鼠標(biāo)操作，方便的獲取每個(gè)粒子的當(dāng)前屬性值。

圖6 應(yīng)用問(wèn)題1中粒子的屬性值觀測(cè)窗口

通過(guò)此部分內(nèi)容演示，向?qū)W生展示了偏粒子群算法的計(jì)算過(guò)程，驗(yàn)證了算法的有效性。

(3)教學(xué)內(nèi)容2。在研究問(wèn)題1的仿真演示基礎(chǔ)上，重新構(gòu)造研究問(wèn)題2。重新通過(guò)偏粒子群算法進(jìn)行計(jì)算求解。

如圖7和圖8所示，偏粒子群算法能夠以較少的迭代步數(shù)達(dá)到全局最優(yōu)。這個(gè)結(jié)果進(jìn)一步驗(yàn)證了算法的有效性。

圖7 應(yīng)用問(wèn)題2的計(jì)算結(jié)果1的截圖

圖8 應(yīng)用問(wèn)題2的計(jì)算結(jié)果1的計(jì)算過(guò)程

但是，多次生成式(11)所示的應(yīng)用問(wèn)題2，偏粒子群算法仿真也顯示如下結(jié)果。

如圖9和圖10所示，粒子群很快收斂到非原點(diǎn)位置，即停留到一個(gè)局部最優(yōu)解。雖然該次優(yōu)解目標(biāo)函數(shù)值(=－0.011 2)非常接近真實(shí)最優(yōu)解，但是并非最優(yōu)解。

圖9 應(yīng)用問(wèn)題2的計(jì)算結(jié)果2的截圖

圖10 應(yīng)用問(wèn)題2的計(jì)算結(jié)果2的計(jì)算過(guò)程

此次計(jì)算雖然沒(méi)有能夠得到應(yīng)用問(wèn)題的最優(yōu)解。但是，這個(gè)結(jié)果解釋了智能優(yōu)化算法的另外一個(gè)重要特性:不像精確算法那樣，智能優(yōu)化算法并不能夠一定計(jì)算得到應(yīng)用問(wèn)題的最優(yōu)解，但是能夠得到應(yīng)用問(wèn)題的效率解。以圖10為例，算法在第5次迭代后就能夠得到次優(yōu)解。而圖5和圖8所示的最優(yōu)解計(jì)算需要進(jìn)行16次迭代。對(duì)于一個(gè)復(fù)雜問(wèn)題而言，如果能夠以1/3的計(jì)算時(shí)間得到一個(gè)工程應(yīng)用滿意的結(jié)果，這也是有效的算法。

(4)延伸內(nèi)容。結(jié)合當(dāng)前最主流的計(jì)算環(huán)境Python，向?qū)W生介紹偏粒子群算法在Python平臺(tái)上的軟件包 pyswarm(http://pythonhosted.org/pyswarm/#overview)。具體包括Python平臺(tái)下該軟件包的安裝，以及函數(shù)pso的參數(shù)設(shè)置和操作方法，講授該工具軟件的實(shí)用手冊(cè)。

(5)知識(shí)點(diǎn)考查。以一個(gè)一維變量的最優(yōu)化問(wèn)題maxG=100－x2(－10≤x≤10)為例，采用偏粒子群算法計(jì)算得到問(wèn)題的最優(yōu)解。

4 結(jié)語(yǔ)

本文以運(yùn)籌學(xué)課程為對(duì)象，介紹計(jì)算機(jī)仿真技術(shù)在課程教學(xué)中可視化展示的優(yōu)勢(shì)。并以運(yùn)籌學(xué)中一個(gè)相對(duì)較難的知識(shí)點(diǎn)-“智能優(yōu)化算法介紹”為例，介紹了仿真方法和仿真模型在教學(xué)實(shí)踐中的應(yīng)用。通過(guò)對(duì)偏粒子群算法的教學(xué)目標(biāo)、內(nèi)容等方面的描述，提出了計(jì)算機(jī)仿真在運(yùn)籌學(xué)課程教學(xué)中的應(yīng)用范式。