本文選題：多目標優(yōu)化 + 超體積指標函數(shù)��； 參考：《電子科技大學》2017年碩士論文

【摘要】：在實際的生產(chǎn)生活中,很多問題都需要使多個目標在給定的約束前提下盡可能達到最優(yōu),這種問題就是多目標優(yōu)化問題。近二十年來,這類問題越來越受到學者的關(guān)注,同時這也是一類在實際生產(chǎn)生活中廣泛存在的問題。比如,在工業(yè)生產(chǎn)中,生產(chǎn)調(diào)度是生產(chǎn)管理的核心問題,也是現(xiàn)代計算機集成制造系統(tǒng)的關(guān)鍵技術(shù),其以生產(chǎn)進度計劃為依據(jù),在現(xiàn)有生產(chǎn)設(shè)備、工藝條件和能力的約束下,對有限的生產(chǎn)資源在時間和空間上進行調(diào)度和規(guī)劃,從而確認生產(chǎn)路線,同時實現(xiàn)最小化總完成時間、最小化總流程時間、最小化總延遲時間等多個生產(chǎn)目標。大部分的多目標優(yōu)化問題都是NP-難問題,一般精確算法并不能在多項式時間內(nèi)求解這些問題。為了有效的求解這類問題,大量的元啟發(fā)式算法被提出。例如遺傳算法、禁忌搜索、蟻群算法等等。在本文中我們將使用路徑鏈接技術(shù)求解多目標優(yōu)化問題,路徑鏈接技術(shù)就是通過在兩個高質(zhì)量的解之間建立路徑來產(chǎn)生新的個體。本文的工作就是將路徑鏈接技術(shù)和基于超體積的多目標局部搜索算法相結(jié)合,提出一個基于路徑鏈接的多目標優(yōu)化算法框架。并將該框架算法應(yīng)用于雙目標無約束二元二次規(guī)劃問題、雙目標二次分配問題、雙目標最大割問題。在傳統(tǒng)的多目標優(yōu)化算法大多是基于局部空間的搜索的情況下,如何有效的跳出局部空間的限制,并高效的生成具有搜索潛力的個體往往是決定算法表現(xiàn)的關(guān)鍵,本文將主要研究基于路徑鏈接技術(shù)的多目標優(yōu)化算法。本文的主要研究工作如下:1)把路徑鏈接技術(shù)與基于超體積的局部搜索算法相結(jié)合,并給出一個基于路徑鏈接和超體積的多目標優(yōu)化算法框架。其中基于超體積的局部搜索算法對每個個體分配基于超體積貢獻的適應(yīng)值,然后進行個體淘汰,該適應(yīng)值能夠有效的評估解的質(zhì)量,并能明顯提高群體的多樣性和最后解的質(zhì)量。2)在給出的基于路徑鏈接和超體積的多目標優(yōu)化算法框架的基礎(chǔ)上,本文選取無約束二元二次規(guī)劃問題,二次分配問題和最大割問題作為應(yīng)用對象,這三個問題分別代表了解的表示為二進制串、排列和集合這三種問題類型。本文并將對如何定義這些問題的解之間的距離及如何對其中特定的問題進行路徑鏈接進行研究,并將給出具體的距離定義方案和路徑鏈接過程。3)最后將在雙目標無約束二元二次規(guī)劃問題,雙目標二次分配問題和雙目標最大割問題上進行對比試驗,試驗算法是基于路徑鏈接和超體積的多目標優(yōu)化算法框架,并且結(jié)合了相應(yīng)問題解的距離的定義和路徑鏈接的方法。最后將對結(jié)果進行分析比較,并將對基于路徑鏈接和超體積的多目標優(yōu)化算法框架的有效性和高效性進行分析。
[Abstract]:In practical production and life, many problems need to make multiple objectives as best as possible under given constraints. This kind of problem is called multi-objective optimization problem. In the past two decades, more and more scholars have paid attention to this kind of problem, which is also a widespread problem in practical production and life. For example, in industrial production, production scheduling is the core problem of production management and the key technology of modern computer integrated manufacturing system. It is based on production schedule, under the constraints of existing production equipment, process conditions and capabilities. The limited production resources are scheduled and planned in time and space to confirm the production route, and to minimize the total completion time, the total process time, the total delay time and so on. Most multiobjective optimization problems are NP-hard problems, and the general exact algorithm can not solve these problems in polynomial time. In order to solve this kind of problem effectively, a large number of meta-heuristic algorithms are proposed. For example, genetic algorithm, Tabu search, ant colony algorithm and so on. In this paper, we will use the path linking technique to solve the multi-objective optimization problem, which is to create new individuals by establishing a path between two high-quality solutions. The work of this paper is to combine the path linking technology with the hypervolume based multi-objective local search algorithm and propose a multi-objective optimization algorithm framework based on path link. The framework algorithm is applied to the bi-objective unconstrained binary quadratic programming problem, the double-objective quadratic assignment problem and the double-objective maximum cut problem. In the traditional multi-objective optimization algorithm is mostly based on the search of local space, how to effectively jump out of the limitations of local space, and efficient generation of individuals with search potential is often the key to determine the performance of the algorithm. In this paper, we will mainly study the multi-objective optimization algorithm based on path linking technology. The main research work of this paper is as follows: (1) combining the path linking technique with the local search algorithm based on hypervolume, a multi-objective optimization algorithm based on path link and hypervolume is proposed. The local search algorithm based on hypervolume assigns the adaptive value based on the hypervolume contribution to each individual, and then eliminates the individual, which can effectively evaluate the quality of the solution. And can obviously improve the diversity of the population and the quality of the final solution.) on the basis of the proposed multi-objective optimization algorithm based on path link and hypervolume, the unconstrained binary quadratic programming problem is selected in this paper. The quadratic assignment problem and the maximum cut problem are applied objects. These three problems represent the representation of the solution as binary string, arrangement and set respectively. This paper will also study how to define the distance between the solutions of these problems and how to link the path to a particular problem. The specific distance definition scheme and path linking process. 3) will be compared with the two objective unconstrained binary quadratic programming problem, the double objective quadratic assignment problem and the double objective maximum cut problem, in the end, a comparison experiment will be carried out on the double objective unconstrained binary quadratic programming problem, the double objective quadratic assignment problem and the double objective maximum cut problem. The experimental algorithm is a multi-objective optimization framework based on path link and hypervolume, and combines the definition of the distance of solution and the method of path link. Finally, the results are analyzed and compared, and the effectiveness and efficiency of the multi-objective optimization framework based on path link and hypervolume are analyzed.
【學位授予單位】：電子科技大學
【學位級別】：碩士
【學位授予年份】：2017
【分類號】：TP18

【參考文獻】

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

1 公茂果;焦李成;楊咚咚;馬文萍;;進化多目標優(yōu)化算法研究[J];軟件學報;2009年02期

2 尚榮華;焦李成;公茂果;馬文萍;;免疫克隆算法求解動態(tài)多目標優(yōu)化問題[J];軟件學報;2007年11期

3 石川;李清勇;史忠植;;一種快速的基于占優(yōu)樹的多目標進化算法[J];軟件學報;2007年03期

4 崔遜學,林闖;一種基于偏好的多目標調(diào)和遺傳算法(英文)[J];軟件學報;2005年05期

5 周育人,李元香,王勇,康立山;Pareto強度值演化算法求解約束優(yōu)化問題[J];軟件學報;2003年07期

相關(guān)博士學位論文 前1條

1 謝承旺;高維目標空間中的進化算法研究[D];武漢大學;2010年

，

本文編號：1885808