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


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