NOVEL REAL CODED GENETIC ALGORITHMS FOR IMPLEMENTING CIRCLE PACKING PROBLEM TO SOLVE REAL LIFE APPLICATIONS

Abstract

This Thesis explores the study of Real Coded Genetic Algorithms (RCGAs) and their applications to the Circle Packing Problem (CPP). Initially, various types of genetic operators are studied, and their performance is evaluated using standard benchmark problems. In addition, novel real-coded genetic operators are proposed to enhance the performance of RCGAs. The CPP is an NP-hard combinatorial optimization problem and a widely used in operations research. It involves arranging a set of circles within a container of varying shapes with the objective of minimizing container size and unused space while maximizing packing density. Despite its complexity, solving the CPP is important due to its wide-ranging applications in diverse fields such as logistics, healthcare, manufacturing, and communication. To address the computational challenges posed by the CPP, this thesis investigates the use of RCGAs, which utilize real-valued representations for solutions. This approach is well-suited for both continuous and discrete optimization problems, enabling more efficient exploration of large and complex solution spaces. Building on this foundation, the research begins with a comprehensive study of genetic operators used in RCGAs. In particular, a detailed analysis is conducted on 41 real-coded crossover operators and 32 mutation operators, with crossovers categorized into three types based on the number of offspring generated: single, two, and multiple. These operators are evaluated across 23 standard benchmark problems to assess their effectiveness and identify the most promising combinations.