Abstract
Differential evolution (DE) has been successful in solving practical optimization problem. However, similar to other optimization algorithms, the search performance of DE depends on the efficacy of the adopted search operators. The ability to adapt these operators within an evolutionary run enhances their ability to find better quality solutions. This adaptation process requires learning algorithms capable of compressing the information embedded within a population into meaningful estimates to adapt the search operators. Hidden Markov Models (HMMs) are learning algorithms designed to estimate parameters by compressing information collected from on a state space. In this paper, we use HMMs to compress the information within a population and use the model for adapting the DE parameters. The resultant DE-HMM algorithm dynamically adjusts the two basic parameters of DE. After a thorough testing of this method and conducting an extensive comparison of its performance on the CEC2005 and CEC2014 dataset, it is shown that the proposed DE-HMM algorithm is able to achieve better results compared with the classical DE and other state-of-the-art methods. On average, the algorithm can achieve this performance faster than other methods in the literature.
Similar content being viewed by others
Explore related subjects
Discover the latest articles, news and stories from top researchers in related subjects.References
The SPSS statistical tool (Jan 2016). http://www.ibm.com/analytics/us/en/technology/spss/
Abbass HA (2002) The self-adaptive pareto differential evolution algorithm. In: Evolutionary computation, 2002. CEC’02. proceedings of the 2002 congress on Bd. 1 IEEE, pp 831–836
Abraham A, Das S, Konar A (2006) Document clustering using differential evolution. In: 2006 IEEE international conference on evolutionary computation IEEE, pp 1784–1791
Al-Dabbagh RD, Kinsheel Azeddien, Mekhilef Saad, Baba Mohd S, Shamshirband Shahaboddin (2014) System identification and control of robot manipulator based on fuzzy adaptive differential evolution algorithm. Adv Eng Softw 78:60–66
Auger A, Hansen N (2005) A restart CMA evolution strategy with increasing population size. In: 2005 IEEE congress on evolutionary computation Bd. 2 IEEE, pp 1769–1776
Baum LE, Petrie T (1966) Statistical inference for probabilistic functions of finite state Markov chains. Ann Math Stat 37(6):1554–1563
Braak CJFT (2006) A Markov Chain Monte Carlo version of the genetic algorithm differential evolution: easy bayesian computing for real parameter spaces. Stat Comput 16(3):239–249
Brest J, Greiner S, Boskovic Borko, Mernik Marjan, Zumer Viljem (2006) Self-adapting control parameters in differential evolution: a comparative study on numerical benchmark problems. IEEE Trans Evol Comput 10(6):646–657
Cao Y, Li Y, Coleman S, Belatreche A, McGinnity TM (2015) Adaptive Hidden Markov Model with anomaly states for price manipulation detection. IEEE Trans Neural Netw Learn Syst 26(2):318–330. https://doi.org/10.1109/TNNLS.2014.2315042
Corriveau G, Guilbault R, Tahan A, Sabourin R (2016) Bayesian network as an adaptive parameter setting approach for genetic algorithms. Complex Intell Syst 2(1):1–22
Črepinšek M, Liu SH, Mernik M (2013) Exploration and exploitation in evolutionary algorithms: a survey. ACM Comput Surv 45(3):35
Das S, Mandal A, Mukherjee R (2014) An adaptive differential evolution algorithm for global optimization in dynamic environments. IEEE Trans Cybern 44(6):966–978
Das S, Mullick SS, Suganthan PN (2016) Recent advances in differential evolution—an updated survey. Swarm Evol Comput 27:1–30
Davis TE, Principe JC (1993) A Markov chain framework for the simple genetic algorithm. Evol Comput 1(3):269–288
Derrac J, García S, Molina D, Herrera F (2011) A practical tutorial on the use of nonparametric statistical tests as a methodology for comparing evolutionary and swarm intelligence algorithms. Swarm Evol Comput 1(1):3–18
Diao R, Shen Q: Deterministic parameter control in harmony search. In: 2010 UK workshop on computational intelligence (UKCI), 2010. ISSN: 2162–7657, pp 1–7
Elsayed SM, Sarker RA, Essam DL, Hamza NM (2014) Testing united multi-operator evolutionary algorithms on the CEC2014 real-parameter numerical optimization. In: 2014 IEEE congress on evolutionary computation (CEC). IEEE, pp 1650–1657
Fan Q, Yan X (2016) Self-adaptive differential evolution algorithm with zoning evolution of control parameters and adaptive mutation strategies. IEEE Trans Cybern 46(1):219–232. https://doi.org/10.1109/TCYB.2015.2399478
Gämperle R, Müller SD, Koumoutsakos P (2002) A parameter study for differential evolution. Adv Intell Syst Fuzzy Syst Evol Comput 10:293–298
García S, Molina D, Lozano M, Herrera F (2009) A study on the use of non-parametric tests for analyzing the evolutionary algorithms behaviour a case study on the CEC2005 special session on real parameter optimization. J Heurist 15(6):617–644
Goldberg DE, Segrest P (1987) Finite Markov chain analysis of genetic algorithms. In: Proceedings of the second international conference on genetic algorithms Bd. 1, p 1
Halder U, Das S, Maity D (2013) A cluster-based differential evolution algorithm with external archive for optimization in dynamic environments. IEEE Trans Cybern 43(3):881–897
Hansen N, Müller SD, Koumoutsakos P (2003) Reducing the time complexity of the derandomized evolution strategy with covariance matrix adaptation (CMA-ES). Evol Comput 11(1):1–18
Hansen N, Ostermeier A (2001) Completely derandomized self-adaptation in evolution strategies. Evol Comput 9(2):159–195
Harl F, Chatelain F, Gouy-Pailler C, Achard S (2016) Bayesian Model for multiple change-points detection in multivariate time series. IEEE Trans Signal Process 64(16):4351–4362. https://doi.org/10.1109/TSP.2016.2566609
He J, Yao X (2001) Drift analysis and average time complexity of evolutionary algorithms. Artif Intell 127(1):57–85
He J, Yao X (2017) Average drift analysis and population scalability. IEEE Trans Evol Comput 21(3):426–439
Hsu CH, Juang CF (2013) Evolutionary robot wall-following control using type-2 fuzzy controller with species-DE-activated continuous ACO. IEEE Trans Fuzzy Syst 21(1):100–112. https://doi.org/10.1109/TFUZZ.2012.2202665
Hu ZB, Su QH, Xiong SW, Hu FG (2008) Self-adaptive hybrid differential evolution with simulated annealing algorithm for numerical optimization. In: 2008 IEEE congress on evolutionary computation (IEEE world congress on computational intelligence) IEEE, pp 1189–1194.
Kamal A, MOhd MN, Elshaikh M, Badlishah R, (2016) Differential evolution (DE) algorithm to optimize Berkeley-MAC protocol for wireless sensor network (WSN). J Theoret Appl Inf Technol 89:2
Karafotias G, Hoogendoorn M, Eiben AE (2015) Parameter control in evolutionary algorithms: trends and challenges. IEEE Trans Evol Comput 19(2):167–187
Kheawhom S (2010) Efficient constraint handling scheme for differential evolutionary algorithm in solving chemical engineering optimization problem. J Ind Eng Chem 16(4):620–628
Ku ML, Chen Y, Liu KJR (2015) Data-driven stochastic models and policies for energy harvesting sensor communications. IEEE J Sel Areas Commun 33(8):1505–1520. https://doi.org/10.1109/JSAC.2015.2391651
Liang JJ, Qin AK, Suganthan PN, Baskar S (2006) Comprehensive learning particle swarm optimizer for global optimization of multimodal functions. IEEE Trans Evol Comput 10(3):281–295
Liang JJ, Qu BY, Suganthan PN (2013) Problem definitions and evaluation criteria for the CEC 2014 special session and competition on single objective real-parameter numerical optimization. In: Computational Intelligence Laboratory, Zhengzhou University, Zhengzhou China and Technical Report, Nanyang Technological University, Singapore
Liu J, Lampinen J (2005) A fuzzy adaptive differential evolution algorithm. Soft Comput 9(6):448–462
Liu ZZ, Wang Y, Yang S, Cai Z (2016) Differential evolution with a two-stage optimization mechanism for numerical optimization. In: 2016 IEEE congress on evolutionary computation (CEC) IEEE
Lou H-L (1995) Implementing the Viterbi algorithm. IEEE Signal Process Mag 12(5):42–52
Mahfoud SW (1993) Finite Markov chain models of an alternative selection strategy for the genetic algorithm. Complex Syst 7(2):155
Mallipeddi R, Suganthan PN, Pan QK, Tasgetiren MF (2011) Differential evolution algorithm with ensemble of parameters and mutation strategies. Appl Soft Comput 11(2):1679–1696
Mohamed MA, Gader P (2000) Generalized hidden Markov models. I. Theoretical frameworks. IEEE Trans Fuzzy Syst 8(1):67–81
Morimoto H (2016) Hidden Markov models and self-organizing maps applied to stroke incidence. Open J Appl Sci 6(03):158
Onwubolu G, Davendra D (2006) Scheduling flow shops using differential evolution algorithm. Eur J Oper Res 171(2):674–692
Qin AK, Huang VL, Suganthan PN (2009) Differential evolution algorithm with strategy adaptation for global numerical optimization. IEEE Trans Evol Comput 13(2):398–417
Rabiner L, Juang B (1986) An introduction to hidden Markov models. IEEE ASSP Mag 3(1):4–16
Jackie Rees, Koehler GJ (2006) Learning genetic algorithm parameters using hidden Markov models. Eur J Oper Res 175(2):806–820
Regulwar DG, Choudhari SA, Raj PA (2010) Differential evolution algorithm with application to optimal operation of multipurpose reservoir. J Water Resour Protect 2(06):560
Ronkkonen J, Kukkonen S, Price KV (2005) Real-parameter optimization with differential evolution. Proc IEEE CEC 1:506–513
Rudolph G (1998) Finite Markov chain results in evolutionary computation: a tour d’horizon. Fundam Inf 35(1–4):67–89
Storn R (1996) On the usage of differential evolution for function optimization. In: Fuzzy Information Processing Society. NAFIPS. 1996 Biennial Conference of the North American IEEE, pp 519–523
Storn R, Price K (1995) Differential evolution—a simple and efficient adaptive scheme for global optimization over continuous spaces. Bd. 3. ICSI Berkeley
Suganthan PN, Hansen N, Liang JJ, Deb K, Chen YP, Auger A, Tiwari S (2005) Problem definitions and evaluation criteria for the CEC 2005 special session on real-parameter optimization. Nanyang Technological University, Singapore; IIT Kanpur Kanpur, India, Forschungsbericht
Tanabe R, Fukunaga AS (2014) Improving the search performance of SHADE using linear population size reduction. In: 2014 IEEE congress on evolutionary computation (CEC) IEEE, pp 1658–1665
Tang L, Dong Y, Liu J (2015) Differential evolution with an individual-dependent mechanism. IEEE Trans Evol Comput 19(4):560–574
Veček N, Črepinšek M, Mernik M (2017) On the influence of the number of algorithms, problems, and independent runs in the comparison of evolutionary algorithms. Appl Soft Comput 54:23–45
Veček N, Mernik M, Črepinšek M (2014) A chess rating system for evolutionary algorithms: a new method for the comparison and ranking of evolutionary algorithms. Inf Sci 277:656–679
Wang Y, Cai Z, Zhang Q (2011) Differential evolution with composite trial vector generation strategies and control parameters. IEEE Trans Evol Comput 15(1):55–66
Wang Y, Li HX, Huang T, Li L (2014) Differential evolution based on covariance matrix learning and bimodal distribution parameter setting. Appl Soft Comput 18:232–247
Wang Y, Liu ZZ, Li J, Li HX, Yen GG (2016) Utilizing cumulative population distribution information in differential evolution. Appl Soft Comput 48:329–346
Wolpert DH, Macready WG (1997) No free lunch theorems for optimization. IEEE Trans Evol Comput 1(1):67–82
Yu WJ, Shen M, Chen WN, Zhan ZH, Gong YJ, Lin Y, Liu O, Zhang J (2014) Differential evolution with two-level parameter adaptation. IEEE Trans Cybern 44(7):1080–1099
Zaman MF, Elsayed SM, Ray T, Sarker RA (2016) Evolutionary algorithms for dynamic economic dispatch problems. IEEE Trans Power Syst 31(2):1486–1495. https://doi.org/10.1109/TPWRS.2015.2428714
Zhang J, Sanderson AC (2009) JADE: adaptive differential evolution with optional external archive. IEEE Trans Evol Comput 13(5):945–958
Author information
Authors and Affiliations
Corresponding author
Electronic supplementary material
Below is the link to the electronic supplementary material.
Rights and permissions
About this article
Cite this article
Keshk, M., Singh, H. & Abbass, H. Automatic estimation of differential evolution parameters using Hidden Markov Models. Evol. Intel. 10, 77–93 (2018). https://doi.org/10.1007/s12065-018-0153-5
Received:
Revised:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s12065-018-0153-5