Volume 4 Number 3
July 2007
Article Contents
Shengxiang Yang and Renato Tinós. A Hybrid Immigrants Scheme for Genetic Algorithms in Dynamic Environments. International Journal of Automation and Computing, vol. 4, no. 3, pp. 243-254, 2007. doi: 10.1007/s11633-007-0243-9
Cite as: Shengxiang Yang and Renato Tinós. A Hybrid Immigrants Scheme for Genetic Algorithms in Dynamic Environments. International Journal of Automation and Computing, vol. 4, no. 3, pp. 243-254, 2007. doi: 10.1007/s11633-007-0243-9

A Hybrid Immigrants Scheme for Genetic Algorithms in Dynamic Environments

  • Received: 2007-03-05
Fund Project:

This work was supported by UK EPSRC(No.EP/E060722/01);Broil FAPESP(Proc.04/04289-6).

  • Dynamic optimization problems are a kind of optimization problems that involve changes over time.They pose a serious challenge to traditional optimization methods as well as conventional genetic algorithms since the goal is no longer to search for the optimal solution(s) of a fixed problem but to track the moving optimum over time.Dynamic optimization problems have attracted a growing interest from the genetic algorithm community in recent years.Several approaches have been developed to enhance the performance of genetic algorithms in dynamic environments.One approach is to maintain the diversity of the population via random immigrants.This paper proposes a hybrid immigrants scheme that combines the concepts of elitism,dualism and random immigrants for genetic algorithms to address dynamic optimization problems.In this hybrid scheme,the best individual,i.e.,the elite,from the previous generation and its dual individual are retrieved as the bases to create immigrants via traditional mutation scheme.These elitism-based and dualism-based immigrants together with some random immigrants are substituted into the current population,replacing the worst individuals in the population.These three kinds of immigrants aim to address environmental changes of slight,medium and significant degrees respectively and hence efficiently adapt genetic algorithms to dynamic environments that are subject to different severities of changes.Based on a series of systematically constructed dynamic test problems,experiments are carried out to investigate the performance of genetic algorithms with the hybrid immigrants scheme and traditional random immigrants scheme.Experimental results validate the efficiency of the proposed hybrid immigrants scheme for improving the performance of genetic algorithms in dynamic environments.
  • 加载中
  • [1] D.E.Goldberg.Genetic Algorithms in Search,Optimization,and Machine Learning,Addison-Wesley,Reading,MA,USA,1989.
    [2] J.H.Holland.Adaptation in NaturaJ and Artificial Systems,Ann Arbor,University of Michigan Press,1975.
    [3] D.E.Goldberg,R.E.Smith.Nonstationary Function Optimization Using Genetic Algorithms with Dominance and Diploidy.In Proceedings of the 2nd International Conference on Genetic Algorithms,Lawrence Erlbaum Associates,Mahwah,NJ,USA,pp.59-68,1987.
    [4] J.Branke.Evolutionary Optimization in Dynamic Environments,Kluwer Academic Publishers,Boston,MA,2001.
    [5] R.W.Morrison.Designing Evolutionary Algorithms for Dynamic Environments,Springer-Verlag,Berlin Heidelberg,2004.
    [6] K.Weicker.Evolutionary Algorithms and Dynamic Optimization Problems,Osnabriick,Germany,Der andere Verlag,2003.
    [7] Y.Jin,J.Branke.Evolutionary Optimization in Uncertain Environments:A Survey.IEEE Transactions on Evolutionary Computation,vol.9,no.3,pp.303-317,2005.
    [8] J.J.Grefenstette.Genetic Algorithms for Changing Environments.Parallel Problem Solving from Nature,Elsevier Science Publishers,The Netherlands,vol.2,pp.137-144,1992.
    [9] F.Vavak,T.C.Fogarty.A Comparative Study of Steady State and Generational Genetic Algorithms for Use in Nonstationary Environments.In Proceedings of AISB Workshop on EvoJutionary Computing,Lecture Notes in Computer Science,Springer-Verlag,Berlin Heidelberg,vol.1143,pp.297-304,1996.
    [10] H.G.Cobb,J.J.Grefenstette.Genetic Algorithms for Tracking Changing Environments.In Proceedings of the 5th International Conference on Genetic Algorithms,Morgan Kaufmann Publishers,San Francisco,CA,USA,pp.523-530,1993.
    [11] R.W.Morrison,K.A.De Jong.Triggered Hypermutation Revisited.In Proceedings of the 2000 IEEE Congress on Evolutionary Computation,IEEE,pp.1025-1032,2000.
    [12] C.N.Bendtsen,T.Krink.Dynamic Memory Model for Non-stationary Optimization.In Proceedings of the 2002 Congress on Evolutionary Computation,IEEE,pp.145-150,2002.
    [13] J.Branke.Memory Enhanced Evolutionary Algorithms for Changing Optimization Problems.In Proceedings of the 1999 Congress on Evolutionary Computation,IEEE,vol.3,pp.1875-1882,1999.
    [14] A.Simoes,E.Costa.An Immune System-based Genetic Algorithm to Deal with Dynamic Environments:Diversity and Memory.In Proceedings of the 6th International Conference on Artificial Neural Networks and Genetic Algorithms,Springer,pp.168-174,2003.
    [15] K.Trojanowski,Z.Michalewicz.Searching for Optima in Non-stationary Environments.In Proceedings of the 1999 Congress on Evolutionary Computation,IEEE,pp.1843-1850,1999.
    [16] S.Yang.Memory-based Immigrants for Genetic Algorithms in Dynamic Environments.In Proceedings of the 2005 Genetic and Evolutionary Computation Conference,vol.2,pp.1115-1122,2005.
    [17] S.Yang.Associative Memory Scheme for Genetic Algorithms in Dynamic Environments.AppJications of EvoJutionary Computing,Lecture Notes in Computer Science,vol.3907,Springer-Verlag,Berlin Heidelberg,pp.788-799,2006.
    [18] J.Branke,T.Kau/31er,C.Schmidth,H.Schmeck.A Multi-population Approach to Dynamic Optimization Problems.In Proceedings of the Adaptive Computing in Design and Manufacturing,pp.299-308,2000.
    [19] D.Parrott,X.Li.Locating and Tracking Multiple Dynamic Optima by a Particle Swarm Model Using Speciation.IEEE Transactions on Evolutionary Computation,vol.10,no.4,pp.444-458,2006.
    [20] S.Yang.Genetic Algorithms with Elitism-based Immigrants for Changing Optimization Problems.Applications of Evolutionary Computing,Lecture Notes in Computer Science,Springer-Verlag,Berlin Heidelberg,vol.4448,pp.627-636,2007.
    [21] S.Yang.Non-stationary Problem Optimization Using the Primal-dual Genetic Algorithm.In Proceedings of the 2003 IEEE Congress on Evolutionary Computation,IEEE,vol.3,pp.2246-253,2003.
    [22] S.Yang,X.Yao.Experimental Study on Population-based Incremental Learning Algorithms for Dynamic Optimization Problems.Soft Computing,vol.9,no.11,pp.815-834,2005.
    [23] W.Cedeno,V.R.Vemuri.On the Use of Niching for Dynamic Landscapes.In Proceedings of the 1997 IEEE International Conference on Evolutionary Computation,IEEE,pp.361-366,1997.
    [24] N.Mori,H.Kita,Y.Nishikawa.Adaptation to Changing Environments by Means of the Memory Based Thermody-namical Genetic Algorithm.In Proceedings of the 7th International Conference on Genetic Algorithms,T.Back (ed.),Morgan Kaufmann Publishers,pp.299-306,1997.
    [25] N.Mori,H.Kita,Y.Nishikawa.Adaptation to a Changing Environment by Means of the Feedback Thermodynamical Genetic Algorithm.Parallel Problem Solving from Nature V,Lecture Notes in Computer Science,Springer-Verlag Berlin Heidelberg,vol.1498,pp.149-158,1998.
    [26] R.W.Morrison,K.A.De Jong.A Test Problem Generator for Non-stationary Environments.In Proceedings of the 1999 Congress on Evolutionary Computation,IEEE,vol.3,pp.2047-2053,1999.
    [27] M.Mitchell,S.Forrest,J.H.Holland.The Royal Road for Genetic Algorithms:Fitness Landscapes and GA Performance.In Proceedings of the 1st European Conference on Artificial Life,MIT Press,Cambridge MA,USA,pp.245-254,1991.
    [28] D.E.Goldberg.The Design of Innovation:Lessons from and for Competent Genetic Algorithms,Kluwer Academic Publishers,Boston,MA,2002.
    [29] L.D.Whitley.Fundamental Principles of Deception in Genetic Search.Foundations of Genetic Algorithms 1,Morgan Kaufmann Publishers,pp.221-241,1991.
  • 加载中
  • [1] Evgeny I. Veremey. Special Spectral Approach to Solutions of SISO LTI H-Optimization Problems . International Journal of Automation and Computing, 2019, 16(1): 112-128.  doi: 10.1007/s11633-017-1110-y
    [2] Dong-Jie Li, Yang-Yang Li, Jun-Xiang Li, Yu Fu. Gesture Recognition Based on BP Neural Network Improved by Chaotic Genetic Algorithm . International Journal of Automation and Computing, 2018, 15(3): 267-276.  doi: 10.1007/s11633-017-1107-6
    [3] Tarek Ababsa, Noureddine Djedl, Yves Duthen. Genetic Programming-based Self-reconfiguration Planning for Metamorphic Robot . International Journal of Automation and Computing, 2018, 15(4): 431-442.  doi: 10.1007/s11633-016-1049-4
    [4] Yuan Ge, Yaoyiran Li. SCHMM-based Compensation for the Random Delays in Networked Control Systems . International Journal of Automation and Computing, 2016, 13(6): 643-652.  doi: 10.1007/s11633-016-1001-7
    [5] Imad Benacer, Zohir Dibi. Extracting Parameters of OFET Before and After Threshold Voltage Using Genetic Algorithms . International Journal of Automation and Computing, 2016, 13(4): 382-391.  doi: 10.1007/s11633-015-0918-6
    [6] Kumaran Rajarathinam,  James Barry Gomm,  Ding-Li Yu,  Ahmed Saad Abdelhadi. PID Controller Tuning for a Multivariable Glass Furnace Process by Genetic Algorithm . International Journal of Automation and Computing, 2016, 13(1): 64-72.  doi: 10.1007/s11633-015-0910-1
    [7] Sunil Nilkanth Pawar,  Rajankumar Sadashivrao Bichkar. Genetic Algorithm with Variable Length Chromosomes for Network Intrusion Detection . International Journal of Automation and Computing, 2015, 12(3): 337-342.  doi: 10.1007/s11633-014-0870-x
    [8] Hong-Bin Wang,  Mian Liu. Design of Robotic Visual Servo Control Based on Neural Network and Genetic Algorithm . International Journal of Automation and Computing, 2012, 9(1): 24-29.  doi: 10.1007/s11633-012-0612-x
    [9] Anna Gorbenko,  Vladimir Popov. Task-resource Scheduling Problem . International Journal of Automation and Computing, 2012, 9(4): 429-441.  doi: 10.1007/s11633-012-0664-y
    [10] Khalid Jebari, Abdelaziz Bouroumi, Aziz Ettouhami. Fuzzy Genetic Sharing for Dynamic Optimization . International Journal of Automation and Computing, 2012, 9(6): 616-626 .  doi: 10.1007/s11633-012-0687-4
    [11] P. S. V. Nataraj, Shanta Sondur. Construction of Bode Envelopes Using REP Based Range Finding Algorithms . International Journal of Automation and Computing, 2011, 8(1): 112-121.  doi: 10.1007/s11633-010-0562-0
    [12] Wu-Yi Yang, Sheng-Xing Liu, Tai-Song Jin, Xiao-Mei Xu. An Optimization Criterion for Generalized Marginal Fisher Analysis on Undersampled Problems . International Journal of Automation and Computing, 2011, 8(2): 193-200.  doi: 10.1007/s11633-011-0573-5
    [13] Han Xue,  Xun Li,  Hong-Xu Ma. Random Fuzzy Chance-constrained Programming Based on Adaptive Chaos Quantum Honey Bee Algorithm and Robustness Analysis . International Journal of Automation and Computing, 2010, 7(1): 115-122.  doi: 10.1007/s11633-010-0115-6
    [14] Qing-Jin Peng,  Xiu-Mei Kang,  Ting-Ting Zhao. Effective Virtual Reality Based Building Navigation Using Dynamic Loading and Path Optimization . International Journal of Automation and Computing, 2009, 6(4): 335-343.  doi: 10.1007/s11633-009-0335-9
    [15] Tung-Kuan Liu, Chiu-Hung Chen, Zu-Shu Li, Jyh-Horng Chou. Method of Inequalities-based Multiobjective Genetic Algorithm for Optimizing a Cart-double-pendulum System . International Journal of Automation and Computing, 2009, 6(1): 29-37.  doi: 10.1007/s11633-009-0029-3
    [16] Efficient Graph-based Genetic Programming Representation with Multiple Outputs . International Journal of Automation and Computing, 2008, 5(1): 81-89.  doi: 10.1007/s11633-008-0081-4
    [17] Fausto Pedro Garcia Márquez,  Diego J. Pedregal. Applied RCM2 Algorithms Based on Statistical Methods . International Journal of Automation and Computing, 2007, 4(2): 109-116.  doi: 10.1007/s11633-007-0109-1
    [18] Pietro S. Oliveto,  Jun He,  Xin Yao. Time Complexity of Evolutionary Algorithms for Combinatorial Optimization:A Decade of Results . International Journal of Automation and Computing, 2007, 4(3): 281-293.  doi: 10.1007/s11633-007-0281-3
    [19] Siddhartha Shakya, John McCall. Optimization by Estimation of Distribution with DEUM Framework Based on Markov Random Fields . International Journal of Automation and Computing, 2007, 4(3): 262-272.  doi: 10.1007/s11633-007-0262-6
    [20] Cheng-Dong Wu, Ying Zhang, Meng-Xin Li, Yong Yue. A Rough Set GA-based Hybrid Method for Robot Path Planning . International Journal of Automation and Computing, 2006, 3(1): 29-34.  doi: 10.1007/s11633-006-0029-5
通讯作者: 陈斌, bchen63@163.com
  • 1. 

    沈阳化工大学材料科学与工程学院 沈阳 110142

  1. 本站搜索
  2. 百度学术搜索
  3. 万方数据库搜索
  4. CNKI搜索

Metrics

Abstract Views (4218) PDF downloads (1612) Citations (0)

A Hybrid Immigrants Scheme for Genetic Algorithms in Dynamic Environments

Fund Project:

This work was supported by UK EPSRC(No.EP/E060722/01);Broil FAPESP(Proc.04/04289-6).

Abstract: Dynamic optimization problems are a kind of optimization problems that involve changes over time.They pose a serious challenge to traditional optimization methods as well as conventional genetic algorithms since the goal is no longer to search for the optimal solution(s) of a fixed problem but to track the moving optimum over time.Dynamic optimization problems have attracted a growing interest from the genetic algorithm community in recent years.Several approaches have been developed to enhance the performance of genetic algorithms in dynamic environments.One approach is to maintain the diversity of the population via random immigrants.This paper proposes a hybrid immigrants scheme that combines the concepts of elitism,dualism and random immigrants for genetic algorithms to address dynamic optimization problems.In this hybrid scheme,the best individual,i.e.,the elite,from the previous generation and its dual individual are retrieved as the bases to create immigrants via traditional mutation scheme.These elitism-based and dualism-based immigrants together with some random immigrants are substituted into the current population,replacing the worst individuals in the population.These three kinds of immigrants aim to address environmental changes of slight,medium and significant degrees respectively and hence efficiently adapt genetic algorithms to dynamic environments that are subject to different severities of changes.Based on a series of systematically constructed dynamic test problems,experiments are carried out to investigate the performance of genetic algorithms with the hybrid immigrants scheme and traditional random immigrants scheme.Experimental results validate the efficiency of the proposed hybrid immigrants scheme for improving the performance of genetic algorithms in dynamic environments.

Shengxiang Yang and Renato Tinós. A Hybrid Immigrants Scheme for Genetic Algorithms in Dynamic Environments. International Journal of Automation and Computing, vol. 4, no. 3, pp. 243-254, 2007. doi: 10.1007/s11633-007-0243-9
Citation: Shengxiang Yang and Renato Tinós. A Hybrid Immigrants Scheme for Genetic Algorithms in Dynamic Environments. International Journal of Automation and Computing, vol. 4, no. 3, pp. 243-254, 2007. doi: 10.1007/s11633-007-0243-9
Reference (29)

Catalog

    /

    DownLoad:  Full-Size Img  PowerPoint
    Return
    Return