Weitere Artikel dieser Ausgabe durch Wischen aufrufen
The online version of this article (doi:10.1007/s11721-016-0129-y) contains supplementary material, which is available to authorized users.
During the last two decades, a large number of metaheuristics have been proposed, leading to various studies that call for a deeper insight into the behaviour, efficiency and effectiveness of such methods. Among numerous concerns that are briefly reviewed in this paper, the presence of a structural bias (i.e. the tendency, not justified by the fitness landscape, to visit some regions of the search space more frequently than other regions) has recently been detected in simple versions of the genetic algorithm and particle swarm optimization. As of today, it remains unclear how frequently such a behaviour occurs in population-based swarm intelligence and evolutionary computation methods, and to what extent structural bias affects their performance. The present study focuses on the search for structural bias in various variants of particle swarm optimization and differential evolution algorithms, as well as in the traditional direct search methods proposed by Nelder–Mead and Rosenbrock half a century ago. We found that these historical direct search methods are structurally unbiased. However, most tested new metaheuristics are structurally biased, and at least some presence of structural bias can be observed in almost all their variants. The presence of structural bias seems to be stronger in particle swarm optimization algorithms than in differential evolution algorithms. The relationships between the strength of the structural bias and the dimensionality of the search space, the number of allowed function calls and the population size are complex and hard to generalize. For 14 algorithms tested on the CEC2011 real-world problems and the CEC2014 artificial benchmarks, no clear relationship between the strength of the structural bias and the performance of the algorithm was found. However, at least for artificial benchmarks, such old and structurally unbiased methods like Nelder–Mead algorithm performed relatively well. This is a warning that the presence of structural bias in novel metaheuristics may hamper their search abilities.
Ampellio, E., & Vassio, L. (2016). A hybrid swarm-based algorithm for single-objective optimization problems involving high-cost analyses. Swarm Intelligence, 10, 99–121. CrossRef
Bonyadi, M. R., & Michalewicz, Z. (2014). A locally convergent rotationally invariant particle swarm optimization algorithm. Swarm Intelligence, 8, 159–198. CrossRef
Bonyadi, M. R., & Michalewicz, Z. (2016). Particle swarm optimization for single objective continuous space problems: A review. Evolutionary Computation. doi: 10.1162/EVCO_r_00180.
Cai, Z. H., Gong, W. Y., Ling, C. X., & Zhang, H. (2011). A clustering-based differential evolution for global optimization. Applied Soft Computing, 11(1), 1363–1379. CrossRef
Chen, W. N., Zhang, J., Lin, Y., Chen, N., Zhan, Z. H., Chung, H. S. H., et al. (2013). Particle swarm optimization with an aging leader and challengers. IEEE Transactions on Evolutionary Computation, 17(2), 241–258. CrossRef
Chinta, S., Kommadath, R., & Kotecha, P. (2016). A note on multi-objective improved teaching-learning based optimization algorithm (MO-ITLBO). Information Sciences, 373, 337–350. CrossRef
Cleghorn, C. W., & Engelbrecht, A. P. (2014). A generalized theoretical deterministic particle swarm model. Swarm Intelligence, 8, 35–59. CrossRef
Cleghorn, C. W., & Engelbrecht, A. P. (2015). Particle swarm variants: Standardized convergence analysis. Swarm Intelligence, 9, 177–203. CrossRef
Clerc, M., & Kennedy, J. (2002). The particle swarm—Explosion, stability, and convergence in a multidimensional complex space. IEEE Transactions on Evolutionary Computation, 6(1), 58–73. CrossRef
Črepinšek, M., Liu, S. H., & Mernik, L. (2012). A note on teaching-learning-based optimization algorithm. Information Sciences, 212, 79–93. CrossRef
Črepinšek, M., Liu, S. H., & Mernik, M. (2014). Replication and comparison of computational experiments in applied evolutionary computing: Common pitfalls and guidelines to avoid them. Applied Soft Computing, 19, 161–170. CrossRef
Črepinšek, M., Liu, S. H., Mernik, L., & Mernik, M. (2016). Is a comparison of results meaningful from the inexact replications of computational experiments? Soft Computing, 20(1), 223–235. CrossRef
Das, S., Abraham, A., & Konar, A. (2008). Particle swarm optimization and differential evolution algorithms: Technical analysis, applications and hybridization perspectives. In Studies in computational intelligence (Vol. 116). Berlin: Springer.
Das, S., Abraham, A., Chakraboty, U. K., & Konar, A. (2009). Differential evolution using a neighborhood-based mutation operator. IEEE Transactions on Evolutionary Computation, 13(3), 526–553. CrossRef
Das, S., Mullick, S. S., & Suganthan, P. N. (2016). Recent advances in differential evolution—An updated survey. Swarm and Evolutionary Computation, 27, 1–30. CrossRef
Das, S., & Suganthan, P. N. (2010). Problem definitions and evaluation criteria for CEC 2011 competition on testing evolutionary algorithms on real world optimization problems. Jadavpur Univ., Nanyang Technol. Univ., Kolkata, India, Technical Report, Dec. 2010.
Das, S., & Suganthan, P. N. (2011). Differential evolution: A survey of the state-of-the-art. IEEE Transactions on Evolutionary Computation, 15(1), 27–54.
Derrac, J., Garcia, S., Hui, S., Suganthan, P. N., & Herrera, F. (2014). Analyzing convergence performance of evolutionary algorithms: A statistical approach. Information Sciences, 289, 41–58. CrossRef
Draa, A. (2015). On the performances of the flower pollination algorithm—Qualitative and quantitative analyses. Applied Soft Computing, 34, 349–371. CrossRef
Duéñez-Guzmán, E. A., & Vose, M. D. (2013). No free lunch and benchmarks. Evolutionary Computation, 21(2), 293–312. CrossRef
Dymond, A. S., Engelbrecht, A. P., Kok, S., & Heyns, P. S. (2015). Tuning optimization algorithms under multiple objective function evaluation budgets. IEEE Transactions on Evolutionary Computation, 19(3), 341–358. CrossRef
Eberhart, R. C., & Kennedy, J. (1995). A new optimizer using particle swarm theory. In Proceedings of the 6th international symposium on micro machine and human science (pp. 39–43). Institute of Electrical and Electronics Engineers (IEEE).
Eiben, A. E., & Jelasity, M. (2002). A critical note on experimental research methodology in EC. In Proceedings of the 2002 Congress (CEC2002) (Vol. 1, pp. 582–587). Institute of Electrical and Electronics Engineers (IEEE).
Eiben, A. E., & Smith, J. (2015). From evolutionary computation to the evolution of things. Nature, 521, 476–482. CrossRef
Elsayed, S. M., Sarker, R. A. & Essam, D. L. (2011). GA with a new multi-parent crossover for constrained optimization. In IEEE Congress on evolutionary computation 2011 (pp. 857–864). Institute of Electrical and Electronics Engineers (IEEE).
Elsayed, S. M., Sarker, R. A., & Essam, D. L. (2014). A new genetic algorithm for solving optimization problems. Engineering Applications of Artificial Intelligence, 27, 57–69. CrossRef
Epitropakis, M. G., Plagianakos, V. P., & Vrahatis, M. N. (2012). Evolving cognitive and social experience in particle swarm optimization through differential evolution: A hybrid approach. Information Sciences, 216, 50–92. CrossRef
Fister, I, Jr., Maklar, U., Brest, J., & Fister, I. (2016). A new population-based nature-inspired algorithm every month: Is the current era coming to the end? In Proceedings of the 3rd Student Computer Science Research Conference (pp. 33–37). Ljubljana: Slovenia, University of Primorska Press.
Fogel, D. B. (2000). What is evolutionary computation? IEEE Spectrum, 37(2), 26–32. CrossRef
Fong, S., Wang, X., Xu, Q., Wong, R., Fiaidhi, J., & Mohammed, S. (2016). Recent advances in metaheuristic algorithms: Does the Makara dragon exist? The Journal of Supercomputing, 72, 3764–3786. CrossRef
Gämperle, R., Müller, S. D., & Koumoutsakos, P. (2002). A parameter study of differential evolution. In Advances in intelligent systems, fuzzy systems, evolutionary computation. Interlaken: WSEAS Press.
Garcia, S., & Herrera, F. (2008). An extension on “Statistical comparisons of classifiers over multiple data sets” for all pairwise comparisons. Journal of Machine Learning Research, 9, 2677–2694. MATH
Hall, J. C., Mills, B., Nguyen, H., & Hall, J. L. (1996). Methodologic standards in surgical trials. Surgery, 119(4), 466–472. CrossRef
Helwig, S., Branke, J., & Mostaghim, S. (2013). Experimental analysis of bound handling techniques in particle swarm optimization. IEEE Transactions on Evolutionary Computation, 17(2), 259–271. CrossRef
Holland, I. H. (1975). Adaptation in natural and artificial systems. Ann Arbor: University of Michigan Press.
Hu, Z. B., Su, Q. H., Yang, X. S., & Xiong, Z. G. (2016). Not guaranteeing convergence of differential evolution on a class of multimodal functions. Applied Soft Computing, 41, 479–487. CrossRef
Islam, S. M., Das, S., Ghosh, S., Roy, S., & Suganthan, P. N. (2012). An adaptive differential evolution algorithm with novel mutation and crossover strategies for global numerical optimization. IEEE Transactions on Systems, Man and Cybernetics, Part B - Cybernetics, 42(2), 482–500. CrossRef
Karaboga, D., & Basturk, B. (2008). On the performance of artificial bee colony (ABC) algorithm. Applied Soft Computing, 8, 687–697. CrossRef
Kennedy, J., & Eberhart, R. C. (1995). Particle swam optimization. In Proceedings of the IEEE international conference on neural networks (pp. 1942–1948). Institute of Electrical and Electronics Engineers (IEEE), 1995.
Kitchenham, B. A., Pfleeger, S. L., Pickard, L. M., Jones, P. W., Hoaglin, D. C., El Emam, K., et al. (2002). Preliminary guidelines for empirical research in software engineering. IEEE Transactions on Software Engineering, 28(8), 721–734. CrossRef
Kononova, A. V., Corne, D. W., De Wilde, P., Shneer, V., & Caraffini, F. (2015). Structural bias in population-based algorithms. Information Sciences, 298, 468–490. CrossRef
Köppen, M., Wolpert, D. H., & Macready, W. G. (2001). Remarks on a recent paper on the “ No free lunch” theorems. IEEE Transactions on Evolutionary Computation, 5(3), 295–296. CrossRef
Leonard, B. J., Engelbrecht, A. P., & Cleghorn, C. W. (2015). Critical considerations on angle modulated particle swarm optimizers. Swarm Intelligence, 9, 291–314. CrossRef
Liang, J. J., Qu, B. Y., & Suganthan, P. N. (2013). Problem definitions and evaluation criteria for the CEC 2014 special session and competition on single objective real-parameter numerical optimization. Technical Report 201311, Computational Intelligence Laboratory, Zhengzhou University, Zhengzhou, China and Nanyang Technological University, Singapore.
Liang, J. J., Qin, A. K., Suganthan, P. N., & Baskar, S. (2006). Comprehensive learning particle swarm optimizer for global optimization of multimodal functions. IEEE Transactions on Evolutionary Computation, 10(3), 281–295. CrossRef
Liao, T., Aydin, D., & Stützle, T. (2013). Artificial bee colonies for continuous optimization: Experimental analysis and improvements. Swarm Intelligence, 7, 327–356. CrossRef
Malan, K. M., & Engelbrecht, A. P. (2013). A survey of techniques for characterising fitness landscapes and some possible ways forward. Information Sciences, 241, 148–163. CrossRef
Malan, K. M., & Engelbrecht, A. P. (2014). Characterising the searchability of continuous optimisation problems for PSO. Swarm Intelligence, 8, 275–302. CrossRef
Michalewicz, Z. (2012). Quo Vadis, evolutionary computation? On a growing gap between theory and practice. In Proceedings of the 2012 World Congress conference on advances in computational intelligence (WCCI’12) (pp. 98–121). Berlin: Springer.
Muñoz, A. A., & Smith-Miles, K. A. (2016). Performance analysis of continuous black-box optimization algorithms via footprints in instance space. Evolutionary Computation. doi: 10.1162/EVCO_a_00194.
Muñoz, M. A., Sun, Y., Kirley, M., & Halgamuge, S. K. (2015). Algorithm selection for black-box continuous optimization problems: A survey on methods and challenges. Information Sciences, 317, 224–245. CrossRef
Neri, F., & Tirronen, V. (2010). Recent advances in differential evolution: A survey and experimental analysis. Artificial Intelligence Review, 33(1–2), 61–106. CrossRef
Piotrowski, A. P. (2015). Regarding the rankings of optimization heuristics based on artificially-constructed benchmark functions. Information Sciences, 297, 191–201. CrossRef
Piotrowski, A. P. (2016). Review of differential evolution population size. Swarm and Evolutionary Computation. doi: 10.1016/j.swevo.2016.05.003.
Piotrowski, A. P., & Napiorkowski, M. J. (2016). May the same numerical optimizer be used when searching either for the best or for the worst solution to a real-world problem? Information Sciences, 373, 124–148. CrossRef
Piotrowski, A. P., Napiorkowski, J. J., & Rowinski, P. M. (2014). How novel is the “novel” black hole optimization approach? Information Sciences, 267, 191–200. CrossRef
Poli, R., Kennedy, J., & Blackwell, T. (2007). Particle swarm optimization. An overview. Swarm Intelligence, 1, 33–57. CrossRef
Pošik, P., Huyer, W., & Pal, L. (2012). A comparison of global search algorithms for continuous black box optimization. Evolutionary Computation, 20(4), 509–541. CrossRef
Press, W. H., Flannery, B. P., Teukolsky, S. A., & Vetterling, W. T. (2006). Numerical recipes in FORTRAN 77: The art of scientific computing. Cambridge: Cambridge University Press. MATH
Price, K. V., Storn, R. M., & Lampinen, J. A. (2005). Differential evolution. A practical approach to global optimization. Berlin: Springer. MATH
Qin, A. K., Huang, V. L., & Suganthan, P. N. (2009). Differential evolution algorithm with strategy adaptation for global numerical optimization. IEEE Transactions on Evolutionary Computation, 13(2), 398–417. CrossRef
Rada-Vilela, J., Johnston, M., & Zhang, M. (2014). Deception, blindness and disorientation in particle swarm optimization applied to noisy problems. Swarm Intelligence, 8, 247–273. CrossRef
Rechenberg, I. (1973). Evolutionsstrategie: Optimierung technischer Systeme nach Prinzipien der biologischen Evolution. Stuttgart: Frommann-Holzboog.
Rowe, J. E., Vose, M. D., & Wright, A. H. (2009). Reinterpreting no free lunch. Evolutionary Computation, 17(1), 117–129. CrossRef
Salomon, R. (1996). Re-evaluating genetic algorithm performance under coordinate rotation on benchmark functions. A survey of some theoretical and practical aspects of genetic algorithms. BioSystems, 39, 263–278. CrossRef
Schumacher, C., Vose, M. D., & Whitley, L. D. (2001). The no free lunch and problem description length. In Proceedings of the 2001 genetic and evolutionary computation conference (pp. 565–570). Morgan Kaufmann.
Shi, Y., & Eberhart, R. C. (1998). A modified particle swarm optimizer. In Proceeding in IEEE Congress on Evolutionary Computation (CEC1998) (pp. 69–73). Institute of Electrical and Electronics Engineers (IEEE).
Sörensen, K., Sevaux, M., & Glover, F. (2015). A history of Metaheuristics. In Proceedings of ORBEL29—29th Belgian conference on Operations Research.
Stephens, M. A. (1970). Use of the Kolmogorov–Smirnov, Cramer–von Mises and related statistics without extensive tables. Journal of the Royal Statistical Society Series B - Statistical Methodology, 32, 115–122. MATH
Storn, R., & Price, K. V. (1995). Differential evolution—A simple and efficient adaptive scheme for global optimization over continuous spaces. Tech. Report TR-95-012, International Computer Sciences Institute, Berkeley, California, USA.
Suganthan, P. N., Hansen, N., Liang, J. J., Deb, K., Chen, Y. P., Auger, A., et al. (2005). Problem definitions and evaluation criteria for the CEC 2005 special session on real-parameter optimization. Nanyang Technol. Univ., Singapore, Tech. Rep. KanGAL #2005005, IIT Kanpur, India.
Ulas, A., Yildiz, O. T., & Alpaydin, E. (2012). Cost-conscious comparison of supervised learning algorithms over multiple data sets. Pattern Recognition, 45, 1772–1781. CrossRef
Van den Bergh, F., & Engelbrecht, A. P. (2004). A cooperative approach to particle swarm optimization. IEEE Transactions on Evolutionary Computation, 8(3), 225–239. CrossRef
Weyland, D. (2010). A rigorous analysis of the harmony search algorithm—How the research community can be misled by a “novel” methodology. International Journal of Applied Metaheuristic Computing, 1–2, 50–60. CrossRef
Weyland, D. (2015). A critical analysis of the harmony search algorithm—How not to solve sudoku. Operations Research Perspectives, 2, 97–105. CrossRef
Whitley, D., & Rowe, J. (2008). Focused no free lunch theorems. In Proceedings of the 10th annual conference on genetic and evolutionary computation (pp. 811–818). Association for Computing Machinery (ACM), 2008.
Wolpert, D. H., & Macready, W. G. (1997). No free lunch theorems for optimization. IEEE Transactions on Evolutionary Computation, 1(1), 67–82. CrossRef
Xin, B., Chen, J., Zhang, J., Fang, H., & Peng, Z. H. (2012). Hybridizing differential evolution and particle swarm optimization to design powerful optimizers: A review and taxonomy. IEEE Transactions on Systems, Mac and Cybernetics, Part C - Applications and Reviews, 42(5), 744–767. CrossRef
Xing, B., & Gao, W. J. (2014). Innovative computational intelligence: A rough guide to 134 clever algorithms. Intelligent Systems Reference Library (Vol. 62). Berlin: Springer. MATH
Yancey, J. M. (1990). Ten rules for reading clinical research reports. The American Journal of Surgery, 159(6), 533–539. CrossRef
Yao, X., Liu, Y., & Li, G. (1999). Evolutionary programming made faster. IEEE Transactions on Evolutionary Computation, 3(2), 82–102. CrossRef
Yuen, S. Y., & Zhang, X. (2015). On composing an algorithm portfolio. Memetic Computing, 7, 203–214. CrossRef
Zelinka, I. (2015). A survey on evolutionary algorithms dynamics and its complexity—Mutual relations, past, present and future. Swarm and Evolutionary Computation, 25, 2–14. CrossRef
Zhang, Y. D., Wang, S. H., & Ji, G. L. (2015). A comprehensive survey on particle swarm optimization algorithm and its applications. Mathematical Problems in Engineering. Article ID: 931256.
- Searching for structural bias in particle swarm optimization and differential evolution algorithms
Adam P. Piotrowski
Jaroslaw J. Napiorkowski
- Springer US
Neuer Inhalt/© ITandMEDIA