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

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

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

本文編號：2794079