動態(tài)優(yōu)化算法研究綜述

動態(tài)優(yōu)化算法研究綜述

0動態(tài)優(yōu)化問題的描述許多復(fù)雜現(xiàn)實(shí)世界的優(yōu)化問題是動態(tài)的。例如，當(dāng)新任務(wù)完成時，必須立即添加到當(dāng)前的議程中。機(jī)器可能會崩潰并降低加工速度。原材料的質(zhì)量正在變化。所謂的動態(tài)優(yōu)化問題（dops）是指適應(yīng)值函數(shù)、問題示例或限制條件變化的優(yōu)化問題。動態(tài)優(yōu)化問題可以包括如下。DOP={max(ormin)f(x,t)s.t.x∈X(t)?S,t∈TDΟΡ={max(ormin)f(x,t)s.t.x∈X(t)?S,t∈ΤS∈Rn,S是搜索空間;t:時間;f:S×T→R是目標(biāo)函數(shù);x是可行解;X(t)是在t時間可行解集合.動態(tài)優(yōu)化問題的目標(biāo)就是尋找一系列隨時間變化的最優(yōu)個體的集合X*={x*t},t∈T,滿足f(x*t,t)≤f(x,t),?x∈X(t)(對于最小化問題).盡管EA(evolutionaryalgorithm)解決靜態(tài)優(yōu)化問題取得了很好的效果,但傳統(tǒng)EA并不能很好地解決動態(tài)優(yōu)化問題,因?yàn)镋A運(yùn)行一段時間后會收斂到一個固定的解或者搜索空間的一個有限區(qū)域.正常而不是過早的收斂對于傳統(tǒng)EA處理靜態(tài)優(yōu)化問題是必需的,但是,對于動態(tài)優(yōu)化問題而言,一旦收斂,當(dāng)新的環(huán)境到來時,EA就失去了探索新的區(qū)域所必需的多樣性,從而不能跟蹤到在新的環(huán)境下已經(jīng)變化了的問題的最優(yōu)解.在動態(tài)優(yōu)化問題中,對不斷變化的最優(yōu)解的快速跟蹤甚至比找到最優(yōu)解本身更有意義.如果環(huán)境完全隨機(jī)改變,就沒有任何可以利用的信息,從零開始進(jìn)行進(jìn)化,將每一次變化的發(fā)生都作為一個新優(yōu)化問題的開始無疑是最好的選擇.但是這種簡單的方法通常是不切實(shí)際的,其主要原因是:沒有利用過去任何信息,每次小變化后都重新對問題進(jìn)行求解;變化后的新問題同老問題一般是有關(guān)聯(lián)的,新問題的解和老問題的解離得并不是很遠(yuǎn);現(xiàn)實(shí)世界里,有些變化是循環(huán)變化的,因此重新使用過去獲得的信息來指導(dǎo)現(xiàn)在的進(jìn)化是有益的.近年來,動態(tài)優(yōu)化算法的研究引起了越來越多研究者的興趣,動態(tài)優(yōu)化算法主要可以分為環(huán)境變化后增加多樣性的方法、運(yùn)行過程中始終保持多樣性的方法、基于記憶機(jī)制的方法、多種群方法和基于預(yù)測機(jī)制方法5類.1可變局部搜索環(huán)境變化后增加多樣性的方法是指一旦檢測到了環(huán)境的變化,就使用外部方法來增加種群的多樣性,從而使EA重新適應(yīng)變化了的環(huán)境.這類方法典型的代表有超級變異方法(hypermutation),這是由Cobb提出的,當(dāng)探測到環(huán)境的變化后立刻猛烈增大變異率,使得趨于收斂的種群發(fā)散.但是這種算法并不是對所有的環(huán)境都是有效的,因?yàn)?首先環(huán)境的變化并不能實(shí)時被察覺到,其次環(huán)境很小的變化可能很容易被跟蹤到,不需要使用破壞性較高的高變異率來實(shí)現(xiàn);另外,由于變異率在整個過程中是不可控的,會導(dǎo)致EA性能的降低.因此,Vavak等提出可變局部搜索(variablelocalsearch,VLS)方法,采用一種稱為可變局部搜索的變異算子,當(dāng)檢測到環(huán)境變化后,變異率不是突然增大,而是逐步增大.對于分布估計算法(estimationofdistributionalgorithm,EDA),Yang提出了PBIL(population-basedincrementallearningalgorithm)算法的超級學(xué)習(xí)模式,用當(dāng)環(huán)境發(fā)生變化時暫時的提高學(xué)習(xí)率來增加多樣性.對于粒子群優(yōu)化算法(PSO),文獻(xiàn)使用了環(huán)境發(fā)生變化后能夠增加種群多樣性的方法.以上的這些方法有以下缺點(diǎn):第一,環(huán)境變化的檢測通常是不容易察覺的.在動態(tài)優(yōu)化問題中,經(jīng)常需要檢測環(huán)境變化,如果能夠假設(shè)環(huán)境的變化或多或少會引起當(dāng)前解質(zhì)量的下降,那么將監(jiān)測整個種群性能或者累積平均最優(yōu)解的退化作為環(huán)境變化的探測器.Branke采用了另一種略有不同的探測環(huán)境變化的方法,在算法運(yùn)行的每一代,若干個個體都要被重新估值.如果其中至少有一個個體的適應(yīng)值發(fā)生了變化,那么就可以認(rèn)為環(huán)境也發(fā)生了變化.但如果在沒有種群個體的地方出現(xiàn)變化,將無法檢測到環(huán)境的變化.第二,不同程度地帶有檢測滯后性的問題,這樣就使得一旦檢測到了環(huán)境的變化,就使用外部方法來增加種群的多樣性的方法并不能及時地對變化了的環(huán)境做出反應(yīng),從而不能有效地跟蹤變化了的最優(yōu)解.第三,用這類方法增加種群的多樣性帶有一定程度的盲目性.多樣性的增加是以破壞前面的好解為代價的.因此,很難找到一種適當(dāng)?shù)亩鄻有?而太多的多樣性會導(dǎo)致種群類似于重新開始的策略,太少的多樣性又不能有效地解決收斂問題.2保持多樣性的方法2.1自組織隨機(jī)移民為了避免種群收斂,必須保持多樣性,使得算法能夠隨時適應(yīng)變化了的環(huán)境,并盡快地跟蹤到變化的最優(yōu)解.Grefenstette提出一種隨機(jī)移民的方法(randomimmigrantsGA,RIGA),即在每一代,種群中的部分個體都會被隨機(jī)產(chǎn)生的個體所替代.這保證了每一代都有新的基因物質(zhì)被引入到種群中,有效地避免了整個種群向一個小的搜索空間的區(qū)域收斂.RIGA不像超級變異的方法作用于整個種群,而是作用于一部分種群,不至于破壞整個進(jìn)行的進(jìn)程.RIGA已經(jīng)成為一種動態(tài)優(yōu)化算法的標(biāo)準(zhǔn)算法,經(jīng)常用于和其他動態(tài)優(yōu)化算法的比較.但RIGA也有一些缺點(diǎn),新插入的隨機(jī)個體可能會因?yàn)樽陨淼倪m應(yīng)度值比較低而在選擇階段就被淘汰了,導(dǎo)致不能使更多的基因物質(zhì)引入.Tinós和Yang在RIGA的基礎(chǔ)上提出了一種自組織隨機(jī)移民算法(self-organizingrandomimmigrantsGA,SORIGA),在每一代中,SORIGA用一定數(shù)量的隨機(jī)產(chǎn)生的若干個體,替換種群中最差的個體以及與其相鄰(序號相鄰)的個體.試驗(yàn)證明SORIGA呈現(xiàn)了自組織行為.當(dāng)多樣性較低時,一個個體被替換能引起許多其他個體的連鎖反應(yīng),從而以一種自適應(yīng)的方式增加種群的多樣性,使EA不至于因?yàn)榉N群收斂到一個區(qū)域而難以適應(yīng)環(huán)境的變化.Fernandes等使用了沙堆(Sandpile)變異算子,沙堆是一個運(yùn)行在混沌和有序之間的自組織臨界狀態(tài)的復(fù)雜系統(tǒng).沙堆變異算子不需要外在的機(jī)制對最優(yōu)值的移動做出反應(yīng),它本身就增加了新的基因物質(zhì).變異率是以自我調(diào)節(jié)的方式增加的,而不需要了解環(huán)境本身的信息.自組織自適應(yīng)方法對多樣性的變化根據(jù)需要進(jìn)行自動控制,勢必會增強(qiáng)算法的性能,但是這類方法的設(shè)計相對困難.有導(dǎo)向的移民策略在處理一些動態(tài)優(yōu)化問題時,表現(xiàn)得更加有效.比起RIGA,這些策略減少了基因物質(zhì)引入的盲目性和對當(dāng)前搜索進(jìn)程的破壞性.這方面主要代表有:Yang提出混合移民模式(AHybridImmigrantsScheme)、基于記憶的移民模式(Memory-BasedImmigrants)以及基于精英的移民模式(Elitism-basedImmigrants).具有導(dǎo)向的移民策略對于解決某一類問題,比如劇烈變化的,變化后的最優(yōu)值在原來最優(yōu)值附近的,周期變化的問題等是有效的,但由于算法對動態(tài)環(huán)境是未知的,因此在缺乏動態(tài)問題先驗(yàn)知識的情況下,限制了算法在多種動態(tài)環(huán)境中的使用.2.2增加多樣性方法Andersen提出了一種共享機(jī)制的動態(tài)優(yōu)化算法,Cedeno等引入了共享和排擠機(jī)制能有效地控制相似個體的個數(shù),使個體盡量地分散到搜索空間中,但排擠距離難以確定.Mori等提出的熱動力GA(ThermodynamicalGeneticAlgorithm,TDGA)的核心思想是通過“自由能量”的變量F來直接控制種群的多樣性.還有一些算法從改變個體配對模式出發(fā),提出了有助于保持種群多樣性的方法.這些方法改變了原有算法隨機(jī)配對的模式,采用了非隨機(jī)配對的模式來增加多樣性.Fernandes等提出了適應(yīng)性非同型配對GA(theAdaptiveDissortativeMatingGA,ADMGA),通過檢測兩個父體之間的海明距離是否滿足一個能夠自我調(diào)節(jié)的門檻值來決定是否配對產(chǎn)生下一代.試驗(yàn)證明在解決動態(tài)欺騙函數(shù)的問題上有很好的效果.非隨機(jī)配對模式雖然在很大程度上保持了多樣性,但是也存在計算量的增加影響算法性能的問題.Wang和Wineberg認(rèn)為多樣性增加(diversityenhancement)不是處理動態(tài)優(yōu)化問題的根本原則,隨之提出了進(jìn)化性(evolvability)的概念,即進(jìn)化性是個體適應(yīng)環(huán)境變化的能力,并給出了進(jìn)化性的度量方法,將進(jìn)化性和適應(yīng)值一起用于選擇操作并基于此提出了進(jìn)化性估計GA(Estimationofevolvabilitygeneticalgorithm,EEGA),通過試驗(yàn)證明了在動態(tài)環(huán)境中,EEGA比GA有較低的多樣性卻比GA有更好的性能.2.3多步算法保持種群多樣性對于PSO,解決動態(tài)優(yōu)化問題,多樣性保持的方法也經(jīng)常使用.Esquivel提出的一種混合PSO(hybridPSO,HPSO)方法中,采用了大變異操作,用以保證系統(tǒng)的多樣性.Blackwell和Bentley提出了一種“帶電粒子”PSO(chargedPSO,CPSO),它通過模擬帶電粒子之間的排斥作用,防止種群收斂從而達(dá)到保持系統(tǒng)多樣性的目的.文獻(xiàn)將模擬退火算法中的基于概率的選擇機(jī)制引入到PSO中,作為PSO算法的選擇函數(shù),以一定概率接收劣解,有助于多樣性的保持.Hashemi等把細(xì)胞自動機(jī)嵌入到搜索空間中,利用各個細(xì)胞中包含粒子的多少來控制種群的多樣性.Janson和Middendorf提出了分層鄰域結(jié)構(gòu)以保持多樣性.Sim?es等受到免疫系統(tǒng)的啟發(fā),使用transformation算子,該算子操作是從基因庫中隨機(jī)選擇一個基因段,移植到一個隨機(jī)抗體中.對于EDA算法,Fernandes等使用了一種新的UMDA(univariatemarginaldistributionalgorithm)概率模型更新策略,旨在修正UMDA在采樣生成種群過程中的多樣性的丟失,從而延遲或避免了種群的完全收斂,提高了UMDA適應(yīng)動態(tài)環(huán)境的能力.Wang等改進(jìn)了原對偶遺傳算法的原對偶映射模式,提出了一種基于統(tǒng)計機(jī)制的適應(yīng)性原對偶映射模式,通過種群中所有個體各個基因位的統(tǒng)計信息決定各個基因位的映射概率,由映射概率決定該基因位是否參與映射.該映射模式保持了種群的多樣性,文獻(xiàn),進(jìn)一步提出了適應(yīng)性基于概率的原對偶映射算子,該算子引入了Lamarckian學(xué)習(xí)機(jī)制,適應(yīng)度值高的映射算子有更高的選擇機(jī)會.Park等提出了一種對偶種群遺傳算法(dualpopulationgeneticalgorithm,DPGA)用于解決靜態(tài)優(yōu)化問題,在文獻(xiàn)中,他們對DPGA做了改進(jìn),提出了DPGA2算法,該算法使用兩個儲備種群,與主種群有不同的距離,通過生存選擇控制來自兩個儲備種群的基因物質(zhì)的流入,使得主種群保持足夠的多樣性來適應(yīng)環(huán)境的變化.本節(jié)所提及的方法都從不同的角度上使得算法在運(yùn)行過程中,始終保持多樣性,這樣一旦環(huán)境發(fā)生變化,算法能及時跟蹤到變化的最優(yōu)值.這類方法一般不需要檢測環(huán)境的變化,因此避免了環(huán)境變化后增加多樣性的方法中不能及時檢測到環(huán)境變化的缺點(diǎn),但是由于持續(xù)地關(guān)注多樣性可能會減慢或阻礙優(yōu)化進(jìn)程.3保持穩(wěn)定性作用于優(yōu)化算法設(shè)計中.主要有20個自在EA中增加記憶的機(jī)制,能夠很好地保存過去的信息,一旦環(huán)境發(fā)生變化,這些信息能夠被重新使用,從而提高算法的性能.尤其是對于周期變化的環(huán)境很有效,當(dāng)環(huán)境重新回到原來的環(huán)境時,存儲的原來環(huán)境的最優(yōu)解信息使EA很快回到最優(yōu)值附近.另外記憶體中的解也可以起到保持多樣性的作用.記憶機(jī)制大多和多樣性保持機(jī)制一起使用,通常有兩種記憶模式:隱式記憶模式和顯式記憶模式.3.1多倍體法制備適合不同環(huán)境的算法隱式記憶模式利用了染色體的冗余表達(dá),大多使用二倍體形式,Goldberg等提出了基于二倍體和基因顯性機(jī)制的遺傳算法,在動態(tài)背包問題的應(yīng)用中,該方法比簡單GA表現(xiàn)出更好的性能.Hadad等提出了多倍體的方法,多倍體的方法更適用于變化頻率較高的環(huán)境.隱式記憶模式使得算法隱式的存儲一些在運(yùn)行過程中有用的信息,但是不清楚算法是否真的以一種有效的方式使用這些信息,隱式記憶模式可能更多的是利用冗余的表達(dá)降低收斂速度,使得種群的多樣性增加,從而能較好的處理變化的環(huán)境.染色體的冗余表達(dá)的方法對于處理數(shù)目較小的幾個環(huán)境狀態(tài)之間振蕩變換的情況下是有效的,但是對于大量環(huán)境狀態(tài)出現(xiàn)的情況效果不是很好,因?yàn)樵谶@種情況下需要的冗余代碼會變長,算法性能降低,此外,由于對問題先驗(yàn)知識的缺乏(即到底有多少環(huán)境狀態(tài)),染色體冗余代碼的設(shè)計會變得困難.3.2基因概率向量的實(shí)驗(yàn)與研究顯式記憶模式是引入額外的存儲空間(記憶體)存儲特定的信息并在后面的運(yùn)行中重新引入到種群使用.Branke提出了顯式記憶的一種直接記憶模式,經(jīng)過幾代后,最優(yōu)解存儲在記憶體中,當(dāng)檢測到環(huán)境發(fā)生變化時,再從記憶體中取回這些解到當(dāng)前種群中,經(jīng)過某種替換策略替換掉同等數(shù)量的個體.當(dāng)最優(yōu)個體重新回到原來的位置的時候,使用這種模式是有效的.但是當(dāng)環(huán)境變化時,取出的記憶體中的信息可能是冗余的,從而影響算法的性能.Yang等在直接記憶模式上做了擴(kuò)展,提出了一種聯(lián)想記憶模式(associativememoryscheme).每隔幾代,存儲在記憶體中的不僅僅是當(dāng)前種群最優(yōu)解本身,還有與最優(yōu)解所在的相關(guān)的環(huán)境信息,借鑒了EDA的思想.與最優(yōu)解相關(guān)的環(huán)境信息用當(dāng)時種群中所有個體基因座上基因所決定的等位基因概率向量來描述.這樣,當(dāng)環(huán)境發(fā)生變化時,將當(dāng)前環(huán)境下的記憶體中的最好解對應(yīng)的等位基因概率向量取出,利用該向量以類似于EDA中生成種群的方式生成一定數(shù)量的個體,用這些個體隨機(jī)替換掉同等數(shù)量的當(dāng)前種群中的個體.通過一系列動態(tài)問題的試驗(yàn)證明通常情況下在動態(tài)環(huán)境中,聯(lián)想記憶模式優(yōu)于傳統(tǒng)的直接記憶模式.與直接記憶好解本身的方法不同,Richter和Yang最近提出了一種基于抽象的記憶模式(abstractionmemoryscheme),算法運(yùn)行過程中,存儲的不是好解本身,而是在搜索空間中好解的大概位置,構(gòu)建了好解空間分布的概率模型,當(dāng)環(huán)境發(fā)生變化時,根據(jù)這個概率模型產(chǎn)生出一定數(shù)量的隨機(jī)個體插入到當(dāng)前種群中,文中還探討了動態(tài)優(yōu)化中記憶和學(xué)習(xí)之間的關(guān)系.直接記憶模式中,并不清楚記憶體中存放的曾經(jīng)出現(xiàn)的最優(yōu)個體是與哪一種具體的動態(tài)環(huán)境相對應(yīng),一旦環(huán)境發(fā)生變化,就把記憶體中所有的個體引入到種群中的方法,帶有一定的盲目性.Ramsey和Grefenstette較早提出的基于案例推理(case-basedreasoning)的記憶來處理動態(tài)優(yōu)化問題的方法就減少了這種盲目性.作者提出一種能表征不同變化環(huán)境特征的方法,用基于案例推理的方法來映射這些變化的環(huán)境和找到的最優(yōu)個體之間的關(guān)系.當(dāng)環(huán)境變化后,這些映射信息再用來確定變化后的環(huán)境并把和這個環(huán)境相關(guān)的最優(yōu)個體引入到當(dāng)前種群中.和以上方法的思想相類似的,Karaman提出了記憶索引EA(thememoryindexingevolutionaryalgorithm,MIEA)來解決0-1動態(tài)背包問題.利用問題的特定信息來定義不同的環(huán)境,為每個環(huán)境進(jìn)行編號.記住新的環(huán)境出現(xiàn)之前的前一個環(huán)境的信息,這個信息是由當(dāng)時種群的等位基因概率向量來描述,每當(dāng)環(huán)境發(fā)生變化時,若檢測到新環(huán)境與過去某個編號的環(huán)境一致,則使用和該編號環(huán)境對應(yīng)的等位基因概率向量來初始化種群,產(chǎn)生的個體替換掉老種群中部分個體再進(jìn)行演化.當(dāng)新出現(xiàn)的環(huán)境與過去所有的環(huán)境都不一致時,再使用超級變異的方法.基于案例推理的記憶方法和使用記憶索引的類似的記憶方法的關(guān)鍵是如何表征環(huán)境信息.當(dāng)環(huán)境變化是可以度量的情況下,這些方法才是可用的.Bendtsen和Krink提出了一種動態(tài)記憶模型(dynamicmemorymodel,DMM),和傳統(tǒng)的基于記憶機(jī)制的方法不同,這種模型的記憶體自身能夠跟蹤動態(tài)環(huán)境的變化,并能夠進(jìn)行自我調(diào)整.通過對移動峰問題和溫室效應(yīng)問題的試驗(yàn),證明了DMM優(yōu)于傳統(tǒng)的靜態(tài)記憶模式.但是當(dāng)問題域很大的時候,使用記憶體中存儲隨機(jī)候選解的方式就不適合了,因?yàn)榭赡苤挥杏洃涹w中的少數(shù)候選解有更新調(diào)整的機(jī)會.對于EDA,Yang在文獻(xiàn)中分別把記憶機(jī)制引入了UMDA和PBIL中,Yang和Yao把聯(lián)想記憶模式引入了PBIL中.Wang等在PSO中使用了記憶的機(jī)制.4標(biāo)準(zhǔn)動態(tài)測試方法多種群方法主要應(yīng)用在一類多峰函數(shù)動態(tài)優(yōu)化問題上,動態(tài)性體現(xiàn)在峰的位置.高度和寬度會隨著時間發(fā)生變化.標(biāo)準(zhǔn)動態(tài)測試問題有移動峰問題(movingpeaksproblem,MPB).4.1最優(yōu)值的搜索多種群方法中,一般把種群分為搜索種群和跟蹤種群,搜索種群用于尋找最優(yōu)值,跟蹤種群用于跟蹤可能的變化.Branke等提出的自組織偵察群SOS(self-organizingscouts)方法中,主種群用來搜索最優(yōu)值,一旦主種群發(fā)現(xiàn)了一個新的峰,就會產(chǎn)生一個新的子種群跟蹤這個峰值的變化.Ursem提出了多種族GA(multi-nationalGA),每個子種群兼有搜索和跟蹤的功能,當(dāng)一個子種群發(fā)現(xiàn)一個新的最優(yōu)值,就會分成兩個子種群用來保證每個子種群在同一時間僅僅跟蹤一個最優(yōu)值.Oppacher等提出一種漂移平衡算法(shiftingbalanceGA,SBGA),一個大種群稱為核心種群,同時有多個小種群稱為小殖民地種群.核心種群用于跟蹤最優(yōu)值的變化,小殖民地種群用于探索不同的區(qū)域,小殖民地種群保證在核心種群之外,核心種群接收來自小殖民地種群搜索到的最優(yōu)個體.4.2多種群方法的使用近年來多種群方法更多地出現(xiàn)在了PSO解決動態(tài)優(yōu)化問題上,Parrott和Li在文獻(xiàn)中使用了物種(species)的概念,定義為使用歐式距離或是海明距離度量的相似粒子所形成的群組.物種種子(speciesseeds)是物種的中心.通過算法確定種群中的哪些個體是物種中心,并以一定距離rs為半徑形成對應(yīng)的物種,由算法得到的物種中心,不僅是物種距離的中心,而且還是該物種中的最優(yōu)粒子.這樣使用PSO的lbest模型更新每個粒子的速度和位置.算法能自適應(yīng)調(diào)整多個物種在搜索空間的分布,跟蹤變化了的多個全局或局部最優(yōu)解.Blackwell和Branke把種群分成一系列相互作用的子種群,使用了排斥(exclusion)算子實(shí)現(xiàn)局部交互,當(dāng)兩個子群離得太近時,具有較低適應(yīng)值的種群重新初始化,還使用反收斂(anti-convergence)算子實(shí)現(xiàn)全局交互,當(dāng)所有的子群都收斂時,初始化其中最差的種群,以期持續(xù)尋找更好的新的峰.Li和Yang也是使用多種群PSO用來跟蹤多峰問題,一個父群用具有較好的全局搜索能力的快速EP(evolutionaryprogramming)保持多樣性,在整個搜索空間中探測有希望的區(qū)域,另外,多個子群用快速PSO算法搜索局部最優(yōu)解.Yang使用了分層聚類的方法(hiterarchicalclustering)把種群分成多個子種群,該方法的好處是子種群初始粒子依據(jù)在適應(yīng)值曲面(fitnesslandscape)的分布自動產(chǎn)生,而不是依賴于像k-means聚類方法中的參數(shù)k.Mender等在差分演化(differentialevolution)上使用了多種群方法.武燕等把多種群的思想引入了UMDA.多種群方法中各個子種群能有效地分開和避免多個種群尋找相同峰的情況出現(xiàn)是兩個關(guān)鍵的問題.多個子種群獨(dú)立地處理搜索空間不同的區(qū)域,因此能夠在新的最優(yōu)值出現(xiàn)時及時跟蹤,并且由于多種群的存在還保留了大量過去搜索到的最優(yōu)值,即保留了搜索空間中若干個有希望的區(qū)域的信息,使得算法能有效處理重新出現(xiàn)的動態(tài)環(huán)境.因此多種群方法也被認(rèn)為是一種多樣性保持和自適應(yīng)的記憶策略.多種群方法是解決動態(tài)優(yōu)化問題的一種非常有效的方法,尤其適合適應(yīng)值函數(shù)多峰或者有競爭峰(competingpeaks)的情況,但是太多的種群會減低搜索的效率,為了有效分離各個子種群而進(jìn)行的大量計算也會影響算法的效率,另外,分離各個子種群經(jīng)常用到的擁擠半徑的參數(shù)的選取比較困難.5消除不確定性的預(yù)測近年來,基于預(yù)測機(jī)制的動態(tài)演化算法引起了越來越多的關(guān)注,預(yù)測未來時刻環(huán)境狀態(tài),根據(jù)預(yù)測做出外部決策,使得EA提前為變化的環(huán)境做準(zhǔn)備,從而提高EA在動態(tài)環(huán)境下的適應(yīng)性,不至于在環(huán)境突然變化時候,EA性能突然減低.目前,用于動態(tài)優(yōu)化問題的基于預(yù)測機(jī)制的算法如下.Branke等在動態(tài)工作調(diào)度問題上,通過外在地搜索更能靈活地適應(yīng)新工作到達(dá)后的環(huán)境變化的解而達(dá)到預(yù)測的目的.靈活性可以通過避免較早的機(jī)器空閑時間來獲得,因此EA中加入了懲罰較早空余時間的措施.這種方法是面向特定問題的,不能推廣到一般的問題中.為了研究在更一般意義上預(yù)測用于動態(tài)優(yōu)化問題,Bosman從理論上討論了對于時間相關(guān)的問題,在某一時間做出的決定可能會影響到未來能獲得的最優(yōu)值.他得出了一種結(jié)合機(jī)器學(xué)習(xí)、統(tǒng)計學(xué)習(xí)和進(jìn)化計算的算法框架.通過機(jī)器學(xué)習(xí)和統(tǒng)計學(xué)習(xí)技術(shù)進(jìn)行未來情況的預(yù)測.隨后還在隨機(jī)動態(tài)問題上做了討論.受到Bosman的啟發(fā),Sim?es等使用具體的統(tǒng)計學(xué)習(xí)方法進(jìn)行預(yù)測,線性回歸用于預(yù)測下次環(huán)境發(fā)生變化的時刻,馬爾可夫鏈用于預(yù)測下次環(huán)境變化可能的狀態(tài).兩個預(yù)測模型都使用了過去的信息來構(gòu)建相應(yīng)的預(yù)測模型.算法引入了記憶機(jī)制來存儲過去的信息.在預(yù)測的環(huán)境變化時刻之前,種群就引入更能適合未來環(huán)境狀態(tài)的信息,從而適應(yīng)變化的環(huán)境,提高算法的性能.該算法主要的局限性在于使用線性回歸來預(yù)測何時發(fā)生環(huán)境變化,僅適用于某種模式的變化,對于更加復(fù)雜的變化模式,線性回歸預(yù)測就會有較大的誤差,而導(dǎo)致算法性能的降低.隨后,Sim?es等在文獻(xiàn)中進(jìn)一步討論了非線性回歸預(yù)測模型的情況.如果最優(yōu)個體在搜索空間中的移動是遵循一定的運(yùn)動模型的,那么使用預(yù)測技術(shù)預(yù)測下一刻最優(yōu)個體的位置,把搜索過程導(dǎo)向新的最優(yōu)個體最有可能存在的區(qū)域,有助于及時跟蹤變化了的最優(yōu)個體.Rossi定義了最優(yōu)值的狀態(tài)包括最優(yōu)值的位置和速度,使用卡爾曼濾波技術(shù)估計系統(tǒng)未來的狀態(tài)并計算估計誤差,兩者分別稱為預(yù)測和準(zhǔn)確度.EA可以通過測量獲得過去最優(yōu)值狀態(tài),并結(jié)合相應(yīng)的運(yùn)動模型,使用卡爾曼濾波技術(shù)得到未來最優(yōu)值的估計值,文中提出了EA可以通過3種技術(shù)使用這個估計值作為外在的信息加入到EA中,從而提高EA跟蹤移動最優(yōu)值的能力.第一種是修改遺傳算子,第二種是使用修正的適應(yīng)度值函數(shù),第三種是使用優(yōu)異個體方式.3種不同的技術(shù)其實(shí)都是使得搜索向未來最有可能出現(xiàn)最優(yōu)值的區(qū)域移動,從而提高了在動態(tài)環(huán)境下算法的適應(yīng)能力.但該算法僅適用最優(yōu)個體在搜索空間運(yùn)動模型是線性具有高斯噪聲的情況.Stroud從個體的適應(yīng)值在動態(tài)環(huán)境下存在不確定性的角度提出了一種新的算法,擴(kuò)展卡爾曼GA(Kalman-extendedgeneticalgorithm,KGA),動態(tài)環(huán)境中個體的適應(yīng)值有兩種不確定性,一種是環(huán)境的變化造成的不確定性,一種是評價個體適應(yīng)度值時造成的不確定性.第一種不確定性可以類似于卡爾曼濾波中的過程噪聲,第二種類似于觀測噪聲.這兩種不確定性可以通過重新評價已存在的個體(觀測)而減低.針對兩種不同的情況,KGA包含了兩種不同的卡爾曼協(xié)方差和適應(yīng)值估計的更新方式.通過卡爾曼技術(shù)對動態(tài)環(huán)境下個體適應(yīng)度的兩種不確定性的預(yù)測來達(dá)到使算法適應(yīng)不斷變化了的環(huán)境的目的.vanHemert等提出了使用元學(xué)習(xí)來預(yù)測環(huán)境的下個狀態(tài).使用兩個種群,當(dāng)前種群和未來種群,用兩個具有同樣參數(shù)的GA演化,未來種群中的個體評價使用由元學(xué)習(xí)預(yù)測的適應(yīng)度值函數(shù).每經(jīng)過固定的代數(shù),未來種群中一定數(shù)目的個體拷貝到當(dāng)前種群中,去掉超過種群大小的多余的最差的個體.通過這種方法,當(dāng)前種群為未來環(huán)境變化做好了準(zhǔn)備.通過挖掘過去每一代最優(yōu)值信息,回歸一個函數(shù)來預(yù)測未來的狀況.如果預(yù)測準(zhǔn)確,使用預(yù)測方法會大大增加算法的性能.然而,使用統(tǒng)計學(xué)習(xí)的方法進(jìn)行預(yù)測需要大量的訓(xùn)練數(shù)據(jù).一方面,大量訓(xùn)練數(shù)據(jù)的獲得需要通過長時間運(yùn)行得到,降低了算法的效率;另一方面,可能會得到錯誤的訓(xùn)練數(shù)據(jù),從而引導(dǎo)種群在一個沒有希望的區(qū)域演化導(dǎo)致更為惡劣的結(jié)果.另外,學(xué)習(xí)模型的選擇也是關(guān)系預(yù)測準(zhǔn)確與否的重要因素,而遺憾的是,EA由于本身的算法特點(diǎn),對外界環(huán)境信息是未知的.對于選擇何種學(xué)習(xí)模型對算法而言存在一定的盲目性,從而使得算法不能適應(yīng)多種多樣的環(huán)境變化.如果能獲得更多的關(guān)于問題本身的先驗(yàn)信息,對于不同的問題選擇不同的學(xué)習(xí)模型將會使基于預(yù)測的方法更加有效.6其他優(yōu)化算法傳統(tǒng)的演化算法一般都是針對靜態(tài)問題的,然而現(xiàn)實(shí)世界很多問題都是動態(tài)的.靜態(tài)環(huán)境下的演化算法由于自身在運(yùn)行過程中不斷收斂到最優(yōu)值附近,多樣性喪失,一旦環(huán)境發(fā)生變化就很難跟蹤到變化的最優(yōu)解.因此,多樣性的增加