【作者】 李丽荣；

【导师】 郑金华；

【作者基本信息】 湘潭大学 ， 计算机应用技术， 2003， 硕士

【摘要】 遗传算法是模拟达尔文的遗传选择和自然淘汰的生物进化过程的一种新的迭代的全局优化搜索算法，已经广泛地应用到组合优化问题求解、自适应控制、规划设计、机器学习和人工生命等领域。由于现实世界中存在的问题往往呈现为多目标属性，而且需要优化的多个目标之间又是相互冲突的，从而多目标遗传算法应运而生，它使得进化群体并行搜寻多个目标，并逐渐找到问题的最优解。本文对近十五年来多目标遗传算法的国内外研究现状进行了较全面地阐述，其优化方法大致分为两大类：带参数的方法和不带参数的方法。带参数的方法主要存在着参数难以选择及过于依赖参数的选择等问题，不带参数的方法主要存在着速度比较慢的问题。为此，本文的研究主要就是从提高寻找非支配集的速度，在保持群体原有特性的前提下降低非支配集的大小，以及新群体的构造等方面入手，通过基于分类和聚类的方法，有效提高多目标遗传算法总体运行效率，降低其计算复杂性，使多目标遗传算法的收敛性能得到进一步改善。该文以NSGA-Ⅱ为基准，对算法进行了改进，具体提出了：用排除法构造非支配集、用聚集距离刻画个体间的内部关系以及构造新群体，来提高运行速度和保持群体的多样性；用聚类算法在保持原有特性的前提下，进一步改善收敛性能等。比较试验结果表明，基于分类和聚类的多目标遗传算法，在运行效率与保持群体多样性等方面取得了较好效果。更多还原

【Abstract】 Genetic Algorithm (GA) is a set of new-global-optimistic search algorithm repeatedly which simulate the process of creature evolution that of Darwinian’s genetic selection and natural elimination. It is widely applied to the domain of combinational evolutionary problem seeking, self-adapt controlling, planning devising, machine learning and artificial life etc. However, there are multi-objective attributes in real-world optimization problems that always conflict, so the multi-objective Genetic Algorithm (MOGA) is put forward. MOGA can deal simultaneously with many objections, and find gradually Pareto-optimal solutions.This paper presents a critical review of MOGA’ current researches mainly in the last 15 years. The multi-objective optimization techniques have two branches, one with parameters and another with no parameters. It’s difficult for us to select parameters in the methods with parameters and its performance is highly dependent on an appropriate selection of the sharing factor. In addition, the work speed is very low in the methods with no parameters. Therefore, we focus on proceeding the algorithm’s performance with increasing the speed of searching non-dominated solutions, reducing the number of non-dominated solutions in precondition of ensuring a better distribution of individuals, and constructing new populations. The multi-objective Genetic Algorithm based on sorting and clustering efficiently increase its run efficiency, debase its compute complexity and improve its convergence performance. In this paper, we takeNSGA-II as a benchmark. It has been improved, and specially proposed: Firstly, we has increased run speed and ensure the diversity of population is with constructing non-dominated set by throwing off the dominated solutions, expressing the interior relation of individuals each other by the crowding distance, and constructing new population. Secondly, we have further improved its convergence performance by clustering in precondition of ensuring a better distribution of individuals. Simulation results on six difficult optimization problems show that the multi-objective Genetic Algorithm based on sorting and clustering have ideal effects on the aspects of its speed and diversify.更多还原