Application of a Genetic algorithm for the rational placement of Rectangular items

Abstract

Objective. The aim of the work is to conduct a comparative analysis of the efficiency of using genetic algorithms to find a rational placement of rectangular parts based on numerical experiments.

Method. There are two main methods for solving optimization problems exact and approximate. The study considers one of the directions of approximate algorithms heuristic, which are based on the assumption of the properties of the optimal solution. In particular, this article considers a genetic algorithm as a method that allows you to find such an arrangement of parts that is close to optimal. To solve the problem, small objects are specified that must be placed without mutual overlap inside large objects so that the objective function reaches a minimum. The relevance of the study of this problem is due to its belonging to the class of NPhard problems.

Result. A program was developed that implements the placement of parts in a semi-infinite strip using a genetic algorithm. The behavior of this program on different classes of problems using three placement procedures was studied. The analysis of the algorithm's operation is carried out on seven categories of known test sets. Each category of input data contains three examples with a different number of elements in the range from 16 to 197.

Conclusion. To solve problems of rational use of materials, the development and software implementation of heuristic approaches is a pressing issue. These methods are effective algorithms for the optimal use of resources financial, material and others. The strength of metaheuristic methods is their ability to solve complex problems without knowledge of the search space, so these methods make it possible to solve difficult optimization problems.