Skip to main content
SpringerLink
Log in

Dynamic Simulated Annealing with Adaptive Neighborhood Using Hidden Markov Model

  • Chapter
  • First Online:
Heuristics for Optimization and Learning

Part of the book series: Studies in Computational Intelligence ((SCI,volume 906))

Abstract

The Simulated Annealing (SA) is a stochastic local search algorithm. Its efficiency involves the adaptation of the neighbourhood structure. In this paper, we integrate Hidden Markov Model (HMM) in SA to dynamically adapt the neighbourhood structure of the simulated annealing at each iteration. HMM has proven its ability to predict the optimal behavior of the neighbourhood function based on the search history. An experiments were performed on many benchmark functions and compared with others SA variants.

This is a preview of subscription content, log in via an institution to check access.

Access this chapter

Log in via an institution
Chapter
USD 29.95
Price excludes VAT (USA)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
eBook
USD 149.00
Price excludes VAT (USA)
  • Available as EPUB and PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book
USD 199.99
Price excludes VAT (USA)
  • Compact, lightweight edition
  • Dispatched in 3 to 5 business days
  • Free shipping worldwide - see info
Hardcover Book
USD 199.99
Price excludes VAT (USA)
  • Durable hardcover edition
  • Dispatched in 3 to 5 business days
  • Free shipping worldwide - see info

Tax calculation will be finalised at checkout

Purchases are for personal use only

Institutional subscriptions

Similar content being viewed by others

References

  1. S. Kirkpatrik, Optimization by simulated annealing. Science 220(4598), 671–680 (1983)

    Article  MathSciNet  Google Scholar 

  2. E. Aarts, F. Bont, E. Habers, P. van Laarhoven, Parallel implementations of the statistical cooling algorithm. Integr. VLSI J. 4, 209–238 (1986)

    Article  Google Scholar 

  3. P. Banerjee, M. Jones, A parallel simulated annealing algorithm for standard cell placement on a hypercube computer, in The Proceedings of the IEEE International Conference on Computer-Aided Design (1986), pp. 34–37

    Google Scholar 

  4. A. Casotto, F. Romeo, A. Sangiovanni-Vincentelli, A parallel simulated annealing algorithm for the placement of macro-cells, in The Proceedings of the IEEE International Conference on Computer-Aided Design (1986), pp. 30–33

    Google Scholar 

  5. H.H. Szu, R.L. Hartley, Fast simulated annealing. Phys. Lett. A 122, 157–162 (1987)

    Article  Google Scholar 

  6. P. Melin, F. Olivas, O. Castillo, F. Valdez, J. Soria, M. Valdez, Optimal design of fuzzy classification systems using PSO with dynamic parameter adaptation through fuzzy logic. Expert Syst. Appl. 40(8), 3196–3206 (2013)

    Article  Google Scholar 

  7. R. Battiti, M. Brunato, Reactive Search and Intelligent Optimization. Computer Science Interfaces (Springer, Berlin, 2008)

    Google Scholar 

  8. A. Corana, M. Marchesi, C. Martini, S. Ridella, Minimizing multimodal functions of continuous variables with the simulated annealing algorithm. ACM Trans. Math. Softw. 13(3), 262–280 (1987)

    Article  MathSciNet  Google Scholar 

  9. M. Miki, T. Hiroyasu, K. Ono, Simulated annealing with advanced adaptive neighborhood, in The 2nd International Workshop on Intelligent Systems Design and Application (2002), pp. 113–118

    Google Scholar 

  10. M. Miki, S. Hiwa, Simulated annealing using an adaptive search vector, in Cybernetics and Intelligent Systems (2006)

    Google Scholar 

  11. M.J.D. Powell, An efficient method for finding the minimum of a function of several variables without calculating derivatives. Comput. J. 7(2), 155–162 (1964)

    Google Scholar 

  12. R.T. Haftka, Z. Gurdal, Elements of Structural Optimization. Solid Mechanics and Its Applications, vol. 11, Chap. 4 (1992), p. 124

    Google Scholar 

  13. L. Rabiner, A tutorial on hidden Markov models and selected applications in speech recognition. Proc. IEEE 77(2), 257–286 (1989)

    Article  Google Scholar 

  14. M. Lalaoui, A. El Afia, A versatile generalized simulated annealing using type-2 fuzzy controller for the mixed-model assembly line balancing problem. IFAC-PapersOnLine 52(13), 2804–2809 (2019). https://doi.org/10.1016/j.ifacol.2019.11.633

    Article  Google Scholar 

  15. A. El Afia, M. Lalaoui, R. Chiheb, A self-controlled simulated annealing algorithm using hidden Markov model state classification. Procedia Comput. Sci. 148, 512–521 (2019). https://doi.org/10.1016/j.procs.2019.01.024

  16. M. Lalaoui, A. El Afia, A fuzzy generalized simulated annealing for a simple assembly line balancing problem. IFAC-PapersOnLine 51(32), 600–605 (2018). https://doi.org/10.1016/j.ifacol.2018.11.489

    Article  Google Scholar 

  17. M. Lalaoui, A. El Afia, R. Chiheb, A self-tuned simulated annealing algorithm using hidden Markov model. Int. J. Electr. Comput. Eng. (IJECE) 8(1), 291–298 (2017). https://doi.org/10.11591/ijece.v8i1.pp291-298

    Article  Google Scholar 

  18. M. Lalaoui, A. El Afia, R. Chiheb, A self-tuned simulated annealing algorithm using hidden Markov model, in The International Conference on Learning and Optimization Algorithms: Theory and Application (LOPAL’2018) (2018). https://doi.org/10.1145/3230905.3230963

  19. A. El Afia, M. Lalaoui, R. Chiheb, Fuzzy logic controller for an adaptive Huang cooling of simulated annealing, in The 2nd International Conference on Big Data, Cloud and Applications (CloudTech’17) IEEE Conference (2017). https://doi.org/10.1145/3090354.3090420

  20. M. Lalaoui, A. El Afia, R. Chiheb, A self-adaptive very fast simulated annealing based on hidden Markov model, in The 3rd International Conference on Cloud Computing Technologies and Applications, ACM Conference (2017). https://doi.org/10.1109/CloudTech.2017.8284698

  21. M. Lalaoui, A. El Afia, R. Chiheb, Hidden Markov model for a self-learning of simulated annealing cooling law, in The 5th International Conference on Multimedia Computing and Systems IEEE Conference, ICMCS’16 (2016). https://doi.org/10.1109/ICMCS.2016.7905557

  22. S. Bouzbita, A. El Afia, R. Faizi, A novel based hidden Markov model approach for controlling the ACS-TSP evaporation parameter, in The 5th International Conference on Multimedia Computing and Systems (ICMCS) (2016), pp. 633–638. https://doi.org/10.1109/ICMCS.2016.7905544

  23. S. Bouzbita, A. El Afia, R. Faizi, M. Zbakh, Dynamic adaptation of the ACS-TSP local pheromone decay parameter based on the hidden Markov model, in The 2nd International Conference on Cloud Computing Technologies and Applications (CloudTech) (2016), pp. 344–349. https://doi.org/10.1109/CloudTech.2016.7847719

  24. A. El Afia, S. Bouzbita, R. Faizi, The effect of updating the local pheromone on ACS performance using fuzzy logic. Int. J. Electr. Comput. Eng. 7(4), 2161–2168 (2017). https://doi.org/10.11591/ijece.v7i3.pp2161-2168

    Article  Google Scholar 

  25. S. Bouzbita, A. El Afia, R. Faizi, Hidden Markov model classifier for the adaptive ACS-TSP pheromone parameters, in Bioinspired Heuristics for Optimization, vol. 774. (Springer, Berlin, 2018), p. 153. https://doi.org/10.1007/978-3-319-95104-1_10

  26. S. Bouzbita, A. El Afia, R. Faizi, Parameter adaptation for ant colony system algorithm using hidden Markov model for TSP problems, in The Proceedings of the International Conference on Learning and Optimization Algorithms: Theory and Applications (ACM, 2018), p. 6. https://doi.org/10.1145/3230905.3230962

  27. S. Bouzbita, A. El Afia, R. Faizi, Adjusting population size of ant colony system using fuzzy logic controller, in The International Conference on Computational Collective Intelligence, vol. 11684 (Springer, Berlin, 2019), pp. 309–320. https://doi.org/10.1007/978-3-030-28374-2_27

  28. A. El Afia, M. Sarhan, O. Aoun, A probabilistic finite state machine design of particle swarm optimization, in Bioinspired Heuristics for Optimization (Springer, Cham, 2019), pp. 185–201. https://doi.org/10.1007/978-3-319-95104-1_12

  29. A. El Afia, O. Aoun, S. Garcia, Adaptive cooperation of multi-swarm particle swarm optimizer-based hidden Markov model. Prog. Artif. Intell. 8, 441–452 (2019). https://doi.org/10.1007/s13748-019-00183-1

    Article  Google Scholar 

  30. O. Aoun, M. Sarhani, A. El Afia, Hidden Markov model classifier for the adaptive particle swarm optimization, in Recent Developments in Metaheuristics (Springer International Publishing, Cham, 2018), pp. 1–15. https://doi.org/10.1007/978-3-319-58253-5_1

  31. O. Aoun, M. Sarhani, A. El Afia, Particle swarm optimisation with population size and acceleration coefficients adaptation using hidden Markov model state classification. Int. J. Metaheuristics 7(1), 1–29 (2018). Inderscience Publishers (IEL). https://doi.org/10.1504/IJMHEUR.2018.091867

  32. O. Aoun, A. El Afia, S. Garcia, Self inertia weight adaptation for the particle swarm optimization, in Proceedings of the International Conference on Learning and Optimization Algorithms: Theory and Applications (ACM, 2018), pp. 8:1–8:6. https://doi.org/10.1145/3230905.3230964

  33. A. El Afia, M. Sarhani, O. Aoun, Hidden Markov model control of inertia weight adaptation for particle swarm optimization. IFAC-PapersOnLine 50(1), 9997–10002 (2017). https://doi.org/10.1016/j.ifacol.2017.08.2030

    Article  Google Scholar 

  34. O. Aoun, M. Sarhani, A. El Afia, Investigation of hidden Markov model for the tuning of metaheuristics in airline scheduling problems. IFAC-PapersOnLine 49(3), 347–352 (2016). https://doi.org/10.1016/j.ifacol.2016.07.058

    Article  Google Scholar 

  35. P. Kouvelis, W.-C. Chiang, J.A. Fitzsimmons, Simulated annealing procedures for machine layout problems in the presence of zoning constraints. Eur. J. Oper. Res. 57(22), 203–223 (1992)

    Article  Google Scholar 

  36. M. Friedman, The use of ranks to avoid the assumption of normality implicit in the analysis of variance. J. Am. Stat. Assoc. 32(200), 675–701 (1937)

    Article  Google Scholar 

  37. A. LaTorre, S. Muelas, J.M. Pena, A comprehensive comparison of large-scale global optimizers. Inf. Sci. 316, 517–549 (2015)

    Article  Google Scholar 

  38. D.J. Sheskin, Handbook of Parametric and Nonparametric Statistical Procedures, 3rd edn. (Chapman & Hall/CRC, Boca Raton, 2004)

    Google Scholar 

Download references

Author information

Authors and Affiliations

  1. National School of Computer Science and Systems Analysis, Mohammed V University, Rabat, Morocco

    Mohamed Lalaoui, Abdellatif El Afia & Raddouane Chiheb

Authors
  1. Mohamed Lalaoui
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Abdellatif El Afia
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Raddouane Chiheb
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Mohamed Lalaoui .

Editor information

Editors and Affiliations

  1. Laboratory of Logistics and Optimization of Industrial Systems (LOSI), University of Technology of Troyes (UTT), Troyes Cedex, France

    Farouk Yalaoui

  2. Industrial System Optimization Laboratory, University of Technology of Troyes (UTT), Troyes Cedex, France

    Lionel Amodeo

  3. CRISTAL UMR CNRS 9189 & INRIA Lille Nord Europe, Parc Scientifique de la Haute Borne, Polytech'Lille - Univrsité of Lille, Villeneuve d'Ascq, France

    El-Ghazali Talbi

Rights and permissions

Reprints and permissions

Copyright information

© 2021 The Editor(s) (if applicable) and The Author(s), under exclusive license to Springer Nature Switzerland AG

About this chapter

Check for updates. Verify currency and authenticity via CrossMark

Cite this chapter

Lalaoui, M., El Afia, A., Chiheb, R. (2021). Dynamic Simulated Annealing with Adaptive Neighborhood Using Hidden Markov Model. In: Yalaoui, F., Amodeo, L., Talbi, EG. (eds) Heuristics for Optimization and Learning. Studies in Computational Intelligence, vol 906. Springer, Cham. https://doi.org/10.1007/978-3-030-58930-1_11

Download citation

Publish with us

Policies and ethics

Search

Navigation