Modeling and convergence analysis of distributed coevolutionary algorithms

A theoretical foundation is presented for modeling and convergence analysis of a class of distributed coevolutionary algorithms applied to optimization problems in which the variables are partitioned among p nodes. An evolutionary algorithm at each of the p nodes performs a local evolutionary search based on its own set of primary variables, and the secondary variable set at each node is clamped during this phase. An infrequent intercommunication between the nodes updates the secondary variables at each node. The local search and intercommunication phases alternate, resulting in a cooperative search by the p nodes. First, we specify a theoretical basis for a class of centralized evolutionary algorithms in terms of construction and evolution of sampling distributions over the feasible space. Next, this foundation is extended to develop a model for a class of distributed coevolutionary algorithms. Convergence and convergence rate analyzes are pursued for basic classes of objective functions. Our theoretical investigation reveals that for certain unimodal and multimodal objectives, we can expect these algorithms to converge at a geometrical rate. The distributed coevolutionary algorithms are of most interest from the perspective of their performance advantage compared to centralized algorithms, when they execute in a network environment with significant local access and internode communication delays. The relative performance of these algorithms is therefore evaluated in a distributed environment with realistic parameters of network behavior.     

Post-evolution of variable-length class prototypes to unlock decision making within support vector machines

Although neural networks and support vector machines (SVMs) are the traditional predictors for the classification of complex problems, these opaque paradigms cannot explain the logic behind the discrimination process. Therefore, within the quite unexplored area of evolutionary algorithms opening the SVM decision black box, the paper appoints a cooperative coevolutionary (CC) technique to extract discriminative and compact class prototypes following a SVM model. Various interactions between the SVM and CC are considered, while many experiments test three decisive hypotheses: fidelity to the SVM prediction, superior accuracy to the CC classifier alone and a compact and comprehensive resulting output, achieved through a class-oriented form of feature selection. Results support the hybridization by statistically and visually demonstrating its advantages.     

A distributed Cooperative coevolutionary algorithm for multiobjective optimization

Recent advances in evolutionary algorithms show that coevolutionary architectures are effective ways to broaden the use of traditional evolutionary algorithms. This paper presents a cooperative coevolutionary algorithm (CCEA) for multiobjective optimization, which applies the divide-and-conquer approach to decompose decision vectors into smaller components and evolves multiple solutions in the form of cooperative subpopulations. Incorporated with various features like archiving, dynamic sharing, and extending operator, the CCEA is capable of maintaining archive diversity in the evolution and distributing the solutions uniformly along the Pareto front. Exploiting the inherent parallelism of cooperative coevolution, the CCEA can be formulated into a distributed cooperative coevolutionary algorithm (DCCEA) suitable for concurrent processing that allows inter-communication of subpopulations residing in networked computers, and hence expedites the computational speed by sharing the workload among multiple computers. Simulation results show that the CCEA is competitive in finding the tradeoff solutions, and the DCCEA can effectively reduce the simulation runtime without sacrificing the performance of CCEA as the number of peers is increased.     

Many objective cooperative bat searching algorithm

In this paper, a many objective cooperative bat searching algorithm (MOCBA) is proposed to solve many-objective optimization problems by using the balanceable fitness estimation method. Similar to the particle swarm optimization (PSO) algorithm and the evolutionary algorithm (EA), the cooperative bat searching algorithm (CBA) is a recently developed swarm intelligence optimization algorithm to efficiently solve single-objective optimization problems. With the balanceable fitness estimation method, the MOCBA balances the diversity ability and convergence ability of the algorithm during searching process. Moreover, the convergence issue for MOCBA is also studied. The results on convergence in mean and convergence in probability of the MCOBA are presented. Experimental results are provided to demonstrate the effectiveness of the proposed MOCBA by comparing with fourteen state-of-the-art many-objective optimization algorithms by solving benchmark functions: DTLZ1–DTLZ5 and WFG1–WFG9. By calculating the means, standard deviations and running the Wilcoxon rank sum tests and the Friedmans tests of 100 algorithm executions, the proposed MOCBA shows superior performance among all the fifteen algorithms.     

Evolutionary algorithm characterization in real parameter optimization problems

This paper deals with the constant problem of establishing a usable and reliable evolutionary algorithm (EA) characterization procedure so that final users like engineers, mathematicians or physicists can have more specific information to choose the most suitable EA for a given problem. The practical goal behind this work is to provide insights into relevant features of fitness landscapes and their relationship to the performance of different algorithms. This should help users to minimize the typical initial stage in which they apply a well-known EA, or a modified version of it, to the functions they want to optimize without really taking into account its suitability to the particular features of the problem. This trial and error procedure is usually due to a lack of objective and detailed characterizations of the algorithms in the literature in terms of the types of functions or landscape characteristics they are well suited to handle and, more importantly, the types for which they are not appropriate. Specifically, the influence of separability and modality of the fitness landscapes on the behaviour of EAs is analysed in depth to conclude that the typical binary classification of the target functions into separable/non-separable and unimodal/multimodal is too general, and characterizing the EAs’ response in these terms is misleading. Consequently, more detailed features of the fitness landscape in terms of separability and modality are proposed here and their relevance in the EAs’ behaviour is shown through experimentation using standardized benchmark functions that are described using those features. Three different EAs, the genetic algorithm, the Covariance Matrix Adaptation Evolution Strategy and Differential Evolution, are evaluated over these benchmarks and their behaviour is explained in terms of the proposed features.     

Approach to decision making in fuzzy environment

A general approach to solving a wide class of optimization problems with fuzzy coefficients in objective functions and constraints is described. It is based on a modification of traditional mathematical programming methods and consists in formulating and solving one and the same problem within the framework of interrelated models with constructing equivalent analogs with fuzzy coefficients in objective function alone. This approach allows one to maximally cut off dominated alternatives from below as well as from above. The subsequent contraction of the decision uncertainty region is associated with reduction of the problem to multicriteria decision making in a fuzzy environment. The approach is applied within the context of fuzzy discrete optimization models, that is based on a modification of discrete optimization algorithms. The results of the paper are of a universal character and are already being used to solve problems of the design and control of power systems and subsystems.     

Runtime analysis of the (mu+1) EA on simple Pseudo-Boolean functions

Although Evolutionary Algorithms (EAs) have been successfully applied to optimization in discrete search spaces, theoretical developments remain weak, in particular for population-based EAs. This paper presents a first rigorous analysis of the (mu+1) EA on pseudo-Boolean functions. Using three well-known example functions from the analysis of the (1+1) EA, we derive bounds on the expected runtime and success probability. For two of these functions, upper and lower bounds on the expected runtime are tight, and on all three functions, the (mu+1) EA is never more efficient than the (1+1) EA. Moreover, all lower bounds grow with mu. On a more complicated function, however, a small increase of mu probably decreases the expected runtime drastically.This paper develops a new proof technique that bounds the runtime of the (mu+1) EA. It investigates the stochastic process for creating family trees of individuals; the depth of these trees is bounded. Thereby, the progress of the population towards the optimum is captured. This new technique is general enough to be applied to other population-based EAs.     

Zen-ReqOptimizer: a search-based approach for requirements assignment optimization

At early phases of a product development lifecycle of large scale Cyber-Physical Systems (CPSs), a large number of requirements need to be assigned to stakeholders from different organizations or departments of the same organization for review, clarification and checking their conformance to standards and regulations. These requirements have various characteristics such as extents of importance to the organization, complexity, and dependencies between each other, thereby requiring different effort (workload) to review and clarify. While working with our industrial partners in the domain of CPSs, we discovered an optimization problem, where an optimal solution is required for assigning requirements to various stakeholders by maximizing their familiarity to assigned requirements, meanwhile balancing the overall workload of each stakeholder. In this direction, we propose a fitness function that takes into account all the above-mentioned factors to guide a search algorithm to find an optimal solution. As a pilot experiment, we first investigated four commonly applied search algorithms (i.e., GA, (1 + 1) EA, AVM, RS) together with the proposed fitness function and results show that (1 + 1) EA performs significantly better than the other algorithms. Since our optimization problem is multi-objective, we further empirically evaluated the performance of the fitness function with six multi-objective search algorithms (CellDE, MOCell, NSGA-II, PAES, SMPSO, SPEA2) together with (1 + 1) EA (the best in the pilot study) and RS (as the baseline) in terms of finding an optimal solution using an real-world case study and 120 artificial problems of varying complexity. Results show that both for the real-world case study and the artificial problems (1 + 1) EA achieved the best performance for each single objective and NSGA-II achieved the best performance for the overall fitness. NSGA-II has the ability to solve a wide range of problems without having their performance degraded significantly and (1 + 1) EA is not fit for problems with less than 250 requirements Therefore we recommend that, if a project manager is interested in a particular objective then (1 + 1) EA should be used; otherwise, NSGA-II should be applied to obtain optimal solutions when putting the overall fitness as the first priority.     

Hybrid coevolutionary programming for Nash equilibrium search in games with local optima

The conventional local optimization path and coevolutionary processes are studied when "local Nash equilibrium (NE) traps" exist. Conventional NE search algorithms in games with local optima can misidentify NE by following a local optimization path. We prove that any iterative NE search algorithms based on local optimization cannot differentiate real NE and "local NE traps". Coevolutionary programming, a parallel and global search algorithm, is applied to overcome this problem. In order to enhance the poor convergence of simple coevolutionary programming, hybrid coevolutionary programming is suggested. The conventional NE algorithms, simple coevolutionary programming, and hybrid coevolutionary algorithms are tested through a simple numerical example and transmission-constrained electricity market examples.     

Virtual player design using self-learning via competitive coevolutionary algorithms

The Google Artificial Intelligence (AI) Challenge is an international contest the objective of which is to program the AI in a two-player real time strategy (RTS) game. This AI is an autonomous computer program that governs the actions that one of the two players executes during the game according to the state of play. The entries are evaluated via a competition mechanism consisting of two-player rounds where each entry is tested against others. This paper describes the use of competitive coevolutionary (CC) algorithms for the automatic generation of winning game strategies in Planet Wars, the RTS game associated with the 2010 contest. Three different versions of a prime algorithm have been tested. Their common nexus is not only the use of a Hall-of-Fame (HoF) to keep note of the winners of past coevolutions but also the employment of an archive of experienced players, termed the hall-of-celebrities (HoC), that puts pressure on the optimization process and guides the search to increase the strength of the solutions; their differences come from the periodical updating of the HoF on the basis of quality and diversity metrics. The goal is to optimize the AI by means of a self-learning process guided by coevolutionary search and competitive evaluation. An empirical study on the performance of a number of variants of the proposed algorithms is described and a statistical analysis of the results is conducted. In addition to the attainment of competitive bots we also conclude that the incorporation of the HoC inside the primary algorithm helps to reduce the effects of cycling caused by the use of HoF in CC algorithms.     

Network-based distributed planning using coevolutionary agents: architecture and evaluation

A novel evolutionary planning framework (coevolutionary virtual design environment) particularly suited to distributed network-enabled design and manufacturing organizations is presented. The approach utilizes distributed evolutionary agents and mobile agents as principal object-oriented software entities that support a network-efficient evolutionary exploration of planning alternatives in which successive populations systematically select planning alternatives that reduce cost and increase throughput. This paper presents the architecture of the coevolutionary virtual design environment, and examines the network-based performance of the coevolutionary algorithms that execute in this environment. Simulation analysis examines the percentage convergence error and percentage computational advantage comparing the distributed network-based implementation to a centralized network-based implementation. The algorithms and architectures are evaluated in a realistic network setting and analyzed using models of network delays and processing times.     

演化算法的时间复杂性

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

Quantum immune clonal coevolutionary algorithm for dynamic multiobjective optimization

The existing algorithms to solve dynamic multiobjective optimization (DMO) problems generally have difficulties in non-uniformity, local optimality and non-convergence. Based on artificial immune system, quantum evolutionary computing and the strategy of co-evolution, a quantum immune clonal coevolutionary algorithm (QICCA) is proposed to solve DMO problems. The algorithm adopts entire cloning and evolves the theory of quantum to design a quantum updating operation, which improves the searching ability of the algorithm. Moreover, coevolutionary strategy is incorporated in global operation and coevolutionary competitive operation and coevolutionary cooperative operation are designed to improve the uniformity, the diversity and the convergence performance of the solutions. The results on test problems and performance metrics compared with ICADMO and DBM suggest that QICCA has obvious effectiveness and advantages which shows great capability of evolving convergent, diverse and uniformly distributed Pareto fronts.     

Bandit-based cooperative coevolution for tackling contribution imbalance in large-scale optimization problems

This paper addresses the issue of computational resource allocation within the context of cooperative coevolution. Cooperative coevolution typically works by breaking a problem down into smaller subproblems (or components) and coevolving them in a round-robin fashion, resulting in a uniform resource allocation among its components. Despite its success on a wide range of problems, cooperative coevolution struggles to perform efficiently when its components do not contribute equally to the overall objective value. This is of crucial importance on large-scale optimization problems where such difference are further magnified. To resolve this imbalance problem, we extend the standard cooperative coevolution to a new generic framework capable of learning the contribution of each component using multi-armed bandit techniques. The new framework allocates the computational resources to each component proportional to their contributions towards improving the overall objective value. This approach results in a more economical use of the limited computational resources. We study different aspects of the proposed framework in the light of extensive experiments. Our empirical results confirm that even a simple bandit-based credit assignment scheme can significantly improve the performance of cooperative coevolution on large-scale continuous problems, leading to competitive performance as compared to the state-of-the-art algorithms.     

协同演化算法研究进展

协同演化算法(coevolutionary algorithms, CEA)是当前国际上计算智能研究的一个热点,它运用生物协同演化的思想,是针对演化算法的不足而兴起的,通过构造两个或多个种群,建立它们之间的竞争或合作关系,多个种群通过相互作用来提高各自性能,适应复杂系统的动态演化环境,以达到种群优化的目的.介绍了协同演化算法的研究状况以及目前的研究进展,概述了它的基本算法、主要特点、理论与技术,同时介绍了一些主要的应用领域,指出了协同演化算法的研究方向.     

Numerical integration in statistical decision-theoretic methods for robust design optimization

The Bayes principle from statistical decision theory provides a conceptual framework for quantifying uncertainties that arise in robust design optimization. The difficulty with exploiting this framework is computational, as it leads to objective and constraint functions that must be evaluated by numerical integration. Using a prototypical robust design optimization problem, this study explores the computational cost of multidimensional integration (computing expectation) and its interplay with optimization algorithms. It concludes that straightforward application of standard off-the-shelf optimization software to robust design is prohibitively expensive, necessitating adaptive strategies and the use of surrogates.     

LeCMPSO算法求解异构无人机协同多任务重分配问题

无人机系统在军事领域有着广泛应用, 由于战场环境复杂多变, 无人机遭遇突发状况后需进行任务重分配.异构无人机是指多种类型的无人机, 可完成单一无人机无法完成的多类型复杂任务, 异构无人机协同多任务重分配问题约束条件复杂且包含混合变量, 现有多目标优化算法不能有效处理此类问题. 为高效求解上述问题, 本文构建多约束异构无人机协同多任务重分配问题模型, 提出一种学习引导的协同多目标粒子群优化算法(LeCMPSO), 该算法引入基于先验知识的初始化策略和基于历史信息学习的粒子更新策略, 能有效避免不可行解的产生并提升算法的搜索效率. 通过在4组实例上的仿真实验表明, 与其他典型的协同进化多目标优化算法相比, 所提算法在解集的多样性、收敛性及搜索时间方面均具有较好的性能.     

Evolutionary algorithms - how to cope with plateaus of constantfitness and when to reject strings of the same fitness

The most simple evolutionary algorithm (EA), the so-called (1 + 1) EA, accepts an offspring if its fitness is at least as large (in the case of maximization) as the fitness of its parent. The variant (1 + 1)* EA only accepts an offspring if its fitness is strictly larger than the fitness of its parent. Here, two functions related to the class of long-path functions are presented such that the (1 + 1) EA maximizes one in polynomial time and needs exponential time for the other while the (1 + 1)* EA has the opposite behavior. These results demonstrate that small changes of an EA may change its behavior significantly. Since the (1 + 1) EA and the (1 + 1)* EA differ only on plateaus of constant fitness, the results also show how EAs behave on such plateaus. The (1 + 1) EA can pass a path of constant fitness and polynomial length in polynomial time. Finally, for these functions, it is shown that local performance measures like the quality gain and the progress rate do not describe the global behavior of EAs     

Properties of Symmetric Fitness Functions

The properties of symmetric fitness functions are investigated. We show that the search spaces obtained from symmetric functions have the zero-correlation structures between fitness and distance. It is also proven that symmetric functions induce a class of the hardest problems in terms of the epistasis variance and its variants. These analyses suggest that the existing quantitative measures cannot discriminate among symmetric functions, which reveals critical limitations of the measures. To take a closer look at the symmetric functions, additional analyses are performed from other viewpoints including additive separability and boundedness. It is shown that additive separability in a symmetric function is closely related to the symmetry of its subfunctions. This elucidates why most of the well-known symmetric fitness functions are additively inseparable. The properties of two-bounded symmetric functions are investigated and they are utilized in designing an efficient algorithm to check additive separability for the two-bounded functions. Throughout this paper, we heavily use the generalized Walsh transform over multary alphabets. Our results have an independent interest as a nontrivial application of the generalized Walsh analysis.     

Self-adaptive mutations may lead to premature convergence

Self-adaptive mutations are known to endow evolutionary algorithms (EA) with the ability of locating local optima quickly and accurately, whereas it was unknown whether these local optima are finally global optima provided that the EA runs long enough. In order to answer this question, it is assumed that the (1+1)-EA with self-adaptation is located in the vicinity P of a local solution with objective function value ε. In order to exhibit convergence to the global optimum with probability one, the EA must generate an offspring that is an element of the lower level set S containing all solutions (including a global one) with objective function value less than ε. In case of multimodal objective functions, these sets P and S are generally not adjacent, i.e., min{∥x-y∥:x∈P, y∈S}>0, so that the EA has to surmount the barrier of solutions with objective function values larger than ε by a lucky mutation. It will be proven that the probability of this event is less than one even under an infinite time horizon. This result implies that the EA can get stuck at a nonglobal optimum with positive probability. Some ideas of how to avoid this problem are discussed as well