Title :
A genetic algorithm approach for the object-sorting task problem
Author :
Lin, Fang-Chang ; Hsu, Jane Yung-jen
Author_Institution :
Dept. of Comput. Sci. & Inf. Eng., Nat. Taiwan Univ., Taipei, Taiwan
Abstract :
Most multi-agent tasks have high complexity. Optimal solutions of them are nearly intractable because of the large complexity. One approach is to use stochastic search techniques such as genetic algorithms to explore the solutions by its implicit parallelism and genetic mechanism. This paper analyzes the complexity of the object-sorting task, shows its NP-completeness, and develops a genetic algorithm to explore the optima. Experimental results show that 1) GA can find an optimal solution quickly for simple problem instances. 2) The results are better than our previous proposed cooperation protocol approach. In addition, the results can serve as a reference foundation of OST to the other approaches
Keywords :
computational complexity; cooperative systems; genetic algorithms; operations research; NP-completeness; cooperation protocol; genetic algorithm; implicit parallelism; multi-agent tasks; object-sorting task problem; stochastic search techniques; Computer science; Concrete; Genetic algorithms; Multiagent systems; Parallel processing; Protocols; Robots; Sorting; Space exploration; Stochastic processes;
Conference_Titel :
Systems, Man and Cybernetics, 1995. Intelligent Systems for the 21st Century., IEEE International Conference on
Conference_Location :
Vancouver, BC
Print_ISBN :
0-7803-2559-1
DOI :
10.1109/ICSMC.1995.537765
