【作者】 慕彩红；

【导师】 焦李成；

【作者基本信息】 西安电子科技大学 ， 电路与系统， 2010， 博士

【摘要】 协同进化是自然界的一种普遍现象。当两个或更多个种群之间的进化相互影响时,就出现了协同进化,它通常被用来解释种群间的相互适应现象。生物学研究表明协同进化对于生物进化是有益的。协同进化算法是将协同进化机制引入传统进化算法而产生的一类进化算法的衍生算法。近年来,使用协同进化算法求解优化问题已成为进化计算研究领域的一个重要方向。本文主要进行协同进化算法的研究,包括建立协同进化模型、设计协同进化算法和进行协同进化算法的应用研究。本文在归纳总结现有协同进化算法的基础上将协同进化算法进行分类,并对各类协同进化算法的研究进展进行了综述。之后,本文针对包括无约束优化、约束优化以及多目标优化在内的数值优化问题提出了新的协同进化模型以及若干新的算法和策略,并将这些新算法应用于通信信号的检测问题和以卫星模块布局设计为背景的带平衡约束的圆形布局问题。本文的主要工作可概括如下:(1)借鉴协同进化和精英策略的思想,提出了解决高维无约束数值优化问题的M-精英协同进化模型和M-精英协同进化算法(M-Elite Coevolutionary Algorithm,MECA)。MECA算法认为适应度较高的个体群(称为精英种群),在整个种群进化中起着主导作用。算法将整个种群划分为由M个精英组成的精英种群和由其余个体组成的普通种群这样两个子种群,依次以M个精英为核心(称为核心精英)来选择成员以组建M个团队。若选中的团队成员是其他精英,则该成员与核心精英利用所定义的协作操作来交换信息;若团队成员选自普通种群,则由核心精英对其进行引导操作。其中,协作操作和引导操作由若干不同类型的交叉或变异算子的组合所定义。理论分析证明,算法以概率1收敛于全局最优解。对15个标准测试函数的测试结果显示,该算法对其中几乎所有测试函数都能够找到最优解或好的次优解。与两种经典的传统进化算法以及三种其他协同进化算法相比,在适应度函数评价次数相同时,该算法所求解的精度更高。同时,该算法的寻优时间较短,甚至略短于同等设置下的标准遗传算法。此外,对参数的实验分析结果显示,该算法对参数不敏感,易于使用。(2)改进M-精英协同进化算法并将其扩展应用于约束优化问题。以M-精英协同进化模型为基础,引入正交交叉算子,并使用静态罚函数法处理约束,研究了M-精英协同进化算法在约束优化问题中的应用。利用13个约束优化测试函数对算法进行了测试,仿真实验和参数分析结果表明该算法寻优精度高,寻优时间少,算法稳定,其性能优于一些经典的约束优化进化算法,也优于所对比的协同进化算法,能够有效解决复杂的约束优化问题。(3)在M-精英协同进化的框架下引入非支配近邻选择机制,提出了非支配近邻协同进化多目标优化算法(Nondominated Neighbor Coevolutionary Algorithm,NNCA)。将非支配种群根据拥挤距离的大小分为精英种群和普通种群,其中精英种群由nE个具有较大拥挤距离值的非支配个体组成。其所处区域个体分布越稀疏的精英个体,越有机会选择更多成员来组建团队,从而实现对其所在区域的更加充分的搜索。为避免当非支配个体过少时算法陷入因非支配近邻选择机制引起的“搜索停滞”状态,NNCA采用精英规模保障机制,即当精英种群实际规模达不到nE时,从由被支配个体构成的备选种群中随机选择若干个备选个体迁移至精英种群中,使精英种群规模达到nE,从而避免算法在当前非支配个体过少时仅围绕有限的几个非支配个体进行搜索以至陷入“搜索停滞”状态。协同进化机制、非支配近邻选择机制和强调精英种群作用的思想相结合,使得算法具有较好的搜索能力和较强的收敛性。关于13个多目标优化测试问题的实验分析结果表明,与NSGA-II、SPEA2以及NNIA等优秀多目标优化进化算法相比,NNCA得到的Pareto最优解在逼近性和宽广性方面具有比较明显的优势,而均匀性也仅次于SPEA2,优于NSGA-II和NNIA。(4)为解决垂直分层空时系统中的最大似然(Maximum-Likelihood,ML)检测算法复杂度过高的问题,并针对通信系统对实时性要求较高的特点,设计了一种复杂度较低且性能优良的算法,即M-精英进化算法(M-elite Evolutionary Algorithm,MEA),并将其应用于垂直分层空时系统的信号检测,来逼近ML检测算法的性能。通过一个经典背包问题的仿真验证了MEA求解组合优化问题的有效性,实际的通信系统仿真表明基于MEA的检测算法的性能优于一些经典的检测算法,也优于基于标准遗传算法及克隆选择算法的检测算法,能够较好地逼近ML检测算法的性能。(5)将M-精英协同进化算法扩展应用于求解带平衡约束的圆形Packing问题,该问题以卫星模块布局设计为背景,属于NP难问题。通过使用静态罚函数方法将约束Packing问题转化为无约束优化问题来求解。首先利用Welded Beam Design、Spring Design、Speed Reducer Design和Three-Bar Truss Design这4个工程设计优化问题验证了MECA解决实际工程问题的能力,之后对3个带平衡约束的圆形Packing问题的典型算例进行了测试,结果显示M-精英协同进化算法以较少的时间代价获得了质量较高的布局结果,能够解决复杂的约束Packing问题。更多还原

【Abstract】 Coevolution is a universal phenomenon in the nature. Coevolution happens when two or more species influence each other’s evolution and it is most often invoked to explain coadaptations between species. The biological study shows that coevolution is beneficial to biological evolution. A Coevolutionary Algorithm (CEA), which employs the coevolutionary mechanism within a classical evolutionary algorithm (EA), is an extension to EAs. Solving optimization problems with CEAs has become an important research area of evolutionary computation in recent years. This dissertation is focused on the research of CEA, including the coevolutionary model building, coevolutionary algorithm design and its applications. Firstly, CEAs are categorized based on the induction of the existing CEAs and then the state-of-the-art of CEAs is surveyed. After that, a new coevolutionary model and several new algorithms and strategies are proposed for numerical optimization including unconstrained optimization, constrained optimization and multiobjective optimization. Afterwards, the new algorithms are applied to the detection of communication signals and the equilibrium-constrained circles packing problem with the background of satellite module layout design. The main innovative points of this dissertation can be summarized as follows:(1) The M-elite coevolutionary model and the M-Elite Coevolutionary Algorithm (MECA) are proposed for high-dimensional unconstrained numerical optimization problems based on the concept of coevolutionary algorithm and elitist strategy. In the MECA, the individuals with high fitness, called elite population, are considered to play dominant roles in the evolutionary process. The whole population is divided into two subpopulations which are elite population composed of M elites and common population including other individuals, and team members are selected to form M teams by M elites acting as the cores of the M teams (named as core elites) respectively. If the team member selected is another elite individual, it will exchange information with the core elite by the cooperative operation defined in the paper; If the team member is chosen from the common population, it will be led by the core elite with the leading operation. The cooperative and leading operation above are defined by different combinations of several crossover operators or mutation operators. The algorithm is proved to converge to the global optimization solution with probability one. Tests on 15 benchmark problems show that the algorithm can find the global optimal solution or near-optimal solution for most problems tested. Compared with two classical EAs and three CEAs, MECA achieves an improved accuracy with the same number of function evaluations. Meanwhile, the runtime of MECA is less, even compared with the standard genetic algorithm with the same parameter setting. Moreover, the parameters of the MECA are analyzed in experiments and the results show that MECA is insensitive to parameters and easy to use.(2) The M-Elite Coevolutionary Algorithm (MECA) is improved and extended to solve constrained optimization problems. The orthogonal crossover operator is introduced into MECA to improve the algorithm performance and static penalty functions are used to handle constraints. Tests are made on 13 benchmark problems. The experimental results and the parameter analysis show that the MECA can obtain high solution quality with less runtime and is robust and it obtains better performances than some classical constrained optimization evolutionary algorithms as well as another coevolutionary algorithm, and can solve difficult constrained optimization problem.(3) The Nondominated Neighbor Coevolutionary Algorithm (NNCA) is proposed for multiobjective optimization by introducing the nondominated neighbor selection (NNS) mechanism to the M-elite coevolutionary frame. The whole nondominated population is divided into two subpopulations which are elite population and common population according to the crowding-distance values, where elite population is composed of nE nondominated individuals with higher crowding-distance values. The elite individual located in less-crowded region will have more chances to select more members for its own group and thus this region can be explored more sufficiently. A Size Guarantee Mechanism (SGM) for elite population is proposed so as to avoid the‘search stagnation’situation due to the NNS mechanism when the nondominated individuals are too few. The SGM is realized in such a way: as the actual size of elite population is smaller than nE, several dominated individuals, which are selected from the reserved population composed of dominated individuals, will emigrate to the elite population to ensure that the size of elite population is equal to nE. The SGM can prevent the algorithm searching around limited nondominated individuals and trapping into the‘search stagnation’situation. The combination of coevolutionary mechanism, NNS mechanism and the idea of emphasizing the role of elite population make the NNCA obtain good search capability and convergence performance. Tests on 13 multiobjective optimization benchmark problems show that NNCA does much better than other excellent multiobjective optimization evolutionary algorithm including NSGA-II, SPEA2 and NNIA in terms of the approximation property and the extent property. Meanwhile, except SPEA2, NNCA does best in terms of diversity maintenance.(4) A new algorithm named as M-elite Evolutionary Algorithm (MEA) is presented with low complexity and high performance to approach the performance of Maximum-Likelihood (ML) detection, for solving the problem of the high complexity of ML detection in real-time Vertical-Bell laboratories LAyered Space-Time (V-BLAST) communication system. The simulation of one knapsack problem validates the effectiveness of MEA to solve combinatorial optimization problems. Furthermore, the simulation of V-BLAST communication system shows that the MEA-based detection algorithm can approach the performance of ML well, and is superior to the detection algorithms based on standard genetic algorithm and that based on clonal selection algorithm as well as some classical ones.(5) The M-Elite Coevolutionary Algorithm (MECA) is extended to the equilibrium-constrained circles packing problem with the background of satellite module layout design, which belongs to NP-hard problem. Static penalty functions are used to transform a constrained packing problem into an unconstrained one. Firstly, four engineering design problems including Welded Beam Design, Spring Design, Speed Reducer Design and Three-Bar Truss Design are used to validate the effectiveness of MECA for practical engineering optimization. Then tests are made on 3 equilibrium-constrained circles packing problems and the experimental results show that the MECA can obtain high quality solution with less runtime, and can solve difficult constrained packing problems.更多还原