Shengxiang Yang
ABSTRACT
Investigating and enhancing the performance of genetic algorithms in dynamic environments have attracted a growing interest from the community of genetic algorithms in recent years. This trend reflects the fact that many real world problems are actually dynamic, which poses serious challenge to traditional genetic algorithms. Several approaches have been developed into genetic algorithms for dynamic optimization problems. Among these approches, random immigrants and memory schemes have shown to be beneficial in many dynamic problems. This paper proposes a hybrid memory and random immigrants scheme for genetic algorithms in dynamic environments. In the hybrid scheme, the best solution in memory is retrieved and acts as the base to create random immigrants to replace the worst individuals in the population. In this way, not only can diversity be maintained but it is done more efficiently to adapt the genetic algorithm to the changing environment. The experimental results based on a series of systematically constructed dynamic problems show that the proposed memory-based immigrants scheme efficiently improves the performance of genetic algorithms in dynamic environments.
- C. N. Bendtsen and T. Krink. Dynamic memory model for non-stationary optimization. In Proc. of the 2002 Congress on Evol. Comput., pages 145--150, 2002.Google Scholar
Cross Ref
- J. Branke. Memory enhanced evolutionary algorithms for changing optimization problems. In Proc. of the 1999 Congress on Evolutionary Computation, volume 3, pages 1875--1882, 1999.Google ScholarCross Ref
- J. Branke. Evolutionary Optimization in Dynamic Environments. Kluwer Academic Publishers, 2002. Google ScholarDigital Library
- J. Branke, T. Kauβler, C. Schmidth, and H. Schmeck. A multi-population approach to dynamic optimization problems. In Proc. of the Adaptive Computing in Design and Manufacturing, pages 299--308, 2000.Google ScholarCross Ref
- H. G. Cobb and J. J. Grefenstette. Genetic algorithms for tracking changing environments. In S. Forrest, editor, Proc. of the 5th Int. Conf. on Genetic Algorithms, pages 523--530, 1993. Google ScholarDigital Library
- D. Dasgupta and D. McGregor. Nonstationary function optimization using the structured genetic algorithm. In R. Männer and B. Manderick, editors, Proc. of the 2nd Int. Conf. on Parallel Problem Solving from Nature, pages 145--154, 1992.Google Scholar
- D. E. Goldberg and R. E. Smith. Nonstationary function optimization using genetic algorithms with dominance and diploidy. In Proc. of the 2nd Int. Conf. on Genetic Algorithms, pages 59--68, 1987. Google ScholarDigital Library
- J. J. Grefenstette. Genetic algorithms for changing environments. In R. Männer and B. Manderick, editors, Proc. of the 2nd Int. Conf. on Parallel Problem Solving from Nature, pages 137--144, 1992.Google Scholar
- E. H. J. Lewis and G. Ritchie. A comparison of dominance mechanisms and simple mutation on non-stationary problems. In Proc. of the 5th Int. Conf. on Parallel Problem Solving from Nature, pages 139--148, 1998. Google ScholarDigital Library
- S. J. Louis and Z. Xu. Genetic algorithms for open shop scheduling and re-scheduling. In Proc. of the 11th ISCA Int. Conf. on Computers and their Applications, pages 99--102, 1996.Google Scholar
- H. K. N. Mori and Y. Nishikawa. Adaptation to changing environments by means of the memory based thermodynamical genetic algorithm. In Proc. of the 7th Int. Conf. on Genetic Algorithms, pages 299--306. Morgan Kaufmann Publishers, 1997.Google Scholar
- K. P. Ng and K. C. Wong. A new diploid scheme and dominance change mechanism for non-stationary function optimisation. In Proc. of the 6th Int. Conf. on Genetic Algorithms, 1997. Google ScholarDigital Library
- C. L. Ramsey and J. J. Greffenstette. Case-based initializtion of genetic algorithms. In Proc. of the 5th Int. Conf. on Genetic Algorithms, 1993. Google ScholarDigital Library
- K. Trojanowski and Z. Michalewicz. Searching for optima in non-stationary environments. In Proc. of the 1999 Congress on Evolutionary Computation, pages 1843--1850, 1999.Google ScholarCross Ref
- F. Vavak and T. C. Fogarty. A comparative study of steady state and generational genetic algorithms for use in nonstationary environments. In T. C. Fogarty, editor, AISB Workshop on Evolutionary Computing, Lecture Notes in Computer Science, volume 1143, pages 297--304. Springer, 1996. Google ScholarDigital Library
- S. Yang. Non-stationary problem optimization using the primal-dual genetic algorithm, In Proc. of the 2003 Congress on Evol. Comput., Vol. 3, pages 2246--2253, 2003.Google Scholar
- S. Yang and X. Yao. Experimental study on population-based incremental learning algorithms for dynamic optimization problems. Soft Computing, 2005, to be published. Google ScholarDigital Library
Index Terms
- Memory-based immigrants for genetic algorithms in dynamic environments
Recommendations
Genetic algorithms with memory-and elitism-based immigrants in dynamic environments
In recent years the genetic algorithm community has shown a growing interest in studying dynamic optimization problems. Several approaches have been devised. The random immigrants and memory schemes are two major ones. The random immigrants scheme ...
Genetic algorithm with adaptive elitism-based immigrants for dynamic optimization problems
GECCO '09: Proceedings of the 11th Annual conference on Genetic and evolutionary computationWe propose a genetic algorithm with adaptive elitism-based immigrants which tunes the balance between elitism-based immigrants and random immigrants by itself. Experimental results show that our genetic algorithm with adaptive elitism-based immigrants ...
A comparative study on the performance of dissortative mating and immigrants-based strategies for evolutionary dynamic optimization
Traditional Genetic Algorithms (GAs) mating schemes select individuals for crossover independently of their genotypic or phenotypic similarities. In Nature, this behavior is known as random mating. However, non-random protocols, in which individuals ...
Comments