An Investigation on Genetic Algorithm Parameters

An Investigation on Genetic Algorithm Parameters Abstract – Genetic algorithms provide a simple and almost generic method to solve complex optimization problems. Despite simplicity of it, genetic algorithm needs careful selection of settings like parent selection methods, mutation methods, population size ... to be able to find good solutions. Choosing unsuitable parameters and methods might result into longer program runs or even bad optimization results. In this report we use genetic algorithm in a sample “Bin Packing” problem. We implement and run the algorithm using different configurations and compare results. We then identify the best configuration among the tested parameters. Keywords: Genetic algorithm, optimization, bin packing, parameter selection, mutation, parent selection. 1 Introduction Choosing parameters and methods in genetic algorithm

might result into very different results. A good configuration might cause the algorithm to converge to best results in a short time while a worse setting might cause the algorithm to run for a long time before finding a good solution or even it might never be able to find a good solution. In this report we implement GA with different parent selection, mutation, recombination methods and also different population sizes. We will then try to identify which settings will work better in this problem’s case. Bin packing problem is about separating bottles of different colors into separate boxes. We have chosen 10 colors and 10 boxes for this purpose. Initially bottles with different colors are inside each box. We will separate bottles into boxes in a way that each box contains only one color. Box have unlimited capacity and our purpose is to minimize the moves between boxes. To be able to test the software we choose an initial data set (random number of bottles from different colors in each box). We use a fixed set of input data to be able to compare performance of different methods in finding the best solution. We will investigate different settings to see how fast they can reach or find a best solution. 1.1 Representation As we described earlier, movement of bottles between boxes will cause boxes to contain only a single color at the end of the movements. If we have 10 colors and 10 boxes then we might have “10!” different possible variations of solutions (in which every box contains a single color). 10 options 9 options 8 options 7 options 6 options 5 options 4 options 3 options 2 options 1 options We can represent solutions with a character string of the length 10. We can then represent each color with one of the alphabets “a to j”. Because box colors are not repetitive, this is called a permutation representation. Siamak Sarmady School of Computer Sciences, Universiti Sains Malaysia, 11800 Penang, Malaysia [P-COM0005/07(R) , P-COM0088/07] {sarmady@cs.usm.my, shaher5481561@yahoo.com} 1.2 Fitness function Our target in this problem is to minimize number of movements between boxes. Perhaps the best fitness function can be based on the number of necessary movements to achieve each solution. Calculation of the number of moves (in any selected solution) could be easily achieved. We present a sample calculation below. Initial Colors in boxes: (number of bottles with...

Website: sarmady.com | Filesize: -
No of Page(s): 10
Download An Investigation on Genetic Algorithm Parameters - Sarmady.pdf