解排列优化的整数编码多智能体进化算法

为解排列优化问题,在多智能体进化算法的基础上,提出一种整数编码的多智能体进化算法。重新定义了竞争算子和自学习算子。在网格内,智能体与周围的8个智能体构成竞争域,优胜智能体将编码段植入失败智能体,只有优胜者能获得自学习机会,自学习算子中智能体通过两种编码段换位方式来提升能量。使用本算法在旅行商问题典型数据上进行测试,与现有文献比较,表明该算法具有更好的全局寻优能力而且收敛稳定性更好。     

项目优化调度的多智能体社会进化算法

结合多智能体系统、进化算法以及关系网模型,提出了一种多智能体社会进化算法用于求解项目活动的一个最优调度顺序以使整个工程的工期最短,每个智能体生存于环境中,为了增加自身能量将与其邻域展开竞争及协同操作,同时可利用自身的知识进行自学习来增加能量,根据项目优化调度的问题特点,设计了智能体的竞争行为、协同行为以及自学习行为,通过对PSPLIB中的标准问题进行测试,同时与其他启发式算法相比较的仿真实验结果表明该算法具有良好的性能,能在较短的时间内寻找到十分接近"最优解"的调度序列.     

求解SAT问题的多智能体社会进化算法

基于Agent社会合作机制以及智能体对环境的感知和反作用能力提出了一种新的求解SAT问题的多智能体社会进化方法MASEA(Multi-Agent Social Evolutionary Algorithm).该方法在多智能体进化思想的基础上,引入人类社会"关系网模型"的概念来建立智能体所能感知的邻域环境;同时在保留原有的竞争算子和自学习算子前提下,根据智能体具有竞争协作的特性,设计了一个新的算子——协作算子来共同完成整个进化过程.以标准SATLIB库中变量个数从20~250的3700个不同规模的标准SAT问题以及基于RB模型所产生的随机实例对MASEA的性能进行了全面的测试,并与其他一些具有较高性能算法的结果进行了比较.结果表明,MASEA具有更高的成功率和更高的运算效率.     

组合优化多智能体进化算法

提出了一种新的组合优化方法——组合优化多智能体进化算法．该方法将智能体固定在网格上，而每个智能体为了增加自身能量将与其邻域展开竞争，同样智能体也可进行自学习来增加能量．理论分析证明算法具有全局收敛性．在实验中，作者分别用强联接、弱联接、重叠联接等各种类型的欺骗函数对算法的性能进行了全面的测试，并将算法用于解决具有树状等级结构的问题．比较结果表明文中算法所需的计算量远远小于其它方法，具有较快的收敛速度．为了测试算法解决大规模问题的能力，作者还将算法用于解决上千维的欺骗问题和等级问题，结果表明该文算法的计算复杂度与问题规模成多项式的关系．此外，将算法用于上千维的欺骗问题和等级问题，在国内外还均未见报到．     

多智能体入侵杂草算法

针对标准入侵杂草算法缺乏信息共享机制的缺陷,将多智能体系统融入标准入侵杂草算法,提出了一种新的多智能体入侵杂草算法.该算法通过多智能体系统中改进的邻域竞争合作算子实现个体间信息的交流,提高收敛速率;利用多智能体系统中的自学习算子增强算法求解精度.五个基准函数测试对比分析结果表明,多智能体入侵杂草算法的求解精度、收敛速度和稳定性优于标准入侵杂草算法、粒子群算法和差分进化算法.     

基于智能体的多目标社会进化算法

提出了一种基于智能体的多目标社会进化算法用以求解多目标优化问题(multiobjective optimization problems,简称MOPs),通过多智能体进化的思想来完成Pareto 解集的寻优过程.该方法定义可信任度来表示智能体间的历史活动信息,并据此确定智能体的邻域、控制智能体间的行为.针对多目标问题的特点,设计了3 个进化算子分别体现适者生存、弱肉强食、多样性原则以及自学习的特性.同时采用擂台赛法则构造Pareto 解的存储种群.仿真实验结果表明,该算法能够较好地收敛到Pareto 最优解集上,并且具有良好的多样性.另外,通过对智能体局部邻域环境建立方式的分析结果表明引入“关系网模型”可有效提高算法的收敛速度,并能在一定程度上提高解的质量.     

多智能体差分进化算法

基于多智能体与差分进化算法的各自优势,充分地将对多智能体环境的感知和反作用于环境的能力与差分进化速度和全局寻优能力有机结合,提出一种多智能体差分进化算法.引入差分进化算子以提高智能体更新速度并保持群体多样性,同时应用正交交叉算子以改善智能体协作特性确保有效竞争,并通过局部寻优算子提高算法的寻优精度.对几种典型测试函数进行了测试,实验结果表明所提出的算法具有较强的全局寻优能力.     

链式多种群多智能体进化算法

将多种群的进化方式和链式结构的动态邻域引入到多智能体进化算法中,提出了一种链式多种群多智能体进化算法.算法设置了多种群交互的演化结构.各种群中的智能体通过与其动态邻域智能体的竞争、合作及自学习操作来增加自身的能量;动态邻域的链式结构提高了算法的效率、降低了计算复杂度;多个种群之间的信息定期以一定的方式进行交互,增强了种群的多样性,减小了算法陷入局部最优的机率.理论分析和多个测试函数的仿真结果均表明:链式多种群多智能体进化算法在求解高维优化问题上具有很好的性能.     

多智能体遗传算法用于线性系统逼近

提出了一种新的参数优化方法--多智能体遗传算法,来求解线性系统逼近问题. 该方法中每个智能体代表一个候选解,即搜索空间中的一个实值向量.所有智能体生存在一 个网格状的环境中,且每个智能体占据一个格点不能移动.为了增加能量,它们将与其邻域 进行合作或竞争,也可以利用自身的知识.因此,设计了4个进化算子来模拟智能体间的竞 争、合作、自学习等行为.该方法利用这些智能体与智能体间的相互作用来达到优化逼近模 型中参数的目的;此外,还采用了一种动态扩展搜索空间的方法以解决算法所需的搜索空间 难以确定的问题.实验中,利用一个稳定和一个非稳定的线性系统逼近问题来验证算法的性 能,并与两种新近提出的方法作了比较.结果表明,该文方法优于其它方法,能够用较少的计 算量找到高质量的逼近模型,具有良好的性能和实际应用价值.     

密度敏感的多智能体进化聚类算法

采用密度敏感距离作为数据相似性度量,并基于多智能体进化的思想提出了一种密度敏感的多智能体进化聚类(density sensitive based multi-agent evolutionary clustering,简称DSMAEC)算法.算法设计了一种基于连接的编码方式,通过解码过程可直接得到最终的聚类结果,无需事先确定聚类类别数,有效地克服了对领域知识的依赖.针对聚类问题,设计了3个有效的进化算子来模拟智能体间的竞争、合作和自学习行为,共同完成智能体的进化,最终达到对数据聚类的目的.分别对人工数据集、UCI数据集以及合成纹理图像进行仿真,实验结果表明,该算法不但可以自动确定聚类类别数,而且能够应付不同结构的数据,适应不同的聚类要求,具有较强的实用价值.     

Design of coordination strategies in multiagent systems via genetic fuzzy systems

This paper suggests an evolutionary approach to design coordination strategies for multiagent systems. Emphasis is given to auction protocols since they are of utmost importance in many real world applications such as power markets. Power markets are one of the most relevant instances of multiagent systems and finding a profitable bidding strategy is a key issue to preserve system functioning and improve social welfare. Bidding strategies are modeled as fuzzy rule-based systems due to their modeling power, transparency, and ability to naturally handle imprecision in input data, an essential ingredient to a multiagent system act efficiently in practice. Specific genetic operators are suggested in this paper. Evolution of bidding strategies uncovers unknown and unexpected agent behaviors and allows a richer analysis of auction mechanisms and their role as a coordination protocol. Simulation experiments with a typical power market using actual thermal plants data show that the evolutionary, genetic-based design approach evolves strategies that enhance agents profitability when compared with the marginal cost-based strategies commonly adopted     

A Multiagent Evolutionary Method for Detecting Communities in Complex Networks

Community structure detection in complex networks contributes greatly to the understanding of complex mechanisms in many fields. In this article, we propose a multiagent evolutionary method for discovering communities in a complex network. The focus of the method lies in the evolutionary process of computational agents in a lattice environment, where each agent corresponds to a candidate solution to the community detection problem. First, the method uses a connection‐based encoding scheme to model an agent and a random‐walk behavior to construct a solution. Next, it applies three evolutionary operators, i.e., competition, crossover, and mutation, to realize information exchange among agents and solution evolution. We tested the performance of our method using synthetic and real‐world networks. The results show its capability in effectively detecting community structures.     

一种改进的求解TSP问题的演化算法

演化算法是解决组合优化问题的高效搜索算法．该文在现有求解TSP问题的演化算法的基础上，通过引入映射算子、优化算子以及增加一些控制策略，提出了一种高效的演化搜索算法．实验表明，该算法是有效的，通过对CHN144以及国际通用的TSPLIB中不同城市规模的数据进行测试表明，其中实例CHN144得到的最短路径为30353．860997，优于吴斌等运用分段算法得到的最短路径30354．3，亦优于朱文兴等人的结果，实例st70和kroB150得到的最短路径分别与运用分段算法得到的最短路径值相同，实例pr136得到的最短路径值为96770．924122，优于TSPLIB中提供的最短路径96772，对于其它实例也均能快速地得到和TSPLIB中提供的最优路径相同或更优的路径，该算法不仅很容易收敛到问题的最优解，而且求解速度极快．     

Multiagent based differential evolution approach to optimal power flow

This paper proposes a new differential evolution approach named as multiagent based differential evolution (MADE) based on multiagent systems, for solving optimal power flow problem with non-smooth and non-convex generator fuel cost curves. This method integrates multiagent systems (MAS) and differential evolution (DE) algorithm. An agent in MADE represents an individual to DE and a candidate solution to the optimization problem. All agents live in a lattice like environment, with each agent fixed on a lattice point. In order to obtain optimal solution quickly, each agent competes and cooperates with its neighbors and it can also use knowledge. Making use of these agent-agent interaction and DE mechanism, MADE realizes the purpose of minimizing the value of objective function. MADE applied to optimal power flow is evaluated on 6 bus system and IEEE 30 bus system with different generator characteristics. Simulation results show that the proposed method converges to better solutions much faster than earlier reported approaches.     

组织进化算法求解SAT问题

基于组织的概念设计了一种新的进化算法——求解SAT问题的组织进化算法(Organizational Evolutionary Algorithm for SAT problem，0EASAT)．OEASAT将SAT问题分解成若干子问题，然后用每个子问题形成一个组织，并根据SAT问题的特点设计了三种组织进化算子——自学习算子、吞并算子和分裂算子以引导组织的进化．根据组织的适应度，将所有组织分成两个种群——最优种群和非最优种群，然后用进化的方式来控制各算子，以协调各组织间的相互作用．OEASAT通过先解决子问题，再协调相冲突变量的方式来求解SAT问题．由于子问题的规模较小，相对于原问题来说较容易解决，这样就达到了降低问题复杂度的目的．实验用标准SATLIB库中变量个数从20-250的3700个不同规模的标准SAT问题对OEASAT的性能作了全面的测试，并与著名的WalkSAT和RFEA2的结果作了比较．结果表明，OEASAT具有更高的成功率和更高的运算效率．对于具有250个变量、1065个子句的SAT问题，OEASAT仅用了1．524s，表现出了优越的性能．     

Genetic fuzzy systems to evolve interaction strategies in multiagent systems

This article suggests an evolutionary approach to designing interaction strategies for multiagent systems, focusing on strategies modeled as fuzzy rule‐based systems. The aim is to learn models evolving database and rule bases to improve agent performance when playing in a competitive environment. In competitive situations, data for learning and tuning are rare, and rule bases must jointly evolve with the databases. We introduce an evolutionary algorithm whose operators use variable length chromosomes, a hierarchical relationship among individuals through fitness, and a scheme that successively explores and exploits the search space along generations. Evolution of interaction strategies uncovers unknown and unexpected agent behaviors and allows a richer analysis of negotiation mechanisms and their role as a coordination protocol. An application concerning an electricity market illustrates the effectiveness of the approach. © 2007 Wiley Periodicals, Inc. Int J Int Syst 22: 971–991, 2007.     

用于求解混合车辆路径问题的混合进化算法

文中研究了具有NP难度的混合车辆路径问题(Mixed Capacitated General Routing Problem,MCGRP),其是在基本车辆路径问题(Vehicle Routing Problem,VRP)的基础上通过添加限载容量约束及弧上的用户需求而衍生的。给定一列车辆数不限的车队,使车辆从站点出发向用户提供服务,服务完用户需求后仍返回站点;规定每辆车的总载重不能超过其载重量,且每个需求只能被一辆车服务且仅服务一次。MCGRP旨在求解每辆车的服务路线,使得在满足以上约束条件的情况下所有车辆的旅行消耗之和最小。混合车辆路径问题具有较高的理论价值和实际应用价值,针对该问题提出了一种高效的混合进化算法。该算法采用基于5种邻域算符的变邻域禁忌搜索来提高解的质量,并通过一种基于路径的交叉算符来继承解的优异性,从而有效地加速算法的收敛。在一组共计23个经典算例上的实验结果表明,该混合进化算法在求解混合车辆路径问题时是非常高效的。     

Fitness landscape analysis and memetic algorithms for the quadratic assignment problem

In this paper, a fitness landscape analysis for several instances of the quadratic assignment problem (QAP) is performed, and the results are used to classify problem instances according to their hardness for local search heuristics and meta-heuristics based on local search. The local properties of the fitness landscape are studied by performing an autocorrelation analysis, while the global structure is investigated by employing a fitness distance correlation analysis. It is shown that epistasis, as expressed by the dominance of the flow and distance matrices of a QAP instance, the landscape ruggedness in terms of the correlation length of a landscape, and the correlation between fitness and distance of local optima in the landscape together are useful for predicting the performance of memetic algorithms-evolutionary algorithms incorporating local search (to a certain extent). Thus, based on these properties, a favorable choice of recombination and/or mutation operators can be found. Experiments comparing three different evolutionary operators for a memetic algorithm are presented.     

Improved heuristics for the bounded-diameter minimum spanning tree problem

Given an undirected, connected, weighted graph and a positive integer k, the bounded-diameter minimum spanning tree (BDMST) problem seeks a spanning tree of the graph with smallest weight, among all spanning trees of the graph, which contain no path with more than k edges. In general, this problem is NP-Hard for 4 ≤ k < n − 1, where n is the number of vertices in the graph. This work is an improvement over two existing greedy heuristics, called randomized greedy heuristic (RGH) and centre-based tree construction heuristic (CBTC), and a permutation-coded evolutionary algorithm for the BDMST problem. We have proposed two improvements in RGH/CBTC. The first improvement iteratively tries to modify the bounded-diameter spanning tree obtained by RGH/CBTC so as to reduce its cost, whereas the second improves the speed. We have modified the crossover and mutation operators and the decoder used in permutation-coded evolutionary algorithm so as to improve its performance. Computational results show the effectiveness of our approaches. Our approaches obtained better quality solutions in a much shorter time on all test problem instances considered.     

Course timetabling using evolutionary operators

Timetabling is the problem of scheduling a set of events while satisfying various constraints. In this paper, we develop and study the performance of an evolutionary algorithm, designed to solve a specific variant of the timetabling problem. Our aim here is twofold: to develop a competitive algorithm, but more importantly, to investigate the applicability of evolutionary operators to timetabling. To this end, the introduced algorithm is tested using a benchmark set. Comparison with other algorithms shows that it achieves better results in some, but not all instances, signifying strong and weak points. To further the study, more comprehensive tests are performed in connection with another evolutionary algorithm that uses strictly group-based operators. Our analysis of the empirical results leads us to question single-level selection, proposing, in its place, a multi-level alternative.