發(fā)布時間：2018-01-13 21:38

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

  更多相關文章： 協(xié)同進化 均勻聚集距離 多目標優(yōu)化 均勻設計 多樣性測度 可分任務調度

【摘要】：全局優(yōu)化和多目標優(yōu)化問題是兩類復雜的優(yōu)化問題,它們在數學、工程、管理、軍事等諸多領域有著廣泛的應用,但是當問題為非線性全局優(yōu)化和非線性非凸多目標優(yōu)化問題時,對它們求解非常困難,研究它們高效的求解算法不僅具有重要的理論意義,而且具有廣泛的應用價值。進化算法是求解這些復雜優(yōu)化問題的一種智能優(yōu)化算法,已經成功地解決了實際中許多復雜優(yōu)化問題。隨著進化算法研究和應用的不斷深入,通過多種機制有機協(xié)同的進化算法已成為提高算法效率和改善其適應性的有效途徑,尤其適合解決高維、非線性、不可微、多局部最優(yōu)、多目標、動態(tài)不確定等復雜優(yōu)化問題。本文針對高維非線性全局優(yōu)化和非線性非凸多目標優(yōu)化問題的高效進化算法進行了深入研究,提出了幾種高效的進化算法,并以并行與分布式系統(tǒng)下的可分任務調度問題為實際應用背景,建立了一個任務優(yōu)化調度模型,并設計了相應的進化算法對模型進行求解。具體工作如下：1、NSGA-Ⅱ(Non-dominated Sorting Genetic Algorithm-Ⅱ)算法是目前求解多目標優(yōu)化問題的最有效算法之一,其中,聚集距離在NSGA-Ⅱ算法的收斂性和分布均勻性保持上起到重要的作用,但算法沒有充分利用微觀的個體本身和宏觀的種群整體信息。為更合理地估計區(qū)域密度,使所求解集更好更均勻地收斂于Pareto最優(yōu)邊界,本文利用均勻聚集區(qū)間和基尼系數權重構造了一種均勻聚集距離算子,并基于該算子提出了一種改進的NSGA-Ⅱ算法。最后,通過對10個標準多目標測試問題的實驗驗證了算法的有效性。2、目標函數加權法是求解多目標優(yōu)化問題最常用和最簡單的方法。但是,對于非凸或者復雜多目標優(yōu)化問題,這種方法無法求出Pareto前沿非凸部分的最優(yōu)解,因而通常無法求出在整個Pareto前沿均勻分布的代表解集。為了解決這個問題,本文提出了一種新的基于自適應多適應度函數和空間劃分進化算法。通過均勻設計將目標空間劃分為相近大小的多個區(qū)域,每個區(qū)域由目標函數加權作為其適應度函數來搜索該區(qū)域內的非支配解。當某個區(qū)域包含較少的非支配解時,該區(qū)域會被劃分為更小的子區(qū)域,且會為每個子區(qū)域添加一個新的適應度函數。因此,每個區(qū)域內的Pareto解將逐步得到更新,最終均勻地分布在整個Pareto前沿。最后,通過求解13個標準測試函數,將所提算法與10個已有算法進行了性能比較。結果表明所提算法的性能要優(yōu)于已有算法,它不僅可以有效的解決非凸及復雜優(yōu)化問題,而且可以在整個Pareto前沿找到分布均勻且寬廣的解集。3、未成熟收斂以及收斂性能差等是目前進化算法面臨的重要缺陷。為了進一步提高進化算法的全局搜索能力和避免算法陷入局部最優(yōu)解,本文提出了一種基于基因多樣性測度的自適應協(xié)同進化算法,并且證明了算法的全局收斂性。該算法以基因多樣性測度為紐帶,實現了算子之間的協(xié)同搜索；通過自適應的選擇算子和變異算子維持了子種群的多樣性,降低算法陷入局部最優(yōu)解的可能性；通過自適應替換算子實現了各子種群信息之間的動態(tài)協(xié)同交換,提高了子種群交互信息價值潛力和算法的搜索能力。最后,通過7個函數優(yōu)化實驗驗證了算法的有效性。4、針對并行與分布式系統(tǒng)下的可分任務調度這一實際應用問題,考慮到處理機的異構性,即處理機具有任意大小的通信速率、計算速率、計算啟動開銷和通信啟動開銷,本文以任務的最短完成時間為目標建立了一個新的優(yōu)化模型。該模型可以解決以下三個問題：確定最優(yōu)的參與計算的處理機數目、最優(yōu)的處理機調度順序,以及最優(yōu)的任務分配方案。為了有效的求解該模型,本文設計了一種新的混合遺傳算法,并證明了該算法以概率1收斂到全局最優(yōu)解。為了加快算法的收斂,在算法中引入了局部搜索策略。最后,通過仿真實驗驗證了模型和算法的有效性。
[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.

【學位授予單位】：西安電子科技大學
【學位級別】：博士
【學位授予年份】：2016
【分類號】：TP18

【相似文獻】

相關期刊論文 前10條

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

2 駱雯,孫延明,陳振威,陳錦昌;判斷點與封閉多邊形相對關系的改進算法[J];機械;1999年03期

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

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

5 林亞平,楊小林;快速概率分析進化算法及其性能研究[J];電子學報;2001年02期

6 章郡鋒;吳曉紅;黃曉強;何小海;;基于暗原色先驗去霧的改進算法[J];電視技術;2013年23期

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

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

9 吳一戎,胡東輝,彭海良;Chirp Scaling SAR成象算法及其實現[J];電子科學學刊;1995年03期

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

相關會議論文 前10條

1 尹冀鋒;;一種新的圖象自適應增強算法[A];四川省通信學會一九九二年學術年會論文集[C];1992年

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

3 謝麗聰;;SVB查詢改寫算法的改進[A];第二十一屆中國數據庫學術會議論文集（研究報告篇）[C];2004年

4 鄭存紅;;復雜背景下相關跟蹤算法研究及DSP實現[A];中國光學學會2010年光學大會論文集[C];2010年

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

6 高山;畢篤彥;魏娜;;一種基于UPF的小目標TBD算法[A];第十四屆全國圖象圖形學學術會議論文集[C];2008年

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

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

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

10 楊任爾;陳懇;勵金祥;;基于棱邊方向檢測的運動自適應去隔行算法[A];Proceedings of 2010 Chinese Control and Decision Conference[C];2010年

相關重要報紙文章 前1條

1 國泰君安資產管理部;“算法交易”是道指暴跌罪魁禍首?[N];上海證券報;2010年

相關博士學位論文 前10條

1 馮輝;網絡化的并行與分布式優(yōu)化算法研究及應用[D];復旦大學;2013年

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

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

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

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

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

7 熊霖;大數據下的數據選擇與學習算法研究[D];西安電子科技大學;2015年

8 周雷;基于圖結構的目標檢測與分割算法研究[D];上海交通大學;2014年

9 王冰;人工蜂群算法的改進及相關應用的研究[D];北京理工大學;2015年

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

相關碩士學位論文 前10條

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

2 陸進;面向含噪數據聚類相關算法的研究[D];復旦大學;2014年

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

4 王繼重;基于Hadoop和Mahout的K-Means算法設計與實現[D];大連海事大學;2016年

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

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

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

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

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

10 張媛;運動車輛檢測與跟蹤算法的研究與實現[D];大連海事大學;2016年

，

本文編號：1420672