【摘要】：在科學(xué)研究和工程領(lǐng)域中許多問題都是由多個相互沖突的目標(biāo)組成,一般稱這一類問題為多目標(biāo)優(yōu)化問題�；诜N群的進(jìn)化算法在單次運(yùn)行中能得到一個近似的Pareto解集,因此多目標(biāo)進(jìn)化算法已經(jīng)成為一種較為普遍且有效的求解多目標(biāo)優(yōu)化問題的方法。帶精英策略的非支配排序算法NSGA-Ⅱ(Elitist Non-dominated Sorting Genetic Algorithm)是2002年Deb等人對算法NSGA的改進(jìn),引入了快速非支配排序算法、精英策略以及擁擠度和擁擠度比較算子,是迄今為止最優(yōu)秀的進(jìn)化多目標(biāo)優(yōu)化算法之一。本文以穩(wěn)態(tài)NSGA-Ⅱ算法為框架,在非支配層的更新策略方面、自適應(yīng)算子選擇策略(Adaptive Operator Selection,AOS)的信用分配策略以及算子選擇策略等方面對穩(wěn)態(tài)NSGA-Ⅱ算法進(jìn)行了改進(jìn),提出基于自適應(yīng)選擇策略的穩(wěn)態(tài)NSGA-Ⅱ算法AOS_SSNSGA-Ⅱ。同時(shí)針對光網(wǎng)絡(luò)的特性,基于穩(wěn)態(tài)NSGA-Ⅱ框架提出了 MRWA_AOSNSGA-Ⅱ-SD算法用于求解光網(wǎng)絡(luò)組播路由波長分配問題。本文的主要工作如下:(1)針對穩(wěn)態(tài)NSGA-Ⅱ算法的改進(jìn),提出了一種基于自適應(yīng)算子選擇策略的穩(wěn)態(tài)NSGA-Ⅱ算法AOS_SSNSGA-Ⅱ。該算法采用穩(wěn)態(tài)NSGA-Ⅱ作為框架,使種群能夠在產(chǎn)生全部子種群之前被立即更新,從而精英信息能夠被及時(shí)的利用,克服了傳統(tǒng)NSGA-Ⅱ算法收斂速度慢的缺點(diǎn)。與此同時(shí),為了減少穩(wěn)態(tài)NSGA-Ⅱ算法維護(hù)非支配層結(jié)構(gòu)的開銷,提出了一種改進(jìn)型非支配層更新策略,通過從當(dāng)前非支配層結(jié)構(gòu)中提取的有效信息,僅在算法開始時(shí)進(jìn)行一次非支配排序,此后只需要對有限數(shù)量的非支配層結(jié)構(gòu)進(jìn)行更新,從而避免了大量不必要的比較操作。為提高算法對問題公式的魯棒性,克服由參數(shù)調(diào)整帶來的成本高、耗時(shí)長等問題,本文在穩(wěn)態(tài)NSGA-Ⅱ算法中加入自適應(yīng)算子選擇策略。對于信用分配方式,提出基于適應(yīng)率排序的信用分配策略,使用一個滑動窗口來記錄算子最近幾次迭代的適應(yīng)度增長率,從而動態(tài)跟蹤搜索過程,同時(shí)引用衰退機(jī)制來增加最佳算子的選擇概率;對于算子選擇策略,由于算子的性能可能會隨著種群的演化而出現(xiàn)很小或較大的波動,而算子所收到的信用值的動態(tài)分布會極大地影響算子選擇器的效率,因此提出基于多臂賭博機(jī)的算子選擇策略。與經(jīng)典進(jìn)化多目標(biāo)算法NSGA-Ⅱ、MOEA/D-DRA與R2-IBEA以及經(jīng)典的多目標(biāo)信用分配策略O(shè)P-Do、SI-Do、CS-Do以及算子選擇方式PM和AP相結(jié)合的方式相比,本文提出的算法AOS-SSNSGA-Ⅱ在ZDT和DTLZ系列標(biāo)準(zhǔn)的測試函數(shù)上有更好的收斂性和多樣性。(2)針對WDM網(wǎng)絡(luò)組播路由波長分配問題中存在多個相互沖突的QoS性能指標(biāo),本文提出光網(wǎng)絡(luò)組播路由的多目標(biāo)優(yōu)化數(shù)學(xué)模型MOMRWA,優(yōu)化的目標(biāo)包括組播網(wǎng)絡(luò)資源使用代價(jià)、端到端延遲、信道利用率,同時(shí)滿足端到端時(shí)延、可用帶寬、丟包率等QoS約束。為解決提出的MOMRWA問題,本文提出自適應(yīng)算子選擇策略與序貫分解機(jī)制相結(jié)合的穩(wěn)態(tài)NSGA-Ⅱ算法MRWA_AOSNSGA-Ⅱ-SD。對于組播波長分配子問題,本文采用動態(tài)波長分配算法中 的波長隨機(jī)分配法,對于組播路由子問題,本文提出備用選路策略;針對算法搜索過程中由于環(huán)路形成的不可行光樹,提出了一種基于MPH算法的光樹修復(fù)機(jī)制。實(shí)驗(yàn)結(jié)果表明提出的MRWA_AOSNSGA-Ⅱ-SD算法與其他算法相比在減少計(jì)算開銷的情況下能夠獲得更優(yōu)的Pareto解集,從而達(dá)到在減少組播路由時(shí)延與網(wǎng)絡(luò)資源使用費(fèi)用的情況下提高信道的利用率。
【學(xué)位授予單位】：湖南大學(xué)
【學(xué)位級別】：碩士
【學(xué)位授予年份】：2018
【分類號】：TP18
【圖文】：

ＮＳＧＡ－ＩＩ，差分進(jìn)化的選擇，而ＡＯＳ是算子的選擇，除此以外在其他方面類??似。??有ＡＯＳ策略的多目標(biāo)進(jìn)化算法的一般流程如圖１．１所示。在第ｔ次迭代中，??ＡＯＳ選擇一個算子來生成后代解，對后代進(jìn)行評估，并將其插入種群中，并根據(jù)??基本多目標(biāo)進(jìn)化算法進(jìn)行更新。如果算子對搜索過程有積極的影響，則會獲得獎??勵信用，這將增加其在后續(xù)迭代中被算子選擇器選擇的機(jī)會，搜索將繼續(xù)進(jìn)行，??直到達(dá)到終止標(biāo)準(zhǔn)為止。??ＡＯＳ策略的兩個主要組成部分是信用分配策略和算子選擇方式，信用分配策??略定義了如何根據(jù)算子在搜索過程中產(chǎn)生的影響來獎勵它，算子選擇方式將通過??上一步產(chǎn)生的獎勵來決定在后續(xù)優(yōu)化中選擇何種算子來應(yīng)用［５１］。??（１）信用分配策略??最常見的信用分配策略會獎勵那些能夠產(chǎn)生比父代的適應(yīng)度高的子代的算子??［４５］。其他的信用分配策略也會獎勵那些能夠產(chǎn)生高質(zhì)量子代的祖先的算子［５２］，但??這種信用分配策略是否有效還尚不清楚［５３］。Ｆｉａｌｈｏ等人建議，應(yīng)該獎勵那些做出??了罕見但大的改進(jìn)的算子

圖２．１多目標(biāo)優(yōu)化過程??多目標(biāo)優(yōu)化問題常用的兩個求解方法為使川多目標(biāo)優(yōu)化算法和將多目標(biāo)優(yōu)化??問題轉(zhuǎn)換成單口標(biāo)優(yōu)化問題。如圖２．１左邊部分為一個理想的多０標(biāo)優(yōu)化問題求??解的步驟流程圖，在步驟１中，多個權(quán)衡解被找到，然后在步驟２中更高層信息??用于從權(quán)衡解中選擇一個解，將這個步驟記住后，很容易可以意識到單目標(biāo)優(yōu)化??是多目標(biāo)優(yōu)化的一種簡單情況。在僅僅只有一個全局最優(yōu)解的單目標(biāo)優(yōu)化的情況??下，步驟１將只會找到一個解，因此不需要執(zhí)行步驟２。在有多個全局最優(yōu)解的??多目標(biāo)優(yōu)化的情況下，兩個步驟都是必要的，首先找到所有的全局最優(yōu)解，然后??通過問題的更高層信息并從其中選擇一個解。如圖２．１右邊部分是將多目標(biāo)優(yōu)化??問題轉(zhuǎn)換成單目標(biāo)優(yōu)化問題稱之為基于偏好的多目標(biāo)優(yōu)化，基于更高層信息，首??先選定了偏好向量ｍ然后偏好向量用于構(gòu)造復(fù)合函數(shù)，最后通過一個單目標(biāo)優(yōu)??化算法求得一個單一的最優(yōu)解。??１１??

ｘ＝（ｘ／，Ｘ２，．．．ｖＸｗ）是決策空間中一個ｎ維的向量，Ｚ７：?是ｍ維的目??標(biāo)向量，它是一個從／７維決策空間到ｍ維目標(biāo)空間０的映射。如圖２．２所示。??ｆＡ?ｅ＝｛Ｆｅ?ｒｗ｝??ｘｉ?＇?ｉｌ?＝?｛ｘｅ?Ｒｎ）????????決策空問?ｆｙ?（１？寧間??圖２．２決策空間到目標(biāo)空間的映射示意圖??２．１．２多目標(biāo)中Ｐａｒｅｔｏ解的相關(guān)定義??在求解多目標(biāo)優(yōu)化問題時(shí)，各個目標(biāo)函數(shù)得到的解可能是相悖的，很難找到??一個解使得所有目標(biāo)函數(shù)的值是最優(yōu)的。因此在求解時(shí)應(yīng)該盡可能的找到一些妥??協(xié)解，這些妥協(xié)解盡可能滿足多個目標(biāo)函數(shù)達(dá)到較優(yōu)。這一組解我們稱之為Ｐａｒｅｔｏ??最優(yōu)解或非支配解集。Ｐａｒｅｔｏ解的相關(guān)定義如下。??定義２．１：Ｐａｒｅｔｏ支配??給定兩個決策向量ＡＶＶＳＱ，如果；ｃ支配ｙ，則表示為ｉ＇ｖ，當(dāng)且僅當(dāng)解；ｃ在??所有目標(biāo)上不差于解且解ｘ至少在一個目標(biāo)上嚴(yán)格好于解??定義２．２：?Ｐａｒｅｔｏ最優(yōu)解??如果解當(dāng)且僅當(dāng)不存在解ｊｃｅｎ使得．ｘｘｘ＊，則稱Ｘ＊為Ｐａｒｅｔｏ最優(yōu)解。??定義２．３：?Ｐａｒｅｔｏ最優(yōu)解集??Ｐａｒｅｔｏ最優(yōu)解集（Ｐａｒｅｔｏｏｐｔｉｍａｌｓｏｌｕｔｉｏｎ），簡稱ＰＳ１。對于在決策空間??中所有最優(yōu)解組成的集合。Ｓ卩，ＰＳ＝｛ｘｅ｜ｘ是Ｐａｒｅｔｏ最優(yōu)解丨。多目標(biāo)進(jìn)化算法中??所求得解集就是Ｐａｒｅｔｏ最優(yōu)解集。??定義２．４：?Ｐａｒｅｔｏ前沿面??Ｐａｒｅｔｏ前沿面（Ｐａｒｅｔｏ?ｆｒｏｎｔ），簡稱ＰＦ。Ｐａｒｅｔｏ最優(yōu)解集中每個最優(yōu)解對應(yīng)的??目標(biāo)向量組成的曲面。??如圖２．３所示
【參考文獻(xiàn)】

中國期刊全文數(shù)據(jù)庫 前3條

1 吳啟武;王建萍;周賢偉;;WDM光網(wǎng)絡(luò)中的組播路由算法研究[J];電信科學(xué);2009年09期

2 公茂果;焦李成;楊咚咚;馬文萍;;進(jìn)化多目標(biāo)優(yōu)化算法研究[J];軟件學(xué)報(bào);2009年02期

3 李昌兵;曹長修;余義斌;;基于混合遺傳算法的多播路由多目標(biāo)優(yōu)化[J];計(jì)算機(jī)仿真;2007年09期

中國碩士學(xué)位論文全文數(shù)據(jù)庫 前1條

1 劉文娟;基于分解的多目標(biāo)量子差分進(jìn)化算法研究[D];山西財(cái)經(jīng)大學(xué);2015年

本文編號：2848487