Comparison of Domination Approaches for Diploid Binary Genetic Algorithms

Abstract

Most studies in application of genetic algorithms deal with static environments. However there is a class of problems where the environment changes in time. From a genetic algorithm point of view, the change may be in the fitness function, in the constraints or the problem instance itself. In such environments, it becomes important for the solution approach to adapt to this change and follow the new optima. Classical genetic algorithms [2] do not have the necessary mechanisms to address the issues encountered when working in such environments. Thus it becomes necessary either to make modifications to existing algorithms or to incorporate other features. The main issues when dealing with dynamic environments is preserving diversity in the gene pool of the population and being able to converge to a solution on the phenotype level. The modifications or the new features have to take this issue into account and incorporate a balance between preserving diversity and converging to a solution. There are several different approaches in literature which deal with variations of genetic algorithms suitable for working in dynamic environments. Since the choice of a suitable approach depends on analyzing the nature of the change in the environment, it is worthwhile to categorize the change based on specific properties. A good set of criteria for this purpose is given in [1] as the frequency of change, the severity of change, the predictability of change and the cycle length/cycle accuracy. Using diploid representations is one of the approaches for addressing performance and diversity issues in dynamic environments. When using a diploid representation for individuals, the choice of a good domination mechanism is a very important factor in performance. There has been some research done in the area of domination in diploid genetic algorithms and a good survey can be found in [1].