MMTD算法在蟻群算法中的應(yīng)用和研究?

朱俚治

（南京航空航天大學(xué)信息中心 南京 210016）

MMTD算法在蟻群算法中的應(yīng)用和研究?

朱俚治

（南京航空航天大學(xué)信息中心 南京 210016）

當(dāng)今的計(jì)算機(jī)專家和工程師們?yōu)榱颂岣邫C(jī)器的智能性，因此在各科的領(lǐng)域中開發(fā)出了眾多的智能算法，這些算法主要用于解決最優(yōu)解問題。蟻群算法是智能算法中的一種，該算法采用由個(gè)體的最優(yōu)解從而引導(dǎo)產(chǎn)生整體的最優(yōu)解。在蟻群算法中當(dāng)螞蟻尋找最短路徑的時(shí)候，利用信息素濃度的不同和揮發(fā)系數(shù)的不同強(qiáng)度為蟻群尋找最優(yōu)解提供了重要依據(jù)。論文根據(jù)已有的蟻群算法，提出了使用MMTD算法對(duì)蟻群信息素的揮發(fā)系數(shù)進(jìn)行衡量和計(jì)算，將MMTD算法在蟻群算法中進(jìn)行應(yīng)用是該文主要?jiǎng)?chuàng)新之處。

蟻群算法；MMTD；信息素；揮發(fā)系數(shù)；智能性

1 引言

群集智能作為一種新興的演化計(jì)算技術(shù)已引起了越來越多相關(guān)研究人員的關(guān)注［7～9］。蟻群算法是一種智能性的仿生物學(xué)算法，該算法最早由M.Dorigo學(xué)者提出，這以后蟻群算法逐步引了起人們的重視，人們將該算法在諸多領(lǐng)域中進(jìn)行了應(yīng)用。當(dāng)今的蟻群算法主要有以下幾個(gè)方面的應(yīng)用，經(jīng)典旅行商問題，二次分配的問題，車間任務(wù)調(diào)度問題等一系列方面的應(yīng)用［7～8］。蟻群算法除了在以上幾個(gè)方面應(yīng)用之外，還能夠在數(shù)據(jù)挖掘中的分類和聚類等方面進(jìn)行應(yīng)用。蟻群算法在這些領(lǐng)域方面的應(yīng)用都獲得了成功，其主要原因是螞蟻個(gè)體的對(duì)不同環(huán)境的具有適應(yīng)性以及螞蟻個(gè)體之間的協(xié)作性的特點(diǎn)，這些都是蟻群算法在各個(gè)科研領(lǐng)域獲得成功應(yīng)用的重要因素。本文根據(jù)蟻群算法的特點(diǎn)，將MMTD算法在螞蟻搜索最短路徑時(shí)候產(chǎn)生的信息素強(qiáng)度和信息素的揮發(fā)性上進(jìn)行衡量和應(yīng)用是本文的主要?jiǎng)?chuàng)新點(diǎn)。

2 蟻群算法的基本原理

2.1 蟻群算法的介紹

蟻群算法最初的目的是幫助人們?nèi)ダ斫馕浵佭@類物種的復(fù)雜行為。蟻群算法出現(xiàn)之后不久便引起了數(shù)學(xué)家，計(jì)算機(jī)專家和工程師們的注意，他們把超越生物本身的模型轉(zhuǎn)換成了一項(xiàng)有用的優(yōu)化和控制算法——蟻群算法，也稱為蟻群系統(tǒng)。在蟻算法中的個(gè)體具有以下的特性［5～7］：

1）蟻群的個(gè)體的行為極為簡(jiǎn)單，通過信息的傳遞個(gè)體之間的協(xié)作，能夠完成復(fù)雜的任務(wù)。

2）蟻群的個(gè)體具有一定記憶力，一定的智能性。

3）蟻群的個(gè)體能夠適應(yīng)周圍環(huán)境的變化，具有一定的適應(yīng)性。

當(dāng)蟻群尋找最短路徑的時(shí)候，在經(jīng)過的路徑上都會(huì)留下一種叫做信息素的物質(zhì)，這種物質(zhì)具有揮發(fā)性。蟻群的個(gè)體與個(gè)體之間能夠感知信息素的這種物質(zhì)，它們通過這種物質(zhì)的揮發(fā)性進(jìn)行信息傳遞和信息交流。尋找最短路徑的蟻群總是向著信息素濃度最強(qiáng)和最高的方向運(yùn)動(dòng)，信息濃度越高則這條路徑中聚集的螞蟻就越多，路徑中的螞蟻越多，越發(fā)增加該路徑的信息素強(qiáng)度，這樣又吸引了更多的螞蟻來到這條路徑之中，從而使得整個(gè)蟻群最終能夠發(fā)現(xiàn)蟻巢到食物之間的最短路徑。

2.2 蟻群的算法的簡(jiǎn)要分析

蟻群是一個(gè)種群，是一個(gè)群體，因此當(dāng)蟻群在尋找到達(dá)食物的最短路徑的時(shí)候并不是個(gè)體行為，而是一個(gè)群體的行為。蟻群算法初始的狀態(tài)是首先通過螞蟻的個(gè)體去尋找最短路徑，從而再使得整個(gè)蟻群都找到最優(yōu)解和最短路徑。在尋找最短路徑的時(shí)候，蟻群中的螞蟻個(gè)體在時(shí)間上并沒有先后，而是在同一個(gè)時(shí)間點(diǎn)內(nèi)可以有若干螞蟻同時(shí)尋找通往目的地的最短路徑。

當(dāng)蟻群尋找最短路徑的時(shí)候有兩個(gè)重要因素：1）螞蟻個(gè)體對(duì)環(huán)境變化的適應(yīng)性；2）螞蟻個(gè)體與個(gè)體之間相互交換信息，及螞蟻之間的協(xié)作性。在蟻群尋找最短路徑的時(shí)候，每一條路徑上都有一定數(shù)量的蟻群在活動(dòng)。螞蟻之間存在協(xié)作性、并行性和個(gè)體的適應(yīng)性等這些特點(diǎn)，能夠使得各條路徑中的蟻群通過信息素的傳遞從而使得整個(gè)蟻群都能夠找到到達(dá)目的地的最短路徑?；谏鲜鱿伻核惴ǖ奶攸c(diǎn)，蟻算法在尋找最短路徑的時(shí)候具有較高的效率，縮短了算法求解的時(shí)間。

3 蟻群的信息素以及信息素的揮發(fā)

3.1 蟻群的信息素

在蟻群出發(fā)之前路徑上的信息素濃度值均為0，當(dāng)蟻群開始搜索達(dá)到食物的最短路徑的時(shí)候就會(huì)在路徑上留下不同濃度的信息素，這些信息素中某些濃度會(huì)強(qiáng)些，而某些信息素的濃度則會(huì)弱些。由于各條路徑上信息素強(qiáng)度的不同，從而決定著蟻群在尋找食物時(shí)有不同的運(yùn)動(dòng)方向，但信息素濃度將隨著時(shí)間的變化而變化，信息素濃度的變?nèi)趸蜃儚?qiáng)能夠不斷地影響蟻群的活動(dòng)。

3.2 蟻群信息素的揮發(fā)性

在蟻群搜索最短路徑的過程中，整個(gè)蟻群都處于不斷的運(yùn)動(dòng)之中。如果某條路徑中的螞蟻數(shù)量較多，那么在該路徑中留下信息素濃度的較強(qiáng)，當(dāng)路徑中的螞蟻數(shù)量較少或十分少的時(shí)候則這時(shí)螞蟻在路徑上留下信息素濃度的較弱或十分的弱。信息素濃度的揮發(fā)和變化是蟻群在不同路徑活動(dòng)中產(chǎn)生的結(jié)果，信息素濃度不斷的變化將引導(dǎo)整個(gè)蟻群去尋找最短路徑，是蟻群尋找最短路徑的關(guān)鍵因素。

蟻群在路徑上留下的信息素具有揮發(fā)性，信息素的揮發(fā)性實(shí)現(xiàn)了蟻群之間信息的傳遞性和進(jìn)行蟻群之間的交流。信息素的揮發(fā)性是蟻群個(gè)體與個(gè)體之間的一種交流方式和交流手段，如果沒有信息素的揮發(fā)性，那么整個(gè)蟻群就缺少必要的信息交流工具。

在通往目的地的各條路徑中，如果某條路徑之中螞蟻數(shù)量越多，此時(shí)信息素濃度越強(qiáng)則信息素的揮發(fā)因子就越大，發(fā)揮因子越大那么該路徑中螞蟻的數(shù)量就會(huì)變多變大。如果某條路徑中螞蟻的數(shù)量在變少的過程中，那么該條路徑中的信息素濃度會(huì)逐步變?nèi)酰瑩]發(fā)因子也會(huì)相應(yīng)的變小，變?nèi)?。因此某條路徑中信息素的濃度變強(qiáng)或變?nèi)跏怯捎诼窂街械南伻簲?shù)量在發(fā)生變化，然而路徑中蟻群數(shù)量的變化往往又確定于信息素濃度和信息素?fù)]發(fā)因子的大小。

4 蟻群算法的計(jì)算公式及其分析

4.1 蟻群信息素的計(jì)算公式

m是螞蟻中的個(gè)數(shù)，n為迭代的次數(shù)，i為螞蟻所在的位置，j為螞蟻所能達(dá)到的位置，?為螞蟻可以到達(dá)位置的集合，ηij為啟發(fā)信息，這里為由i到 j的路徑的能見度。τij為路徑i到 j的路徑的信息素強(qiáng)度。?為螞蟻k由i到 j的路徑上留下的信息素?cái)?shù)量。α為路徑權(quán)，β為啟發(fā)性信息的權(quán)，ρ為路徑上信息素?cái)?shù)量的蒸發(fā)系數(shù)，Q信息素質(zhì)量系數(shù)［3～4］。

4.2 信息素計(jì)算公式的分析

每條路徑中的信息素濃度會(huì)隨著時(shí)間增強(qiáng)或減弱。信息素濃度最高最強(qiáng)的路徑往往是蟻群算法中選擇的路徑。

現(xiàn)在有N條路徑，在N條路徑中的信息素濃度各不相同。如果某條路徑上信息素濃度變強(qiáng)，則蟻群向這條路徑運(yùn)動(dòng)。當(dāng)有螞蟻向這條路徑運(yùn)動(dòng)，那么該路徑信息素的濃度會(huì)逐步變大變強(qiáng)的值會(huì)逐步變大，信息素的揮發(fā)性就會(huì)逐步增強(qiáng)，因此此時(shí)τij的值也將變大。如果某條路徑上信息素濃度在變?nèi)醯倪^程中，那么這條路徑蟻群中的數(shù)量將越來越少這時(shí)的值會(huì)逐步變小。由于該條路徑中的螞蟻數(shù)量在逐漸減少，那么τij的值也將逐步變小，那么這條路徑中的τij會(huì)逐步接近于0。

蟻群中的螞蟻在選擇路徑的時(shí)候，協(xié)作性體現(xiàn)在當(dāng)個(gè)別螞蟻個(gè)體在選擇了適當(dāng)路徑的時(shí)候，能夠通過蟻群信息素能夠使得螞蟻個(gè)體與個(gè)體進(jìn)行信息交流，使得別的螞蟻也能夠選擇相同的路徑，從而實(shí)現(xiàn)蟻群之間相互的協(xié)作性。在蟻群選擇路徑的過程中，使得信息素濃度τij值變大的路徑被選擇的幾率較大，相反的信息素濃度τij值變小變?nèi)醯穆窂奖贿x著幾率將十分的小，因此信息素的作用在蟻群的協(xié)作性方面起到了關(guān)鍵性的作用。

5 MMTD算法技術(shù)簡(jiǎn)介

5.1 中介真值程度度量知識(shí)簡(jiǎn)介

中介邏輯將事物的屬性描述成三種狀態(tài)，事物屬性的兩個(gè)對(duì)立面和對(duì)立面的中間過渡狀態(tài)。在中介真值程度度量方法中，提出了事物超態(tài)屬性概念，該方法符合中介思想事物的屬性并且被劃分為五種狀態(tài)：事物的兩個(gè)對(duì)立面，對(duì)立面的中間過渡狀態(tài)和事物超態(tài)對(duì)立面［1～2］。這里用符號(hào)表示為～P，P與╕P，超態(tài)+p與超態(tài)╕+p。現(xiàn)用數(shù)軸將以上的描述的概念表達(dá)如下［1～2］：

圖1 中介真值程度度量一維函數(shù)圖

對(duì)數(shù)軸 y=f(x)表示的含義有以下說明［1～2］：

數(shù)軸上用符號(hào)P與╕P分別表示事物對(duì)立面的兩個(gè)屬性，符號(hào)～P表示反對(duì)對(duì)立面的中間過渡狀態(tài)達(dá)事物的屬性。

1）如果數(shù)軸上數(shù)值點(diǎn)的位置逐步接近P，則事物A所具有P的屬性逐步增強(qiáng)。

2）如果該數(shù)值點(diǎn)的位置落在真值╕P和 P的取范圍之間，則事物A的屬性就部分地具有╕P的屬性，同時(shí)又部分地具有P的屬性。

3）如果數(shù)軸上數(shù)值點(diǎn)的位置逐步接近╕P，則事物A所具有╕P的屬性逐步增強(qiáng)。

5.2 中介真值程度度量中的距離比率函數(shù)

在中介真值程度度量的方法中，數(shù)軸上某數(shù)值點(diǎn)通過距離比率函數(shù)來計(jì)算事物所具有屬性的強(qiáng)弱。

定理1 給定 y=f(x)∈f(X)，ξ(h(y))=h(y)，則有［1～2］

1）當(dāng) αF+εF＜y＜αT-εT時(shí) ，gT(x)∈(0，1) ，gF(x)∈(0，1)。

2）當(dāng) y＞αT+εT時(shí)，gT(x)＞1；當(dāng) y＜αF-εF時(shí)，gF(x)＞1。

3）當(dāng) y＜αF-εF時(shí)，gT(x)＜0 ；當(dāng) y＞αT+εT時(shí)，gF(x)＜0。

4）gT(x)+gF(x)=1。

（1）相對(duì)于 P 的距離比率函數(shù)［1～2］

6 MMTD方法的應(yīng)用

6.1 關(guān)于蟻群信息素濃度公式的描述

函數(shù)：f(x)=所有目前最新的信息素強(qiáng)度-已知的最大信息素強(qiáng)度

τij表示信息素強(qiáng)度，t+1表示當(dāng)前時(shí)刻，t表示前一時(shí)刻。

τij(t+1)表示當(dāng)前時(shí)刻的信息素強(qiáng)度及所有最新的信息素強(qiáng)度，τij(t)表示前一時(shí)刻的信息素強(qiáng)度及已知的最大信息素強(qiáng)度。函數(shù)：

分析和討論：

1）τij(t+1)＞ τij(t)

當(dāng)τij(t+1)＞τij(t)的時(shí)候：如果當(dāng)前時(shí)刻的信息素強(qiáng)度τij(t+1)與前一個(gè)時(shí)刻的信息素強(qiáng)度τij(t)的差值越大，則信息素的強(qiáng)度在增強(qiáng)，并且這時(shí)路徑的信息素濃度會(huì)逐步變大變強(qiáng)。當(dāng)τij(t+1)在變大中，根據(jù)蟻群算法的特點(diǎn)可知蟻群總是向信息素濃度變大的路徑運(yùn)動(dòng)。當(dāng)該條路螞蟻的數(shù)量就越大，則某條路徑信息素的濃度越大，該條路徑被選擇作為最短路徑的可能性就越大。

2） τij(t+1)＜ τij(t)

當(dāng)τij(t+1)＜τij(t)的時(shí)候：如果當(dāng)前時(shí)刻的信息素強(qiáng)度τij(t+1)與前一個(gè)時(shí)刻的信息素強(qiáng)度τij(t)的差值越大，則信息素的強(qiáng)度在減弱，并且這時(shí)路徑的信息素濃度會(huì)逐步變小變?nèi)酢．?dāng)τij(t+1)也在變小中，根據(jù)蟻群算法的特點(diǎn)可知蟻群總是向信息素濃度變大的路徑運(yùn)動(dòng)，如果某條路徑蟻群產(chǎn)生的信息素濃度逐步的變小，該路徑被蟻群舍棄的可能性很大，該路徑不是蟻群尋找的最短路徑。

6.2 中介對(duì)信息素濃度的描述

以下用中介真值程度度量方法對(duì)蟻群產(chǎn)生的信息素濃度做以下的研究：

數(shù)軸 y=f(x)上有P，～P，╕P三個(gè)數(shù)據(jù)區(qū)域，P代表信息素濃度增強(qiáng)，╕P代表信息素濃度減弱，～P代表信息素濃度半強(qiáng)半弱。

6.3 距離比率函數(shù)

從數(shù)軸上 y=f(x)可以知道，在數(shù)軸上以～P為對(duì)稱中心，左右分別為╕P和P。

圖2 中介真值程度度量一維函數(shù)的應(yīng)用

y=f(x)的 值 落 在 三 個(gè) 值 域 范 圍（αr+εr，αl- εl），（αr-εr，αr+ εr）（αl- εl，αl+ εl）。 ～P 的區(qū)域 為（ αr+εr，αl-εl），╕P 的 區(qū) 域 為（αr-εr，αr+εr），P 的區(qū)域?yàn)椋é羖-εl，αl+εl）。 P 的真值為1，╕P的真值為0。

相對(duì)于P的距離比率函數(shù)

通過距離比率函數(shù)hT(x)對(duì)y值的計(jì)算，如果有：

1）若函數(shù) hT(x)=1，y值落在區(qū)域（αl-εl，αl+εl），則此時(shí)信息素強(qiáng)度增強(qiáng)，其真值為1。

2）若函數(shù) hT(x)=0，y值落在區(qū)域（αr-εr，αr+εr），則此時(shí)信息素強(qiáng)度減弱，其真值為0。

7 結(jié)語

蟻群算法是一種仿生物學(xué)的智能性算法，該算法主要解決的問題是尋找到達(dá)食物的最短路徑。蟻群算法的特點(diǎn)是從有個(gè)體的最優(yōu)解從而引導(dǎo)整個(gè)群體的最優(yōu)解，該算法有較廣泛的應(yīng)用性，在諸多領(lǐng)域有著廣泛的應(yīng)用。本文根據(jù)蟻群在尋找最短路徑時(shí)候螞蟻具有的適應(yīng)性和協(xié)作性的特點(diǎn)，提出了將具有模糊思想的MMTD算法在蟻群尋找最短路徑中進(jìn)行首次應(yīng)用。將MMTD算法在蟻群算法中進(jìn)行應(yīng)用是本文的主要?jiǎng)?chuàng)新點(diǎn)，這也是將具有模糊思想算法在蟻群算法中的應(yīng)用嘗試。

［1］洪龍，肖奚安，朱梧槚.中介真值程度的度量及其應(yīng)用（I）［J］.計(jì)算機(jī)學(xué)報(bào)，2006（12）：2186-2193.HONG Long，XIAO Xian，ZHU Wujia.Measure of Medi?um Truth Scale and Its Application（I）［J］.Chinese Jour?nal of computers，2006（12）：2186-2193.

［2］朱梧槚，肖奚安.數(shù)學(xué)基礎(chǔ)與模糊數(shù)學(xué)基礎(chǔ)［J］.自然雜志，1984（10）：723-726，800.ZHU Wujia，XIAO Xian.Foundations of Classical Mathe?matics and Fuzzy Mathematics［J］.Nature Magazine，1984（10）：723-726，800.

［3］吳慶洪，張穎，馬宗民.蟻群算法綜述［J］.微型計(jì)算機(jī)信息，2011，27（3）：1-5.WU Qinghong，ZHANG Ying，MA Zongmin.An overview of the ant colony algorithm［J］.Micro computer informa?tion，2011，27（3）：1-5.

［4］胡小兵，袁銳，黃席樾，等.蟻群算法原理的仿真研究［J］.計(jì)算機(jī)仿真，2004，21（8）：125-127.HU Xiaobing，YUAN Rui，HUANG Yuexi，et al.Research simulation of ant colony algorithm principle［J］.Computer Simulation，2004，21（8）：125-127.

［5］程艷燕.蟻群算法基本原理及其應(yīng)用綜述［J］.科技創(chuàng)業(yè)月刊，2011（4）：117-120.CHENG Yanyan.Basic principle of ant colony algorithm and its application in［J］.Science and technology entre?preneurship monthly，2011（4）：117-120.

［6］李開榮，陳宏建，陳崚.一種動(dòng)態(tài)自適應(yīng)蟻群算法［J］.計(jì)算機(jī)工程與應(yīng)用，2004（29）：149-152.LI Kairong，CHEN Hongjian，CHEN Ling.A dynamic adaptive ant colony algorithm［J］.Computer Engineering and Applications，2004（29）：149-152.

［7］黃摯雄，張登科，黎群輝.蟻群算法及其改進(jìn)形式綜述［J］.計(jì)算技術(shù)與自動(dòng)化，2006，25（3）：35-38.HUANG Zhiqiong，ZHANG Dengke，LI Qunfai.Ant colo?ny algorithm and its improved form review［J］.Journal of computing and automation，2006，25（3）：35-38.

［8］馮寶華.蟻群優(yōu)化算法的原理改進(jìn)［J］.計(jì)算機(jī)與信息技術(shù)，2007（31）：94-96.FENG Baohua.Principle ACO Improvement［J］.Computer and Information Technology，2007（31）：94-96.

［9］馮月華，陳州吉.基于群體智能的蟻群算法原理及應(yīng)用研究［J］.蘭州文理學(xué)院學(xué)報(bào)（自然科學(xué)版），2014，28（2）：58-62.FENG Yuehua，CHEN Zhoujie.The principle and applica?tion of ant colony algorithm based on swarm intelligence research［J］.Journal of lan zhou journals of liberal arts college（natural science edition），2014，28（2）：58-62.

［10］朱樹人，匡芳君，王艷華.基于粒度原理的蟻群聚類算法［J］.計(jì)算機(jī)工程，2005，31（23）：162-166.ZHU Shuren，KUANG Fangjun，WANG Yanhua.granu?larity based on ant colony clustering algorithm principle［J］.Computer Engineering，2005，31（23）：162-166.

［11］劉士新，宋建海，唐加福.蟻群最優(yōu)化-模型算法及應(yīng)用綜述［J］.系統(tǒng)工程學(xué)報(bào)，2004，19（5）：496-502.LIU Shixin，SONG Jianhai，TANG Jiafu.ant colony opti?mization-model algorithm and application of a overview［J］.Journal of Systems Engineering，2004，19（5）：496-502.

Application and Research of MMTD Algorithm in Ant Colony Algorithm

ZHU Lizhi
（Information Center，Nanjing University of Aeronautics&Amp，Astronautics，Nanjing 210016）

Nowadays，computer experts and engineers in order to improve the intelligence of the machine，so in the field of subjects developed many intelligent algorithm.The algorithm is mainly used for the optimal solution to solve the problem.Ant colony algorithm is a kind of intelligent algorithm，which uses the optimal solution of the individual to guide the overall optimal solution.In ant colony algorithm，when the ants find the shortest path，it is important to find the optimal solution with different intensity of pher?omone concentration and volatile coefficient.Based on the existing ant colony algorithm，this paper proposes the use of MMTD algo?rithm to measure and calculate the evaporation coefficient of ant pheromone，and the application of MMTD algorithm in ant colony algorithm is the main innovation of this paper.

ant colony algorithm，MMTD，pheromone，volatile coefficient，intelligence

Class Number TP301

TP301

10.3969/j.issn.1672-9722.2017.12.006

2017年6月6日，

2017年7月27日

朱俚治，男，工程師，研究方向：網(wǎng)絡(luò)安全，計(jì)算機(jī)算法和技術(shù)。