Using evolution strategies to solve DEC-POMDP problems

Decentralized partially observable Markov decision process (DEC-POMDP) is an approach to model multi-robot decision making problems under uncertainty. Since it is NEXP-complete there is no efficient exact algorithm to solve these problems and in spite of the attention it has taken recently, so far only a few approximate solutions that can solve small problems have been proposed. In this study, we offer a novel approximate solution algorithm for DEC-POMDP problems using evolution strategies, and a novel approach to approximately calculate the fitness of the chromosomes which correspond to the expected reward. We also propose a new problem which is a more complex, modified version of the grid meeting problem and solve it. Our results show that our algorithm is scalable and we can solve problems that have more states than the problems attempted in previous studies.     

Evolution strategies with cumulative step length adaptation on the noisy parabolic ridge

This paper presents an analysis of the performance of the (μ/μ,λ)-ES with isotropically distributed mutations and cumulative step length adaptation on the noisy parabolic ridge. Several forms of dependency of the noise strength on the distance from the ridge axis are considered. Closed form expressions are derived that describe the mutation strength and the progress rate of the strategy in high-dimensional search spaces. It is seen that as for the sphere model, larger levels of noise present lead to cumulative step length adaptation generating increasingly inadequate mutation strengths, and that the problem can be ameliorated to some degree by working with larger populations.     

Self-adaptation of evolution strategies under noisy fitness evaluations

This paper investigates the self-adaptation behavior of ()-evolution strategies (ES) on the noisy sphere model. To this end, the stochastic system dynamics is approximated on the level of the mean value dynamics. Being based on this “microscopic” analysis, the steady state behavior of the ES for the scaled noise scenario and the constant noise strength scenario will be theoretically analyzed and compared with real ES runs. An explanation will be given for the random walk like behavior of the mutation strength in the vicinity of the steady state. It will be shown that this is a peculiarity of the -ES and that intermediate recombination strategies do not suffer from such behavior.     

Active-guided evolution strategies for large-scale capacitated vehicle routing problems

We present an adaptation of the active-guided evolution strategies metaheuristic for the capacitated vehicle routing problem. The capacitated vehicle routing problem is a classical problem in operations research in which a set of minimum total cost routes must be determined for a fleet of identical capacitated vehicles in order to service a number of demand or supply points. The applied metaheuristic combines the strengths of the well-known guided local search and evolution strategies metaheuristics into an iterative two-stage procedure. The computational experiments were carried out on a set of 76 benchmark problems. The results demonstrate that the suggested method is highly competitive, providing the best-known solutions to 70 test instances.     

Evolution strategies and multi-objective optimization of permanent magnet motor

When designing a permanent magnet motor, several geometry and material parameters are to be defined. This is not an easy task, as material properties and magnetic fields are highly non-linear and the design of a motor is therefore often an iterative process. From an engineering point of view, we usually want to maximize the efficiency of the motor and from an economic point of view we want to minimize the cost of the motor. As these two things seldom go hand in hand, the goal is to find the best efficiency per cost. The scope of this paper is therefore to investigate the applicability of evolution strategies, ES to effectively design and optimize parameters of permanent magnet motors. Single as well as multi-objective optimization procedures are carried out. A modified way of creating the strategy parameters for the ES algorithm is also proposed and has together with the standard ES algorithm undergone a comprehensive parameter study for the parameters ρ and λ. The results of this parameter study show a significant improvement in stability and speed with the use of the modified ES version. To find the most effective selector for a multi-objective optimization, MOO, of the motor a performance examination of 4 different selectors from the group of programs called PISA has been made and compared for MOO of the efficiency and cost of the motor. This performance examination showed that the indicator based evolutionary algorithm, IBEA, and hypervolume estimation algorithm, HypE, selectors performed almost equally good on this MOO problem where the HypE selector only had a slightly better performance indicator.     

The optimisation of space structures using evolution strategies with functional networks

In this work, the input for large space structures is created using the Formex algebra of the Formian software. The different search and optimisation algorithm known as evolution strategies (ESs) has been applied to find the optimal design of the space trusses considering the areas of the members of the space structures as discrete variables. The objective function is obtained for first few generations by using a structural analysis package such as Feast and for other generations by functional networks (FNs). Initially, to obtain the data for a functional network, a structural package such as Feast is used. The use of a functional network is motivated by time consuming repeated analyses required by evolution strategies during the optimisation process. In addition, a multilevel optimisation approach is implemented by reducing the size of the search space for individual design variables in each successive level of the optimisation process for the first example; for the remaining three examples, a functional network has been combined with evolution strategies to get away with the use of a structural analysis package and a multilevel optimisation technique. The numerical tests presented demonstrate the computational advantage of the proposed approach of ESs combined with functional networks (FNs) which become pronounced for fairly large scale optimisation problems involving about 700 degrees of freedom.     

Human-competitive lens system design with evolution strategies

Lens system design provides ideal problems for evolutionary algorithms: a complex non-linear optimization task, often with intricate physical constraints, for which there is no analytical solutions. This paper demonstrates, through the use of two evolution strategies, namely non-isotropic Self-Adaptive evolution strategy (SA-ES) and Covariance Matrix Adaptation evolution strategy (CMA-ES), as well as multiobjective Non-Dominated Sort Genetic Algorithm 2 (NSGA-II) optimization, the human competitiveness of an approach where an evolutionary algorithm is hybridized with a local search algorithm to solve both a classic benchmark problem, and a real-world problem.     

差分进化算法参数控制与适应策略综述

差分进化算法逐渐成为进化计算领域最流行的随机搜索算法之一,已被成功用于求解各类应用问题.差分进化算法参数设置与其性能密切相关,因此算法参数控制与适应策略设计是目前该领域的研究热点之一,目前已涌现出大量参数控制方案,但尚缺乏系统性的综述与分析.首先简要介绍差分进化算法的基本原理与操作,然后将目前参数控制与适应策略分成基于经验的参数控制、参数随机化适应策略、基于统计学习的参数随机化适应策略和参数自适应策略4类进行系统性综述,重点介绍其中的参数适应与自适应策略.此外,为分析各种参数控制与适应策略的功效,以实值函数优化为问题背景设计了相关实验,进一步分析各种策略的效率与实用性,实验结果表明,参数自适应控制策略是目前该领域最有效的方法之一.     

Weighted averaging and stochastic approximation

We explore the relationship between weighted averaging and stochastic approximation algorithms, and study their convergence via a sample-path analysis. We prove that the convergence of a stochastic approximation algorithm is equivalent to the convergence of the weighted average of the associated noise sequence. We also present necessary and sufficient noise conditions for convergence of the average of the output of a stochastic approximation algorithm in the linear case. We show that the averaged stochastic approximation algorithms can tolerate a larger class of noise sequences than the stand-alone stochastic approximation algorithms.This research was supported by the National Science Foundation through Grants ECS-9410313 and ECS-9501652.This research was supported by the National Science Foundation through NYI Grant IRI-9457645.     

Efficient covariance matrix update for variable metric evolution strategies

Randomized direct search algorithms for continuous domains, such as evolution strategies, are basic tools in machine learning. They are especially needed when the gradient of an objective function (e.g., loss, energy, or reward function) cannot be computed or estimated efficiently. Application areas include supervised and reinforcement learning as well as model selection. These randomized search strategies often rely on normally distributed additive variations of candidate solutions. In order to efficiently search in non-separable and ill-conditioned landscapes the covariance matrix of the normal distribution must be adapted, amounting to a variable metric method. Consequently, covariance matrix adaptation (CMA) is considered state-of-the-art in evolution strategies. In order to sample the normal distribution, the adapted covariance matrix needs to be decomposed, requiring in general Θ(n ³) operations, where n is the search space dimension. We propose a new update mechanism which can replace a rank-one covariance matrix update and the computationally expensive decomposition of the covariance matrix. The newly developed update rule reduces the computational complexity of the rank-one covariance matrix adaptation to Θ(n ²) without resorting to outdated distributions. We derive new versions of the elitist covariance matrix adaptation evolution strategy (CMA-ES) and the multi-objective CMA-ES. These algorithms are equivalent to the original procedures except that the update step for the variable metric distribution scales better in the problem dimension. We also introduce a simplified variant of the non-elitist CMA-ES with the incremental covariance matrix update and investigate its performance. Apart from the reduced time-complexity of the distribution update, the algebraic computations involved in all new algorithms are simpler compared to the original versions. The new update rule improves the performance of the CMA-ES for large scale machine learning problems in which the objective function can be evaluated fast.     

Structural optimization of as-built parts using reverse engineering and evolution strategies

In industry, some parts are prone to failures or their design is simply sub-optimal. In those critical situations, one would like to be able to make changes to the part, making it lighter or improving its mechanical resistance. The problem of as-built parts is that the original computer-aided design (CAD) model is not available or is lost. To optimize them, a reverse engineering process is necessary to capture the shape and topology of the original design. This paper describes how to capture the original design geometry using a semi-automated reverse engineering process based on measurement provided by an optical 3D sensor. Following this reverse engineering process, a Fixed Grid Finite Element method and evolutionary algorithms are used to find the optimum shape that will minimize stress and weight. Several examples of industrial parts are presented. These examples show the advantages and disadvantages of the proposed method in an industrial scenario. Presented at the 7th World Congress on Computational Mechanics, Los Angeles 2006.     

Weighted comparison of two cumulative incidence functions with R-CIFsmry package

In this paper we propose a class of flexible weight functions for use in comparison of two cumulative incidence functions. The proposed weights allow the users to focus their comparison on an early or a late time period post treatment or to treat all time points with equal emphasis. These weight functions can be used to compare two cumulative incidence functions via their risk difference, their relative risk, or their odds ratio. The proposed method has been implemented in the R-CIFsmry package which is readily available for download and is easy to use as illustrated in the example.     

On three new approaches to handle constraints within evolution strategies

Evolutionary algorithms with a self-adaptive step control mechanism like evolution strategies (ES) often suffer from premature fitness stagnation on constrained numerical optimization problems. When the optimum lies on the constraint boundary or even in a vertex of the feasible search space, a disadvantageous success probability results in premature step size reduction. We introduce three new constraint-handling methods for ES on constrained continuous search spaces. The death penalty step control evolution strategy (DSES) is based on the controlled reduction of a minimum step size depending on the distance to the infeasible search space. The two sexes evolution strategy (TSES) is inspired by the biological concept of sexual selection and pairing. At last, the nested angle evolution strategy (NAES) is an approach in which the angles of the correlated mutation of the inner ES are adapted by the outer ES. All methods are experimentally evaluated on four selected test problems and compared with existing penalty-based constraint-handling methods.     

适用于高维优化问题的改进进化策略

针对高维连续函数优化问题,研究了CES(classical evo lution strateg ies)的变异方式、繁殖方式,提出了全基因变异与单基因变异的概念,通过理论分析和仿真计算论证了单基因变异比全基因变异具有更好的局部搜索能力和少的计算开销;针对CES策略参数(变异幅度)随机性过强,不能很好地跟踪进化过程的问题,提出了随着进化过程递减的策略参数.最后,建立了单基因Gauss变异与均匀变异相结合、使用精英繁殖、递减型策略参数、小种群规模的(μ λ k)-ES,给出了一组100维典型测试函数的仿真计算结果.     

一种基于带权多因素的分步优化技术及实现

本文结合油田地面建设总体规划方案优选的实际,提出了一种适用于带权多因素树型结构的优化技术。     

An adaptive penalty based covariance matrix adaptation–evolution strategy

Although most of unconstrained optimization problems with moderate to high dimensions can be easily handled with Evolutionary Computation (EC) techniques, constraint optimization problems (COPs) with inequality and equality constraints are very hard to deal with. Despite the fact that only equality constraints can be used to eliminate a certain variable, both types of constraints implicitly enforce a relation between problem variables. Most conventional constraint handling methods in EC do not consider the correlations between problem variables imposed by the problem constraints. This paper relies on the idea that a proper genetic operator, which captures mentioned implicit correlations, can improve performance of evolutionary constrained optimization algorithms. With this in mind, we employ a (μ+λ)-Evolution Strategy with a simplified variant of Covariance Matrix Adaptation based mutation operator along an adaptive weight adjustment scheme. The proposed algorithm is tested on two test sets. The outperformance of the algorithm is significant on the first benchmark when compared with five conventional methods. The results on the second test set show that algorithm is highly competitive when benchmarked with three state-of-art algorithms. The main drawback of the algorithm is its slightly lower speed of convergence for problems with high dimension and/or large search domain.     

基于粒子群的加权朴素贝叶斯入侵检测模型

针对传统朴素贝叶斯算法对高维复杂的入侵行为检测效率低下的状况,提出一种基于粒子群的加权朴素贝叶斯入侵检测模型。模型首先用粗糙集理论对样本属性特征集进行约简,再利用改进的粒子群算法优化加权朴素贝叶斯算法的属性权值,获得属性权值的最优解,用获得的最优解构造贝叶斯分类器完成检测。其中,改进的粒子群是采用权衡因子方法更新其速度和位置公式,避免产生局部最优。两种算法的结合,既能解决传统朴素贝叶斯算法的特征项冗余问题,同时也可以优化特征项间的强独立性问题。通过实验证实了该模型的实效性,提高了检测率。     

加权无标度网络病毒传播控制中带粒子群优化的免疫策略

为有效解决加权无标度网络中的病毒传播控制问题,基于图分割思想,同时考虑子网络规模和子网络节点的强度和两个优化目标,引入遗传算法的变异和交叉算子以提高种群多样性并避免算法过早陷入局部最优解,进而提出一种带粒子群优化的免疫策略.仿真实验结果表明所提免疫策略比目前公认高效的目标免疫策略效果更好,可通过免疫指定数量的节点,较好地将网络分割成节点个数尽可能少、节点强度和尽可能小的子网络.     

基于多变异策略的自适应差分进化算法

为了克服差分进化算法寻优精度低、收敛速度慢、稳定性差等不足,提出一种基于多变异策略的自适应差分进化算法（ADE-MM）。首先,在3个变异策略的选择过程中添加2个具有学习功能的扰动阈值,以提高种群多样性,扩大搜索范围;然后,根据上次迭代的成功参数自适应调整当前参数,提高寻优精度和寻优速度;最后,利用向量粒子池法和中心粒子法产生新的向量粒子,进一步提高寻优效果。使用8个函数、5种对比算法（RMDE、OLCPDE、JADE、SaDE、MDE_pBX）进行测试,且每种例子都独立执行30次。ADE-MM算法在均值和方差的比较中取得了全胜,其中在30维的情况下取得了5个独立胜利,3个并列胜利;在50维的情况下取得了6个独立胜利,2个并列胜利;在100维的情况下全部为独立胜利。同时在Wilcoxon rank sum test、胜率和算法耗时分析中,ADE-MM算法也取得优异的表现。实验结果表明,相对于其他5种对比算法,ADE-MM算法具有更强的全局寻优能力、收敛性和稳定性。     

动态调整惯性权重的粒子群算法优化

为了优化目前粒子群算法比较容易陷入局部最优、后期收敛过慢等的缺陷,在本文提出了一种改进惯性权重参数来优化算法的方法.其中结合了差分进化算法中的变异算子的操作来提升算法的自适应并且对算法的速度和搜索空间进行边界限制以防止粒子跳出所规定的搜索空间.选择相应的测试函数,使用Matlab软件将提出的改进算法与其他两种算法进行仿真实验对比,结果表明,本文所提出的算法在后期收敛速度以及取得适应度值的稳定性上有一定的提升.