协同演化算法研究进展

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

双精英协同进化遗传算法

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

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

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

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.     

分布式进化算法的性能测试与分析

针对分布式进化算法设计过程中由于缺乏对性能影响因素的分析而导致算法无法达到预期加速比的问题,提出一种全面的性能分析方法。根据分布式进化算法的组成结构,将影响分布式进化算法性能的因素分为进化操作开销、适应值计算开销和通信开销三个部分。首先研究进化算法在不同个体编码维数下进化操作开销的特性;其次,在进化操作开销相对固定的情况下,通过使用操作系统的延时函数控制适应值计算开销,通过改变个体编码维数控制通信开销;最后,应用控制变量方法,逐一测试各因素对算法加速比的影响。实验结果展现了三种因素的相互制约关系,给出了分布式进化算法获得更好加速比的条件。     

Multi-objective multiagent credit assignment in reinforcement learning and NSGA-II

Multiagent systems have had a powerful impact on the real world. Many of the systems it studies (air traffic, satellite coordination, rover exploration) are inherently multi-objective, but are often treated as single-objective problems within the research. A key concept within multiagent systems is that of credit assignment: quantifying an individual agent’s impact on the overall system performance. In this work,we extend the concept of credit assignment into multi-objective problems. We apply credit assignment through difference evaluations to two different policy selection paradigms to demonstrate their broad applicability. We first examine reinforcement learning, in which using difference evaluations improves performance by (i) increasing learning speed by up to 10\(\times \), (ii) producing solutions that dominate all solutions discovered by a traditional team-based credit assignment schema and (iii) losing only 0.61 % of dominated hypervolume in a scenario where 20 % of agents act in their own interests instead of the system’s interests (compared to a 43 % loss when using a traditional global reward in the same scenario). We then derive multiple methods for incorporating difference evaluations into a state-of-the-art multi-objective evolutionary algorithm, NSGA-II. Median performance of the NSGA-II considering credit assignment dominates best-case performance of NSGA-II not considering credit assignment in a multiagent multi-objective problem. Our results strongly suggest that in a multiagent multi-objective problem, proper credit assignment is at least as important to performance as the choice of multi-objective algorithm.     

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.     

异构集成代理辅助多目标粒子群优化算法

针对代理辅助进化算法在减少昂贵适应度评估时难以通过少量样本点构造高质量代理模型的问题,提出异构集成代理辅助多目标粒子群优化算法。该方法通过使用加权平均法将Kriging模型和径向基函数网络模型组合成高精度的异构集成模型,达到增强算法处理不确定性信息能力的目的。基于集成学习的两种代理模型分别应用于全局搜索和局部搜索,在多目标粒子群优化算法框架基础上,新提出的方法为每个目标函数自适应地构造了异构集成模型,利用其模型的非支配解来指导粒子群的更新,得出目标函数的最优解集。实验结果表明,所提方法提高了代理模型的搜索能力,减少了评估次数,并且随着搜索维度的增加,其计算复杂性也具有更好的可扩展性。     

基于分布式深度强化学习的微电网实时优化调度

随着海量新能源接入到微电网中, 微电网系统模型的参数空间成倍增长, 其能量优化调度的计算难度不断上升. 同时, 新能源电源出力的不确定性也给微电网的优化调度带来巨大挑战. 针对上述问题, 本文提出了一种基于分布式深度强化学习的微电网实时优化调度策略. 首先, 在分布式的架构下, 将主电网和每个分布式电源看作独立智能体. 其次, 各智能体拥有一个本地学习模型, 并根据本地数据分别建立状态和动作空间, 设计一个包含发电成本、交易电价、电源使用寿命等多目标优化的奖励函数及其约束条件. 最后, 各智能体通过与环境交互来寻求本地最优策略, 同时智能体之间相互学习价值网络参数, 优化本地动作选择, 最终实现最小化微电网系统运行成本的目标. 仿真结果表明, 与深度确定性策略梯度算法(Deep Deterministic Policy Gradient, DDPG)相比, 本方法在保证系统稳定以及求解精度的前提下, 训练速度提高了17.6%, 成本函数值降低了67%, 实现了微电网实时优化调度.     

Hybrid evolutionary algorithm with extreme machine learning fitness function evaluation for two-stage capacitated facility location problems

This paper considers the two-stage capacitated facility location problem (TSCFLP) in which products manufactured in plants are delivered to customers via storage depots. Customer demands are satisfied subject to limited plant production and limited depot storage capacity. The objective is to determine the locations of plants and depots in order to minimize the total cost including the fixed cost and transportation cost. However, the problem is known to be NP-hard. A practicable exact algorithm is impossible to be developed. In order to solve large-sized problems encountered in the practical decision process, an efficient alternative approximate method becomes more valuable. This paper aims to propose a hybrid evolutionary algorithm framework with machine learning fitness approximation for delivering better solutions in a reasonable amount of computational time. In our study, genetic operators are adopted to perform the search process and a local search strategy is used to refine the best solution found in the population. To avoid the expensive consumption of computational time during the fitness evaluating process, the framework uses extreme machine learning to approximate the fitness of most individuals. Moreover, two heuristics based on the characteristics of the problem is incorporated to generate a good initial population. Computational experiments are performed on two sets of test instances from the recent literature. The performance of the proposed algorithm is evaluated and analyzed. Compared with other algorithms in the literature, the proposed algorithm can find the optimal or near-optimal solutions in a reasonable amount of computational time. By employing the proposed algorithm, facilities can be positioned more efficiently, which means the fixed cost and the transportation cost can be decreased significantly, and organizations can enhance competitiveness by using the optimized facility location scheme.     

Binary quantum-inspired gravitational search algorithm-based multi-criteria scheduling for multi-processor computing systems

A quantum-inspired hybrid scheduling technique is proposed for multi-processor computing systems. The proposed algorithm is a hybridization of principles of quantum mechanics (QM) and a nature-inspired intelligence, gravitational search algorithm (GSA). The principles of QM such as quantum bit, superposition and rotation gate help to design an efficient agent representation as well as intense exploration capability of GSA enhances toward better converging rate. The fitness function is designed with the aim to minimize makespan, adequate balancing of loads and proper utilization of the deployed resources during the evaluation of agents. Several standard benchmarks as well as synthetic data sets are used to analyze and validate the work. The performance improvement of the proposed algorithm is compared with recently designed algorithms like quantum genetic algorithm, particle swarm optimization-based multi-criteria scheduling, Improved-GA, GSA and Cloudy-GSA. The significance of the algorithm is tested using a hypothesis analysis of variance.

     

An efficient differential evolution using speeded-up k-nearest neighbor estimator

In evolutionary algorithm, one of the main issues is how to reduce the number of fitness evaluations required to obtain optimal solutions. Generally a large number of evaluations are needed to find optimal solutions, which leads to an increase of computational time. Expensive cost may have to be paid for fitness evaluation as well. Differential evolution (DE), which is widely used in many applications due to its simplicity and good performance, also cannot escape from this problem. In order to solve this problem a fitness approximation model has been proposed so far, replacing real fitness function for evaluation. In fitness approximation, an ability to estimate accurate value with compact structure is needed for good performance. Therefore in this paper we propose an efficient differential evolution using fitness estimator. We choose k-nearest neighbor (kNN) as fitness estimator because it does not need any training period or complex computation. However too many training samples in the estimator may cause computational complexity to be exponentially high. Accordingly, two schemes with regard to accuracy and efficiency are proposed to improve the estimator. Our proposed algorithm is tested with various benchmark functions and shown to find good optimal solutions with less fitness evaluation and more compact size, compared with DE and DE-kNN.     

Block-matching algorithm based on harmony search optimization for motion estimation

Motion estimation is one of the major problems in developing video coding applications. Among all motion estimation approaches, Block-matching (BM) algorithms are the most popular methods due to their effectiveness and simplicity for both software and hardware implementations. A BM approach assumes that the movement of pixels within a defined region of the current frame can be modeled as a translation of pixels contained in the previous frame. In this procedure, the motion vector is obtained by minimizing a certain matching metric that is produced for the current frame over a determined search window from the previous frame. Unfortunately, the evaluation of such matching measurement is computationally expensive and represents the most consuming operation in the BM process. Therefore, BM motion estimation can be viewed as an optimization problem whose goal is to find the best-matching block within a search space. The simplest available BM method is the Full Search Algorithm (FSA) which finds the most accurate motion vector through an exhaustive computation of all the elements of the search space. Recently, several fast BM algorithms have been proposed to reduce the search positions by calculating only a fixed subset of motion vectors despite lowering its accuracy. On the other hand, the Harmony Search (HS) algorithm is a population-based optimization method that is inspired by the music improvisation process in which a musician searches for harmony and continues to polish the pitches to obtain a better harmony. In this paper, a new BM algorithm that combines HS with a fitness approximation model is proposed. The approach uses motion vectors belonging to the search window as potential solutions. A fitness function evaluates the matching quality of each motion vector candidate. In order to save computational time, the approach incorporates a fitness calculation strategy to decide which motion vectors can be only estimated or actually evaluated. Guided by the values of such fitness calculation strategy, the set of motion vectors is evolved through HS operators until the best possible motion vector is identified. The proposed method has been compared to other BM algorithms in terms of velocity and coding quality. Experimental results demonstrate that the proposed algorithm exhibits the best balance between coding efficiency and computational complexity.     

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.     

An effective subgradient algorithm for the generalized assignment problem

A modified subgradient algorithm is presented for the generalized assignment problem, which, like the classical assignment problem, is concerned with the minimum cost assignment of agents to jobs. The generalized assignment problem, however, permits differences in job performance efficiencies among agents and thereby allows the possibility that each agent may be assigned more than a single job, as long as each job is ultimately assigned and the total resources available to every agent are not exceeded. A two stage heuristic algorithm using a modified subgradient approach and branch and bound is developed for solving the problem. By computing step sizes precisely and using the dual as a bound, the algorithm is shown to be particularly effective and easy to program and implement. A numerical example is presented to illustrate the model and method, and computational experience is cited for problems containing up to 12,000 0–1 variables.     

A simple multimembered evolution strategy to solve constrained optimization problems

This work presents a simple multimembered evolution strategy to solve global nonlinear optimization problems. The approach does not require the use of a penalty function. Instead, it uses a simple diversity mechanism based on allowing infeasible solutions to remain in the population. This technique helps the algorithm to find the global optimum despite reaching reasonably fast the feasible region of the search space. A simple feasibility-based comparison mechanism is used to guide the process toward the feasible region of the search space. Also, the initial stepsize of the evolution strategy is reduced in order to perform a finer search and a combined (discrete/intermediate) panmictic recombination technique improves its exploitation capabilities. The approach was tested with a well-known benchmark. The results obtained are very competitive when comparing the proposed approach against other state-of-the art techniques and its computational cost (measured by the number of fitness function evaluations) is lower than the cost required by the other techniques compared.     

Biasing Coevolutionary Search for Optimal Multiagent Behaviors

Cooperative coevolutionary algorithms (CEAs) offer great potential for concurrent multiagent learning domains and are of special utility to domains involving teams of multiple agents. Unfortunately, they also exhibit pathologies resulting from their game-theoretic nature, and these pathologies interfere with finding solutions that correspond to optimal collaborations of interacting agents. We address this problem by biasing a cooperative CEA in such a way that the fitness of an individual is based partly on the result of interactions with other individuals (as is usual), and partly on an estimate of the best possible reward for that individual if partnered with its optimal collaborator. We justify this idea using existing theoretical models of a relevant subclass of CEAs, demonstrate how to apply biasing in a way that is robust with respect to parameterization, and provide some experimental evidence to validate the biasing approach. We show that it is possible to bias coevolutionary methods to better search for optimal multiagent behaviors     

Accelerated biogeography-based optimization with neighborhood search for optimization

Biogeography-based optimization (BBO) inherently lacks exploration capability that leads to slow convergence. To address this limitation, authors present a memetic algorithm (MA) named as aBBOmDE, which is a new variant of BBO. In aBBOmDE, the performance of BBO is accelerated with the help of a modified mutation and clear duplicate operators. Then modified DE (mDE) is embedded as a neighborhood search operator to improve the fitness from a predefined threshold. mDE is used with mutation operator DE/best/1/bin to explore the search near the best solution. The length of local search is a choice that balances between the search capability and the computational cost. In aBBOmDE, migration mechanism is kept same as that of BBO in order to maintain its exploitation ability. Modified operators are utilized to enhance the exploration ability while a neighborhood search operator further enhances the search capability of the algorithm. This combination significantly improves the convergence characteristics of the original algorithm. Extensive experiments have been carried out on forty benchmark functions to show the effectiveness of the proposed algorithm. The results have been compared with original BBO, DE, CMAES, other MA and DE/BBO, a hybrid version of DE and BBO. aBBOmDE is also applied to compute patch dimensions of rectangular microstrip patch antennas (MSAs) with various substrate thicknesses so as to be used a CAD formula for antenna design.     

正弦余弦指引的乌鸦搜索算法研究

乌鸦搜索算法模拟乌鸦觅食行为对个体位置进行更新与搜索，为降低基本乌鸦搜索位置更新策略本身存在的盲目性，将正弦余弦作为局部优化算子嵌入到基本算法中，提出了正弦余弦指引的乌鸦搜索算法。该算法通过正弦余弦操作使每一个乌鸦个体都可以充分吸收自身与最优个体的位置差信息，有效指引乌鸦个体沿最优值方向趋近最优值，改善算法的收敛效果和寻优精度。并对一系列测试函数进行寻优实验，实验结果表明该改进算法性能良好。     

A Swarm Intelligence inspired algorithm for contour detection in images

Swarm Intelligence uses a set of agents which are able to move and gather local information in a search space and utilize communication, limited memory, and intelligence for problem solving. In this work, we present an agent-based algorithm which is specifically tailored to detect contours in images. Following a novel movement and communication scheme, the agents are able to position themselves distributed over the entire image to cover all important image positions. To generate global contours, the agents examine the local windowed image information, and based on a set of fitness functions and via communicating with each other, they establish connections. Instead of a centralized paradigm, the global solution is discovered by some principal rules each agent is following. The algorithm is independent of object models or training steps. In our evaluation we focus on boundary detection as a major step towards image segmentation. We therefore evaluate our algorithm using the Berkeley Segmentation Dataset (BSDS) and compare its performance to existing methods via the BSDS benchmark and Pratt's Figure of Merit.