基于约束强度的演化算法

为了克服惩罚函数法存在的罚参数难以选择和控制的主要缺陷,利用个体违反约束条件的程度函数,定义了约束强度指标,并设计了一种新的具有较强全局搜索能力的多父体杂交算子,从而提出一种基于约束强度的有效的演化算法.通过数值验证比较其性能优于现有的一些约束单目标优化演化算法.     

Evolutionary pattern search algorithms for unconstrained andlinearly constrained optimization

We describe a convergence theory for evolutionary pattern search algorithms (EPSA) on a broad class of unconstrained and linearly constrained problems. EPSA adaptively modify the step size of the mutation operator in response to the success of previous optimization steps. The design of EPSA is inspired by recent analyzes of pattern search methods. Our analysis significantly extends the previous convergence theory for EPSA. Our analysis applies to a broader class of EPSA and it applies to problems that are nonsmooth, have unbounded objective functions, and are linearly constrained. Further, we describe a modest change to the algorithmic framework of EPSA for which a nonprobabilistic convergence theory applies. These analyses are also noteworthy because they are considerably simpler than previous analyses of EPSA     

一类带约束动态多目标优化问题的进化算法

动态多目标约束优化问题是一类NP-Hard问题,定义了动态环境下进化种群中个体的序值和个体的约束度,结合这两个定义给出了一种选择算子.在一种环境变化判断算子下给出了求解环境变量取值于正整数集Z+的一类带约束动态多目标优化问题的进化算法.通过几个典型的Benchmark函数对算法的性能进行了测试,其结果表明新算法能够较好地求出带约束动态多目标优化问题在不同环境下质量较好、分布较均匀的Pareto最优解集.     

Evolutionary algorithms, homomorphous mappings, and constrained parameter optimization

During the last five years, several methods have been proposed for handling nonlinear constraints using evolutionary algorithms (EAs) for numerical optimization problems. Recent survey papers classify these methods into four categories: preservation of feasibility, penalty functions, searching for feasibility, and other hybrids. In this paper we investigate a new approach for solving constrained numerical optimization problems which incorporates a homomorphous mapping between n-dimensional cube and a feasible search space. This approach constitutes an example of the fifth decoder-based category of constraint handling techniques. We demonstrate the power of this new approach on several test cases and discuss its further potential.     

一种求解约束优化问题的进化算法及其工程应用

提出一种改进的用于求解约束优化问题的进化算法.该算法利用混沌方法初始化个体以保证其均匀分布在搜索空间中.在进化过程中,将种群分为可行子种群和不可行子种群,分别采用不同的交叉和变异操作,以平衡算法的全局和局部搜索能力.标准测试问题的实验结果表明了改进算法的有效性.最后将改进算法应用到两个工程优化设计问题中,得到了满意的结果.     

Evolutionary constrained optimization using an addition of ranking method and a percentage-based tolerance value adjustment scheme

One of the most important issues in developing an evolutionary optimization algorithm is the proper handling of any constraints on the problem. One must balance the objective function against the degree of constraint violation in such a way that neither is dominant. Common approaches to strike this balance include implementing a penalty function and the more recent stochastic ranking method, but these methods require an extra tuning parameter which must be chosen by the user. The present paper demonstrates that a proper balance can be achieved using an addition of ranking method. Through the ranking of the individuals with respect to the objective function and constraint violation independently, we convert these two properties into numerical values of the same order of magnitude. This removes the requirement of a user-specified penalty coefficient or any other tuning parameters. Direct addition of the ranking terms is then performed to integrate all information into a single decision variable. This approach is incorporated into a (μ, λ) evolution strategy and tested on thirteen benchmark problems, one engineering design problem, and five difficult problems with a high dimensionality or many constraints. The performance of the proposed strategy is similar to that of the stochastic ranking method when dealing with inequality constraints, but it has a much simpler ranking procedure and does not require any tuning parameters. A percentage-based tolerance value adjustment scheme is also proposed to enable feasible search when dealing with equality constraints.     

Evolutionary optimization using graphical models

We have previously shown that a genetic algorithm can be approximated by an evolutionary algorithm using the product of univariate marginal distributions of selected points as search distribution. This algorithm (UMDA) successfully optimizes difficult multi-modal optimization problems. For correlated fitness landscapes more complex factorizations of the search distribution have to be used. These factorizations are used by the Factorized Distribution Algorithm FDA. In this paper we extend FDA to an algorithm which computes a factorization from the data. The factorization can be represented by a Bayesian network. The Bayesian network is used to generate the search points. Heinz Mühlenbein, Ph.D.: He is a research manager at GMD, the German national center for information technology. He obtained his diploma in mathematics from the University of Cologne in 1969, and his Ph.D from the University of Bonn in 1975. He entered GMD in 1969. He has worked on performance analysis of computer systems, computer networks, and massively parallel computers. Since 1988 his research interests are in Natural Computation. He was Visiting Professor at the Universities Paderborn, Bonn, Edinburgh and Carnegie-Mellon University. He has published over 60 research papers. He initiated the international conference series in natural computation PPSN in 1990. From 1993 to 1998 he was responsible European editor of Evolutionary Computation. He is presently on the Editorial Board of Evolutionary Computation, Scientific Computation and Journal of Heuristics. Thilo Mahnig, Ph.D. student: He is working at GMD — German National Research Center for Information Technology in St. Augustin. He obtained his diploma in mathematics from the University of Bonn in differential geometry in 1996. His research interest lies in the theory of population based optimization algorithms. He has co-authored several papers with Heinz Mühlenbein.     

A Design for Cellular Evolutionary Computation by using Bacteria

In this paper, we propose a general idea of Cellular Evolutionary Computation (CEC). CEC is Evolutionary Computation that solves the optimization problems with real DNA molecules and cells. The easiest means of cellular evolution is achieved by adding some genes to the main frame of gene network in the cell. However, in some cases it is necessary to optimize the gene parameters to achieve a desirable gene network output. We are working toward a realization of Evolutionary Computation algorithm to deal with the network optimization problems. We also suggest a novel method to realize a crossover operator for CEC via homologous recombination system within bacterial cells. Our ultimate objective of this study is the achievement of gene network evolution of the cell. We suggest an idea of cell-based computing that the cell-related problems are addressed by their related cells.     

Subspace identification with guaranteed stability using constrained optimization

In system identification, the true system is often known to be stable. However, due to finite sample constraints, modeling errors, plant disturbances and measurement noise, the identified model may be unstable. We present a constrained optimization method to ensure asymptotic stability of the identified model in the context of subspace identification methods. In subspace identification, we first obtain an estimate of the state sequence or extended observability matrix and then solve a least squares optimization problem to estimate the system parameters. To ensure asymptotic stability of the identified model, we write the least-squares optimization problem as a convex linear programming problem with mixed equality, quadratic, and positive-semidefinite constraints suitable for existing convex optimization codes such as SeDuMi. We present examples to illustrate the method and compare to existing approaches.     

On Model-Based Evolutionary Computation

 Traditional evolutionary computing techniques use an explicit fitness function – mathematical or simulated – to derive a solution to a problem from a population of individuals, over a number of generations. In this paper an approach which allows such techniques to be used on problems in which evaluations are costly, which cannot be expressed formally, or which are difficult to simulate, is examined. A neural network is trained using example individuals with the explicit fitness and the resulting model of the fitness function is then used by the evolutionary algorithm to find a solution. It is shown that the approach is effective over a small range of function types in comparison to the traditional approach when limited training data is available. An iterative step is then added whereby after a number of generations the current best individual in a population is evaluated directly on the explicit fitness function. The individual and its “real” fitness are then added to the training data and the neural network is re-trained to improve its approximation of the fitness function. It is shown that in this way the performance of the model-based architecture is greatly improved on more rugged/complex landscapes without a large increase in the amount of training data required.     

模糊机会约束规划下的物流配送路径优化

针对模糊需求信息条件下物流配送路径优化问题进行了分析,运用模糊数学的可能性理论建立了该问题的模糊机会约束规划模型,并构造了一种新的禁忌搜索算法进行求解。算例说明,该模型及算法对于模糊需求下物流配送路径优化问题具有一定的实用价值。     

A constrained optimization perspective on actor–critic algorithms and application to network routing

We propose a novel actor–critic algorithm with guaranteed convergence to an optimal policy for a discounted reward Markov decision process. The actor incorporates a descent direction that is motivated by the solution of a certain non-linear optimization problem. We also discuss an extension to incorporate function approximation and demonstrate the practicality of our algorithms on a network routing application.     

思维进化计算综述

近年来,进化计算的研究引起了人们很大的关注,它运用模拟生物进化过程的思想,生成计算机程序来解决问题。介绍了一种进化计算的新分支——思维进化计算,并对其理论、框架、算子、主要特点进行了概述,同时介绍了思维进化计算的主要应用领域,最后探讨了思维进化计算的研究方向。     

Evolutionary multiobjective optimization using an outranking-based dominance generalization

One aspect that is often disregarded in the current research on evolutionary multiobjective optimization is the fact that the solution of a multiobjective optimization problem involves not only the search itself, but also a decision making process. Most current approaches concentrate on adapting an evolutionary algorithm to generate the Pareto frontier. In this work, we present a new idea to incorporate preferences into a multi-objective evolutionary algorithm (MOEA). We introduce a binary fuzzy preference relation that expresses the degree of truth of the predicate “x is at least as good as y”. On this basis, a strict preference relation with a reasonably high degree of credibility can be established on any population. An alternative x is not strictly outranked if and only if there does not exist an alternative y which is strictly preferred to x. It is easy to prove that the best solution is not strictly outranked. For validating our proposed approach, we used the non-dominated sorting genetic algorithm II (NSGA-II), but replacing Pareto dominance by the above non-outranked concept. So, we search for the non-strictly outranked frontier that is a subset of the Pareto frontier. In several instances of a nine-objective knapsack problem our proposal clearly outperforms the standard NSGA-II, achieving non-outranked solutions which are in an obviously privileged zone of the Pareto frontier.     

Energy constrained multi-robot sensor-based coverage path planning using capacitated arc routing approach

Multi-robot sensor-based coverage path planning requires every point given in the workspace has to be covered at least by a sensor of a robot in the robot team. In this study, a novel algorithm was proposed for the sensor-based coverage of narrow environments by considering energy capacities of the robots. For this purpose, the environment was modeled by a Generalized Voronoi diagram-based graph to guarantee complete sensor-based coverage. Then, depending on the required arc set, a complete coverage route was created by using the Chinese Postman Problem or the Rural Postman Problem, and this route was partitioned among robots by considering energy capacities. Route partitioning was realized by modifying the Ulusoy partitioning algorithm which has polynomial complexity. This modification handles two different energy consumptions of mobile robots during sensor-based coverage, which was not considered before. The developed algorithm was coded in C++ and implemented on P3-DX mobile robots both in laboratory and in MobileSim simulation environments. It was shown that the convenient routes for energy constrained multi-robots could be generated by using the proposed algorithm in less than 1 s.     

一个效率可观的启发式多约束QoS路由算法

提出的MWA_MCP(maximal weight amputation for multi-constrained problem)算法,充分利用了BFS(bread first search)算法计算复杂度简单的特点,使用BFS搜索QoS路径.MWA_MCP在搜索过程中有选择地去掉QoS性能差的边,即权重较大的边将在搜索中有策略地被去掉.与仿真的几个算法相比,MWA_MCP体现了较高的路由性能.     

Mixed constrained image filter design using particle swarm optimization

This article describes an evolutionary image filter design for noise reduction using particle swarm optimization (PSO), where mixed constraints on the circuit complexity, power, and signal delay are optimized. First, the evaluated values of correctness, complexity, power, and signal delay are introduced to the fitness function. Then PSO autonomously synthesizes a filter. To verify the validity of our method, an image filter for noise reduction was synthesized. The performance of the resultant filter by PSO was similar to that of a genetic algorithm (GA), but the running time of PSO is 10% shorter than that of GA.     

Linearly constrained optimization

For linearly constrained optimization problems an algorithm is presented which is based on conjugate gradients. Numerical tests demonstrate a favourable behaviour of the new algorithm.     

一种适用于移动网络的能量约束路由协议

移动Ad Hoc网络是一种受能量约束的移动系统,是否具有较长的生命周期是评价该网络路由协议的一个重要的尺度。基于移动网络节点的能量级以及不同的使用策略,论文提出了一种基于能量约束的路由协议--ECRP。该路由协议不仅使系统消耗的能量较低而且也延长了系统的生命周期以及改进了延时特性。论文给出了ECRP的正确性和复杂性分析。仿真结果表明ECRP具有较好的延时特性、较低的能量消耗和较长的网络生命周期,提供了一种解决移动Ad Hoc网络路由的有效方法。