幾種智能優(yōu)化方法

1.遺傳算法遺傳算法(GeneticAlgorithms,GA)是由美國密歇根大學(xué)的 JohnH.Holland教授及其學(xué)生于20世紀(jì)60年代末到70年代初提出的。在1975年出版的《自然與人工系統(tǒng)的自適應(yīng)性》一書中，Holland系統(tǒng)地闡述了遺傳算法的基本原理和方法，提出了對遺傳算法的理論發(fā)展極為重要的模板理論。遺傳算法基本思想：遺傳算法是根據(jù)問題的目標(biāo)函數(shù)構(gòu)造一個適值函數(shù)，對于有多個解構(gòu)成的種群進(jìn)行評估、遺傳運算、選擇，經(jīng)多代繁殖，獲得適應(yīng)值最好的個體作為問題的最優(yōu)解。具體描述如下。產(chǎn)生初始種群遺傳算法是一種基于群體尋優(yōu)的方法，算法運行時是以一個種群在搜索空間進(jìn)行搜索。一般是采用隨機(jī)方法產(chǎn)生一個初始種群。也可以采用其他方法構(gòu)造一個初始種群。根據(jù)問題的目標(biāo)函數(shù)構(gòu)造適值函數(shù)在遺傳算法中使用適值函數(shù)來表征種群中每個個體對其生存環(huán)境的適應(yīng)能力， 每個個體具有一定的適應(yīng)值。適應(yīng)值是種群中個體生存機(jī)會的唯一確定值。適值函數(shù)直接決定著群體的進(jìn)化行為。適值函數(shù)基本上依據(jù)優(yōu)化的目標(biāo)函數(shù)來確定。為了能夠直接將適值函數(shù)與群體中的個體優(yōu)劣相聯(lián)系，在遺傳算法中適應(yīng)值規(guī)定為非負(fù)，并且在任何情況下總是希望越大越好。根據(jù)適應(yīng)值的好壞不斷選擇和繁殖在遺傳算法中自然選擇規(guī)律的體現(xiàn)就是以適應(yīng)值的大小決定的概率分布來進(jìn)行計算選擇。 個體的適應(yīng)值越大，該個體被遺傳到下一代的概率越大；反之，個體適應(yīng)值越小，該個體被遺傳到下一代的概率越小。被選擇的個體兩兩進(jìn)行繁殖，繁殖產(chǎn)生的個體組成新的種群。這樣的選擇和繁殖的過程不斷重復(fù)。若干代后得到適應(yīng)值最好的個體即為最優(yōu)解在若干代后，得到適應(yīng)值最好的個體所對應(yīng)的解即被認(rèn)為是問題的最優(yōu)解。遺傳算法構(gòu)成要素：種群和種群大小種群是有染色體構(gòu)成的。每個個體就是一個染色體，每個染色體對應(yīng)著問題的一個解。種群中個體的數(shù)量稱為種群大小或種群規(guī)模。種群規(guī)模通常采用一個不變的常數(shù)。一般來說種群規(guī)模越大越好，但是種群規(guī)模增大也將導(dǎo)致運算時間的增大。在一些特殊情況下，群體規(guī)模也可能采用與遺傳代數(shù)相關(guān)的變量，以獲取更好的優(yōu)化效果。編碼方法(EncodingScheme)編碼方法也稱為基因的表達(dá)方法。在遺傳算法中，種群中每個個體，即染色體是由基因構(gòu)成的。所以染色體與要優(yōu)化的問題的解如何進(jìn)行對應(yīng)，就需要通過基因來進(jìn)行表示，即染色體進(jìn)行正確的編碼(一般用二進(jìn)制編碼)。正確地對染色體進(jìn)行編碼來表示問題的解是遺傳算法的基礎(chǔ)工作，也是最重要的工作。遺傳算子(GeneticOperator)遺傳算子包括交叉(Crossover)和(Mutation)。遺傳算子模擬了每一代中創(chuàng)造后代的繁殖過程，是遺傳算法的精髓。交叉是最重要的遺傳算子，它同時對兩個染色體進(jìn)行操作，組合二者的特性產(chǎn)生新的后代。交叉最簡單的方式是在雙親的染色體上隨機(jī)地選擇一個斷點，將斷點的右段相互交換，從而形成兩個新的后代。這種方式對于二進(jìn)制編碼最適合。遺傳算法的性能很大程度上取決于采用的交叉運算的方式。交叉率定義為各代中交叉產(chǎn)生后代數(shù)與種群中個體數(shù)的比。 顯然，較高的交叉率將達(dá)到更大的解空間，從而減小停止在非最優(yōu)解上的機(jī)會；但交叉率過高，會因過多搜索不必要的解空間而浪費大量的計算時間。變異率定義為種群中變異基因數(shù)在總基因數(shù)中的百分比。變異率控制著新基因?qū)敕N群的比例。若變異率太低，一些有用的基因就難以進(jìn)入選擇；若太高，即隨機(jī)的變化太多，那么后代就可能失去從雙親繼承下來的好特性，這樣算法就會失去從過去搜索中學(xué)習(xí)的能力。選擇策略和停止準(zhǔn)則選擇策略是從當(dāng)前種群中選擇適應(yīng)值高的個體以生成交配池的過程。使用最多的是正比例選擇策略。選擇過程體現(xiàn)了生物進(jìn)化過程中“適者生存，優(yōu)勝劣汰”的思想，并保證優(yōu)良基因遺傳給下一代。一般使用最大迭代次數(shù)作為停止準(zhǔn)則。蟻群算法20世紀(jì)90年代初，意大利學(xué)者DorigoM等人提出一種模擬昆蟲王國中螞蟻群體覓食行為方式的仿生優(yōu)化算法一一蟻群算法( AntColonyAlgorithm,ACA)。該算法引入正反饋并行機(jī)制，具有較強(qiáng)的魯棒性、優(yōu)良的分布式計算機(jī)制、易于與其他方法結(jié)合等優(yōu)點。據(jù)生物學(xué)家的觀察和研究，發(fā)現(xiàn)自然界中的螞蟻有能力在沒有任何可見提示下找出從蟻穴到食物的最短路徑，并且能隨環(huán)境的變化而變化，適應(yīng)性地搜索新的路徑，產(chǎn)生新的選擇。作為昆蟲的螞蟻在尋找食物源時，能在其走過的路徑上釋放一種螞蟻特有的分泌物一一信息素，使得一定范圍內(nèi)的其他螞蟻能察覺到并由此影響它們以后的行為當(dāng)一些路徑上通過的螞蟻越來越大時，其留下的信息素濃度也越來越大，好來螞蟻選擇該路徑的概率也越高，從而更增加了該路徑的信息素強(qiáng)度，這種選擇被稱為螞蟻的自催化行為。 因此，也可以將螞蟻王國理解成所謂的增強(qiáng)型學(xué)習(xí)系統(tǒng)。自從蟻群算法在著名的旅行商問題( TSP和二次分配問題(QAP)上取得成效以來，已陸續(xù)滲透到其他問題領(lǐng)域中，如工件排序、圖著色問題、車輛調(diào)度問題、大規(guī)模集成電路設(shè)計、通訊網(wǎng)絡(luò)中的負(fù)載平衡問題等。蟻群算法這種來自生物界的隨機(jī)搜索尋優(yōu)方法目前已在許多方面表現(xiàn)出相當(dāng)好的性能，它的正反饋性和協(xié)同性是指可用于分布式系統(tǒng)，其隱藏的并行性更是具有極強(qiáng)的發(fā)展?jié)摿?。其求解的問題領(lǐng)域也在進(jìn)一步擴(kuò)大，如一些約束型問題和多目標(biāo)問題，從1998年10月與比利時布魯塞爾召開的第一屆蟻群優(yōu)化國際研討會的內(nèi)容中可以看出這種帶有構(gòu)造性特征的搜索方法所產(chǎn)生的深遠(yuǎn)影響和廣泛應(yīng)用。模擬退火算法模擬退火算法(SimulatedAnnealing,SA)是屬于一種通用的隨機(jī)搜索算法，是局部搜索算法的擴(kuò)展，它的早期思想是在1953年由Metropolis提出來的，到1983年由Kirkpatrick等人成功的應(yīng)用在組合優(yōu)化問題中.模擬退火法來源于固體退火原理，將固體加熱到一定溫度后，它的所有分子在狀態(tài)空間自由運動.隨著溫度的逐漸下降，分子停留在不同的狀態(tài)，分子運動逐漸趨于有序，最后以一定的結(jié)構(gòu)排列.這種由高溫向低溫逐漸降溫的過程稱為退火 .退火過程中系統(tǒng)地熵值不斷減小系統(tǒng)能量隨溫度的降低趨于最小值.固體退火過程與優(yōu)化問題之間存在著類似性.Kirkpatrick等人把Metropolis等人對用固體在恒定問題下達(dá)到熱平衡過程的模擬引入到優(yōu)化過程中 .即如果E2-E1<0則接受新狀態(tài)，否則按概率P接受新狀態(tài).T為一隨即時間t增加而下降的參變量，相當(dāng)于退火過程中的溫度.這種利用優(yōu)化問題求解物理系統(tǒng)退火過程的相似性 ，使用Metropolis算法，適當(dāng)控制溫度的下降過程，實現(xiàn)模擬退火，從而達(dá)到求解全局優(yōu)化問題的隨機(jī)性方法稱之為“模擬退火算法”。模擬退火算法在搜索策略上引入了適當(dāng)?shù)碾S機(jī)因素和物理系統(tǒng)退火過程的自然機(jī)理，使得在迭代過程中出現(xiàn)可以接受使目標(biāo)函數(shù)值變“好”的試探點，也可以以一定的概率接受使目標(biāo)函數(shù)值變“差”的試探點、接受概率隨溫度的下降逐漸減小。這樣避免了搜索過程陷入局部最優(yōu)解，有利于提高求的全局最優(yōu)解的可靠性。 因此，模擬退火算法具有實用廣泛性，求的全局最優(yōu)解的可靠性高，算法簡單，便于實現(xiàn)等優(yōu)點。基本模擬退火算法的步驟：步驟1:選擇初始狀態(tài)H(初始解)、初始溫度、降溫次數(shù)等；步驟2:生產(chǎn)H',并計算兩種狀態(tài)下的目標(biāo)函數(shù)變化 f(H)-f(H')；步驟3:按接收概率置換H為H';步驟4:重復(fù)步驟2和步驟3直至滿足結(jié)束條件。禁忌搜索算法禁忌搜索算法(TabooSearch,TS是繼遺傳算法之后又一種元啟發(fā)式優(yōu)化算法，最早于1977年由Glover提出。它采用了類似爬山法的移動原理，將最近若干步內(nèi)所得到的解存儲在一種稱為Tabu的列表中，從而強(qiáng)制搜索避免再次重復(fù)表中的解。如果說遺傳算法開辟了在解空間中從多出發(fā)點搜索問題最優(yōu)解的先河， 則禁忌搜索法是首次在搜索過程中使用記憶功能的先驅(qū)，他們在求解各種實際問題中都取得了相對的成功。算法基本步驟大致如下：步驟1:選擇初始解XO,X*<—XO,Z*<-f(X*);禁忌列表Tabu為空；步驟2：對當(dāng)前解鄰域中的X，若f(X)<Z*,并且X不再Tabu中或者X在Tabu中，但不符合期望準(zhǔn)則，則X*<—X，Z*<—f(X);X*進(jìn)Tabu;步驟3:重復(fù)步驟2直至滿足結(jié)束條件。禁忌搜索算法自提出以來，已陸續(xù)應(yīng)用到 TSPQAP、工件排序、車輛路徑問題、電路設(shè)計問題。圖著色問題、背包問題等領(lǐng)域。在 TS法提出初期，就已與神經(jīng)網(wǎng)絡(luò)進(jìn)行了有機(jī)的結(jié)合，20世紀(jì)90年代還增有求解過有幾十萬個頂點的大型 TSP問題。該方法與模擬退火算法、遺傳算法。蟻群算法等相結(jié)合，形成了更為有力的混合型啟發(fā)式算法。人工神經(jīng)網(wǎng)絡(luò)神經(jīng)網(wǎng)絡(luò)的基本原理是構(gòu)造人工神經(jīng)網(wǎng)絡(luò)模型的一個基本依據(jù)。 1943年McCulloch和Pitts建立了第一個人工神經(jīng)網(wǎng)絡(luò)模型， 后被擴(kuò)展為“認(rèn)知”模型。認(rèn)知模型的一個功效可以用來解決簡單的分類問題。1982年，美國生物物理學(xué)家Hopfield提出人工神經(jīng)網(wǎng)絡(luò)(ArtificialNeuralNetworks,ANNs)模型，才被認(rèn)為是一個重大突破。而 Hopfield和Tank用ANN方法求解TSP獲得成功以來，更是引起了極大的關(guān)注。該方法的思想是通過對神經(jīng)網(wǎng)絡(luò)引入適當(dāng)?shù)哪芰亢瘮?shù)，使之與TSP的目標(biāo)函數(shù)一致來確定神經(jīng)元之間的連接權(quán)， 隨著網(wǎng)絡(luò)狀態(tài)的變化，其能力不斷減少，最后達(dá)到平衡時， 及收斂到局部最優(yōu)解。但是，這種算法在求解中很有可能陷入在解空間中作無目標(biāo)的周游或者落到許多局部最小點中的某一點上， 盡管可以適當(dāng)修正Liapunov函數(shù)，但一些根本性的困難仍很難消除。隨著人們對感知機(jī)興趣的衰退，神經(jīng)網(wǎng)絡(luò)的研究沉寂了相當(dāng)長的時間。 80年代初期，模擬與數(shù)字混合的超大規(guī)模集成電路制作技術(shù)提高到新的水平， 完全付諸實用化，此外，數(shù)字計算機(jī)的發(fā)展在若干應(yīng)用領(lǐng)域遇到困難。 這一背景預(yù)示，向人工神經(jīng)網(wǎng)絡(luò)尋求出路的時機(jī)已經(jīng)成熟。美國的物理學(xué)家Hopfield于1982年和1984年在美國科學(xué)院院刊上發(fā)表了兩篇關(guān)于人工神經(jīng)網(wǎng)絡(luò)研究的論文，引起了巨大的反響。人們重新認(rèn)識到神經(jīng)網(wǎng)絡(luò)的威力以及付諸應(yīng)用的現(xiàn)實性。隨即，一大批學(xué)者和研究人員圍繞著 Hopfield提出的方法展開了進(jìn)一步的工作，形成了80年代中期以來人工神經(jīng)網(wǎng)絡(luò)的研究熱潮。粒子群算法粒子群算法(ParticleSwarmOptimization,PSO)是由美國社會心理學(xué)家JamesKennedy和電氣工程師RussellEberhart在1995年共同提出的，是繼遺傳算法、蟻群算法之后的又一種新的群體智能算法，目前以成為進(jìn)化算法的一個重要分支。PSO基本思想是受Eberhart和Kennedy對許多鳥類群體行為進(jìn)行建模與仿真研究結(jié)果的啟發(fā)，而其模型及仿真算法主要利用了生物學(xué)家FrankHepper的模型：當(dāng)一只鳥飛離鳥群而飛向棲息地時，將導(dǎo)致它周圍的其他鳥也飛向棲息地，直到整個鳥群都落到棲息地。鳥群尋找棲息地與對一個特定問題尋找解很類似。正是由于這一發(fā)現(xiàn)，Eberhart和Kennedy對FrankHepper的模型進(jìn)行修正，以使微粒能夠飛向解空間并在最好解處降落。其關(guān)鍵在于探索和開發(fā)之間尋找一個恰到的平衡。另一方面，需要在個性與社會性之間尋求平衡，即希望個體既具有個性化，又希望其知道其他個體已經(jīng)找到優(yōu)解并向他們學(xué)習(xí)，即社會性?；玖Ｗ尤核惴ǖ暮诵牟襟E如下：步驟1：依照初始化過程，對微粒群的隨機(jī)位置和速度進(jìn)行初始設(shè)定；步驟2：計算每個微粒的適應(yīng)值；步驟3：對每個微粒，將其適應(yīng)值與所經(jīng)歷過的最好位置進(jìn)行比較，若較好，則將其作為當(dāng)前最好位置；步驟4：對每個微粒，將其適應(yīng)值與全局所經(jīng)歷過的最好位置的適應(yīng)值進(jìn)行比較，若較好，則將其作為當(dāng)前全局最好位置；步驟5:對微粒的速度和位置進(jìn)行進(jìn)化；步驟6:若未達(dá)到結(jié)束條件，則返回步驟 2.捕食搜索算法捕食搜索算法(PredatorySearch,PS是由巴西學(xué)者AlexandreLinhares在1998年提出來的一種用于解決組合優(yōu)化問題的模擬動物捕食行為的空間搜索策略。AlexandreLinhares把捕食搜索策略分別應(yīng)用于解決TSP問題和超大規(guī)模集成電路設(shè)計問題，都取得了較好的效果。捕食動物的搜索過程分為