第10講智能優(yōu)化算法簡(jiǎn)介

智能優(yōu)化算法簡(jiǎn)介

山東輕工業(yè)學(xué)院數(shù)理學(xué)院

李彬自二十世紀(jì)七十年代末以來(lái)發(fā)展起來(lái)一些非傳統(tǒng)的優(yōu)化方法，這些方法都是根據(jù)某些物理或生物現(xiàn)象的啟發(fā)而設(shè)計(jì)的，采用這些方法可以較充分的利用目標(biāo)函數(shù)的全局信息，從而解決上述問(wèn)題，這些方法主要包括：1、遺傳算法：這種方法是模擬自然界生物體的遺傳和變異過(guò)程而得到的.2、模擬退火：這種方法是模擬統(tǒng)計(jì)物理中的退火過(guò)程而設(shè)計(jì)的。3、人工神經(jīng)網(wǎng)絡(luò)：其中的某些模型比如Hopfield網(wǎng)絡(luò)可以用來(lái)處理優(yōu)化問(wèn)題.4、禁忌搜索：這是模擬有記憶的智能過(guò)程的方法.5、蟻群算法：這是模擬螞蟻尋找最優(yōu)路徑而設(shè)計(jì)的方法.引言局部搜索，模擬退火，遺傳算法，禁忌搜索的形象比喻：

為了找出地球上最高的山，一群有志氣的兔子們開(kāi)始想辦法.1．兔子朝著比現(xiàn)在高的地方跳去.他們找到了不遠(yuǎn)處的最高山峰.但是這座山不一定是珠穆朗瑪峰.這就是局部搜索，它不能保證局部最優(yōu)值就是全局最優(yōu)值.引言局部搜索，模擬退火，遺傳算法，禁忌搜索的形象比喻：

為了找出地球上最高的山，一群有志氣的兔子們開(kāi)始想辦法.

2．兔子喝醉了.他隨機(jī)地跳了很長(zhǎng)時(shí)間.這期間，它可能走向高處，也可能踏入平地。但是，他漸漸清醒了并朝最高方向跳去.這就是模擬退火.引言局部搜索，模擬退火，遺傳算法，禁忌搜索的形象比喻：

為了找出地球上最高的山，一群有志氣的兔子們開(kāi)始想辦法.

3．兔子們吃了失憶藥片，并被發(fā)射到太空，然后隨機(jī)落到了地球上的某些地方.他們不知道自己的使命是什么.但是，如果你過(guò)幾年就殺死一部分海拔低的兔子，多產(chǎn)的兔子們自己就會(huì)找到珠穆朗瑪峰.這就是遺傳算法.

引言局部搜索，模擬退火，遺傳算法，禁忌搜索的形象比喻：

為了找出地球上最高的山，一群有志氣的兔子們開(kāi)始想辦法.

4.兔子們知道一個(gè)兔的力量是渺小的.他們互相轉(zhuǎn)告著，哪里的山已經(jīng)找過(guò)，并且找過(guò)的每一座山他們都留下一只兔子做記號(hào).他們制定了下一步去哪里尋找的策略.這就是禁忌搜索.

引言群體智能的定義受社會(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)出智能行為的特性”.

1.群體中相互合作的個(gè)體是分布式的(Distributed)，這樣更能夠適應(yīng)當(dāng)前環(huán)境下的工作狀態(tài);

2.沒(méi)有中心的控制與數(shù)據(jù)，這樣的系統(tǒng)更具有魯棒性(Robust)，不會(huì)由于某一個(gè)或者某幾個(gè)個(gè)體的故障而影響整個(gè)問(wèn)題的求解.3.可以不通過(guò)個(gè)體之間直接通信而是通過(guò)非直接通信進(jìn)行合作，這樣的系統(tǒng)具有更好的可擴(kuò)充性.4.由于系統(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).群體智能的特點(diǎn)和優(yōu)點(diǎn)在計(jì)算智能(Computational

Intelligence)領(lǐng)域有兩種基于群智能的算法：蟻群算法(Ant

Colony

Optimization)

是對(duì)螞蟻群落食物采集過(guò)程的模擬，已經(jīng)成功運(yùn)用在很多離散優(yōu)化問(wèn)題上.

粒子群優(yōu)化算法(Particle

Swarm

Optimization，PSO)是一種進(jìn)化計(jì)算技術(shù)(Evolutionary

Computation)，由Eberhart博士和Kennedy博士發(fā)明.源于對(duì)鳥(niǎo)群捕食的行為研究.

群體智能算法1蟻群算法原理

蟻群算法是對(duì)自然界螞蟻的尋徑方式進(jìn)行模似而得出的一種仿生算法。螞蟻在運(yùn)動(dòng)過(guò)程中，能夠在它所經(jīng)過(guò)的路徑上留下一種稱之為外激素(pheromone)的物質(zhì)進(jìn)行信息傳遞，而且螞蟻在運(yùn)動(dòng)過(guò)程中能夠感知這種物質(zhì)，并以此指導(dǎo)自己的運(yùn)動(dòng)方向，因此由大量螞蟻組成的蟻群集體行為便表現(xiàn)出一種信息正反饋現(xiàn)象：某一路徑上走過(guò)的螞蟻越多，則后來(lái)者選擇該路徑的概率就越大.

為了說(shuō)明蟻群算法的原理，先簡(jiǎn)要介紹一下螞蟻搜尋食物的具體過(guò)程.在蟻群尋找食物時(shí)，它們總能找到一條從食物到巢穴之間的最優(yōu)路徑.這是因?yàn)槲浵佋趯ふ衣窂綍r(shí)會(huì)在路徑上釋放出一種特殊的信息素.當(dāng)它們碰到一個(gè)還沒(méi)有走過(guò)的路口時(shí)．就隨機(jī)地挑選一條路徑前行.與此同時(shí)釋放出與路徑長(zhǎng)度有關(guān)的信息素.路徑越長(zhǎng)，釋放的激索濃度越低.當(dāng)后來(lái)的螞蟻再次碰到這個(gè)路口的時(shí)候．選擇激素濃度較高路徑概率就會(huì)相對(duì)較大.這樣形成一個(gè)正反饋.最優(yōu)路徑上的激索濃度越來(lái)越大．而其它的路徑上激素濃度卻會(huì)隨著時(shí)間的流逝而消減.最終整個(gè)蟻群會(huì)找出最優(yōu)路徑.2簡(jiǎn)化的螞蟻尋食過(guò)程1/3螞蟻從A點(diǎn)出發(fā)，速度相同，食物在D點(diǎn)，可能隨機(jī)選擇路線ABD或ACD。假設(shè)初始時(shí)每條分配路線一只螞蟻，每個(gè)時(shí)間單位行走一步，本圖為經(jīng)過(guò)9個(gè)時(shí)間單位時(shí)的情形：走ABD的螞蟻到達(dá)終點(diǎn)，而走ACD的螞蟻剛好走到C點(diǎn)，為一半路程.2簡(jiǎn)化的螞蟻尋食過(guò)程2/3本圖為從開(kāi)始算起，經(jīng)過(guò)18個(gè)時(shí)間單位時(shí)的情形：走ABD的螞蟻到達(dá)終點(diǎn)后得到食物又返回了起點(diǎn)A，而走ACD的螞蟻剛好走到D點(diǎn).2簡(jiǎn)化的螞蟻尋食過(guò)程3/3

假設(shè)螞蟻每經(jīng)過(guò)一處所留下的信息素為一個(gè)單位，則經(jīng)過(guò)36個(gè)時(shí)間單位后，所有開(kāi)始一起出發(fā)的螞蟻都經(jīng)過(guò)不同路徑從D點(diǎn)取得了食物，此時(shí)ABD的路線往返了2趟，每一處的信息素為4個(gè)單位，而ACD的路線往返了一趟，每一處的信息素為2個(gè)單位，其比值為2:1.

尋找食物的過(guò)程繼續(xù)進(jìn)行，則按信息素的指導(dǎo)，蟻群在ABD路線上增派一只螞蟻（共2只），而ACD路線上仍然為一只螞蟻。再經(jīng)過(guò)36個(gè)時(shí)間單位后，兩條線路上的信息素單位積累為12和4，比值為3:1.

若按以上規(guī)則繼續(xù)，蟻群在ABD路線上再增派一只螞蟻（共3只），而ACD路線上仍然為一只螞蟻.再經(jīng)過(guò)36個(gè)時(shí)間單位后，兩條線路上的信息素單位積累為24和6，比值為4:1.

若繼續(xù)進(jìn)行，則按信息素的指導(dǎo)，最終所有的螞蟻會(huì)放棄ACD路線，而都選擇ABD路線.這也就是前面所提到的正反饋效應(yīng).3蟻群系統(tǒng)在TSP問(wèn)題中的應(yīng)用10城市TSP問(wèn)題20城市TSP問(wèn)題3蟻群系統(tǒng)在TSP問(wèn)題中的應(yīng)用30城市TSP問(wèn)題48城市TSP問(wèn)題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)值(FitnessValue)，每個(gè)粒子還有