DocumentCode :
1152442
Title :
A Multiagent Evolutionary Algorithm for Combinatorial Optimization Problems
Author :
Liu, Jing ; Zhong, Weicai ; Jiao, Licheng
Author_Institution :
Inst. of Intell. Inf. Process., Xidian Univ., Xi´´an, China
Volume :
40
Issue :
1
fYear :
2010
Firstpage :
229
Lastpage :
240
Abstract :
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.
Keywords :
combinatorial mathematics; computational complexity; evolutionary computation; multi-agent systems; CmOPs; MAEA-CmOPs; MultiAgent EA; combinatorial optimization problems; multiagent evolutionary algorithm; multiagent systems; polynomial basis; time complexity; Combinatorial optimization problems (CmOPs); deceptive problems; evolutionary algorithms (EAs); hierarchical problems; multiagent systems;
fLanguage :
English
Journal_Title :
Systems, Man, and Cybernetics, Part B: Cybernetics, IEEE Transactions on
Publisher :
ieee
ISSN :
1083-4419
Type :
jour
DOI :
10.1109/TSMCB.2009.2025775
Filename :
5175378
Link To Document :
بازگشت