No Fit Polygon for Nesting Problem Solving with Hybridizing Ant Algorithms

Qiang Yang

Computer School, Yangtze University, Jingzhou, China.

DOI: 10.4236/jsea.2014.75040                

Abstract

In design science, these two kinds of problems are mutually nested, however, the nesting could not blind us for the fact that their problem-solving and solution justification methods are different. The ant algorithms research field, builds on the idea that the study of the behavior of ant colonies or other social insects is interesting, because it provides models of distributed organization which could be utilized as a source of inspiration for the design of optimization and distributed control algorithms. In this paper, a relatively new type of hybridizing ant search algorithm is developed, and the results are compared against other algorithms. The intelligence of this heuristic approach is not portrayed by individual ants, but rather is expressed by the colony as a whole inspired by labor division and brood sorting. This solution obtained by this method will be evaluated against the one obtained by other traditional heuristics.

Keywords

Genetic Algorithm, Search, Ant Algorithms, No Fit Polygon, Simulated Annealing

Conflicts of Interest

The authors declare no conflicts of interest.

References

[1]	Albano, G.S. (2010) Optimal Allocation of Two-Dimensional Irregular Shapes Using Heuristic Search Methods. IEEE Transactions on Systems, Man, and Cybernetics, 10, 242-248.
[2]	Bullnheimer, B., Hartl, R.F. and Strauss, C. (2009) An Improved Ant system Algorithm for the Vehicle Routing Problem. Annals of Operations Research, 89, 319-328.
[3]	Burke, E. and Kendall, G. (2012) Applying Evolutionary Algorithms the No Fit Polygon to the Nesting Problem. The International Conference on Artificial Intelligence, Monte Carlo Resort, Las Vegas, 28 July 2012, 317-324.
[4]	Burke, E. and Kendall, G. (2012) Applying Simulated Annealing and the No Fit Polygon to the Nesting Problem. WMC World Manufacturing Congress, Durham, September 2012, 214-222.
[5]	Abaji, R.H.A. (2002) Evolutionary Techniques for Multi-Objective VLSI Netlist Partitioning. Thesis Work, COE Department KFUPM, Dhahran.
[6]	Vaishnav, H. and Pedram, M. (1999) Delay Optimal Partitioning Targeting Low Power VLSI Circuits. IEEE Transaction on Computer Aided Design, 18, 298-301.
[7]	Alpert, J. and Yao, S.-Z. (1995) Spectral Partitioning: The More Eigenvectors, the Better. Design Automation Conference, San Francisco, 1995, 195-200.
[8]	Hagen, L. and Kahng, A. (2012) New Spectral Methods for Ratio Cut Partitioning And Clustering. IEEE Transaction on CAD, 11, 1074-1085. http://dx.doi.org/10.1109/43.159993
[9]	Areibi, S. and Vannelli, A. (1994) Advanced Search Techniques for Circuit Partitioning. In: Pardalos, P. and Wolkowicz, H., Eds., Quadratic Assignment and Related Problems, DIMACS Series in Discrete Mathematics and Theoretical Computer Science, 16, 77-99.
[10]	Hagen, L. and Kahng, A. (1997) Combining Problem Reduction and Adaptive Multistart: A New Technique for Superior Iterative Partitioning. IEEE Transactions on Computer-Aided Design, 16, 709-717. http://dx.doi.org/10.1109/43.644032
[11]	Sanchis, L.A. (2009) Multiple-Way Network Partitioning. IEEE Traction on Computer Society, 38, 62-81.
[12]	Falkenauer, E. (2008) Genetic Algorithms and Grouping Problems. John Wiley and Sons, New York.
[13]	Forsyth, P. and Wren, A. (2007) An Ant System for Bus Driver Scheduling. 7th International Workshop on Computer-Aided Scheduling of Public Transport, Boston, 1-18.
[14]	Maniezzo, V. and Colorni, A. (2011) The Ant System Applied to the Quadratic Assignment Problem. IEEE Transactions on Knowledge and Data Engineering, 11, 769-778.
[15]	Oliveira, J.F., Gomes, A.M. and Ferreira, S. (2000) TOPOS A New Constructive Algorithm for Nesting Problems. OR-Spektrum, 22, 263-284.
[16]	Stützle, T. and Dorigo, M. (2009) ACO Algorithms for the Traveling Salesman Problem. In: Miettinen, K., Makela, M., Neittaanmaki, P. and Periaux, J., Eds., Evolutionary Algorithms in Engineering and Computer Science, Wiley, Hoboken, 1-10.