Applying ant algorithms and the no fit polygon to the nesting problem

Citation

Burke E & Kendall G (1999) Applying ant algorithms and the no fit polygon to the nesting problem. In: Foo N (ed.) Advanced Topics in Artificial Intelligence: 12th Australian Joint Conference on Artificial Intelligence, AI’99 Sydney, Australia, December 6–10, 1999 Proceedings. Lecture Notes in Computer Science, 1747. 12th Australian Joint Conference on Artificial Intelligence, AI’99, Sydney, Australia, 06.12.1999-10.12.1999. Berlin Heidelberg: Springer, pp. 453-464. http://link.springer.com/chapter/10.1007%2F3-540-46695-9_38; https://doi.org/10.1007/3-540-46695-9_38

Abstract
In previous work solutions for the nesting problem are produced using the no fit polygon (NFP), a new evaluation method and three evolutionary algorithms (simulated annealing (SA), tabu search (TS) and genetic algorithms (GA)). Tabu search has been shown to produce the best quality solutions for two problems. In this paper this work is developed. A relatively new type of search algorithm (ant algorithm) is developed and the results from this algorithm are compared against SA, TS and GA We discuss the ideas behind ant algorithms and describe how they have been implemented with regards to the nesting problem. The evaluation method used is described, as is the NFP. Computational results are given.

Keywords
genetic algorithm; search; ant algorithms; no fit polygon; simulated annealing