Liu Jing, Zhong Weicai, Jiao Licheng
Institute of Intelligent Information Processing, Xidian University, Xi'an 710071, China.
IEEE Trans Syst Man Cybern B Cybern. 2010 Feb;40(1):229-40. doi: 10.1109/TSMCB.2009.2025775. Epub 2009 Jul 28.
Based on our previous works, multiagent systems and evolutionary algorithms (EAs) are integrated to form a new algorithm for combinatorial optimization problems (CmOPs), namely, MultiAgent EA for CmOPs (MAEA-CmOPs). In MAEA-CmOPs, all agents live in a latticelike environment, with each agent fixed on a lattice point. To increase energies, all agents compete with their neighbors, and they can also increase their own energies by making use of domain knowledge. Theoretical analyses show that MAEA-CmOPs converge to global optimum solutions. Since deceptive problems are the most difficult CmOPs for EAs, in the experiments, various deceptive problems with strong linkage, weak linkage, and overlapping linkage, and more difficult ones, namely, hierarchical problems with treelike structures, are used to validate the performance of MAEA-CmOPs. The results show that MAEA-CmOP outperforms the other algorithms and has a fast convergence rate. MAEA-CmOP is also used to solve large-scale deceptive and hierarchical problems with thousands of dimensions, and the experimental results show that MAEA-CmOP obtains a good performance and has a low computational cost, which the time complexity increases in a polynomial basis with the problem size.
基于我们之前的工作，多智能体系统和进化算法（EAs）被集成起来，形成了一种用于组合优化问题（CmOPs）的新算法，即用于CmOPs的多智能体进化算法（MAEA-CmOPs）。在MAEA-CmOPs中，所有智能体生活在一个类似晶格的环境中，每个智能体固定在一个晶格点上。为了增加能量，所有智能体与其邻居竞争，并且它们还可以通过利用领域知识来增加自身的能量。理论分析表明，MAEA-CmOPs收敛于全局最优解。由于欺骗性问题是进化算法最难处理的CmOPs，在实验中，使用了各种具有强链接、弱链接和重叠链接的欺骗性问题，以及更难的问题，即具有树状结构的分层问题，来验证MAEA-CmOPs的性能。结果表明，MAEA-CmOP优于其他算法，并且具有快速的收敛速度。MAEA-CmOP还被用于解决具有数千维的大规模欺骗性和分层问题，实验结果表明，MAEA-CmOP获得了良好的性能，并且计算成本较低，其时间复杂度随问题规模以多项式形式增加。
