動(dòng)態(tài)環(huán)境中的進(jìn)化計(jì)算方法及其應(yīng)用研究.pdf

1、現(xiàn)實(shí)世界中的優(yōu)化問(wèn)題大多是時(shí)變的，問(wèn)題的最優(yōu)解會(huì)隨著目標(biāo)函數(shù)，環(huán)境參數(shù)或者約束條件的變化隨時(shí)發(fā)生變化。顯然在求解這類動(dòng)態(tài)優(yōu)化問(wèn)題時(shí)，—種最直接的方法就是將每次環(huán)境的變化都看作是一個(gè)新優(yōu)化問(wèn)題的開(kāi)始，從頭進(jìn)行求解。然而這種簡(jiǎn)單的方法通常是不切實(shí)際的，一方面是因?yàn)椴恢赜眠^(guò)去的信息從頭求解問(wèn)題太浪費(fèi)時(shí)間，另—方面環(huán)境的變化有時(shí)很難被探測(cè)到，或者至少在_段時(shí)間內(nèi)是不能夠被發(fā)現(xiàn)的。此外，新問(wèn)題的最優(yōu)解與舊問(wèn)題的最優(yōu)解可能相差不多，如果每次微小的變

2、化都需要對(duì)問(wèn)題重新進(jìn)行求解是非常不經(jīng)濟(jì)的。 進(jìn)化計(jì)算方法是—類模擬生物進(jìn)化過(guò)程中自然選擇機(jī)制和遺傳信息傳遞規(guī)律的優(yōu)化方法，由于自然進(jìn)化過(guò)程實(shí)際上是一種隨機(jī)的自適應(yīng)、自學(xué)習(xí)的動(dòng)態(tài)過(guò)程，所以進(jìn)化計(jì)算自然就成為解決各種動(dòng)態(tài)優(yōu)化和不確定優(yōu)化問(wèn)題的一種選擇。然而一般進(jìn)化計(jì)算方法在迭代過(guò)程中種群最終會(huì)收斂于一個(gè)滿意解，從而失去了探索問(wèn)題空間所必需的種群多樣性。因此一旦算法的種群趨于收斂，它也就失去了對(duì)環(huán)境變化的適應(yīng)能力，這就是進(jìn)化算法在動(dòng)態(tài)

3、環(huán)境中所面臨的主要挑戰(zhàn)。 為了解決上述問(wèn)題，本文遵循綜述—算法研究—算法應(yīng)用的思路對(duì)動(dòng)態(tài)進(jìn)化計(jì)算方法進(jìn)行系統(tǒng)性研究，具體內(nèi)容如下： (1)對(duì)動(dòng)態(tài)環(huán)境中進(jìn)化計(jì)算方法的相關(guān)研究情況進(jìn)行了詳細(xì)地綜述。首先對(duì)進(jìn)化計(jì)算方法所關(guān)注的動(dòng)態(tài)優(yōu)化問(wèn)題進(jìn)行概述，詳細(xì)介紹了動(dòng)態(tài)環(huán)境的基本特征以及各種被用于測(cè)試算法性能的動(dòng)態(tài)優(yōu)化問(wèn)題，并對(duì)算法性能的評(píng)估方法和環(huán)境變化的探測(cè)方法也進(jìn)行了簡(jiǎn)述。然后綜述了各種動(dòng)態(tài)環(huán)境中的進(jìn)化算法，把這些方法分為修改E

4、A算子策略，始終保持種群多樣性策略，基于記憶的方法和多種群的方法四類進(jìn)行介紹。最后對(duì)求解動(dòng)態(tài)優(yōu)化問(wèn)題的粒子群優(yōu)化算法也進(jìn)行簡(jiǎn)單綜述。 (2)對(duì)—種求解動(dòng)態(tài)0-1優(yōu)化問(wèn)題的原對(duì)偶遺傳算法(PDGA)進(jìn)行研究，通過(guò)對(duì)算法中一個(gè)關(guān)鍵運(yùn)算一原對(duì)偶映射(PDM)的討論和分析，提出了一種基于統(tǒng)計(jì)概率的PDM方法，通過(guò)一組動(dòng)態(tài)測(cè)試函數(shù)的實(shí)驗(yàn)表明這種基于統(tǒng)計(jì)概率的PDGA(S-PDGA)在動(dòng)態(tài)環(huán)境中能夠獲得更好的性能。 (3)時(shí)變背包問(wèn)

5、題是一類被廣泛研究的動(dòng)態(tài)優(yōu)化問(wèn)題，雖然這類問(wèn)題并不是實(shí)際意義上的優(yōu)化問(wèn)題，但是很多現(xiàn)實(shí)世界中的問(wèn)題都可以通過(guò)它來(lái)描述。針對(duì)這類問(wèn)題的研究有利于動(dòng)態(tài)進(jìn)化計(jì)算方法在簡(jiǎn)單的函數(shù)優(yōu)化和最終應(yīng)用到求解復(fù)雜的現(xiàn)實(shí)優(yōu)化問(wèn)題之間搭建起聯(lián)系的橋梁。本文利用PDGA算法對(duì)兩類不同的時(shí)變背包問(wèn)題進(jìn)行求解，仿真實(shí)驗(yàn)表明所提出的S-PDGA算法能夠很好解決這類問(wèn)題。 (4)近些年來(lái)，利用用粒子群優(yōu)化算法(PSO)求解動(dòng)態(tài)優(yōu)化問(wèn)題的研究引起了越來(lái)越多的關(guān)注

6、。本文將一種顯式記憶的思想引入到PSO中，同時(shí)為了保持算法的搜索能力和開(kāi)發(fā)能力的平衡，將整個(gè)粒子群分成搜索粒子群、開(kāi)發(fā)粒子群和記憶粒子群三個(gè)子粒子群，從而提出了—種記憶增強(qiáng)的三島PSO算法。為了增強(qiáng)這種三島PSO算法的探索能力，本文進(jìn)一步討論了—種觸發(fā)式記憶的方法，提出了兩種不同的觸發(fā)方案，并對(duì)記憶信息的各種重用方法也進(jìn)行了討論，通過(guò)對(duì)移動(dòng)峰問(wèn)題的實(shí)驗(yàn)，表明了這種觸發(fā)式記憶方法能夠使PSO更為適用和有效地求解動(dòng)態(tài)優(yōu)化問(wèn)題。 (5

7、)對(duì)動(dòng)態(tài)環(huán)境中的多粒子群PSO算法進(jìn)行研究。首先討論了各粒子群之間如何進(jìn)行相互作用和聯(lián)系以及怎樣更新的各種策略，提出了一種多粒子群PSO算法(MPSO)，然后根據(jù)一種分叉GA的思想，提出了另—種多粒子群算法(FPSO)以解決MPSO中子種群數(shù)量不易直接確定的問(wèn)題，最后通過(guò)實(shí)驗(yàn)來(lái)檢驗(yàn)兩種多粒子群PSO算法的優(yōu)劣點(diǎn)。 (6)城市供水系統(tǒng)的運(yùn)行是一個(gè)持續(xù)不問(wèn)斷的過(guò)程，本文將整個(gè)供水調(diào)度過(guò)程看作是一個(gè)連續(xù)的實(shí)時(shí)優(yōu)化過(guò)程，利用基于記憶的P