A genetic algorithm approach for the object-sorting task problem
Fang-Chang Lin, Jane Yung-jen Hsu · 2002
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.