本文關(guān)鍵詞：兩類復(fù)雜優(yōu)化問題的進(jìn)化算法及應(yīng)用研究　出處：《西安電子科技大學(xué)》2016年博士論文　論文類型：學(xué)位論文

  更多相關(guān)文章： 協(xié)同進(jìn)化 均勻聚集距離 多目標(biāo)優(yōu)化 均勻設(shè)計(jì) 多樣性測度 可分任務(wù)調(diào)度

【摘要】：全局優(yōu)化和多目標(biāo)優(yōu)化問題是兩類復(fù)雜的優(yōu)化問題,它們?cè)跀?shù)學(xué)、工程、管理、軍事等諸多領(lǐng)域有著廣泛的應(yīng)用,但是當(dāng)問題為非線性全局優(yōu)化和非線性非凸多目標(biāo)優(yōu)化問題時(shí),對(duì)它們求解非常困難,研究它們高效的求解算法不僅具有重要的理論意義,而且具有廣泛的應(yīng)用價(jià)值。進(jìn)化算法是求解這些復(fù)雜優(yōu)化問題的一種智能優(yōu)化算法,已經(jīng)成功地解決了實(shí)際中許多復(fù)雜優(yōu)化問題。隨著進(jìn)化算法研究和應(yīng)用的不斷深入,通過多種機(jī)制有機(jī)協(xié)同的進(jìn)化算法已成為提高算法效率和改善其適應(yīng)性的有效途徑,尤其適合解決高維、非線性、不可微、多局部最優(yōu)、多目標(biāo)、動(dòng)態(tài)不確定等復(fù)雜優(yōu)化問題。本文針對(duì)高維非線性全局優(yōu)化和非線性非凸多目標(biāo)優(yōu)化問題的高效進(jìn)化算法進(jìn)行了深入研究,提出了幾種高效的進(jìn)化算法,并以并行與分布式系統(tǒng)下的可分任務(wù)調(diào)度問題為實(shí)際應(yīng)用背景,建立了一個(gè)任務(wù)優(yōu)化調(diào)度模型,并設(shè)計(jì)了相應(yīng)的進(jìn)化算法對(duì)模型進(jìn)行求解。具體工作如下：1、NSGA-Ⅱ(Non-dominated Sorting Genetic Algorithm-Ⅱ)算法是目前求解多目標(biāo)優(yōu)化問題的最有效算法之一,其中,聚集距離在NSGA-Ⅱ算法的收斂性和分布均勻性保持上起到重要的作用,但算法沒有充分利用微觀的個(gè)體本身和宏觀的種群整體信息。為更合理地估計(jì)區(qū)域密度,使所求解集更好更均勻地收斂于Pareto最優(yōu)邊界,本文利用均勻聚集區(qū)間和基尼系數(shù)權(quán)重構(gòu)造了一種均勻聚集距離算子,并基于該算子提出了一種改進(jìn)的NSGA-Ⅱ算法。最后,通過對(duì)10個(gè)標(biāo)準(zhǔn)多目標(biāo)測試問題的實(shí)驗(yàn)驗(yàn)證了算法的有效性。2、目標(biāo)函數(shù)加權(quán)法是求解多目標(biāo)優(yōu)化問題最常用和最簡單的方法。但是,對(duì)于非凸或者復(fù)雜多目標(biāo)優(yōu)化問題,這種方法無法求出Pareto前沿非凸部分的最優(yōu)解,因而通常無法求出在整個(gè)Pareto前沿均勻分布的代表解集。為了解決這個(gè)問題,本文提出了一種新的基于自適應(yīng)多適應(yīng)度函數(shù)和空間劃分進(jìn)化算法。通過均勻設(shè)計(jì)將目標(biāo)空間劃分為相近大小的多個(gè)區(qū)域,每個(gè)區(qū)域由目標(biāo)函數(shù)加權(quán)作為其適應(yīng)度函數(shù)來搜索該區(qū)域內(nèi)的非支配解。當(dāng)某個(gè)區(qū)域包含較少的非支配解時(shí),該區(qū)域會(huì)被劃分為更小的子區(qū)域,且會(huì)為每個(gè)子區(qū)域添加一個(gè)新的適應(yīng)度函數(shù)。因此,每個(gè)區(qū)域內(nèi)的Pareto解將逐步得到更新,最終均勻地分布在整個(gè)Pareto前沿。最后,通過求解13個(gè)標(biāo)準(zhǔn)測試函數(shù),將所提算法與10個(gè)已有算法進(jìn)行了性能比較。結(jié)果表明所提算法的性能要優(yōu)于已有算法,它不僅可以有效的解決非凸及復(fù)雜優(yōu)化問題,而且可以在整個(gè)Pareto前沿找到分布均勻且寬廣的解集。3、未成熟收斂以及收斂性能差等是目前進(jìn)化算法面臨的重要缺陷。為了進(jìn)一步提高進(jìn)化算法的全局搜索能力和避免算法陷入局部最優(yōu)解,本文提出了一種基于基因多樣性測度的自適應(yīng)協(xié)同進(jìn)化算法,并且證明了算法的全局收斂性。該算法以基因多樣性測度為紐帶,實(shí)現(xiàn)了算子之間的協(xié)同搜索；通過自適應(yīng)的選擇算子和變異算子維持了子種群的多樣性,降低算法陷入局部最優(yōu)解的可能性；通過自適應(yīng)替換算子實(shí)現(xiàn)了各子種群信息之間的動(dòng)態(tài)協(xié)同交換,提高了子種群交互信息價(jià)值潛力和算法的搜索能力。最后,通過7個(gè)函數(shù)優(yōu)化實(shí)驗(yàn)驗(yàn)證了算法的有效性。4、針對(duì)并行與分布式系統(tǒng)下的可分任務(wù)調(diào)度這一實(shí)際應(yīng)用問題,考慮到處理機(jī)的異構(gòu)性,即處理機(jī)具有任意大小的通信速率、計(jì)算速率、計(jì)算啟動(dòng)開銷和通信啟動(dòng)開銷,本文以任務(wù)的最短完成時(shí)間為目標(biāo)建立了一個(gè)新的優(yōu)化模型。該模型可以解決以下三個(gè)問題：確定最優(yōu)的參與計(jì)算的處理機(jī)數(shù)目、最優(yōu)的處理機(jī)調(diào)度順序,以及最優(yōu)的任務(wù)分配方案。為了有效的求解該模型,本文設(shè)計(jì)了一種新的混合遺傳算法,并證明了該算法以概率1收斂到全局最優(yōu)解。為了加快算法的收斂,在算法中引入了局部搜索策略。最后,通過仿真實(shí)驗(yàn)驗(yàn)證了模型和算法的有效性。
[Abstract]:Global optimization and multi-objective optimization problems are two kinds of complex optimization problems, in mathematics, engineering, management, military and other fields has been widely used, but when the problem is a multi-objective optimization problem of nonlinear and non convex global optimization and nonlinear, it is difficult to solve them, study their efficient algorithm not only has the important theoretical significance, but also has wide application value. The evolutionary algorithm is an intelligent optimization algorithm for solving the complex optimization problems, has succeeded in solving many complex optimization problems in practice. With the research and application of the algorithm deeply, through various mechanisms of organic co evolutionary algorithm has become an effective way to improve the algorithm to improve the efficiency and adaptability, especially suitable for solving high dimensional, nonlinear, non differentiable, locally optimal, multi-objective, uncertain dynamic and complex optimization problems. This paper studies efficient evolutionary algorithm for non convex multiobjective optimization problem of high-dimensional nonlinear global optimization and nonlinear characteristics, puts forward several efficient evolutionary algorithms, and practical applications in parallel and distributed systems can be divided into task scheduling, a task scheduling model, and design the evolutionary algorithm corresponding to solve the model. The details are as follows: 1, NSGA- II (Non-dominated Sorting Genetic Algorithm- II) algorithm is one of the most effective algorithm to solve multi-objective optimization problem in which the crowding distance plays an important role in the convergence and distribution of NSGA- II algorithm to maintain homogeneity, but the algorithm does not make full use of the micro individual and macro population overall information. For the better estimation of regional density, the better solution set more uniformly converges to the optimal boundary Pareto, Uniform aggregation interval and Gene coefficient weight to construct a uniform distance based aggregation operator, and the operator is proposed based on an improved NSGA- algorithm. Finally, based on the multi-objective test problems of 10 standard experiments verify the effectiveness of.2 algorithm, the objective function is the weighted method for multi-objective optimization problems the most common and simple method. However, for non convex or complex multi-objective optimization problem, this method can find the optimal solution of the nonconvex Pareto front, and usually cannot find out evenly throughout the Pareto front generation table set. In order to solve this problem, this paper presents a new adaptive multi adaptation function and space division evolutionary algorithm based on uniform design. Through the objective space is divided into multiple regions similar to the size of each region by weighted objective function as the fitness function Searching the non dominated solutions in the region. When the non dominated solution of a region contains less, the area will be divided into smaller sub regions, and will add a new fitness function for each sub region. Therefore, each region within the Pareto solution will gradually be updated, eventually uniformly distributed throughout the Pareto frontier. Finally, by solving 13 standard test functions, the proposed algorithm is compared with 10 existing algorithms are compared. The results show that the performance of the proposed algorithm is superior to the existing algorithms, it can not only convex and non effective to solve complex optimization problems, but also can find the solution and uniform distribution set.3 broad in the Pareto frontier, premature convergence and convergence performance of the poor is an important defect of current evolutionary algorithm face. In order to further improve the global search ability of evolutionary algorithm and avoid local optima, this paper. A co evolutionary algorithm based on adaptive measurement of gene diversity, and prove the global convergence of the algorithm. The algorithm to measure the genetic diversity as a link, to achieve synergies between the search operator; the selection operator and adaptive mutation operator to maintain the diversity of sub populations, reduce the possibility of getting into local optimal algorithm the solution; the adaptive operator realizes the dynamic substitution between sub population information collaborative exchange, improve the sub population interaction information value potential and search ability of the algorithm. Finally, through the 7 function optimization experiments verify the effectiveness of the.4 algorithm, aiming at the practical problem of scheduling parallel and distributed system under the sub tasks, taking into account the heterogeneity of processors, computing speed of communication rate, the processor has any size, computational overhead and communication overhead start start, taking To establish a new optimization model of task completion time shortest as the goal. The model can solve the following three problems: to determine the optimal number of processors involved in the computation of the optimal sequence, processor scheduling, and the optimal task allocation scheme. In order to solve the proposed model, this paper designed a new hybrid the genetic algorithm, and proves that the algorithm with probability 1 converges to the global optimal solution. In order to speed up the convergence of the algorithm, the local search strategy is introduced in the algorithm. Finally, through the simulation experiments verify the effectiveness of the model and algorithm.

【學(xué)位授予單位】：西安電子科技大學(xué)
【學(xué)位級(jí)別】：博士
【學(xué)位授予年份】：2016
【分類號(hào)】：TP18

【相似文獻(xiàn)】

相關(guān)期刊論文 前10條

1 葛磊;武芳;王鵬波;張冬林;;3維建筑綜合中基于最小特征的面平移算法[J];測繪科學(xué)技術(shù)學(xué)報(bào);2009年02期

2 駱雯,孫延明,陳振威,陳錦昌;判斷點(diǎn)與封閉多邊形相對(duì)關(guān)系的改進(jìn)算法[J];機(jī)械;1999年03期

3 李林;盧顯良;;一種基于切割映射的規(guī)則沖突消除算法[J];電子學(xué)報(bào);2008年02期

4 劉巧玲;張紅英;林茂松;;一種簡單快速的圖像去霧算法[J];計(jì)算機(jī)應(yīng)用與軟件;2013年07期

5 林亞平,楊小林;快速概率分析進(jìn)化算法及其性能研究[J];電子學(xué)報(bào);2001年02期

6 章郡鋒;吳曉紅;黃曉強(qiáng);何小海;;基于暗原色先驗(yàn)去霧的改進(jìn)算法[J];電視技術(shù);2013年23期

7 楊鐵軍;靳婷;;一種動(dòng)態(tài)整周模糊值求解算法及其仿真分析[J];系統(tǒng)工程與電子技術(shù);2007年01期

8 周秀玲;郭平;陳寶維;王靜;;幾種計(jì)算超體積算法的比較研究[J];計(jì)算機(jī)工程;2011年03期

9 吳一戎,胡東輝,彭海良;Chirp Scaling SAR成象算法及其實(shí)現(xiàn)[J];電子科學(xué)學(xué)刊;1995年03期

10 王貴竹;一種產(chǎn)生單向分解值的算法[J];安徽大學(xué)學(xué)報(bào)(自然科學(xué)版);2001年03期

相關(guān)會(huì)議論文 前10條

1 尹冀鋒;;一種新的圖象自適應(yīng)增強(qiáng)算法[A];四川省通信學(xué)會(huì)一九九二年學(xué)術(shù)年會(huì)論文集[C];1992年

2 寧春平;田家瑋;郭延輝;王影;張英濤;鄭桂霞;劉研;;計(jì)算機(jī)輔助增強(qiáng)、分割算法在鑒別乳腺良、惡性腫塊中的應(yīng)用價(jià)值[A];中華醫(yī)學(xué)會(huì)第十次全國超聲醫(yī)學(xué)學(xué)術(shù)會(huì)議論文匯編[C];2009年

3 謝麗聰;;SVB查詢改寫算法的改進(jìn)[A];第二十一屆中國數(shù)據(jù)庫學(xué)術(shù)會(huì)議論文集（研究報(bào)告篇）[C];2004年

4 鄭存紅;;復(fù)雜背景下相關(guān)跟蹤算法研究及DSP實(shí)現(xiàn)[A];中國光學(xué)學(xué)會(huì)2010年光學(xué)大會(huì)論文集[C];2010年

5 楊文杰;吳軍;;RFID抗沖突算法研究[A];2008通信理論與技術(shù)新進(jìn)展——第十三屆全國青年通信學(xué)術(shù)會(huì)議論文集（上）[C];2008年

6 高山;畢篤彥;魏娜;;一種基于UPF的小目標(biāo)TBD算法[A];第十四屆全國圖象圖形學(xué)學(xué)術(shù)會(huì)議論文集[C];2008年

7 周磊;張衛(wèi)華;王曉奇;張軍;;基于流水算法的智能路障機(jī)器人設(shè)計(jì)[A];2011年全國電子信息技術(shù)與應(yīng)用學(xué)術(shù)會(huì)議論文集[C];2011年

8 潘巍;李戰(zhàn)懷;陳群;索博;李衛(wèi)榜;;面向MapReduce的非對(duì)稱分片復(fù)制連接算法優(yōu)化技術(shù)研究[A];第29屆中國數(shù)據(jù)庫學(xué)術(shù)會(huì)議論文集（B輯）（NDBC2012）[C];2012年

9 李偉偉;蔡康穎;鄭新;王文成;;3D模型中重復(fù)結(jié)構(gòu)的多尺度快速檢測算法[A];第六屆和諧人機(jī)環(huán)境聯(lián)合學(xué)術(shù)會(huì)議（HHME2010)、第19屆全國多媒體學(xué)術(shù)會(huì)議（NCMT2010）、第6屆全國人機(jī)交互學(xué)術(shù)會(huì)議（CHCI2010）、第5屆全國普適計(jì)算學(xué)術(shù)會(huì)議（PCC2010）論文集[C];2010年

10 楊任爾;陳懇;勵(lì)金祥;;基于棱邊方向檢測的運(yùn)動(dòng)自適應(yīng)去隔行算法[A];Proceedings of 2010 Chinese Control and Decision Conference[C];2010年

相關(guān)重要報(bào)紙文章 前1條

1 國泰君安資產(chǎn)管理部;“算法交易”是道指暴跌罪魁禍?zhǔn)?[N];上海證券報(bào);2010年

相關(guān)博士學(xué)位論文 前10條

1 馮輝;網(wǎng)絡(luò)化的并行與分布式優(yōu)化算法研究及應(yīng)用[D];復(fù)旦大學(xué);2013年

2 許玉杰;云計(jì)算環(huán)境下海量數(shù)據(jù)的并行聚類算法研究[D];大連海事大學(xué);2014年

3 李琰;基于貓群算法的高光譜遙感森林類型識(shí)別研究[D];東北林業(yè)大學(xué);2015年

4 陳加順;海洋環(huán)境下聚類算法的研究[D];南京航空航天大學(xué);2014年

5 王洋;基于群體智能的通信網(wǎng)絡(luò)告警關(guān)聯(lián)規(guī)則挖掘算法研究[D];太原理工大學(xué);2015年

6 雷雨;面向考試時(shí)間表問題的啟發(fā)式進(jìn)化算法研究[D];西安電子科技大學(xué);2015年

7 熊霖;大數(shù)據(jù)下的數(shù)據(jù)選擇與學(xué)習(xí)算法研究[D];西安電子科技大學(xué);2015年

8 周雷;基于圖結(jié)構(gòu)的目標(biāo)檢測與分割算法研究[D];上海交通大學(xué);2014年

9 王冰;人工蜂群算法的改進(jìn)及相關(guān)應(yīng)用的研究[D];北京理工大學(xué);2015年

10 蔣亦樟;多視角和遷移學(xué)習(xí)識(shí)別方法和智能建模研究[D];江南大學(xué);2015年

相關(guān)碩士學(xué)位論文 前10條

1 姚鑫宇;EMD去噪與MUSIC算法在DOA估計(jì)中的聯(lián)合應(yīng)用[D];昆明理工大學(xué);2015年

2 陸進(jìn);面向含噪數(shù)據(jù)聚類相關(guān)算法的研究[D];復(fù)旦大學(xué);2014年

3 葉一舟;紅外弱小目標(biāo)檢測算法研究[D];上海交通大學(xué);2015年

4 王繼重;基于Hadoop和Mahout的K-Means算法設(shè)計(jì)與實(shí)現(xiàn)[D];大連海事大學(xué);2016年

5 何靜;遙感圖像的快速壓縮算法研究[D];北京交通大學(xué);2016年

6 章華燕;鋼軌擦傷檢測算法研究[D];北京交通大學(xué);2016年

7 王一博;MODIS地震熱異常的數(shù)據(jù)處理與算法研究[D];中國石油大學(xué)(華東);2014年

8 成鑫;基于組合優(yōu)化問題的多目標(biāo)模因算法的研究[D];南京航空航天大學(xué);2015年

9 傅致暉;基于協(xié)同分割的視頻目標(biāo)分割算法研究[D];上海交通大學(xué);2015年

10 張媛;運(yùn)動(dòng)車輛檢測與跟蹤算法的研究與實(shí)現(xiàn)[D];大連海事大學(xué);2016年

，

本文編號(hào)：1420672