群优化算法
PSO粒子群優(yōu)化算法
1. 引言
粒子群優(yōu)化算法(PSO)是一種進(jìn)化計(jì)算技術(shù)(evolutionary computation)，由Eberhart博士和kennedy博士發(fā)明。源于對(duì)鳥(niǎo)群捕食的行為研究
PSO同遺傳算法類似，是一種基于迭代的優(yōu)化工具。系統(tǒng)初始化為一組隨機(jī)解，通過(guò)迭代搜尋最優(yōu)值。但是并沒(méi)有遺傳算法用的交叉(crossover)以及變異(mutation)。而是粒子在解空間追隨最優(yōu)的粒子進(jìn)行搜索。詳細(xì)的步驟以后的章節(jié)介紹
同遺傳算法比較，PSO的優(yōu)勢(shì)在于簡(jiǎn)單容易實(shí)現(xiàn)并且沒(méi)有許多參數(shù)需要調(diào)整。目前已廣泛應(yīng)用于函數(shù)優(yōu)化，神經(jīng)網(wǎng)絡(luò)訓(xùn)練，模糊系統(tǒng)控制以及其他遺傳算法的應(yīng)用領(lǐng)域
2. 背景: 人工生命
"人工生命"是來(lái)研究具有某些生命基本特征的人工系統(tǒng). 人工生命包括兩方面的內(nèi)容
1. 研究如何利用計(jì)算技術(shù)研究生物現(xiàn)象
2. 研究如何利用生物技術(shù)研究計(jì)算問(wèn)題
我們現(xiàn)在關(guān)注的是第二部分的內(nèi)容. 現(xiàn)在已經(jīng)有很多源于生物現(xiàn)象的計(jì)算技巧. 例如, 人工神經(jīng)網(wǎng)絡(luò)是簡(jiǎn)化的大腦模型. 遺傳算法是模擬基因進(jìn)化過(guò)程的.
現(xiàn)在我們討論另一種生物系統(tǒng)- 社會(huì)系統(tǒng). 更確切的是, 在由簡(jiǎn)單個(gè)體組成的群落與環(huán)境以及個(gè)體之間的互動(dòng)行為. 也可稱做"群智能"(swarm intelligence). 這些模擬系統(tǒng)利用局部信息從而可能產(chǎn)生不可預(yù)測(cè)的群體行為
例如floys 和 boids, 他們都用來(lái)模擬魚(yú)群和鳥(niǎo)群的運(yùn)動(dòng)規(guī)律, 主要用于計(jì)算機(jī)視覺(jué)和計(jì)算機(jī)輔助設(shè)計(jì).
在計(jì)算智能(computational intelligence)領(lǐng)域有兩種基于群智能的算法. 蟻群算法(ant colony optimization)和粒子群算法(particle swarm optimization). 前者是對(duì)螞蟻群落食物采集過(guò)程的模擬. 已經(jīng)成功運(yùn)用在很多離散優(yōu)化問(wèn)題上.
粒子群優(yōu)化算法(PSO) 也是起源對(duì)簡(jiǎn)單社會(huì)系統(tǒng)的模擬. 最初設(shè)想是模擬鳥(niǎo)群覓食的過(guò)程. 但后來(lái)發(fā)現(xiàn)PSO是一種很好的優(yōu)化工具.
3. 算法介紹
如前所述，PSO模擬鳥(niǎo)群的捕食行為。設(shè)想這樣一個(gè)場(chǎng)景：一群鳥(niǎo)在隨機(jī)搜索食物。在這個(gè)區(qū)域里只有一塊食物。所有的鳥(niǎo)都不知道食物在那里。但是他們知道當(dāng)前的位置離食物還有多遠(yuǎn)。那么找到食物的最優(yōu)策略是什么呢。最簡(jiǎn)單有效的就是搜尋目前離食物最近的鳥(niǎo)的周圍區(qū)域。
PSO從這種模型中得到啟示并用于解決優(yōu)化問(wèn)題。PSO中，每個(gè)優(yōu)化問(wèn)題的解都是搜索空間中的一只鳥(niǎo)。我們稱之為“粒子”。所有的例子都有一個(gè)由被優(yōu)化的函數(shù)決定的適應(yīng)值(fitness value)，每個(gè)粒子還有一個(gè)速度決定他們飛翔的方向和距離。然后粒子們就追隨當(dāng)前的最優(yōu)粒子在解空間中搜索
PSO 初始化為一群隨機(jī)粒子(隨機(jī)解)。然后通過(guò)疊代找到最優(yōu)解。在每一次疊代中，粒子通過(guò)跟蹤兩個(gè)"極值"來(lái)更新自己。第一個(gè)就是粒子本身所找到的最優(yōu)解。這個(gè)解叫做個(gè)體極值pBest. 另一個(gè)極值是整個(gè)種群目前找到的最優(yōu)解。這個(gè)極值是全局極值gBest。另外也可以不用整個(gè)種群而只是用其中一部分最為粒子的鄰居，那么在所有鄰居中的極值就是局部極值。
在找到這兩個(gè)最優(yōu)值時(shí), 粒子根據(jù)如下的公式來(lái)更新自己的速度和新的位置
v[] = v[] + c1 * rand() * (pbest[] - present[]) + c2 * rand() * (gbest[] - present[]) (a)
present[] = persent[] + v[] (b)
v[] 是粒子的速度, persent[] 是當(dāng)前粒子的位置. pbest[] and gbest[] 如前定義 rand () 是介于（0， 1）之間的隨機(jī)數(shù). c1, c2 是學(xué)習(xí)因子. 通常 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
在每一維粒子的速度都會(huì)被限制在一個(gè)最大速度Vmax，如果某一維更新后的速度超過(guò)用戶設(shè)定的Vmax，那么這一維的速度就被限定為Vmax
4. 遺傳算法和 PSO 的比較
大多數(shù)演化計(jì)算技術(shù)都是用同樣的過(guò)程
1. 種群隨機(jī)初始化
2. 對(duì)種群內(nèi)的每一個(gè)個(gè)體計(jì)算適應(yīng)值(fitness value).適應(yīng)值與最優(yōu)解的距離直接有關(guān)
3. 種群根據(jù)適應(yīng)值進(jìn)行復(fù)制
4. 如果終止條件滿足的話，就停止，否則轉(zhuǎn)步驟2
從以上步驟，我們可以看到PSO和GA有很多共同之處。兩者都隨機(jī)初始化種群，而且都使用適應(yīng)值來(lái)評(píng)價(jià)系統(tǒng)，而且都根據(jù)適應(yīng)值來(lái)進(jìn)行一定的隨機(jī)搜索。兩個(gè)系統(tǒng)都不是保證一定找到最優(yōu)解
但是，PSO 沒(méi)有遺傳操作如交叉(crossover)和變異(mutation). 而是根據(jù)自己的速度來(lái)決定搜索。粒子還有一個(gè)重要的特點(diǎn)，就是有記憶。
與遺傳算法比較, PSO 的信息共享機(jī)制是很不同的. 在遺傳算法中，染色體(chromosomes) 互相共享信息，所以整個(gè)種群的移動(dòng)是比較均勻的向最優(yōu)區(qū)域移動(dòng). 在PSO中, 只有g(shù)Best (or lBest) 給出信息給其他的粒子， 這是單向的信息流動(dòng). 整個(gè)搜索更新過(guò)程是跟隨當(dāng)前最優(yōu)解的過(guò)程. 與遺傳算法比較, 在大多數(shù)的情況下，所有的粒子可能更快的收斂于最優(yōu)解
5. 人工神經(jīng)網(wǎng)絡(luò) 和 PSO
人工神經(jīng)網(wǎng)絡(luò)(ANN)是模擬大腦分析過(guò)程的簡(jiǎn)單數(shù)學(xué)模型，反向轉(zhuǎn)播算法是最流行的神經(jīng)網(wǎng)絡(luò)訓(xùn)練算法。進(jìn)來(lái)也有很多研究開(kāi)始利用演化計(jì)算(evolutionary computation)技術(shù)來(lái)研究人工神經(jīng)網(wǎng)絡(luò)的各個(gè)方面。
演化計(jì)算可以用來(lái)研究神經(jīng)網(wǎng)絡(luò)的三個(gè)方面：網(wǎng)絡(luò)連接權(quán)重，網(wǎng)絡(luò)結(jié)構(gòu)(網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)，傳遞函數(shù))，網(wǎng)絡(luò)學(xué)習(xí)算法。
不過(guò)大多數(shù)這方面的工作都集中在網(wǎng)絡(luò)連接權(quán)重，和網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)上。在GA中，網(wǎng)絡(luò)權(quán)重和/或拓?fù)浣Y(jié)構(gòu)一般編碼為染色體(Chromosome)，適應(yīng)函數(shù)(fitness function)的選擇一般根據(jù)研究目的確定。例如在分類問(wèn)題中，錯(cuò)誤分類的比率可以用來(lái)作為適應(yīng)值
演化計(jì)算的優(yōu)勢(shì)在于可以處理一些傳統(tǒng)方法不能處理的例子例如不可導(dǎo)的節(jié)點(diǎn)傳遞函數(shù)或者沒(méi)有梯度信息存在。但是缺點(diǎn)在于：在某些問(wèn)題上性能并不是特別好。2. 網(wǎng)絡(luò)權(quán)重的編碼而且遺傳算子的選擇有時(shí)比較麻煩
最近已經(jīng)有一些利用PSO來(lái)代替反向傳播算法來(lái)訓(xùn)練神經(jīng)網(wǎng)絡(luò)的論文。研究表明PSO 是一種很有潛力的神經(jīng)網(wǎng)絡(luò)算法。PSO速度比較快而且可以得到比較好的結(jié)果。而且還沒(méi)有遺傳算法碰到的問(wèn)題
這里用一個(gè)簡(jiǎn)單的例子說(shuō)明PSO訓(xùn)練神經(jīng)網(wǎng)絡(luò)的過(guò)程。這個(gè)例子使用分類問(wèn)題的基準(zhǔn)函數(shù)(Benchmark function)IRIS數(shù)據(jù)集。(Iris 是一種鳶尾屬植物) 在數(shù)據(jù)記錄中，每組數(shù)據(jù)包含Iris花的四種屬性：萼片長(zhǎng)度，萼片寬度，花瓣長(zhǎng)度，和花瓣寬度，三種不同的花各有50組數(shù)據(jù). 這樣總共有150組數(shù)據(jù)或模式。
我們用3層的神經(jīng)網(wǎng)絡(luò)來(lái)做分類。現(xiàn)在有四個(gè)輸入和三個(gè)輸出。所以神經(jīng)網(wǎng)絡(luò)的輸入層有4個(gè)節(jié)點(diǎn)，輸出層有3個(gè)節(jié)點(diǎn)我們也可以動(dòng)態(tài)調(diào)節(jié)隱含層節(jié)點(diǎn)的數(shù)目，不過(guò)這里我們假定隱含層有6個(gè)節(jié)點(diǎn)。我們也可以訓(xùn)練神經(jīng)網(wǎng)絡(luò)中其他的參數(shù)。不過(guò)這里我們只是來(lái)確定網(wǎng)絡(luò)權(quán)重。粒子就表示神經(jīng)網(wǎng)絡(luò)的一組權(quán)重，應(yīng)該是4*6+6*3=42個(gè)參數(shù)。權(quán)重的范圍設(shè)定為[-100，100] (這只是一個(gè)例子，在實(shí)際情況中可能需要試驗(yàn)調(diào)整).在完成編碼以后，我們需要確定適應(yīng)函數(shù)。對(duì)于分類問(wèn)題，我們把所有的數(shù)據(jù)送入神經(jīng)網(wǎng)絡(luò)，網(wǎng)絡(luò)的權(quán)重有粒子的參數(shù)決定。然后記錄所有的錯(cuò)誤分類的數(shù)目作為那個(gè)粒子的適應(yīng)值。現(xiàn)在我們就利用PSO來(lái)訓(xùn)練神經(jīng)網(wǎng)絡(luò)來(lái)獲得盡可能低的錯(cuò)誤分類數(shù)目。PSO本身并沒(méi)有很多的參數(shù)需要調(diào)整。所以在實(shí)驗(yàn)中只需要調(diào)整隱含層的節(jié)點(diǎn)數(shù)目和權(quán)重的范圍以取得較好的分類效果。
6. PSO的參數(shù)設(shè)置
從上面的例子我們可以看到應(yīng)用PSO解決優(yōu)化問(wèn)題的過(guò)程中有兩個(gè)重要的步驟: 問(wèn)題解的編碼和適應(yīng)度函數(shù)
PSO的一個(gè)優(yōu)勢(shì)就是采用實(shí)數(shù)編碼, 不需要像遺傳算法一樣是二進(jìn)制編碼(或者采用針對(duì)實(shí)數(shù)的遺傳操作.例如對(duì)于問(wèn)題 f(x) = x1^2 + x2^2+x3^2 求解, 粒子可以直接編碼為 (x1, x2, x3), 而適應(yīng)度函數(shù)就是f(x). 接著我們就可以利用前面的過(guò)程去尋優(yōu).這個(gè)尋優(yōu)過(guò)程是一個(gè)疊代過(guò)程, 中止條件一般為設(shè)置為達(dá)到最大循環(huán)數(shù)或者最小錯(cuò)誤
PSO中并沒(méi)有許多需要調(diào)節(jié)的參數(shù),下面列出了這些參數(shù)以及經(jīng)驗(yàn)設(shè)置
粒子數(shù): 一般取 20 – 40. 其實(shí)對(duì)于大部分的問(wèn)題10個(gè)粒子已經(jīng)足夠可以取得好的結(jié)果, 不過(guò)對(duì)于比較難的問(wèn)題或者特定類別的問(wèn)題, 粒子數(shù)可以取到100 或 200
粒子的長(zhǎng)度: 這是由優(yōu)化問(wèn)題決定, 就是問(wèn)題解的長(zhǎng)度
粒子的范圍: 由優(yōu)化問(wèn)題決定,每一維可是設(shè)定不同的范圍
Vmax: 最大速度,決定粒子在一個(gè)循環(huán)中最大的移動(dòng)距離,通常設(shè)定為粒子的范圍寬度,例如上面的例子里,粒子 (x1, x2, x3) x1 屬于 [-10, 10], 那么 Vmax 的大小就是 20
學(xué)習(xí)因子: c1 和 c2 通常等于 2. 不過(guò)在文獻(xiàn)中也有其他的取值. 但是一般 c1 等于 c2 并且范圍在0和4之間
中止條件: 最大循環(huán)數(shù)以及最小錯(cuò)誤要求. 例如, 在上面的神經(jīng)網(wǎng)絡(luò)訓(xùn)練例子中, 最小錯(cuò)誤可以設(shè)定為1個(gè)錯(cuò)誤分類, 最大循環(huán)設(shè)定為2000, 這個(gè)中止條件由具體的問(wèn)題確定.
全局PSO和局部PSO: 我們介紹了兩種版本的粒子群優(yōu)化算法: 全局版和局部版. 前者速度快不過(guò)有時(shí)會(huì)陷入局部最優(yōu). 后者收斂速度慢一點(diǎn)不過(guò)很難陷入局部最優(yōu). 在實(shí)際應(yīng)用中, 可以先用全局PSO找到大致的結(jié)果,再有局部PSO進(jìn)行搜索.
另外的一個(gè)參數(shù)是慣性權(quán)重, 由Shi 和Eberhart提出, 有興趣的可以參考他們1998年的論文(題目: A modified particle swarm optimizer)
7. Online Resources of PSO
The development of PSO is still ongoing. And there are still many unknown areas in PSO research such as the mathematical validation of particle swarm theory.
One can find much information from the internet. Following are some information you can get online:
http://www.particleswarm.net lots of information about Particle Swarms and, particularly, Particle Swarm Optimization. lots of Particle Swarm Links.
http://icdweb.cc.purdue.edu/~hux/PSO.shtml lists an updated bibliography of particle swarm optimization and some online paper links
http://www.researchindex.com/ you can search particle swarm related papers and references.
2006.7.11 13:20 作者：xiao1jun收藏 | 評(píng)論：0
蟻群算法
簡(jiǎn)介：蟻群算法(ant colony optimization, ACO)，又稱螞蟻算法，是一種用來(lái)在圖中尋找優(yōu)化路徑的機(jī)率型技術(shù)。它由Marco Dorigo于1992年在他的博士論文中引入，其靈感來(lái)源于螞蟻在尋找食物過(guò)程中發(fā)現(xiàn)路徑的行為。
蟻群算法(ant colony optimization, ACO)，又稱螞蟻算法，是一種用來(lái)在圖中尋找優(yōu)化路徑的機(jī)率型技術(shù)。它由Marco Dorigo于1992年在他的博士論文中引入，其靈感來(lái)源于螞蟻在尋找食物過(guò)程中發(fā)現(xiàn)路徑的行為。
為什么小小的螞蟻能夠找到食物？他們具有智能么？設(shè)想，如果我們要為螞蟻設(shè)計(jì)一個(gè)人工智能的程序，那么這個(gè)程序要多么復(fù)雜呢？首先，你要讓螞蟻能夠避開(kāi)障礙物，就必須根據(jù)適當(dāng)?shù)牡匦谓o它編進(jìn)指令讓他們能夠巧妙的避開(kāi)障礙物，其次，要讓螞蟻找到食物，就需要讓他們遍歷空間上的所有點(diǎn)；再次，如果要讓螞蟻找到最短的路徑，那么需要計(jì)算所有可能的路徑并且比較它們的大小，而且更重要的是，你要小心翼翼的編程，因?yàn)槌绦虻腻e(cuò)誤也許會(huì)讓你前功盡棄。這是多么不可思議的程序！太復(fù)雜了，恐怕沒(méi)人能夠完成這樣繁瑣冗余的程序。
然而，事實(shí)并沒(méi)有你想得那么復(fù)雜，上面這個(gè)程序每個(gè)螞蟻的核心程序編碼不過(guò)100多行！為什么這么簡(jiǎn)單的程序會(huì)讓螞蟻干這樣復(fù)雜的事情？答案是：簡(jiǎn)單規(guī)則的涌現(xiàn)。事實(shí)上，每只螞蟻并不是像我們想象的需要知道整個(gè)世界的信息，他們其實(shí)只關(guān)心很小范圍內(nèi)的眼前信息，而且根據(jù)這些局部信息利用幾條簡(jiǎn)單的規(guī)則進(jìn)行決策，這樣，在蟻群這個(gè)集體里，復(fù)雜性的行為就會(huì)凸現(xiàn)出來(lái)。這就是人工生命、復(fù)雜性科學(xué)解釋的規(guī)律！那么，這些簡(jiǎn)單規(guī)則是什么呢？下面詳細(xì)說(shuō)明：
1、范圍：
螞蟻觀察到的范圍是一個(gè)方格世界，螞蟻有一個(gè)參數(shù)為速度半徑（一般是3），那么它能觀察到的范圍就是3*3個(gè)方格世界，并且能移動(dòng)的距離也在這個(gè)范圍之內(nèi)。
2、環(huán)境：
螞蟻所在的環(huán)境是一個(gè)虛擬的世界，其中有障礙物，有別的螞蟻，還有信息素，信息素有兩種，一種是找到食物的螞蟻灑下的食物信息素，一種是找到窩的螞蟻灑下的窩的信息素。每個(gè)螞蟻都僅僅能感知它范圍內(nèi)的環(huán)境信息。環(huán)境以一定的速率讓信息素消失。
3、覓食規(guī)則：
在每只螞蟻能感知的范圍內(nèi)尋找是否有食物，如果有就直接過(guò)去。否則看是否有信息素，并且比較在能感知的范圍內(nèi)哪一點(diǎn)的信息素最多，這樣，它就朝信息素多的地方走，并且每只螞蟻多會(huì)以小概率犯錯(cuò)誤，從而并不是往信息素最多的點(diǎn)移動(dòng)。螞蟻找窩的規(guī)則和上面一樣，只不過(guò)它對(duì)窩的信息素做出反應(yīng)，而對(duì)食物信息素沒(méi)反應(yīng)。
4、移動(dòng)規(guī)則：
每只螞蟻都朝向信息素最多的方向移，并且，當(dāng)周圍沒(méi)有信息素指引的時(shí)候，螞蟻會(huì)按照自己原來(lái)運(yùn)動(dòng)的方向慣性的運(yùn)動(dòng)下去，并且，在運(yùn)動(dòng)的方向有一個(gè)隨機(jī)的小的擾動(dòng)。為了防止螞蟻原地轉(zhuǎn)圈，它會(huì)記住最近剛走過(guò)了哪些點(diǎn)，如果發(fā)現(xiàn)要走的下一點(diǎn)已經(jīng)在最近走過(guò)了，它就會(huì)盡量避開(kāi)。
5、避障規(guī)則：
如果螞蟻要移動(dòng)的方向有障礙物擋住，它會(huì)隨機(jī)的選擇另一個(gè)方向，并且有信息素指引的話，它會(huì)按照覓食的規(guī)則行為。
7、播撒信息素規(guī)則：
每只螞蟻在剛找到食物或者窩的時(shí)候撒發(fā)的信息素最多，并隨著它走遠(yuǎn)的距離，播撒的信息素越來(lái)越少。
根據(jù)這幾條規(guī)則，螞蟻之間并沒(méi)有直接的關(guān)系，但是每只螞蟻都和環(huán)境發(fā)生交互，而通過(guò)信息素這個(gè)紐帶，實(shí)際上把各個(gè)螞蟻之間關(guān)聯(lián)起來(lái)了。比如，當(dāng)一只螞蟻找到了食物，它并沒(méi)有直接告訴其它螞蟻這兒有食物，而是向環(huán)境播撒信息素，當(dāng)其它的螞蟻經(jīng)過(guò)它附近的時(shí)候，就會(huì)感覺(jué)到信息素的存在，進(jìn)而根據(jù)信息素的指引找到了食物。
問(wèn)題：
說(shuō)了這么多，螞蟻究竟是怎么找到食物的呢？
在沒(méi)有螞蟻找到食物的時(shí)候，環(huán)境沒(méi)有有用的信息素，那么螞蟻為什么會(huì)相對(duì)有效的找到食物呢？這要?dú)w功于螞蟻的移動(dòng)規(guī)則，尤其是在沒(méi)有信息素時(shí)候的移動(dòng)規(guī)則。首先，它要能盡量保持某種慣性，這樣使得螞蟻盡量向前方移動(dòng)（開(kāi)始，這個(gè)前方是隨機(jī)固定的一個(gè)方向），而不是原地?zé)o謂的打轉(zhuǎn)或者震動(dòng)；其次，螞蟻要有一定的隨機(jī)性，雖然有了固定的方向，但它也不能像粒子一樣直線運(yùn)動(dòng)下去，而是有一個(gè)隨機(jī)的干擾。這樣就使得螞蟻運(yùn)動(dòng)起來(lái)具有了一定的目的性，盡量保持原來(lái)的方向，但又有新的試探，尤其當(dāng)碰到障礙物的時(shí)候它會(huì)立即改變方向，這可以看成一種選擇的過(guò)程，也就是環(huán)境的障礙物讓螞蟻的某個(gè)方向正確，而其他方向則不對(duì)。這就解釋了為什么單個(gè)螞蟻在復(fù)雜的諸如迷宮的地圖中仍然能找到隱蔽得很好的食物。
當(dāng)然，在有一只螞蟻找到了食物的時(shí)候，其他螞蟻會(huì)沿著信息素很快找到食物的。
螞蟻如何找到最短路徑的？這一是要?dú)w功于信息素，另外要?dú)w功于環(huán)境，具體說(shuō)是計(jì)算機(jī)時(shí)鐘。信息素多的地方顯然經(jīng)過(guò)這里的螞蟻會(huì)多，因而會(huì)有更多的螞蟻聚集過(guò)來(lái)。假設(shè)有兩條路從窩通向食物，開(kāi)始的時(shí)候，走這兩條路的螞蟻數(shù)量同樣多（或者較長(zhǎng)的路上螞蟻多，這也無(wú)關(guān)緊要）。當(dāng)螞蟻沿著一條路到達(dá)終點(diǎn)以后會(huì)馬上返回來(lái)，這樣，短的路螞蟻來(lái)回一次的時(shí)間就短，這也意味著重復(fù)的頻率就快，因而在單位時(shí)間里走過(guò)的螞蟻數(shù)目就多，灑下的信息素自然也會(huì)多，自然會(huì)有更多的螞蟻被吸引過(guò)來(lái)，從而灑下更多的信息素……；而長(zhǎng)的路正相反，因此，越來(lái)越多地螞蟻聚集到較短的路徑上來(lái)，最短的路徑就近似找到了。也許有人會(huì)問(wèn)局部最短路徑和全局最短路的問(wèn)題，實(shí)際上螞蟻逐漸接近全局最短路的，為什么呢？這源于螞蟻會(huì)犯錯(cuò)誤，也就是它會(huì)按照一定的概率不往信息素高的地方走而另辟蹊徑，這可以理解為一種創(chuàng)新，這種創(chuàng)新如果能縮短路途，那么根據(jù)剛才敘述的原理，更多的螞蟻會(huì)被吸引過(guò)來(lái)。
引申:
跟著螞蟻的蹤跡，你找到了什么？通過(guò)上面的原理敘述和實(shí)際操作，我們不難發(fā)現(xiàn)螞蟻之所以具有智能行為，完全歸功于它的簡(jiǎn)單行為規(guī)則，而這些規(guī)則綜合起來(lái)具有下面兩個(gè)方面的特點(diǎn)：
1、多樣性
2、正反饋
多樣性保證了螞蟻在覓食的時(shí)候不置走進(jìn)死胡同而無(wú)限循環(huán)，正反饋機(jī)制則保證了相對(duì)優(yōu)良的信息能夠被保存下來(lái)。我們可以把多樣性看成是一種創(chuàng)造能力，而正反饋是一種學(xué)習(xí)強(qiáng)化能力。正反饋的力量也可以比喻成權(quán)威的意見(jiàn)，而多樣性是打破權(quán)威體現(xiàn)的創(chuàng)造性，正是這兩點(diǎn)小心翼翼的巧妙結(jié)合才使得智能行為涌現(xiàn)出來(lái)了。
引申來(lái)講，大自然的進(jìn)化，社會(huì)的進(jìn)步、人類的創(chuàng)新實(shí)際上都離不開(kāi)這兩樣?xùn)|西，多樣性保證了系統(tǒng)的創(chuàng)新能力，正反饋保證了優(yōu)良特性能夠得到強(qiáng)化，兩者要恰到好處的結(jié)合。如果多樣性過(guò)剩，也就是系統(tǒng)過(guò)于活躍，這相當(dāng)于螞蟻會(huì)過(guò)多的隨機(jī)運(yùn)動(dòng)，它就會(huì)陷入混沌狀態(tài)；而相反，多樣性不夠，正反饋機(jī)制過(guò)強(qiáng)，那么系統(tǒng)就好比一潭死水。這在蟻群中來(lái)講就表現(xiàn)為，螞蟻的行為過(guò)于僵硬，當(dāng)環(huán)境變化了，螞蟻群仍然不能適當(dāng)?shù)恼{(diào)整。
既然復(fù)雜性、智能行為是根據(jù)底層規(guī)則涌現(xiàn)的，既然底層規(guī)則具有多樣性和正反饋特點(diǎn)，那么也許你會(huì)問(wèn)這些規(guī)則是哪里來(lái)的？多樣性和正反饋又是哪里來(lái)的？我本人的意見(jiàn)：規(guī)則來(lái)源于大自然的進(jìn)化。而大自然的進(jìn)化根據(jù)剛才講的也體現(xiàn)為多樣性和正反饋的巧妙結(jié)合。而這樣的巧妙結(jié)合又是為什么呢？為什么在你眼前呈現(xiàn)的世界是如此栩栩如生呢？答案在于環(huán)境造就了這一切，之所以你看到栩栩如生的世界，是因?yàn)槟切┎荒軌蜻m應(yīng)環(huán)境的多樣性與正反饋的結(jié)合都已經(jīng)死掉了，被環(huán)境淘汰了！
參數(shù)說(shuō)明：
最大信息素：螞蟻在一開(kāi)始擁有的信息素總量，越大表示程序在較長(zhǎng)一段時(shí)間能夠存在信息素。信息素消減的速度：隨著時(shí)間的流逝，已經(jīng)存在于世界上的信息素會(huì)消減，這個(gè)數(shù)值越大，那么消減的越快。
錯(cuò)誤概率表示這個(gè)螞蟻不往信息素最大的區(qū)域走的概率，越大則表示這個(gè)螞蟻越有創(chuàng)新性。
速度半徑表示螞蟻一次能走的最大長(zhǎng)度，也表示這個(gè)螞蟻的感知范圍。
記憶能力表示螞蟻能記住多少個(gè)剛剛走過(guò)點(diǎn)的坐標(biāo)，這個(gè)值避免了螞蟻在本地打轉(zhuǎn)，停滯不前。而這個(gè)值越大那么整個(gè)系統(tǒng)運(yùn)行速度就慢，越小則螞蟻越容易原地轉(zhuǎn)圈。
2006.7.11 13:08 作者：xiao1jun收藏 | 評(píng)論：0
智能算法綜述
1 什么是智能算法
智能計(jì)算也有人稱之為“軟計(jì)算”，是們受自然（生物界）規(guī)律的啟迪，根據(jù)其原理，模仿求解問(wèn)題的算法。從自然界得到啟迪，模仿其結(jié)構(gòu)進(jìn)行發(fā)明創(chuàng)造，這就是仿生學(xué)。這是我們向自然界學(xué)習(xí)的一個(gè)方面。另一方面，我們還可以利用仿生原理進(jìn)行設(shè)計(jì)(包括設(shè)計(jì)算法)，這就是智能計(jì)算的思想。這方面的內(nèi)容很多，如人工神經(jīng)網(wǎng)絡(luò)技術(shù)、遺傳算法、模擬退火算法、模擬退火技術(shù)和群集智能技術(shù)等。
2 人工神經(jīng)網(wǎng)絡(luò)算法
“人工神經(jīng)網(wǎng)絡(luò)”(ARTIFICIAL NEURALNETWORK，簡(jiǎn)稱ANN)是在對(duì)人腦組織結(jié)構(gòu)和運(yùn)行機(jī)制的認(rèn)識(shí)理解基礎(chǔ)之上模擬其結(jié)構(gòu)和智能行為的一種工程系統(tǒng)。早在本世紀(jì)40年代初期，心理學(xué)家McCulloch、數(shù)學(xué)家Pitts就提出了人工神經(jīng)網(wǎng)絡(luò)的第一個(gè)數(shù)學(xué)模型，從此開(kāi)創(chuàng)了神經(jīng)科學(xué)理論的研究時(shí)代。其后，FRosenblatt、Widrow和J. J .Hopfield等學(xué)者又先后提出了感知模型，使得人工神經(jīng)網(wǎng)絡(luò)技術(shù)得以蓬勃發(fā)展。
神經(jīng)系統(tǒng)的基本構(gòu)造是神經(jīng)元(神經(jīng)細(xì)胞)，它是處理人體內(nèi)各部分之間相互信息傳遞的基本單元。據(jù)神經(jīng)生物學(xué)家研究的結(jié)果表明，人的一個(gè)大腦一般有1010～1011個(gè)神經(jīng)元。每個(gè)神經(jīng)元都由一個(gè)細(xì)胞體，一個(gè)連接其他神經(jīng)元的軸突和一些向外伸出的其它較短分支——樹(shù)突組成。軸突的功能是將本神經(jīng)元的輸出信號(hào)(興奮)傳遞給別的神經(jīng)元。其末端的許多神經(jīng)末梢使得興奮可以同時(shí)傳送給多個(gè)神經(jīng)元。樹(shù)突的功能是接受來(lái)自其它神經(jīng)元的興奮。神經(jīng)元細(xì)胞體將接受到的所有信號(hào)進(jìn)行簡(jiǎn)單處理(如：加權(quán)求和，即對(duì)所有的輸入信號(hào)都加以考慮且對(duì)每個(gè)信號(hào)的重視程度——體現(xiàn)在權(quán)值上——有所不同)后由軸突輸出。神經(jīng)元的樹(shù)突與另外的神經(jīng)元的神經(jīng)末梢相連的部分稱為突觸。
2.1 人工神經(jīng)網(wǎng)絡(luò)的特點(diǎn)
人工神經(jīng)網(wǎng)絡(luò)是由大量的神經(jīng)元廣泛互連而成的系統(tǒng)，它的這一結(jié)構(gòu)特點(diǎn)決定著人工神經(jīng)網(wǎng)絡(luò)具有高速信息處理的能力。人腦的每個(gè)神經(jīng)元大約有103～104個(gè)樹(shù)突及相應(yīng)的突觸，一個(gè)人的大腦總計(jì)約形成1014～1015個(gè)突觸。用神經(jīng)網(wǎng)絡(luò)的術(shù)語(yǔ)來(lái)說(shuō)，即是人腦具有1014～1015個(gè)互相連接的存儲(chǔ)潛力。雖然每個(gè)神經(jīng)元的運(yùn)算功能十分簡(jiǎn)單，且信號(hào)傳輸速率也較低(大約100次/秒)，但由于各神經(jīng)元之間的極度并行互連功能，最終使得一個(gè)普通人的大腦在約1秒內(nèi)就能完成現(xiàn)行計(jì)算機(jī)至少需要數(shù)10億次處理步驟才能完成的任務(wù)。
人工神經(jīng)網(wǎng)絡(luò)的知識(shí)存儲(chǔ)容量很大。在神經(jīng)網(wǎng)絡(luò)中，知識(shí)與信息的存儲(chǔ)表現(xiàn)為神經(jīng)元之間分布式的物理聯(lián)系。它分散地表示和存儲(chǔ)于整個(gè)網(wǎng)絡(luò)內(nèi)的各神經(jīng)元及其連線上。每個(gè)神經(jīng)元及其連線只表示一部分信息，而不是一個(gè)完整具體概念。只有通過(guò)各神經(jīng)元的分布式綜合效果才能表達(dá)出特定的概念和知識(shí)。
由于人工神經(jīng)網(wǎng)絡(luò)中神經(jīng)元個(gè)數(shù)眾多以及整個(gè)網(wǎng)絡(luò)存儲(chǔ)信息容量的巨大，使得它具有很強(qiáng)的不確定性信息處理能力。即使輸入信息不完全、不準(zhǔn)確或模糊不清，神經(jīng)網(wǎng)絡(luò)仍然能夠聯(lián)想思維存在于記憶中的事物的完整圖象。只要輸入的模式接近于訓(xùn)練樣本，系統(tǒng)就能給出正確的推理結(jié)論。
正是因?yàn)槿斯ど窠?jīng)網(wǎng)絡(luò)的結(jié)構(gòu)特點(diǎn)和其信息存儲(chǔ)的分布式特點(diǎn)，使得它相對(duì)于其它的判斷識(shí)別系統(tǒng)，如：專家系統(tǒng)等，具有另一個(gè)顯著的優(yōu)點(diǎn)：健壯性。生物神經(jīng)網(wǎng)絡(luò)不會(huì)因?yàn)閭€(gè)別神經(jīng)元的損失而失去對(duì)原有模式的記憶。最有力的證明是，當(dāng)一個(gè)人的大腦因意外事故受輕微損傷之后，并不會(huì)失去原有事物的全部記憶。人工神經(jīng)網(wǎng)絡(luò)也有類似的情況。因某些原因，無(wú)論是網(wǎng)絡(luò)的硬件實(shí)現(xiàn)還是軟件實(shí)現(xiàn)中的某個(gè)或某些神經(jīng)元失效，整個(gè)網(wǎng)絡(luò)仍然能繼續(xù)工作。
人工神經(jīng)網(wǎng)絡(luò)是一種非線性的處理單元。只有當(dāng)神經(jīng)元對(duì)所有的輸入信號(hào)的綜合處理結(jié)果超過(guò)某一門(mén)限值后才輸出一個(gè)信號(hào)。因此神經(jīng)網(wǎng)絡(luò)是一種具有高度非線性的超大規(guī)模連續(xù)時(shí)間動(dòng)力學(xué)系統(tǒng)。它突破了傳統(tǒng)的以線性處理為基礎(chǔ)的數(shù)字電子計(jì)算機(jī)的局限，標(biāo)志著人們智能信息處理能力和模擬人腦智能行為能力的一大飛躍。
2.2 幾種典型神經(jīng)網(wǎng)絡(luò)簡(jiǎn)介
2.2.1 多層感知網(wǎng)絡(luò)(誤差逆?zhèn)鞑ド窠?jīng)網(wǎng)絡(luò))
在1986年以Rumelhart和McCelland為首的科學(xué)家出版的《ParallelDistributed Processing》一書(shū)中，完整地提出了誤差逆?zhèn)鞑W(xué)習(xí)算法，并被廣泛接受。多層感知網(wǎng)絡(luò)是一種具有三層或三層以上的階層型神經(jīng)網(wǎng)絡(luò)。典型的多層感知網(wǎng)絡(luò)是三層、前饋的階層網(wǎng)絡(luò)，即：輸入層I、隱含層(也稱中間層)J和輸出層K。相鄰層之間的各神經(jīng)元實(shí)現(xiàn)全連接，即下一層的每一個(gè)神經(jīng)元與上一層的每個(gè)神經(jīng)元都實(shí)現(xiàn)全連接，而且每層各神經(jīng)元之間無(wú)連接。
但BP網(wǎng)并不是十分的完善，它存在以下一些主要缺陷：學(xué)習(xí)收斂速度太慢、網(wǎng)絡(luò)的學(xué)習(xí)記憶具有不穩(wěn)定性，即：當(dāng)給一個(gè)訓(xùn)練好的網(wǎng)提供新的學(xué)習(xí)記憶模式時(shí)，將使已有的連接權(quán)值被打亂，導(dǎo)致已記憶的學(xué)習(xí)模式的信息的消失。
2.2.2 競(jìng)爭(zhēng)型(KOHONEN)神經(jīng)網(wǎng)絡(luò)
它是基于人的視網(wǎng)膜及大腦皮層對(duì)剌激的反應(yīng)而引出的。神經(jīng)生物學(xué)的研究結(jié)果表明：生物視網(wǎng)膜中，有許多特定的細(xì)胞，對(duì)特定的圖形(輸入模式)比較敏感，并使得大腦皮層中的特定細(xì)胞產(chǎn)生大的興奮，而其相鄰的神經(jīng)細(xì)胞的興奮程度被抑制。對(duì)于某一個(gè)輸入模式，通過(guò)競(jìng)爭(zhēng)在輸出層中只激活一個(gè)相應(yīng)的輸出神經(jīng)元。許多輸入模式，在輸出層中將激活許多個(gè)神經(jīng)元，從而形成一個(gè)反映輸入數(shù)據(jù)的“特征圖形”。競(jìng)爭(zhēng)型神經(jīng)網(wǎng)絡(luò)是一種以無(wú)教師方式進(jìn)行網(wǎng)絡(luò)訓(xùn)練的網(wǎng)絡(luò)。它通過(guò)自身訓(xùn)練，自動(dòng)對(duì)輸入模式進(jìn)行分類。競(jìng)爭(zhēng)型神經(jīng)網(wǎng)絡(luò)及其學(xué)習(xí)規(guī)則與其它類型的神經(jīng)網(wǎng)絡(luò)和學(xué)習(xí)規(guī)則相比，有其自己的鮮明特點(diǎn)。在網(wǎng)絡(luò)結(jié)構(gòu)上，它既不象階層型神經(jīng)網(wǎng)絡(luò)那樣各層神經(jīng)元之間只有單向連接，也不象全連接型網(wǎng)絡(luò)那樣在網(wǎng)絡(luò)結(jié)構(gòu)上沒(méi)有明顯的層次界限。它一般是由輸入層(模擬視網(wǎng)膜神經(jīng)元)和競(jìng)爭(zhēng)層(模擬大腦皮層神經(jīng)元，也叫輸出層)構(gòu)成的兩層網(wǎng)絡(luò)。兩層之間的各神經(jīng)元實(shí)現(xiàn)雙向全連接，而且網(wǎng)絡(luò)中沒(méi)有隱含層。有時(shí)競(jìng)爭(zhēng)層各神經(jīng)元之間還存在橫向連接。競(jìng)爭(zhēng)型神經(jīng)網(wǎng)絡(luò)的基本思想是網(wǎng)絡(luò)競(jìng)爭(zhēng)層各神經(jīng)元競(jìng)爭(zhēng)對(duì)輸入模式的響應(yīng)機(jī)會(huì)，最后僅有一個(gè)神經(jīng)元成為競(jìng)爭(zhēng)的勝者，并且只將與獲勝神經(jīng)元有關(guān)的各連接權(quán)值進(jìn)行修正，使之朝著更有利于它競(jìng)爭(zhēng)的方向調(diào)整。神經(jīng)網(wǎng)絡(luò)工作時(shí)，對(duì)于某一輸入模式，網(wǎng)絡(luò)中與該模式最相近的學(xué)習(xí)輸入模式相對(duì)應(yīng)的競(jìng)爭(zhēng)層神經(jīng)元將有最大的輸出值，即以競(jìng)爭(zhēng)層獲勝神經(jīng)元來(lái)表示分類結(jié)果。這是通過(guò)競(jìng)爭(zhēng)得以實(shí)現(xiàn)的，實(shí)際上也就是網(wǎng)絡(luò)回憶聯(lián)想的過(guò)程。
除了競(jìng)爭(zhēng)的方法外，還有通過(guò)抑制手段獲取勝利的方法，即網(wǎng)絡(luò)競(jìng)爭(zhēng)層各神經(jīng)元抑制所有其它神經(jīng)元對(duì)輸入模式的響應(yīng)機(jī)會(huì)，從而使自己“脫穎而出”，成為獲勝神經(jīng)元。除此之外還有一種稱為側(cè)抑制的方法，即每個(gè)神經(jīng)元只抑制與自己鄰近的神經(jīng)元，而對(duì)遠(yuǎn)離自己的神經(jīng)元不抑制。這種方法常常用于圖象邊緣處理，解決圖象邊緣的缺陷問(wèn)題。
競(jìng)爭(zhēng)型神經(jīng)網(wǎng)絡(luò)的缺點(diǎn)和不足：因?yàn)樗鼉H以輸出層中的單個(gè)神經(jīng)元代表某一類模式。所以一旦輸出層中的某個(gè)輸出神經(jīng)元損壞，則導(dǎo)致該神經(jīng)元所代表的該模式信息全部丟失。
2.2.3 Hopfield神經(jīng)網(wǎng)絡(luò)
1986年美國(guó)物理學(xué)家J.J.Hopfield陸續(xù)發(fā)表幾篇論文，提出了Hopfield神經(jīng)網(wǎng)絡(luò)。他利用非線性動(dòng)力學(xué)系統(tǒng)理論中的能量函數(shù)方法研究反饋人工神經(jīng)網(wǎng)絡(luò)的穩(wěn)定性，并利用此方法建立求解優(yōu)化計(jì)算問(wèn)題的系統(tǒng)方程式。基本的Hopfield神經(jīng)網(wǎng)絡(luò)是一個(gè)由非線性元件構(gòu)成的全連接型單層反饋系統(tǒng)。
網(wǎng)絡(luò)中的每一個(gè)神經(jīng)元都將自己的輸出通過(guò)連接權(quán)傳送給所有其它神經(jīng)元，同時(shí)又都接收所有其它神經(jīng)元傳遞過(guò)來(lái)的信息。即：網(wǎng)絡(luò)中的神經(jīng)元t時(shí)刻的輸出狀態(tài)實(shí)際上間接地與自己的t-1時(shí)刻的輸出狀態(tài)有關(guān)。所以Hopfield神經(jīng)網(wǎng)絡(luò)是一個(gè)反饋型的網(wǎng)絡(luò)。其狀態(tài)變化可以用差分方程來(lái)表征。反饋型網(wǎng)絡(luò)的一個(gè)重要特點(diǎn)就是它具有穩(wěn)定狀態(tài)。當(dāng)網(wǎng)絡(luò)達(dá)到穩(wěn)定狀態(tài)的時(shí)候，也就是它的能量函數(shù)達(dá)到最小的時(shí)候。這里的能量函數(shù)不是物理意義上的能量函數(shù)，而是在表達(dá)形式上與物理意義上的能量概念一致，表征網(wǎng)絡(luò)狀態(tài)的變化趨勢(shì)，并可以依據(jù)Hopfield工作運(yùn)行規(guī)則不斷進(jìn)行狀態(tài)變化，最終能夠達(dá)到的某個(gè)極小值的目標(biāo)函數(shù)。網(wǎng)絡(luò)收斂就是指能量函數(shù)達(dá)到極小值。如果把一個(gè)最優(yōu)化問(wèn)題的目標(biāo)函數(shù)轉(zhuǎn)換成網(wǎng)絡(luò)的能量函數(shù)，把問(wèn)題的變量對(duì)應(yīng)于網(wǎng)絡(luò)的狀態(tài)，那么Hopfield神經(jīng)網(wǎng)絡(luò)就能夠用于解決優(yōu)化組合問(wèn)題。
對(duì)于同樣結(jié)構(gòu)的網(wǎng)絡(luò)，當(dāng)網(wǎng)絡(luò)參數(shù)(指連接權(quán)值和閥值)有所變化時(shí)，網(wǎng)絡(luò)能量函數(shù)的極小點(diǎn)(稱為網(wǎng)絡(luò)的穩(wěn)定平衡點(diǎn))的個(gè)數(shù)和極小值的大小也將變化。因此，可以把所需記憶的模式設(shè)計(jì)成某個(gè)確定網(wǎng)絡(luò)狀態(tài)的一個(gè)穩(wěn)定平衡點(diǎn)。若網(wǎng)絡(luò)有M個(gè)平衡點(diǎn)，則可以記憶M個(gè)記憶模式。
當(dāng)網(wǎng)絡(luò)從與記憶模式較靠近的某個(gè)初始狀態(tài)(相當(dāng)于發(fā)生了某些變形或含有某些噪聲的記憶模式，也即：只提供了某個(gè)模式的部分信息)出發(fā)后，網(wǎng)絡(luò)按Hopfield工作運(yùn)行規(guī)則進(jìn)行狀態(tài)更新，最后網(wǎng)絡(luò)的狀態(tài)將穩(wěn)定在能量函數(shù)的極小點(diǎn)。這樣就完成了由部分信息的聯(lián)想過(guò)程。
Hopfield神經(jīng)網(wǎng)絡(luò)的能量函數(shù)是朝著梯度減小的方向變化，但它仍然存在一個(gè)問(wèn)題，那就是一旦能量函數(shù)陷入到局部極小值，它將不能自動(dòng)跳出局部極小點(diǎn)，到達(dá)全局最小點(diǎn)，因而無(wú)法求得網(wǎng)絡(luò)最優(yōu)解。
3 遺傳算法
遺傳算法（Genetic Algorithms）是基于生物進(jìn)化理論的原理發(fā)展起來(lái)的一種廣為應(yīng)用的、高效的隨機(jī)搜索與優(yōu)化的方法。其主要特點(diǎn)是群體搜索策略和群體中個(gè)體之間的信息交換，搜索不依賴于梯度信息。它是在70年代初期由美國(guó)密執(zhí)根（Michigan）大學(xué)的霍蘭（Holland）教授發(fā)展起來(lái)的。1975年霍蘭教授發(fā)表了第一本比較系統(tǒng)論述遺傳算法的專著《自然系統(tǒng)與人工系統(tǒng)中的適應(yīng)性》（《Adaptationin Natural and Artificial Systems》）。遺傳算法最初被研究的出發(fā)點(diǎn)不是為專門(mén)解決最優(yōu)化問(wèn)題而設(shè)計(jì)的，它與進(jìn)化策略、進(jìn)化規(guī)劃共同構(gòu)成了進(jìn)化算法的主要框架，都是為當(dāng)時(shí)人工智能的發(fā)展服務(wù)的。迄今為止，遺傳算法是進(jìn)化算法中最廣為人知的算法。
近幾年來(lái)，遺傳算法主要在復(fù)雜優(yōu)化問(wèn)題求解和工業(yè)工程領(lǐng)域應(yīng)用方面，取得了一些令人信服的結(jié)果，所以引起了很多人的關(guān)注。在發(fā)展過(guò)程中，進(jìn)化策略、進(jìn)化規(guī)劃和遺傳算法之間差異越來(lái)越小。遺傳算法成功的應(yīng)用包括：作業(yè)調(diào)度與排序、可靠性設(shè)計(jì)、車輛路徑選擇與調(diào)度、成組技術(shù)、設(shè)備布置與分配、交通問(wèn)題等等。
3.1 特點(diǎn)
遺傳算法是解決搜索問(wèn)題的一種通用算法，對(duì)于各種通用問(wèn)題都可以使用。搜索算法的共同特征為： ① 首先組成一組候選解； ② 依據(jù)某些適應(yīng)性條件測(cè)算這些候選解的適應(yīng)度； ③ 根據(jù)適應(yīng)度保留某些候選解，放棄其他候選解； ④ 對(duì)保留的候選解進(jìn)行某些操作，生成新的候選解。在遺傳算法中，上述幾個(gè)特征以一種特殊的方式組合在一起：基于染色體群的并行搜索，帶有猜測(cè)性質(zhì)的選擇操作、交換操作和突變操作。這種特殊的組合方式將遺傳算法與其它搜索算法區(qū)別開(kāi)來(lái)。
遺傳算法還具有以下幾方面的特點(diǎn)：
(1)遺傳算法從問(wèn)題解的串集開(kāi)始嫂索，而不是從單個(gè)解開(kāi)始。這是遺傳算法與傳統(tǒng)優(yōu)化算法的極大區(qū)別。傳統(tǒng)優(yōu)化算法是從單個(gè)初始值迭代求最優(yōu)解的；容易誤入局部最優(yōu)解。遺傳算法從串集開(kāi)始搜索，覆蓋面大，利于全局擇優(yōu)。
(2)許多傳統(tǒng)搜索算法都是單點(diǎn)搜索算法，容易陷入局部的最優(yōu)解。遺傳算法同時(shí)處理群體中的多個(gè)個(gè)體，即對(duì)搜索空間中的多個(gè)解進(jìn)行評(píng)估，減少了陷入局部最優(yōu)解的風(fēng)險(xiǎn)，同時(shí)算法本身易于實(shí)現(xiàn)并行化。
(3)遺傳算法基本上不用搜索空間的知識(shí)或其它輔助信息，而僅用適應(yīng)度函數(shù)值來(lái)評(píng)估個(gè)體，在此基礎(chǔ)上進(jìn)行遺傳操作。適應(yīng)度函數(shù)不僅不受連續(xù)可微的約束，而且其定義域可以任意設(shè)定。這一特點(diǎn)使得遺傳算法的應(yīng)用范圍大大擴(kuò)展。
(4)遺傳算法不是采用確定性規(guī)則，而是采用概率的變遷規(guī)則來(lái)指導(dǎo)他的搜索方向。
(5)具有自組織、自適應(yīng)和自學(xué)習(xí)性。遺傳算法利用進(jìn)化過(guò)程獲得的信息自行組織搜索時(shí)，硬度大的個(gè)體具有較高的生存概率，并獲得更適應(yīng)環(huán)境的基因結(jié)構(gòu)。
3.2 運(yùn)用領(lǐng)域
前面描述是簡(jiǎn)單的遺傳算法模型，可以在這一基本型上加以改進(jìn)，使其在科學(xué)和工程領(lǐng)域得到廣泛應(yīng)用。下面列舉了一些遺傳算法的應(yīng)用領(lǐng)域： ① 優(yōu)化：遺傳算法可用于各種優(yōu)化問(wèn)題。既包括數(shù)量?jī)?yōu)化問(wèn)題，也包括組合優(yōu)化問(wèn)題。 ② 程序設(shè)計(jì)：遺傳算法可以用于某些特殊任務(wù)的計(jì)算機(jī)程序設(shè)計(jì)。 ③ 機(jī)器學(xué)習(xí)：遺傳算法可用于許多機(jī)器學(xué)習(xí)的應(yīng)用，包括分類問(wèn)題和預(yù)測(cè)問(wèn)題等。 ④ 經(jīng)濟(jì)學(xué)：應(yīng)用遺傳算法對(duì)經(jīng)濟(jì)創(chuàng)新的過(guò)程建立模型，可以研究投標(biāo)的策略，還可以建立市場(chǎng)競(jìng)爭(zhēng)的模型。 ⑤ 免疫系統(tǒng)：應(yīng)用遺傳算法可以對(duì)自然界中免疫系統(tǒng)的多個(gè)方面建立模型，研究個(gè)體的生命過(guò)程中的突變現(xiàn)象以及發(fā)掘進(jìn)化過(guò)程中的基因資源。 ⑥ 進(jìn)化現(xiàn)象和學(xué)習(xí)現(xiàn)象：遺傳算法可以用來(lái)研究個(gè)體是如何學(xué)習(xí)生存技巧的，一個(gè)物種的進(jìn)化對(duì)其他物種會(huì)產(chǎn)生何種影響等等。 ⑦ 社會(huì)經(jīng)濟(jì)問(wèn)題：遺傳算法可以用來(lái)研究社會(huì)系統(tǒng)中的各種演化現(xiàn)象，例如在一個(gè)多主體系統(tǒng)中，協(xié)作與交流是如何演化出來(lái)的。
4 模擬退火算法
模擬退火算法來(lái)源于固體退火原理，將固體加溫至充分高，再讓其徐徐冷卻，加溫時(shí)，固體內(nèi)部粒子隨溫升變?yōu)闊o(wú)序狀，內(nèi)能增大，而徐徐冷卻時(shí)粒子漸趨有序，在每個(gè)溫度都達(dá)到平衡態(tài)，最后在常溫時(shí)達(dá)到基態(tài)，內(nèi)能減為最小。根據(jù)Metropolis準(zhǔn)則，粒子在溫度T時(shí)趨于平衡的概率為e-ΔE/(kT)，其中E為溫度T時(shí)的內(nèi)能，ΔE為其改變量，k為Boltzmann常數(shù)。用固體退火模擬組合優(yōu)化問(wèn)題，將內(nèi)能E模擬為目標(biāo)函數(shù)值f ，溫度T演化成控制參數(shù)t，即得到解組合優(yōu)化問(wèn)題的模擬退火算法：由初始解i和控制參數(shù)初值t開(kāi)始，對(duì)當(dāng)前解重復(fù)“產(chǎn)生新解→計(jì)算目標(biāo)函數(shù)差→接受或舍棄”的迭代，并逐步衰減t值，算法終止時(shí)的當(dāng)前解即為所得近似最優(yōu)解，這是基于蒙特卡羅迭代求解法的一種啟發(fā)式隨機(jī)搜索過(guò)程。退火過(guò)程由冷卻進(jìn)度表(CoolingSchedule)控制，包括控制參數(shù)的初值t及其衰減因子Δt、每個(gè)t值時(shí)的迭代次數(shù)L和停止條件S。
5 群體（群集）智能（Swarm Intelligence）
受社會(huì)性昆蟲(chóng)行為的啟發(fā)，計(jì)算機(jī)工作者通過(guò)對(duì)社會(huì)性昆蟲(chóng)的模擬產(chǎn)生了一系列對(duì)于傳統(tǒng)問(wèn)題的新的解決方法，這些研究就是群集智能的研究。群集智能(Swarm Intelligence)中的群體(Swarm)指的是“一組相互之間可以進(jìn)行直接通信或者間接通信(通過(guò)改變局部環(huán)境)的主體，這組主體能夠合作進(jìn)行分布問(wèn)題求解”。而所謂群集智能指的是“無(wú)智能的主體通過(guò)合作表現(xiàn)出智能行為的特性”。群集智能在沒(méi)有集中控制并且不提供全局模型的前提下，為尋找復(fù)雜的分布式問(wèn)題的解決方案提供了基礎(chǔ)。
群集智能的特點(diǎn)和優(yōu)點(diǎn)：群體中相互合作的個(gè)體是分布式的(Distributed)，這樣更能夠適應(yīng)當(dāng)前網(wǎng)絡(luò)環(huán)境下的工作狀態(tài); 沒(méi)有中心的控制與數(shù)據(jù)，這樣的系統(tǒng)更具有魯棒性(Robust)，不會(huì)由于某一個(gè)或者某幾個(gè)個(gè)體的故障而影響整個(gè)問(wèn)題的求解。可以不通過(guò)個(gè)體之間直接通信而是通過(guò)非直接通信(Stimergy)進(jìn)行合作，這樣的系統(tǒng)具有更好的可擴(kuò)充性(Scalability)。由于系統(tǒng)中個(gè)體的增加而增加的系統(tǒng)的通信開(kāi)銷在這里十分小。系統(tǒng)中每個(gè)個(gè)體的能力十分簡(jiǎn)單，這樣每個(gè)個(gè)體的執(zhí)行時(shí)間比較短，并且實(shí)現(xiàn)也比較簡(jiǎn)單，具有簡(jiǎn)單性(Simplicity)。因?yàn)榫哂羞@些優(yōu)點(diǎn)，雖說(shuō)群集智能的研究還處于初級(jí)階段，并且存在許多困難，但是可以預(yù)言群集智能的研究代表了以后計(jì)算機(jī)研究發(fā)展的一個(gè)重要方向。
在計(jì)算智能(ComputationalIntelligence)領(lǐng)域有兩種基于群智能的算法，蟻群算法(Ant Colony Optimization)和粒子群算法(ParticleSwarm Optimization)，前者是對(duì)螞蟻群落食物采集過(guò)程的模擬，已經(jīng)成功運(yùn)用在很多離散優(yōu)化問(wèn)題上。
5.1 蟻群優(yōu)化算法
受螞蟻覓食時(shí)的通信機(jī)制的啟發(fā)，90年代Dorigo提出了蟻群優(yōu)化算法(Ant ColonyOptimization，ACO)來(lái)解決計(jì)算機(jī)算法學(xué)中經(jīng)典的“貨郎擔(dān)問(wèn)題”。如果有n個(gè)城市，需要對(duì)所有n個(gè)城市進(jìn)行訪問(wèn)且只訪問(wèn)一次的最短距離。
在解決貨郎擔(dān)問(wèn)題時(shí)，蟻群優(yōu)化算法設(shè)計(jì)虛擬的“螞蟻”將摸索不同路線，并留下會(huì)隨時(shí)間逐漸消失的虛擬“信息素”。虛擬的“信息素”也會(huì)揮發(fā)，每只螞蟻每次隨機(jī)選擇要走的路徑，它們傾向于選擇路徑比較短的、信息素比較濃的路徑。根據(jù)“信息素較濃的路線更近"的原則，即可選擇出最佳路線。由于這個(gè)算法利用了正反饋機(jī)制，使得較短的路徑能夠有較大的機(jī)會(huì)得到選擇，并且由于采用了概率算法，所以它能夠不局限于局部最優(yōu)解。
蟻群優(yōu)化算法對(duì)于解決貨郎擔(dān)問(wèn)題并不是目前最好的方法，但首先，它提出了一種解決貨郎擔(dān)問(wèn)題的新思路；其次由于這種算法特有的解決方法，它已經(jīng)被成功用于解決其他組合優(yōu)化問(wèn)題，例如圖的著色(GraphColoring)以及最短超串(Shortest Common Supersequence)等問(wèn)題。
5.2 粒子群優(yōu)化算法
粒子群優(yōu)化算法(PSO)是一種進(jìn)化計(jì)算技術(shù)(EvolutionaryComputation)，有Eberhart博士和Kennedy博士發(fā)明。源于對(duì)鳥(niǎo)群捕食的行為研究。
PSO同遺傳算法類似，是一種基于疊代的優(yōu)化工具。系統(tǒng)初始化為一組隨機(jī)解，通過(guò)疊代搜尋最優(yōu)值。但是并沒(méi)有遺傳算法用的交叉(crossover)以及變異(mutation)。而是粒子在解空間追隨最優(yōu)的粒子進(jìn)行搜索。
同遺傳算法比較，PSO的優(yōu)勢(shì)在于簡(jiǎn)單容易實(shí)現(xiàn)并且沒(méi)有許多參數(shù)需要調(diào)整。目前已廣泛應(yīng)用于函數(shù)優(yōu)化，神經(jīng)網(wǎng)絡(luò)訓(xùn)練，模糊系統(tǒng)控制以及其他遺傳算法的應(yīng)用領(lǐng)域。
粒子群優(yōu)化算法(PSO) 也是起源對(duì)簡(jiǎn)單社會(huì)系統(tǒng)的模擬，最初設(shè)想是模擬鳥(niǎo)群覓食的過(guò)程，但后來(lái)發(fā)現(xiàn)PSO是一種很好的優(yōu)化工具。
5.2.1 算法介紹
PSO模擬鳥(niǎo)群的捕食行為。一群鳥(niǎo)在隨機(jī)搜索食物，在這個(gè)區(qū)域里只有一塊食物。所有的鳥(niǎo)都不知道食物在那里。但是他們知道當(dāng)前的位置離食物還有多遠(yuǎn)。那么找到食物的最優(yōu)策略是什么呢。最簡(jiǎn)單有效的就是搜尋目前離食物最近的鳥(niǎo)的周圍區(qū)域。
PSO從這種模型中得到啟示并用于解決優(yōu)化問(wèn)題。PSO中，每個(gè)優(yōu)化問(wèn)題的解都是搜索空間中的一只鳥(niǎo)。我們稱之為“粒子”。所有的粒子都有一個(gè)由被優(yōu)化的函數(shù)決定的適應(yīng)值(fitnessvalue)，每個(gè)粒子還有一個(gè)速度決定他們飛翔的方向和距離。然后粒子們就追隨當(dāng)前的最優(yōu)粒子在解空間中搜索。
PSO初始化為一群隨機(jī)粒子(隨機(jī)解)，然后通過(guò)疊代找到最優(yōu)解，在每一次疊代中，粒子通過(guò)跟蹤兩個(gè)“極值”來(lái)更新自己。第一個(gè)就是粒子本身所找到的最優(yōu)解，這個(gè)解叫做個(gè)體極值pBest，另一個(gè)極值是整個(gè)種群目前找到的最優(yōu)解，這個(gè)極值是全局極值gBest。另外也可以不用整個(gè)種群而只是用其中一部分最優(yōu)粒子的鄰居，那么在所有鄰居中的極值就是局部極值。
5.2.2 PSO算法過(guò)程
① 種群隨機(jī)初始化。
② 對(duì)種群內(nèi)的每一個(gè)個(gè)體計(jì)算適應(yīng)值(fitness value)。適應(yīng)值與最優(yōu)解的距離直接有關(guān)。
③ 種群根據(jù)適應(yīng)值進(jìn)行復(fù)制 。
④ 如果終止條件滿足的話，就停止，否則轉(zhuǎn)步驟 ② 。
從以上步驟，我們可以看到PSO和遺傳算法有很多共同之處。兩者都隨機(jī)初始化種群，而且都使用適應(yīng)值來(lái)評(píng)價(jià)系統(tǒng)，而且都根據(jù)適應(yīng)值來(lái)進(jìn)行一定的隨機(jī)搜索。兩個(gè)系統(tǒng)都不是保證一定找到最優(yōu)解。但是，PSO沒(méi)有遺傳操作如交叉(crossover)和變異(mutation)，而是根據(jù)自己的速度來(lái)決定搜索。粒子還有一個(gè)重要的特點(diǎn)，就是有記憶。
與遺傳算法比較，PSO的信息共享機(jī)制是很不同的。在遺傳算法中，染色體(chromosomes)互相共享信息，所以整個(gè)種群的移動(dòng)是比較均勻的向最優(yōu)區(qū)域移動(dòng)。在PSO中, 只有g(shù)Best (orlBest) 給出信息給其他的粒子， 這是單向的信息流動(dòng)。整個(gè)搜索更新過(guò)程是跟隨當(dāng)前最優(yōu)解的過(guò)程。與遺傳算法比較, 在大多數(shù)的情況下，所有的粒子可能更快的收斂于最優(yōu)解。
現(xiàn)在已經(jīng)有一些利用PSO代替反向傳播算法來(lái)訓(xùn)練神經(jīng)網(wǎng)絡(luò)的論文。研究表明PSO 是一種很有潛力的神經(jīng)網(wǎng)絡(luò)算法，同時(shí)PSO速度比較快而且可以得到比較好的結(jié)果。
6 展望
目前的智能計(jì)算研究水平暫時(shí)還很難使“智能機(jī)器”真正具備人類的常識(shí)，但智能計(jì)算將在21世紀(jì)蓬勃發(fā)展。不僅僅只是功能模仿要持有信息機(jī)理一致的觀點(diǎn)。即人工腦與生物腦將不只是功能模仿，而是具有相同的特性。這兩者的結(jié)合將開(kāi)辟一個(gè)全新的領(lǐng)域，開(kāi)辟很多新的研究方向。智能計(jì)算將探索智能的新概念，新理論，新方法和新技術(shù)，而這一切將在以后的發(fā)展中取得重大成就。
總結(jié)
- 上一篇： 蚁群算法，PSO算法以及两种算法可以融合
- 下一篇： 提高效率的几个软件和快捷键