Abstract:
Genetic algorithms are evolutionary metaheuristic algorithms that are used to solve complex problems. Although many variations exist in the literature, a common theme in all genetic algorithms is the application of a set of evolutionary operators to a set of random solutions in an iterative fashion. These evolutionary operators aim to generate new solutions in a semi-random manner in order to achieve the best possible solution. The effectiveness of evolutionary operators is largely dependent on two competing factors, namely exploration and exploitation of the problem space.
Although various genetic algorithm operators and their modifications are proposed and compared in the literature, how different operators perform together in terms of exploration and exploitation is not analyzed. We reduce exploration and exploitation to diversity and fitness of the solution set and examine the interactions between various components of a genetic algorithm in detail. For that purpose, we select grouping genetic algorithms which are specialized versions of genetic algorithms for grouping problems such as bin packing and line balancing problems as our domain. Then, by first proposing a new grouping genetic algorithm for U-Shaped Assembly Line Balancing problem (UALBP) we provide a detailed cross-examination of the possible evolutionary operators for bin packing problem (BPP) and UALBP