數學建模之智慧型計算（2）
1、 從真實螞蟻到人工螞蟻
蟻群演算法是一種受自然界生物的行為啟發而產生的「自然」演算法。它是從對蟻群行為的研究中產生的。其基本原理如下圖：
圖1 蟻群覓食路線
上圖表示螞蟻覓食的線路，為蟻穴 , 為食源，從到有兩條線路可走，是長路徑，是短路徑。螞蟻走過一條路線以後，在地面上會留下資訊素氣味，後來螞蟻就是根據留在地面上這種氣味的強度選擇移動的方向。圖表示起始情況，假定蟻穴中有只螞蟻，分別用表示，ｂ為食源。
開始時蟻穴中螞蟻向食源移動，由於路線和上均沒有螞蟻通過，在這兩條路線上都沒有資訊素氣味，因此螞蟻選擇這兩條線路的機會均等。令蟻選擇線路，蟻選擇線路，假定螞蟻移動的速度相同，當蟻到達食源時，蟻還在途中，如圖。蟻到達食源以後就返回，這時從返回也有兩條線路選擇，哪一條線路上資訊素的氣味重就選擇哪一條。
因為蟻還在途中，沒有到達終點，這時**路上靠近端處，蟻還沒有留下資訊素氣味，所以蟻返回蟻穴的線路只有乙個選擇，就是由原路返回。當蟻返回時，蟻開始出發，蟻的線路選擇必定是，因為這時上氣味濃度比上重 (上已有螞蟻兩次通過 ) ，如圖所示。當蟻到達食源時 ,蟻返回線路必然選擇，如圖所示。
如此繼續下去 ，沿線路上移動的螞蟻越來越多，這就是巢穴到食源的最短路線，螞蟻根據線路上留下資訊素濃度的大小，確定在路線上移動的方向，蟻群向資訊素濃度重的線路集聚的現象稱為正反饋。螞蟻演算法正是基於正反饋原理的啟發式演算法。
蟻群覓食過程中的簡單規則
每只螞蟻並不是像我們想象的需要知道整個世界的資訊，他們其實只關心很小範圍內的眼前資訊，而且根據這些區域性資訊利用幾條簡單的規則進行決策，這樣，在蟻群這個集體裡，複雜性的行為就會凸現出來。這就是人工生命、複雜性科學解釋的規律！那麼，這些簡單規則是什麼呢？
下面詳細說明：
1、範圍：
螞蟻觀察到的範圍是乙個方格世界，螞蟻有乙個引數為速度半徑（一般是3），那麼它能觀察到的範圍就是3*3個方格世界，並且能移動的距離也在這個範圍之內。
2、環境：
螞蟻所在的環境是乙個虛擬的世界，其中有障礙物，有別的螞蟻，還有資訊素，資訊素有兩種，一種是找到食物的螞蟻灑下的食物資訊素，一種是找到窩的螞蟻灑下的窩的資訊素。每個螞蟻都僅僅能感知它範圍內的環境資訊。環境以一定的速率讓資訊素消失。
3、覓食規則：
在每只螞蟻能感知的範圍內尋找是否有食物，如果有就直接過去。否則看是否有資訊素，並且比較在能感知的範圍內哪一點的資訊素最多，這樣，它就朝資訊素多的地方走，並且每只螞蟻多會以小概率犯錯誤，從而並不是往資訊素最多的點移動。螞蟻找窩的規則和上面一樣，只不過它對窩的資訊素做出反應，而對食物資訊素沒反應。
4、移動規則：
每只螞蟻都朝向資訊素最多的方向移，並且，當周圍沒有資訊素指引的時候，螞蟻會按照自己原來運動的方向慣性的運動下去，並且，在運動的方向有乙個隨機的小的擾動。為了防止螞蟻原地轉圈，它會記住最近剛走過了哪些點，如果發現要走的下一點已經在最近走過了，它就會盡量避開。
5、避障規則：
如果螞蟻要移動的方向有障礙物擋住，它會隨機的選擇另乙個方向，並且有資訊素指引的話，它會按照覓食的規則行為。
7、播撒資訊素規則：
每只螞蟻在剛找到食物或者窩的時候撒發的資訊素最多，並隨著它走遠的距離，播撒的資訊素越來越少。
根據這幾條規則，螞蟻之間並沒有直接的關係，但是每只螞蟻都和環境發生互動，而通過資訊素這個紐帶，實際上把各個螞蟻之間關聯起來了。比如，當乙隻螞蟻找到了食物，它並沒有直接告訴其它螞蟻這兒有食物，而是向環境播撒資訊素，當其它的螞蟻經過它附近的時候，就會感覺到資訊素的存在，進而根據資訊素的指引找到了食物。
蟻群演算法(ant colony optimization, aco)，又稱螞蟻演算法，是一種用來在圖中尋找優化路徑的機率型演算法。它由marco dorigo於2023年在他的博士**中提出，其靈感**於上述所描述的螞蟻在尋找食物過程中發現路徑的行為。其中「資訊素」在蟻群演算法中期到非常重要的啟示作用。
[1] colorni a, dorigo m, maniezzo v, etal. distributed optimization by ant colonies . proceedings of the 1st european conference on artifical life, 1991,134-142
[2] dorigo m. optimzation,learning and natural department of electronics, politenico dimilano,italy,1992
在蟻群演算法中，需要定義人工螞蟻的概念，人工螞蟻具有雙重特性，首先，它們是真實馬一行維特徵的一種抽象，通過對真實螞蟻行為的觀察，將蟻群行為中的智慧型化因素賦予人工螞蟻；另一方面，為了解決實際問題，人工螞蟻必須具備真實螞蟻一些所不具備的特性。歸納起來看，它與真實螞蟻之間主要存在下列異同
二、人工蟻與真實蟻的共同特徵比較
1、 人工蟻與真實蟻一樣，都是乙個需要合作的群體
問題的解決需要通過人工蟻的合作來完成，人工蟻群通過相
互協調與合作從而有可能找到全域性最優方案，而每只人工蟻的單獨行動只可能找到區域性最優解
2、 人工蟻和真實蟻一樣，都要完成乙個共同的任務
人工蟻與真實蟻一樣，都要完成乙個共同的任務，即需尋找
乙個從源節點（巢穴）到目的節點（食物源）之間的最短路經（或最小代價），人工螞蟻與真實螞蟻一樣都不能跳躍，必須在相鄰節點之間移動，直至遍歷所有可能路徑，為了減少計算複雜度並尋找出最短路徑，需要記錄當前路徑
3、 人工蟻與真實蟻一樣都通過使用資訊素進行間接通訊
人工蟻與真實蟻一樣都存在一種改變當前所處環境的機制：
真實螞蟻在經過的路徑上留下資訊素，人工蟻則不斷修改更新在其所經過的路徑上儲存的資訊，是一種模擬自然界中的資訊素軌跡更新的過程
4、 人工蟻利用真實蟻覓食行為中的自催化機制—正反饋
當一些路徑上通過的螞蟻越來越多時，路徑上留下的資訊素
軌跡也越來越多，使得資訊素強度變大，根據螞蟻清傾向於選擇資訊強度大的特點，後來的螞蟻選擇該路經的概率也越高，從而增加了該路經的資訊素強度，這稱之為自催化過程
自催化機制利用資訊素作為反饋，通過對系統演化過程中較優解的增強作用，使得問題的解向著全域性最優的方向逐步接近
5、 資訊素的揮發機制
在蟻群演算法中設定一種揮發機制，類似於真實資訊素的揮發，
這種機制需要螞蟻忘記過去，不受過去經驗的過分約束，有利於指引螞蟻朝著新的方向搜尋，避免早熟收斂
6、 利用當前資訊進行路徑選擇的隨機選擇策略
人工蟻於真實蟻都是利用概率選擇策略實現乙個節點到相
鄰節點的移動，選擇策略只利用當前的資訊去**未來的情況，而不能利用未來的資訊，因此，人工蟻與真實蟻所使用的選擇策略在時間和空間上都具有區域性特性
人工蟻具備一些真實蟻所不具備的特徵，主要體現在下列五個方面
1、 人工蟻存在於離散空間中，它們的移動實質上是有乙個離散狀態到另乙個離散狀態的轉移；
2、 人工蟻具有乙個記錄其過去自身行為的內在狀態；
3、 人工蟻存在於與時間無關聯的環境之中
4、 人工蟻並非完全盲從，它受到問題特徵的啟發，例如，
有的問題中人工螞蟻產生乙個解後改變資訊量，而在有的問題中人工螞蟻每做一次選擇便改變資訊量
5、為了提公升人工蟻系統的效能，改進演算法效率，人工蟻可增加一些效能，如**未來、區域性優化、回溯等。在很多具體應用中，人工蟻可以在區域性優化的過程中交換資訊以及實行簡單**等。
三、基本蟻群演算法模型的建立
1、螞蟻個體的抽象
抽象出能夠為建立模型起作用的真實蟻群的機理，摒棄與建立模型演算法無關的因素.
2023年數學建模總結
隨著2014年全國大學生數學建模競賽落下帷幕，回顧這一年來點點滴滴的準備和奮鬥，校數模組感慨頗多。在這一年的時間內，學校領導對數學建模競賽給予了高度的重視，在教務處的直接領導下，理學院相關老師對此進行了全校動員 競賽選拔 暑期培訓等相關工作。現在把近一年的數學建模工作總結如下 數學建模對我們來說並不...
2023年數學建模競賽
2010年數學建模第一次模擬競賽試題 a題 網路流量和容量的規劃 計算機通訊網路是由路由器和交換機及它們之間的通訊鏈路組成。每條鏈路上有各自的容量和流量。網路費用是根據不同的路由策略和容量的型別來計算，一條鏈路的費用由兩部分組成 與容量型別有關的固定費用和與連路長度有關的可變費用。現有一通訊網路共8...
2023年數學建模題目
a題校車問題 許多學校都建有新校區，常常需要將老校區的教師和工作人員用校車送到新校區。由於每天到新校區的教師和工作人員很多，往往需要安排許多車輛。如何有效的安排車輛及讓教師和工作人員盡量滿意是個十分重要的問題。現有如下問題請你設計解決。假設老校區的教師和工作人員分布在50個區，各區的距離見表1。各區...