Backtracking search optimization algorithm for numerical optimization problems. (English) Zbl 1288.65092

Summary: This paper introduces the backtracking search optimization algorithm (BSA), a new evolutionary algorithm (EA) for solving real-valued numerical optimization problems. EAs are popular stochastic search algorithms that are widely used to solve non-linear, non-differentiable and complex numerical optimization problems. Current research aims at mitigating the effects of problems that are frequently encountered in EAs, such as excessive sensitivity to control parameters, premature convergence and slow computation. In this vein, development of BSA was motivated by studies that attempt to develop simpler and more effective search algorithms. Unlike many search algorithms, BSA has a single control parameter. Moreover, BSA’s problem-solving performance is not over sensitive to the initial value of this parameter. BSA has a simple structure that is effective, fast and capable of solving multimodal problems and that enables it to easily adapt to different numerical optimization problems. BSA’s strategy for generating a trial population includes two new crossover and mutation operators. BSA’s strategies for generating trial populations and controlling the amplitude of the search-direction matrix and search-space boundaries give it very powerful exploration and exploitation capabilities. In particular, BSA possesses a memory in which it stores a population from a randomly chosen previous generation for use in generating the search-direction matrix. Thus, BSA’s memory allows it to take advantage of experiences gained from previous generations when it generates a trial preparation. This paper uses the Wilcoxon signed-rank test to statistically compare BSA’s effectiveness in solving numerical optimization problems with the performances of six widely used EA algorithms: PSO, CMAES, ABC, JDE, CLPSO and SADE. The comparison, which uses 75 boundary-constrained benchmark problems and three constrained real-world benchmark problems, shows that in general, BSA can solve the benchmark problems more successfully than the comparison algorithms.


65K10 Numerical optimization and variational techniques
90C59 Approximation methods and heuristics in mathematical programming


ABC; levmar; JADE; CEC 05; GSA
Full Text: DOI


[1] Deb, K.; Pratap, A.; Agarwal, S., A fast and elitist multiobjective genetic algorithm: nsga-II, IEEE Trans. Evol. Comput., 6, 182-197, (2002)
[2] Ishibuch, H.; Yoshida, T.; Murata, T., Balance between genetic search and local search in memetic algorithms for multiobjective permutation flowshop scheduling, IEEE Trans. Evol. Comput., 7, 204-223, (2003)
[3] Kishore, J. K.; Patnaik, L. M.; Mani, V., Application of genetic programming for multicategory pattern classification, IEEE Trans. Evol. Comput., 4, 242-258, (2000)
[4] de Carvalho, M. G.; Laender, A. H.F.; Goncalves, M. A., A genetic programming approach to record deduplication, IEEE Trans. Knowl. Data. Eng., 24, 399-412, (2012)
[5] Qin, A. K.; Huang, V. L.; Suganthan, P. N., Differential evolution algorithm with strategy adaptation for global numerical optimization, IEEE Trans. Evol. Comput., 13, 398-417, (2009)
[6] Brest, J.; Greiner, S.; Boskovic, B.; Mernik, M.; Zumer, V., Self-adapting control parameters in differential evolution: a comparative study on numerical benchmark problems, IEEE Trans. Evol. Comput., 10, 646-657, (2006)
[7] Tasgetiren, M. F.; Suganthan, P. N.; Pan, Q. K., An ensemble of discrete differential evolution algorithms for solving the generalized traveling salesman problem, Appl. Math. Comput., 215, 3356-3368, (2010) · Zbl 1183.65071
[8] Liang, J. J.; Qin, A. K.; Suganthan, P. N.; Baskar, S., Comprehensive learning particle swarm optimizer for global optimization of multimodal functions, IEEE Trans. Evol. Comput., 10, 281-295, (2006)
[9] Kanzow, C.; Yamashita, N.; Fukushima, T., Levenberg-Marquardt methods with strong local convergence properties for solving nonlinear equations with convex constraints, J. Comput. Appl. Math., 172, 375-397, (2004) · Zbl 1064.65037
[10] Zhang, J.; Sanderson, A. C., JADE: adaptive differential evolution with optional external archive, IEEE Trans. Evol. Comput., 13, 945-958, (2009)
[11] Neri, F.; Tirronen, V., Recent advances in differential evolution: a survey and experimental analysis, Artif. Intell. Rev., 33, 61-106, (2010)
[12] Karaboga, D.; Akay, B., A comparative study of artificial bee colony algorithm, Appl. Math. Comput., 214, 108-132, (2009) · Zbl 1169.65053
[13] Karaboga, D.; Basturk, B., A powerful and efficient algorithm for numerical function optimization: artificial bee colony (ABC) algorithm, J. Global. Optim., 39, 459-471, (2007) · Zbl 1149.90186
[14] He, Q.; Wang, L., An effective co-evolutionary particle swarm optimization for constrained engineering design problems, Eng. Appl. Artif. Intell., 20, 89-99, (2007)
[15] Salman, A. A.; Ahmad, I.; Omran, M. G.H., Frequency assignment problem in satellite communications using differential evolution, Comput. Oper. Res., 37, 2152-2163, (2010) · Zbl 1231.90212
[16] De Falco, I.; Della Cioppa, A.; Maisto, D., Differential evolution as a viable tool for satellite image registration, Appl. Softw. Comput., 8, 1453-1462, (2008)
[17] Najkar, N.; Razzazi, F.; Sameti, H., A novel approach to HMM-based speech recognition systems using particle swarm optimization, Math. Comput. Model., 52, 1910-1920, (2010) · Zbl 1207.68303
[18] Wang, S.; Wang, S.; Ma, J. J., An improved co-evolutionary particle swarm optimization for wireless sensor networks with dynamic deployment, Sensors, 7, 354-370, (2007)
[19] Sousa, T.; Silva, A.; Neves, A., Particle swarm based data mining algorithms for classification tasks, Parallel Comput., 30, 767-783, (2004)
[20] Das, S.; Konar, A., A swarm intelligence approach to the synthesis of two-dimensional IIR filters, Eng. Appl. Artif. Intell., 20, 1086-1096, (2007)
[21] Mohandes, M. A., Modeling global solar radiation using particle swarm optimization (PSO), Sol. Energy, 86, 3137-3145, (2012)
[22] Qin, H., Aberration correction of a single aspheric Lens with particle swarm algorithm, Opt. Commun., 285, 2996-3000, (2012)
[23] Ourique, C. O.; Biscaia, E. C.; Pinto, J. C., The use of particle swarm optimization for dynamical analysis in chemical processes, Comput. Chem. Eng., 26, 1783-1793, (2002)
[24] Bonilla-Petriciolet, A.; Segovia-Hernandez, J. G., Particle swarm optimization for phase stability and equilibrium calculations in reactive systems, Comput. Aid. Ch., 26, 635-640, (2009)
[25] Liu, B.; Wang, L.; Liu, Y.; Qian, B.; Jin, Y. H., An effective hybrid particle swarm optimization for batch scheduling of polypropylene processes, Comput. Aid. Ch., 34, 518-528, (2010)
[26] Zhang, J.; Xie, L.; Wang, S., Particle swarm for the dynamic optimization of biochemical processes, Comput. Aid. Ch., 21, 497-502, (2006)
[27] Dorigo, M.; Maniezzo, V.; Colorni, A., Ant system: optimization by a colony of cooperating agents, IEEE Trans. Syst. Man. Cybern. B, 26, 29-41, (1996)
[28] Simon, D., Biogeography-based optimization, IEEE Trans. Evol. Comput., 12, 702-713, (2008)
[29] X.S. Yang, S. Deb, Cuckoo search via levy flights World Congress on Nature and Biologically Inspired Computing’Nabic-2009, Coimbatore, India, vol. 4, 2009, pp. 210-214.
[30] P. Civicioglu, E. Besdok, A conceptual comparison of the cuckoo-search, particle swarm optimization, differential evolution and artificial bee colony algorithms, Artif. Intell. Rev., in press. doi: http://dx.doi.org/10.1007/s10462-011-9276-0.
[31] Rashedi, E.; Nezamabadi-pour, H.; Saryazdi, S., GSA: a gravitational search algorithm, Inf. Sci., 13, 2232-2248, (2009) · Zbl 1177.90378
[32] Xiang, T.; Liao, X.; Wong, K., An improved particle swarm optimization algorithm combined with piecewise linear chaotic map, Appl. Math. Comput., 190, 1637-1645, (2007) · Zbl 1122.65363
[33] Clerc, M.; Kennedy, J., The particle swarm - explosion, stability, and convergence in a multidimensional complex space, IEEE Trans. Evol. Comput., 6, 58-73, (2002)
[34] Storn, R.; Price, K., Differential evolution - a simple and efficient heuristic for global optimization over continuous spaces, J. Global Optim., 11, 341-359, (1997) · Zbl 0888.90135
[35] Qin, A. K.; Suganthan, P. N., Self-adaptive differential evolution algorithm for numerical optimization, IEEE Trans. Evol. Comput., 1-3, 1785-1791, (2005)
[36] Geem, Z. W.; Kim, J. H.; Loganathan, G. V., A new heuristic optimization algorithm: harmony search, Simulation, 76, 60-68, (2001)
[37] Igel, C.; Hansen, N.; Roth, S., Covariance matrix adaptation for multi-objective optimization, Evol. Comput., 15, 1-28, (2007)
[38] Thangaraj, R.; Pant, M.; Abraham, A.; Bouvry, P., Particle swarm optimization: hybridization perspectives and experimental illustrations, Appl. Math. Comput., 217, 5208-5226, (2011) · Zbl 1209.65064
[39] Tsoulos, I. G.; Stavrakoudis, A., Enhancing PSO methods for global optimization, Appl. Math. Comput., 216, 2988-3001, (2010) · Zbl 1193.65103
[40] Thangaraj, R.; Pant, M.; Abraham, A., Particle swarm optimization: hybridization perspectives and experimental illustrations, Appl. Math. Comput, 217, 5208-5226, (2011) · Zbl 1209.65064
[41] D. Bratton, J. Kennedy, Defining a standard for particle swarm optimization, in: IEEE Swarm Intelligence Symposium, Honolulu, 2007, 1-4244-0708-7.
[42] M.G.H. Omran, M. Clerc, 2011, <http://www.particleswarm.info/>, accessed 15 January, 2013.
[43] P.N. Suganthan, N. Hansen, J.J. Liang, K. Deb, Y.P. Chen, A. Auger, S. Tiwari, Problem definitions and evaluation criteria for the CEC 2005 special session on real-parameter optimization, Technical Report, 2005, pp. 1-50.
[44] S. Das, P.N. Suganthan, Problem definitions and evaluation criteria for CEC 2011 competition on testing evolutionary algorithms on real world optimization problems, Technical Report, 2012, 1-42.
[45] P. Civicioglu, 2013, <http://www.pinarcivicioglu.com/bsa.html>, accessed 15 January, 2013.
[46] Derrac, J.; Garcia, S.; Molina, D.; Herrera, F., A practical tutorial on the use of nonparametric statistical tests as a methodology for comparing evolutionary and swarm intelligence algorithms, Swarm Evol. Comput., 1, 3-18, (2011)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.