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

關(guān)鍵詞：蟻群算法；數(shù)學(xué)建模；最優(yōu)解

1 群體智能簡介

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

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

2 蟻群算法的數(shù)學(xué)模型

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

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

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

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

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

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

2.1 問題簡述

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

2.2 模型建立

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

dij=■

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

引入決策變量：

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

則目標(biāo)函數(shù)可以表示為：

minZ=■Xijdij

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

令：

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

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

m=■bi（t）

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

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

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

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

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

△？灼ij=■△？灼ijk

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

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

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

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

？濁ij=■

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

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

這樣就構(gòu)建好了蟻群算法的基本模型。

2.3 模型解釋

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

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

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

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

3.1 模型描述

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

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

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

3號區(qū)域：航站樓北側(cè)，有廊橋的區(qū)域，主要用于停放A320，

B737等重型民航客機。

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

標(biāo)準(zhǔn)模型下的幾點說明：（1）為了考慮軟件的通用性，任

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

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

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

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

3.2 程序設(shè)計解決實際模型

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

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

圖1 程序主界面

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

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

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

圖3 起飛間隔設(shè)置

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

圖4

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

4 結(jié)束語

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

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

參考文獻

[1]李麗香，彭海朋，楊義先.混沌蟻群算法及應(yīng)用[M].中國科學(xué)技術(shù)出版社，2003.

[2]李士勇.蟻群算法及其應(yīng)用[M].哈爾濱：哈爾濱工業(yè)大學(xué)出版社，2004.

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

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

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

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

[8]司守奎.數(shù)學(xué)建模與應(yīng)用[M].長沙：國防工業(yè)出版社，2011.

[9]韓中庚.數(shù)學(xué)建模方法與應(yīng)用[M].高等教育出版社，2009.

[10]林道榮，秦志林.數(shù)學(xué)實驗與數(shù)學(xué)建模[M].科學(xué)出版社，2011.