logo

SCIENCE CHINA Information Sciences, Volume 62, Issue 7: 070207(2019) https://doi.org/10.1007/s11432-018-9753-5

Theoretical analysis of the convergence property of a basic pigeon-inspired optimizer in a continuous search space

More info
  • ReceivedAug 20, 2018
  • AcceptedNov 30, 2018
  • PublishedJun 6, 2019

Abstract

The pigeon-inspired optimization (PIO) algorithm is a newly presented swarm intelligence optimization algorithm inspired by the homing behavior of pigeons. AlthoughPIO has demonstrated effectiveness and superiority in numerous fields, particularly in practicalengineering optimization, there have been few results concerning the theoretical foundations of PIO. This paper conductsconvergence analysis of basic PIO in a continuous search space in two aspects. First, we analyze the convergence of each pigeon'sexpected position using a difference equation and prove that the average position of each pigeon inthe swarm will converge to the same value. To further study the stochastic globalconvergence property of the pigeon swarm, we apply the martingale theory to investigatethe basic PIO swarm sequence, and achieve a sufficient condition to guarantee global convergenceof the basic PIO. Our theoretical analysis shows that this convergence depends upon the accumulation of the minimum probability with which the pigeon swarm jumps to the global-optimal region at each iteration. The mathematical methods proposed in this study, particularly the martingale technique, also provide a new effective approach for the theoretical analysis of bio-inspired algorithms in continuous optimization.


Acknowledgment

This work was supported by Natural Science Foundation of China-Guangdong Joint Fund (Grant No. U1501254), National Natural Science Foundation of China (Grant Nos. 61772225, 61876207), Guangdong Natural Science Funds for Distinguished Young Scholar (Grant No. 2014A030306050), the Ministry of Education - China Mobile Research Funds (Grant No. MCM20160206), Guangdong High-level Personnel of Special Support Program (Grant No. 2014TQ01X664), International Cooperation Project of Guangzhou (Grant No. 201807010047), and Science and Technology Program of Guangzhou (Grant Nos. 201804010276, 201707010227, 201707010228).


References

[1] Bonyadi M R, Michalewicz Z. Particle Swarm Optimization for Single Objective Continuous Space Problems: A Review.. Evolary Computation, 2017, 25: 1-54 CrossRef PubMed Google Scholar

[2] Dorigo M, Blum C. Ant colony optimization theory: A survey. Theor Comput Sci, 2005, 344: 243-278 CrossRef Google Scholar

[3] Shi Y H. An Optimization Algorithm Based on Brainstorming Process. Int J Swarm Intelligence Res, 2011, 2: 35-62 CrossRef Google Scholar

[4] Duan H B, Qiao P X. Pigeon-inspired optimization: a new swarm intelligence optimizer for air robot path planning. Int Jnl Intel Comp Cyber, 2014, 7: 24-37 CrossRef Google Scholar

[5] Zhang B, Duan H B. Three-Dimensional Path Planning for Uninhabited Combat Aerial Vehicle Based on Predator-Prey Pigeon-Inspired Optimization in Dynamic Environment.. IEEE/ACM Trans Comput Biol Bioinf, 2017, 14: 97-107 CrossRef PubMed Google Scholar

[6] Xu X B, Deng Y M. UAV Power Component-DC Brushless Motor Design With Merging Adjacent-Disturbances and Integrated-Dispatching Pigeon-Inspired Optimization. IEEE Trans Magn, 2018, 54: 1-7 CrossRef ADS Google Scholar

[7] Duan H B, Li S T, Shi Y H. Predator-Prey Brain Storm Optimization for DC Brushless Motor. IEEE Trans Magn, 2013, 49: 5336-5340 CrossRef ADS Google Scholar

[8] Li T, Zhou C J, Wang B. A Hybrid Algorithm Based on Artificial Bee Colony and Pigeon Inspired Optimization for 3D Protein Structure Prediction. j bionanosci, 2018, 12: 100-108 CrossRef Google Scholar

[9] Sushnigdha G, Joshi A. Trajectory design of re-entry vehicles using combined pigeon inspired optimization and orthogonal collocation method. IFAC-PapersOnLine, 2018, 51: 656--662. Google Scholar

[10] Xin L, Xian N. Biological object recognition approach using space variant resolution and pigeon-inspired optimization for UAV. Sci China Technol Sci, 2017, 60: 1577-1584 CrossRef Google Scholar

[11] Rajendran S, M. Sankareswaran U. A Novel Pigeon Inspired Optimization in Ovarian Cyst Detection. CMIR, 2016, 12: 43-49 CrossRef Google Scholar

[12] Lei X, Ding Y, Wu F X. Detecting protein complexes from DPINs by density based clustering with Pigeon-Inspired Optimization Algorithm. Sci China Inf Sci, 2016, 59: 070103 CrossRef Google Scholar

[13] Duan H B, Ye F. Progresses in pigeon-inspired optimization algorithms. J Beijing Univ Technol (Nat Sci Ed), 2017, 43: 1--7. Google Scholar

[14] Xu G, Yu G S. On convergence analysis of particle swarm optimization algorithm. J Comput Appl Math, 2018, 333: 65-73 CrossRef Google Scholar

[15] Liu Q F. Order-2 Stability Analysis of Particle Swarm Optimization.. Evolary Computation, 2015, 23: 187-216 CrossRef PubMed Google Scholar

[16] Bonyadi M R, Michalewicz Z. Analysis of Stability, Local Convergence, and Transformation Sensitivity of a Variant of the Particle Swarm Optimization Algorithm. IEEE Trans Evol Computat, 2016, 20: 370-385 CrossRef Google Scholar

[17] Nguyen H T, Wang T H. A Graduate Course in Probability and Statistics, Volume I, Essentials of Probability for Statistics. Beijing: Tsinghua University Press, 2008. Google Scholar

[18] Elaydi S N. An Introduction to Difference Equations. 3rd ed. New York: Springer, 2005. Google Scholar

[19] Rudolph G. Convergence properties of evolutionary algorithms. Dissertation for Ph.D. Degree. Hamburg: University of Hamburg, 1997. Google Scholar

[20] Rudolph G. Stochastic convergence. In: Handbook of Natural Computing. Berlin: Springer, 2010. Google Scholar

[21] Agapie A, Agapie M. Transition Functions for Evolutionary Algorithms on Continuous State-space. J Math Model Algor, 2007, 6: 297-315 CrossRef Google Scholar

[22] Agapie A, Agapie M, Zbaganu G. Evolutionary algorithms for continuous-space optimisation. Int J Syst Sci, 2013, 44: 502-512 CrossRef Google Scholar

[23] Agapie A, Agapie M, Rudolph G. Convergence of evolutionary algorithms on the n-dimensional continuous space.. IEEE Trans Cybern, 2013, 43: 1462-1472 CrossRef PubMed Google Scholar

[24] Beyer H G. The Theory of Evolution Strategies. New York: Springer, 2001. Google Scholar

  •   

    Algorithm 1 Basic pigeon-inspired optimization (PIO) algorithm

    3. Landmark operations $t=N{c_{1\max~}}+1$ to $N{c_{2\max~}}$ Rank all pigeon individuals according to their fitness values; ${N_p}(t)~=~{\mathop{\rm~ceil}\nolimits}~(~{\frac{{{N_p}(t~-~1)}}{2}}~)$;

    Keep ${N_p}(t)$ individuals with better fitness values and abandon the others; Calculate ${{\boldsymbol~X}_C}(t)$ and update ${{\boldsymbol~x}_k}(t)$, $k~=~1,~\ldots,~{N_p}$ according to Eqs. (4) and (5); Evaluate ${{\boldsymbol~x}_k}(t)$, $k~=~1,~\ldots,~{N_p}$ and update ${{\boldsymbol~P}_g}(t)$;

    4. Output ${{\boldsymbol~P}_g}(N{c_{2\max~}})$ is output as the global optimum.

    Require:${N_p}$: number of individuals in a pigeon swarm. $D$: dimension of the search space. $R$: the map and compass factor. $N{c_{1\max~}}$: maximum number of generations for which the map-and-compass operation is performed. $N{c_{2\max~}}$: maximum number of generations for which the landmark operation is performed.

    Output: ${{\boldsymbol~P}_g}$: the global best position. 1. Initialization

    Set initial values for $N{c_{1\max~}}$, $N{c_{2\max~}}$, ${N_p}$, $D$, and $R$.

    Set initial position ${{\boldsymbol~x}_k}$ and velocity ${{\boldsymbol~v}_k}$ for each pigeon, $k~=~1,~\ldots,~{N_p}$.2. Map and compass operations

    for $t=1$ to $N{c_{1\max~}}$

    for $k=1$ to ${N_p}$

    Calculate ${{\boldsymbol~v}_k}(t)$ and ${{\boldsymbol~x}_k}(t)$ according to Eqs. (1) and (2);

    end for

    Evaluate ${{\boldsymbol~x}_k}(t)$, $k~=~1,~\ldots~,~{N_p}$ and update ${{\boldsymbol~P}_g}(t)$;

    end for

Copyright 2019 Science China Press Co., Ltd. 《中国科学》杂志社有限责任公司 版权所有

京ICP备18024590号-1