啟發(fā)式優(yōu)化算法綜述

1、1啟發(fā)式優(yōu)化算法化算法綜述一、啟一、啟發(fā)式算法式算法簡介1、定、定義由于傳統(tǒng)的優(yōu)化算法如最速下降法，線性規(guī)劃，動態(tài)規(guī)劃，分支定界法，單純形法，共軛梯度法，擬牛頓法等在求解復(fù)雜的大規(guī)模優(yōu)化問題中無法快速有效地尋找到一個合理可靠的解，使得學(xué)者們期望探索一種算法:它不依賴問題的數(shù)學(xué)性能，如連續(xù)可微，非凸等特性對初始值要求不嚴(yán)格、不敏感，并能夠高效處理髙維數(shù)多模態(tài)的復(fù)雜優(yōu)化問題，在合理時間內(nèi)尋找到全局最優(yōu)值或靠近全局最優(yōu)的值。于是基于實際應(yīng)用的

2、需求，智能優(yōu)化算法應(yīng)運而生。智能優(yōu)化算法借助自然現(xiàn)象的一些特點，抽象出數(shù)學(xué)規(guī)則來求解優(yōu)化問題，受大自然的啟發(fā)，人們從大自然的運行規(guī)律中找到了許多解決實際問題的方法。對于那些受大自然的運行規(guī)律或者面向具體問題的經(jīng)驗、規(guī)則啟發(fā)出來的方法，人們常常稱之為啟發(fā)式算法（HeuristicAlgithm）。為什么要引出啟發(fā)式算法，因為NP問題，一般的經(jīng)典算法是無法求解，或求解時間過長，我們無法接受。因此，采用一種相對好的求解算法，去盡可能逼近最優(yōu)解

3、，得到一個相對優(yōu)解，在很多實際情況中也是可以接受的。啟發(fā)式算法是一種技術(shù)，這種技術(shù)使得在可接受的計算成本內(nèi)去搜尋最好的解，但不一定能保證所得的可行解和最優(yōu)解，甚至在多數(shù)情況下，無法闡述所得解同最優(yōu)解的近似程度。啟發(fā)式算法是和問題求解及搜索相關(guān)的，也就是說啟發(fā)式算法是為了提高搜索效率才提出的。人在解決問題時所采取的一種根據(jù)經(jīng)驗規(guī)則進(jìn)行發(fā)現(xiàn)的方法。其特點是在解決問題時利用過去的經(jīng)驗選擇已經(jīng)行之有效的方法，而不是系統(tǒng)地、以確定的步驟去尋求答案

4、，以隨機(jī)或近似隨機(jī)方法搜索非線性復(fù)雜空間中全局最優(yōu)解的尋取。啟發(fā)式解決問題的方法是與算法相對立的。算法是把各種可能性都一一進(jìn)行嘗試，最終能找到問題的答案，但它是在很大的問題空間內(nèi)，花費大量的時間和精力才能求得答案。啟發(fā)式方法則是在有限的搜索空間內(nèi)，大大減少嘗試的數(shù)量，能迅速地達(dá)到問題的解決。2、發(fā)展歷史啟發(fā)式算法的計算量都比較大，所以啟發(fā)式算法伴隨著計算機(jī)技術(shù)的發(fā)展，才能取得了巨大的成就。縱觀啟發(fā)式算法的歷史發(fā)展史：40年代：由于實際需

5、要，提出了啟發(fā)式算法（快速有效）。50年代：逐步繁榮，其中貪婪算法和局部搜索等到人們的關(guān)注。60年代:反思，發(fā)現(xiàn)以前提出的啟發(fā)式算法速度很快，但是解得質(zhì)量不能保證，而且對大規(guī)模的問題仍然無能為力（收斂速度慢）。70年代：計算復(fù)雜性理論的提出，NP問題。許多實際問題不可能在合理的時間范圍內(nèi)找到全局最優(yōu)解。發(fā)現(xiàn)貪婪算法和局部搜索算法速度快，但解不好的原因主要是他們只是在局部的區(qū)域內(nèi)找解，等到的解沒有全局最優(yōu)性。由此必須引入新的搜索機(jī)制和策略

6、。Holl的遺傳算法出現(xiàn)了（GeicAlgithm）再次引發(fā)了人們研究啟發(fā)式算法的興趣。80年代以后：模擬退火算法（SimulatedAnnealingAlgithm），人工神經(jīng)網(wǎng)絡(luò)（ArtificialNeuralwk），禁忌搜索（TabuSearch）相繼出現(xiàn)。最近比較火熱的：演化算法（EvolutionaryAlgithm）蟻群算法（AntAlgithms），擬人擬物算法，量子算法等。3行方式。不同的編碼策略對遺傳算法的運行效率有

7、較大的影響。問題的編碼一般應(yīng)滿足完備性、健全性和非冗長性H個原則，完備性是指問題空間中的所有點都能成為GA編碼空間中點的表現(xiàn)型；健全性是指GA編碼空間中染色體必須對應(yīng)問題空間中的某一潛在解；非冗長性是指染色體和潛在解必須一一對應(yīng)PS1。對于一個特定的問題，如何設(shè)計出一種高效的編碼方式是遺傳算法所面臨的難題之一，遺憾的是，研究者們至今也沒能找到一種通用的編碼策略。目前，工程優(yōu)化中多采用兩種常用的編碼方式，即二進(jìn)制編碼Psi和實數(shù)編碼PD1

8、。二進(jìn)制編碼的染色體是由一個二值集合｛01｝所組成的二進(jìn)制符號串。作為GA算法的標(biāo)準(zhǔn)編碼方式，該編碼方式尤其適用于能用二值向量描述的優(yōu)化問題，如化學(xué)反應(yīng)P11、多用途過程規(guī)劃P3和最優(yōu)水流參數(shù)評估Psi等；實數(shù)編碼是指個體的每個基因值用某一范圍的一個浮點數(shù)表示，個體的編碼長度等于其決策變量（設(shè)計變量）的個數(shù)。這種編碼方式適用于精度要求較高的遺傳算法中，便于較大空間的遺傳搜索：改善了遺傳算法的計算復(fù)雜性，提高了運算效率；便于遺傳算法和經(jīng)典

9、優(yōu)化算法的混合使用：目前基于實數(shù)編碼的遺傳算法也被廣泛用于優(yōu)化問題中，如多目標(biāo)優(yōu)化IW，凸輪輪廓設(shè)汁等。2)選擇操作。選擇是指從群體中選擇優(yōu)良的個體并淘汰劣質(zhì)個體的操作。它建立在適應(yīng)度評估的基礎(chǔ)上，遼應(yīng)度楚大的個體，被選擇的可能性就越大，它的吁孫＂在下一代的個數(shù)就越多。選擇出來的個體被放入配對庫中。目前常用的選擇方法有輪盤賭方法、最佳個體保留法、期望值法和排序選擇法等。3）交叉操作。交叉是指兩個父代個體的部分結(jié)構(gòu)加W替換重組而生成新個體

10、的操作，目的是為了能夠在下一代產(chǎn)生新的個體。通過交叉操作，遺傳算法的搜索能力得W提高。交叉是遺傳算法獲取新優(yōu)良個體最重要的手段，按照一定的交叉概率在配對庫中隨機(jī)地選取兩個個體進(jìn)行交叉，交叉的位置也是隨機(jī)確定的。4）變異。變異就是很小的變異概率隨機(jī)地改變?nèi)后w中個體的某些基因的值。變異操作中位置選取的基本過程如下：產(chǎn)生一個在0~1之間的隨機(jī)數(shù)，如果小于Pm則進(jìn)行變異操作。①、模、模擬退火退火模擬退火算法來源于固體退火原理，是一種基于概率的算

11、法，將固體加溫至充分高，再讓其徐徐冷卻，加溫時，固體內(nèi)部粒子隨溫升變?yōu)闊o序狀，內(nèi)能增大，而徐徐冷卻時粒子漸趨有序，在每個溫度都達(dá)到平衡態(tài)，最后在常溫時達(dá)到基態(tài)，內(nèi)能減為最小。模擬退火算法新解的產(chǎn)生和接受可分為如下四個步驟：第一步是由一個產(chǎn)生函數(shù)從當(dāng)前解產(chǎn)生一個位于解空間的新解；為便于后續(xù)的計算和接受，減少算法耗時，通常選擇由當(dāng)前新解經(jīng)過簡單地變換即可產(chǎn)生新解的方法，如對構(gòu)成新解的全部或部分元素進(jìn)行置換、互換等，注意到產(chǎn)生新解的變換方法決

12、定了當(dāng)前新解的鄰域結(jié)構(gòu)，因而對冷卻進(jìn)度表的選取有一定的影響。第二步是計算與新解所對應(yīng)的目標(biāo)函數(shù)差。因為目標(biāo)函數(shù)差僅由變換部分產(chǎn)生，所以目標(biāo)函數(shù)差的計算最好按增量計算。事實表明，對大多數(shù)應(yīng)用而言，這是計算目標(biāo)函數(shù)差的最快方法。第三步是判斷新解是否被接受判斷的依據(jù)是一個接受準(zhǔn)則，最常用的接受準(zhǔn)則是Metropolis準(zhǔn)則:若ΔT0則接受S′作為新的當(dāng)前解S，否則以概率exp(ΔTT)接受S′作為新的當(dāng)前解S。第四步是當(dāng)新解被確定接受時，用新