基于路径链接技术的多目标优化算法研究

发布时间：2018-05-14 02:01

本文选题：多目标优化 + 超体积指标函数　；参考：《电子科技大学》2017年硕士论文

【摘要】：在实际的生产生活中,很多问题都需要使多个目标在给定的约束前提下尽可能达到最优,这种问题就是多目标优化问题。近二十年来,这类问题越来越受到学者的关注,同时这也是一类在实际生产生活中广泛存在的问题。比如,在工业生产中,生产调度是生产管理的核心问题,也是现代计算机集成制造系统的关键技术,其以生产进度计划为依据,在现有生产设备、工艺条件和能力的约束下,对有限的生产资源在时间和空间上进行调度和规划,从而确认生产路线,同时实现最小化总完成时间、最小化总流程时间、最小化总延迟时间等多个生产目标。大部分的多目标优化问题都是NP-难问题,一般精确算法并不能在多项式时间内求解这些问题。为了有效的求解这类问题,大量的元启发式算法被提出。例如遗传算法、禁忌搜索、蚁群算法等等。在本文中我们将使用路径链接技术求解多目标优化问题,路径链接技术就是通过在两个高质量的解之间建立路径来产生新的个体。本文的工作就是将路径链接技术和基于超体积的多目标局部搜索算法相结合,提出一个基于路径链接的多目标优化算法框架。并将该框架算法应用于双目标无约束二元二次规划问题、双目标二次分配问题、双目标最大割问题。在传统的多目标优化算法大多是基于局部空间的搜索的情况下,如何有效的跳出局部空间的限制,并高效的生成具有搜索潜力的个体往往是决定算法表现的关键,本文将主要研究基于路径链接技术的多目标优化算法。本文的主要研究工作如下:1)把路径链接技术与基于超体积的局部搜索算法相结合,并给出一个基于路径链接和超体积的多目标优化算法框架。其中基于超体积的局部搜索算法对每个个体分配基于超体积贡献的适应值,然后进行个体淘汰,该适应值能够有效的评估解的质量,并能明显提高群体的多样性和最后解的质量。2)在给出的基于路径链接和超体积的多目标优化算法框架的基础上,本文选取无约束二元二次规划问题,二次分配问题和最大割问题作为应用对象,这三个问题分别代表了解的表示为二进制串、排列和集合这三种问题类型。本文并将对如何定义这些问题的解之间的距离及如何对其中特定的问题进行路径链接进行研究,并将给出具体的距离定义方案和路径链接过程。3)最后将在双目标无约束二元二次规划问题,双目标二次分配问题和双目标最大割问题上进行对比试验,试验算法是基于路径链接和超体积的多目标优化算法框架,并且结合了相应问题解的距离的定义和路径链接的方法。最后将对结果进行分析比较,并将对基于路径链接和超体积的多目标优化算法框架的有效性和高效性进行分析。
[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

【参考文献】