粒子群算法介紹（摘自）
成都創(chuàng)新互聯(lián)是專業(yè)的日喀則網(wǎng)站建設(shè)公司，日喀則接單;提供網(wǎng)站設(shè)計、網(wǎng)站建設(shè),網(wǎng)頁設(shè)計,網(wǎng)站設(shè)計,建網(wǎng)站,PHP網(wǎng)站建設(shè)等專業(yè)做網(wǎng)站服務;采用PHP框架,可快速的進行日喀則網(wǎng)站開發(fā)網(wǎng)頁制作和功能擴展;專業(yè)做搜索引擎喜愛的網(wǎng)站,專業(yè)的做網(wǎng)站團隊,希望更多企業(yè)前來合作!
優(yōu)化問題是工業(yè)設(shè)計中經(jīng)常遇到的問題,許多問題最后都可以歸結(jié)為優(yōu)化問題. 為了解決各種各樣的優(yōu)化問題,人們提出了許多優(yōu)化算法,比較著名的有爬山法、遺傳算法等.優(yōu)化問題有兩個主要問題:一是要求尋找全局最小點,二是要求有較高的收斂速度. 爬山法精度較高,但是易于陷入局部極小. 遺傳算法屬于進化算法( Evolutionary Algorithms) 的一種,它通過模仿自然界的選擇與遺傳的機理來尋找最優(yōu)解. 遺傳算法有三個基本算子:選擇、交叉和變異. 但是遺傳算法的編程實現(xiàn)比較復雜,首先需要對問題進行編碼,找到最優(yōu)解之后還需要對問題進行解碼,另外三個算子的實現(xiàn)也有許多參數(shù),如交叉率和變異率,并且這些參數(shù)的選擇嚴重影響解的品質(zhì),而目前這些參數(shù)的選擇大部分是依靠經(jīng)驗.1995 年Eberhart 博士和kennedy 博士提出了一種新的算法;粒子群優(yōu)化(Partical Swarm Optimization -PSO) 算法 . 這種算法以其實現(xiàn)容易、精度高、收斂快等優(yōu)點引起了學術(shù)界的重視,并且在解決實際問題中展示了其優(yōu)越性.
粒子群優(yōu)化(Partical Swarm Optimization - PSO) 算法是近年來發(fā)展起來的一種新的進化算法( Evolu2tionary Algorithm - EA) .PSO 算法屬于進化算法的一種,和遺傳算法相似,它也是從隨機解出發(fā),通過迭代尋找最優(yōu)解,它也是通過適應度來評價解的品質(zhì). 但是它比遺傳算法規(guī)則更為簡單,它沒有遺傳算法的“交叉”(Crossover) 和“變異”(Mutation) 操作. 它通過追隨當前搜索到的最優(yōu)值來尋找全局最優(yōu) .
粒子群算法
1. 引言
粒子群優(yōu)化算法(PSO)是一種進化計算技術(shù)(evolutionary computation)，有Eberhart博士和kennedy博士發(fā)明。源于對鳥群捕食的行為研究
PSO同遺傳算法類似，是一種基于疊代的優(yōu)化工具。系統(tǒng)初始化為一組隨機解，通過疊代搜尋最優(yōu)值。但是并沒有遺傳算法用的交叉(crossover)以及變異(mutation)。而是粒子在解空間追隨最優(yōu)的粒子進行搜索。詳細的步驟以后的章節(jié)介紹
同遺傳算法比較，PSO的優(yōu)勢在于簡單容易實現(xiàn)并且沒有許多參數(shù)需要調(diào)整。目前已廣泛應用于函數(shù)優(yōu)化，神經(jīng)網(wǎng)絡訓練，模糊系統(tǒng)控制以及其他遺傳算法的應用領(lǐng)域
2. 背景: 人工生命
"人工生命"是來研究具有某些生命基本特征的人工系統(tǒng). 人工生命包括兩方面的內(nèi)容
1. 研究如何利用計算技術(shù)研究生物現(xiàn)象
2. 研究如何利用生物技術(shù)研究計算問題
我們現(xiàn)在關(guān)注的是第二部分的內(nèi)容. 現(xiàn)在已經(jīng)有很多源于生物現(xiàn)象的計算技巧. 例如, 人工神經(jīng)網(wǎng)絡是簡化的大腦模型. 遺傳算法是模擬基因進化過程的.
現(xiàn)在我們討論另一種生物系統(tǒng)- 社會系統(tǒng). 更確切的是, 在由簡單個體組成的群落與環(huán)境以及個體之間的互動行為. 也可稱做"群智能"(swarm intelligence). 這些模擬系統(tǒng)利用局部信息從而可能產(chǎn)生不可預測的群體行為
例如floys 和 boids, 他們都用來模擬魚群和鳥群的運動規(guī)律, 主要用于計算機視覺和計算機輔助設(shè)計.
在計算智能(computational intelligence)領(lǐng)域有兩種基于群智能的算法. 蟻群算法(ant colony optimization)和粒子群算法(particle swarm optimization). 前者是對螞蟻群落食物采集過程的模擬. 已經(jīng)成功運用在很多離散優(yōu)化問題上.
粒子群優(yōu)化算法(PSO) 也是起源對簡單社會系統(tǒng)的模擬. 最初設(shè)想是模擬鳥群覓食的過程. 但后來發(fā)現(xiàn)PSO是一種很好的優(yōu)化工具.
3. 算法介紹
如前所述，PSO模擬鳥群的捕食行為。設(shè)想這樣一個場景：一群鳥在隨機搜索食物。在這個區(qū)域里只有一塊食物。所有的鳥都不知道食物在那里。但是他們知道當前的位置離食物還有多遠。那么找到食物的最優(yōu)策略是什么呢。最簡單有效的就是搜尋目前離食物最近的鳥的周圍區(qū)域。
PSO從這種模型中得到啟示并用于解決優(yōu)化問題。PSO中，每個優(yōu)化問題的解都是搜索空間中的一只鳥。我們稱之為“粒子”。所有的例子都有一個由被優(yōu)化的函數(shù)決定的適應值(fitness value)，每個粒子還有一個速度決定他們飛翔的方向和距離。然后粒子們就追隨當前的最優(yōu)粒子在解空間中搜索
PSO 初始化為一群隨機粒子(隨機解)。然后通過疊代找到最優(yōu)解。在每一次疊代中，粒子通過跟蹤兩個"極值"來更新自己。第一個就是粒子本身所找到的最優(yōu)解。這個解叫做個體極值pBest. 另一個極值是整個種群目前找到的最優(yōu)解。這個極值是全局極值gBest。另外也可以不用整個種群而只是用其中一部分最為粒子的鄰居，那么在所有鄰居中的極值就是局部極值。
在找到這兩個最優(yōu)值時, 粒子根據(jù)如下的公式來更新自己的速度和新的位置
v[] = v[] + c1 * rand() * (pbest[] - present[]) + c2 * rand() * (gbest[] - present[]) (a)
present[] = persent[] + v[] (b)
v[] 是粒子的速度, persent[] 是當前粒子的位置. pbest[] and gbest[] 如前定義 rand () 是介于（0， 1）之間的隨機數(shù). c1, c2 是學習因子. 通常 c1 = c2 = 2.
程序的偽代碼如下
For each particle
____Initialize particle
END
Do
____For each particle
________Calculate fitness value
________If the fitness value is better than the best fitness value (pBest) in history
____________set current value as the new pBest
____End
____Choose the particle with the best fitness value of all the particles as the gBest
____For each particle
________Calculate particle velocity according equation (a)
________Update particle position according equation (b)
____End
While maximum iterations or minimum error criteria is not attained
在每一維粒子的速度都會被限制在一個最大速度Vmax，如果某一維更新后的速度超過用戶設(shè)定的Vmax，那么這一維的速度就被限定為Vmax
4. 遺傳算法和 PSO 的比較
大多數(shù)演化計算技術(shù)都是用同樣的過程
1. 種群隨機初始化
2. 對種群內(nèi)的每一個個體計算適應值(fitness value).適應值與最優(yōu)解的距離直接有關(guān)
3. 種群根據(jù)適應值進行復制
4. 如果終止條件滿足的話，就停止，否則轉(zhuǎn)步驟2
從以上步驟，我們可以看到PSO和GA有很多共同之處。兩者都隨機初始化種群，而且都使用適應值來評價系統(tǒng)，而且都根據(jù)適應值來進行一定的隨機搜索。兩個系統(tǒng)都不是保證一定找到最優(yōu)解
但是，PSO 沒有遺傳操作如交叉(crossover)和變異(mutation). 而是根據(jù)自己的速度來決定搜索。粒子還有一個重要的特點，就是有記憶。
與遺傳算法比較, PSO 的信息共享機制是很不同的. 在遺傳算法中，染色體(chromosomes) 互相共享信息，所以整個種群的移動是比較均勻的向最優(yōu)區(qū)域移動. 在PSO中, 只有g(shù)Best (or lBest) 給出信息給其他的粒子，這是單向的信息流動. 整個搜索更新過程是跟隨當前最優(yōu)解的過程. 與遺傳算法比較, 在大多數(shù)的情況下，所有的粒子可能更快的收斂于最優(yōu)解
5. 人工神經(jīng)網(wǎng)絡 和 PSO
人工神經(jīng)網(wǎng)絡(ANN)是模擬大腦分析過程的簡單數(shù)學模型，反向轉(zhuǎn)播算法是最流行的神經(jīng)網(wǎng)絡訓練算法。進來也有很多研究開始利用演化計算(evolutionary computation)技術(shù)來研究人工神經(jīng)網(wǎng)絡的各個方面。
演化計算可以用來研究神經(jīng)網(wǎng)絡的三個方面：網(wǎng)絡連接權(quán)重，網(wǎng)絡結(jié)構(gòu)(網(wǎng)絡拓撲結(jié)構(gòu)，傳遞函數(shù))，網(wǎng)絡學習算法。
不過大多數(shù)這方面的工作都集中在網(wǎng)絡連接權(quán)重，和網(wǎng)絡拓撲結(jié)構(gòu)上。在GA中，網(wǎng)絡權(quán)重和/或拓撲結(jié)構(gòu)一般編碼為染色體(Chromosome)，適應函數(shù)(fitness function)的選擇一般根據(jù)研究目的確定。例如在分類問題中，錯誤分類的比率可以用來作為適應值
演化計算的優(yōu)勢在于可以處理一些傳統(tǒng)方法不能處理的例子例如不可導的節(jié)點傳遞函數(shù)或者沒有梯度信息存在。但是缺點在于：在某些問題上性能并不是特別好。2. 網(wǎng)絡權(quán)重的編碼而且遺傳算子的選擇有時比較麻煩
最近已經(jīng)有一些利用PSO來代替反向傳播算法來訓練神經(jīng)網(wǎng)絡的論文。研究表明PSO 是一種很有潛力的神經(jīng)網(wǎng)絡算法。PSO速度比較快而且可以得到比較好的結(jié)果。而且還沒有遺傳算法碰到的問題
這里用一個簡單的例子說明PSO訓練神經(jīng)網(wǎng)絡的過程。這個例子使用分類問題的基準函數(shù)(Benchmark function)IRIS數(shù)據(jù)集。(Iris 是一種鳶尾屬植物) 在數(shù)據(jù)記錄中，每組數(shù)據(jù)包含Iris花的四種屬性：萼片長度，萼片寬度，花瓣長度，和花瓣寬度，三種不同的花各有50組數(shù)據(jù). 這樣總共有150組數(shù)據(jù)或模式。
我們用3層的神經(jīng)網(wǎng)絡來做分類?，F(xiàn)在有四個輸入和三個輸出。所以神經(jīng)網(wǎng)絡的輸入層有4個節(jié)點，輸出層有3個節(jié)點我們也可以動態(tài)調(diào)節(jié)隱含層節(jié)點的數(shù)目，不過這里我們假定隱含層有6個節(jié)點。我們也可以訓練神經(jīng)網(wǎng)絡中其他的參數(shù)。不過這里我們只是來確定網(wǎng)絡權(quán)重。粒子就表示神經(jīng)網(wǎng)絡的一組權(quán)重，應該是4*6+6*3=42個參數(shù)。權(quán)重的范圍設(shè)定為[-100，100] (這只是一個例子，在實際情況中可能需要試驗調(diào)整).在完成編碼以后，我們需要確定適應函數(shù)。對于分類問題，我們把所有的數(shù)據(jù)送入神經(jīng)網(wǎng)絡，網(wǎng)絡的權(quán)重有粒子的參數(shù)決定。然后記錄所有的錯誤分類的數(shù)目作為那個粒子的適應值?，F(xiàn)在我們就利用PSO來訓練神經(jīng)網(wǎng)絡來獲得盡可能低的錯誤分類數(shù)目。PSO本身并沒有很多的參數(shù)需要調(diào)整。所以在實驗中只需要調(diào)整隱含層的節(jié)點數(shù)目和權(quán)重的范圍以取得較好的分類效果。
6. PSO的參數(shù)設(shè)置
從上面的例子我們可以看到應用PSO解決優(yōu)化問題的過程中有兩個重要的步驟: 問題解的編碼和適應度函數(shù)
PSO的一個優(yōu)勢就是采用實數(shù)編碼, 不需要像遺傳算法一樣是二進制編碼(或者采用針對實數(shù)的遺傳操作.例如對于問題 f(x) = x1^2 + x2^2+x3^2 求解, 粒子可以直接編碼為 (x1, x2, x3), 而適應度函數(shù)就是f(x). 接著我們就可以利用前面的過程去尋優(yōu).這個尋優(yōu)過程是一個疊代過程, 中止條件一般為設(shè)置為達到最大循環(huán)數(shù)或者最小錯誤
PSO中并沒有許多需要調(diào)節(jié)的參數(shù),下面列出了這些參數(shù)以及經(jīng)驗設(shè)置
粒子數(shù): 一般取 20 – 40. 其實對于大部分的問題10個粒子已經(jīng)足夠可以取得好的結(jié)果, 不過對于比較難的問題或者特定類別的問題, 粒子數(shù)可以取到100 或 200
粒子的長度: 這是由優(yōu)化問題決定, 就是問題解的長度
粒子的范圍: 由優(yōu)化問題決定,每一維可是設(shè)定不同的范圍
Vmax: 最大速度,決定粒子在一個循環(huán)中最大的移動距離,通常設(shè)定為粒子的范圍寬度,例如上面的例子里,粒子 (x1, x2, x3) x1 屬于 [-10, 10], 那么 Vmax 的大小就是 20
學習因子: c1 和 c2 通常等于 2. 不過在文獻中也有其他的取值. 但是一般 c1 等于 c2 并且范圍在0和4之間
中止條件: 最大循環(huán)數(shù)以及最小錯誤要求. 例如, 在上面的神經(jīng)網(wǎng)絡訓練例子中, 最小錯誤可以設(shè)定為1個錯誤分類, 最大循環(huán)設(shè)定為2000, 這個中止條件由具體的問題確定.
全局PSO和局部PSO: 我們介紹了兩種版本的粒子群優(yōu)化算法: 全局版和局部版. 前者速度快不過有時會陷入局部最優(yōu). 后者收斂速度慢一點不過很難陷入局部最優(yōu). 在實際應用中, 可以先用全局PSO找到大致的結(jié)果,再有局部PSO進行搜索.
另外的一個參數(shù)是慣性權(quán)重, 由Shi 和Eberhart提出, 有興趣的可以參考他們1998年的論文(題目: A modified particle swarm optimizer)
蟻群算法(ant colony optimization, ACO)，又稱螞蟻算法，是一種用來在圖中尋找優(yōu)化路徑的機率型技術(shù)。它由Marco Dorigo于1992年在他的博士論文中引入，其靈感來源于螞蟻在尋找食物過程中發(fā)現(xiàn)路徑的行為。
為什么小小的螞蟻能夠找到食物？他們具有智能么？設(shè)想，如果我們要為螞蟻設(shè)計一個人工智能的程序，那么這個程序要多么復雜呢？首先，你要讓螞蟻能夠避開障礙物，就必須根據(jù)適當?shù)牡匦谓o它編進指令讓他們能夠巧妙的避開障礙物，其次，要讓螞蟻找到食物，就需要讓他們遍歷空間上的所有點；再次，如果要讓螞蟻找到最短的路徑，那么需要計算所有可能的路徑并且比較它們的大小，而且更重要的是，你要小心翼翼的編程，因為程序的錯誤也許會讓你前功盡棄。這是多么不可思議的程序！太復雜了，恐怕沒人能夠完成這樣繁瑣冗余的程序。
然而，事實并沒有你想得那么復雜，上面這個程序每個螞蟻的核心程序編碼不過100多行！為什么這么簡單的程序會讓螞蟻干這樣復雜的事情？答案是：簡單規(guī)則的涌現(xiàn)。事實上，每只螞蟻并不是像我們想象的需要知道整個世界的信息，他們其實只關(guān)心很小范圍內(nèi)的眼前信息，而且根據(jù)這些局部信息利用幾條簡單的規(guī)則進行決策，這樣，在蟻群這個集體里，復雜性的行為就會凸現(xiàn)出來。這就是人工生命、復雜性科學解釋的規(guī)律！那么，這些簡單規(guī)則是什么呢？下面詳細說明：
1、范圍：
螞蟻觀察到的范圍是一個方格世界，螞蟻有一個參數(shù)為速度半徑（一般是3），那么它能觀察到的范圍就是3*3個方格世界，并且能移動的距離也在這個范圍之內(nèi)。
2、環(huán)境：
螞蟻所在的環(huán)境是一個虛擬的世界，其中有障礙物，有別的螞蟻，還有信息素，信息素有兩種，一種是找到食物的螞蟻灑下的食物信息素，一種是找到窩的螞蟻灑下的窩的信息素。每個螞蟻都僅僅能感知它范圍內(nèi)的環(huán)境信息。環(huán)境以一定的速率讓信息素消失。
3、覓食規(guī)則：
在每只螞蟻能感知的范圍內(nèi)尋找是否有食物，如果有就直接過去。否則看是否有信息素，并且比較在能感知的范圍內(nèi)哪一點的信息素最多，這樣，它就朝信息素多的地方走，并且每只螞蟻多會以小概率犯錯誤，從而并不是往信息素最多的點移動。螞蟻找窩的規(guī)則和上面一樣，只不過它對窩的信息素做出反應，而對食物信息素沒反應。
4、移動規(guī)則：
每只螞蟻都朝向信息素最多的方向移，并且，當周圍沒有信息素指引的時候，螞蟻會按照自己原來運動的方向慣性的運動下去，并且，在運動的方向有一個隨機的小的擾動。為了防止螞蟻原地轉(zhuǎn)圈，它會記住最近剛走過了哪些點，如果發(fā)現(xiàn)要走的下一點已經(jīng)在最近走過了，它就會盡量避開。
5、避障規(guī)則：
如果螞蟻要移動的方向有障礙物擋住，它會隨機的選擇另一個方向，并且有信息素指引的話，它會按照覓食的規(guī)則行為。
7、播撒信息素規(guī)則：
每只螞蟻在剛找到食物或者窩的時候撒發(fā)的信息素最多，并隨著它走遠的距離，播撒的信息素越來越少。
根據(jù)這幾條規(guī)則，螞蟻之間并沒有直接的關(guān)系，但是每只螞蟻都和環(huán)境發(fā)生交互，而通過信息素這個紐帶，實際上把各個螞蟻之間關(guān)聯(lián)起來了。比如，當一只螞蟻找到了食物，它并沒有直接告訴其它螞蟻這兒有食物，而是向環(huán)境播撒信息素，當其它的螞蟻經(jīng)過它附近的時候，就會感覺到信息素的存在，進而根據(jù)信息素的指引找到了食物。
說了這么多，螞蟻究竟是怎么找到食物的呢？
在沒有螞蟻找到食物的時候，環(huán)境沒有有用的信息素，那么螞蟻為什么會相對有效的找到食物呢？這要歸功于螞蟻的移動規(guī)則，尤其是在沒有信息素時候的移動規(guī)則。首先，它要能盡量保持某種慣性，這樣使得螞蟻盡量向前方移動（開始，這個前方是隨機固定的一個方向），而不是原地無謂的打轉(zhuǎn)或者震動；其次，螞蟻要有一定的隨機性，雖然有了固定的方向，但它也不能像粒子一樣直線運動下去，而是有一個隨機的干擾。這樣就使得螞蟻運動起來具有了一定的目的性，盡量保持原來的方向，但又有新的試探，尤其當碰到障礙物的時候它會立即改變方向，這可以看成一種選擇的過程，也就是環(huán)境的障礙物讓螞蟻的某個方向正確，而其他方向則不對。這就解釋了為什么單個螞蟻在復雜的諸如迷宮的地圖中仍然能找到隱蔽得很好的食物。
當然，在有一只螞蟻找到了食物的時候，其他螞蟻會沿著信息素很快找到食物的。
螞蟻如何找到最短路徑的？這一是要歸功于信息素，另外要歸功于環(huán)境，具體說是計算機時鐘。信息素多的地方顯然經(jīng)過這里的螞蟻會多，因而會有更多的螞蟻聚集過來。假設(shè)有兩條路從窩通向食物，開始的時候，走這兩條路的螞蟻數(shù)量同樣多（或者較長的路上螞蟻多，這也無關(guān)緊要）。當螞蟻沿著一條路到達終點以后會馬上返回來，這樣，短的路螞蟻來回一次的時間就短，這也意味著重復的頻率就快，因而在單位時間里走過的螞蟻數(shù)目就多，灑下的信息素自然也會多，自然會有更多的螞蟻被吸引過來，從而灑下更多的信息素……；而長的路正相反，因此，越來越多地螞蟻聚集到較短的路徑上來，最短的路徑就近似找到了。也許有人會問局部最短路徑和全局最短路的問題，實際上螞蟻逐漸接近全局最短路的，為什么呢？這源于螞蟻會犯錯誤，也就是它會按照一定的概率不往信息素高的地方走而另辟蹊徑，這可以理解為一種創(chuàng)新，這種創(chuàng)新如果能縮短路途，那么根據(jù)剛才敘述的原理，更多的螞蟻會被吸引過來。
引申:
跟著螞蟻的蹤跡，你找到了什么？通過上面的原理敘述和實際操作，我們不難發(fā)現(xiàn)螞蟻之所以具有智能行為，完全歸功于它的簡單行為規(guī)則，而這些規(guī)則綜合起來具有下面兩個方面的特點：
1、多樣性
2、正反饋
多樣性保證了螞蟻在覓食的時候不置走進死胡同而無限循環(huán)，正反饋機制則保證了相對優(yōu)良的信息能夠被保存下來。我們可以把多樣性看成是一種創(chuàng)造能力，而正反饋是一種學習強化能力。正反饋的力量也可以比喻成權(quán)威的意見，而多樣性是打破權(quán)威體現(xiàn)的創(chuàng)造性，正是這兩點小心翼翼的巧妙結(jié)合才使得智能行為涌現(xiàn)出來了。
引申來講，大自然的進化，社會的進步、人類的創(chuàng)新實際上都離不開這兩樣東西，多樣性保證了系統(tǒng)的創(chuàng)新能力，正反饋保證了優(yōu)良特性能夠得到強化，兩者要恰到好處的結(jié)合。如果多樣性過剩，也就是系統(tǒng)過于活躍，這相當于螞蟻會過多的隨機運動，它就會陷入混沌狀態(tài)；而相反，多樣性不夠，正反饋機制過強，那么系統(tǒng)就好比一潭死水。這在蟻群中來講就表現(xiàn)為，螞蟻的行為過于僵硬，當環(huán)境變化了，螞蟻群仍然不能適當?shù)恼{(diào)整。
既然復雜性、智能行為是根據(jù)底層規(guī)則涌現(xiàn)的，既然底層規(guī)則具有多樣性和正反饋特點，那么也許你會問這些規(guī)則是哪里來的？多樣性和正反饋又是哪里來的？我本人的意見：規(guī)則來源于大自然的進化。而大自然的進化根據(jù)剛才講的也體現(xiàn)為多樣性和正反饋的巧妙結(jié)合。而這樣的巧妙結(jié)合又是為什么呢？為什么在你眼前呈現(xiàn)的世界是如此栩栩如生呢？答案在于環(huán)境造就了這一切，之所以你看到栩栩如生的世界，是因為那些不能夠適應環(huán)境的多樣性與正反饋的結(jié)合都已經(jīng)死掉了，被環(huán)境淘汰了！
!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN" ""
html xmlns=""HEAD
meta http-equiv="Content-Type" content="text/html; charset=gb2312" /
style
.ant{
position:absolute;
background-color:#000000;
overflow:hidden;
width:2px;
height:2px;
}
.food{
position:absolute;
background-color:#0000ff;
overflow:hidden;
width:2px;
height:2px;
}
.nest{
position:absolute;
background-color:#ff0000;
overflow:hidden;
width:2px;
height:2px;
}
/style
script type="text/JavaScript"
//============================
//系統(tǒng)參數(shù)初始化
//----------------------------
//生命體數(shù)量與軌跡長度
Unit=10;Path=30;
//生命體速度上下限
v0=2;vM=10;
//生命體加速度變化范圍
Kr=0.1;Kv=0.1*(vM-v0);
//生命體運動范圍
x0=0;xM=document.documentElement.clientWidth;
y0=0;yM=document.documentElement.clientHeight;
//生命體出生地(巢穴)
xi0=x0+(xM-x0)*Math.random();
yi0=y0+(yM-y0)*Math.random();
str0='div class="ant" style="left:'+xi0+';top:'+yi0+';"/div';
//食物所在地
xf=x0+(xM-x0)*Math.random();
yf=y0+(yM-y0)*Math.random();
//氣味感知范圍
R_2=5*5;
//============================
var r=new Array();
var v=new Array();
var dr=new Array();
var dv=new Array();
var x=new Array();
var y=new Array();
var life=new Array();
//單擊暫停
var xi0,yi0,xf,yf;
var Time0,str0;
window.status='pause';
function document.onclick(){
if(window.status=='pause'){
window.status=0;
nest.style.left=xi0;
nest.style.top=yi0;
food.style.left=xf;
food.style.top=yf;
//測試初始化時間用
Time0=(new Date()).getTime();
init(0);
}else{
window.status='pause';
}
}
//窗口大小調(diào)整后刷新頁面以調(diào)整系統(tǒng)參數(shù)
function window.onresize(){
// window.location.href=document.location;
}
//初始化函數(shù)
function init(i){
if(window.status!='pause'iUnit){
if(!life){
document.body.appendChild(life=document.createElement(str0));
x=xi0;
y=yi0;
r=Math.random();
v=1/Math.random();
dr=Kr*Math.random();
dv=Kv*Math.random();
}
Move(i);
window.status=i+1;
setTimeout('init('+(i+1)+')',i);
// }else{
// alert('生成耗時：'+((new Date()).getTime()-Time0)+'ms');
}
}
//運動函數(shù)
Total=Unit*Path;
P2=2*Math.PI;
function Move(i){
if(window.status!='pause'){
k=i%Unit;
X=x[k];
Y=y[k];
R=r[k];
V=v[k];
if(!life){
str='div class="ant" style="left:'+X+';top:'+Y+';"/div';
document.body.appendChild(life=document.createElement(str));
}
obj=life;
R+=dr[k]*(2*Math.random()-1);
V+=dv[k]*(2*Math.random()-1);
X+=Math.sin(P2*R)*V;
Y+=Math.cos(P2*R)*V;
//遇到食物原路返回并減小角度變化
distance=(X-xf)*(X-xf)+(Y-yf)*(Y-yf);
if(distanceR_2){
R+=0.5;
r/=2;
v*=2;
}
distance=(X-xi0)*(X-xi0)+(Y-yi0)*(Y-yi0);
if(distanceR_2){
R+=0.5;
r/=2;
v*=2;
}
/*----------------------------------
/*================================*/
//碰撞邊界反彈
R=(Xx0||XxM)?-R:R;
R=(Yy0||YyM)?0.5-R:R;
X=x[k]+Math.sin(P2*R)*V;
Y=y[k]+Math.cos(P2*R)*V;
/*================================*/
//溢出邊界重生(類似流星效果)
if(Xx0||XxM||Yy0||YyM){
X=xi0;
Y=yi0;
}
/*----------------------------------
/*================================*/
//邊界限制
x[k]=X=(Xx0)?x0:(XxM)?xM-2:X;
y[k]=Y=(Yy0)?y0:(YyM)?yM-2:Y;
r[k]=R1?R-1:R0?R+1:R;
v[k]=V=(Vv0)?v0:((VvM)?V:vM);
/*================================*/
obj.style.left=x[k]=X;
obj.style.top=y[k]=Y;
setTimeout('Move('+(i+Unit)%Total+')',Unit);
}
}
//根據(jù)瀏覽器自動加載動畫
switch(navigator.appName.toLowerCase()){
case "netscape":
window.addEventListener("load",document.onclick,false);
break;
case "microsoft internet explorer":
default:
window.attachEvent("onload",document.onclick);
break;
}
/script
/head
body scroll="no"
div id="food" class="food"/div
div id="nest" class="nest"/div
/body
/html
蟻群算法java實現(xiàn)以及TSP問題蟻群算法求解
蟻群算法原理與應用講解
蟻群算法原理與應用1 -自然計算與群體智能
1、蟻群算法(Ant Clony Optimization,ACO)是一種群智能算法，它是由一群無智能或有輕微智能的個體（Agent）通過相互協(xié)作而表現(xiàn)出智能行為，從而為求解復雜問題提供了一個新的可能性。
2、是一種仿生學的算法，是由自然界中螞蟻覓食的行為而啟發(fā)。（artificial ants；雙橋?qū)嶒灒?/p>
3、運作機理：當一定路徑上通過的螞蟻越來越多時，其留下的信息素軌跡也越來越多，后來螞蟻選擇該路徑的概率也越高，從而更增加了該路徑的信息素強度，而強度大的信息素會吸引更多的螞蟻，從而形成一種正反饋機制。
4、蟻群算法歐化過程中的兩個重要原則：
?a、螞蟻在眾多路徑中轉(zhuǎn)移路線的選擇規(guī)則。
?b、全局化信息素更新規(guī)則。信息素更新的實質(zhì)就是人工螞蟻根據(jù)真實螞蟻在訪問過的邊上留下的信息素和蒸發(fā)的信息素來模擬真實信息素數(shù)量的變化，從而使得越好的解得到越多的增強。這就形成了一種自催化強化學習(Autocatalytic Reinforcement Learning)的正反饋機制。
1、描述：螞蟻數(shù)量m；城市之間的信息素矩陣pheromone；每次迭代的m個螞蟻的最短路徑 ? ?BestLength；最佳路徑BestTour。 ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? 每只螞蟻都有 ：禁忌表(Tabu)存儲已訪問過的城市，允許訪問的城市表(Allowed)存儲還可以訪問的城市，矩陣（ Delta ）來存儲它在一個循環(huán)（或者迭代）中給所經(jīng)過的路徑釋放的信息素。
2、 狀態(tài)轉(zhuǎn)移概率 ：在搜索過程中，螞蟻根據(jù)各條路徑上的信息量及路徑的啟發(fā)信息來計算狀態(tài)轉(zhuǎn)移概率。在t時刻螞蟻k由元素（城市）i轉(zhuǎn)移到元素（城市）j的狀態(tài)轉(zhuǎn)移概率：
τij (t) ：時刻路徑(i, j)上的信息量。ηij=1/dij ：啟發(fā)函數(shù)。
α為信息啟發(fā)式因子 ，表示軌跡的相對重要性，反映了螞蟻在運動過程中積累的信息在螞蟻運動時所起的作用，其值越大，則該螞蟻越傾向于選擇其它螞蟻經(jīng)過的路徑，螞蟻之間的協(xié)作性越強；
β為期望啟發(fā)式因子 ，表示能見度的相對重要性，反映螞蟻在運動過程中啟發(fā)信息在螞蟻選擇路徑中的受重視程度，其值越大，則該狀態(tài)狀態(tài)轉(zhuǎn)移概率越接近于貪心規(guī)則；
3、 息素更新規(guī)則 ：
ρ表示信息素揮發(fā)系數(shù)；Δτij(t)表示本次循環(huán)中路徑(i, j)上的信息素增量，初始時刻Δτij(t) =0。
4、三種信息增量計算方法：
區(qū)別：第一種利用了全局信息，在走一圈后更新。二、三中都利用的是局部信息。通常使用第一種。
5、TSP中流程圖
蒙特卡洛： 大量隨機抽樣下的比對，最后結(jié)果就是在當前抽樣數(shù)量下篩選出的一定是最想要的那個結(jié)果。舉例：假如籃子里有1000個蘋果(你定的測試集)，讓你 每次閉著眼睛找一個最大的，可以不限制挑選次數(shù)；于是，你可以閉著眼隨機拿了一個，然后再隨機拿一個與第一個比，留下大的；再隨機拿一個，與前次留下的比較，又 可以留下大的；循環(huán)往復這樣：拿的次數(shù)越多，挑出最大蘋果的可能性也就越大!但除非你把1000個蘋果都挑一遍，否則你無法肯定最終挑出來的就是最大的一個。如果有 10000個蘋果的話，繼續(xù)如此說不定就能找到更大的！
模擬退火 ：“漸漸”清楚自己的目標是什么！并不斷朝“越發(fā)”明確的目標邁進，“越來越”不被誘惑干擾。舉例：為了找出地球上最高的山，一只兔子在開始并沒有 合適的策略，它隨機地跳了很長時間！在這期間，它可能走向高處，也可能踏入平地或溝壑。但是，隨著時間的流逝，它“漸漸清醒”! 并“直直地”朝著最高的方向跳去， 最后就到達了珠穆朗瑪峰。
粒子群 ：信息的社會共享，以一個團隊的形式來搜索！團隊里成員信息共享，共同進步；避免一個人工作時出現(xiàn)目光短淺，沒有全局意識。舉例：就像下圍棋，只 專注于一個角落的戰(zhàn)斗不一定能獲取最終的勝利，只有放眼全局，把所有己方的棋子都盤活，相互間彼此幫助，才能獲得最后勝利。
蟻群 ：和粒子群算法有些相似，都是靠團隊的力量共同去找目標！蟻群算法中特殊的是它的"信息素"揮發(fā)! 這個效果是其他算法中沒有的！
以上所有的最優(yōu)化算法都很難做到極高的精度，這是必然的： 一是 因為全局搜索已經(jīng)耗費了大量的時間和資源，再過分強調(diào)精度有些不經(jīng)濟； 二是 因為全局搜索得到的最值可以理解為一精確最值的一個準確范圍！即進入這個范圍再進行精確的搜索一定可以找到精確最值；但是，全局最優(yōu)的核心是隨機/概率，當進入一個準確范圍時，這個范圍肯定是很小的，如果之后精確搜索還用全局搜索的概率參數(shù)(此時來說波動范圍太大了)，很可能又會跳出這個好不容易找到的精確區(qū)域！
因此： 全局最優(yōu)算法與局部最優(yōu)算法是要相結(jié)合的 ！全局最優(yōu)算法負責劃定最值所在的一個精確的、較小的范圍內(nèi)，即告訴局部最優(yōu)算法在這個范圍內(nèi)繼續(xù)找一定可以找到精確解；局部最優(yōu)算法按照較小的步長、較高的精度繼續(xù)搜索精確最值。
常用全局最優(yōu)算法：蒙特卡洛(MC)、模擬退火(SA)、粒子群(PSO)、蟻群(AG)；
常用局部最優(yōu)算法：梯度下降法、牛頓法、阻尼牛頓法、共軛梯度法；
推薦搭配1：蒙特卡洛
推薦搭配2：粒子群 + 梯度下降
推薦搭配3：蟻群 + 梯度下降 + 重檢機制
以上提到算法的 “程序 + 詳細使用說明” 參考以下地址：
優(yōu)化算法
“蟻群算法”學習包下載
下載地址： (請使用 eMule 下載)
近一百多篇文章，打包壓縮后有 24.99MB ，基本上是從維普數(shù)據(jù)庫中下載來的，僅供學習和研究之用，請務用于商業(yè)活動或其他非法活動中，各文章版權(quán)歸原作者所有。
如果您覺得本人這樣做侵犯了您的版權(quán)，請在本帖后回復，本人會馬上刪除相應的文章。
以下是文件列表，全是 PDF 格式的：
基于蟻群優(yōu)化算法遞歸神經(jīng)網(wǎng)絡的短期負荷預測
蟻群算法的小改進
基于蟻群算法的無人機任務規(guī)劃
多態(tài)蟻群算法
MCM基板互連測試的單探針路徑優(yōu)化研究
改進的增強型蟻群算法
基于云模型理論的蟻群算法改進研究
基于禁忌搜索與蟻群最優(yōu)結(jié)合算法的配電網(wǎng)規(guī)劃
自適應蟻群算法在序列比對中的應用
基于蟻群算法的QoS多播路由優(yōu)化算法
多目標優(yōu)化問題的蟻群算法研究
多線程蟻群算法及其在最短路問題上的應用研究
改進的蟻群算法在2D HP模型中的應用
制造系統(tǒng)通用作業(yè)計劃與蟻群算法優(yōu)化
基于混合行為蟻群算法的研究
火力優(yōu)化分配問題的小生境遺傳螞蟻算法
基于蟻群算法的對等網(wǎng)模擬器的設(shè)計與實現(xiàn)
基于粗粒度模型的蟻群優(yōu)化并行算法
動態(tài)躍遷轉(zhuǎn)移蟻群算法
基于人工免疫算法和蟻群算法求解旅行商問題
基于信息素異步更新的蟻群算法
用于連續(xù)函數(shù)優(yōu)化的蟻群算法
求解復雜多階段決策問題的動態(tài)窗口蟻群優(yōu)化算法
蟻群算法在鑄造生產(chǎn)配料優(yōu)化中的應用
多階段輸電網(wǎng)絡最優(yōu)規(guī)劃的并行蟻群算法
求解旅行商問題的混合粒子群優(yōu)化算法
微粒群優(yōu)化算法研究現(xiàn)狀及其進展
隨機攝動蟻群算法的收斂性及其數(shù)值特性分析
廣義蟻群與粒子群結(jié)合算法在電力系統(tǒng)經(jīng)濟負荷分配中的應用
改進的蟻群算法及其在TSP中的應用研究
蟻群算法的全局收斂性研究及改進
房地產(chǎn)開發(fā)項目投資組合優(yōu)化的改進蟻群算法
一種改進的蟻群算法用于灰色約束非線性規(guī)劃問題求解
一種自適應蟻群算法及其仿真研究
一種動態(tài)自適應蟻群算法
螞蟻群落優(yōu)化算法在蛋白質(zhì)折疊二維親-疏水格點模型中的應用
用改進蟻群算法求解函數(shù)優(yōu)化問題
連續(xù)優(yōu)化問題的蟻群算法研究進展
蟻群算法概述
Ant colony system algorithm for the optimization of beer fermentation control
蟻群算法在K—TSP問題中的應用
Parallel ant colony algorithm and its application in the capacitated lot sizing problem for an agile supply chain
基于遺傳蟻群算法的機器人全局路徑規(guī)劃研究
改進的蟻群算法在礦山物流配送路徑優(yōu)化中的研究
基于蟻群算法的配電網(wǎng)絡綜合優(yōu)化方法
基于蟻群算法的分類規(guī)則挖掘算法
蟻群算法在連續(xù)性空間優(yōu)化問題中的應用
蟻群算法在礦井通風系統(tǒng)優(yōu)化設(shè)計中的應用
基于蟻群算法的液壓土錨鉆機動力頭優(yōu)化設(shè)計
改進蟻群算法設(shè)計拉式膜片彈簧
計算機科學技術(shù)
基本蟻群算法及其改進
TSP改進算法及在PCB數(shù)控加工刀具軌跡中的應用
可靠性優(yōu)化的蟻群算法
對一類帶聚類特征TSP問題的蟻群算法求解
蟻群算法理論及應用研究的進展
基于二進制編碼的蟻群優(yōu)化算法及其收斂性分析
蟻群算法的理論及其應用
基于蟻群行為仿真的影像紋理分類
啟發(fā)式蟻群算法及其在高填石路堤穩(wěn)定性分析中的應用
蟻群算法的研究現(xiàn)狀
一種快速全局優(yōu)化的改進蟻群算法及仿真
聚類問題的蟻群算法
蟻群最優(yōu)化——模型、算法及應用綜述
基于信息熵的改進蟻群算法及其應用
機載公共設(shè)備綜合管理系統(tǒng)任務分配算法研究
基于改進蟻群算法的飛機低空突防航路規(guī)劃
利用信息量留存的蟻群遺傳算法
An Improved Heuristic Ant-Clustering Algorithm
改進型蟻群算法在內(nèi)燃機徑向滑動軸承優(yōu)化設(shè)計中的應用
基于蟻群算法的PID參數(shù)優(yōu)化
基于蟻群算法的復雜系統(tǒng)多故障狀態(tài)的決策
蟻群算法在數(shù)據(jù)挖掘中的應用研究
基于蟻群算法的基因聯(lián)接學習遺傳算法
基于細粒度模型的并行蟻群優(yōu)化算法
Binary-Coding-Based Ant Colony Optimization and Its Convergence
運載火箭控制系統(tǒng)漏電故障診斷研究
混沌擾動啟發(fā)式蟻群算法及其在邊坡非圓弧臨界滑動面搜索中的應用
蟻群算法原理的仿真研究
Hopfield neural network based on ant system
蟻群算法及其實現(xiàn)方法研究
分層實體制造激光頭切割路徑的建模與優(yōu)化
配送網(wǎng)絡規(guī)劃蟻群算法
基于蟻群算法的城域交通控制實時滾動優(yōu)化
基于蟻群算法的復合形法及其在邊坡穩(wěn)定分析中的應用
Ant Colony Algorithm for Solving QoS Routing Problem
多產(chǎn)品間歇過程調(diào)度問題的建模與優(yōu)化
基于蟻群算法的兩地之間的最佳路徑選擇
蟻群算法求解問題時易產(chǎn)生的誤區(qū)及對策
用雙向收斂蟻群算法解作業(yè)車間調(diào)度問題
物流配送路徑安排問題的混合蟻群算法
求解TSP問題的模式學習并行蟻群算法
基于蟻群算法的三維空間機器人路徑規(guī)劃
蟻群優(yōu)化算法及其應用
蟻群算法不確定性分析
一種求解TSP問題的相遇蟻群算法
基于蟻群優(yōu)化算法的彩色圖像顏色聚類的研究
鈑金件數(shù)控激光切割割嘴路徑的優(yōu)化
基于蟻群算法的圖像分割方法
一種基于蟻群算法的聚類組合方法
圓排列問題的蟻群模擬退火算法
智能混合優(yōu)化策略及其在流水作業(yè)調(diào)度中的應用
蟻群算法在QoS網(wǎng)絡路由中的應用
一種改進的自適應路由算法
基于蟻群算法的煤炭運輸優(yōu)化方法
基于蟻群智能和支持向量機的人臉性別分類方法
蟻群算法在啤酒發(fā)酵控制優(yōu)化中的應用
一種基于時延信息的多QoS快速自適應路由算法
蟻群算法中參數(shù)α、β、ρ設(shè)置的研究——以TSP問題為例
基于人工蟻群優(yōu)化的矢量量化碼書設(shè)計算法
具有自適應雜交特征的蟻群算法
蟻群算法在原料礦粉混勻優(yōu)化中的應用
基于多Agent的蟻群算法在車間動態(tài)調(diào)度中的應用研究
用蟻群優(yōu)化算法求解中國旅行商問題
蟻群算法在嬰兒營養(yǎng)米粉配方中的應用
蟻群算法在機械優(yōu)化設(shè)計中的應用
蟻群優(yōu)化算法的研究現(xiàn)狀及研究展望
蟻群優(yōu)化算法及其應用研究進展
蟻群算法的理論與應用
簡單蟻群算法的仿真分析
一種改進的蟻群算法求解最短路徑問題
基于模式求解旅行商問題的蟻群算法
一種求解TSP的混合型蟻群算法
基于MATLAB的改進型基本蟻群算法
動態(tài)蟻群算法求解TSP問題
用蟻群算法求解類TSP問題的研究
蟻群算法求解連續(xù)空間優(yōu)化問題的一種方法
用混合型螞蟻群算法求解TSP問題
求解復雜TSP問題的隨機擾動蟻群算法
基于蟻群算法的中國旅行商問題滿意解
蟻群算法的研究現(xiàn)狀和應用及螞蟻智能體的硬件實現(xiàn)
蟻群算法概述
蟻群算法的研究現(xiàn)狀及其展望
基于蟻群算法的配電網(wǎng)網(wǎng)架優(yōu)化規(guī)劃方法
用于一般函數(shù)優(yōu)化的蟻群算法
協(xié)同模型與遺傳算法的集成
基于蟻群最優(yōu)的輸電網(wǎng)絡擴展規(guī)劃
自適應蟻群算法
凸整數(shù)規(guī)劃問題的混合蟻群算法
一種新的進化算法—蛟群算法
基于協(xié)同工作方式的一種蟻群布線系統(tǒng)
遺傳算法（Genetic Algorithm）是模擬達爾文生物進化論的自然選擇和遺傳學機理的生物進化過程的計算模型，是一種通過模擬自然進化過程搜索最優(yōu)解的方法。
蟻群算法(ant colony optimization, ACO)，又稱螞蟻算法，是一種用來在圖中尋找優(yōu)化路徑的機率型算法。
粒子群算法，也稱粒子群優(yōu)化算法（Particle Swarm Optimization），縮寫為 PSO， 是近年來由J. Kennedy和R. C. Eberhart等[1] 開發(fā)的一種新的進化算法(Evolutionary Algorithm - EA)。PSO 算法屬于進化算法的一種，和模擬退火算法相似，它也是從隨機解出發(fā)，通過迭代尋找最優(yōu)解，它也是通過適應度來評價解的品質(zhì)，但它比遺傳算法規(guī)則更為簡單，它沒有遺傳算法的“交叉”(Crossover) 和“變異”(Mutation) 操作，它通過追隨當前搜索到的最優(yōu)值來尋找全局最優(yōu)。
重慶分公司
重慶分公司
