约束优化进化算法

约束优化问题是科学和工程应用领域经常会遇到的一类数学规划问题.近年来,约束优化问题求解已成为进化计算研究的一个重要方向.从约束优化进化算法=约束处理技术+进化算法的研究框架出发,从约束处理技术和进化算法两个基本方面对约束优化进化算法的研究及进展进行了综述.此外,对约束优化进化算法中的一些重要问题进行了探讨.最后进行了各种算法的比较性总结,深入分析了目前约束优化进化算法中亟待解决的问题,并指出了值得进一步研究的方向.     

约束优化进化算法综述

约束优化进化算法主要研究如何利用进化计算方法求解约束优化问题,是进化计算领城的一个重要研究课题.约束优化问题求解存在约束区域离散、等式约束、非线性约束等挑战,其问题的本质是如何处理可行解与不可行解的关系才能使得算法更高效.本文首先介绍了约束优化问题的定义,然后系统地分析了目前存在的约束优化方法,同时基于约束处理机制将这些方法分为罚函数法、可行性法则、随机排序法、约束处理法、多目标优化法、混合法六类,并从约束处理方法的方面对约束优化进化算法的最新研究进展进行综述.最后,指出约束优化进化算法需进一步研究的方向与关键问题.     

Evolutionary design of Evolutionary Algorithms

Manual design of Evolutionary Algorithms (EAs) capable of performing very well on a wide range of problems is a difficult task. This is why we have to find other manners to construct algorithms that perform very well on some problems. One possibility (which is explored in this paper) is to let the evolution discover the optimal structure and parameters of the EA used for solving a specific problem. To this end a new model for automatic generation of EAs by evolutionary means is proposed here. The model is based on a simple Genetic Algorithm (GA). Every GA chromosome encodes an EA, which is used for solving a particular problem. Several Evolutionary Algorithms for function optimization are generated by using the considered model. Numerical experiments show that the EAs perform similarly and sometimes even better than standard approaches for several well-known benchmarking problems.     

演化算法的时间复杂性

演化算法在工程领域取得了广泛的应用,但是其基础理论尚未完全建立。文章讨论了演化算法的时间复杂性,提出一个估计(1+1)EA平均计算时间的简单方法,对几个实例的应用显示了该方法分析演化算法计算时间的有效性。     

采用混沌变异的进化算法

根据混沌理论关于进化与混沌的关系,设计一种采用混沌变异算子的进化算法,并提出“尺度收缩”的变异策略。对极小值函数优化问题的仿真实例表明,混沌变异是实数编码进化算法变异算子的有效实现;而采用“尺度收缩”策略的混沌变异算子明显改善了群体平均适应值,提高了算法性能,是解决优化问题的有效方法。     

Evolving Evolutionary Algorithms with Patterns

A new model for evolving evolutionary algorithms (EAs) is proposed in this paper. The model is based on the multi expression programming (MEP) technique. Each MEP chromosome encodes an evolutionary pattern which is repeatedly used for generating the individuals of a new generation. The evolved pattern is embedded into a standard evolutionary scheme which is used for solving a particular problem. Several evolutionary algorithms for function optimization are evolved by using the considered model. The evolved evolutionary algorithms are compared with a human-designed genetic algorithm. Numerical experiments show that the evolved evolutionary algorithms can compete with standard approaches for several well-known benchmarking problems.     

一种进化算法的应用研究

该文对丛式井组井口定位进行了研究。丛式井就是由同一井场出发打多口井,它可以发挥井场的最大作用,节约用地,提高经济效益。这样如何选择最优点进行打井就成为了一个关键问题。这个问题可以抽象为一个求平面多边形内最优点的问题。该文推导了较有价值的求解本问题最优解的算法,包括目前采用的经验法和基本的穷举法。该文在较新的进化策略算法方面做了一些改进,达到更好的效果。通过实例验证,进化策略算法较以往通常采用的算法有优势。     

演化算法的收敛速率与效率分析

该文讨论了演化算法的收敛速度与效率问题．引入了衡量演化算法收敛快慢的新标准——收敛阶和收敛因子等概念,使用顺序统计方法讨论了收敛阶和收敛因子的计算问题．考虑到演化算法的收敛速度和每代群体的工作量,用收敛阶(或收敛因子)和函数评价次数定义了演化算法的效率．对于常见的球函数模型．推导出(μ,λ)演化策略收敛因子和效率公式．从理论上分析了(μ,λ)演化策略中参数μ,λ的最佳比值．     

多目标进化算法中多样性策略的研究

进化多目标优化中由于进化算子固有的随机误差以及进化过程中选择压力和选择噪音的影响使得进化群体容易丧失多样性,而保持进化群体的多样性不仅有利于进化群体搜索,而且也是多目标优化的重要目标。对多目标进化算法的多样性策略进行了分类,在统一的框架下描述了各种策略的机制,并分析了各自的特性。随后,分析并比较了多样性保持算子的复杂度。最后,证明了一般意义下多目标进化算法的收敛性,指出在设计新的多样性策略中需要保证进化世代间的单调性,避免出现退化现象。     

一种基于遗传算法与进化编程的系统辨识方法

分析比较了遗传算法（GA）和进化编码（EP）在解决系统辨识问题中的优劣，提出一种将GA和EP相结合的新的系统辨识方法，该方法既不依赖于种群的初始值，又具有较强的稳定性。仿真结果表明了该方法的有效性和独到之处。     

基于演化算法的全加器优化设计

演化硬件研究工作中的一个重要研究内容就是电路优化设计,电路优化设计有望实现复杂电路的自动设计并获得新颖、优化的设计结果,因而成为国际性的研究热点。将演化算法引入全加器电路的优化设计中,引入了新的个体评估机制并提出了适用于全加器演化的演化算法。通过仿真实验验证了算法的有效性。     

进化算法中的模式定理及建筑块

探讨了进化算法中的模式定理及建筑块理论．通过引入模式进化、模式进化能力、适度模式等概念，以标准遗传算法为例，证明了在变异算子独立的条件下，进化算法中模式的构成与多点交叉和变异的顺序无关，然后证明了具有强进化能力的模式，将以指数阶增长．该文的模式理论有别于Holland等人提出的模式理论，特别是在交叉算子上采用了多点交叉算子，给出了相应的公式；并从这一推导过程论证了建筑块假设的合理性，可以称之为建筑块理论．     

优化设计中的多目标进化算法

近十多年来多目标进化算法是人工智能领域的一个相当活跃的研究热点。该文从非Pareto方法、基于Pareto方法及贝叶斯多目标优化算法等角度对当今多目标进化算法进行了分析,归纳了新出现的各种方法和技术,探讨了这个领域发展中存在的问题,并进一步给出了发展方向。此外文中分别对后两类提出了解决一般问题的计算效果较好的改进算法和新的算法。     

Evolutionary Algorithms for Multi-Objective Optimization: Performance Assessments and Comparisons

Evolutionary techniques for multi-objective(MO) optimization are currently gainingsignificant attention from researchers invarious fields due to their effectiveness androbustness in searching for a set of trade-offsolutions. Unlike conventional methods thataggregate multiple attributes to form acomposite scalar objective function,evolutionary algorithms with modifiedreproduction schemes for MO optimization arecapable of treating each objective componentseparately and lead the search in discoveringthe global Pareto-optimal front. The rapidadvances of multi-objective evolutionaryalgorithms, however, poses the difficulty ofkeeping track of the developments in this fieldas well as selecting an existing approach thatbest suits the optimization problem in-hand.This paper thus provides a survey on variousevolutionary methods for MO optimization. Manywell-known multi-objective evolutionaryalgorithms have been experimented with andcompared extensively on four benchmark problemswith different MO optimization difficulties.Besides considering the usual performancemeasures in MO optimization, e.g., the spreadacross the Pareto-optimal front and the abilityto attain the global trade-offs, the paper alsopresents a few metrics to examinethe strength and weakness of each evolutionaryapproach both quantitatively and qualitatively.Simulation results for the comparisons areanalyzed, summarized and commented.     

演化算法时间复杂性的趋势条件

计算时间复杂性是演化理论中的一个重大课题.将趋势分析引入演化算法的平均时间复杂性分析,可用于很广一类演化算法及许多问题.基于趋势分析,研究了确定演化算法时间复杂性的一些有用的趋势条件.这些条件应用于完全欺骗问题以验证其有效性.     

多目标进化算法测试问题的设计与分析

为了有效检测多目标优化进化算法的性能,从3个方面进行多目标优化测试问题的设计,即约束条件、最优解分布的均匀性、算法逼近Pareto最优前沿的难度,采用NSGA-Ⅱ算法对这些测试问题进行仿真实验,并将算法求得的最优解可视化。结果显示,测试问题能够有效检测算法在上述3方面的性能。     

多目标进化算法中选择策略的研究

在多目标进化算法(multiobjective evolutiorlsry algorithms,MOEAs)的文献中,对算法的选择策略进行系统研究的还很少,而MOEAs的选择策略不仅引导算法的搜索过程、决定搜索的方向而且对算法的收敛性有重要的影响,它是算法能否成功求解多目标优化问题的关键因素之一.在统一的框架下,首先讨论了多目标优化问题中适应度函数的构造问题,然后根据MOEAs的选择机制和原理将它们的选择策略重新分成了6种类型.一般文献中很少对多目标进化算法的操作算子采用符号化描述,这样不利于对算子的深层次理解,符号化描述了各类选择策略的操作机制和原理,并分析了各类策略的优劣性.最后,从理论上证明了具备一定特征的多目标进化算法的收敛性,证明的过程表明了将算法运行终止时得到的P known作为多目标优化问题的Pareto最优解集或近似最优解集的合理性.     

进化算法在复杂网络中的应用综述

复杂网络作为现今科学研究中的一个热点学科,在过去20年里得到了巨大的发展.现实中大量的复杂的交互系统,比如互联网、交通运输网、神经网络等都可以抽象为复杂网络,以进行系统的分析和研究.进化算法作为优化工具应用于复杂网络的不同领域的各个任务中,如网络社团结构的检测任务、网络动力学中的鲁棒性优化任务、网络传播中关键节点的搜寻任务等.本文首先对复杂网络和进化算法相关的基础知识进行了全面的概述,重点讨论了复杂网络中目标优化的研究进展,针对不同任务对优化目标及其具体应用展开了详细介绍,同时,对算法的性能评价指标进行了概述.此外,本文通过一系列实验展示了单/多目标优化算法在复杂网络优化问题上的性能表现,以及部分目标之间的相关性关系.最后对复杂网络中优化问题未来的研究动向进行了展望,为今后研究人员开展进化计算和复杂网络相结合的相关研究提供一些思路.     

混合量子进化算法及其应用

文章将量子进化算法(QEA)和粒子群算法(PSO)互相结合,提出了两种混合量子进化算法。第一种算法叫做嵌入式粒子群量子进化算法,其主要思想是将简化的PSO进化方程嵌入QEA的进化操作中,简化了QEA算法的结构,增强了QEA跳出局部极值的能力。第二种算法叫做量子二进制粒子群算法,其主要思想是将QEA中的量子染色体的概念引入二进制粒子群算法(BPSO),提高了BPSO算法保持种群多样性的能力和运算速度。通过对0-1背包问题和多用户检测问题的求解表明,新的算法不仅操作更简单,而且全局搜索能力有了显著的提高。     

Single and Multi-objective Evolutionary Algorithms for the Coordination of Serial Manufacturing Operations

This paper focuses on a typical problem arising in serial production, where two consecutive departments must sequence their internal work, each taking into account the requirements of the other one. Even if the considered problem is inherently multi-objective, to date the only heuristic approaches dealing with this problem use single-objective formulations, and also require specific assumptions on the objective function, leaving the most general case of the problem open for innovative approaches. In this paper, we develop and compare three evolutionary algorithms for dealing with such a type of combinatorial problems. Two algorithms are designed to perform directed search by aggregating the objectives of each department in a single fitness, while a third one is designed to search for the Pareto front of non-dominated solutions. We apply the three algorithms to considerably complex case studies derived from industrial production of furniture. Firstly, we validate the effectiveness of the proposed genetic algorithms considering a simple case study for which information about the optimal solution is available. Then, we focus on more complex case studies, for which no a priori indication on the optimal solutions is available, and perform an extensive comparison of the various approaches. All the considered algorithms are able to find satisfactory solutions on large production sequences with nearly 300 jobs in acceptable computation times, but they also exhibit some complementary characteristics that suggest hybrid combinations of the various methods.