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

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

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

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

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

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

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

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