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

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

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

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

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

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

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

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

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

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

本文編號(hào)：2848487