Sequential quadratic programming enhanced backtracking search algorithm

doi:10.1007/s11704-016-5556-9

Front. Comput. Sci.

2018, Vol. 12

Issue (2) : 316-330 https://doi.org/10.1007/s11704-016-5556-9

RESEARCH ARTICLE

Sequential quadratic programming enhanced backtracking search algorithm

Wenting ZHAO¹, Lijin WANG^1,², Yilong YIN¹(

), Bingqing WANG¹, Yuchun TANG³

¹. School of Computer Science and Technology, Shandong University, Jinan 250101, China
². College of Computer and Information Science, Fujian Agriculture and Forestry University, Fuzhou 350002, China
³. Research Center for Sectional and Imaging Anatomy, Shandong University School of Medicine, Jinan 250012, China

Download: PDF(2190 KB)
Export: BibTeX | EndNote | Reference Manager | ProCite | RefWorks

Abstract

In this paper, we propose a new hybrid method called SQPBSA which combines backtracking search optimization algorithm (BSA) and sequential quadratic programming (SQP). BSA, as an exploration search engine, gives a good direction to the global optimal region, while SQP is used as a local search technique to exploit the optimal solution. The experiments are carried on two suits of 28 functions proposed in the CEC-2013 competitions to verify the performance of SQPBSA. The results indicate the proposed method is effective and competitive.

Keywords numerical optimization backtracking search algorithm sequential quadratic programming local search

Corresponding Author(s): Yilong YIN

Just Accepted Date: 12 October 2016 Online First Date: 08 December 2017 Issue Date: 23 March 2018

Cite this article:

Wenting ZHAO,Lijin WANG,Yilong YIN, et al. Sequential quadratic programming enhanced backtracking search algorithm[J]. Front. Comput. Sci., 2018, 12(2): 316-330.

URL:

https://academic.hep.com.cn/fcs/EN/10.1007/s11704-016-5556-9
https://academic.hep.com.cn/fcs/EN/Y2018/V12/I2/316

1	Holland J H. Adaptation in Natural and Artificial Systems: An Introductory Analysis with Applications to Biology, Control, and Artificial Intelligence. Cambridge, Massachusettes: The MIT press, 1992
2	Storn R, Price K. Differential evolution-a simple and efficient adaptive scheme for global optimization over continuous spaces. Technical Report TR-95-012. Berkeley, CA: International Computer Science Institue, 1995
3	Dorigo M, Maniezzo V, Colorni A. Ant system: optimization by a colony of cooperating agents. IEEE Transactions on Systems, Man, and Cybernetics, Part B: Cybernetics, 1996, 26(1): 29–41 https://doi.org/10.1109/3477.484436
4	Kennedy J, Eberhart R C. Particle swarm optimization. In: Proceedings of IEEE International Conference on Neural Networks. 1995, 1942–1948 https://doi.org/10.1109/ICNN.1995.488968
5	Eberhart R C, Kennedy J. A new optimizer using particle swarm theory. In: Proceedings of the 6th International Symposium on Micro Machine and Human Science. 1995, 39–43 https://doi.org/10.1109/MHS.1995.494215
6	Chen W N, Zhang J, Lin Y, Chen N, Zhan Z H, Chung H S H, Li Y, Shi Y H. Particle swarm optimization with an aging leader and challengers. IEEE Transactions on Evolutionary Computation, 2013, 17(2): 241–258 https://doi.org/10.1109/TEVC.2011.2173577
7	Yu W J, Shen M, Chen W N, Zhan Z H, Gong Y J, Lin Y, Liu O, Zhang J. Differential evolution with two-level parameter adaptation. IEEE Transactions on Cybernetics, 2014, 44(7): 1080–1099 https://doi.org/10.1109/TCYB.2013.2279211
8	Civicioglu P. Backtracking search optimization algorithm for numerical optimization problems. Applied Mathematics and Computation, 2013, 219(15): 8121–8144 https://doi.org/10.1016/j.amc.2013.02.017
9	Agarwal S K, Shah S, Kumar R. Classification of mental tasks from eeg data using backtracking search optimization based neural classifier. Neurocomputing, 2015, 166: 397–403 https://doi.org/10.1016/j.neucom.2015.03.041
10	Yang D D, Ma H G, Xu D H, Zhang B H. Fault measurement for siso system using the chaotic excitation. Journal of the Franklin Institute, 2015, 352(8): 3267–3284 https://doi.org/10.1016/j.jfranklin.2015.04.015
11	Zhang C J, Lin Q, Gao L, Li X Y. Backtracking search algorithm with three constraint handling methods for constrained optimization problems. Expert Systems with Applications, 2015, 42(21): 7831–7845 https://doi.org/10.1016/j.eswa.2015.05.050
12	Zhao W T, Wang L J, Yin Y L, Wang B Q, Wei Y, Yin Y S. An improved backtracking search algorithm for constrained optimization problems. In: Proceedings of the 7th International Conference on Knowledge Science, Engineering and Management. 2014, 222–233 https://doi.org/10.1007/978-3-319-12096-6_20
13	Mallick S, Kar R, Mandal D, Ghoshal S. CMOS analogue amplifier circuits optimisation using hybrid backtracking search algorithm with differential evolution. Journal of Experimental & Theoretical Artificial Intelligence, 2016, 28(4): 719–749 https://doi.org/10.1080/0952813X.2015.1042533
14	Wang L T, Zhong Y W, Yin Y L, Zhao W T, Wang B Q, Xu Y L. A hybrid backtracking search optimization algorithm with differential evolution. Mathematical Problems in Engineering, 2015 https://doi.org/10.1155/2015/769245
15	Ali A F. A memetic backtracking search optimization algorithm for economic dispatch problem. Egyptian Computer Science Journal, 2015, 39(2)
16	Qian C, Yu Y, Zhou Z H. Pareto ensemble pruning. In: Proceedings of the 29th AAAI Conference on Artificial Intelligence. 2015, 2935–2941
17	Attaviriyanupap P, Kita H, Tanaka E, Hasegawa J. A hybrid EP and SQP for dynamic economic dispatch with nonsmooth fuel cost function. IEEE Transactions on Power Systems, 2002, 17(2): 411–416 https://doi.org/10.1109/TPWRS.2002.1007911
18	Cai J J, Li Q, Li L X, Peng H P, Yang Y X. A hybrid CPSO–SQP method for economic dispatch considering the valve-point effects. Energy Conversion and Management, 2012, 53(1): 175–181 https://doi.org/10.1016/j.enconman.2011.08.023
19	Basu M. Hybridization of bee colony optimization and sequential quadratic programming for dynamic economic dispatch. International Journal of Electrical Power & Energy Systems, 2013, 44(1): 591–596 https://doi.org/10.1016/j.ijepes.2012.08.026
20	Morshed M J, Asgharpour A. Hybrid imperialist competitivesequential quadratic programming (HIC-SQP) algorithm for solving economic load dispatch with incorporating stochastic wind power: a comparative study on heuristic optimization techniques. Energy Conversion and Management, 2014, 84: 30–40 https://doi.org/10.1016/j.enconman.2014.04.006
21	Zhan Z H, Zhang J, Li Y, Shi Y H. Orthogonal learning particle swarm optimization. IEEE Transactions on Evolutionary Computation, 2011, 15(6): 832–847 https://doi.org/10.1109/TEVC.2010.2052054
22	Blum C, Puchinger J, Raidl G R, Roli A. Hybrid metaheuristics in combinatorial optimization: a survey. Applied Soft Computing, 2011, 11(6): 4135–4151 https://doi.org/10.1016/j.asoc.2011.02.032
23	Lozano M, García-Martínez C. Hybrid metaheuristics with evolutionary algorithms specializing in intensification and diversification: Overview and progress report. Computers & Operations Research, 2010, 37(3): 481–497 https://doi.org/10.1016/j.cor.2009.02.010
24	Zhang J, Zhan Z H, Lin Y, Chen N, Gong Y J, Zhong J H, Chung H, Li Y, Shi Y H. Evolutionary computation meets machine learning: a survey. Computational Intelligence Magazine, IEEE, 2011, 6(4): 68–75 https://doi.org/10.1109/MCI.2011.942584
25	Nocedal J, Wright S. Sequential quadratic programming. In: Sun W Y,Yuan Y X, eds. Optimization Theory and Methods. Springer Optimization and Its Application, Vol 1. Springer Science & Business Media, 2006, 529–533
26	Wilson R B. A simplicial algorithm for concave programming. Dissertation for the Doctoral Degree. Cambridge, MA: Harvard University, 1963
27	Liang J J, Qu B Y, Suganthan P N, Hernández-Díaz A G. Problem definitions and evaluation criteria for the CEC 2013 special session on real-parameter optimization. Technical Report. 2013
28	Qian H, Hu Y Q, Yu Y. Derivative-free optimization of highdimensional non-convex functions by sequential random embeddings. In: Preceedings of the 25th International Joint Conference on Artificial Intelligence. 2016, 1946–1952
29	Karaboga D. An idea based on honey bee swarm for numerical optimization. Technical Report. 2005
30	Clerk M. Standard particle swarm optimisation. Technical Report. 2012
31	Hansen N, Ostermeier A. Completely derandomized self-adaptation in evolution strategies. Evolutionary Computation, 2001, 9(2): 159–195 https://doi.org/10.1162/106365601750190398
32	Igel C, Hansen N, Roth S. Covariance matrix adaptation for multiobjective optimization. Evolutionary Computation, 2007, 15(1): 1–28 https://doi.org/10.1162/evco.2007.15.1.1
33	Liang J J, Qin A K, Suganthan P N, Baskar S. Comprehensive learning particle swarm optimizer for global optimization of multimodal functions. IEEE Transactions on Evolutionary Computation, 2006, 10(3): 281–295 https://doi.org/10.1109/TEVC.2005.857610
34	Qin A K, Suganthan P N. Self-adaptive differential evolution algorithm for numerical optimization. In: Proceedings of IEEE Congress on Evolutionary Computation. 2005, 1785–1791 https://doi.org/10.1109/CEC.2005.1554904
35	Brest J, Greiner S, Bošković B, Mernik M, Zumer V. Self-adapting control parameters in differential evolution: a comparative study on numerical benchmark problems. IEEE Transactions on Evolutionary Computation, 2006, 10(6): 646–657 https://doi.org/10.1109/TEVC.2006.872133
36	Suganthan P N, Hansen N, Liang J J, Deb K, Chen Y P, Auger A, Tiwari S. Problem definitions and evaluation criteria for the CEC 2005 special session on real-parameter optimization. KanGAL Report. 2005
37	Gong W Y, Cai Z H. Differential evolution with ranking-based mutation operators. IEEE Transactions on Cybernetics, 2013, 43(6): 2066–2081 https://doi.org/10.1109/TCYB.2013.2239988
38	Loshchilov I. CMA-ES with restarts for solving CEC 2013 benchmark problems. In: Proceedings of IEEE Congress on Evolutionary Computation. 2013, 369–376 https://doi.org/10.1109/CEC.2013.6557593
39	Zambrano-Bigiarini M, Clerc M, Rojas R. Standard particle swarm optimisation 2011 at CEC-2013: a baseline for future PSO improvements. In: Proceedings of IEEE Congress on Evolutionary Computation. 2013, 2337–2344 https://doi.org/10.1109/CEC.2013.6557848
40	El-Abd M. Testing a particle swarm optimization and artificial bee colony hybrid algorithm on the CEC13 benchmarks. In: Proceedings of IEEE Congress on Evolutionary Computation. 2013, 2215–2220 https://doi.org/10.1109/CEC.2013.6557832
41	Dos Santos Coelho L, Ayala H V H. Population’s variance-based adaptive differential evolution for real parameter optimization. In: Proceedings of IEEE Congress on Evolutionary Computation. 2013, 1672–1677
42	Nepomuceno F V, Engelbrecht A P. A self-adaptive heterogeneous PSO for real-parameter optimization. In: Proceedings of IEEE Congress on Evolutionary Computation. 2013, 361–368 https://doi.org/10.1109/CEC.2013.6557592

[1]

Download

[1]	Yi CHU, Chuan LUO, Shaowei CAI, Haihang YOU. Empirical investigation of stochastic local search for maximum satisfiability[J]. Front. Comput. Sci., 2019, 13(1): 86-98.
[2]	Yiqiao CAI,Yonghong CHEN,Tian WANG,Hui TIAN. Improving differential evolution with a new selection method of parents for mutation[J]. Front. Comput. Sci., 2016, 10(2): 246-269.

Viewed

Full text

Abstract

Cited

Shared

Discussed