計算機仿真在運籌學優化算法教學中的應用
——以偏粒子群算法為例

李 鋒

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

0 引言

運籌學(operations research)的應用數學天性，要求工商管理學院的學生通過課程學習，能夠靈活地應用理論知識完成對實際問題的分析、建模和求解。在這個問題求解的規范流程中，分析和建模對學生的知識點掌握和靈活應用有著較高的要求，而問題求解則要求學生能夠熟練應用專業工具軟件實現二次編程、計算求解和參數分析。如果教師在教學或學生在學習過程中過于強調理論學習而忽視工具求解，勢必造成學生“至多”能夠建立應用問題的數學模型，但對如何解決問題一籌莫展。長此以往，勢必削弱學生解決實際問題的能力，最終影響課程所要求的教學目標和能力培養。

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

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

1 國內外研究現狀

運籌學課程特點，強調教學中理論聯系實際，因此該領域國內外專家都在探索除傳統數學建模和問題求解以外的其他各種形式的教學和教輔。本文主要以運營管理領域中最具盛名的運籌學和管理科學協會(Institute for Operations Research and the Management Sciences，INFORMS)對于運籌學教學、教改探索和實踐為標桿，論述當前相關課程學習中的先進理念和方法。

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

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

在該領域發展趨勢影響下，結合前期教學工作和教研項目積累，本文嘗試將計算機仿真技術引入到優化算法的教學開發中，幫助學生快速地掌握高級的優化算法原理計算步驟。下面給出了一個典型的智能優化算法-偏粒子群算法的計算機仿真描述和可視化教學。

2 優化算法中偏粒子群算法

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

2.1 偏粒子群算法的步驟

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

假定在給定的一個空間領域中，只有一個位置有食物。而在此空間中，一群鳥都在隨機的飛行，并在飛行的過程中不斷的交流對于食物位置的信息:當一只鳥更接近于食物時，它會將自己的位置廣播給其他所有鳥;而其他的鳥都將根據該位置信息調整自己的飛行方向和飛行速度，朝著這個位置飛去。最終，所有鳥都將聚集在食物所在的位置。

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

以一個二維變量的優化問題為例:

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

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

接著，計算粒子所處位置的目標函數，即適應度函數值。

此時，初始化粒子的當前個人最優解以及目標函數值為:

隨后，確定當前所有粒子中的最優目標函數值，以及相應的位置坐標:

算法的第2步為粒子的迭代搜索過程。具體來說，粒子將根據共享的群體最優解信息，以及自身當前狀態和速度調整自己的速度，并隨即更新自己的位置。具體來說，每個粒子將根據當前自己的速度(具有一定的慣性)，自己最優解的位置偏好和群體最優解的位置偏好計算飛行速度:

式中:velocityInertia定義了粒子的速度慣性;personalBestWeight為其對自己已知最優解的偏好權重，globalBestWeight為其對群體最優解的偏好權重。

在計算得到粒子的速度后，可以得到單位時間間隔之后位置為:

接著，根據式(3)重新計算粒子在新位置上的目標函數值。并在此基礎上，更新每個粒子的當前最優解和群體的最優解。

粒子群算法將重復第2步所示的計算，直到找到最優解。

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

以偏粒子群算法為代表的群體智能算法由于涉及多個獨立決策對象的決策過程，以及對象之間的信息交互，更加適合于與其有天然聯系的多智能體建模與仿真;實現其問題求解過程。

在多智能體建模方法下，每一個粒子都將被設置為一個獨立決策的智能體對象。它紀錄了自己的搜索軌跡和搜索結果，同時還不斷與其他粒子交換信息。具體來說，每個粒子的靜態屬性和動態行為方法如圖1所示。

在每個偏粒子群算法的迭代步驟中，每個“粒子”智能體的計算過程如圖2所示。

由圖2可見，偏粒子群算法中每個粒子的行為相對簡單，僅僅是根據群體最優解和自己的最優解進行應激式的調整。但是，通過粒子群之間關于群體最優解的信息交互，使得粒子群能夠實現復雜優化問題的計算求解。而這一點也正是群體智能算法的魅力所在。

3 偏粒子群算法的仿真課件開發

3.1 復雜優化問題實例

為了課堂演示偏粒子群算法的算法能力，在教學中考慮以下兩個問題。第1個問題為確定、連續性問題:

第2個問題在第1個問題基礎上，增加了隨機性因素ρ(服從標準0-1均勻分布)，即:

無論是第1個問題還是第2個問題，都可以得到相同的最優解和取值:

但是，相比于第1個問題，第2個問題存在若干個局部最小值，使得算法搜索起來更加吃力。

3.2 多智能體仿真的代碼開發

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

相比于Swarm、Repast等多智能體建模與仿真工具，Netlogo軟件平臺開發更加簡單和智能。以式(12)所示的第2個優化問題為例，其在Netlogo軟件平臺下，只需要如下一行代碼就可以實現。

為了增強問題求解空間的可視性，采用不同灰度來顯示不同位置的目標函數值/Fitness值。

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

圖3 Netlogo軟件平臺上的問題可行域空間

3.3 仿真課件的主要內容

在仿真程序開發的基礎上，設計智能優化算法課堂教學信息如下(2學時):

(1)教學目標。在工商管理學院的《運籌學》本科教學中，介紹常見用于解決復雜應用問題的智能優化算法。教學目的包括介紹具體智能優化算法的算法思路、計算步驟和結果解釋，以及介紹智能優化算法在運籌學應用領域的適用性。

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

如圖4(a)所示，在初始化階段，總共有10個粒子(紅色標示點)被隨機的放置在問題求解的二位空間上。在計算過程中，紅色的軌跡線不斷給出10個粒子在每次迭代(即仿真時鐘t+1)中的位置更新。最終，如圖4(i)所示，最終粒子匯集到了中心點，即搜索到應用問題1的最優解處，此時計算結束。

圖4 應用問題1的求解過程可視化(部分)

圖5給出了計算過程中，偏粒子群全局最優解的變化過程(式(5))。由圖5可見，全局最優解很快就收斂到應用問題最優解(原點，即目標函數為0)的位置。

圖5 應用問題1中GlobalBestFitness的變化過程

如圖6所示，在仿真演示過程中，教師還可以通過鼠標操作，方便的獲取每個粒子的當前屬性值。

圖6 應用問題1中粒子的屬性值觀測窗口

通過此部分內容演示，向學生展示了偏粒子群算法的計算過程，驗證了算法的有效性。

(3)教學內容2。在研究問題1的仿真演示基礎上，重新構造研究問題2。重新通過偏粒子群算法進行計算求解。

如圖7和圖8所示，偏粒子群算法能夠以較少的迭代步數達到全局最優。這個結果進一步驗證了算法的有效性。

圖7 應用問題2的計算結果1的截圖

圖8 應用問題2的計算結果1的計算過程

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

如圖9和圖10所示，粒子群很快收斂到非原點位置，即停留到一個局部最優解。雖然該次優解目標函數值(=－0.011 2)非常接近真實最優解，但是并非最優解。

圖9 應用問題2的計算結果2的截圖

圖10 應用問題2的計算結果2的計算過程

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

(4)延伸內容。結合當前最主流的計算環境Python，向學生介紹偏粒子群算法在Python平臺上的軟件包 pyswarm(http://pythonhosted.org/pyswarm/#overview)。具體包括Python平臺下該軟件包的安裝，以及函數pso的參數設置和操作方法，講授該工具軟件的實用手冊。

(5)知識點考查。以一個一維變量的最優化問題maxG=100－x2(－10≤x≤10)為例，采用偏粒子群算法計算得到問題的最優解。

4 結語

本文以運籌學課程為對象，介紹計算機仿真技術在課程教學中可視化展示的優勢。并以運籌學中一個相對較難的知識點-“智能優化算法介紹”為例，介紹了仿真方法和仿真模型在教學實踐中的應用。通過對偏粒子群算法的教學目標、內容等方面的描述，提出了計算機仿真在運籌學課程教學中的應用范式。