协同演化算法研究进展

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

Training multi-agent teams from zero knowledge with the competitive coevolutionary team-based particle swarm optimiser

A new competitive coevolutionary team-based particle swarm optimiser (CCPSO(t)) algorithm is developed to train multi-agent teams from zero knowledge. The CCPSO(t) algorithm is applied to train a team of agents to play simple soccer. The algorithm uses the charged particle swarm optimiser in a competitive and cooperative coevolutionary training environment to train neural network controllers for the players. The CCPSO(t) algorithm makes use of the FIFA league ranking relative fitness function to gather detailed performance metrics from each game played. The training performance and convergence behaviour of the particle swarm are analysed. A hypothesis is presented that explains the lack of convergence in the particle swarms. After applying a clustering algorithm on the particle positions, a detailed visual and quantitative analysis of the player strategies is presented. The final results show that the CCPSO(t) algorithm is capable of evolving complex gameplay strategies for a complex non-deterministic game.     

基于共同进化计算模型的基因连锁问题求解

针对传统单种群进化类算法(conventional evolutionary algorithms,简称CEAs)求解基因连锁问题的不足,基于生物界共同进化机制提出求解NK基因连锁问题的合作式共同进化算法(Coevolutionary algorithm,简称CoEA),探讨其子种群的合作方式与个体适应值的计算方法,并从数学上分析该算法的性能,指出共同进化算法中高于平均适应值模式的递增指数高于传统单种群进化算法.仿真结果证实了理论分析.结果表明,共同进化算法比传统单种群进化算法对求解基因连锁问题的效力和效     

A Competitive-Cooperative Coevolutionary Paradigm for Dynamic Multiobjective Optimization

In addition to the need for satisfying several competing objectives, many real-world applications are also dynamic and require the optimization algorithm to track the changing optimum over time. This paper proposes a new coevolutionary paradigm that hybridizes competitive and cooperative mechanisms observed in nature to solve multiobjective optimization problems and to track the Pareto front in a dynamic environment. The main idea of competitive-cooperative coevolution is to allow the decomposition process of the optimization problem to adapt and emerge rather than being hand designed and fixed at the start of the evolutionary optimization process. In particular, each species subpopulation will compete to represent a particular subcomponent of the multiobjective problem, while the eventual winners will cooperate to evolve for better solutions. Through such an iterative process of competition and cooperation, the various subcomponents are optimized by different species subpopulations based on the optimization requirements of that particular time instant, enabling the coevolutionary algorithm to handle both the static and dynamic multiobjective problems. The effectiveness of the competitive-cooperation coevolutionary algorithm (COEA) in static environments is validated against various multiobjective evolutionary algorithms upon different benchmark problems characterized by various difficulties in local optimality, discontinuity, nonconvexity, and high-dimensionality. In addition, extensive studies are also conducted to examine the capability of dynamic COEA (dCOEA) in tracking the Pareto front as it changes with time in dynamic environments.      

Supply Estimation Using Coevolutionary Genetic Algorithms in the Spanish Electrical Market

The price of electrical energy in Spain has not been regulated by the government since 1998, but determined by the supply from the generators in a competitive market, the so-called electrical pool. A genetic method for analyzing data from this new market is presented in this paper. The eventual objective is to determine the individual supply curves of the competitive agents. Adopting the point of view of the game theory, different genetic algorithm configurations using coevolutionary and non-coevolutionary strategies combined with scalar and multi-objective fitness are compared. The results obtained are the first step toward solving the induction of the optimal individual strategies into the Spanish electrical market from data in terms of perfect oligopolistic behavior.     

Comparison between two coevolutionary feature weighting algorithms in clustering

Feature weighting is an aspect of increasing importance in clustering because data are becoming more and more complex nowadays. In this paper, we propose two new feature weighting methods based on coevolutive algorithms. The first one is inspired by the Lamarck theory (inheritance of acquired characteristics) and uses the distance-based cost function defined in the LKM algorithm as fitness function. The second method uses a fitness function based on a new partitioning quality measure. It does not need a distance-based measure. We compare classical hill-climbing optimization with these new genetic algorithms on three data sets from UCI. Results show that the proposed methods are better than the hill-climbing based algorithms. We also present a process of hyperspectral remotely sensed image classification. The experiments, corroborated by geographers, highlight the benefits of using coevolutionary feature weighting methods to improve knowledge discovery process.     

Fitness function shaping in multiagent cooperative coevolutionary algorithms

Coevolution is a promising approach to evolve teams of agents which must cooperate to achieve some system objective. However, in many coevolutionary approaches, credit assignment is often subjective and context dependent, as the fitness of an individual agent strongly depends on the actions of the agents with which it collaborates. In order to alleviate this problem, we introduce a cooperative coevolutionary algorithm which biases the evolutionary search as well as shapes agent fitness functions to promote behavior that benefits the system-level performance. More specifically, we bias the search using a hall of fame approximation of optimal collaborators, and shape the agent fitness using the difference evaluation function. Our results show that shaping agent fitness with the difference evaluation improves system performance by up to 50 %, and adding an additional fitness bias improves performance by up to 75 % in our experiments. Finally, an analysis of system performance as a function of computational cost demonstrates that this algorithm makes extremely efficient use of computational resources, having a higher performance as a function of computational cost than any other algorithm tested.     

Implicit representation in genetic algorithms using redundancy

A new representation combining redundancy and implicit fitness constraints is introduced that performs better than a simple genetic algorithm (GA) and a structured GA in experiments. The implicit redundant representation (IRR) consists of a string that is over-specified, allowing for sections of the string to remain inactive during function evaluation. The representation does not require the user to prespecify the number of parameters to evaluate or the location of these parameters within the string. This information is obtained implicitly by the fitness function during the GA operations. The good performance of the IRR can be attributed to several factors: less disruption of existing fit members due to the increased probability of crossovers and mutation affecting only redundant material; discovery of fit members through the conversion of redundant material into essential information; and the ability to enlarge or reduce the search space dynamically by varying the number of variables evaluated by the fitness function. The IRR GA provides a more biologically parallel representation that maintains a diverse population throughout the evolution process. In addition, the IRR provides the necessary flexibility to represent unstructured problem domains that do not have the explicit constraints required by fixed representations.     

Environmental effects on the coevolution of pursuit and evasion strategies

The game of tag is frequently used in the study of pursuit and evasion strategies that are discovered through competitive coevolution. The aim of coevolution is to create an arms race where opposing populations cyclically evolve in incremental improvements, driving the system towards better strategies. A coevolutionary simulation of the game of tag involving two populations of agents; pursuers and evaders, is developed to investigate the effects of a boundary and two obstacles. The evolution of strategies through Chemical Genetic Programming optimizes the mapping of genotypic strings to phenotypic trees. Four experiments were conducted, distinguished by speed differentials and environmental conditions. Designing experiments to evaluate the efficacy of emergent strategies often reveal necessary steps needed for coevolutionary progress. The experiments that excluded obstacles and boundaries provided design pointers to ensure coevolutionary progress as well as a deeper understanding of strategies that emerged when obstacles and boundaries were added. In the latter, we found that an awareness of the environment and the pursuer was not critical in an evader’s strategy to survive, instead heading to the edge of the boundary or behind an obstacle in a bid to ‘throw-off or hide from the pursuer’ or simply turn in circles was often sufficient, thereby revealing possible suboptimal strategies that were environment specific. We also observed that a condition for coevolutionary progress was that the problem complexity must be surmountable by at least one population; that is, some pursuer must be able to tag an opponent. Due to the use of amino-acid building blocks in our Chemical Genetic Program, our simulations were able to achieve significant complexity in a short period of time.

Coevolution of multiple species through niche construction modifying shared environments

Niche construction is a process whereby organisms, through their metabolism, activities, and choices, modify their own and/or each other’s niches. Our purpose is to clarify the interactions between evolution and niche construction by focusing on non-linear interactions between genetic and environmental factors shared by interacting species. We constructed a new fitness landscape model termed the NKES model by introducing environmental factors and their interactions with genetic factors into Kauffman’s NKCS model. The evolutionary experiments were conducted using hill-climbing and niche-constructing processes on this landscape. The results have shown that the average fitness among species strongly depends on the ruggedness of the fitness landscape (K) and the degree of the effect of niche construction on genetic factors (E). Especially, we observed two different roles of niche construction: moderate perturbations on hill-climbing processes on the rugged landscapes, and the strong constraint which yields the convergence to a stable state. Also, we show that the difference in the structures of (direct or indirect) interactions among species drastically changes the coevolutionary process of the whole ecosystem by comparing the evolutionary dynamics of the NKES model with that of the NKCS model.     

双精英协同进化遗传算法

针对传统遗传算法早熟收敛和收敛速度慢的问题,提出一种双精英协同进化遗传算法(double elite coevolutionary genetic algorithm,简称DECGA).该算法借鉴了精英策略和协同进化的思想,选择两个相异的、高适应度的个体(精英个体)作为进化操作的核心,两个精英个体分别按照不同的评价函数来选择个体,组成各自的进化子种群.两个子种群分别采用不同的进化策略,以平衡算法的勘探和搜索能力.理论分析证明,该算法具有全局收敛性.通过对测试函数的实验,其结果表明,该算法能搜索到几乎所有测试函数的最优解,同时能够有效地保持种群的多样性.与已有算法相比,该算法在收敛速度和搜索全局最优解上都有了较大的改进和提高.     

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.     

M-精英协同进化数值优化算法

为了解决高维无约束数值优化问题,借鉴协同进化和精英策略的思想,提出了M-精英协同进化算法.该算法认为,适应度较高的个体群(称为精英种群)在整个种群进化中起着主导作用.算法将整个种群划分为由M个精英组成的精英种群和由其余个体组成的普通种群这样两个子种群,依次以M个精英为核心(称为核心精英)来选择成员以组建M个团队.若选中的团队成员是其他精英,则该成员与核心精英利用所定义的协作操作来交换信息;若团队成员选自普通种群,则由核心精英对其进行引导操作.其中,协作操作和引导操作由若干不同类型的交叉或变异算子的组合所定义.理论分析证明,算法以概率1收敛于全局最优解.对15个标准测试函数进行的测试显示,该算法能够找到其中几乎所有被测函数的最优解或好的次优解.与3个已有的算法相比,在评价次数相同时,该算法所求解的精度更高.同时,该算法的运行时间较短,甚至略短于同等设置下的标准遗传算法.此外,对参数的实验分析显示,该算法对参数不敏感,易于使用.     

A Tournament-Based Competitive Coevolutionary Algorithm

For an efficient competitive coevolutionary algorithm, it is important that competing populations be capable of maintaining a coevolutionary balance and hence, continuing evolutionary arms race to increase the levels of complexity. We propose a competitive coevolutionary algorithm that combines the strategies of neighborhood-based evolution, entry fee exchange tournament competition (EFE-TC) and localized elitism. An emphasis is placed on analyzing the effects of these strategies on the performance of competitive coevolutionary algorithms. We have tested the proposed algorithm with two adversarial problems: sorting network and Nim game problems that have different characteristics. The experimental results show that the interacting effects of the strategies appear to promote a balanced evolution between host and parasite populations, which naturally leads them to keep on evolutionary arms race. Consequently, the proposed algorithm provides good quality solutions with a little computation time.     

Solving the balance problem of massively multiplayer online role-playing games using coevolutionary programming

In massively multiplayer online role-playing games (MMORPGs), each race holds some attributes and skills. Each skill contains several abilities such as physical damage and hit rate. All those attributes and abilities are functions of the character's level, which are called Ability-Increasing Functions (AIFs). A well-balanced MMORPG is characterized by having a set of well-balanced AIFs. In this paper, we propose a coevolutionary design method, including integration with the modified probabilistic incremental program evolution (PIPE) and the cooperative coevolutionary algorithm (CCEA), to solve the balance problem of MMORPGs. Moreover, we construct a simplest turn-based game model and perform a series of experiments based on it. The results indicate that the proposed method is able to obtain a set of well-balanced AIFs more efficiently, compared with the simple genetic algorithm (SGA), the simulated annealing algorithm (SAA) and the hybrid discrete particle swarm optimization (HDPSO) algorithm. The results also show that the performance of PIPE has been significantly improved through the modification works.     

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.     

Solution of multiobjective optimization problems: coevolutionary algorithm based on evolutionary game theory

When attempting to solve multiobjective optimization problems (MOPs) using evolutionary algorithms, the Pareto genetic algorithm (GA) has now become a standard of sorts. After its introduction, this approach was further developed and led to many applications. All of these approaches are based on Pareto ranking and use the fitness sharing function to keep diversity. On the other hand, the scheme for solving MOPs presented by Nash introduced the notion of Nash equilibrium and aimed at solving MOPs that originated from evolutionary game theory and economics. Since the concept of Nash Equilibrium was introduced, game theorists have attempted to formalize aspects of the evolutionary equilibrium. Nash genetic algorithm (Nash GA) is the idea to bring together genetic algorithms and Nash strategy. The aim of this algorithm is to find the Nash equilibrium through the genetic process. Another central achievement of evolutionary game theory is the introduction of a method by which agents can play optimal strategies in the absence of rationality. Through the process of Darwinian selection, a population of agents can evolve to an evolutionary stable strategy (ESS). In this article, we find the ESS as a solution of MOPs using a coevolutionary algorithm based on evolutionary game theory. By applying newly designed coevolutionary algorithms to several MOPs, we can confirm that evolutionary game theory can be embodied by the coevolutionary algorithm and this coevolutionary algorithm can find optimal equilibrium points as solutions for an MOP. We also show the optimization performance of the co-evolutionary algorithm based on evolutionary game theory by applying this model to several MOPs and comparing the solutions with those of previous evolutionary optimization models. This work was presented, in part, at the 8th International Symposium on Artificial Life and Robotics, Oita, Japan, January 24#x2013;26, 2003.     

Simple models of coevolutionary genetic algorithms

The use of evolutionary computing techniques in coevolutionary/multiagent systems is becoming increasingly popular. This paper presents some simple models of the genetic algorithm in such systems, with the aim of examining the effects of different types of interdependence between individuals. Using the models, it is shown that for a fixed amount of interdependence between homogeneous coevolving individuals, the existence of partner gene variance, gene symmetry, and the level at which fitness is applied can have significant effects. Similarly, for heterogeneous coevolving systems with fixed interdependence, partner gene variance and fitness application are also found to have a significant effect, as is the partnering strategy used.     

Behavioral diversity, choices and noise in the iterated prisoner's dilemma

Real-world dilemmas rarely involve just two choices and perfect interactions without mistakes. In the iterated prisoner's dilemma (IPD) game, intermediate choices or mistakes (noise) have been introduced to extend its realism. This paper studies the IPD game with both noise and multiple levels of cooperation (intermediate choices) in a coevolutionary environment, where players can learn and adapt their strategies through an evolutionary algorithm. The impact of noise on the evolution of cooperation is first examined. It is shown that the coevolutionary models presented in this paper are robust against low noise (when mistakes occur with low probability). That is, low levels of noise have little impact on the evolution of cooperation. On the other hand, high noise (when mistakes occur with high probability) creates misunderstandings and discourages cooperation. However, the evolution of cooperation in the IPD with more choices in a coevolutionary learning setting also depends on behavioral diversity. This paper further investigates the issue of behavioral diversity in the coevolution of strategies for the IPD with more choices and noise. The evolution of cooperation is more difficult to achieve if a coevolutionary model with low behavioral diversity is used for IPD games with higher levels of noise. The coevolutionary model with high behavioral diversity in the population is more resistant to noise. It is shown that strategy representations can have a significant impact on the evolutionary outcomes because of different behavioral diversities that they generate. The results further show the importance of behavioral diversity in coevolutionary learning.     

复杂模糊分类系统的协同进化设计方法

提出一种基于协同进化算法的复杂模糊分类系统的设计方法．该方法由以下3步组成:1)利用Simba算法进行特征变量选择;2)采用模糊聚类算法辨识初始的模糊模型;3)利用协同进化算法对所获得的初始模糊模型进行结构和参数的优化．协同进化算法由三类种群组成;规则数种群,规则前件种群和隶属函数种群;其适应度函数同时考虑模型的精确性和解释性,采用三类种群合作计算的策略．利用该方法对多个典型问题进行分类,仿真结果验证了方法的有效性．