第2章 進(jìn)化計(jì)算

第2章進(jìn)化計(jì)算

2.1進(jìn)化計(jì)算導(dǎo)論進(jìn)化是一個(gè)優(yōu)化過程，目的是在不斷變化的競(jìng)爭(zhēng)環(huán)境中提高某生物（或系統(tǒng)）的生存能力。幾個(gè)世紀(jì)以來，進(jìn)化作為一個(gè)概念，曾被激烈地討論過。直到今天，它仍是一個(gè)備受關(guān)注的話題。在不同的領(lǐng)域，進(jìn)化可以有不同的解釋。而本課程所關(guān)注的是生物中的進(jìn)化概念。目前，生物進(jìn)化仍是一個(gè)存在大量爭(zhēng)論的概念，對(duì)于它的定義，Lamarckian和Darwinian的觀點(diǎn)現(xiàn)已被廣泛接受。Darwin（1809-1882）被認(rèn)為是進(jìn)化理論和共同起源法則的奠基人，而Lamarck（1744-1829）可能是把生物進(jìn)化理論化的第一人。Jean-BaptisteLamarck的進(jìn)化理論是關(guān)于遺傳的，如獲得性狀的遺傳。其主要觀點(diǎn)是生物個(gè)體在生命期中逐漸適應(yīng)環(huán)境，并將性狀傳給后代，后代也能不斷適應(yīng)。根據(jù)Lamarck的理論，適應(yīng)的過程依賴于使用和丟棄這兩個(gè)概念：在一段時(shí)間中，生物個(gè)體丟棄掉它所不需要的性狀，表現(xiàn)出它需要的性狀。CharlesDarwin的自然選擇學(xué)說是生物進(jìn)化的基礎(chǔ)。Darwin的進(jìn)化論可以描述為：在一個(gè)資源有限、種群穩(wěn)定的世界中，每個(gè)生物個(gè)體都會(huì)與其他生物個(gè)體為了生存而競(jìng)爭(zhēng)。擁有優(yōu)良性狀的個(gè)體會(huì)更加容易獲得生存和繁殖的機(jī)會(huì)，它的性狀也更易于傳給后代。這些優(yōu)良性狀被下一代繼承，經(jīng)過一段時(shí)間便成為種群中的主要性狀。Darwin理論的第二部分提到，在幼年生物體的發(fā)育過程中，隨機(jī)事件會(huì)導(dǎo)致幼年生物體性狀的隨機(jī)改變。如果新出現(xiàn)的性狀有益于生物體，則該生物獲得生存的概率會(huì)有所提高。進(jìn)化計(jì)算（EC）是指以進(jìn)化過程作為計(jì)算模型的問題解決系統(tǒng)。如自然選擇、適者生存、繁殖等都是這個(gè)問題解決系統(tǒng)的基本組成部分。Lamarck進(jìn)化論一切物種都是其他物種演變和進(jìn)化而來的，而生物的演變和進(jìn)化是一個(gè)緩慢和連續(xù)的過程。環(huán)境的變化能夠引起生物的變異，環(huán)境的變化迫使生物發(fā)生適應(yīng)性的進(jìn)化。有神經(jīng)系統(tǒng)的動(dòng)物發(fā)生變異的原因，除了環(huán)境變化和雜交外，更重要是通過用進(jìn)廢退和獲得性狀遺傳。生物進(jìn)化的方向從簡(jiǎn)單到復(fù)雜，從低到高。最原始的生物起源于自然發(fā)生。生物并不起源于共同祖先。拉馬克曾以長(zhǎng)頸鹿的進(jìn)化為例，說明他的“用進(jìn)廢退”觀點(diǎn)。長(zhǎng)頸鹿的祖先頸部并不長(zhǎng)，由于干旱等原因。在低處已找不到食物，迫使它伸長(zhǎng)脖頸去吃高處的樹葉，久而久之，它的頸部就變長(zhǎng)了。一代又一代，遺傳下去，它的脖子越來越長(zhǎng)，終于進(jìn)化為現(xiàn)在我們所見的長(zhǎng)頸鹿。Darwin進(jìn)化論包括兩部分：遺傳(基因)變異；自然選擇生物不是靜止的，而是進(jìn)化的。物種不斷變異，舊物種消滅，新物種產(chǎn)生。生物的進(jìn)化是連續(xù)和逐漸，不會(huì)發(fā)生突變。生物之間存在一定的親緣關(guān)系，他們具有共同的祖先。自然選擇。生物過渡繁殖，但是它們的生存空間和食物有限，從而面臨生存斗爭(zhēng)，包括:種內(nèi)、種間以及生物與環(huán)境的斗爭(zhēng)。自然選擇是達(dá)爾文進(jìn)化論的核心。孟德爾學(xué)說1857年，身為神父，孟德爾通過對(duì)植物進(jìn)行一系列仔細(xì)的實(shí)驗(yàn)。孟德爾發(fā)現(xiàn)植物的父母單獨(dú)地把自身的性狀傳遞給子。至關(guān)重要的是，他還發(fā)現(xiàn)性狀不是單純地混合在一起，而是保持著獨(dú)立性：一株高的植物和一株矮的植物繁殖出來的后代要么是高的，要么是矮的，而不是介于兩者之間。表明性狀是分開獨(dú)立地遺傳給下一代，后來這稱為遺傳基因。讓人驚奇的是，孟德爾的重要發(fā)現(xiàn)被人們忽略了數(shù)十年，直到20世紀(jì)初才被人們認(rèn)可。

孟德爾學(xué)說1、分離定律：基因作為獨(dú)特的獨(dú)立單位而代代相傳。細(xì)胞中有成對(duì)的基本遺傳單位，在雜交的生殖細(xì)胞中，一個(gè)來自雄性親本，一個(gè)來自雌性親本.2、獨(dú)立分配定律：在一對(duì)染色體上的基因?qū)χ械牡任换蚰軌颡?dú)立遺傳。孟德爾的這兩條遺傳基本定律就是新遺傳學(xué)的起點(diǎn)，孟德爾也因此被后人稱為現(xiàn)代遺傳學(xué)的奠基人。新達(dá)爾文主義將達(dá)爾文進(jìn)化論和孟德爾-摩根基因相結(jié)合，成為現(xiàn)被廣泛接受的新達(dá)爾文主義。新達(dá)爾文注意認(rèn)為，只用種群上和物種內(nèi)的少量統(tǒng)計(jì)過程就可以充分地解釋大多數(shù)生命歷史，這些過程就是繁殖、變異、競(jìng)爭(zhēng)、選擇。繁殖是所有生命的共同特性；變異保證了任何生命系統(tǒng)能在正熵世界中連續(xù)繁殖自己；對(duì)于限制在有限區(qū)域中的不斷膨脹的種群來說，競(jìng)爭(zhēng)和選擇是不可避免的結(jié)論。生物學(xué)中的遺傳概念在生物細(xì)胞中，控制并決定生物遺傳特性的物質(zhì)是脫氧核糖核酸，簡(jiǎn)稱DNA。染色體是其載體。DNA是由四種堿基按一定規(guī)則排列組成的長(zhǎng)鏈。四種堿基不同的排列決定了生物不同的表現(xiàn)性狀。例如，改變DNA長(zhǎng)鏈中的特定一段（稱為基因），即可改變?nèi)梭w的身高。細(xì)胞在分裂時(shí)，DNA通過復(fù)制而轉(zhuǎn)移到新產(chǎn)生的細(xì)胞中，新的細(xì)胞就繼承了上一代細(xì)胞的基因。生物學(xué)中的遺傳概念有性生殖生物在繁殖下一代時(shí)，兩個(gè)同元染色體之間通過交叉而重組，亦即在兩個(gè)染色體的某一相同位置處DNA被切斷，其前后兩串分別交叉形成兩個(gè)新的染色體。在細(xì)胞進(jìn)行復(fù)制時(shí)可能以很小的概率產(chǎn)生某些復(fù)制差錯(cuò)，從而使DNA發(fā)生某種變異，產(chǎn)生新的染色體。這些新的染色體將決定新的個(gè)體（后代）的新的性狀。生物學(xué)中的遺傳概念在一個(gè)群體中，并不是所有的個(gè)體都能得到相同的繁殖機(jī)會(huì)，對(duì)生存環(huán)境適應(yīng)度高的個(gè)體將獲得更多的繁殖機(jī)會(huì)；對(duì)生存環(huán)境適應(yīng)度較低的個(gè)體，其繁殖機(jī)會(huì)相對(duì)較少，即所謂自然選擇。而生存下來的個(gè)體組成的群體，其品質(zhì)不斷得以改良，稱為進(jìn)化。生物的進(jìn)化是經(jīng)過無(wú)數(shù)次有利的進(jìn)化積累而成的，不同的環(huán)境保留了不同的變異后代！

Time

Initialpopulation（初始種群）Select（選擇）Crossover（交叉）AnotherCrossoverAmutation（變異）AnotherMutationOldpopulation+childrenNewPopulation:Generation2Generation3Generation4,etc…遺傳算法的基本思想首先實(shí)現(xiàn)從性狀到基因得映射，即編碼工作，然后從代表問題可能潛在解集得一個(gè)種群開始進(jìn)行進(jìn)化求解。初代種群（編碼集合）產(chǎn)生后，按照優(yōu)勝劣汰的原則，根據(jù)個(gè)體適應(yīng)度大小挑選（選擇）個(gè)體，進(jìn)行復(fù)制、交叉、變異，產(chǎn)生出代表新的解集的群體，再對(duì)其進(jìn)行挑選以及一系列遺傳操作，如此往復(fù)，逐代演化產(chǎn)生出越來越好的近似解。概念說明選擇：通過適應(yīng)度的計(jì)算，淘汰不合理的個(gè)體。類似于自然界的物競(jìng)天擇.復(fù)制：編碼的拷貝，類似于細(xì)胞分裂中染色體的復(fù)制。交叉：編碼的交叉重組，類似于染色體的交叉重組。變異：編碼按小概率擾動(dòng)產(chǎn)生的變化，類似于基因的突變。這個(gè)過程將導(dǎo)致種群像自然進(jìn)化一樣，后代種群比前代更加適應(yīng)環(huán)境，末代種群中得最優(yōu)個(gè)體經(jīng)過解碼（從基因到性狀的映射），可以作為問題近似最優(yōu)解。遺傳算法歷史1965年，Holland首次提出人工遺傳操作的重要性，并把這些應(yīng)用于自然系統(tǒng)和人工系統(tǒng)中。1967年，Bagley在他的論文中首次提出了遺傳算法這一術(shù)語(yǔ)，并討論了遺傳算法在自動(dòng)博弈中的應(yīng)用。1970年，Cavicchio把遺傳算法應(yīng)用于模式識(shí)別中。第一個(gè)把遺傳算法應(yīng)用于函數(shù)優(yōu)化的是Hollstien。遺傳算法歷史1975年Holland出版了他的著名專著《自然系統(tǒng)和人工系統(tǒng)的適應(yīng)性》該書系統(tǒng)地闡述了遺傳算法的基本理論和方法，并提出了對(duì)遺傳算法極為重要的模式理論，該理論首次確認(rèn)了結(jié)構(gòu)重組遺傳操作對(duì)于獲得隱并行性的重要性。同年，DeJong完成了他的重要論文《遺傳自適應(yīng)系統(tǒng)的行為分析》。他在該論文中所做的研究工作可看作是遺傳算法發(fā)展過程中的一個(gè)里程碑。遺傳算法歷史在一系列研究工作的基礎(chǔ)上，上世紀(jì)80年代由Goldberg進(jìn)行歸納總結(jié)，形成了遺傳算法的基本框架。產(chǎn)生初始種群計(jì)算適應(yīng)度是否滿足優(yōu)化準(zhǔn)則最佳個(gè)體選擇交叉變異解碼（基因到性狀）YN父代子代開始結(jié)束2.1.1一般進(jìn)化算法借助于對(duì)隨機(jī)選擇的若干個(gè)體進(jìn)行自然選擇的進(jìn)化過程，可以被看作是在染色體值空間中的一個(gè)搜索過程。在這個(gè)意義上，進(jìn)化算法就是一種對(duì)給定問題求最優(yōu)解的隨機(jī)搜索方法。該進(jìn)化搜索主要受到以下幾個(gè)部分的影響。（1）編碼：與染色體一樣，對(duì)問題的解編碼。（2）適應(yīng)度函數(shù)：用于求適應(yīng)度的函數(shù)，表征個(gè)體的生存能力。（3）初始化：種群的初始化。（4）選擇：選擇算子。（5）繁殖（reproduction）：繁殖算子。一個(gè)通用的進(jìn)化算法：一般進(jìn)化算法令代數(shù)計(jì)數(shù)器t=0;創(chuàng)建和初始化nx維的群體pop(0)，包含ns個(gè)個(gè)體；While終止條件不為真do

獲得每個(gè)個(gè)體xi(t)的適應(yīng)度值f(xi(t));

采用復(fù)制算法來產(chǎn)生后代;

選擇新群體pop(t+1);

進(jìn)入下一代，即t=t+1;end編碼在進(jìn)化計(jì)算中，每個(gè)個(gè)體都代表一個(gè)優(yōu)化問題的備選解；個(gè)體的性狀由染色體（也叫基因組）表示。而性狀是指最優(yōu)化問題所搜索的變量，每個(gè)需要優(yōu)化的變量被稱為基因——攜帶信息的最小單位。這些變量在可行域中的一組值叫等位基因。個(gè)體的性狀可以被分為兩類進(jìn)化信息：基因型和表現(xiàn)型?；蛐兔枋隽藗€(gè)體的基因組成，它繼承于父代。表現(xiàn)型是一個(gè)個(gè)體在特定環(huán)境里所表現(xiàn)出的行為特征，它定義了個(gè)體的樣貌。

在設(shè)計(jì)進(jìn)化算法中，一個(gè)重要的步驟是找到備選解的合適的表示方案（如染色體）。搜索算法的效率與復(fù)雜性很大程度上依賴于這個(gè)表示方案。不同典型方法中的不同進(jìn)化算法往往使用不同的表示方案。多數(shù)進(jìn)化算法把解表示為某種數(shù)據(jù)類型的向量，但遺傳編程是個(gè)例外，它把個(gè)體表示為樹的形式。以遺傳算法為例進(jìn)行說明解空間一個(gè)解的編碼染色體編碼其中的一個(gè)碼和碼所在的位置基因/基因位求下述二元函數(shù)的最大值：遺傳算法的運(yùn)算對(duì)象是表示個(gè)體的符號(hào)串，所以必須把變量x1,x2編碼為一種符號(hào)串。本題中，用無(wú)符號(hào)二進(jìn)制整數(shù)來表示。因x1,x2

為0~7之間的整數(shù)，所以分別用3位無(wú)符號(hào)二進(jìn)制整數(shù)來表示，將它們連接在一起所組成的6位無(wú)符號(hào)二進(jìn)制數(shù)就形成了個(gè)體的基因型，表示一個(gè)可行解。例如，基因型X＝101110所對(duì)應(yīng)的表現(xiàn)型是：x＝[5，6]。個(gè)體的表現(xiàn)型x和基因型X之間可通過編碼和解碼程序相互轉(zhuǎn)換。初始種群進(jìn)化算法是一種基于種群的隨機(jī)搜索算法。因此，每個(gè)進(jìn)化算法都會(huì)維護(hù)一個(gè)由備選解構(gòu)成的種群。應(yīng)用進(jìn)化算法解決優(yōu)化問題的第一步是產(chǎn)生一個(gè)初始種群。產(chǎn)生初始種群的標(biāo)準(zhǔn)方法是在可行域中產(chǎn)生隨機(jī)值，并分配給每個(gè)染色體的每個(gè)基因。隨機(jī)選擇的目標(biāo)是確保初始種群為整個(gè)搜索空間的均勻表示。如果初始種群沒有覆蓋搜索空間，則有可能使得未覆蓋區(qū)域被搜索過程所忽略。初始種群的大小會(huì)影響計(jì)算復(fù)雜性和空間搜索能力。大量的個(gè)體能增加多樣性，進(jìn)而提高種群的空間搜索能力。然而，個(gè)體越多，每代的計(jì)算量越大。當(dāng)每代的計(jì)算時(shí)間增加時(shí)，可能只需要較小的代數(shù)便能找到可以接受的解；另一方面，如果一個(gè)種群的個(gè)體數(shù)量較小，則只能探索空間中的較小部分。雖然每代的計(jì)算時(shí)間減少了，但進(jìn)化算法需要更多的代數(shù)才能收斂得到一個(gè)與大種群相當(dāng)?shù)慕Y(jié)果。X1=[011101]=[x1,x2]=[3,5]X2=[101011]=[x1,x2]=[5,3]X3=[011100]=[x1,x2]=[3,4]X4=[111001]=[x1,x2]=[7,1]遺傳算法是對(duì)群體進(jìn)行的進(jìn)化操作，需要給其淮備一些表示起始搜索點(diǎn)的初始群體數(shù)據(jù)。本例中，群體規(guī)模的大小取為4，即群體由4個(gè)個(gè)體組成，每個(gè)個(gè)體可通過隨機(jī)方法產(chǎn)生。適應(yīng)度函數(shù)在達(dá)爾文式的進(jìn)化模型里，擁有最好性狀的個(gè)體獲得生存和繁殖的機(jī)會(huì)更大。在進(jìn)化算法中，為確定一個(gè)個(gè)體的生存能力，我們用一個(gè)數(shù)學(xué)函數(shù)來表征染色體所表示的解有多好。

所謂適應(yīng)度函數(shù)f，將把一個(gè)染色體映射成一個(gè)標(biāo)量值：f:Гnx→R

式中，Г代表nx維染色體元素的數(shù)據(jù)類型。適應(yīng)度函數(shù)可以用目標(biāo)函數(shù)來表示。本例中，目標(biāo)函數(shù)總?cè)》秦?fù)值，并且是以求函數(shù)最大值為優(yōu)化目標(biāo)，故可直接利用目標(biāo)函數(shù)值作為個(gè)體的適應(yīng)度。注意：不同的優(yōu)化問題要求適應(yīng)度函數(shù)的形式不同。（1）在無(wú)約束優(yōu)化問題中，適應(yīng)度函數(shù)即為目標(biāo)函數(shù)。（2）在帶約束的優(yōu)化問題中，進(jìn)化算法的適應(yīng)度函數(shù)要包含兩個(gè)目標(biāo)：一個(gè)原始的目標(biāo)函數(shù)，另一個(gè)是約束懲罰函數(shù)。（3）在多目標(biāo)優(yōu)化問題（MOP）中，可以通過帶權(quán)重的聚集方法解決，適應(yīng)度函數(shù)為全部子目標(biāo)的加權(quán)和。另一種解決方法為基于Pareto的優(yōu)化算法。（4）在動(dòng)態(tài)和噪聲問題中，解的函數(shù)值隨著時(shí)間而改變，動(dòng)態(tài)適應(yīng)度函數(shù)依賴于時(shí)間，而噪聲函數(shù)往往會(huì)添加高斯噪聲成分。

適應(yīng)度函數(shù)的角色在進(jìn)化算法中非常重要。進(jìn)化算子，如選擇、交叉、變異和精英選擇，都會(huì)用適應(yīng)度函數(shù)來評(píng)估染色體。例如，當(dāng)選擇父代個(gè)體用于交叉時(shí)，選擇算子會(huì)更傾向最適應(yīng)的個(gè)體，而變異算子會(huì)傾向最不適應(yīng)的個(gè)體。選擇選擇是進(jìn)化算法中的主要算子之一，與達(dá)爾文的適者生存的概念直接相關(guān)，選擇算子的主要目標(biāo)是獲得更好的解。在每一代的結(jié)束，一個(gè)由備選解構(gòu)成的新種群會(huì)被選擇作為下一代種群。新種群可以僅從后代中選擇，或是同時(shí)從后代與父代中選擇。選擇算子的目標(biāo)是確保優(yōu)良個(gè)體能存活到下一代。下面介紹兩個(gè)最常用的選擇算子：（1）隨機(jī)選擇隨機(jī)選擇是最簡(jiǎn)單的選擇算子，它讓每個(gè)個(gè)體都有1/ns的概率被選擇（ns為種群中個(gè)體的總數(shù)）。不使用適應(yīng)度信息，這就意味著最好的個(gè)體與最差的個(gè)體有相同的幾率存活到下一代。

（2）比例選擇使選擇傾向于更具適應(yīng)性的個(gè)體，可使用一個(gè)正比于適應(yīng)度的概率分布用于個(gè)體選擇：（2）比例選擇使選擇傾向于更具適應(yīng)性的個(gè)體，可使用一個(gè)正比于適應(yīng)度的概率分布用于個(gè)體選擇：其中，為xi被選擇的概率。

在本例中，采用比例選擇算子來確定各個(gè)個(gè)體復(fù)制到下一代群體中的數(shù)量。具體操作過程如下：1）先計(jì)算出群體中所有個(gè)體的適應(yīng)度的總和

；2）其次計(jì)算出每個(gè)個(gè)體的相對(duì)適應(yīng)度的大小，它即為每個(gè)個(gè)體被遺傳到下一代群體中的概率；3）每個(gè)概率值組成一個(gè)區(qū)域，全部概率值之和為1；4）最后再產(chǎn)生一個(gè)0到1之間的隨機(jī)數(shù)，依據(jù)該隨機(jī)數(shù)出現(xiàn)在上述哪一個(gè)概率區(qū)域內(nèi)來確定各個(gè)個(gè)體被選中的次數(shù)。繁殖繁殖是從選擇的父代中應(yīng)用交叉和變異算子生成子代的過程。交叉是通過組合隨機(jī)選擇的兩個(gè)或多個(gè)父代個(gè)體的基因物質(zhì)生成新個(gè)體的過程。如果選擇關(guān)注的是最具適應(yīng)能力的個(gè)體，則選擇壓力可能會(huì)降低新種群的多樣性而引起過早收斂。

本例采用單點(diǎn)交叉的的方法，其具體操作過程是：（1）先對(duì)群體進(jìn)行隨機(jī)配對(duì)；（2）其次隨機(jī)設(shè)置交叉點(diǎn)位置；（3）最后再相互交換配對(duì)染色體之間的部分基因。變異是隨機(jī)改變?nèi)旧w基因值的過程。其主要目標(biāo)是使種群引入新的基因物質(zhì)，提高基因的多樣性。應(yīng)用變異的過程應(yīng)該注意不要破壞高適應(yīng)度個(gè)體的優(yōu)良基因?yàn)榇?，變異通常以較低的概率進(jìn)行。另一方面，變異概率也可與個(gè)體的適應(yīng)度成反比：適應(yīng)度越低的個(gè)體，變異越高。為了提高前期迭代的探索能力，變異概率可以初始為較大值，并隨著時(shí)間逐漸減少直到最后一代。本例中，我們采用基本位變異的方法來進(jìn)行變異運(yùn)算，其具體操作過程是：（1）首先確定出各個(gè)個(gè)體的基因變異位置，下表所示為隨機(jī)產(chǎn)生的變異點(diǎn)位置，其中的數(shù)字表示變異點(diǎn)設(shè)置在該基因處；（2）然后依照某一概率將變異點(diǎn)的原有基因值取反。對(duì)群體P(t)進(jìn)行一輪選擇、交叉、變異運(yùn)算之后可得到新一代的群體p(t+1)。從上表中可以看出，群體經(jīng)過一代進(jìn)化之后，其適應(yīng)度的最大值、平均值都得到了明顯的改進(jìn)。事實(shí)上，這里已經(jīng)找到了最佳個(gè)體“111111”。

繁殖可以使用替換機(jī)制，即當(dāng)且僅當(dāng)新產(chǎn)生的子代個(gè)體的適應(yīng)度優(yōu)于它的父代個(gè)體時(shí)，才進(jìn)行替換。終止條件在進(jìn)化算法中，進(jìn)化算子不斷迭代執(zhí)行，直到滿足終止條件。最簡(jiǎn)單的終止條件是限制進(jìn)化算法執(zhí)行的代數(shù)或是調(diào)用適應(yīng)度函數(shù)的次數(shù)。這個(gè)限制不能太小，否則進(jìn)化算法不會(huì)有充足的時(shí)間去探索未知空間。除了限制執(zhí)行時(shí)間，另一個(gè)用于確定種群是否收斂的標(biāo)準(zhǔn)也經(jīng)常使用。收斂可以不嚴(yán)格地定義為種群變得穩(wěn)定的時(shí)候，換句話說，就是在種群中沒有基因或表現(xiàn)特征改變時(shí)。以下是常用的一些收斂準(zhǔn)則。（1）當(dāng)連續(xù)幾代內(nèi)都沒有提高時(shí)則終止。如監(jiān)視最優(yōu)個(gè)體的適應(yīng)度，如果在一個(gè)給定大小的時(shí)間窗內(nèi)沒有顯著更新，則進(jìn)化算法可以終止。相反，如果此條件不滿足，則使用其它機(jī)制以增加多樣性來獲得更大的探索空間，如增加變異概率和變異次數(shù)。（2）當(dāng)種群中沒有改變時(shí)終止。在連續(xù)幾代內(nèi)，基因信息的平均改變量太小，則進(jìn)化算法可以終止。（3）當(dāng)?shù)玫揭粋€(gè)可接受的解時(shí)終止。如果x*(t)表示目標(biāo)函數(shù)的最優(yōu)值，則當(dāng)最優(yōu)個(gè)體xi，滿足，則一個(gè)可接受的解被找到。為收斂誤差，如果過大，則找到的可接受解較差；如果過小，則在給定的時(shí)間限制下，進(jìn)化算法很難終止。（4）當(dāng)目標(biāo)函數(shù)斜率接近0時(shí)終止。2.1.2進(jìn)化計(jì)算與經(jīng)典優(yōu)化算法經(jīng)典的優(yōu)化算法已經(jīng)在線性、二次型、強(qiáng)凸性、單模及其他某些特定問題方面取得了很大成功，而進(jìn)化計(jì)算則對(duì)連續(xù)、不可微、多模和帶噪問題更為有效。

進(jìn)化計(jì)算與經(jīng)典優(yōu)化算法（ClassicalOptimization，CO）之間的不同主要在于搜索過程及搜索過程中使用的信息。（1）搜索過程：經(jīng)典優(yōu)化算法使用確定的規(guī)則從搜索空間中的一點(diǎn)移到另一點(diǎn)。進(jìn)化計(jì)算則使用概率變換規(guī)則。同時(shí)，進(jìn)化計(jì)算還對(duì)搜索空間進(jìn)行并行搜索，而經(jīng)典優(yōu)化算法使用順序搜索。一個(gè)進(jìn)化算法從不同的初始點(diǎn)開始搜索，這樣能并行搜索大量空間。經(jīng)典優(yōu)化算法只能從一個(gè)點(diǎn)，連續(xù)地向最優(yōu)點(diǎn)調(diào)整移動(dòng)。（2）搜索表面信息：經(jīng)典優(yōu)化算法使用搜索空間的偏導(dǎo)數(shù)信息（通常為一階或二階）來啟發(fā)搜索路徑。另一方面，進(jìn)化計(jì)算不使用偏導(dǎo)數(shù)信息，它使用個(gè)體的適應(yīng)度來指導(dǎo)搜索。2.2進(jìn)化策略Rechenberg提出，既然生物過程已經(jīng)由進(jìn)化優(yōu)化，并且進(jìn)化本身就是一個(gè)生物過程，那么進(jìn)化必然也能優(yōu)化其本身。由Rechenberg在20世紀(jì)60年代首次提出，并由Schwefel進(jìn)一步發(fā)展的進(jìn)化策略（ES），就是基于“進(jìn)化的進(jìn)化”(theevolutionofevolution)。進(jìn)化策略同時(shí)考慮基因型和顯型，其重點(diǎn)在于個(gè)體的顯型表現(xiàn)。每個(gè)個(gè)體由其基因建造塊和一組對(duì)其所在環(huán)境個(gè)體表現(xiàn)建模的策略參數(shù)表示。進(jìn)化包括基因型特征的進(jìn)化和策略參數(shù)的進(jìn)化，其中基因型特征的進(jìn)化由策略參數(shù)控制。進(jìn)化策略和其它進(jìn)化計(jì)算范例另外的一個(gè)不同點(diǎn)是對(duì)于變異個(gè)體的接受僅發(fā)生在成功情況下。換句話說，變異個(gè)體只在變異結(jié)果的適應(yīng)度增加的情況下才被接受。進(jìn)化策略的另一個(gè)有趣的地方是子代可能由多于兩個(gè)親代產(chǎn)生。2.2.1一般進(jìn)化策略算法第一個(gè)進(jìn)化策略由于流體動(dòng)力學(xué)問題的實(shí)驗(yàn)優(yōu)化而被發(fā)明（I.Rechenberg.CyberneticSolutionPathofanExperimentalProblem.Technicalreport,MinisteryofAviation,1965）。這種早期的進(jìn)化策略的種群中只包含一個(gè)個(gè)體，并且只使用變異操作。在每一代中，變異后的個(gè)體與其父代進(jìn)行比較，并選擇較好的一個(gè)，這種選擇策略被稱為（1+1）策略。進(jìn)化策略中的個(gè)體用傳統(tǒng)的十進(jìn)制實(shí)型數(shù)表示，即：其中，Xt——第t代個(gè)體的數(shù)值，

N(0,σ)——服從正態(tài)分布的隨機(jī)數(shù)，其均值為零，標(biāo)準(zhǔn)差為σ。

一個(gè)進(jìn)化策略由如下幾個(gè)主要部分組成：（1）初始化：對(duì)于每個(gè)個(gè)體，其基因型被初始化以滿足問題邊界約束。策略參數(shù)同樣被初始化。（2）重組：子代由兩個(gè)及兩個(gè)以上的親代通過交叉算子得到。（3）變異：子代進(jìn)行變異，其變異步長(zhǎng)由自適應(yīng)策略參數(shù)決定。（4）評(píng)估：通過一個(gè)絕對(duì)適應(yīng)度函數(shù)來決定個(gè)體基因型所表示的解的質(zhì)量。（5）選擇：選擇算子在進(jìn)化策略中用于兩種目的。首先，選擇親代以重組；其次，決定何種子代可以生存以產(chǎn)生下一代。

一個(gè)實(shí)現(xiàn)進(jìn)化策略的一般框架由如下算法給出。其中，參數(shù)μ和λ分別表示親代和子代的個(gè)數(shù)。進(jìn)化策略算法設(shè)定代計(jì)數(shù)器，t=0；初始化策略參數(shù)；產(chǎn)生并初始化具有μ個(gè)個(gè)體的種群pop(0)；for每個(gè)個(gè)體xi(t)∈pop(t)do

計(jì)算適應(yīng)度f(wàn)(xi(t))；endwhile終止條件不為真dofori=1,2,……,λdo

隨機(jī)選擇ρ≥2個(gè)親代；

通過應(yīng)用親代基因型和策略參數(shù)上的交叉算子產(chǎn)生子代；

變異子代策略參數(shù)和基因型；計(jì)算子代適應(yīng)度；end

選擇新的種群pop(t+1);

進(jìn)入下一代，即t=t+1;end進(jìn)化策略的最初試驗(yàn)采用上述算法，主要采用單親本—單子代的搜索，即“（1+1）進(jìn)化策略((1+1)-ES)”，其中單個(gè)子代是由單個(gè)親本產(chǎn)生的，它們都被置于生存競(jìng)爭(zhēng)中，較弱的一個(gè)要被挑選出來消去。當(dāng)把這種算法用于函數(shù)優(yōu)化時(shí)，發(fā)現(xiàn)它有兩個(gè)缺點(diǎn)：1）各維取定常的標(biāo)準(zhǔn)差使得程序收斂到最優(yōu)解的速度很慢；2）點(diǎn)到點(diǎn)搜索的脆弱本質(zhì)使得程序在局部極值附近容易受停滯的影響（雖然此算法表明可以漸近地收斂到全局最優(yōu)點(diǎn)）。早期的(1十1)-ES，沒有體現(xiàn)群體的作用，只是單個(gè)個(gè)體在進(jìn)化，具有明顯的局限性。隨后，Rechenberg又提出(μ+1)-ES，在這種進(jìn)化策略中，父代有μ個(gè)個(gè)體(μ＞1)，并且引入重組(Recombination)算子，使父代個(gè)體組合出新的個(gè)體。在執(zhí)行重組時(shí)，從μ個(gè)父代個(gè)體中用隨機(jī)的方法任選兩個(gè)個(gè)體：然后從這兩個(gè)個(gè)體中組合出如下新個(gè)體：式中qi＝1或2，它以相同的概率針對(duì)i＝1，2，…，n隨機(jī)選取。對(duì)重組產(chǎn)生的新個(gè)體執(zhí)行突變操作，突變方式及σ的調(diào)整與(1+1)-ES相同。將突變后的個(gè)體與父代μ個(gè)個(gè)體相比較，若優(yōu)于父代最差個(gè)體，則代替后者成為下一代μ個(gè)個(gè)體新成員，否則，重新執(zhí)行重組和突變產(chǎn)生另一新個(gè)體。(μ+1)-ES和(1+1)-ES具有相同的策略：只產(chǎn)生一個(gè)新個(gè)體。(μ+1)-ES的特點(diǎn)在于：

1）采用群體，其中包含μ個(gè)個(gè)體；

2）增添重組算子，它相當(dāng)于遺傳算法中的交叉算子，從父代繼承信息構(gòu)成新個(gè)體。顯然，(μ+1)-ES比(1+1)-ES有了明顯的改進(jìn)，為進(jìn)化策略這種新的進(jìn)化算法奠定良好的基礎(chǔ)。

下面介紹兩個(gè)主要的進(jìn)化策略算子，選擇算子和交叉算子。

（1）選擇算子

在一個(gè)進(jìn)化策略中，選擇有兩個(gè)任務(wù)：（a）選擇需要重組的親代；（b）選擇新的種群。進(jìn)化策略的選擇有兩種：一種為(μ+λ)選擇，另一種為(μ,λ)選擇。(μ+λ)選擇（也被稱為加法策略）是從μ個(gè)父代個(gè)體及λ個(gè)子代新個(gè)體中確定性地?fù)駜?yōu)選出μ個(gè)個(gè)體組成下一代新群體。(μ,λ)選擇（也被稱為逗號(hào)策略）是從λ個(gè)子代新個(gè)體中確定性地?fù)駜?yōu)桃選μ個(gè)個(gè)體(要求λ＞μ)組成下一代群體，每個(gè)個(gè)體只存活一代，隨即被新個(gè)體頂替。粗略地看，似乎(μ+λ)選擇最好，它可以保證最優(yōu)個(gè)體存活，使群體的進(jìn)化過程呈單調(diào)上升趨勢(shì)。但是，深入分析后發(fā)現(xiàn)(μ+λ)選擇具有下述缺點(diǎn)：粗略地看，似乎(μ+λ)選擇最好，它可以保證最優(yōu)個(gè)體存活，使群體的進(jìn)化過程呈單調(diào)上升趨勢(shì)。但是，深入分析后發(fā)現(xiàn)(μ+λ)選擇具有下述缺點(diǎn)：1）(μ+λ)選擇保留舊個(gè)體，它有時(shí)會(huì)是過時(shí)的可行解，妨礙算法向最優(yōu)方向發(fā)展。(μ，λ)選擇全部舍棄舊個(gè)體，使算法始終從新的基礎(chǔ)上全方位進(jìn)化。2）(μ+λ)選擇保留舊個(gè)體，有時(shí)是局部最優(yōu)解，從而誤導(dǎo)進(jìn)化策略收斂于次優(yōu)解而不是最優(yōu)解。(μ，λ)選擇舍棄舊的優(yōu)良個(gè)體，容易進(jìn)化至全局員優(yōu)解。3）(μ+λ)選擇在保留舊個(gè)體的同時(shí)，也將進(jìn)化參數(shù)σ保留下來，不利于進(jìn)化策略中的自適應(yīng)調(diào)整機(jī)制。(μ，λ)選擇則恰恰相反，可促進(jìn)這種自適應(yīng)調(diào)整。最佳選擇策略的使用由需要解決的問題而定。高度回旋的搜索空間需要更好的搜索性，對(duì)此(μ,λ)-ES策略一般優(yōu)于(μ+λ)-ES，前者已成為當(dāng)前進(jìn)化策略的主流。在(μ+λ)-ES中，為了控制群體的多樣性和選擇的力度，比值μ/λ是一個(gè)重要參數(shù)，它對(duì)算法的收斂速度有很大影響。一方面，μ不能太小，否則群體太單調(diào)(例如μ＝1的極端情況)；另一方面，μ也不能太大，否則計(jì)算工作量過大。通常，μ取15或更多一些。λ數(shù)值的大小，類似于μ的作用，也要適當(dāng)。某些研究表明，比值μ/λ宜取1/7左右。也就是說，若μ=15，則λ宜取100。

（2）交叉算子(μ+1)-ES策略是第一個(gè)利用交叉算子的進(jìn)化策略。在進(jìn)化策略中，交叉被同時(shí)用于基因型（決策變量向量）和策略參數(shù)。交叉算子因用于產(chǎn)生單一子代的親代個(gè)數(shù)及組合產(chǎn)生子代的親代的基因型素材和策略參數(shù)不同而不同。一般來說，標(biāo)記(μ/ρ,+λ)用于表示在交叉算子中使用了ρ個(gè)親代?；讦训闹?，建立起如下兩種方法：1）局部交叉（ρ=2），一個(gè)子代從兩個(gè)隨機(jī)選擇的親代產(chǎn)生。2）全局交叉（2<ρ≤μ），超過兩個(gè)隨機(jī)選擇的親代被用于產(chǎn)生子代。ρ的值越大，產(chǎn)生的子代的多樣性也就越大。大ρ值的全局交叉提高了進(jìn)化策略的探索性。

在局部和全局交叉中，重組方式有如下三種：1）離散重組：真正的親代等位基因被用于構(gòu)造子代。對(duì)于基因型和策略參數(shù)向量的每一個(gè)成分，相應(yīng)隨機(jī)選擇的成分被使用。先隨機(jī)選擇兩個(gè)父代個(gè)體：然后將其分量進(jìn)行隨機(jī)交換，構(gòu)成子代新個(gè)體的各個(gè)分量，從而得出如下新個(gè)體：2）中值重組：這種重組方式也是先隨機(jī)選擇兩個(gè)父代個(gè)體，然后將父代個(gè)體各分量的平均值作為子代新個(gè)體的分量，構(gòu)成的新個(gè)體為：這時(shí)，新個(gè)體的各個(gè)分量兼容兩個(gè)父代個(gè)體信息，而在離散重組中則只含有某一個(gè)父代個(gè)體的因子。3）混雜重組：這種重組方式的特點(diǎn)在于父代個(gè)體的選擇上?；祀s重組時(shí)先隨機(jī)選擇一個(gè)固定的父代個(gè)體，然后針對(duì)子代個(gè)體每個(gè)分量再?gòu)母复后w中隨機(jī)選擇第二個(gè)父代個(gè)體。也就是說，第二個(gè)父代個(gè)體是經(jīng)常變化的。至于父代兩個(gè)個(gè)體的組合方式，既可以采用離散方式，也可以來用中值方式，甚至可以把中值重組中的1/2改為[0,1]之間的任一權(quán)值。研究表明，進(jìn)化策略采用重組后，明顯增加算法的收斂速度。Schwefel建議，對(duì)于目標(biāo)變量X宜用離散重組，對(duì)于策略因子σ及α宜用中值重組或混雜中值重組。2.2.2高級(jí)話題——約束處理方法現(xiàn)實(shí)世界中存在大量的優(yōu)化問題，特別是在科學(xué)研究和工程實(shí)踐領(lǐng)域，而這些問題往往都帶有約束。由于問題自身的不同特點(diǎn)，運(yùn)籌學(xué)中的傳統(tǒng)方法已難以獨(dú)立解決。進(jìn)化算法作為一種基于群體搜索的智能優(yōu)化方法，魯棒性強(qiáng)且具有全局搜索能力，十分適合求解約束優(yōu)化問題。因此，利用進(jìn)化算法求解這些問題己越來越受到國(guó)內(nèi)外研究者們的關(guān)注。

下面以單目標(biāo)約束優(yōu)化問題為例進(jìn)行說明。定義1約束優(yōu)化問題：不失一般性，以最小化為例，形式化描述如下：其中，f(x)為目標(biāo)函數(shù)，。為n維的搜索空問，常數(shù)向量l和u表示其邊界，定義為：F為可行區(qū)域，滿足m個(gè)附加的線性或非線性約束(m≥0)：其中，q為不等式約束的數(shù)目，m-q為等式約束的數(shù)目。對(duì)于一個(gè)不等式約束在可行區(qū)域F的某一點(diǎn)x處滿足，則稱該約束在點(diǎn)x處是活躍的。因此，所有等式約束在可行解區(qū)域F內(nèi)都是活躍的。一般而言，約束優(yōu)化問題是難以處理的，特別當(dāng)目標(biāo)函數(shù)和約束都是任意形式時(shí)。這也是運(yùn)籌學(xué)中對(duì)約束優(yōu)化問題進(jìn)行分類研究的原因。當(dāng)所有約束都是線性時(shí)，問題被稱為線性約束優(yōu)化問題；而此時(shí)若目標(biāo)函數(shù)為多項(xiàng)式且次數(shù)不超過2，則被稱為二次規(guī)劃問題。在二次規(guī)劃問題中，最有名的是線性規(guī)劃問題，即目標(biāo)函數(shù)也是線性的。對(duì)于這些特殊類別的約束優(yōu)化問題，運(yùn)籌學(xué)中已有成熟的方法進(jìn)行求解；而不屬于這些類別的問題則往往難以求解。求解約束優(yōu)化問題的另一個(gè)難點(diǎn)在于局部最優(yōu)解。因?yàn)榫植孔顑?yōu)解能夠滿足函數(shù)求導(dǎo)上的數(shù)學(xué)性質(zhì)，則基于梯度方法的優(yōu)化技術(shù)讓往只能找到一個(gè)局部最優(yōu)解。對(duì)于約束優(yōu)化問題，建立一個(gè)確定性的全局優(yōu)化方法(優(yōu)于窮舉搜索)是不可能的。進(jìn)化算法是一種智能的全局優(yōu)化方法，可以求解不同類型的問題(如問題不連續(xù)或不可微)，因此利用進(jìn)化算法進(jìn)行約束優(yōu)化也越來越受到關(guān)注。其中，最為關(guān)鍵的問題就是如何進(jìn)行有效的約束處理，即如何有效均衡在可行區(qū)域與不可行區(qū)域的搜索。進(jìn)化算法中的約束處理是將搜索偏向于可行區(qū)域，但為避免算法陷入局部最優(yōu)，也需要考慮不可行區(qū)域的搜索。目前，進(jìn)化算法中的約束處理方法可分類如下：（1）

傳統(tǒng)的懲罰函數(shù)法該方法最初由Courant于20世紀(jì)40年代提出，隨后由Carroll、Fiacco和McCormick進(jìn)行了擴(kuò)展。該方法的基本思想是：通過對(duì)不可行解的目標(biāo)函數(shù)值加上（或減去）一個(gè)約束違反程度值，即對(duì)不可行解進(jìn)行懲罰，將約束優(yōu)化問題轉(zhuǎn)換為不帶約束的優(yōu)化問題。一般而言，懲罰函數(shù)法具有兩種方式：外部方式和內(nèi)部方式。在外部方式中，搜索從不可行區(qū)域向可行區(qū)域移動(dòng)。而在內(nèi)部方式中，懲罰項(xiàng)的大小和解與約束邊界的距離成反比關(guān)系，即當(dāng)解接近約束邊界時(shí)，懲罰項(xiàng)將趨于無(wú)窮大。內(nèi)部方式最大的不足是初始群體中要有一個(gè)可行解，而對(duì)某些問題而言，找到可行解就是一個(gè)NP-hard問題。此外，目前懲罰函數(shù)法的研究也以外部方式為主。外部懲罰函數(shù)的一般形式可表示為：其中，ri和cj是懲罰系數(shù)，為正常數(shù)，Gi(x)和Hj(x)分別是不等式約束gi(x)和等式約束hj(x)的函數(shù)，一般定義為：其中，β和γ一般取值1或2。在求解約束優(yōu)化問題時(shí)，也常將等式約束轉(zhuǎn)換為不等式約束，即其中δ為事先設(shè)定的一個(gè)很小的正常數(shù)。理論上而言，懲罰系數(shù)應(yīng)盡可能的小，使得不可行解剛好不是最優(yōu)的，這被稱為最小懲罰準(zhǔn)則(mimimumpenaltyrule)。因?yàn)閼土P過大或過小，都不利于進(jìn)化算法找到可行的最優(yōu)解；若懲罰過大，算法雖能快速收斂到可行區(qū)域，但當(dāng)問題在搜索空間上具有多個(gè)不連續(xù)的可行區(qū)域時(shí)，算法往往只能找到其一，則很可能找到一個(gè)可行的局部最優(yōu)解；若懲罰過小，算法則不能有效地在可行區(qū)域中進(jìn)行搜索，大部分搜索被浪費(fèi)在不可行區(qū)域上，特別的，當(dāng)問題的可行區(qū)域十分小時(shí)，算法有可能找不到可行解。因此，設(shè)置合適的懲罰系數(shù)成為進(jìn)化算法能否找到最優(yōu)可行解的關(guān)鍵，也成為懲罰函數(shù)法能否有效求解約束優(yōu)化問題的關(guān)鍵，但懲罰系數(shù)往往與問題相關(guān)，難以設(shè)置。外部方式的懲罰函數(shù)可分類如下：靜態(tài)懲罰、動(dòng)態(tài)懲罰、退火懲罰、反饋懲罰、隔離懲罰和死亡懲罰等。（2）采用特殊的編碼和算子在求解一些（特別困難的）問題時(shí)，常用的編碼方式往往不再有效，即在此編碼下的搜索空間十分復(fù)雜。因此，對(duì)于這些問題，采用特殊的編碼方式來簡(jiǎn)化搜索空間，同時(shí)采用特殊的算子來保持解的可行性，將十分有效。Davis在其著作中利用該方法求解了一系列實(shí)際問題，Michalewicz在開發(fā)的GENOCOP（GeneticalgorithmforNumericalOptimizationforConstrainedProblems）系統(tǒng)中也采用了該方法。特別的，對(duì)于那些連可行解都難以找到的問題，該方法的優(yōu)勢(shì)將更為明顯?？傊摲椒ㄗ畲蟮膬?yōu)勢(shì)在于能快速找到可行解，因?yàn)椴捎昧颂厥獾木幋a和算子；但也因此，該方法的求解范圍受到了限制，只能用于求解某一類的約束優(yōu)化問題。（3）修復(fù)方法對(duì)于很多組合優(yōu)化問題而言，如旅行商問題(TravelingSalesmanProblem)、背包問題(KnapsackProblem)等，將不可行解修復(fù)為可行解往往十分簡(jiǎn)單。修復(fù)得到的可行解，可僅用于適應(yīng)度的評(píng)估，也可以一定概率替換群體中原來的不可行解。Liepins及其同事在多種組合優(yōu)化問題上進(jìn)行了實(shí)驗(yàn)對(duì)比，結(jié)果表明采用修復(fù)方法的進(jìn)化算法在性能上具有明顯的優(yōu)勢(shì)。對(duì)于修復(fù)方法而言，關(guān)鍵問題是如何設(shè)計(jì)修復(fù)策略，即將不可行解有效地轉(zhuǎn)換為可行解的方法。然而，目前并沒有標(biāo)準(zhǔn)的設(shè)計(jì)方法，但可以采用貪心方法和隨機(jī)方法等。修復(fù)方法的另一個(gè)問題就是修復(fù)后的可行解以多大的概率去替換原來的不可行解。從實(shí)驗(yàn)結(jié)果上來看，對(duì)組合優(yōu)化問題，Orvosh和Davis指出當(dāng)替換概率為5％時(shí)，算法的性能達(dá)到最優(yōu)；對(duì)非線性約束的數(shù)值優(yōu)化問題，MichaIewicz指出15％的替換概率是最佳的選擇。但是，這些都只是經(jīng)驗(yàn)值，并沒有充分的理論依據(jù)。綜上，當(dāng)修復(fù)代價(jià)較低且不會(huì)引起太大的搜索偏向時(shí)，修復(fù)方法是一個(gè)很好的選擇。然而，該方法與問題相關(guān)，即每個(gè)問題都需要特定的修復(fù)方法。（4）分離目標(biāo)和約束的方法該方法是對(duì)目標(biāo)函數(shù)和約束違反程度分別處理，避開了傳統(tǒng)懲罰函數(shù)法中懲罰系數(shù)難以選擇的問題。但從本質(zhì)上而言，該方法是一種不需要懲罰系數(shù)的懲罰函數(shù)法，可以說是對(duì)傳統(tǒng)懲罰函數(shù)法的擴(kuò)展，也是目前進(jìn)化約束優(yōu)化研究中的熱點(diǎn)。約束違反程度一般定義為：其中，表示示第i個(gè)約束的違反程度，具體定義如下：其中δ為事先設(shè)定的一個(gè)很小的正常數(shù)。分離目標(biāo)和約束的方法避開了懲罰系數(shù)難以選擇的困難，是一種更為有效且通用的約束處理機(jī)制，但并沒有從本質(zhì)上解決如何有效地均衡可行區(qū)域與不可行區(qū)域搜索的問題。（5）混合方法該類方法是在進(jìn)化算法中采用另一種優(yōu)化技術(shù)（常為數(shù)值優(yōu)化方法）來進(jìn)行約束處理。其中，主要的優(yōu)化技術(shù)有：拉格朗日方法、數(shù)學(xué)規(guī)劃方法、模糊邏輯方法等。這些技術(shù)為進(jìn)化約束優(yōu)化提供了新的解決思路，但往往也將這些方法的不足帶到了混合算法中。在以上的五類方法中，懲罰函數(shù)法（包括分離目標(biāo)和約束的方法）由于簡(jiǎn)單、有效，是目前進(jìn)化約束優(yōu)化研究中最為常用的約束處理方法。綜上所述，如何有效均衡可行區(qū)域和不可行區(qū)域的搜索始終是進(jìn)化約束優(yōu)化中最為核心的問題。目前的研究工作雖取得了一定的進(jìn)展，但對(duì)于等式約束很多或變量很多的約束優(yōu)化問題而言，目前的約束處理方法仍難以進(jìn)行有效搜索，值得我們進(jìn)一步研究。2.2.3高級(jí)話題——多目標(biāo)優(yōu)化現(xiàn)實(shí)世界中的很多優(yōu)化問題都具有多個(gè)相互沖突的目標(biāo)。例如投資問題，一般希望投入資金最少、風(fēng)險(xiǎn)最低且收益最大。若沒有先驗(yàn)知識(shí)，單目標(biāo)優(yōu)化中的方法已難以有效地求解這類問題。多目標(biāo)優(yōu)化問題(MultiobjectiveOptimizationProblem，簡(jiǎn)稱MOP)的定義如下：定義1多目標(biāo)優(yōu)化問題：不失一般性，以最小化問題為例，形式化描述為：其中，表示n維決策空間x中的一個(gè)決策向量，與分別表示決策空間第i維的下界與上界，為第k個(gè)目標(biāo)函數(shù)。在多目標(biāo)優(yōu)化問題中，由于目標(biāo)之前往往存在沖突，則所有目標(biāo)不可能同時(shí)達(dá)到最優(yōu)，因此多目標(biāo)優(yōu)化問題的最優(yōu)解通常是一個(gè)集合。為描述這樣的集合，我們先給出Pareto支配的概念。

定義2Pareto支配：對(duì)于決策空間X中的任意兩個(gè)決策向量a和b，a支配b即

當(dāng)當(dāng)且僅當(dāng)(以最小化為例進(jìn)行討論)即向量a的目標(biāo)值都不大于向量b的目標(biāo)值，且至少存在一個(gè)目標(biāo)，向量a對(duì)應(yīng)的目標(biāo)值嚴(yán)格小于向量b對(duì)應(yīng)的目標(biāo)值。定義3Pareto最優(yōu)解：對(duì)決策空間X中的任一向量a，a為Pareto最優(yōu)，當(dāng)且僅當(dāng)即決策空間X中不存在Pareto支配向量a的決策向量。定義4Pareto最優(yōu)解集(ParetooptimaISet，簡(jiǎn)稱POS)：由決策空間x中的所有Pareto最優(yōu)解構(gòu)成，設(shè)該集合為P，具體定義如下：并定義該集合對(duì)應(yīng)的目標(biāo)向量集合為Pareto最優(yōu)前沿(ParetooptimalFront，簡(jiǎn)稱為POF)。從上述定義中可以看到，多目標(biāo)優(yōu)化的目標(biāo)不是找到單個(gè)解，而是獲得一個(gè)解集，并能滿足如下兩個(gè)要求：（1）逼近性：解集在目標(biāo)空間中與Pareto最優(yōu)前沿的距離盡可能?。唬?）分布性：解集在目標(biāo)空間的分布性盡可能的好，即其分布可以表示或近似表示Pareto最優(yōu)前沿的分布。因此，多目標(biāo)優(yōu)化與單目標(biāo)優(yōu)化的主要區(qū)別體現(xiàn)在：

（1）優(yōu)化目標(biāo)的區(qū)別：多目標(biāo)優(yōu)化需要同時(shí)滿足逼近性和分布性；單目標(biāo)優(yōu)化只要滿足逼近性即可；

（2）搜索空間的區(qū)別：多目標(biāo)優(yōu)化不僅需要考慮決策空間，還需要考慮目標(biāo)空間；單目標(biāo)優(yōu)化只需考慮決策空間；（3）人工限制的區(qū)別：現(xiàn)實(shí)世界中的優(yōu)化問題往往都具有多個(gè)目標(biāo)，以前的研究者通過人工限制方式將其轉(zhuǎn)換為單目標(biāo)優(yōu)化問題，而多目標(biāo)優(yōu)化則可以不需要人工限制的介入。按照使用問題先驗(yàn)知識(shí)的程度，多目標(biāo)優(yōu)化傳統(tǒng)方法可分為如下四類：（1）不使用先驗(yàn)知識(shí)的方法，即搜索前后都不使用先驗(yàn)知識(shí)；（2）搜索后使用先驗(yàn)知識(shí)的方法，即找到最優(yōu)解集后再按先驗(yàn)知識(shí)選擇；（3）搜索前使用先驗(yàn)知識(shí)的方法，即按先驗(yàn)知識(shí)搜索最優(yōu)解集；（4）交互方法，即搜索過程中使用先驗(yàn)知識(shí)。目前，代表性的傳統(tǒng)方法主要有：（1）加權(quán)求和方法通過對(duì)目標(biāo)加權(quán)求和，將多目標(biāo)優(yōu)化問題轉(zhuǎn)換為單目標(biāo)優(yōu)化問題：其中，加權(quán)系數(shù)λi≥0，且滿足。該方法是求解多目標(biāo)優(yōu)化問題最簡(jiǎn)單的方法，且對(duì)于Pareto最優(yōu)前沿為凸的問題，理論上而言，該方法可保證找到Pareto最優(yōu)解集中的任何一個(gè)解。但當(dāng)決策空間與目標(biāo)空間的映射關(guān)系是非線性時(shí)，一組均勻分布的加權(quán)系數(shù)并不能找到一組均勻分布的解集；另外，使用不同的加權(quán)系數(shù)并不能保證找到不同的Pareto最優(yōu)解。而該方法最大的缺陷在于不能找到Pareto最優(yōu)前沿為凹的解。（2）ε-約束方法Haimes等人于1971年提出將某個(gè)目標(biāo)函數(shù)作為優(yōu)化目標(biāo)，而約束其它目標(biāo)函數(shù)的方法來求解多目標(biāo)優(yōu)化問題，具體方式如下：其中εi

表示約束參數(shù)，fk(x)為優(yōu)化目標(biāo)。通過設(shè)置不同的εi，該方法就可以找到多個(gè)不同的Pareto最優(yōu)解，且對(duì)優(yōu)化問題Pareto最優(yōu)前沿的凸凹性不敏感。但是，設(shè)置合適的εi值，往往需要先驗(yàn)知識(shí)，特別是當(dāng)優(yōu)化問題的目標(biāo)數(shù)增多時(shí)。（3）Benson方法該方法于1978年由Benson提出，具體方式如下：其中，z為目標(biāo)空間上的向量。該方法的目標(biāo)就是最大化向量f(x)與向量z構(gòu)成的超立方體的周長(zhǎng)，因此該問題的最優(yōu)解是一個(gè)Pareto最優(yōu)解。通過設(shè)定不同的向量z，就可以獲得不同的Pareto最優(yōu)解；且設(shè)置合適的向量z，還可以找到非凸區(qū)域上的Pareto最優(yōu)解。但當(dāng)目標(biāo)函數(shù)是不可微時(shí)，基于梯度的方法往往很難求解。（4）目標(biāo)規(guī)劃方法目標(biāo)規(guī)劃方法最初是由Charnes等人于1955年在求解單目標(biāo)線性規(guī)劃問題時(shí)提出的，并在lgnizio和Lee等人的工作之后受到關(guān)注。Romero于1991年對(duì)該方法進(jìn)行了深入的總結(jié)。該方法的主要思想如下：對(duì)目標(biāo)函數(shù)設(shè)置預(yù)定目標(biāo)，即目標(biāo)函數(shù)的期望值，并找到能達(dá)到或最接近期望值的解。該方式的主要方式有：加權(quán)的目標(biāo)規(guī)劃方法、字典序的目標(biāo)規(guī)劃方法和最小最大的目標(biāo)規(guī)劃方法。

該方法的主要特點(diǎn)是求解效率較高，但需要先驗(yàn)知識(shí)。

可以看到，傳統(tǒng)方法在求解多目標(biāo)優(yōu)化問題時(shí)往往存在困難（特別是期望獲得多個(gè)Pareto最優(yōu)解時(shí)），主要體現(xiàn)在：（1）傳統(tǒng)方法在一次運(yùn)行中只能獲得一個(gè)Pareto最優(yōu)解，因?yàn)閭鹘y(tǒng)方法都是將多目標(biāo)優(yōu)化問題轉(zhuǎn)化為單目標(biāo)優(yōu)化問題進(jìn)行求解；（2）當(dāng)Pareto前沿為凹時(shí)，一些傳統(tǒng)方法不能確保找到所有的Pareto最優(yōu)解；（3）幾乎所有的傳統(tǒng)方法都需要一定的先驗(yàn)知識(shí)。而傳統(tǒng)方法最大的優(yōu)勢(shì)是在理論上可以收斂到Pareto最優(yōu)解集。

相對(duì)于上述傳統(tǒng)方法，進(jìn)化算法作為一種群體搜索算法，十分適合求解多目標(biāo)優(yōu)化問題。主要因?yàn)椋海?）進(jìn)化算法在一次運(yùn)行中可以獲得多個(gè)Pareto最優(yōu)解；（2）進(jìn)化算法對(duì)問題自身的要求低，可以用于不同類型問題。(如不可微、不連續(xù)的問題)的求解。2.3差分進(jìn)化

差分進(jìn)化（DE）是一個(gè)由Storn和Price在1995年提出的社會(huì)性的、基于種群的搜索策略。和其它進(jìn)化算法（EA）一樣，DE是一種模擬生物進(jìn)化的隨機(jī)模型，通過反復(fù)迭代，使得那些適應(yīng)環(huán)境的個(gè)體被保存了下來。但相比于進(jìn)化算法，DE保留了基于種群的全局搜索策略，采用實(shí)數(shù)編碼、基于差分的簡(jiǎn)單變異操作和一對(duì)一的競(jìng)爭(zhēng)生存策略，降低了遺傳操作的復(fù)雜性。同時(shí)，DE特有的記憶能力使其可以動(dòng)態(tài)跟蹤當(dāng)前的搜索情況，以調(diào)整其搜索策略，具有較強(qiáng)的全局收斂能力和魯棒性，且不需要借助問題的特征信息，適于求解一些利用常規(guī)的數(shù)學(xué)規(guī)劃方法所無(wú)法求解的復(fù)雜環(huán)境中的優(yōu)化問題。2.3.1基本的差分進(jìn)化DE算法主要用于求解連續(xù)變量的全局優(yōu)化問題，其主要工作步驟與其他進(jìn)化算法基本一致，主要包括變異(Mutation)、交叉(Crossover)、選擇(Selection)三種操作。

算法的基本思想是從某一隨機(jī)產(chǎn)生的初始群體開始，利用從種群中隨機(jī)選取的兩個(gè)個(gè)體的差向量作為第三個(gè)個(gè)體的隨機(jī)變化源，將差向量加權(quán)后按照一定的規(guī)則與第三個(gè)個(gè)體求和而產(chǎn)生變異個(gè)體，該操作稱為變異。然后，變異個(gè)體與某個(gè)預(yù)先決定的目標(biāo)個(gè)體進(jìn)行參數(shù)混合，生成試驗(yàn)個(gè)體，這一過程稱之為交叉。如果試驗(yàn)個(gè)體的適應(yīng)度值優(yōu)于目標(biāo)個(gè)體的適應(yīng)度值，則在下一代中試驗(yàn)個(gè)體取代目標(biāo)個(gè)體，否則目標(biāo)個(gè)體仍保存下來，該操作稱為選擇。在每一代的進(jìn)化過程中，每一個(gè)體矢量作為目標(biāo)個(gè)體一次，算法通過不斷地迭代計(jì)算，保留優(yōu)良個(gè)體，淘汰劣質(zhì)個(gè)體，引導(dǎo)搜索過程向全局最優(yōu)解逼近。設(shè)f是最小化適應(yīng)度函數(shù)，適應(yīng)度函數(shù)以實(shí)數(shù)向量的形式取一個(gè)候選方案作為參數(shù)，給出一個(gè)實(shí)數(shù)數(shù)值作為候選方案的輸出適應(yīng)值。其目的是在搜索空間的所有方案

p中找到

m使得

f(m)≤f(p)。最大化是找到一個(gè)

m使得

f(m)≥f(p)。

設(shè)

X=(x1,x2,…,xn)∈?n是種群中一個(gè)個(gè)體，基本的差分進(jìn)化算法如下所述：

（1）在搜索空間中隨機(jī)地初始化所有的個(gè)體。

（2）重復(fù)如下操作直到滿足終止條件（最大迭代數(shù)或者找到滿足適應(yīng)值的個(gè)體）。（3）隨機(jī)地從種群中選擇三個(gè)彼此不同的個(gè)體

a，b和

c。

（4）選擇一個(gè)隨機(jī)索引

R∈{1,...,n}，n是被優(yōu)化問題的維數(shù)。

（5）通過對(duì)每個(gè)

i∈{1,...,n}進(jìn)行如下的迭代，計(jì)算可能的新個(gè)體Y=[y1,...,yn]生成一個(gè)隨機(jī)數(shù)

ri~U(0,1)；

1）如果(i=R)或者(ri<CR)，

yi=ai+F(bi?ci)，否則

yi=xi；

2）如果(f(yi)<f(xi))，則在種群中使用改進(jìn)的新生成的

yi替換原來的

xi，否則不變。

（6）選擇具有最小適應(yīng)度值的

xi作為搜索的結(jié)果。其中：F∈[0,2]為縮放因子，CR∈[0,1]為交叉因子，種群大小NP>3。

基本差分進(jìn)化算法的一般框架由如下算法給出。差分進(jìn)化算法設(shè)定代計(jì)數(shù)器，t=0；初始化控制參數(shù)β和pr；產(chǎn)生并初始化具有ns個(gè)個(gè)體的種群pop(0)；while終止條件不為真dofor每個(gè)個(gè)體xi(t)∈pop(t)do

計(jì)算適應(yīng)度f(wàn)(xi(t))；通過應(yīng)用變異算子產(chǎn)生測(cè)試向量ui(t)；通過應(yīng)用交叉算子產(chǎn)生子代x’i(t)；iff(x’i(t))優(yōu)于f(xi(t))then

將x’i(t)加入pop(t+1);endelse將xi(t)加入pop(t+1);endendend將最佳適應(yīng)度的個(gè)體作為解返回。2.3.1.1差異向量

個(gè)體的位置提供了關(guān)于適應(yīng)度場(chǎng)景的有價(jià)值的信息。一個(gè)好的均勻隨機(jī)初始化算法被用于構(gòu)建初始種群。之間距離很大的初始個(gè)體將提供一個(gè)關(guān)于整個(gè)搜索空間的良好表示。之后，隨著搜索進(jìn)度，個(gè)體之間的距離變小，所有的個(gè)體收斂到一個(gè)相同的解。記住個(gè)體之間的初始距離尺度受種群的大小影響。種群中個(gè)體數(shù)量越多，則距離尺度越小。

個(gè)體間的距離是當(dāng)前種群多樣性的一個(gè)很好的指標(biāo)，為了使種群聯(lián)系到一點(diǎn)，步長(zhǎng)的尺度應(yīng)當(dāng)被排序。如果存在之間距離很遠(yuǎn)的個(gè)體，個(gè)體應(yīng)該采用更大的步長(zhǎng)以探索盡可能多的搜索空間。另一方面，如果個(gè)體之間的距離很近，應(yīng)當(dāng)采用小步長(zhǎng)來探索局部空間。該行為是由差分進(jìn)化通過計(jì)算變異步長(zhǎng)作為隨機(jī)選擇的個(gè)體之間的加權(quán)差異而獲得的。因此變異的第一步是首先計(jì)算一個(gè)或多個(gè)差異向量，之后使用這些差異向量來判斷步長(zhǎng)的尺度和方向。

使用向量差分以存檔變量有一些優(yōu)點(diǎn)：（1）首先，以當(dāng)前種群表示的關(guān)于適應(yīng)度場(chǎng)景的信息用于指導(dǎo)搜索方向。（2）其次，由于中心極限定理（中心極限定理指出當(dāng)隨機(jī)變量的采樣數(shù)量趨于無(wú)窮時(shí)，其隨機(jī)變量的分布服從高斯分布），變異步長(zhǎng)呈高斯分布，使得種群顯著增大以允許足夠數(shù)量的差異向量。差異向量形成的分布的均值總是零，提供從種群中均勻選擇的用于計(jì)算差異向量的個(gè)體。在個(gè)體被均勻選擇的情況下，差異向量(xi1-xi2)和(xi2-xi1)以相同的概率出現(xiàn)，這里xi1和xi2是兩個(gè)隨機(jī)選擇的個(gè)體。結(jié)果步長(zhǎng)的零均值保證了種群不會(huì)由于遺傳漂變而受到傷害。同樣應(yīng)當(dāng)注意到分布的偏移由差異向量的尺度決定。（3）最后，區(qū)分變得極微小，導(dǎo)致了非常小的變異。2.3.1.2變異算子

在一些進(jìn)化算法中，變異步長(zhǎng)以相同的概率分布函數(shù)被抽樣，差分進(jìn)化與這些進(jìn)化算法不同在于：（1）變異首先被用于產(chǎn)生一個(gè)測(cè)試向量，之后用于在交叉算子中產(chǎn)生一個(gè)子代。（2）變異步長(zhǎng)不以之前我們知道的概率分布函數(shù)被抽樣。

在差分進(jìn)化中，變異步長(zhǎng)受當(dāng)前種群的個(gè)體間差異影響。差分進(jìn)化變異算子通過變異加權(quán)差分的目標(biāo)向量對(duì)于當(dāng)前種群的每個(gè)個(gè)體產(chǎn)生一個(gè)微小的向量。然后，這個(gè)微小的向量通過交叉算子產(chǎn)生子代。對(duì)于每個(gè)親代xi(t)以如下方式產(chǎn)生一個(gè)微小的向量ui(t)：從種群中選擇一個(gè)目標(biāo)向量xi1(t)，使得i≠i1。然后，從種群中隨機(jī)選擇兩個(gè)種群xi2(t)和xi3(t)，使得i≠i1≠i2≠i3且i2，i3~U(1,ns)。使用這些個(gè)體，測(cè)試向量以如下的方式擾動(dòng)目標(biāo)向量而形成：ui(t)=xi1(t)+β(xi2(t)+xi3(t))。

式中β∈(0,∞)為標(biāo)量因子，控制差分變量的放大。在差分進(jìn)化計(jì)算中，每個(gè)基因位的改變值取決于其他個(gè)體之間的差值，充分利用了群體中其他個(gè)體的信息，達(dá)到了擴(kuò)充種群多樣性的同時(shí)，也避免了單純?cè)趥€(gè)體內(nèi)部進(jìn)行變異操作所帶來的隨機(jī)性和盲目性。在隨機(jī)向量差分法中每個(gè)個(gè)體的變異取決于兩個(gè)隨機(jī)個(gè)體的向量差：采用最優(yōu)解加隨機(jī)向量差分法，每個(gè)個(gè)體由當(dāng)前最優(yōu)解決定，分布在當(dāng)前最優(yōu)解的鄰域范圍內(nèi)，利用了當(dāng)前最優(yōu)種群最優(yōu)個(gè)體的信息，加速了搜索速度，但同時(shí)如果種群分布密度高，可能會(huì)導(dǎo)致算法陷入局部最優(yōu)解；采用最優(yōu)解與隨機(jī)向量差分法，用個(gè)體局部信息和群體全局信息指導(dǎo)算法進(jìn)一步搜索的能力，較最優(yōu)解加隨機(jī)向量法降低了陷入局部最優(yōu)解的危險(xiǎn)。當(dāng)向量偏差大時(shí)，導(dǎo)致個(gè)體的變異強(qiáng)度高；反之，個(gè)體的變異強(qiáng)度低。差分進(jìn)化計(jì)算與種群的分布密度相關(guān)，因此如果種群分布密度高，則個(gè)體的變異強(qiáng)度較低。2.3.1.3交叉算子

差分進(jìn)化算子實(shí)現(xiàn)了測(cè)試向量ui(t)和親代向量xi(t)的離散重組以產(chǎn)生子代x’i(t)。使用如下方法實(shí)現(xiàn)交叉：式中xij(t)表示向量xi(t)的第j個(gè)元素，其J是將承受擾動(dòng)（或交叉位的集合）的元素下標(biāo)的集合?？梢允褂貌煌姆椒ㄒ耘袛嗉螶，以下兩種方法較為常用：（1）二項(xiàng)式交叉。交叉位從可能的交叉位集合{1,2,….,n}中隨機(jī)選出，n是問題維度。在基本差分進(jìn)化算法中（本PPT第74頁(yè)），pr是考慮包含交叉位的概率。pr越大，選擇交叉位也就越多。這意味著細(xì)微向量的更多元素可以被用于產(chǎn)生子代以及更少的親代向量。因?yàn)槭褂昧艘粋€(gè)概略決策來包含一個(gè)交叉位，其可能出現(xiàn)沒有點(diǎn)被選擇的情況，在這種情況下，子代就是其親代xi(t)。這個(gè)問題對(duì)于低維搜索空間更加明顯。為了確保至少有子代的一個(gè)元素不同于親代，交叉位集合ζ初始化為包含一個(gè)隨機(jī)選擇的點(diǎn)j*。

對(duì)于選擇交叉位的差分進(jìn)化二項(xiàng)式交叉j*~U(1,n)；ζ←ζU{j*}；for每個(gè)j∈{1,…,n}doifU(0,1)<pr且j≠j*then

ζ←ζU{j}；endend（2）指數(shù)交叉。從一個(gè)隨機(jī)選擇的索引，指數(shù)交叉算子選擇一個(gè)鄰接點(diǎn)的序列，將這個(gè)潛在的交叉位處理為一個(gè)環(huán)。下面的偽代碼表明至少有一個(gè)交叉位被選擇，并且形成索引，選擇下一個(gè)直到U(0,1)≥pr，或|ζ|=n。

在差分進(jìn)化計(jì)算中，進(jìn)行交叉操作的主體是父代個(gè)體和由它經(jīng)過差分變異操作后得到的新個(gè)體，雖然這種方法看似沒有進(jìn)行個(gè)體之間的信息交互，但由于新個(gè)體經(jīng)過差分變異而來，本身保存有種群中其他個(gè)體的信息，因此差分進(jìn)化的交叉算子同樣具有個(gè)體之間信息交互的機(jī)制。對(duì)于選擇交叉位的差分進(jìn)化指數(shù)交叉ζ←{}；j~U(1,n-1)；repeat

ζ←ζU{j+1}；j=j+1modn；untilU(0,1)≥pr或|ζ|=n2.3.1.4選擇算子

選擇用于決定哪個(gè)個(gè)體將在編譯算子中發(fā)揮作用以產(chǎn)生測(cè)試向量，并且決定哪個(gè)親代或者子代將存活至下一代。結(jié)合交叉算子的情況，將使用若干選擇方法。使用隨機(jī)選擇從差異向量已被計(jì)算的個(gè)體中選出個(gè)體。對(duì)于大多數(shù)差分進(jìn)化實(shí)現(xiàn)，要么隨機(jī)選擇目標(biāo)向量，要么選擇最優(yōu)個(gè)體。

為了構(gòu)建下一代的種群，使用判斷選擇：如果子代的適應(yīng)度如果優(yōu)于其親代，則子代替換其親代；否則，親代存活至下一代。這確保了種群的平均適應(yīng)度不致惡化。2.3.1.5控制參數(shù)

除了種群步長(zhǎng)ns，差分進(jìn)化的性能由兩個(gè)控制參數(shù)控制，規(guī)模因子β和重組概率pr（見本PPT第74頁(yè)基本算法）。這些參數(shù)的作用如下：（1）種群大小。種群大小對(duì)于差分進(jìn)化算法的探索性有著直接的影響。種群中個(gè)體數(shù)量越多，可用的差異向量就越多，則更多的方向可以被探索。然而，應(yīng)當(dāng)記住每代計(jì)算復(fù)雜度隨種群大小增加而增加。經(jīng)驗(yàn)告訴我們ns≈n。然而編譯算子的本性提供了個(gè)體數(shù)量的下界為ns>2nv+1，式中nv是使用的差異的個(gè)數(shù)。對(duì)于nv個(gè)差異，需要2nv個(gè)個(gè)體，對(duì)于每個(gè)差異有2個(gè)。附加的個(gè)體表示目標(biāo)向量。

（2）規(guī)模因子。規(guī)模因子β∈(0,∞)控制差異變量（xi2-xi3）的增大。β值越小，變異步長(zhǎng)越小，且算法收斂時(shí)間越長(zhǎng)。β值較大有利于增加探索性，但可能導(dǎo)致算法超過好的最優(yōu)值。β值應(yīng)當(dāng)足夠小以允許差異探索緊湊的空間，并且足夠大以維持多樣性。當(dāng)種群數(shù)量增加時(shí)，規(guī)模因子應(yīng)當(dāng)減少。種群中個(gè)體越多，差異向量的尺度越小，比較靠近的個(gè)體將變成同一個(gè)個(gè)體。因此，較小的步長(zhǎng)用于開采局部區(qū)域。經(jīng)驗(yàn)結(jié)果建議使用較大的ns和β經(jīng)常導(dǎo)致早熟，并且β=0.5通常提供了足夠好的性能。（3）重組概率。重組的概率pr對(duì)于差分進(jìn)化的多樣性有著直接的影響。這個(gè)參數(shù)控制親代xi(t)的元素個(gè)數(shù)。重組的概率越高，在新一代中就引入了越多的變種，由此增加了多樣性和探索性。增加pr通常導(dǎo)致更快的收斂，同時(shí)減少pr增加了搜索的魯棒性。

差分進(jìn)化策略的大多數(shù)實(shí)現(xiàn)將控制參數(shù)作為一個(gè)常數(shù)。盡管實(shí)驗(yàn)表明差分進(jìn)化收斂于這些參數(shù)的不同值有著密切的關(guān)系，但是性能（例如精度、魯棒性和速度）可以通過對(duì)于每個(gè)新問題尋找控制參數(shù)的最佳值而得以提高。2.3.2基本差分進(jìn)化的變種

2.3.2.1混合差分進(jìn)化策略

基本的差分進(jìn)化非常高效和魯棒，原始差分進(jìn)化策略的一些自適應(yīng)方法被發(fā)展出來以進(jìn)一步的提高性能?；具M(jìn)化策略已經(jīng)與其它的進(jìn)化算法，比如梯度下降法、粒子群算法、人工神經(jīng)網(wǎng)絡(luò)、模擬退火算法等相結(jié)合。下面主要介紹基于梯度的混合差分進(jìn)化。

最早的混合差分進(jìn)化之一由Chiou和 Wang發(fā)展出來，被稱為混合差分進(jìn)化?；旌喜罘诌M(jìn)化引入了兩種新的算子：為了提高收斂性能的加速算子（不以犧牲多樣性為代價(jià)）和提供差分進(jìn)化掙脫局部極值能力的遷移算子。

如果變異和交叉算子未能提升最佳個(gè)體的適應(yīng)度，則加速算子使用梯度下降法以調(diào)整最佳個(gè)體的朝向以獲得更佳的位置。令表示當(dāng)前種群pop(t)在應(yīng)用變異和交叉算子前的最優(yōu)個(gè)體，令為經(jīng)過應(yīng)用于變異和交叉于所有的個(gè)體的下一代種群中的最佳個(gè)體。則假設(shè)一個(gè)最小化問題，加速算子計(jì)算如下向量：式中是學(xué)習(xí)率或步長(zhǎng)；是目標(biāo)函數(shù)f的梯度。新的向量x(t)替換新的種群pop(t)中最差的個(gè)體。

講學(xué)習(xí)率初始化為1，例如。如果梯度下降未能產(chǎn)生一個(gè)具有更好適應(yīng)度的新向量x(t)，學(xué)習(xí)率以一個(gè)因子削減。梯度下降不斷重復(fù)直到足夠趨近于0，或者已經(jīng)達(dá)到梯度下降步的最大次數(shù)。

結(jié)合加速和遷移的混合差分進(jìn)化設(shè)定代計(jì)數(shù)器，t=0；初始化控制參數(shù)β和pr；產(chǎn)生并初始化具有ns個(gè)個(gè)體的種群pop(0)；while終止條件不為真do

當(dāng)需要時(shí)應(yīng)用遷移算子；for每個(gè)個(gè)體xi(t)∈pop(t)do

計(jì)算適應(yīng)度f(wàn)(xi(t))；通過應(yīng)用變異算子產(chǎn)生測(cè)試向量ui(t)；通過應(yīng)用交叉算子產(chǎn)生一個(gè)子代x’i(t)；iff(x’i(t))優(yōu)于f(xi(t))then

將x’i(t)加入pop(t+1);endelse將xi(t)加入pop(t+1);endend

當(dāng)需要時(shí)應(yīng)用加速算子；end將最佳適應(yīng)度的個(gè)體作為結(jié)果返回。

使用梯度下降可以顯著的加速搜索，但其也存在著會(huì)陷入局部極值的缺陷。遷移算子通過增加種群多樣性以解決這個(gè)問題。這是通過將最佳個(gè)體繁殖出多個(gè)新個(gè)體，并將這些個(gè)體替代當(dāng)前種群而做到的。個(gè)體按如下方式繁殖：

式中。繁殖出的個(gè)體稱為。

遷移算子僅當(dāng)當(dāng)前種群多樣性變得太小時(shí)使用，這就是說，當(dāng)：式中：式中ε1和ε2分別表示考慮最佳個(gè)體種群多樣性和基因型多樣性的忍耐性。如，那么個(gè)體i的第j個(gè)元素的值就接近于最佳個(gè)體的第j個(gè)元素的值。

2.3.2.2基于種群的差分進(jìn)化

為了提高差分進(jìn)化的探索能力，有學(xué)者提出使用兩個(gè)種群集。第二個(gè)種群被稱為備用種群popa(t)，作為那些被差分進(jìn)化選擇算子拒絕的親代的存檔。在初始化過程中，隨機(jī)選擇出ns對(duì)向量。兩個(gè)向量中間最佳的那個(gè)作為一個(gè)個(gè)體被插入到種群pop(0)中，另一個(gè)向量xia(0)被插入備份種群popa(0)之中。在每一代中，對(duì)于每個(gè)被產(chǎn)生的子代，如果子代的適應(yīng)度不優(yōu)于親代，與拋棄子代x’i(0)不同，其考慮在備份種群中包括子代。如果f(x’i(t))優(yōu)于xia(t)，那么x’i(t)替換xia(t)。備份集合周期性的被用于替換pop(t)中最差個(gè)體為popa(t)中的最佳個(gè)體。2.3.3高級(jí)話題——約束控制方法使用如下的方法以應(yīng)用差分進(jìn)化以解決第2.2.2節(jié)中所定義的約束優(yōu)化問題。（1）罰方法。通過增加一個(gè)函數(shù)以懲罰與約束沖突的解來調(diào)整目標(biāo)函數(shù)。（2）通過在一個(gè)擴(kuò)展拉格朗日中嵌入約束將約束問題轉(zhuǎn)化為一個(gè)非約束問題。（3）為了保持初始解的可行性，采用一些方法決定步長(zhǎng)和搜索方向。（4）通過改變差分進(jìn)化的選擇算子，可以拒絕非可行解，并且促進(jìn)非可行解的修理。為了達(dá)到此目的，選擇算子接受一個(gè)滿足如下條件的子代x’i：a)如果x’i滿足所有的約束且f(x’i)≤f(xi)，那么x’i替換其親代xi（假設(shè)是一個(gè)最小化問題）。b)如果x’i是可行的且xi是不可行的，那么x’i替換xi。c)如果x’i和xi都是不可行的，那么如果x’i違反的約束的數(shù)量小于等于xi違反的約束的數(shù)量，那么x’i替換xi。

在親代和子代都表示可行解的情況下，沒有朝向更好適應(yīng)度場(chǎng)景的選擇壓力；在一定程度上，朝向最小違反約束數(shù)量的解。2.3.4高級(jí)話題——多目標(biāo)優(yōu)化多目標(biāo)優(yōu)化需要同時(shí)優(yōu)化多個(gè)沖突的目標(biāo)。多目標(biāo)差分進(jìn)化方法包括：

（1）將問題轉(zhuǎn)化為一個(gè)最大最小問題。（2）權(quán)聚合方法。（3）基于種群的方法。如果K個(gè)目標(biāo)需要優(yōu)化，則使用K個(gè)子種群，這里每個(gè)種群優(yōu)化一個(gè)目標(biāo)。這些子種群組織成一個(gè)環(huán)拓?fù)?。在每次迭代中，在差分進(jìn)化繁殖算子的應(yīng)用之前，種群popk中的最佳個(gè)體popk?遷移至種群popk+1，其被用于種群popk+1以產(chǎn)生對(duì)這個(gè)種群的測(cè)試向量。

（4）基于Pareto的方法，其改變差分進(jìn)化算子以包括支配概念。

變異：有學(xué)者提出僅在當(dāng)前種群中非支配解上應(yīng)用變異，計(jì)算差異為隨機(jī)選擇的個(gè)體xi1和隨機(jī)選擇的支配xi1的向量xi2之間的差異；這就是說，xi1

xi2，如果xi1不由當(dāng)前種群的任何其它個(gè)體支配，差異設(shè)定為0。

選擇：一個(gè)對(duì)于選擇算子的簡(jiǎn)單變化是當(dāng)且僅當(dāng)xi’

xi以子代xi’替換親代xi。一個(gè)替換的方法是，可以使用非支配排序基因算法的辦法，這里非支配排序和定級(jí)被用于親代和子代。之后下一代種群優(yōu)先選擇具有較高排序的那些個(gè)體。2.4協(xié)同進(jìn)化

協(xié)同進(jìn)化（CoE）是密切相關(guān)的物種的互補(bǔ)進(jìn)化。兩個(gè)物種的協(xié)同進(jìn)