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

1、現(xiàn)代優(yōu)化算法現(xiàn)代優(yōu)化算法李金屏濟(jì)南大學(xué)信息科學(xué)與工程學(xué)院模式識(shí)別與智能系統(tǒng)研究所(1st version in 2002.9)2006.9392內(nèi)容概要n優(yōu)化算法簡(jiǎn)介運(yùn)籌學(xué) n正交試驗(yàn)法nTABU禁忌搜索算法 n模擬退火算法n遺傳算法&進(jìn)化計(jì)算n現(xiàn)代優(yōu)化算法再述n課題組的工作其它問(wèn)題：其它問(wèn)題：計(jì)算復(fù)雜性；鄰域概念；NP, NP-C 和NP-hard；Markov過(guò)程；人工生命，螞蟻算法，免疫算法，混沌優(yōu)化算法，memetic算法等。其它問(wèn)題。393優(yōu)化算法簡(jiǎn)介概念、基本形式概念、基本形式n什么是優(yōu)化？就是從各種方案中選取一個(gè)最好的。從數(shù)學(xué)角度看，優(yōu)化理論就是研究如何在狀態(tài)空間中尋找到全局最優(yōu)

2、點(diǎn)。n比如水泥混凝土的性能，涉及到水、沙、石子、水泥和其他摻雜物比例。學(xué)校課程表排課問(wèn)題、售票員上崗問(wèn)題、公司內(nèi)部人員安排出效益等。降低成本、提高效益是問(wèn)題的關(guān)鍵。n一般的優(yōu)化具有下面形式：minf (x1, x2, , xn)s.t. g(x) 0，xD其中x1, x2, , xn（即問(wèn)題的可行域，代表問(wèn)題參數(shù)的選擇范圍），即minf (X)，其中X（矢量形式）。f(x)是決策問(wèn)題的數(shù)學(xué)模型，也是決策問(wèn)題的目標(biāo)函數(shù)目標(biāo)函數(shù)，g(x) 0是決策問(wèn)題的約束條件約束條件，D是決策問(wèn)題的定義域（可行域可行域）。問(wèn)題歸結(jié)為求極值。極值點(diǎn)非常多，需要找到全局最小點(diǎn)。注：求問(wèn)題的最大和最小是同一個(gè)問(wèn)題，算

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

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

5、性搜索策略策略，比如單純形法單純形法、梯度下降法梯度下降法、爬山法爬山法、貪心法貪心法等，其基本思想是在狀態(tài)轉(zhuǎn)移過(guò)程中，只接受更好的狀態(tài)，拒絕惡化惡化的狀態(tài)。n全局性優(yōu)化算法主要用于求解非凸問(wèn)題或多峰問(wèn)題多峰問(wèn)題，通常使用概率性概率性搜索策略搜索策略，即狀態(tài)轉(zhuǎn)移規(guī)則狀態(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ī)則和合理的概率性狀態(tài)接收規(guī)則概率性狀態(tài)接收規(guī)則搜索新的更優(yōu)點(diǎn)，在確定的時(shí)間或搜索次數(shù)之內(nèi)停止算法。 396優(yōu)化算法簡(jiǎn)介二者需要結(jié)合二者需要結(jié)合n局部?jī)?yōu)

6、化算法由于易于陷入局部極優(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)解避免過(guò)早地陷入局部極優(yōu)解從而搜索到全局性最優(yōu)解。n通常，局部?jī)?yōu)化算法能夠快速地收斂到局部極優(yōu)解，而全局性優(yōu)化算法通過(guò)概率搜索可以獲得在概率意義上盡可能好的全局性最優(yōu)解區(qū)域，但是其局部極優(yōu)點(diǎn)搜索能力較低。這是全局搜索算法和局部搜索算法之間的固有矛盾固有矛盾。對(duì)此人們進(jìn)行了多種研究?；窘鉀Q方法基本解決方法在于二者的結(jié)合，即利用全局性優(yōu)化算法在整個(gè)可行域中搜索最優(yōu)區(qū)域，利用局部搜索算法搜索最優(yōu)區(qū)域中的最優(yōu)解。nMemetic算法算法就是全

7、局性搜索和局部性搜索相結(jié)合的算法的總稱。又可以稱為雜和優(yōu)化算法雜和優(yōu)化算法 (Hybrid Optimization Algorithm)。397內(nèi)容概要n優(yōu)化算法簡(jiǎn)介運(yùn)籌學(xué) n正交試驗(yàn)法nTABU禁忌搜索算法 n模擬退火算法n遺傳算法n現(xiàn)代優(yōu)化算法再述n課題組的工作398正交試驗(yàn)法正交試驗(yàn)法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)條件。其中的決策變量和取值分別叫做因素

8、和水平。尋優(yōu)時(shí)，先確定影響決策目標(biāo)的因素和水平，再選擇適當(dāng)?shù)恼槐恚纯砂凑槐戆才旁囼?yàn)，最后分析試驗(yàn)的結(jié)果和發(fā)現(xiàn)最佳的水平。399正交試驗(yàn)法正交試驗(yàn)法n正交表的形式為L(zhǎng)n(t1t2tm)，簡(jiǎn)記為L(zhǎng)n(tm)，其中n為試驗(yàn)數(shù)，m為因素?cái)?shù)，ti為水平數(shù)。正交設(shè)計(jì)法能夠確保決策變量具有最佳的散布性和代表性，因此獲得的最佳水平應(yīng)該具有相當(dāng)高的滿意度。n實(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)單易學(xué)，一般文化水平的人（比如初中以上）經(jīng)過(guò)幾天時(shí)間就可以掌握，因此該算法具有極其廣泛的使用范圍。其

9、難點(diǎn)在于特定正交表的構(gòu)造，人們正深入研究各種特殊正交表的構(gòu)造方法。 3910內(nèi)容概要n優(yōu)化算法簡(jiǎn)介運(yùn)籌學(xué) n正交試驗(yàn)法nTABU禁忌搜索算法 n模擬退火算法n遺傳算法n現(xiàn)代優(yōu)化算法再述n課題組的工作3911TABU禁忌搜索算法n禁忌搜索算法（tabu search） 是局部鄰域搜索算法的推廣，是人工智能在組合優(yōu)化算法中的一個(gè)成功應(yīng)用。Glover在1986年首次提出這一概念，進(jìn)而形成一套完整算法。n禁忌，就是禁止重復(fù)前面的工作。為了回避局部鄰域搜索陷入局部最優(yōu)的主要不足，采用一個(gè)禁忌表記錄已經(jīng)達(dá)到過(guò)的局部最優(yōu)點(diǎn)，在下一次搜索中，利用禁忌表中的信息不再或者有選擇地搜索這些點(diǎn)，以此來(lái)跳出局部最優(yōu)點(diǎn)

10、。nTabu算法由幾個(gè)基本要素的組合：鄰域，Tabu表及評(píng)價(jià)函數(shù)。鄰域與一般優(yōu)化技術(shù)中的定義一致；Tabu表是一個(gè)或數(shù)個(gè)數(shù)據(jù)序列，是對(duì)先前的數(shù)步搜索所作的記錄，記錄的方式有很多，記錄的長(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條件則接受，否則拒絕，直至迭代終止。 3912TABU禁忌搜索算法nTabu算法被認(rèn)為是人工智能在組合優(yōu)化中的成功應(yīng)用，但是仍有很多技術(shù)的細(xì)節(jié)問(wèn)題有待討論。如參數(shù)的選擇問(wèn)題，該問(wèn)題包括禁忌對(duì)象及其長(zhǎng)度、候選集合的確定等。另外還涉及

11、到評(píng)價(jià)函數(shù)、特赫規(guī)則、終止規(guī)則等的合理確定。n在提高搜索效率方面，文獻(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 Shop調(diào)度問(wèn)題上的應(yīng)用。電子學(xué)報(bào)，2001,29(5),622-625。 3913內(nèi)容概要n優(yōu)化算法簡(jiǎn)介運(yùn)籌學(xué) n正交試驗(yàn)法nTABU禁忌搜索算法 n模擬退火算法n遺傳算法

12、n現(xiàn)代優(yōu)化算法再述n課題組的工作3914模擬退火算法n模擬退火算法（simulated annealing algorithm, SAA）是一種重要的全局性啟發(fā)式概率搜索算法，其物理背景是固體的退火過(guò)程。 n歷史上，兩個(gè)人物對(duì)于SAA的發(fā)展起了關(guān)鍵性的作用，他們分別是N. Metropolis和S. Kirkpatrick。n在利用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

13、遷移到新的狀態(tài)j取決于Ei、Ej之間的關(guān)系：當(dāng)EjEi時(shí)，系統(tǒng)遷移到新的狀態(tài)；當(dāng)EjEi時(shí)，系統(tǒng)將以如下概率遷移到新的狀態(tài)3915模擬退火算法在大量遷移之后，系統(tǒng)趨于能量較低的平衡態(tài)，其微觀狀態(tài)的概率密度分布趨于Gibbs正則分布。n1982年，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)。n目前，模擬退火算法已經(jīng)廣泛地用于求解TSP、VLSI電路設(shè)計(jì)等NP完全問(wèn)題。1 Ej Ei.else即3916模擬退火算法n我國(guó)第一部系統(tǒng)討論模

14、擬退火算法的中文專著非數(shù)值并行算算法模擬退火算法比較詳細(xì)地討論了模擬退火算法的數(shù)學(xué)和物理背景、理論基礎(chǔ)以及實(shí)現(xiàn)形式，介紹了1994年以前國(guó)內(nèi)外一些學(xué)者在理論和應(yīng)用上的研究成果。這些成果主要是針對(duì)模擬退火算法性能的提高，如怎樣控制冷卻進(jìn)度表（cooling schedule）參數(shù)（即初始溫度、降溫策略、溫度終值準(zhǔn)則、Markov鏈長(zhǎng)），怎樣實(shí)現(xiàn)模擬退火算法的并行運(yùn)算，怎樣進(jìn)一步改進(jìn)模擬退火算法等。n這些改進(jìn)主要包括：選取合適的初始溫度、最優(yōu)保留策略、與局部搜索相結(jié)合、回火退火法等。需要說(shuō)明，文獻(xiàn)中的局部搜索法實(shí)質(zhì)上仍然是隨機(jī)搜索，只是僅接受優(yōu)化解，不接受惡化解。n近些年來(lái)，不少學(xué)者對(duì)于模擬退火算

15、法進(jìn)行了深入的研究和改進(jìn)。包括：討論模擬退火與傳統(tǒng)局部?jī)?yōu)化算法如單純形法、Powell方法等的結(jié)合7，研究鄰域結(jié)構(gòu)與選取狀態(tài)轉(zhuǎn)移隨機(jī)步長(zhǎng)方法以及相應(yīng)的降溫方案，如何采取合適的退火終止條件等。 3917模擬退火算法n基本算法（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 i:=jelseif exp(f(i)f(j)/Tk random0,1 the

16、n i:=j end; k:=k+1; CALCULATE-LENGTH(Lk); CALCULATE-CONTROL(Tk);until stopcriterionend;計(jì)算計(jì)算冷卻進(jìn)度表冷卻進(jìn)度表Markov鏈長(zhǎng)Metropolis規(guī)則3918模擬退火算法最初路徑算法結(jié)果目前最好結(jié)果3919模擬退火算法n一些文獻(xiàn)：1、康立山，謝云，尤矢勇等。非數(shù)值并行算法模擬退火算法。北京：科學(xué)出版社，1998年。2、王卓鵬，高國(guó)成，楊為平。一種改進(jìn)的快速模擬退火組合優(yōu)化法。系統(tǒng)工程理論與實(shí)踐，1999，(2): 7376。3、趙玉清，余志軍。加速全局優(yōu)化鮑威爾法和模擬退火法的組合。電子學(xué)報(bào)，1998，

17、26(9): 7577。4、楊若黎，顧基發(fā)。一種高效的模擬退火全局優(yōu)化算法。系統(tǒng)工程理論與實(shí)踐，1997，(5): 2935。3920內(nèi)容概要n優(yōu)化算法簡(jiǎn)介運(yùn)籌學(xué) n正交試驗(yàn)法nTABU禁忌搜索算法 n模擬退火算法n遺傳算法n現(xiàn)代優(yōu)化算法再述n課題組的工作3921遺傳算法nDarwin 的物種進(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)。染色體又是由DNA 和蛋白質(zhì)組成的。基因中保留著遺傳物質(zhì)。通過(guò)基因的復(fù)制(prod

18、uction)、交叉(crossover)和變異(mutation)實(shí)現(xiàn)生物的性狀的變異和遺傳。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é)構(gòu)的研究對(duì)象min（或max）f (x)，s.t. g(x) 0，xD 遺傳算法可以具有較好的搜索效果。3922遺傳算法n基本思路基本思路：第一步：建立研究對(duì)象的數(shù)學(xué)結(jié)構(gòu)模型，確定目標(biāo)函數(shù)類型（即求目標(biāo)函數(shù)的最大值還是最小值?）。 第二步：確

19、定表示可行解的染色體編碼方法，即確定個(gè)體基因型X及遺傳算法的搜索空間。 第三步：確定解碼方法，即確定由個(gè)體基因型X到相應(yīng)表現(xiàn)型的對(duì)應(yīng)關(guān)系或轉(zhuǎn)換關(guān)系。3923遺傳算法n基本思路基本思路：第四步：設(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)保留策略。3924遺傳算法n為了提高其搜索效率，可以在三個(gè)方面提出改進(jìn)措施

20、：1) 采用更好的搜索策略。采用更好的搜索策略。主要包括：精英策略（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)機(jī)制，通過(guò)引入正交設(shè)計(jì)法構(gòu)造出“正交交配”算子，從而在每個(gè)家庭內(nèi)部形成局部競(jìng)爭(zhēng)環(huán)境的進(jìn)化算法；利用小生境技術(shù)、聚類分析或狹義遺傳算法而

21、提出的分區(qū)域搜索遺傳算法等。3925遺傳算法2) 采用更加合理的編碼策略采用更加合理的編碼策略。如采用十進(jìn)制編碼，多維實(shí)數(shù)編碼，或根據(jù)模式定理將二進(jìn)制編碼的低階、高平均適應(yīng)度的長(zhǎng)定義距模式轉(zhuǎn)換為短定義距模式等。3)合理配置運(yùn)行參數(shù)合理配置運(yùn)行參數(shù)。遺傳算法的求解效率在很大程度上取決于編碼串長(zhǎng)度l（對(duì)于二進(jìn)制編碼）、種群規(guī)模M、交叉概率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)行了深入廣泛的討論。3926遺傳算法n編碼串長(zhǎng)度l直

22、接決定問(wèn)題的求解精度。選擇策略、交叉算子和變異算子對(duì)于種群早熟、收斂等有重大影響，不少工作對(duì)此進(jìn)行了有益的探討。適應(yīng)度函數(shù)f (M)是遺傳算法的一個(gè)瓶頸，人們針對(duì)不同問(wèn)題提出了許多不同的適應(yīng)度函數(shù)定義。 n最近有文獻(xiàn)研究了遺傳算法的一些統(tǒng)計(jì)性質(zhì)，提出進(jìn)化截止代數(shù)和平均截止代數(shù)的概念，指出進(jìn)化截止代數(shù)分布呈現(xiàn)典型的分布，還研究了遺傳算法的優(yōu)化效率。這種研究對(duì)于深刻理解遺傳算法非常有益。n事實(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ù)分布中主要

23、起到什么作用？3927內(nèi)容概要n優(yōu)化算法簡(jiǎn)介運(yùn)籌學(xué) n正交試驗(yàn)法nTABU禁忌搜索算法 n模擬退火算法n遺傳算法n現(xiàn)代優(yōu)化算法再述n課題組的工作3928現(xiàn)代優(yōu)化算法一般性描述一般性描述全局性優(yōu)化理論的一般性描述全局性優(yōu)化理論的一般性描述n首先，需要確定的是狀態(tài)的表示狀態(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ù)編碼與二進(jìn)制編碼之間就存在明確的一一對(duì)應(yīng)的關(guān)系。原碼編碼采用決策變量本身作為狀態(tài)參量，也是一種編碼方式，只不過(guò)我們已經(jīng)習(xí)以為常了。選擇不同的編碼方式

24、對(duì)于優(yōu)化效率具有不同的影響。我們采用C(x)表示的x編碼，稱為個(gè)體。3929現(xiàn)代優(yōu)化算法一般性描述一般性描述全局性優(yōu)化理論的一般性描述全局性優(yōu)化理論的一般性描述n兩種搜索方式：?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í)；多點(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ū)別。3930現(xiàn)代優(yōu)化算法一般性描述一般性描述全局性優(yōu)化理論的一般性描述全局性優(yōu)化理

25、論的一般性描述n兩種搜索策略：確定性和概率性。由于許多實(shí)際問(wèn)題的決策變量不連續(xù)，或者沒(méi)有解析表達(dá)式或者解析表達(dá)式比較復(fù)雜致使無(wú)法進(jìn)行理論分析，而且大多數(shù)問(wèn)題的極值數(shù)目未知，無(wú)法提供全局性搜索的確定性信息，因此通常采用概率性搜索策略，包括：1. 狀態(tài)轉(zhuǎn)移規(guī)則，2. 狀態(tài)接受規(guī)則。n狀態(tài)轉(zhuǎn)移規(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)镃反映f(x)的鄰域結(jié)構(gòu)鄰域結(jié)構(gòu)，合理的C應(yīng)該保證概率性搜索的狀態(tài)具有最大代表性最大代表性。這就要求C符合最佳概率分布最佳概率分布。3931現(xiàn)代優(yōu)化算法一般性描

26、述一般性描述全局性優(yōu)化理論的一般性描述全局性優(yōu)化理論的一般性描述n狀態(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)法3932現(xiàn)代優(yōu)化算法一些特例一些特例n在可行域中進(jìn)行純隨機(jī)性概率搜索，將獲得Monte Carlo方法方法，此時(shí)的狀態(tài)轉(zhuǎn)移完全是隨

27、機(jī)的完全是隨機(jī)的，沒(méi)有利用任何啟發(fā)信息。n隨機(jī)地從多個(gè)初始狀態(tài)出發(fā)進(jìn)行局部搜索，實(shí)際上是一種最原始的全局性和局部性優(yōu)化算法的結(jié)合，即多點(diǎn)隨機(jī)試探局部搜索法多點(diǎn)隨機(jī)試探局部搜索法，此時(shí)的啟發(fā)信息完全體現(xiàn)于局部搜索部分，全局性優(yōu)化部分仍然是隨機(jī)的和隨機(jī)的和盲目的盲目的。n利用禁忌表禁忌表記錄曾經(jīng)或已經(jīng)到達(dá)過(guò)的局部極優(yōu)解，下次搜索時(shí)利用該表信息不再或有選擇地搜索這些點(diǎn)，以此跳出局部極優(yōu)解，增加搜索的區(qū)域，是禁忌搜索禁忌搜索的基本思想。顯然這種搜索的效率是比較高的，但參數(shù)設(shè)置參數(shù)設(shè)置是一個(gè)需要認(rèn)真研究的問(wèn)題，涉及到禁忌對(duì)象禁忌對(duì)象、禁忌長(zhǎng)度禁忌長(zhǎng)度、候選集合候選集合、評(píng)價(jià)函數(shù)評(píng)價(jià)函數(shù)、特赦規(guī)則特赦規(guī)則

28、、終止規(guī)則終止規(guī)則等的合理確定。這里的全局性啟發(fā)信息體現(xiàn)在禁忌表。3933現(xiàn)代優(yōu)化算法一些特例一些特例n從可行域的某個(gè)初始狀態(tài)出發(fā)，按照符合一定概率分布的狀態(tài)轉(zhuǎn)移規(guī)則搜索最優(yōu)解，利用概率的方法接受新?tīng)顟B(tài)，即更好結(jié)果肯定接受，惡化結(jié)果按照一定概率接受，而且隨著搜索的進(jìn)行接受惡化解的概率逐漸變小，這是模擬退火模擬退火的基本思想。這種搜索沒(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)化。3934現(xiàn)代優(yōu)化算法一些特例一些特例n從可行域

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