【摘要】：多目標(biāo)優(yōu)化問題是在科學(xué)研究和生產(chǎn)應(yīng)用中廣泛存在的一類具有挑戰(zhàn)性的優(yōu)化問題。其難點在于問題的多個目標(biāo)之間往往存在沖突,導(dǎo)致通常不存在一個可以滿足所有優(yōu)化目標(biāo)的解,因此現(xiàn)有的解析方法難以對其進(jìn)行精確求解。演化算法因其基于種群的多點搜索機(jī)制,及對問題性質(zhì)不做特別假設(shè),天然地符合多目標(biāo)優(yōu)化尋找一組在多個目標(biāo)之間進(jìn)行折衷的最優(yōu)解集的逼近集合的需求。因此,多目標(biāo)演化算法已成為求解這類問題的主流技術(shù)手段之一。隨著多目標(biāo)演化算法的發(fā)展,其擴(kuò)放性逐漸受到了研究者的關(guān)注。相比于多目標(biāo)演化算法在目標(biāo)維度的擴(kuò)放性受到的廣泛關(guān)注,目前研究其在決策變量維度的擴(kuò)放性的工作較少。然而,這一點是與實際需求是相悖的。其一,大規(guī)模多目標(biāo)優(yōu)化問題的求解是有其應(yīng)用需求的,如深度神經(jīng)網(wǎng)絡(luò)權(quán)值優(yōu)化問題、大規(guī)模多目標(biāo)社交網(wǎng)絡(luò)分析、多目標(biāo)車輛路徑規(guī)劃問題等;其二,現(xiàn)有多目標(biāo)演化算法的性能隨變量數(shù)增大而急劇下降,難以有效求解大規(guī)模多目標(biāo)問題�；诖�,本文針對大規(guī)模多目標(biāo)演化優(yōu)化進(jìn)行研究,通過分析連續(xù)和離散多目標(biāo)優(yōu)化問題的特性,設(shè)計高效求解大規(guī)模多目標(biāo)優(yōu)化問題的多目標(biāo)演化算法。本文的主要研究工作與創(chuàng)新之處包括以下幾個方面:1.面向大規(guī)模多目標(biāo)連續(xù)優(yōu)化問題的分析和演化算法研究。由于多個優(yōu)化目標(biāo)之間存在沖突,人們通常希望尋求一組稱之為Pareto最優(yōu)解集,來尋求多個目標(biāo)之間的折衷。針對這類問題,研究者們已經(jīng)提出了許多多目標(biāo)演化算法。但這些算法的性能隨規(guī)模增大顯著降低。因此,本文首先通過幾個典型的測試問題集,深入分析制約現(xiàn)有多目標(biāo)演化算法可擴(kuò)放性的關(guān)鍵瓶頸,并將這些測試問題依據(jù)規(guī)模因素所帶來的影響劃分為三類,即聚焦收斂性的問題、聚焦多樣性且無收斂-多樣相關(guān)性的問題、聚焦多樣性且有收斂-多樣相關(guān)性的問題。對于第一類問題,現(xiàn)有的大規(guī)模單目標(biāo)優(yōu)化的研究成果天然地可以借鑒進(jìn)來。對于第二類問題,由于收斂-多樣之間無相關(guān)性,算法對于收斂性和多樣性的需求可以相對獨(dú)立地得到滿足。實驗結(jié)果表明,現(xiàn)有的大規(guī)模算法可以很好地對這類問題進(jìn)行求解。對于第三類問題,與前兩類問題的優(yōu)異性能相比,現(xiàn)有的大規(guī)模算法不能對其進(jìn)行很好地求解,甚至表現(xiàn)出比傳統(tǒng)多目標(biāo)演化算法還要差的性能。因此,對于這類問題的求解,亟待研究�；诖�,本文提出了一個帶多樣性導(dǎo)向機(jī)制的大規(guī)模多目標(biāo)演化算法。它以經(jīng)典的SMS-EMOA為基本框架,引入一個基于外部集的新解生成器以加強(qiáng)多樣性。該新解生成器的基本思想是,強(qiáng)迫外部集中的個體搜索Pareto前沿的不同區(qū)域,以產(chǎn)生目標(biāo)空間中多樣的新生個體。我們提出了一個雙重局部搜索機(jī)制以實現(xiàn)其搜索。實驗結(jié)果表明,該算法可以比現(xiàn)有算法在第三類問題上得到更好的解,并且實現(xiàn)更好的收斂性和多樣性之間的平衡。2.針對一種復(fù)雜的現(xiàn)實大規(guī)模多目標(biāo)連續(xù)優(yōu)化問題,即ROC凸包最大化問題,進(jìn)行研究�；赗OC凸包的分類問題旨在尋找一組在TPR和FPR之間進(jìn)行權(quán)衡的分類器。其本質(zhì)上是一個多目標(biāo)優(yōu)化問題。隨著數(shù)據(jù)維度、分類器超參數(shù)目等變量的數(shù)目規(guī)模急劇增大,這類問題展現(xiàn)出大規(guī)模多目標(biāo)優(yōu)化問題的特性。然而,不同于一般性的多目標(biāo)優(yōu)化問題,它的求解目標(biāo)是尋求一組稱之為凸包解集的最優(yōu)解集。因此,研究者們已經(jīng)提出了一些基于凸包的多目標(biāo)演化算法。然而,在求解大規(guī)模問題時,現(xiàn)有算法表現(xiàn)出多樣性不足的現(xiàn)象。因此,本文在現(xiàn)有算法的基礎(chǔ)上,提出了一個改進(jìn)版的基于凸包的多目標(biāo)演化算法,以加強(qiáng)其多樣性。具體地,該算法采用一個基于個體最小值凸包的多目標(biāo)排序策略和基于凸包面積最大化的選擇機(jī)制實現(xiàn)對種群的選擇。在多個高維不平衡數(shù)據(jù)集上的實驗結(jié)果表明,通過優(yōu)化一組神經(jīng)網(wǎng)絡(luò)的權(quán)值,該算法可比現(xiàn)有算法得到的分類性能更好。3.針對一種復(fù)雜的現(xiàn)實大規(guī)模多目標(biāo)離散優(yōu)化問題,即社交網(wǎng)絡(luò)上的影響力最大化問題,進(jìn)行研究。社交網(wǎng)絡(luò)上的影響力最大化問題是近年來得到廣泛關(guān)注的一個組合優(yōu)化問題。在競爭環(huán)境下,該問題的研究旨在從眾多網(wǎng)絡(luò)節(jié)點中,找出在其他參與者的競爭下影響力仍能超過指定閾值的、始發(fā)數(shù)最少的一組節(jié)點。然而,隨著社交網(wǎng)絡(luò)規(guī)模的增大,現(xiàn)有的研究方法難以在可接受的時間內(nèi)給出一個質(zhì)量可接受的解�；诖�,本文首先將競爭環(huán)境中的影響力最大化問題建模成一個多目標(biāo)優(yōu)化問題,并設(shè)計了一個可擴(kuò)放的多目標(biāo)演化算法對其進(jìn)行求解。具體地,一個變可行域搜索的機(jī)制被提出以加速算法的搜索速率,以提升多樣性和收斂性之間平衡。在多個大規(guī)模的社交網(wǎng)絡(luò)上的實驗結(jié)果表明,該算法相對于現(xiàn)有方法,可以在問題求解的性能和時間開銷之間給出一個比較好的平衡。
【學(xué)位授予單位】：中國科學(xué)技術(shù)大學(xué)
【學(xué)位級別】：博士
【學(xué)位授予年份】：2018
【分類號】：TP18
【圖文】：

逡逑１．５本文的組織結(jié)構(gòu)逡逑本文的組織結(jié)構(gòu)如圖１．１所示。第１章介紹了大規(guī)模多目標(biāo)優(yōu)化的背景知識、逡逑當(dāng)前研究中存在的一些問題，以及本文的主要工作。第２章對大規(guī)模多目標(biāo)演化逡逑算法的研究進(jìn)展進(jìn)行了全面的綜述。逡逑第１章：緒論逡逑第２章：大規(guī)模多目逡逑標(biāo)優(yōu)化的研宄現(xiàn)狀逡逑／邋一逡逑！邋｜第３章：大規(guī)模邐｜第４章：基于大規(guī)邐｜第５章：基于多目標(biāo)逡逑多目標(biāo)演化算邐模多目標(biāo)演化的邐演化的大規(guī)模社交網(wǎng)逡逑！邐＾邐｜邋ＲＯＣ凸包最大化邐｜邋絡(luò)影響力最大化逡逑Ｖ—邐邐邐邐邐邐—．．．．．．邐邐—．．．．．．邐邐Ｊ逡逑第６章：總結(jié)和展望逡逑圖１．１本文組織結(jié)構(gòu)圖逡逑９逡逑

間相互沖突，多目標(biāo)演化算法通常會對其進(jìn)行權(quán)衡，c\索一組稱為Ｐａｒｅｔｏ最優(yōu)逡逑解的解集。所有Ｐａｒｅｔｏ最優(yōu)解的集合在目標(biāo)空間中的圖像稱為Ｐａｒｅｔｏ前沿ｔ１４＇逡逑然而，Ｐａｒｅｔｏ前沿與ＲＯＣ凸包不完全相同，如圖４．１所示。點Ａ和Ｄ位于逡逑ＲＯＣ凸包上，而點Ｂ，Ｃ和Ｅ不在。盡管在Ｐａｒｅｔｏ最優(yōu)的概念中所有五個分類逡逑器被認(rèn)為是同等最優(yōu)的，但是對應(yīng)于點Ｂ，Ｃ和Ｅ的分類器在ＲＯＣ圖中表現(xiàn)出逡逑更差的性能。當(dāng)且僅：１：彳某個分類器的性能在ＲＯＣ凸包N、該分類器才被認(rèn)為是逡逑最佳的。由于在ＲＯＣ圖中，任何虛擬分類器都可以通過混合兩個真實分類器來逡逑構(gòu)造，其性能可以由這兩個真實分類器對應(yīng)的點的連接線上的點表示［％。因此，逡逑可以通過ＲＯＣ凸包來改進(jìn)與Ｐａｒｅｔｏ前沿相對應(yīng)的一組分類器�？紤]到ＲＯＣ凸逡逑包的這種特性，傳統(tǒng)的基于Ｐａｒｅｔｏ的多Q儽暄莼惴ǹ贍芪薹ù锏攪己玫男閱�。辶x弦虼�，臭溨了官懻V徊窖芯客拱蘊(yùn)岣擼遙希瞇閱艿墓ぷ鰨蓿保矗梗蕁ｅ義希矗峰義

本文編號：2794079