【作者】 张敏；

【导师】 王煦法； 罗文坚；

【作者基本信息】 中国科学技术大学 ， 计算机应用技术， 2008， 博士

【摘要】 现实世界中存在大量的优化问题,特别是在科学研究和工程实践领域,而这些问题往往都带有约束条件,且有时优化问题的目标还不止一个。由于问题自身的不同特点,运筹学中的传统方法已经难以独立解决。进化算法作为一种基于群体搜索的全局优化方法,十分适合于约束优化问题和多目标优化问题的求解。因此,进化优化研究受到国内外研究者们越来越多的关注,成为目前进化计算领域的研究热点。本论文旨在通过对进化算法进行深入的探索和研究,面向单目标约束优化、多目标优化和多目标约束优化设计高效的进化算法与策略,并进行相应的理论和实验分析。具体而言,本论文的主要研究工作包括以下几个方面:(1)针对单目标约束优化,为进一步提高对可行解空间进行精确偏向搜索的能力,给出了精确偏向搜索的三个前提条件,并结合随机排序方法提出了一种新的搜索偏向选择策略,以进化策略为基础进行了算法实现。为使进化算法获得可行的全局最优解,分析了在进化过程中如何对待好的不可行解的问题,通过分析随机排序中比较概率对可行解最终位置的影响,提出了一种动态随机选择策略,并以多个体差分进化为框架进行了算法实现,然后讨论了进化过程中比较概率的调整问题。实验结果分别表明了这两种策略的有效性。(2)针对多目标优化,通过对模拟二进制交叉算子以及进化策略中的变异和重组算子的对比分析,为稳态多目标进化算法ε-MOEA设计了一种正态分布交叉算子,该算子既具有与模拟二进制交叉算子相当的开发能力,又具有更强的空间搜索能力,实验结果表明该算子明显提高了算法ε-MOEA获得的非支配解集的质量。通过分析算法ε-MOEA中参数ε与非支配解集规模之间的关系,提出了一种新的自适应调整参数ε的策略,并应用于该算法中,实验结果表明了该策略的有效性:另外,讨论了自适应调整参数ε引起的遗传漂移问题,指出了两种情形下的遗传漂移,并给出了相应的解决思路与方案。通过引入归档集合,提出了一种参数ε自适应的稳态ε-MOEA算法,并对该算法的稳态性进行了理论证明;为降低算法的计算量,通过对归档集合设置规模上限并采用先进先出的更新策略,在实验中设计了一种近似稳态算法,并进行了相应的实验比较。(3)针对多目标约束优化,为提高边界搜索能力,提出了两种在多目标差分进化中选择当前最优解的模式。为获得了分布性更好的Pareto前沿,借鉴单目标约束优化中Runarsson与Yao的搜索偏向策略,将增强边界搜索的两个模式分别应用于进化多目标约束优化的搜索过程中,提出了一种混合算法DE-MOEA求解多目标约束优化问题,并在12个常用的测试函数上进行了实验。实验结果和分析表明,与求解多目标约束优化问题的经典算法CNSGA-Ⅱ相比,混合算法DE-MOEA具有更好的性能,特别是在获得的Pareto前沿的分布性上。另外,对混合算法DE-MOEA的参数设置也进行了分析和讨论。本论文通过对进化约束优化和进化多目标优化的研究,设计了面向单目标约束优化的搜索偏向选择策略和动态随机选择策略、面向多目标优化的正态分布交叉算子和参数ε自适应调整策略及参数ε自适应的稳态ε-MOEA算法、面向多目标约束优化的混合差分进化和遗传算法的方法。这些工作不仅对进化优化的研究有着重要的意义,也对进化算法的实际优化应用有着重要的意义。更多还原

【Abstract】 It is common to face a number of optimization problems in many areas of the real world, especially in the science and engineering fields. However, these problems are often constrained, and sometimes the optimizing objective number is more than one. Because of the different features of these problems, the traditional methods in Operational Research are hard to solve these problems effectively. As robust population-based global search methods, Evolutionary Algorithms (EAs) are very promising to solve the constrained optimization problems and the multiobjective optimization problems. Therefore, the research of evolutionary optimization has received more and more attentions, and has become a hot research field in Evolutionary Computation.The aim of this dissertation is to explore the theories and mechanisms of EAs and to design effective algorithms and strategies for Single-objective Constrained Optimization, Multiobjective Optimization and Multiobjective Constrained Optimization, and to do the corresponding theoretic and experimental analyses. The main research works in this dissertation consist of the following aspects.(1) For Single-objective Constrained Optimization, in order to improve the explicit search biases ability in feasible regions, three preconditions of explicit search biases are presented, and then a novel search biases selection strategy is proposed by using stochastic ranking and is implemented within the framework of Evolution Strategy (ES). In order to effectively locate the feasible global optimum, how much attention should be paid to the promising infeasible solutions is investigated. Then with the analyses of the influence of the comparison probability in stochastic ranking on the final position of the feasible solution after ranking, a novel dynamic stochastic selection strategy is put forward within the framework of multimember differential evolution and the dynamic settings of the comparison probability are also discussed. Experimental results on common benchmark functions demonstrate the effectiveness of the two strategies, respectively.(2) For Multiobjective Optimization, by the comparisons and analyses of the simulated binary crossover (SBX) and mutation operator in ES, a novel normal distribution crossover (NDX) is designed for the steady-state multiobjective evolutionary algorithm (MOEA)ε-MOEA with the introduction of discrete recombination operator in ES. So the NDX not only has the equal exploitation ability with the SBX, but also has more effective exploration ability. And the experimental results show that the NDX significantly improve the quality of the obtained non-dominated solutions by the algorithmε-MOEA. Based on the analyses of the relationship between the value of the parameterεand the maximum number of the non-dominated solutions, a novel self-adaption strategy for the parameterεinε-MOEA is proposed. Then this novel strategy is applied in the algorithmε-MOEA, and the experimental results on 10 benchmark functions demonstrate that even if without the good initial value for the parameterε, the algorithm is able to approximately obtain the expected number of non-dominated solutions, which are very close to and uniformly distributed on the Pareto-optimal front. Furthermore, the genetic drift phenomenon arose by the self-adaption strategy is discussed. Two cases of genetic drifts are pointed out, and the (possible) corresponding solutions are provided. By the introduction of the archive set, a steady-stateε-MOEA with the self-adaption of the parameterεis proposed and the steady-sate characteristic is also proved theoretically. In order to reduce the computational amount, an approximate steady state algorithm is designed in the experiments by setting the upper limit and adopting the FIFO (First In, First Out) updating strategy for the archive set, and the comparison experiments on common test functions are also done.(3) For Multiobjective Constrained Optimization, in order to enhance the boundary search ability, two schemes of selecting the current best solutions for multiobjective differential evolution are proposed. And in order to obtain more complete Pareto front, a hybrid approach named DE-MOEA based on genetic algorithm and multiobjective differential evolution is given within the (N+N) framework by the reference of the search biases strategy suggested by Runarsson and Yao, i.e., the two schemes are used in the evolutionary multiobjective constrained optimization. Then the hybrid algorithm DE-MOEA is compared with the current state-of-the-art algorithm CNSGA-II on 12 common test functions, and the experimental results show that the hybrid algorithm has better performance, especially in the distribution of the obtained Pareto front. In addition, the parameter settings in the hybrid algorithm DE-MOEA are also analyzed and discussed.In this dissertation, with the studies in evolutionary constrained optimization and evolutionary multiobjective optimization, a novel search biases selection strategy and a novel dynamic stochastic selection strategy are designed for Single-objective Constrained Optimization, a novel normal distribution crossover, a novel self-adaption strategy for the parameterεand a steady-stateε-MOEA with the self-adaption of the parameterεare proposed for Multiobjective Optimization, and a hybrid algorithm based on genetic algorithm and multiobjective differential evolution is suggested for Multiobjective constrained optimization. The works in this dissertation are very important to the research of the evolutionary optimization and the optimization applications of EAs in the real world.更多还原