蟻群算法求解洛陽分院初中高教機(jī)、航班起飛順序的最優(yōu)解

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

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

1 群體智能簡(jiǎn)介

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

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

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

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

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

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

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

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

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

2.1 問題簡(jiǎn)述

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

2.2 模型建立

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

dij=■

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

引入決策變量：

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

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

minZ=■Xijdij

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

令：

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

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

m=■bi（t）

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

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

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

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

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

△？灼ij=■△？灼ijk

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

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

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

因?yàn)橐懻撁總€(gè)螞蟻選擇一個(gè)城市的概率，這里引入一個(gè)能見度的概念，用？濁ij來表示，則有：

？濁ij=■

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

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

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

2.3 模型解釋

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

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

3 洛陽機(jī)場(chǎng)飛機(jī)起順序問題的模型建立

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

3.1 模型描述

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

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

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

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

B737等重型民航客機(jī)。

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

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

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

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

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

最終所求問題就是：合理安排各個(gè)飛機(jī)的起飛順序，使總得起飛時(shí)間最小。

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

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

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

圖1 程序主界面

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

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

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

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

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

圖4

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

4 結(jié)束語

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

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

參考文獻(xiàn)

[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].長(zhǎng)沙：國防工業(yè)出版社，2011.

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

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