Pigeon Inspired Optimization (PIO) Algorithm: A Novel method motivated from the behavior of Pigeons for Optimal Solution

1. Introduction

    Pigeon-inspired Optimization (PIO) algorithm is a novel swarm intelligence optimization algorithm, which was firstly invented by Duan in 2014. Population-based swarm intelligence algorithms have been widely accepted and successfully applied to solve many optimization problems. All the bio-inspired optimization algorithms are trying to simulate the natural ecosystem mechanisms, which have greatly improved the feasibility of the modern optimization techniques, and offered practical solutions for those complicated combinatorial optimization problems [1]. Path planning is the problem of designing the path a vehicle is supposed to follow in such a way that a certain objective is maximized and a goal is reached. Pigeons are the most popular bird in the world, and they were once used to send the message by Egyptians, which also occurred in many military affairs. Homing pigeons can easily find their homes by using three homing tools: magnetic field, sun and landmarks. In this paper, we presented a new bio-inspired swarm intelligence optimizer Pigeon Inspired Optimization (PIO) [2]. In this newly invented algorithm, map and compass operator model is presented based on magnetic field and sun, while landmark operator model is presented based on landmarks. We also applied this newly proposed PIO algorithm for solving air robot path planning problem. Investigation of pigeons’ ability to detect different magnetic fields demonstrates that the pigeons’ impressive homing skills almost depend on tiny magnetic particles in their beaks. Specifically, there are iron crystals in pigeons’ beaks, which can give birds a nose for north. Studies show that the species seem to have a system in which signals from magnetite particles are carried from the nose to the brain by the trigeminal nerve (Mora et al., 2004) [4]. Evidence that the sun is also involved in pigeon navigation has been interpreted, either partly or entirely, in terms of the pigeon’s ability to distinguish differences in altitude between the Sun at the home base and at the point of release (Whiten, 1972). Recent researches on pigeon behavior also show that the pigeon can follow some landmarks, such as main roads, railways and rivers rather than head for their destination directly [5].

2. Inspiration of PIO Algorithm

      In biology, a population may divide into some subgroup. In the face of natural enemies, the subgroups will cooperate to resist. Nevertheless, they also compete with each other in the interests of food, mating, territory, and so on. Cooperation and competition make the population survive and evolve better [6]. To simulate these natural behaviors, UAVs work together to complete the search task via information interaction, in the mean time UAVs compete with each other to search the specific vital cells. We propose a CPIO algorithm based on the cooperation-competition mechanism as the search algorithm for MUCS, as shown in Figure 1. In which, one subgroup pigeons is abstracted as one UAV. The cooperation-competition relationship between pigeons reflects the cooperative relationship between UAVs MUCS based on CPIO is composed of three parts: CPIO, UAVs, and environment model [7].

3. Pigeon Inspired Optimization (PIO) Algorithm

    Because homing pigeons have special ability that they can find their way home themselves, people take advantages of them in many fields, for example, news communication, sports communication, marine communication and military communication. The messenger pigeon is a variety of domestic pigeon derived from the rock pigeon, selectively bred for its ability to find its way home over extremely long distances [8]. The wild rock pigeon has an innate homing ability, meaning that it will generally return to its nest, using magneto reception. This made it relatively easy to breed from the birds that repeatedly found their way home over long distances. Flights as long as 1,800 km have been recorded by birds in competitive pigeon racing. Their average flying speed over moderate 965 km distances is around 97 km/h and speeds of up to 160 km/h have been observed in top racers for short distances. In fact, there are lots of researches studying pigeons’ special ability. They claimed that pigeons use a combination of the sun, the earth’s magnetic field and landmarks to find their way around [9]. Pigeons can sense the earth magnetic field and they take the sun position as a compass to form a map in their memories which guides them to the right direction. Meantime, pigeons also have the ability to recognize the landmarks they have met before so that they can obtain the best path to their destination. PIO algorithm completely reproduces these processes. While in landmark section, pigeons update their positions using the best center position of each iteration. Through these two parts of updates, pigeons will soon find the global best position of the history.

    Although the superiority of PIO algorithm outperforms other intelligent optimization algorithms, like PSO and DE, it still suffers from the common problem of premature convergence. The first step controls the balance between convergence velocity and global search ability; by modifying the dynamic process of the variation for map and compass factor to find the balance point. The second step is constructed based on the conditional crossover operation to optimize the global optima. Multiple UAVs mission assignment problem is employed to examine the effectiveness of this method, and the experiment results show the superior performance of our modified PIO algorithm [10].

      By analyzing the flight data gathered by miniature GPS during multiple pigeon flocking flights, a hierarchical network was discovered in the in-flight leader-follower relations of pigeons. In a pigeon flock, except the general leader whose motion will not be influenced by the other pigeon, each pigeon has its rank in the hierarchy. During the flight, pigeons will attempt to follow the ones in upper ranks and lead the ones in lower ranks. The leadership hierarchy is hypothesized to be the result of feedback between learning and competence. Inspired by the hierarchical learning in pigeon flocks, modified MPIO is proposed [11]. In the basic PIO, all the pigeons will correct their positions X_i based on the sum and magnetic field described by the current global best position X_g, and the landmark image preview message specified by the weighted average of positions X_center. In the modified MPIO, pigeons are split into two roles: One is the general leader and the other is the ordinary follower. By the non-dominated sorting in Pareto sorting scheme, all the pigeons will be divided into different sets: first frontier S₁, second frontier S_2, and so on. The crowded comparison operator will continue to sort the pigeons in each set. Which are supposed to fly based on the map and compass operator and the landmark operator, and updates their states by the current global best position X_g and the weighted average of positions X_center, where P₁ is the percentage of general leaders in the pigeon flock [12].

3.1. Steps for PIO Algorithm

• Initialize Parameters
• Evaluate the fitness of Pigeons
• Select the operator to be conducted
• Update the Pigeons
• Pigeons have been generated
• Termination

3.1.1. Initialize Parameters

     Initialize parameters of PIO algorithm, such as the number of pigeons, the solution dimension space, the maxim number of iteration and the initial annealing temperature and initial random set of pigeons [13].

3.1.2. Evaluate the fitness of Pigeons

     The rotation, translation and scaling of the given sketch are initialized in the Subsequently, the transformed sketch is fitted within the potential field according to compute the matching index, namely, the fitness value of the pigeon [14].

3.1.3. Select the operator to be conducted

     Compare with the given probability, if a random value between 0 and 1 is smaller, then perform the map and compass operator [15]. Otherwise, conduct the landmark operator.

3.1.4. Update the Pigeons

     If the map and compass operator is selected, the velocity and position of each pigeon is updated by respectively. Else, utilize to update the individual [16].

3.1.5. Pigeons have been generated

     The pigeon’s position, Xg_best is the global best position which has the minimum fitness function value in the pigeon’s new position.

3.1.6. Termination

     Finally, parameters in guidance compensation are optimized to achieve higher landing accuracy with less height error integration. After four layers’ design, normal acceleration as well as its oscillation and pitch rate response are checked to accord with the criteria [17].

3.2. Flow Chart of PIO Algorithm

4. Numerical Expression of PIO Algorithm

    Steps Involved in Solving the Given Problem Using PIO Algorithm [18],

5. Applications of PIO Algorithm

• Binocular Camera Systems
• Brushless Direct Current (BLDC) motor[19]
• Multidimensional Knapsack Problem
• Critical Peak Pricing
• Hose Drogue System (HDS)[20]
• Unmanned Aerial vehicle (UAV)

6. Advantages of PIO Algorithm

• Nature has greatly inspired and motivated us in finding solutions to various optimization problems.
• Comparative results indicate that out method is much better than other methods [21].
• The most important requirements since path planning have to occur quickly due to fast vehicle dynamics.
• PIO algorithm is feasible and reliable to generate the constrained gliding trajectory for hypersonic gliding vehicles.
• Comparative simulations are conducted to verify the feasibility of the multilayer design strategy and the superiority of CMPIO [22].
• The information of both cameras is completely used, and the poses of them can be determined accurately at the same time [23].
• Performance of this technique is evaluated through simulations in term of reduction in electricity cost, Peak to Average Ratio (PAR) by scheduling smart appliances.

Reference

[1] Li, C. and Duan, H. (2014). Target detection approach for UAVs via improved Pigeon-inspired Optimization and Edge Potential Function. Aerospace Science and Technology, 39, pp.352-360.

[2] Deng, Y. and Duan, H. (2016). Control parameter design for automatic carrier landing system via pigeon-inspired optimization. Nonlinear Dynamics, 85(1), pp.97-106.

[3] Qiu, H. and Duan, H. (2015). Multi-objective pigeon-inspired optimization for brushless direct current motor parameter design. Science China Technological Sciences, 58(11), pp.1915-1923.

[4] Zhao, J. and Zhou, R. (2015). Pigeon-inspired optimization applied to constrained gliding trajectories. Nonlinear Dynamics, 82(4), pp.1781-1795.

[5] Sun, X., Qi, N. and Yao, W. (2015). Boolean Networks-Based Auction Algorithm for Task Assignment of Multiple UAVs. Mathematical Problems in Engineering, 2015, pp.1-8.

[6] Li, P. and Li, S. (2008). Quantum-inspired evolutionary algorithm for continuous space optimization based on Bloch coordinates of qubits. Neurocomputing, 72(1-3), pp.581-591.

[7] Lei, X., Ding, Y. and Wu, F. (2016). Detecting protein complexes from DPINs by density based clustering with Pigeon-Inspired Optimization Algorithm. Science China Information Sciences, 59(7).

[8] Salem, M. and Khelfi, M. (2014). Predator and Prey Modified Biogeography Based Optimization Approach (PMBBO) in Tuning a PID Controller for Nonlinear Systems. International Journal of Intelligent Systems and Applications, 6(11), pp.12-20.

[9] Xin, L. and Xian, N. (2017). Biological object recognition approach using space variant resolution and pigeon-inspired optimization for UAV. Science China Technological Sciences, 60(10), pp.1577-1584.

[10] Xue, Q. and Duan, H. (2017). Robust attitude control for reusable launch vehicles based on fractional calculus and pigeon-inspired optimization. IEEE/CAA Journal of Automatica Sinica, 4(1), pp.89-97.

[11] Pei, J., Su, Y. and Zhang, D. (2016). Fuzzy energy management strategy for parallel HEV based on pigeon-inspired optimization algorithm. Science China Technological Sciences, 60(3), pp.425-433.

[12] Yang, Z., Duan, H., Fan, Y. and Deng, Y. (2018). Automatic Carrier Landing System multilayer parameter design based on Cauchy Mutation Pigeon-Inspired Optimization. Aerospace Science and Technology, 79, pp.518-530.

[13] de Sa Ferreira, R., Barroso, L., Rochinha Lino, P., Carvalho, M. and Valenzuela, P. (2013). Time-of-Use Tariff Design Under Uncertainty in Price-Elasticities of Electricity Demand: A Stochastic Optimization Approach. IEEE Transactions on Smart Grid, 4(4), pp.2285-2295.

[14] Deng, Y., Zhu, W. and Duan, H. (2016). Hybrid membrane computing and pigeon-inspired optimization algorithm for brushless direct current motor parameter design. Science China Technological Sciences, 59(9), pp.1435-1441.

[15] Vijay, D. (2017). Efficient Energy Management System for Smart Grid Using Bacterial Foraging Optimization Technique. International Journal Of Engineering And Computer Science.

[16] YANG, Z., DUAN, H. and FAN, Y. (2018). Unmanned aerial vehicle formation controller design via the behavior mechanism in wild geese based on Levy flight pigeon-inspired optimization. SCIENTIA SINICA Technologica, 48(2), pp.161-169.

[17] Sabba, S. and Chikhi, S. (2014). A discrete binary version of bat algorithm for multidimensional knapsack problem. International Journal of Bio-Inspired Computation, 6(2), p.140.

[18] Naz, M., Iqbal, Z., Javaid, N., Khan, Z., Abdul, W., Almogren, A. and Alamri, A. (2018). Efficient Power Scheduling in Smart Homes Using Hybrid Grey Wolf Differential Evolution Optimization Technique with Real Time and Critical Peak Pricing Schemes. Energies, 11(2), p.384.

[19] Qiu, H. and Duan, H. (2018). A multi-objective pigeon-inspired optimization approach to UAV distributed flocking among obstacles. Information Sciences.

[20] Sun, Y., Duan, H. and Xian, N. (2018). Fractional-order controllers optimized via heterogeneous comprehensive learning pigeon-inspired optimization for autonomous aerial refueling hose–drogue system. Aerospace Science and Technology, 81, pp.1-13.

[21] Hu, C., Xia, Y. and Zhang, J. (2018). Adaptive Operator Quantum-Behaved Pigeon-Inspired Optimization Algorithm with Application to UAV Path Planning. Algorithms, 12(1), p.3.

[22] Sushnigdha, G. and Joshi, A. (2018). Re-entry trajectory optimization using pigeon inspired optimization based control profiles. Advances in Space Research, 62(11), pp.3170-3186.

[23] Dey, K. and Saha, A. (1985). Design Theory of a Multimode Rectangular Waveguide Taper with Truncated Gaussian Mode Conversion Distribution Function. IETE Journal of Research, 31(3), pp.93-96.