The behavior of evolutionary algorithms in combinatorial optimization

Abstract

Since combinatorial optimization is a branch of optimization, its domain consists of solution sets having different combinations of feasible answers to a problem. Some of the most famous combinatorial optimization problems can be listed as: Finding the shortest path (Travelling Salesman Problem in more specific), finding minimum spanning tree in a graph, black box optimization, solving a maze, optimizing airline network and so on. Evolutionary computation (EC) is one of the best computing techniques for solving combinatorial optimization problems. In EC, there are some algorithms inspiring from nature to find the best solution among the possible solutions' set. Genetic algorithm (GA) is a stochastic search technique which can be used to solve sequencing problems. Although it is being discussed for decades, Genetic Algorithms (GA) still finds very interesting application areas including most of the famous combinatorial optimization problems. All kinds of sequencing problems can be handled with GA. Its mechanisms (crossover, mutation and selection operators) simulate the behavior of reproduction process in nature and the result set is able to "evolve" to find better solutions. For this reason, they can easily be applied on problems which need to find the best solution among the solution candidates. GA is very convenient technique to observe performance with the changing parameters. For this reason, parameter tuning can be done on the same set of candidate solutions to find the best parameter combination of GA to solve the problem. When parameter tuning is applied, it has been observed that different parameter combinations can be more effective on different problems. In this study, the solution of a combinatorial optimization problem is searched by using GA. The operators used to simulate evolution mechanism play an important role on the behavior of the algorithm. The crossover rates for solving a sequencing problem with GA have been given as 0.7, 0.75, 0.8, 0.85, 0.9, 0.95 and 1.0. When the corresponding crossover rate values of the successful scenarios are examined, it is observed that the number of scenarios having crossover rates of 0.7 and 0.95 is more than the others. The same extraction can be done for the mutation rates. As mutation rates, 0.1, 0.15 and 0.2 were used. The number of successful scenarios with the mutation rate of 0.2 was more than the others. The population size interval is given as 100 – 200 (100, 120, 140, 160, 180 and 200) in the study. The system needs to test different sizes of populations because increasing the population size to a certain extent encourages the diversity of the population that the GA deals with. This means that as the population size increases, the possibility of having individuals with various values of fitness also increases. With populations of a small size, runtime and fitness values are more likely to be the best. As the population grows, finding “very reliable” solutions gets more difficult. Also the lengths of the sequences to be optimized directly affect the performance of GA. Two different sizes of data sets were selected. The smaller dataset has 17, the larger dataset has 30 chromosomes in each individual. This means that the genetic algorithm has to work in two different chromosome sizes. For all parameter combinations of genetic operators, three different crossover operators were applied in four different ways. That is; 1 – point order crossover (called GA1), 2 – point crossover (called GA2), partially mapped crossover – PMX (called GA3 in this project) and choosing one of the three crossover techniques randomly in each run (called GA4). Two different mutation operators were used randomly in each run. These are swap mutation and inversion mutation. The population used in GA is generated randomly. Since the different combinations of chromosomes indicate a different solution, obtaining random sequences of chromosomes is a crucial task for the genetic algorithm. This part can be considered as the most important and time consuming part of preparing data. Preparing the data in the proper format is also related with obtaining the possible solution set because sequencing chromosomes randomly is tightly dependent with the encoding mechanism of the genetic algorithm. There are several encoding mechanisms like binary encoding and real number encoding. For a combinatorial optimization problem having distinct integer values as the genes of a chromosome, permutation encoding is the correct encoding mechanism. In this kind of encoding, the order of neighboring genes has an importance. The importance of the order of the genes can be up to some prerequisite rules. For this reason, it is needed to have nonrecurring sequence of genes in a chromosome. For GA, the best solution has the reliability percentage of 98.53, which is a remarkable result emphasizing that GA mechanism is one of the best ways to implement solutions to combinatorial optimization problems. Differential Evolution (DE) is also a branch of evolutionary computation, in which optimization is done to find the best solution among all candidate solutions. As GA does, DE also creates new candidate solutions in each generation to obtain the individual having the best fitness value. In this optimization technique, unlike GA, mutation operator has a great importance to create a mutant individual. There are many algorithms to create the mutant individual, which is a candidate solution if it has better fitness value than the individual randomly chosen for mutation. The mutation mechanisms used in the study are DE/rand/1, DE/best/1, Simplex1 and Simplex2. For mutation, again unlike GA, DE has no mutation rates. This means that mutation is done in each generation. For crossover, there is a simple selection structure with a certain crossover rate. The crossover rates differ from the rates used in GA for this study because crossover is not the main operator for DE. The crossover rates used in this study are 0.5 and 0.8. Instead of the mutation rate, DE has another important parameter to execute. The F value is a constant used for the calculations of mutation operators of DE. The values used for F are 0.5 and 0.6. When four mutation operators are executed for two different crossover rates and two different F values, very satisfactory results are obtained. The results for Simplex1 and Simplex2 algorithms were better than the DE/rand/1 and DE/best/1 algorithms. The best solution has given the reliability percentage of 96.84, which puts forward that DE is a good tool to make optimization with. The best result was obtained for the parameter combination of 0.5 crossover rate and 0.5 F value. The idea behind using evolutionary algorithms like genetic algorithms or differential evolution algorithms for combinatorial problems is that the structure of these algorithms very much suit to the structure of combinatorial optimization problems. As future work, a hybrid version of genetic algorithms and differential evolution algorithms will be applied to a specific domain to observe the performance changes in finding the best solution.