二进制编码差异演化算法在Agent联盟形成中的应用

A Binary-Encoding Differential Evolution Algorithm for Agent Coalition

在多Agent系统中,通过形成联盟可以提高Agent求解问题的能力,因此,联盟是多Agent系统的重要合作方法.从本质上讲,Agent联盟的形成是一个复杂的组合优化问题.引入差异演化算法来解决这一问题.差异演化是一种基于群体差异的演化算法,适合于求解连续空间的最优化问题.首次将以实数编码的差异演化算法应用于Agent联盟问题,提出二进制编码的差异演化算法解决组合优化问题,通过引入S型函数把变异操作的结果限制在集合{0,1}上,可以快速、高效地找出合适的Agent联盟.与遗传算法和蚁群算法的对比实验表明,该算法是正确、有效、可行的,在运行时间和解的性能上都优于相关算法.

In multi-agent systems, it can improve agent＇s abilities of problem solving to form coalition. So, coalition is an important cooperative method in multi-agent systems. But the number of the possible coalitions is exponential since each agent can form coalition with others. Essentially, forming agent coalition is a combinatorial optimization problem. As a modern optimization method, differential evolution （DE） introduced by Storn and Price in 1997 is one of the most successful evolutionary algorithms which are adopted to solve this problem. The original differential evolution which is based on the individual differential reconstruction idea is designed for the global continuous optimization problem. In order to solve the combinatorial optimization problem by DE, in this paper, a novel binary-encoding differential evolution （BDE） algorithm is presented and applied to find out agent coalition fast and efficiently. By using a Sigmoid function, the new algorithm constrains the result of mutation operator in { 0,1 }, so as to adopt the combinatorial optimization problem. Some simulations which include 30 agents have been achieved for the novel binary-encoding differential evolution, genetic algorithm （GA） and ant colony algorithm （ACA）. The experimental results show that the new algorithm is feasible and efficient. It is superior to other related methods such as GA and ACA both on the quality of solution and on the convergence rate.