A multiagent evolutionary algorithm with direct and indirect combined representation for constraint satisfaction problems

详细信息    查看全文

• 作者：Xingxing Hao ; Jing Liu
• 关键词：Constraint satisfaction problem ; Direct representation ; Indirect representation ; Direct and indirect combined representation ; Multiagent evolutionary algorithm
• 刊名：Soft Computing
• 出版年：2017
• 出版时间：February 2017
• 年：2017
• 卷：21
• 期：3
• 页码：781-793
• 全文大小：
• 刊物类别：Engineering
• 刊物主题：Computational Intelligence; Artificial Intelligence (incl. Robotics); Mathematical Logic and Foundations; Control, Robotics, Mechatronics;
• 出版者：Springer Berlin Heidelberg
• ISSN：1433-7479
• 卷排序：21

文摘

The evolutionary algorithms (EAs) became more and more important in solving NP-hard problems in recent years. The representation of specific problems in EAs is very important and it has a great influence on the performance of EAs. The constraint satisfaction problems (CSPs) are typical NP-hard problems and the representation of CSPs can be traditionally divided into two types, namely the direct and indirect representations. The variables in direct representation represent the actual values that they can take, and can be evaluated directly. Whereas in indirect representation, a specific permutation is assigned to variables, and the individual is incapable of being evaluated without a decoder. In order to take advantage of both representations to enforce the ability of EAs in solving CSPs, we propose a combination of these two representations in this article. The minimum conflict decoder is employed to transform indirect representation to direct representation and several new behaviors are designed for agents in multiagent evolutionary algorithms. In experiments, 250 benchmark binary CSPs and 79 graph coloring problems are tested. The comparisons among the direct, indirect and the combined representation methods are conducted. Experimental results illustrate that the method of combined representation outperforms the two other methods.