蟻群算法求解洛陽分院初中高教機、航班起飛順序的最優解

摘 要：隨著洛陽機場的擴建，洛陽市欲打造空港產業聚集地，必然會造成航班量的提升。此外中國民航飛行學院洛陽分院飛行訓練任務的加劇，也極大地考驗洛陽北郊機場負荷極限。不同的飛機，初中高教機以及空客、波音的民航客機對起飛、進場時間，在跑道上滑行的時間等都有不同的時限要求。通過優化的算法，合理安排不同飛機的起飛順序，一方面可以極大地增加機場的負荷量，另一方面也可以節約運營的時間成本，對于機場交通管制擁有積極的意義。研究在單一變量下最優解問題的相關模型和方法有很多，但是，在多種變量作用下求解最優解問題卻較難找到合適的相關模型，蟻群算法就為解決在復雜變量環境下最優解問題而生的，其靈感來源于螞蟻在尋找食物的過程中發現路徑的行為。蟻群算法是一種模擬進化算法，該算法具有許多優良的性質。文章的目的在于收集洛陽分院初中高教機以及空客波音相關機型的起落要求的數據，抽象出有效的數學模型，用數學建模的思想來管理數據，并通過蟻群算法，探究初中高教機及航班飛機起飛順序的最優解。

關鍵詞：蟻群算法；數學建模；最優解

1 群體智能簡介

蟻群算法，英文名稱：Ant Colony Optimization，（ACO），在有些文獻中亦稱為螞蟻算法，由DORIGO博士從觀察螞蟻尋找食物的過程中逐步發現路徑的行為而獲得靈感。蟻群算法的本質是一種模擬進化算法，具有很多優良的性質，根據數值仿真實驗，蟻群算法具有現實的有效性和很高的應用價值，但在熟悉蟻群算法和對蟻群建立理想模型之前，應該首先討論群體智能的相關概念。

由于螞蟻是一種社會化協作的昆蟲，螞蟻群體是由許多能力單一而且有限的單一螞蟻組成的群體，但是螞蟻的每個個體又可以通過彼此間簡單的合作，完成一個較為復雜的整體性的工作，在混沌理論里，將螞蟻種群的這種能力稱為“群體智能”。和螞蟻群體類似，蜂群的單個個體智能水平亦不高，同樣沒有統一的指揮，但是蜂群卻可以建起巨大的蜂巢、運送食物、繁殖后代，因為蜂群和蟻群一樣，都是一種擁有完備結構和社會組織的分布式系統。由于群體組織的原因，依靠單個個體，無法完成任何復雜的工作，若依靠整個群體的力量，螞蟻可以完成非常復雜的任務。

2 蟻群算法的數學模型

雖然蟻群算法有著智能化、自組織性等諸多優點，但也存在搜索時間過長、易于停滯的問題，為了克服經典算法的這些缺點，很多國家和地區的學者提出了不少改進算法。

1996年L.M.Gambardella和M.Dorigo又提出了一種修正算法，他們稱之為螞蟻種群系統算法[5]ACS，并且將AS算法和ACS算法定義為螞蟻種群優化算法ACO。

1997年T.Stitzle提出了改進的最大最小螞蟻系統MMAS算法[6]。

1999年，我國學者吳慶洪提出了具有變異特性的蟻群算法[7]。

1999年，意大利學者F.Abbattista等提出了和遺傳算法相結合的算法[8]。

由于文章討論洛陽機場的飛機起降順序問題，數據量較小，問題并不復雜，所以在算法的選擇上以M.Dorigo的經典蟻群優化算法為主，下面就以基于蟻群的螞蟻系統的算法數學模型為例，介紹經典蟻群優化算法的數學模型和優化思路，下面求解著名的n個城市的旅行商問題為例來說明經典蟻群算法模型。

2.1 問題簡述

給定n個城市以及各城市間的距離，旅行商問題可以描述為求一條經過各城市一次且僅一次的最短路線問題。

2.2 模型建立

對n個城市建立理想平面坐標系，城市i的坐標為（xi，yi），城市j的坐標為（xj，yj），設dij為城市i與j之間的歐拉距離，則：

dij=■

其圖論描述為：給定圖G=（N，E），其中N為城市集合，E為城市之間相互連接組成的邊的集合，已知城市間鏈接距離，要求確定一條長度最短的回路。即走完所有城市一次且僅一次的最短回路，此問題可以描述為：“適當選擇圖上所有頂點的一個排列以組成最短路徑”

引入決策變量：

Xij=1（訪問i后訪問j）0（其他情況）

則目標函數可以表示為：

minZ=■Xijdij

將最短距離的尋找交給蟻群來解決：

令：

bi（t），（i=1，2，…，n）

為在時間t在城市i的螞蟻的數目，令：

m=■bi（t）

為螞蟻的總數，且每個螞蟻都是有如下特征的簡單智能體：

（1）它會根據某種概率選擇走哪一個城市，這個概率是城市距離和同他連接路徑的信息素的數量的函數。（2）為了使得螞蟻能夠完全合理的旅行，必須禁止螞蟻旅行訪問過的城市，這個可以通過一個緊急表格來實現。（3）當螞蟻完成了一次旅行，它就在走過的每個路徑上（i，j）釋放適量的信息素。

令？灼ij（t）是時間t路徑上（i，j）上的信息素強度。每個螞蟻在時間t時刻選擇下一個時間t+1要到達的城市，在時間間隔（t，t+1）內，對m個螞蟻，調用螞蟻系統迭代算法一次，算法的n次迭代叫做一圈，每一只螞蟻完成了遍歷所有城市一遍的一次旅行。在每只螞蟻k構造出一個完整閉合路徑并計算了相應長度之后（用Lk表示），路徑上的信息素強度會根據以下公式得到更新：

？灼ij（t+n）=？籽×？灼ij（t）+△？灼ij

其中？籽（0？燮？籽？燮1）是一個常數，它表示信息素揮發后的剩余度，即螞蟻爬行軌跡的持久性，1-？漬表示在時間t和時間t+n內信息素的揮發，并且在上述公式里面有：

△？灼ij=■△？灼ijk

？灼ij（t）表示路徑（i，j）在t時刻的信息素軌跡強度，△？灼ijk表示螞蟻在時間間隔（t，t+n）內路徑（i，j）上留下來的單位長度的路徑信息素數量，其具體公式為：

其中Q是個常數，且Lk表示沒一個螞蟻k旅行過的路徑總長度。

為了確保每一只螞蟻訪問每一個節點一次，并且避免重復，沒一個螞蟻都已一個禁忌表forbidk，用來存儲螞蟻當前訪問過的城市（節點），用禁忌表使螞蟻到這些城市的轉移概率為0，用計算機語言來講，就是禁止“螞蟻”訪問這些節點。當一次旅行完成之后，用禁忌表來計算問題現在的點。然后清空禁忌表，螞蟻就可以重新自由的選擇新的路徑了。forbidk（S）表示禁忌表中第s個元素，表示在現在的一次旅行中k個螞蟻訪問的第s個城市。

因為要討論每個螞蟻選擇一個城市的概率，這里引入一個能見度的概念，用？濁ij來表示，則有：

？濁ij=■

表示路徑（i，j）的能見度，對于每一個螞蟻k來說，從城市i到城市j的額轉移概率為：

在上式中allowedk={N-forbidk}，α和β是控制路徑能見度相對重要性的參數，若（i，j）之間的距離比較短，則？濁ij較大，pij也較大。也就是說，距離較近的城市以較大的概率被選擇。

這樣就構建好了蟻群算法的基本模型。

2.3 模型解釋

下面文章以計算機編程的思想表述蟻群算法的基本模型，整個系統在0時刻進行初始化過程，給每一條邊（i，j）設定一個初始信息素強度值？灼ij（0）。每一只螞蟻的forbidk的第一個元素為這個螞蟻出發的城市，即它的初始城市。每一只螞蟻從城市i移動到城市j，螞蟻會根據兩個城市之間的概率函數選擇移動城市，在城市從i到j移動的概率即為p■■■■（t）。此時有兩個原則需要注意：（1）信息素強度：表征過去有多少螞蟻選擇了這條路徑（i，j）；（2）能見度函數：說明了越近的城市，被訪問的期望值就越大。

顯然在p■■（t）函數中，如果α=0，就不在考慮路徑上的信息素的作用，因為（？灼ij（t））α=1為定常數，這樣模型就簡化稱為一個具有多起點的隨機貪心搜索算法。在n次循環以后，所有的螞蟻都對所有的路徑完成了一次遍歷，所以每一只螞蟻的forbidk就會滿。在此時就可以計算每一個螞蟻k旅行過的路徑總長度Lk，△？灼ijk也會隨著信息素強度的更新方程而更新。與此同時，由螞蟻找到最短路徑（即minkLk，k=1，2，3，…m）將被系統保存，所有禁忌表將被清空。重復這一過程，直到周游計數器達到最大NcMax或者所有螞蟻都走同一條路線。

3 洛陽機場飛機起順序問題的模型建立

洛陽機場飛機起降環境比較復雜，機型眾多，就目前的起飛情況來看，主要有SR20機型，PA-44機型，MA600機型，和航班的A320機型，以及少量B737機型，如果想建立數學模型，則必須將一些問題簡單化、抽象化、理想化。模型的建立對實際的運營情況具有現實的指導意義。

3.1 模型描述

洛陽機場停機坪目前共分為三塊區域：為了便于表述，本論文給三塊區域分別編號：

1號區域：C、D、E號機庫門口，主要用于停放SR20，可以用于停放PA-44但幾率很少。

2號區域：A、B號機庫門口至二號道口北側停機坪，主要用于停放SR20、PA-44和MA600。

3號區域：航站樓北側，有廊橋的區域，主要用于停放A320，

B737等重型民航客機。

標準模型下有如下假設：（1）所有停放在機坪上的飛機分布合理，即任何一架飛機劃出進入跑道都是順暢的、無阻礙的，都不會受其他飛機位置的影響。（2）每一架飛機無論是小型飛機還是中大型飛機，從飛機開始滑行至滑行到跑道端頭，所花的時間t相同。即影響起飛效率的單一變量就是起飛間隔。（3）理想化起飛，飛機起飛不受環境因素限制。

標準模型下的幾點說明：（1）為了考慮軟件的通用性，任

何區域所停放的飛機種類可以自定義；（2）不同類型飛機的起飛間隔可以自定義；（3）涉及蟻群算法的各種常用參數可以自定義。

有以上說明后，模型可以表述如下：

假設洛陽機場1號區域停放了a1架SR20，b1架PA-44，c1架MA600/A320/B-737（可根據實際情況令相應種類的飛機數量為0）；2號區域停放了a2架SR20，b2架PA-44，c2架MA600/A320/B-737；3號區域停放了a3架SR20，b3架PA-44，c3架MA600/A320/B-737。不同種類飛機的起飛受飛機種類的限制，這個數值一般和飛機的起飛重量，體積等參數有關，例如，SR20屬于輕型飛機，一架SR20起飛以后，緊接著讓一架SR20飛機起飛，則前后兩種都屬于輕型飛機，他們之間的起飛間隔應該為t1，如果前面是一架SR20，后面是一架中型的PA-44，則起飛時間間隔為t2…t9，則一共有如表1的幾種排列組合。

最終所求問題就是：合理安排各個飛機的起飛順序，使總得起飛時間最小。

3.2 程序設計解決實際模型

考慮程序的通用性，本設計將很多涉及蟻群算法的常數參數可以進行自定義，在實際運算過程中，這些參數是可以通過實驗來測算的，在使用本軟件的時候只要將不同機場的測算結果進行填入本軟件，既可以計算相應的排序結果，所以本軟件在設計之初就考慮了軟件的通用性。

洛陽機場一共有三個停機位，暫定名為1號，2號，3號停機位，原則上，1號機位只能用來停SR20，2號機位可以停SR20，PA-44，MA600，3號機位只能停A320，B737，為了增加軟件的通用性，本設計可以任意自定義每種機型的數目，如果不能停的機型，就可以將其的數量設置為0。此外，為了讓本軟件可以有廣泛的應用，本設計設置了7個停機坪號，以應付中國絕大多數機場的應用場景，同樣，用不到的機坪，可以直接在飛機數目框中填0。軟件設計圖如圖1所示。

圖1 程序主界面

由前面的論述我們可知，蟻群算法在實際應用過程中要確定五個常數參數他們分別是：α，β，ρ，Q和NcMax，根據前面的理論概述，我們可以得到每個常數參數所代表的含義：（1）α和β控制路徑和能見度相對重要性的參數，如果要計算具體環境走完路徑的真實值，α和β應由實驗測得，在本軟件中，如果只做定性排序，則只要α和β大于1即可。（2）ρ表示信息素揮發后的剩余度，且0≤ρ≤1），在真實環境中同樣由實驗測得，定性分析不影響排序結果。（3）Q為常數，它可以決定每段路徑的信息素總量，亦表征螞蟻個體散播信息素的能力，只要Q設定為普通自然數，不影響排序結果。（4）NcMax在本軟件中表示循環次數，NcMax越大，列出的可能性越多，則最短時間越接近真實最短時間。當NcMax≤A■■，繼續增大NcMax就不再有意義，因此如果想得到真實的最短時間，應該讓NcMax≥A■■。

點擊主界面的“參數”按鈕，就可以進行算法設置本。設計的參數輸入框如圖2所示。

表1所討論的起飛間隔參數，在主界面的“間隔”按鈕下進行設置，其截面如圖3所示。

圖3 起飛間隔設置

將參數設置好以后，點擊“排序”按鈕就可以計算出，最優的起飛順序，并且給出起飛時間，圖4為排序結果的事例。

圖4

針對以上排序結果，做如下解釋：L代表輕型飛機，1代表1號停機坪，A代表此停機坪的第一架飛機，B代表第二架，一次類推，則排序結果如上述所示。

4 結束語

通過多方的建模驗證，本程序可以很好地解決航班起飛順序排序最優解問題，當然，通過和空管部門有關同志的交流得知，實際安排飛機起飛順序和多方面因素有關系，不能一味追求最短時間。因此本程序只是用創新的方法解決一個工程問題，只作為純技術應用的討論，或作為洛陽機場空管部門安排飛機起飛順序的參考，并不作為安排起飛順序的指導程序。

另外，由于軟件在設計之初就考慮了軟件的通用性，因此，本軟件并不僅僅局限于給航班起飛順序排序，理論上，本軟件適用于解決多種有時間間隔要求的排序最優解問題。

參考文獻

[1]李麗香，彭海朋，楊義先.混沌蟻群算法及應用[M].中國科學技術出版社，2003.

[2]李士勇.蟻群算法及其應用[M].哈爾濱：哈爾濱工業大學出版社，2004.

[3]吳啟迪，汪鐳.智能蟻群算法及應用[M].上海：上海科技出版社，2002.

[4]馬良，朱剛.蟻群優化算法[M].科技出版社，2008.

[5]段海濱.蟻群算法原理及其應用[M].北京：科學出版社，2005.

[6]劉浩.MATLAB R2012a完全自學一本通[M].電子工業出版社，2013.

[8]司守奎.數學建模與應用[M].長沙：國防工業出版社，2011.

[9]韓中庚.數學建模方法與應用[M].高等教育出版社，2009.

[10]林道榮，秦志林.數學實驗與數學建模[M].科學出版社，2011.