MULTI-STAGE ANT ALGORITHM OF ONE-DIMENSIONAL PACKING BASED ON EFFICIENT DECISION ENCODING METHODS AND TWO-LEVEL EVOLUTIONARY MEMORY

Abstract

The aim of the work is to develop and study bioinspired search methods for solving problems of one-dimensional packaging in identical containers based on effective algorithms for encoding and decoding solutions, composite criteria and a two-level structure of evolutionary memory. The paper proposes the structure of an ordered code for packing one-dimensional elements into identical containers, the main advantage of which is that one packaging solution corresponds to one code and vice versa. The search procedure is based on the modified metaheuristics of the ant algorithm. At each iteration, the one-dimensional packing algorithm has a multistep structure. The stages are performed sequentially one after the other, starting from the first one. Each stage of the С_k includes procedures performed by the z_k agent. The number of stages is equal to the number of agents in the population plus the final iteration stage. The main task solved by the constructive algorithm at the С_k stage is to construct the R_k code for packing a set of X elements into identical containers. The stage is divided into periods according to the number of lists X_jk generated by the agent z_k. The period is divided into stages. In each period, the following tasks are solved sequentially in stages: agent z_k constructively generates a set Rk of ordered lists Xjk of onedimensional packaging in identical containers; fjk estimates of the packaging of each container O_j by elements of the list <X_jk> are calculated; the amount of λ_jk pheromone proportional to the f_jk estimate is calculated; the estimate W_k=∑_i(f_jk)  is calculated one-dimensional packing of a set of elements X into H identical containers; pheromone is deposited on the edges of graph G corresponding to the list X_jk in the cells of the accumulative memory matrix E of the second level. After all agents of the z_k population Z have formed ordered lists of R_k, the accumulated pheromone is added to the main memory matrix Φ of the first level. For each R_k, the total F_k indicator of the packaging quality of the set of X elements is calculated. The final operation in the iteration is pheromone evaporation on the edges of graph G and fixation of z_k with the best F_k. Experimental studies have been conducted to determine the quality of the method's operation on large-dimensional test sets. To compare the developed algorithm with known methods and approximate algorithms, the authors selected several groups of benchmarks from various sources