The Shifting Balance Genetic Algorithm

Two observed deficiencies of the GA are its tendency to get trapped at local maxima and the difficulty it has handling a changing environment after convergence has occurred. A mechanism proposed by Sewall Wright in the 1930s addresses the problem of premature convergence: his Shifting Balance Theory (SBT) of evolution. In this work the SBT has been modified to remove defects inherent in its original formulation, while keeping the properties that should both increase the

adaptive abilities of the GA and prevent it from prematurely converging. The system has been implemented and is called the Shifting Balance Genetic Algorithm (SBGA). Experimental results and analysis are presented demonstrating that the SBGA does, in fact, lessen the problem of premature convergence and also improves performance under a dynamic environment, thereby mitigating both deficiencies. 1 INTRODUCTION While the Genetic Algorithm (GA) has been very successful when applied to a wide range of problems, in some respects the GA does not behave as adaptively as expected. A perennial problem is that of premature convergence, where a GA will become fixated on a single solution that comes to dominate the population. Many modifications of the original GA are motivated by reducing the risk of premature convergence. However, there is a second problem attendant on premature convergence even when the GA does not get trapped at any local maxima and finds the global maximum. The GA would then converge on that solution, and thereby lose the diversity in the population. With the loss of diversity, crossover loses its effectiveness and the only way for the GA to change is by mutation, which is usually set very low. Consequently, after convergence has occurred, the GA will have lost much of its ability to find other solutions. However, if the fitness function is not static, and the optimum changes to some other point in the gene-space, or even just drifts away from the current optimum, the GA will be nearly powerless to follow it. Sewall Wright, one of the founders of population genetics, proposed a mechanism for solving the problem of premature convergence in the 1930s. His theory, known as the Shifting Balance Theory, while conceptually fertile and influential, has never been developed in enough detail to enable its testing and application in genetics. We wish to abstract the conceptual core of his theory and render it applicable to evolutionary computation. In doing so, we have found that the resulting modified theory not only helps prevent premature convergence but also improves the behavior of the GA in dynamically changing environments. The primary interest of this paper is the behavior of evolutionary systems when faced with dynamic environments. While fundamental to the purpose behind Holland’s creation of the Genetic Algorithm, little research has been published on the topic. Some of this work is concerned with diploid chromosomes ((Goldberg and Smith, 1987), (Ng and Wong,...

Website: www.socs.uoguelph.ca | Filesize: -
No of Page(s): 7
Download The Shifting Balance Genetic Algorithm - School of Computer Science.pdf