Analyzing The Performance Of Crossover Operators (OX, OBX, PBX, MPX) To Solve Combinatorial Problems
Rajiv Kumar, Minakshi Memoria, Madhur Thapliyal, Madhu Kirola, Ishteyaaq Ahmad, Ashulekha Gupta, Shagun Tyagi, Nabila Ansari
Abstract
Traveling Salesman problems and Scheduling problems are examples of combinatorial optimization problem. For this type of problem Genetic Algorithm (GA) can be used to get a perfect approximation in a short period. These problems are considered as NP-Hard problems. A genetic algorithm is a stochastic approach that can be applied to solve optimization problems. GA has many operators through which it finds the results. The main operators are selection, crossover, mutation operators. Without a crossover operator, a genetic algorithm works as a random algorithm. So, the Crossover operator is the main explorative operator which can search large search space. The goal of this research is to better understand crossover operator’s performance. For the experimental study, four different crossover operators are implemented to solve the sequence based combinatorial problem. It has been observed that Position-Based Crossover outperforms as compared to the other crossover operators in the study. It is the more appropriate operator for the ordering problem such as traveling salesman problems and Process scheduling problems.