Abstract
In this paper a genetic algorithm is proposed where the worst individual and individuals with indices close to its index are replaced in every generation by randomly generated individuals for dynamic optimization problems. In the proposed genetic algorithm, the replacement of an individual can affect other individuals in a chain reaction. The new individuals are preserved in a subpopulation which is defined by the number of individuals created in the current chain reaction. If the values of fitness are similar, as is the case with small diversity, one single replacement can affect a large number of individuals in the population. This simple approach can take the system to a self-organizing behavior, which can be useful to control the diversity level of the population and hence allows the genetic algorithm to escape from local optima once the problem changes due to the dynamics.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
Bak, P.: How Nature Works: The Science of Self-organized Criticality. Oxford University Press (1997)
Bak, P., Tang, C., Wiesenfeld, K.: Self-organized criticality. An explanation of 1/f noise. Phys. Rev. Lett. 59(4), 381–384 (1987)
Boettcher, S., Percus, A.G.: Optimization with extremal dynamics. Complexity 8(2), 57–62 (2003)
Branke, J.: Evolutionary Optimization in Dynamic Environments. Kluwer (2001)
Branke, J.: Evolutionary approaches to dynamic optimization problems – introduction and recent trends. In: Branke, J. (ed.) Proceedings of the GECCO Workshop on Evolutionary Algorithms for Dynamic Optimization Problems, pp. 2–4 (2003)
Cedeno, W., Vemuri, V.R.: On the use of niching for dynamic landscapes. In: Proceedings of the 1997 IEEE International Conference on Evolutionary Computation, pp. 361–366 (1997)
Cobb, H.G.: An investigation into the use of hypermutation as an adaptive operator in genetic algorithms having continuouis, time-dependent nonstationary environments. Technical Report AIC-90-001, Naval Research Laboratory, Washington, USA (1990)
Cobb, H.G., Grefenstette, J.J.: Genetic algorithms for tracking changing environments. In: Forrest, S. (ed.) Proceedings of the 5th International Conference on Genetic Algorithms, pp. 523–530 (1993)
Deb, K., Goldberg, D.E.: Analyzing deception in trap functions. In: Whitley, L.D. (ed.) Foundation of Genetic Algorithms 2, pp. 93–108 (1993)
Goldberg, D.A.: Genetic Algorithms in Search, Optimization, and Machine Learning. Addison-Wesley Publishing Company Inc. (1989)
Goldberg, D.A.: The Design of Innovation: Lessons from and for Competent Genetic Algorithms. Kluwer Academic Publishers, Boston, MA (2002)
Gould, S.J.: Wonderful Life: The Burgess Shale and the Nature of History. W. W. Norton and Company (1989)
Grefenstette, J.J.: Genetic algorithms for changing environments. In: Maenner, R., Manderick, B. (eds.) Parallel Problem Solving from Nature 2, pp. 137–144. North Holland (1992)
Jensen, H.J.: Self-organized Criticality: Emergent Complex Behavior in Physical and Biological Systems. Cambridge University Press (1998)
Jin, Y., Branke, J.: Evolutionary optimization in uncertain environments – a survey. IEEE Trans. Evol. Comput. 9(3), 303–317 (2005)
Kauffman, S.A.: The Origins of Order: Self-organization and Selection in Evolution. Oxford University Press (1993)
Krink, T., Thomsen, R.: Self-organized criticality and mass extinction in evolutionary algorithms. In: Proceedings of the 2001 Congress on Evolutionary Computation, vol. 2, pp. 1155–1161 (2001)
Løvbjerg, M., Krink, T.: Extending particle swarm optimisers with self-organized criticality. In: Proceedings of the 2002 IEEE Congress on Evolutionary Computation, vol. 2, pp. 1588–1593 (2002)
Mitchell, M.: An Introduction to Genetic Algorithms. MIT Press (1996)
Mori, N., Kita, H., Nishikawa, Y.: Adaptation to a changing environment by means of the feedback thermodynamical genetic algorithm. In: Eiben, A.E., Bäck, T., Schoenauer, M., Schwefel, H.-P. (eds.) Parallel Problem Solving from Nature, number 1498 in LNCS, pp. 149–158. Springer (1998)
Raup, D.M.: Biological extinction in earth history. Science 231, 1528–1533 (1986)
Trojanowski, K., Michalewicz, Z.: Evolutionary optimization in non-stationary environments. J. Comput. Sci. Technol. 1(2), 93–124 (2000)
Vavak, F., Fogarty, T.C., Jukes, K.: A genetic algorithm with variable range of local search for tracking changing environments. In: Voigt, H.-M. (ed.) Parallel Problem Solving from Nature, number 1141 in LNCS. Springer Verlag, Berlin (1996)
Yang, S.: Non-stationary problem optimization using the primal-dual genetic algorithm. In: Sarker, R., Reynolds, R., Abbass, H., Tan, K.-C., McKay, R., Essam, D., Gedeon, T. (eds.) Proceedings of the 2003 IEEE Congress on Evolutionary Computation, vol. 3, pp. 2246–2253 (2003)
Yang, S.: Constructing dynamic test environments for genetic algorithms based on problem difficulty. In: Proceedings of the 2004 IEEE Congress on Evolutionary Computation, vol. 2, pp. 1262–1269 (2004)
Yang, S., Yao, X.: Experimental study on population-based incremental learning algorithms for dynamic optimization problems. Soft Comput. 9(11), 815–834 (2005)
Acknowledgments
The authors would like to thank Prof. Wolfgang Bazhaf and the anonymous reviewers for their thoughtful suggestions and helpful comments, which greatly contributed to the improvement of the paper. This work was supported by FAPESP (Proc. 04/04289-6).
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Tinós, R., Yang, S. A self-organizing random immigrants genetic algorithm for dynamic optimization problems. Genet Program Evolvable Mach 8, 255–286 (2007). https://doi.org/10.1007/s10710-007-9024-z
Received:
Revised:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10710-007-9024-z