The scalability of evolved on line bin packing heuristics

Citation

Burke E, Hyde M, Kendall G & Woodward J (2007) The scalability of evolved on line bin packing heuristics. In: 2007 IEEE Congress on Evolutionary Computation, CEC 2007. IEEE Congress on Evolutionary Computation. IEEE Congress on Evolutionary Computation, 2007. CEC 2007, Singapore, 25.09.2007-28.09.2007. Piscataway, NJ, USA: IEEE, pp. 2530-2537. http://ieeexplore.ieee.org/xpl/articleDetails.jsp?arnumber=4424789; https://doi.org/10.1109/CEC.2007.4424789

Abstract
The scalability of an evolved multi-agent system is an important characteristic of the system. The multi-agent system is normally evolved in a particular configuration of system parameters. However, an optimized solution using one set of system parameters does not necessarily means a good solution using a different set of system parameters. The research presented in this paper studies the performance scalability of evolved solutions in reactive multi-agent systems for the heap formation task. The scalability variable considered in the research was the cardinality of the agents group, whereas keeping the rest of the system and collective resources invariable. In the first phase of the experiments, best solutions for different system configurations were found using genetic algorithm. In the second phase, the evolved solutions were cross-tested in all system configurations. The research showed that evolved solutions performed well if the agents/objects ratio of the multi-agent system used in testing was similar to the agents/objects ratio of the multi-agent system used in evolution. Additionally, evolved solutions scaled well only on limited intervals that did not span over the critical point, which corresponded to the condition where the number of agents is equal to the number of objects. Typically, solutions that performed well on one side of the critical point performed badly on the other side, suggesting the solutions performances were significantly dependant on agents/objects ratio.

Keywords
multi-agent systems