A comparative study between traditional genetic algorithms and breeder genetic algorithms

number: 
852
إنجليزية
department: 
Degree: 
Imprint: 
Computer Science
Author: 
Maha Sabah Salmo
Supervisor: 
Dr. Mazin Z. Othman
Dr.Venus W. Samawi
year: 
2004

Abstract:

Genetic Algorithm (GA) becomes a suitable searching or optimization method for solving many of complex problems. The weak point of GAs, is how to represent individuals for problems with real variables; researches have dealt with their discrete representation (bits or integers) rather than with the real values themselves. This is obviously an approach limiting the power of the timization process. Therefore certain manipulations are usually essential to speed up arJ improve GA performance to suit all kind of problems. Traditional Genetic Algorithms (TGA), Breeder Genetic Algorithms (BGAs), and two natural-based mutation (with static and dynamic population size), for solution of certain problems are suggested. In this work, BGAs are based on the concepts of evolution of species and selection typical of GAs, however they differ in the fact that the evolution of population in 'driven' by using breeding mechanism. In addition to using crossover and mutatior operations dealing with real values themselves not with discrete terms, also GAs are used with two natural-based mutations (i.e. the Frame-shift and Trans location). These operators are based on the corresponding biological events. The Frame-shift tries to mimic as closely as possible biological insertions and deletions, while in Translocation a piece of one chromosome is transferred to a nonhomologous chromosome. Moreover, Dynamic population size is also used to prevent the convergence and to improve the fitness value (convergence means that all individuals in the population are the same). Increasing population size depends on the problem to be solved, the initialization of population size, the fitness values, and the number of generations. The implementation of BGAs, two natural-based mutations used with Traditional Genetic Algorithm (TGA) together with the discussion of their effects on the performance of GA are presented in this work. A comparison between these methods and TGA are also illustrated in this work. Three problems (Solving Instantaneous Algebraic Equations (SIAEq's), Traveling. Salesman Problem (TSP), and Substitution Ciphers (SC)) are solved in this work using the over mentioned techniques to study and illustrate the behavior of each GA types.