|Article title||TWO-DIMENSIONAL STRIP PACKING BASED ON SIMULATION OF ADAPTIVE BEHAVIOR OF AN ANT COLONY|
|Authors||V.A. Vanidovsky, O.B. Lebedev|
|Section||SECTION I. EVOLUTIONARY MODELLING, GENETIC AND BIONIC ALGORITHMS|
|Month, Year||07, 2014 @en|
|Abstract||The problem of two-dimensional Strip Packing (1.5 DBP). As a data structure, carrying information about the package, the sequence of numbers used rectangles representing the order of their placement. An important role in obtaining solutions plays a decoder performing stacking rectangles rules laid down in it. New mechanisms for solving the problem of packaging, using mathematical methods, which lays down the principles of the natural mechanisms of decision-making. In this paper, as the basic structure of the decoder selected heuristics Floor Seiling No Rotation (FCNR). To build the decoder and the code sequence used modification heuristics (FCNR) and metaheuristics based on simulation of adaptive behavior of an ant colony. Unlike the canonical paradigm ant ant algorithm to find solutions to the graph G = (X, U) is constructed with a partition on the route of the formation and on the tops within each part, subgraphs whose edges are delayed pheromone. The structure of the graph search for solutions, the procedure of finding solutions on the graph ways pheromone deposition and evaporation. We use a cyclic (ant-cycle) method of ant systems. Experimental studies were carried out on IBM PC. The time complexity of the algorithm (ICA), experimentally obtained, practically coincides with the theoretical studies and for the considered test problems is (ICA ≈ O (n2)). Compared with existing algorithms to improve the results achieved by 2–3 %.|
|Keywords||Two-dimensional strip packing; swarm intelligence; ant colony; adaptive behavior; optimization.|
|References||1. Bischoff E.E. and Wдscher G. Cutting and packing, European Journal of Operational Research, 1995, No. 84, pp. 503-505.
2. Ross P., Marin-Blazquez J.G., Schulenburg, S. and Hart E. Learning a Procedure That Can Solve Hard Bin-Packing Problems: A New GA-Based Approach to Hyper-heurstics, Proceeding of the Genetic and Evolutionary Computation Conference, GECCO 2003, Chicargo, Illinois, USA, 2003, pp. 1295-1306.
3. Potarusov R.V., Kureychik V.M. Problema odnomernoy upakovki elementov [The one-dimensional problem of packing items], Izvestiya TRTU [Izvestiya TSURE], 2006, No. 8 (66), pp. 88-93.
4. Kureychik V.M. Algoritmy odnomernoy upakovki elementov [Algorithms of one-dimensional packing items], Izvestiya YuFU. Tekhnicheskie nauki [Izvestiya SFedU. Engineering Sciences], 2013, No. 7 (144), pp. 8-11.
5. Valeeva A.F., Agliullin M.N. Modelirovanie pryamougolnoy upakovki na baze metaevristiki muravinoy kolonii [Modeling rectangular packing on the basis of metaheuristic ant colony], Mezhvuzovskiy nauchnyy sbornik «Prinyatie resheniy v usloviyakh neopredelennosti» [Interuniversity collection of scientific works "problems of decision Making under uncertainty"]. Ufa, 2005, Vol. 2, pp. 55-63.
6. Levine J. and Ducatelle F. Ant Colony Optimization and Local Search for Bin Packing and Cutting Stock Problems. Centre for Intelligent Systems and their Applications, School of Informatics, University of Edinburgh, 2003.
7. Timofeeva O.P., Sokolova Eh.S., Milov K.V. Geneticheskiy algoritm v optimizatsii upakovki konteynerov [Genetic algorithm optimization of packaging containers], Trudy NGTU. Informatika i sistemy upravleniya [Proceedings of NSTU. Informatics and control systems], 2013, No. 4 (101), pp. 167-172.
8. Lebedev O.B., Zorin V.Yu. Upakovka na osnove metoda muravinoy kolonii [Packaging on the basis of ant colony], Izvestiya YuFU. Tekhnicheskie nauki [Izvestiya SFedU. Engineering Sciences], 2010, No. 12 (113), pp. 25-30.
9. Lebedev V.B., Lebedev O.B. Roevoy intellekt na osnove integratsii modeley adaptivnogo povedeniya muravinoy i pchelinoy koloniy [Swarm intelligence-based integration models of adaptive behavior of ant and bee colonies], Izvestiya YuFU. Tekhnicheskie nauki [Izvestiya SFedU. Engineering Sciences], 2013, No. 7 (144), pp. 41-47.
10. Lebedev B.K., Lebedev V.B. Optimizatsiya metodom kristallizatsii rossypi alternativ [Optimization method of crystallization placer alternatives], Izvestiya YuFU. Tekhnicheskie nauki [Izvestiya SFedU. Engineering Sciences], 2013, No. 7 (144), pp. 11-17.
11. Lebedev B.K., Lebedev O.B. Modelirovanie adaptivnogo povedeniya muravinoy kolonii pri poiske resheniy, interpretiruemykh derevyami [Simulation of adaptive behavior ant colony to find solutions, interpreted trees], Izvestiya YuFU. Tekhnicheskie nauki [Izvestiya SFedU. Engineering Sciences], 2012, No. 7 (132), pp. 27-35.
12. Dorigo M. and Stьtzle T. Ant Colony Optimization. MIT Press, Cambridge, MA, 2004.
13. Lebedev O.B. Modeli adaptivnogo povedeniya muravinoy kolonii v zadachakh proektirovaniya [Models of adaptive behavior of ant colonies in the design tasks]. Taganrog: Izd-vo YuFU, 2013.
14. Kureychik V.M., Lebedev B.K., Lebedev O.B. Razbienie na osnove modelirovaniya adaptivnogo povedeniya biologicheskikh sistem [Split based on the simulation of adaptive behavior of biological systems], Neyrokompyutery: razrabotka, primenenie [Neurocomputers: design, application], 2010, No. 2, pp. 28-34.