Title: Convergence analysis of cuckoo search algorithm based on martingale theory

Authors: Lijun Sun; Xiaodong Liu; Tianfei Chen; Ming Yan; Shaokui Ma

Addresses: Key Laboratory of Grain Information Processing and Control, Ministry of Education, Henan University of Technology, Zhengzhou 450001, China; Henan Key Laboratory of Grain Photoelectric Detection and Control, Henan University of Technology, Zhengzhou 450001, China; School of Information Science and Engineering, Henan University of Technology, Zhengzhou 450001, China ' Key Laboratory of Grain Information Processing and Control, Ministry of Education, Henan University of Technology, Zhengzhou 450001, China; Henan Key Laboratory of Grain Photoelectric Detection and Control, Henan University of Technology, Zhengzhou 450001, China; School of Electrical Engineering, Henan University of Technology, Zhengzhou 450001, China ' Key Laboratory of Grain Information Processing and Control, Ministry of Education, Henan University of Technology, Zhengzhou 450001, China; Henan Key Laboratory of Grain Photoelectric Detection and Control, Henan University of Technology, Zhengzhou 450001, China; School of Information Science and Engineering, Henan University of Technology, Zhengzhou 450001, China ' Key Laboratory of Grain Information Processing and Control, Ministry of Education, Henan University of Technology, Zhengzhou 450001, China; Henan Key Laboratory of Grain Photoelectric Detection and Control, Henan University of Technology, Zhengzhou 450001, China; School of Electrical Engineering, Henan University of Technology, China ' Key Laboratory of Grain Information Processing and Control, Ministry of Education, Henan University of Technology, Zhengzhou 450001, China; Henan Key Laboratory of Grain Photoelectric Detection and Control, Henan University of Technology, Zhengzhou 450001, China; School of Electrical Engineering, Henan University of Technology, China

Abstract: Cuckoo search (CS) algorithm is an emerging kind of biologically inspired algorithm that has been successfully applied in several areas. However, its mathematical theory has not yet been fully established up to now, and the theoretical analysis of convergence is relatively inadequate. In this article, the martingale theory is introduced for the first time to prove the convergence of CS, which replaces the ergodic analysis of the Markov chain. First of all, according to the basic principles of CS, we establish the mathematical model of the Markov chain and group state sequence, and its Markov properties are analysed, and then the optimal group state set is obtained. After that, the supermartingale of the cuckoo evolution sequence with an optimal fitness value is derived. In the end, based on the convergence theorem of supermartingale, it is demonstrated that the CS algorithm ensures global convergence.

Keywords: cuckoo search; CS; Markov chain; convergence; martingale theory.

DOI: 10.1504/IJMIC.2021.123431

International Journal of Modelling, Identification and Control, 2021 Vol.39 No.2, pp.128 - 137

Received: 19 Feb 2021
Accepted: 07 Jun 2021
Published online: 20 Jun 2022 *

Full-text access for editors Full-text access for subscribers Purchase this article Comment on this article