A cooperative coevolutionary genetic approach to solve packing problems

Resumen

One important type of computational problem is the grouping problems, where a set of elements is divided into a collection of subsets. One of these problems is the One-Dimensional Bin Packing Problem (1D-BPP), which is a classic optimization problem known for its applicability and complexity.1D-BPP belongs to a special class of problems called NP-hard, in which, given a set of variable size of elements, we pursue to accommodate them within fixed size containers, seeking to optimize the number of containers to use, that is, using the smallest number of containers to place the largest number of items possible [1]. The 1D-BPP is one of the most fundamental problems in combinatorial optimization and has been widely studied for decades. As one of the most representative problems of the constant grouping problems, newsets of instances are proposed and also new algorithms that try to solve it. The 1D-BPP has many applications in real life, hence its relevance and also serves as a starting point to understand other more complex grouping problems. There are several metaheuristic strategies proposed to solve the 1D-BPP. However, most of these approacheshave focused on the resolution of specific instances and have not considered the generality in order to increase the capacity of solution in problems or instances [2]. One of the strategies that helps the generality is the Coevolution. The objective of this work is to introduce a Cooperative Coevolutionary Genetic Algorithm (CCGA) to solve the 1D-BPP problem, by creating subspecies focused on improving the population in different aspects. For this, we propose a coding scheme and genetic operators adapted to a coevolutionary approach that allows the division of species. The proposal is based on the state-of-the art algorithm called the Grouping Genetic Algorithm with Controlled Gene Transmission (GGA-CGT) [3]. As a result, a better understanding of the impact of including coevolutionary strategies in the resolution of mono-objective grouping problems is presented. Finally, a general overview of CCGA and its performance is discussed, including suggestions for addressing other grouping problems with similar characteristics to 1DBPP.