Improving binary optimization algorithms using genuine uniform initialization

Abstract

Population-based metaheuristic algorithms play a crucial role in solving complex optimization problems. The effectiveness of these algorithms is significantly influenced by the initial population of candidate solutions. This thesis investigates the critical aspect of initialization in population-based metaheuristic algorithms. This research studies Uniform Covering (UC) binary initialization method as the substitute for the Bit-string Uniform (BU) binary population initialization method for population initialization step in binary optimization algorithms. BU is the most commonly used random binary population initialization method in the literature, however, this research uncovers the adverse impact of employing this approach on binary optimization algorithms. Study in this thesis reveals that UC method is capable of providing gene-wise uniformity and chromosome-wise uniformity simultaneously, however BU method is not capable of providing chromosome-wise uniformity in the population. Monte-Carlo simulation and mathematical proofs are provided to demonstrate the limitations of the BU initialization in providing the diversity and uniformity in population initialization, meanwhile the effectiveness of the UC method is revealed as the alternative method, aiming to enhance algorithm convergence, robustness, and solution quality. In order to illustrate the effect of the BU and UC initialization on binary optimization algorithms, several experiments are conducted on single-objective and multi-objective combinatorial optimization problems including feature selection and knapsack problems using GA and NSGA-II algorithms representative of the binary optimization problems and binary optimization algorithms respectively. The experiments outcome confirm that BU initialization drastically degrade the performance of the algorithms and UC initialization is the proper way for the random binary population initialization.