現(xiàn)代優(yōu)化算法

1、現(xiàn)代優(yōu)化算法,李金屏濟(jì)南大學(xué)信息科學(xué)與工程學(xué)院模式識(shí)別與智能系統(tǒng)研究所(1st version in 2002.9)2006.9,39,2,內(nèi)容概要,優(yōu)化算法簡(jiǎn)介——運(yùn)籌學(xué) 正交試驗(yàn)法TABU禁忌搜索算法 模擬退火算法遺傳算法&進(jìn)化計(jì)算現(xiàn)代優(yōu)化算法再述課題組的工作,,其它問(wèn)題：計(jì)算復(fù)雜性；鄰域概念；NP, NP-C 和NP-hard；Markov過(guò)程；人工生命，螞蟻算法，免疫算法，混沌優(yōu)化算法，me

2、metic算法等。其它問(wèn)題。,39,3,優(yōu)化算法簡(jiǎn)介——概念、基本形式,什么是優(yōu)化？就是從各種方案中選取一個(gè)最好的。從數(shù)學(xué)角度看，優(yōu)化理論就是研究如何在狀態(tài)空間中尋找到全局最優(yōu)點(diǎn)。比如水泥混凝土的性能，涉及到水、沙、石子、水泥和其他摻雜物比例。學(xué)校課程表排課問(wèn)題、售票員上崗問(wèn)題、公司內(nèi)部人員安排出效益等。降低成本、提高效益是問(wèn)題的關(guān)鍵。一般的優(yōu)化具有下面形式：minf (x1, x2, …, xn)s.t. g(x) ? 0

3、，x?D其中x1, x2, …, xn?Ω（即問(wèn)題的可行域，代表問(wèn)題參數(shù)的選擇范圍），即minf (X)，其中X?Ω（矢量形式）。f(x)是決策問(wèn)題的數(shù)學(xué)模型，也是決策問(wèn)題的目標(biāo)函數(shù)，g(x) ?0是決策問(wèn)題的約束條件，D是決策問(wèn)題的定義域（可行域）。問(wèn)題歸結(jié)為求極值。極值點(diǎn)非常多，需要找到全局最小點(diǎn)。注：求問(wèn)題的最大和最小是同一個(gè)問(wèn)題，算法完全一樣。,39,4,如果決策問(wèn)題是一個(gè)凸問(wèn)題，可以利用線性規(guī)劃、非線性規(guī)劃等求解。然而

4、大量的實(shí)際問(wèn)題是非凸問(wèn)題，需要在大量的局部極優(yōu)解中尋找全局最優(yōu)解。此時(shí)，決策變量x是否連續(xù)，數(shù)學(xué)模型f(x)是否具有解析表達(dá)式，對(duì)于求解難度會(huì)有不同的影響。這是一個(gè)全局尋優(yōu)問(wèn)題。很多方法討論的是如何在一個(gè)極值點(diǎn)附近搜索極值點(diǎn)。一般情況下，利用窮舉的方法是不可能的。 習(xí)慣上，將優(yōu)化算法分為兩類：局部?jī)?yōu)化算法和全局性優(yōu)化算法。前者可以稱為經(jīng)典優(yōu)化算法，已經(jīng)得到了人們廣泛深入的研究。目前，運(yùn)籌學(xué)（確定論方法）主要包括這些方面的內(nèi)容，線性規(guī)

5、劃、整數(shù)規(guī)劃、0–1規(guī)劃、非線性規(guī)劃、排隊(duì)論、決策論。后者習(xí)慣上稱為現(xiàn)代優(yōu)化算法，是20世紀(jì)80年代興起的新型全局性優(yōu)化算法，主要包括禁忌搜索、模擬退火、遺傳算法等，其主要應(yīng)用對(duì)象是優(yōu)化問(wèn)題中的難解問(wèn)題，即NP–hard問(wèn)題,優(yōu)化算法簡(jiǎn)介——優(yōu)化算法分類,39,5,優(yōu)化算法簡(jiǎn)介——局部?jī)?yōu)化、全局優(yōu)化,有文獻(xiàn)將神經(jīng)網(wǎng)絡(luò)也列入現(xiàn)代優(yōu)化算法的范疇，從全局優(yōu)化的角度看，這并不適宜，因?yàn)樯窠?jīng)網(wǎng)絡(luò)的優(yōu)化算法本質(zhì)上是局部?jī)?yōu)化算法和全局優(yōu)化算法的綜合應(yīng)

6、用。局部?jī)?yōu)化算法主要用于解決凸問(wèn)題或單峰問(wèn)題，通常使用確定性搜索策略，比如單純形法、梯度下降法、爬山法、貪心法等，其基本思想是在狀態(tài)轉(zhuǎn)移過(guò)程中，只接受更好的狀態(tài)，拒絕惡化的狀態(tài)。全局性優(yōu)化算法主要用于求解非凸問(wèn)題或多峰問(wèn)題，通常使用概率性搜索策略，即狀態(tài)轉(zhuǎn)移規(guī)則，這是由于實(shí)際的全局性優(yōu)化問(wèn)題通常沒(méi)有解析表達(dá)式或者解析表達(dá)式非常復(fù)雜難以進(jìn)行理論分析。其基本思想是在可行域中從給定的一個(gè)或多個(gè)隨機(jī)初始點(diǎn)出發(fā)進(jìn)行搜索，利用適當(dāng)?shù)臓顟B(tài)轉(zhuǎn)移規(guī)則

7、和合理的概率性狀態(tài)接收規(guī)則搜索新的更優(yōu)點(diǎn)，在確定的時(shí)間或搜索次數(shù)之內(nèi)停止算法。,39,6,優(yōu)化算法簡(jiǎn)介——二者需要結(jié)合,局部?jī)?yōu)化算法由于易于陷入局部極優(yōu)解而無(wú)法用于解決多峰問(wèn)題；同時(shí)，全局性優(yōu)化算法采用適當(dāng)?shù)臓顟B(tài)轉(zhuǎn)移規(guī)則和概率性狀態(tài)接受規(guī)則，能夠避免過(guò)早地陷入局部極優(yōu)解從而搜索到全局性最優(yōu)解。通常，局部?jī)?yōu)化算法能夠快速地收斂到局部極優(yōu)解，而全局性優(yōu)化算法通過(guò)概率搜索可以獲得在概率意義上盡可能好的全局性最優(yōu)解區(qū)域，但是其局部極優(yōu)點(diǎn)搜索能

8、力較低。這是全局搜索算法和局部搜索算法之間的固有矛盾。對(duì)此人們進(jìn)行了多種研究?；窘鉀Q方法在于二者的結(jié)合，即利用全局性優(yōu)化算法在整個(gè)可行域中搜索最優(yōu)區(qū)域，利用局部搜索算法搜索最優(yōu)區(qū)域中的最優(yōu)解。Memetic算法就是全局性搜索和局部性搜索相結(jié)合的算法的總稱。又可以稱為雜和優(yōu)化算法 (Hybrid Optimization Algorithm)。,39,7,內(nèi)容概要,優(yōu)化算法簡(jiǎn)介——運(yùn)籌學(xué) 正交試驗(yàn)法TABU禁忌搜索算法 模擬退火

9、算法遺傳算法現(xiàn)代優(yōu)化算法再述課題組的工作,,39,8,正交試驗(yàn)法,在工農(nóng)業(yè)生產(chǎn)及科學(xué)實(shí)驗(yàn)中，為了試制新產(chǎn)品，改革工藝，尋找優(yōu)良的生產(chǎn)條件，需要安排一系列的實(shí)驗(yàn)。全面實(shí)驗(yàn)成本很高，而且往往做不到。因此，需要進(jìn)行部分試驗(yàn)。正交試驗(yàn)法就是一種實(shí)際中廣泛使用的部分試驗(yàn)法，又叫正交設(shè)計(jì)法或正交優(yōu)化法，即通過(guò)少數(shù)次試驗(yàn)找到最好的或者較好的實(shí)驗(yàn)條件。其中的決策變量和取值分別叫做因素和水平。尋優(yōu)時(shí)，先確定影響決策目標(biāo)的因素和水平，再選擇適當(dāng)?shù)恼?/p>

10、表，即可按正交表安排試驗(yàn)，最后分析試驗(yàn)的結(jié)果和發(fā)現(xiàn)最佳的水平。,39,9,正交試驗(yàn)法,正交表的形式為L(zhǎng)n(t1?t2?…?tm)，簡(jiǎn)記為L(zhǎng)n(tm)，其中n為試驗(yàn)數(shù)，m為因素?cái)?shù)，ti為水平數(shù)。正交設(shè)計(jì)法能夠確保決策變量具有最佳的散布性和代表性，因此獲得的最佳水平應(yīng)該具有相當(dāng)高的滿意度。實(shí)際上，正交試驗(yàn)法獲得的最佳結(jié)果優(yōu)于總體試驗(yàn)結(jié)果的n/(n+1)，劣于總體試驗(yàn)結(jié)果的1/(n+1)，具有良好的全局最優(yōu)性。該算法的另外一個(gè)最大優(yōu)勢(shì)在于簡(jiǎn)

11、單易學(xué)，一般文化水平的人（比如初中以上）經(jīng)過(guò)幾天時(shí)間就可以掌握，因此該算法具有極其廣泛的使用范圍。其難點(diǎn)在于特定正交表的構(gòu)造，人們正深入研究各種特殊正交表的構(gòu)造方法。,39,10,內(nèi)容概要,優(yōu)化算法簡(jiǎn)介——運(yùn)籌學(xué) 正交試驗(yàn)法TABU禁忌搜索算法 模擬退火算法遺傳算法現(xiàn)代優(yōu)化算法再述課題組的工作,,39,11,TABU禁忌搜索算法,禁忌搜索算法（tabu search） 是局部鄰域搜索算法的推廣，是人工智能在組合優(yōu)化算法中的一

12、個(gè)成功應(yīng)用。Glover在1986年首次提出這一概念，進(jìn)而形成一套完整算法。禁忌，就是禁止重復(fù)前面的工作。為了回避局部鄰域搜索陷入局部最優(yōu)的主要不足，采用一個(gè)禁忌表記錄已經(jīng)達(dá)到過(guò)的局部最優(yōu)點(diǎn)，在下一次搜索中，利用禁忌表中的信息不再或者有選擇地搜索這些點(diǎn)，以此來(lái)跳出局部最優(yōu)點(diǎn)。Tabu算法由幾個(gè)基本要素的組合：鄰域，Tabu表及評(píng)價(jià)函數(shù)。鄰域與一般優(yōu)化技術(shù)中的定義一致；Tabu表是一個(gè)或數(shù)個(gè)數(shù)據(jù)序列，是對(duì)先前的數(shù)步搜索所作的記錄，記錄

13、的方式有很多，記錄的長(zhǎng)度也是可變的，選取的好壞直接影響算法的效率；評(píng)價(jià)函數(shù)通常就是問(wèn)題的目標(biāo)函數(shù)或它的某種變換形式，用于對(duì)一個(gè)移動(dòng)作出評(píng)價(jià)。由Tabu表和評(píng)價(jià)函數(shù)可以構(gòu)造一種Tabu條件，若新點(diǎn)滿足Tabu條件則接受，否則拒絕，直至迭代終止。,39,12,TABU禁忌搜索算法,Tabu算法被認(rèn)為是人工智能在組合優(yōu)化中的成功應(yīng)用，但是仍有很多技術(shù)的細(xì)節(jié)問(wèn)題有待討論。如參數(shù)的選擇問(wèn)題，該問(wèn)題包括禁忌對(duì)象及其長(zhǎng)度、候選集合的確定等。另外還涉及

14、到評(píng)價(jià)函數(shù)、特赫規(guī)則、終止規(guī)則等的合理確定。在提高搜索效率方面，文獻(xiàn)[*]針對(duì)調(diào)度問(wèn)題提出一種變鄰域結(jié)構(gòu)的禁忌搜索算法，使鄰域結(jié)構(gòu)隨算法的進(jìn)程改變，鄰域規(guī)模小，并且保持了可達(dá)性；在算法的結(jié)合方面，有將禁忌搜索和遺傳算法相結(jié)合，構(gòu)造禁忌遺傳算法，主要是利用禁忌搜索的以下特點(diǎn)來(lái)改善遺傳算法：即Tabu搜索能有效利用全局信息、搜索過(guò)程中的獲得信息和能夠跳出局部最優(yōu)點(diǎn)。 [*]孫元?jiǎng)P，劉民，吳澄。變鄰域結(jié)構(gòu)Tabu搜索算法及其在Job S

15、hop調(diào)度問(wèn)題上的應(yīng)用。電子學(xué)報(bào)，2001,29(5),622-625。,39,13,內(nèi)容概要,優(yōu)化算法簡(jiǎn)介——運(yùn)籌學(xué) 正交試驗(yàn)法TABU禁忌搜索算法 模擬退火算法遺傳算法現(xiàn)代優(yōu)化算法再述課題組的工作,,39,14,模擬退火算法,模擬退火算法（simulated annealing algorithm, SAA）是一種重要的全局性啟發(fā)式概率搜索算法，其物理背景是固體的退火過(guò)程。 歷史上，兩個(gè)人物對(duì)于SAA的發(fā)展起了關(guān)鍵性的

16、作用，他們分別是N. Metropolis和S. Kirkpatrick。在利用Monte Carlo方法模擬恒定溫度下固體達(dá)到熱平衡態(tài)過(guò)程的研究中，1953年Metropolis提出了重要性采樣準(zhǔn)則，即對(duì)于處在微觀狀態(tài) i 的固體系統(tǒng)施加一個(gè)隨機(jī)擾動(dòng)，使其狀態(tài)變?yōu)閖。設(shè)與狀態(tài)i、j對(duì)應(yīng)的固體系統(tǒng)能量分別為Ei、Ej。則固體系統(tǒng)能否由狀態(tài) i 遷移到新的狀態(tài)j取決于Ei、Ej之間的關(guān)系：當(dāng)Ej≤Ei時(shí)，系統(tǒng)遷移到新的狀態(tài)；當(dāng)Ej&

17、gt;Ei時(shí)，系統(tǒng)將以如下概率遷移到新的狀態(tài),39,15,模擬退火算法,在大量遷移之后，系統(tǒng)趨于能量較低的平衡態(tài)，其微觀狀態(tài)的概率密度分布趨于Gibbs正則分布。1982年，Kirkpatrick將退火思想首先引入求解組合優(yōu)化問(wèn)題，提出了SAA。引入一個(gè)溫度參數(shù)T。開(kāi)始時(shí)，取T為一個(gè)較大的數(shù)值，此時(shí)狀態(tài)轉(zhuǎn)移比較自由。隨著溫度降低，狀態(tài)轉(zhuǎn)移逐漸困難，最后原則上應(yīng)該收斂到全局最優(yōu)點(diǎn)。目前，模擬退火算法已經(jīng)廣泛地用于求解TSP、VLSI電

18、路設(shè)計(jì)等NP–完全問(wèn)題。,,1 Ej ≤ Ei.,else,即,39,16,模擬退火算法,我國(guó)第一部系統(tǒng)討論模擬退火算法的中文專著《非數(shù)值并行算算法——模擬退火算法》比較詳細(xì)地討論了模擬退火算法的數(shù)學(xué)和物理背景、理論基礎(chǔ)以及實(shí)現(xiàn)形式，介紹了1994年以前國(guó)內(nèi)外一些學(xué)者在理論和應(yīng)用上的研究成果。這些成果主要是針對(duì)模擬退火算法性能的提高，如怎樣控制冷卻進(jìn)度表（cooling schedule）參數(shù)（即初始溫度、降溫策略、溫度終

19、值準(zhǔn)則、Markov鏈長(zhǎng)），怎樣實(shí)現(xiàn)模擬退火算法的并行運(yùn)算，怎樣進(jìn)一步改進(jìn)模擬退火算法等。這些改進(jìn)主要包括：選取合適的初始溫度、最優(yōu)保留策略、與局部搜索相結(jié)合、回火退火法等。需要說(shuō)明，文獻(xiàn)中的局部搜索法實(shí)質(zhì)上仍然是隨機(jī)搜索，只是僅接受優(yōu)化解，不接受惡化解。近些年來(lái)，不少學(xué)者對(duì)于模擬退火算法進(jìn)行了深入的研究和改進(jìn)。包括：討論模擬退火與傳統(tǒng)局部?jī)?yōu)化算法如單純形法、Powell方法等的結(jié)合[7]，研究鄰域結(jié)構(gòu)與選取狀態(tài)轉(zhuǎn)移隨機(jī)步長(zhǎng)方法

20、以及相應(yīng)的降溫方案，如何采取合適的退火終止條件等。,39,17,模擬退火算法,基本算法（PASCAL偽碼）：Procedure SIMULATED ANNEALING;beginINITIALIZE (i0, T0, L0);k:=0;i:=i0;repeat for l:=1 to Lk do beginGENERATE (j from Si)if f(j) ≤ f(i) then

21、 i:=jelseif exp[(f(i)—f(j))/Tk] >random[0,1] then i:=j end; k:=k+1; CALCULATE-LENGTH(Lk); CALCULATE-CONTROL(Tk);until stopcriterionend;,計(jì)算冷卻進(jìn)度表,Markov鏈長(zhǎng),Metropolis規(guī)則,39,18,模擬退火算法,最初路徑,算法結(jié)果,

22、目前最好結(jié)果,39,19,模擬退火算法,一些文獻(xiàn)：1、康立山，謝云，尤矢勇等。非數(shù)值并行算法——模擬退火算法。北京：科學(xué)出版社，1998年。2、王卓鵬，高國(guó)成，楊為平。一種改進(jìn)的快速模擬退火組合優(yōu)化法。系統(tǒng)工程理論與實(shí)踐，1999，(2): 73–76。3、趙玉清，余志軍。加速全局優(yōu)化–鮑威爾法和模擬退火法的組合。電子學(xué)報(bào)，1998，26(9): 75–77。4、楊若黎，顧基發(fā)。一種高效的模擬退火全局優(yōu)化算法。系統(tǒng)工程理論與實(shí)踐

23、，1997，(5): 29–35。,39,20,內(nèi)容概要,優(yōu)化算法簡(jiǎn)介——運(yùn)籌學(xué) 正交試驗(yàn)法TABU禁忌搜索算法 模擬退火算法遺傳算法現(xiàn)代優(yōu)化算法再述課題組的工作,,39,21,遺傳算法,Darwin 的物種進(jìn)化的主要思想是自然選擇(Natural selection)。生物通過(guò)競(jìng)爭(zhēng)來(lái)進(jìn)化，以適應(yīng)環(huán)境。生物通過(guò)遺傳(Heredity)、變異(Mutation)等過(guò)程實(shí)現(xiàn)進(jìn)化。遺傳和變異的物質(zhì)基礎(chǔ)是染色體(Chromosome

24、)。染色體又是由DNA 和蛋白質(zhì)組成的?；蛑斜Ａ糁z傳物質(zhì)。通過(guò)基因的復(fù)制(production)、交叉(crossover)和變異(mutation)實(shí)現(xiàn)生物的性狀的變異和遺傳。標(biāo)準(zhǔn)遺傳算法的基本框架是由Holland于20世紀(jì)60年代提出的，它使用二進(jìn)制編碼，采用賭輪選擇和隨機(jī)配對(duì)，關(guān)鍵是編碼。這是一類模擬生物進(jìn)化過(guò)程的全局性優(yōu)化算法，其搜索效率取決于搜索策略或狀態(tài)轉(zhuǎn)移策略、編碼策略、運(yùn)行參數(shù)的合理配置等方面。對(duì)于具有下面數(shù)學(xué)結(jié)

25、構(gòu)的研究對(duì)象min（或max）f (x)，s.t. g(x) ? 0，x?D 遺傳算法可以具有較好的搜索效果。,39,22,遺傳算法,基本思路：第一步：建立研究對(duì)象的數(shù)學(xué)結(jié)構(gòu)模型，確定目標(biāo)函數(shù)類型（即求目標(biāo)函數(shù)的最大值還是最小值?）。 第二步：確定表示可行解的染色體編碼方法，即確定個(gè)體基因型X及遺傳算法的搜索空間。 第三步：確定解碼方法，即確定由個(gè)體基因型X到相應(yīng)表現(xiàn)型的對(duì)應(yīng)關(guān)系或轉(zhuǎn)換關(guān)系。,39,23,遺傳算法,基本思路

26、：第四步：設(shè)計(jì)遺傳算子，包括選擇算子、交叉算子、變異算子等的具體操作方法。第五步：確定個(gè)體適應(yīng)度的量化評(píng)價(jià)方法，即制定由目標(biāo)函數(shù) f(x) 到個(gè)體適應(yīng)度的轉(zhuǎn)換規(guī)則。第六步：確定遺傳算法的有關(guān)運(yùn)行參數(shù)。包括編碼串長(zhǎng)度l（對(duì)于二進(jìn)制編碼）、交叉概率Pc、變異概率Pm、種群規(guī)模M、終止代數(shù)T等運(yùn)行參數(shù)的設(shè)置。第七步：設(shè)計(jì)遺傳算法程序，其中使用了最優(yōu)保留策略。,39,24,遺傳算法,為了提高其搜索效率，可以在三個(gè)方面提出改進(jìn)措施：1)

27、 采用更好的搜索策略。主要包括：精英策略（elitist strategy）；構(gòu)造與模擬退火算法、局部搜索算法如最速下降法等相結(jié)合的混和遺傳算法（hybrid genetic algorithm）；通過(guò)改造模式定理和引入半序關(guān)系將所有模式構(gòu)成一個(gè)半序格，從而將人工智能理論中的狀態(tài)空間搜索算法如A算法與遺傳算法相結(jié)合而提出的統(tǒng)計(jì)遺傳算法（statistical genetic algorithm）；基于家族優(yōu)生學(xué)原理構(gòu)成兩兩結(jié)合的家族競(jìng)爭(zhēng)

28、機(jī)制，通過(guò)引入正交設(shè)計(jì)法構(gòu)造出“正交交配”算子，從而在每個(gè)家庭內(nèi)部形成局部競(jìng)爭(zhēng)環(huán)境的進(jìn)化算法；利用小生境技術(shù)、聚類分析或狹義遺傳算法而提出的分區(qū)域搜索遺傳算法等。,39,25,遺傳算法,2) 采用更加合理的編碼策略。如采用十進(jìn)制編碼，多維實(shí)數(shù)編碼，或根據(jù)模式定理將二進(jìn)制編碼的低階、高平均適應(yīng)度的長(zhǎng)定義距模式轉(zhuǎn)換為短定義距模式等。3)合理配置運(yùn)行參數(shù)。遺傳算法的求解效率在很大程度上取決于編碼串長(zhǎng)度l（對(duì)于二進(jìn)制編碼）、種群規(guī)模M、交叉概

29、率Pc、變異概率Pm、終止代數(shù)T、適應(yīng)度函數(shù)f (M)等運(yùn)行參數(shù)的設(shè)置，當(dāng)然與具體的選擇算子也有很大關(guān)系，這在搜索策略中已經(jīng)有一定體現(xiàn)。除了種群規(guī)模和終止代數(shù)之外，人們對(duì)于染色體編碼、交叉和變異概率、適應(yīng)度函數(shù)等進(jìn)行了深入廣泛的討論。,39,26,遺傳算法,編碼串長(zhǎng)度l直接決定問(wèn)題的求解精度。選擇策略、交叉算子和變異算子對(duì)于種群早熟、收斂等有重大影響，不少工作對(duì)此進(jìn)行了有益的探討。適應(yīng)度函數(shù)f (M)是遺傳算法的一個(gè)瓶頸，人們針對(duì)不

30、同問(wèn)題提出了許多不同的適應(yīng)度函數(shù)定義。 最近有文獻(xiàn)研究了遺傳算法的一些統(tǒng)計(jì)性質(zhì)，提出進(jìn)化截止代數(shù)和平均截止代數(shù)的概念，指出進(jìn)化截止代數(shù)分布呈現(xiàn)典型的Г分布，還研究了遺傳算法的優(yōu)化效率。這種研究對(duì)于深刻理解遺傳算法非常有益。事實(shí)上，進(jìn)化截止代數(shù)分布之中蘊(yùn)含著許多豐富的知識(shí)，比如，平均進(jìn)化截止代數(shù)、成功率等主要依賴于哪些因素？種群規(guī)模M、研究對(duì)象數(shù)學(xué)結(jié)構(gòu)的極值個(gè)數(shù)、極值大小分布和極值區(qū)域半徑分布、染色體串長(zhǎng)l等在進(jìn)化截止代數(shù)分布中主

31、要起到什么作用？,39,27,內(nèi)容概要,優(yōu)化算法簡(jiǎn)介——運(yùn)籌學(xué) 正交試驗(yàn)法TABU禁忌搜索算法 模擬退火算法遺傳算法現(xiàn)代優(yōu)化算法再述課題組的工作,,39,28,現(xiàn)代優(yōu)化算法——一般性描述,——全局性優(yōu)化理論的一般性描述首先，需要確定的是狀態(tài)的表示，即決策變量x的編碼問(wèn)題。通常x是以數(shù)值方式編碼比如浮點(diǎn)數(shù)，也有二進(jìn)制方式，還有符號(hào)編碼如字母等。實(shí)際上編碼方式不應(yīng)該影響搜索的結(jié)果，只要x與其編碼具有一一對(duì)應(yīng)的關(guān)系，如浮點(diǎn)數(shù)編碼

32、與二進(jìn)制編碼之間就存在明確的一一對(duì)應(yīng)的關(guān)系。原碼編碼采用決策變量本身作為狀態(tài)參量，也是一種編碼方式，只不過(guò)我們已經(jīng)習(xí)以為常了。選擇不同的編碼方式對(duì)于優(yōu)化效率具有不同的影響。我們采用C(x)表示的x編碼，稱為個(gè)體。,39,29,現(xiàn)代優(yōu)化算法——一般性描述,——全局性優(yōu)化理論的一般性描述兩種搜索方式：?jiǎn)吸c(diǎn)法和多點(diǎn)法。單點(diǎn)法是一種串行方式，即從一個(gè)初始狀態(tài)（單個(gè)個(gè)體）出發(fā)，按照某種方式轉(zhuǎn)移狀態(tài)進(jìn)行全局優(yōu)化，這種方式通常要消耗較多機(jī)時(shí)；多

33、點(diǎn)法是一種并行方式，即從可行域的多個(gè)初始狀態(tài)（多個(gè)個(gè)體）同時(shí)進(jìn)行搜索尋找全局最優(yōu)解，但是空間開(kāi)銷大。根據(jù)各態(tài)歷經(jīng)假設(shè)，理論上二者可以具有相同的搜索效果。事實(shí)上，單CPU情況下的單點(diǎn)法和多點(diǎn)法并沒(méi)有本質(zhì)性的區(qū)別。,39,30,現(xiàn)代優(yōu)化算法——一般性描述,——全局性優(yōu)化理論的一般性描述兩種搜索策略：確定性和概率性。由于許多實(shí)際問(wèn)題的決策變量不連續(xù)，或者沒(méi)有解析表達(dá)式或者解析表達(dá)式比較復(fù)雜致使無(wú)法進(jìn)行理論分析，而且大多數(shù)問(wèn)題的極值數(shù)目

34、未知，無(wú)法提供全局性搜索的確定性信息，因此通常采用概率性搜索策略，包括：1. 狀態(tài)轉(zhuǎn)移規(guī)則，2. 狀態(tài)接受規(guī)則。狀態(tài)轉(zhuǎn)移規(guī)則研究從當(dāng)前狀態(tài)C(x)如何轉(zhuǎn)移到下一狀態(tài)C(x’)，即C(x)+?C ? C(x’)，?C表示狀態(tài)轉(zhuǎn)移量，需要根據(jù)決策問(wèn)題的數(shù)學(xué)結(jié)構(gòu)來(lái)確定。這是因?yàn)?C反映f(x)的鄰域結(jié)構(gòu)，合理的?C應(yīng)該保證概率性搜索的狀態(tài)具有最大代表性。這就要求?C符合最佳概率分布。,39,31,現(xiàn)代優(yōu)化算法——一般性描述,——全局性優(yōu)化理

35、論的一般性描述狀態(tài)接受規(guī)則研究如何接受按照狀態(tài)轉(zhuǎn)移規(guī)則獲得的新?tīng)顟B(tài)，即確定性接受還是概率性接受。確定性方式仍然是只接受更好的結(jié)果，拒絕惡化的結(jié)果。通常使用概率性方式，也有兩種做法：一種是更好結(jié)果肯定接受，惡化結(jié)果按照一定概率接受；另一種是無(wú)論好惡均以一定概率接受，只是結(jié)果越好接受概率越高。不同方式對(duì)于最終結(jié)果會(huì)有不同影響。由于狀態(tài)接受規(guī)則體現(xiàn)優(yōu)勝劣汰的思想，全局優(yōu)化也會(huì)陷入局部極優(yōu)解，因此必須考慮多樣性問(wèn)題。單點(diǎn)法,39,32,現(xiàn)代優(yōu)

36、化算法——一些特例,在可行域中進(jìn)行純隨機(jī)性概率搜索，將獲得Monte Carlo方法，此時(shí)的狀態(tài)轉(zhuǎn)移完全是隨機(jī)的，沒(méi)有利用任何啟發(fā)信息。隨機(jī)地從多個(gè)初始狀態(tài)出發(fā)進(jìn)行局部搜索，實(shí)際上是一種最原始的全局性和局部性優(yōu)化算法的結(jié)合，即多點(diǎn)隨機(jī)試探局部搜索法，此時(shí)的啟發(fā)信息完全體現(xiàn)于局部搜索部分，全局性優(yōu)化部分仍然是隨機(jī)的和盲目的。利用禁忌表記錄曾經(jīng)或已經(jīng)到達(dá)過(guò)的局部極優(yōu)解，下次搜索時(shí)利用該表信息不再或有選擇地搜索這些點(diǎn)，以此跳出局部極優(yōu)解，

37、增加搜索的區(qū)域，是禁忌搜索的基本思想。顯然這種搜索的效率是比較高的，但參數(shù)設(shè)置是一個(gè)需要認(rèn)真研究的問(wèn)題，涉及到禁忌對(duì)象、禁忌長(zhǎng)度、候選集合、評(píng)價(jià)函數(shù)、特赦規(guī)則、終止規(guī)則等的合理確定。這里的全局性啟發(fā)信息體現(xiàn)在禁忌表。,39,33,現(xiàn)代優(yōu)化算法——一些特例,從可行域的某個(gè)初始狀態(tài)出發(fā)，按照符合一定概率分布的狀態(tài)轉(zhuǎn)移規(guī)則搜索最優(yōu)解，利用概率的方法接受新?tīng)顟B(tài)，即更好結(jié)果肯定接受，惡化結(jié)果按照一定概率接受，而且隨著搜索的進(jìn)行接受惡化解的概率逐漸

38、變小，這是模擬退火的基本思想。這種搜索沒(méi)有結(jié)合局部?jī)?yōu)化算法，但具有隱含的局部?jī)?yōu)化能力。需要考慮的參數(shù)包括初始溫度選取、Markov鏈長(zhǎng)度（平衡態(tài)判據(jù)）、溫度控制策略、終止條件等。這里的啟發(fā)信息體現(xiàn)在狀態(tài)轉(zhuǎn)移規(guī)則和狀態(tài)接受規(guī)則，分別指導(dǎo)全局性優(yōu)化和局部性優(yōu)化。,39,34,現(xiàn)代優(yōu)化算法——一些特例,從可行域中的多個(gè)初始狀態(tài)（個(gè)體）出發(fā)進(jìn)行并行搜索，在搜索過(guò)程中個(gè)體之間不斷交流信息，采用概率方式接受新個(gè)體，比如賭盤形式。這是遺傳算法的基本思

39、想，采用一種群體搜索策略。這種方法具有很強(qiáng)的全局搜索能力和較強(qiáng)的局部搜索能力，自動(dòng)嵌入有增加多樣性的算子（交叉和變異運(yùn)算），主要缺陷是容易出現(xiàn)“早熟”。需要考慮的因素有個(gè)體編碼方式、種群規(guī)模、選擇算子、交叉算子、變異算子、終止代數(shù)、適應(yīng)度函數(shù)等。其啟發(fā)信息在于選擇方式（直接影響以后搜索的區(qū)域）、個(gè)體信息交流（模式的優(yōu)化組合）等。結(jié)論：在全局性優(yōu)化算法的一般性描述下各種優(yōu)化算法之間存在著密切的內(nèi)在聯(lián)系，是不同情況下的特殊算法。其中禁忌搜

40、索、模擬退火屬于單點(diǎn)法，遺傳算法屬于多點(diǎn)法，Monte Carlo方法和多點(diǎn)隨機(jī)試探局部搜索法既可以以單點(diǎn)法方式進(jìn)行，也可以以多點(diǎn)法方式進(jìn)行。,39,35,內(nèi)容概要,優(yōu)化算法簡(jiǎn)介——運(yùn)籌學(xué) 正交試驗(yàn)法TABU禁忌搜索算法 模擬退火算法遺傳算法現(xiàn)代優(yōu)化算法再述課題組的工作,,39,36,課題組的工作——已經(jīng)完成的工作,局部?jī)?yōu)化算法的改進(jìn)：梯度下降法——自適應(yīng)調(diào)整其學(xué)習(xí)率（步長(zhǎng)調(diào)整）——《模式識(shí)別與人工智能》、《系統(tǒng)工程與電

41、子技術(shù)》遺傳算法的參數(shù)確定：遺傳算法平均截止代數(shù)和成功率與種群規(guī)模之間的關(guān)系?！断到y(tǒng)仿真學(xué)報(bào)》（增刊）遺傳算法改進(jìn)：與正交試驗(yàn)法相結(jié)合——正交遺傳算法?！峨娮訉W(xué)報(bào)》遺傳算法改進(jìn)：與梯度下降法的結(jié)合——混合遺傳算法?！冬F(xiàn)代信息技術(shù)理論與應(yīng)用——CIE-YC'2002》遺傳算法改進(jìn)：與小生境進(jìn)化算法、聚類分析相結(jié)合?！缎⌒臀⑿陀?jì)算機(jī)系統(tǒng)》,39,37,課題組的工作——Publications,

42、BP小波神經(jīng)網(wǎng)絡(luò)快速學(xué)習(xí)算法研究。李金屏，王風(fēng)濤，楊波。 《系統(tǒng)工程與電子技術(shù)》，Vol.23,No.8,2001,72-75.遺傳算法平均截止代數(shù)和成功率與種群規(guī)模之間的關(guān)系。李金屏，何苗，楊波。《系統(tǒng)仿真學(xué)報(bào)》(增刊),2001, Vol.13, 206-210.提高BP小波神經(jīng)網(wǎng)絡(luò)收斂速度的研究。李金屏，何苗，劉明軍，楊波?！赌Ｊ阶R(shí)別與人工智能》, 2002, 15(1):28-35。正交遺傳算法。史奎凡，董吉文，李金屏，曲

43、守寧，楊波?！峨娮訉W(xué)報(bào)》 ，2002，Vol.30，No.10.利用混合遺傳算法提高小波神經(jīng)網(wǎng)絡(luò)收斂速度的研究。李金屏，牛業(yè)亭，盧剛。《現(xiàn)代信息技術(shù)理論與應(yīng)用：CIE-YC‘2002》，701-705，合肥：中國(guó)科學(xué)技術(shù)大學(xué)出版社，2002.8。 基于小生境算法和聚類分析的快速收斂遺傳算法。李金屏，李素芳，楊波。《小型微型計(jì)算機(jī)系統(tǒng)》，2004，Vol.25，No.6?；煦鐑?yōu)化算法性能分析。李金屏，韓延彬，孫志勝?！缎⌒臀⑿陀?jì)算機(jī)