• 
    

    
    

      99热精品在线国产_美女午夜性视频免费_国产精品国产高清国产av_av欧美777_自拍偷自拍亚洲精品老妇_亚洲熟女精品中文字幕_www日本黄色视频网_国产精品野战在线观看 ?

      淺析多目標(biāo)優(yōu)化問題

      2013-08-15 00:54:11張淑艷段鵬松鄒衛(wèi)琴
      科技視界 2013年14期
      關(guān)鍵詞:測(cè)試用例支配適應(yīng)度

      張淑艷 段鵬松 鄒衛(wèi)琴

      (1.鄭州大學(xué) 軟件技術(shù)學(xué)院,河南 鄭州 450000;2.江西理工大學(xué) 軟件學(xué)院,江西 南昌 330000)

      多目標(biāo)優(yōu)化問題MOPs(Multi objective Optimization Problems)是工程實(shí)踐和科學(xué)研究中的主要問題形式之一,廣泛存在于優(yōu)化控制、機(jī)械設(shè)計(jì)、數(shù)據(jù)挖掘、移動(dòng)網(wǎng)絡(luò)規(guī)劃和邏輯電路設(shè)計(jì)等問題中。MOPs有多個(gè)目標(biāo),且各目標(biāo)相互沖突。對(duì)于MOPs,通常存在一個(gè)折衷的解集(即Pareto最優(yōu)解集),解集中的各個(gè)解在多目標(biāo)之間進(jìn)行權(quán)衡。獲取具有良好收斂性及分布性的解集是求解MOPs的關(guān)鍵。

      1 問題定義

      最小化MOPs的一般描述如下:

      min F(x)=(f1(x),f2(x),…,fm(x))

      其中解x=(x1,x2,…,xn)∈Ω為在決策空間Ω中的n維決策向量,f1(x),f2(x),…,fm(x)為 m 個(gè)相互沖突的目標(biāo)函數(shù)。 對(duì)于解 x1,x2∈Ω,x1支配 x2(記作 x1?x2),當(dāng)且僅當(dāng)?i∈(1,2,…,m)使得 fi(x1)≤fi(x2),且?i∈{1,2,…,m},使得 fi(x1)≤fi(x2)。解 x*∈Ω 為 Pareto 最優(yōu)解,當(dāng)且僅當(dāng)不存在解x∈Ω,使得x?x*。Pareto最優(yōu)解的集合稱為Pareto 最優(yōu)解集(記作 P*),P*={x*∈Ω|﹁?x∈Ω:x?x*}。 Pareto 最優(yōu)解集P*在目標(biāo)空間的映射稱為真實(shí)Pareto前沿面 (記作PF*),PF*={F(x*)=(f1(x*),f2(x*),…,fm(x*))|x*∈P*}。若 x1?x2,則稱 x2為支配解。解集P'被稱為非支配解集,當(dāng)且僅當(dāng)P'中不含支配解。

      2 多目標(biāo)優(yōu)化算法

      目前,大量算法用于求解MOPs。通常,可以將求解MOPs的算法分為兩類。

      第一類算法,將MOPs轉(zhuǎn)化為單目標(biāo)優(yōu)化問題。算法為每個(gè)目標(biāo)設(shè)置權(quán)值,通過加權(quán)的方式將多目標(biāo)轉(zhuǎn)化為單目標(biāo)。經(jīng)過改變權(quán)值大小,多次求解MOPs可以得到多個(gè)最優(yōu)解,構(gòu)成非支配解集[1]。

      第二類算法,直接求解MOPs。這類算法主要依靠進(jìn)化算法。進(jìn)化算法這種面向種群的全局搜索法,對(duì)于直接得到非支配解集是非常有效的?;谶M(jìn)化算法的多目標(biāo)優(yōu)化算法被稱為多目標(biāo)進(jìn)化算法。根據(jù)其特性,多目標(biāo)進(jìn)化算法可以劃分為兩代[2]。

      (1)第一代算法:以適應(yīng)度共享機(jī)制為分布性策略,并利用Pareto支配關(guān)系設(shè)計(jì)適應(yīng)度函數(shù)。代表算法如下。VEGA將種群劃分為若干子種群,每個(gè)子種群相對(duì)于一個(gè)目標(biāo)進(jìn)行優(yōu)化,最終將子種群合并。MOGA根據(jù)解的支配關(guān)系,為每個(gè)解分配等級(jí),算法按照等級(jí)為解設(shè)置適應(yīng)度函數(shù)。NSGA采用非支配排序的思想為每個(gè)解分配虛擬適應(yīng)度值,在進(jìn)化過程中,算法根據(jù)虛擬適應(yīng)度值采用比例選擇法選擇下一代。NPGA根據(jù)支配關(guān)系采用錦標(biāo)賽選擇法,當(dāng)解的支配關(guān)系相同時(shí),算法使用小生境技術(shù)選擇最優(yōu)的解進(jìn)入下一代。

      (2)第二代算法:以精英解保留機(jī)制為特征,并提出了多種較好的分布性策略。代表算法如下。NSGA-II降低了非支配排序的復(fù)雜度,并提出了基于擁擠距離的分布性策略。SPEA2提出了新的適應(yīng)度分配策略和基于環(huán)境選擇的分布性策略。PESA-II根據(jù)網(wǎng)絡(luò)超格選擇個(gè)體并使用了基于擁擠系數(shù)的分布性策略。

      近年來,在求解MOPs上,新的算法框架也在不斷提出。粒子群算法、分布估計(jì)算法、分解算法等已被逐漸用于求解MOPs。

      3 評(píng)估方法

      求解MOPs通常得到一個(gè)非支配解集,而解集的評(píng)估相對(duì)于單個(gè)解的評(píng)估更加復(fù)雜。目前存在多種方法評(píng)估非支配解集的質(zhì)量。通常,對(duì)非支配解集的評(píng)估分為兩個(gè)方面[3]。一方面,是收斂性,即評(píng)估非支配解集在目標(biāo)空間與真實(shí)Pareto前沿面的趨近程度。常用方法有錯(cuò)誤率、覆蓋率、世代距離、高維空間及其比率、基于聚集距離的趨近度評(píng)價(jià)方法等;另一方面,是分布性,即評(píng)估非支配解集在目標(biāo)空間分布的廣度和均勻度,常用方法有空間評(píng)價(jià)方法、基于個(gè)體信息的評(píng)價(jià)方法、網(wǎng)格分布評(píng)價(jià)方法、個(gè)體空間的分布度評(píng)價(jià)方法、基于聚類的評(píng)價(jià)函數(shù)等。

      4 測(cè)試用例

      算法性能的評(píng)估需要客觀的測(cè)試用例。Schaffer、Kursawe和Deb分別在1985年、1991年和1999年提出了較簡(jiǎn)單的兩目標(biāo)優(yōu)化測(cè)試用例SCH、KUR和DEB。Zitzler、Deb和Thiele在2000年提出了6個(gè)兩目標(biāo)優(yōu)化測(cè)試用例 ZDT1~ZDT6。 Deb、Thiele、Laumanns和 Zitzler在2002年提出了 7個(gè)多目標(biāo)優(yōu)化測(cè)試用例 DTLZ1~DTLZ7,DTLZ1~DTLZ7的決策變量和目標(biāo)數(shù)可以擴(kuò)展到任何數(shù)目[4]。上述測(cè)試用例均無約束,其Pareto最優(yōu)解集和真實(shí)Pareto前沿面可在(http://www.cs.cinvestav.mx/~emoobook/)下載。 Liu在 2008年為 CEC2009提出了 23個(gè)更加復(fù)雜的測(cè)試用例 CF1~CF10、R2-DTLZ2、R3-DTLZ3、WFG1 和CF1~CF10。其中CF1~CF7為7個(gè)無約束兩目標(biāo)優(yōu)化測(cè)試用例,CF8~CF10 為 3 個(gè)無約束三目標(biāo)優(yōu)化測(cè)試用例,R2-DTLZ2、R3-DTLZ3、WFG1為3個(gè)無約束五目標(biāo)優(yōu)化測(cè)試用例,CF1~CF7為7個(gè)帶約束兩目標(biāo)優(yōu)化測(cè)試用例,CF8~CF10為3個(gè)帶約束三目標(biāo)優(yōu)化測(cè)試用例。CEC2009的測(cè)試用例的問題描述、Pareto最優(yōu)解集和真實(shí)Pareto前沿面 可 在 網(wǎng) 站 (http://dces.essex.ac.uk/staff/qzhang/moeacompetition09.htm)下載。

      5 挑戰(zhàn)和困難

      由于MOPs與現(xiàn)實(shí)應(yīng)用的密切相關(guān)性,MOPs面臨許多研究課題:

      (1)現(xiàn)有大部分求解MOPs的算法都基于進(jìn)化算法,新的算法框架亟待提出。

      (2)對(duì)多目標(biāo)優(yōu)化算法的評(píng)估需要能夠客觀反映算法優(yōu)劣的評(píng)估方法和一組測(cè)試用例。評(píng)估方法和測(cè)試用例的選擇和設(shè)計(jì),是一個(gè)研究的關(guān)鍵問題。

      (3)現(xiàn)有多目標(biāo)優(yōu)化算法各有其優(yōu)缺點(diǎn),某個(gè)算法對(duì)求解一個(gè)問題是有效的,而對(duì)求解另一個(gè)問題可能是無效的。那么如何使各算法的優(yōu)缺點(diǎn)互補(bǔ)也是一個(gè)尚待研究的問題。

      6 結(jié)論

      MOPs在工程實(shí)踐和科學(xué)研究中是非常重要的。本文通過對(duì)MOPs的問題定義、多目標(biāo)優(yōu)化算法、評(píng)估方法、測(cè)試用例四個(gè)方面對(duì)MOPs的相關(guān)問題進(jìn)行闡述,最后分析了求解MOPs的挑戰(zhàn)和困難。

      [1]P.Hajela and C.Y.Lin.Genetic search strategies in multicriterion optimal design[J].Structural and Multidisciplinary Optimization,1992,4(2):99-107.

      [2]Coello Coello,C.A.Evolutionary Multi-Objective Optimization:A Historical View of the Field[J].IEEE Computational Intelligence Magazine,2006,1(1):28-36.

      [3]鄭金華.多目標(biāo)進(jìn)化算法及其應(yīng)用[M].北京:科學(xué)出版社,2007.

      [4]公茂果,焦李成,楊咚咚,馬文萍.進(jìn)化多目標(biāo)優(yōu)化算法研究[J].軟件學(xué)報(bào),2009,20(2):271-289.

      猜你喜歡
      測(cè)試用例支配適應(yīng)度
      改進(jìn)的自適應(yīng)復(fù)制、交叉和突變遺傳算法
      被貧窮生活支配的恐懼
      意林(2021年9期)2021-05-28 20:26:14
      基于SmartUnit的安全通信系統(tǒng)單元測(cè)試用例自動(dòng)生成
      跟蹤導(dǎo)練(四)4
      基于混合遺傳算法的回歸測(cè)試用例集最小化研究
      基于決策空間變換最近鄰方法的Pareto支配性預(yù)測(cè)
      隨心支配的清邁美食探店記
      Coco薇(2016年8期)2016-10-09 00:02:56
      基于空調(diào)導(dǎo)風(fēng)板成型工藝的Kriging模型適應(yīng)度研究
      基于依賴結(jié)構(gòu)的測(cè)試用例優(yōu)先級(jí)技術(shù)
      少數(shù)民族大學(xué)生文化適應(yīng)度調(diào)查
      岱山县| 上蔡县| 兖州市| 黄山市| 高邑县| 蛟河市| 荆门市| 定南县| 阜康市| 夏津县| 双柏县| 阿拉尔市| 鸡东县| 蓬莱市| 赞皇县| 高密市| 金塔县| 洪泽县| 北海市| 穆棱市| 金华市| 岗巴县| 清涧县| 榆林市| 祁阳县| 南城县| 民丰县| 秦皇岛市| 澄城县| 驻马店市| 五原县| 娄底市| 西昌市| 吕梁市| 四会市| 广灵县| 宜丰县| 卢氏县| 富民县| 甘孜| 乐平市|