More Web Proxy on the site http://driver.im/

Article

Metaheuristic optimization: algorithm analysis and open problems

Author:

Xin-She YangAuthors Info & Claims

SEA'11: Proceedings of the 10th international conference on Experimental algorithms

Pages 21 - 32

Published: 05 May 2011 Publication History

Abstract

Metaheuristic algorithms are becoming an important part of modern optimization. A wide range of metaheuristic algorithms have emerged over the last two decades, and many metaheuristics such as particle swarm optimization are becoming increasingly popular. Despite their popularity, mathematical analysis of these algorithms lacks behind. Convergence analysis still remains unsolved for the majority of metaheuristic algorithms, while efficiency analysis is equally challenging. In this paper, we intend to provide an overview of convergence and efficiency studies of metaheuristics, and try to provide a framework for analyzing metaheuristics in terms of convergence and efficiency. This can form a basis for analyzing other algorithms. We also outline some open questions as further research topics.

References

[1]

Auger, A., Doerr, B.: Theory of Randomized Search Heuristics: Foundations and Recent Developments. World Scientific, Singapore (2010).

Digital Library

[2]

Auger, A., Teytaud, O.: Continuous lunches are free plus the design of optimal optimization algorithms. Algorithmica 57(1), 121-146 (2010).

Digital Library

[3]

Bell, W.J.: Searching Behaviour: The Behavioural Ecology of Finding Resources. Chapman & Hall, London (1991).

[4]

Bertsimas, D., Tsitsiklis, J.: Simulated annealing. Stat. Science 8, 10-15 (1993).

[5]

Blum, C., Roli, A.: Metaheuristics in combinatorial optimization: Overview and conceptural comparison. ACM Comput. Surv. 35, 268-308 (2003).

Digital Library

[6]

Chatterjee, A., Siarry, P.: Nonlinear inertia variation for dynamic adapation in particle swarm optimization. Comp. Oper. Research 33, 859-871 (2006).

Digital Library

[7]

Clerc, M., Kennedy, J.: The particle swarm - explosion, stability, and convergence in a multidimensional complex space. IEEE Trans. Evolutionary Computation 6, 58-73 (2002).

Digital Library

[8]

Dorigo, M.: Optimization, Learning and Natural Algorithms. PhD thesis. Politecnico di Milano, Italy (1992).

[9]

Engelbrecht, A.P.: Fundamentals of Computational Swarm Intelligence. Wiley, Chichester (2005).

Digital Library

[10]

Floudas, C.A., Pardalos, P.M.: A Collection of Test Problems for Constrained Global Optimization Algorithms. LNCS, vol. 455. Springer, Heidelberg (1990).

Digital Library

[11]

Floudas, C.A., Pardolos, P.M.: Encyclopedia of Optimization, 2nd edn. Springer, Heidelberg (2009).

[12]

Gamerman, D.: Markov Chain Monte Carlo. Chapman & Hall/CRC (1997).

[13]

Geyer, C.J.: Practical Markov Chain Monte Carlo. Statistical Science 7, 473-511 (1992).

[14]

Ghate, A., Smith, R.: Adaptive search with stochastic acceptance probabilities for global optimization. Operations Research Lett. 36, 285-290 (2008).

Digital Library

[15]

Granville, V., Krivanek, M., Rasson, J.P.: Simulated annealing: A proof of convergence. IEEE Trans. Pattern Anal. Mach. Intel. 16, 652-656 (1994).

Digital Library

[16]

Gutowski, M.: Lévy flights as an underlying mechanism for global optimization algorithms. ArXiv Mathematical Physics e-Prints (June 2001).

[17]

Kennedy, J., Eberhart, R.C.: Particle swarm optimization. In: Proc. of IEEE International Conference on Neural Networks, Piscataway, NJ, pp. 1942-1948 (1995).

[18]

Kennedy, J., Eberhart, R.C.: Swarm intelligence. Academic Press, London (2001).

Digital Library

[19]

Holland, J.: Adaptation in Natural and Artificial systems. University of Michigan Press, Ann Anbor (1975).

[20]

Kirkpatrick, S., Gellat, C.D., Vecchi, M.P.: Optimization by simulated annealing. Science 220, 670-680 (1983).

[21]

Matthews, C., Wright, L., Yang, X.S.: Sensitivity Analysis, Optimization, and Sampling Methodds Applied to Continous Models. National Physical Laboratory Report, UK (2009).

[22]

Neumann, F., Witt, C.: Bioinspired Computation in Combinatorial Optimization: Algorithms and Their Computational Complexity. Springer, Heidelberg (2010).

Digital Library

[23]

Nolan, J.P.: Stable distributions: models for heavy-tailed data. American University (2009).

[24]

Pavlyukevich, I.: Lévy flights, non-local search and simulated annealing. J. Computational Physics 226, 1830-1844 (2007).

Digital Library

[25]

Rebennack, S., Arulselvan, A., Elefteriadou, L., Pardalos, P.M.: Complexity analysis for maximum flow problems with arc reversals. J. Combin. Optimization 19(2), 200-216 (2010).

[26]

Reynolds, A.M., Rhodes, C.J.: The Lévy fligth paradigm: random search patterns and mechanisms. Ecology 90, 877-887 (2009).

[27]

Steinhöfel, K., Albrecht, A.A., Wong, C.-K.: Convergence analysis of simulated annealing-based algorithms solving flow shop scheduling problems. In: Bongiovanni, G., Petreschi, R., Gambosi, G. (eds.) CIAC 2000. LNCS, vol. 1767, pp. 277-290. Springer, Heidelberg (2000).

Digital Library

[28]

Sobol, I.M.: A Primer for the Monte Carlo Method. CRC Press, Boca Raton (1994).

[29]

Talbi, E.G.: Metaheuristics: From Design to Implementation. Wiley, Chichester (2009).

Digital Library

[30]

Viswanathan, G.M., Buldyrev, S.V., Havlin, S., da Luz, M.G.E., Raposo, E.P., Stanley, H.E.: Lévy flight search patterns of wandering albatrosses. Nature 381, 413-415 (1996).

[31]

Wolpert, D.H., Macready, W.G.: No free lunch theorems for optimisation. IEEE Transaction on Evolutionary Computation 1, 67-82 (1997).

Digital Library

[32]

Yang, X.S.: Nature-Inspired Metaheuristic Algorithms. Luniver Press (2008).

Digital Library

[33]

Yang, X.S.: Engineering Optimization: An Introduction with Metaheuristic Applications. John Wiley & Sons, Chichester.

Digital Library

[34]

Yang, X.S.: Firefly algorithm, stochastic test functions and design optimisation. Int. J. Bio-Inspired Computation 2, 78-84 (2010).

Digital Library

[35]

Yang, X.S., Deb, S.: Engineering optimization by cuckoo search. Int. J. Math. Modelling & Num. Optimization 1, 330-343 (2010).

Cited By

Singh RAwasthi LSikka G(2022)Towards Metaheuristic Scheduling Techniques in Cloud and Fog: An Extensive Taxonomic ReviewACM Computing Surveys10.1145/349452055:3(1-43)Online publication date: 3-Feb-2022
https://dl.acm.org/doi/10.1145/3494520
Brajević IIgnjatović J(2019)An upgraded firefly algorithm with feasibility-based rules for constrained engineering optimization problemsJournal of Intelligent Manufacturing10.1007/s10845-018-1419-630:6(2545-2574)Online publication date: 1-Aug-2019
https://dl.acm.org/doi/10.1007/s10845-018-1419-6
Biswas ABiswas B(2017)Analyzing evolutionary optimization and community detection algorithms using regression line dominanceInformation Sciences: an International Journal10.1016/j.ins.2017.02.050396:C(185-201)Online publication date: 1-Aug-2017
https://dl.acm.org/doi/10.1016/j.ins.2017.02.050
Show More Cited By

Metaheuristic optimization: algorithm analysis and open problems
1. Mathematics of computing
  1. Probability and statistics
    1. Probabilistic reasoning algorithms

Recommendations

A modified VNS metaheuristic for max-bisection problems

Variable neighborhood search (VNS) metaheuristic as presented in Festa et al. [Randomized heuristics for the MAX-CUT problem, Optim. Methods Software 17 (2002) 1033-1058] can obtain high quality solution for max-cut problems. Therefore, it is worthwhile ...
Combination of Metaheuristic and Exact Algorithms for Solving Set Covering-Type Optimization Problems

We propose a new generic framework for solving combinatorial optimization problems that can be modeled as a set covering problem. The proposed algorithmic framework combines metaheuristics with exact algorithms through a guiding mechanism based on ...
Solving weighted Max-Sat optimization problems using a Taboo Scatter Search metaheuristic
SAC '04: Proceedings of the 2004 ACM symposium on Applied computing

In the last three decades, many researchers have focused on the Satisfiability problem and on many of its variants, in particular, on the Weighted Maximum Satisfiability problem (Max-W-Sat). The latter is known to be difficult to solve, due to a high ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Guide Proceedings

SEA'11: Proceedings of the 10th international conference on Experimental algorithms

May 2011

460 pages

ISBN:9783642206610

Editors:
Panos M. Pardalos,
Steffen Rebennack
Colorado School of Mines, Golden, CO

Publisher

Springer-Verlag

Berlin, Heidelberg

Publication History

Published: 05 May 2011

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

6
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 18 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Singh RAwasthi LSikka G(2022)Towards Metaheuristic Scheduling Techniques in Cloud and Fog: An Extensive Taxonomic ReviewACM Computing Surveys10.1145/349452055:3(1-43)Online publication date: 3-Feb-2022
https://dl.acm.org/doi/10.1145/3494520
Brajević IIgnjatović J(2019)An upgraded firefly algorithm with feasibility-based rules for constrained engineering optimization problemsJournal of Intelligent Manufacturing10.1007/s10845-018-1419-630:6(2545-2574)Online publication date: 1-Aug-2019
https://dl.acm.org/doi/10.1007/s10845-018-1419-6
Biswas ABiswas B(2017)Analyzing evolutionary optimization and community detection algorithms using regression line dominanceInformation Sciences: an International Journal10.1016/j.ins.2017.02.050396:C(185-201)Online publication date: 1-Aug-2017
https://dl.acm.org/doi/10.1016/j.ins.2017.02.050
El-Qulity SMohamed A(2016)A generalized national planning approach for admission capacity in higher educationComputational Intelligence and Neuroscience10.1155/2016/52073622016(21-21)Online publication date: 1-Jan-2016
https://dl.acm.org/doi/10.1155/2016/5207362
Ghodrati AMalakooti MSoleimani M(2012)A hybrid ICA/PSO algorithm by adding independent countries for large scale global optimizationProceedings of the 4th Asian conference on Intelligent Information and Database Systems - Volume Part III10.1007/978-3-642-28493-9_12(99-108)Online publication date: 19-Mar-2012
https://dl.acm.org/doi/10.1007/978-3-642-28493-9_12
Ghodrati ALotfi S(2012)A hybrid CS/PSO algorithm for global optimizationProceedings of the 4th Asian conference on Intelligent Information and Database Systems - Volume Part III10.1007/978-3-642-28493-9_11(89-98)Online publication date: 19-Mar-2012
https://dl.acm.org/doi/10.1007/978-3-642-28493-9_11

View Options

View options

Media

Figures

Other

Tables

View Table of Contents