CPO: A Crow Particle Optimization Algorithm
- https://doi.org/10.2991/ijcis.2018.125905658How to use a DOI?
- Metaheuristic algorithm; Crow search algorithm; Particle swarm optimization; Function optimization; Hybridization algorithm
Particle swarm optimization (PSO) is the most well known of the swarm-based intelligence algorithms and is inspired by the social behavior of bird flocking. However, the PSO algorithm converges prematurely, which rapidly decreases the population diversity, especially when approaching local optima. Recently, a new metaheuristic algorithm called the crow search algorithm (CSA) was proposed. The CSA is similar to the PSO algorithm but is based on the intelligent behavior of crows. The main concept behind the CSA is that crows store excess food in hiding places and retrieve it when needed. The primary advantage of the CSA is that it is rather simple, having just two parameters: flight length and awareness probability. Thus, the CSA can be applied to optimization problems very easily. This paper proposes a hybridization algorithm based on the PSO algorithm and CSA, known as the crow particle optimization (CPO) algorithm. The two main operators are the exchange and local search operators. It also implements a local search operator to enhance the quality of the best solutions from the two systems. Simulation results demonstrated that the CPO algorithm exhibits a significantly higher performance in terms of both fitness value and computation time compared to other algorithms.
- © 2019 The Authors. Published by Atlantis Press SARL.
- Open Access
- This is an open access article distributed under the CC BY-NC 4.0 license (http://creativecommons.org/licenses/by-nc/4.0/).
In recent years, various metaheuristic algorithms  have been attracted growing interest in the optimization problems community. This kind of research is inspired by natural behavior, and it has yielded algorithms such as artificial bee colony (ABC) , ant colony optimization (ACO) , cuckoo search (CS) , differential evolution (DE) , firefly algorithm (FA) , gravitational searching algorithm (GSA) , and particle swarm optimization (PSO) . In addition, various applications have been proposed for such metaheuristics algorithms in areas such as in of bioinformatics , clustering , deep learning , DNA fragment assembly , flow-shopscheduling , feature selection , geographical information systems , image segmentation , job-shop scheduling , power system , traveling salesman , vector quantization , and the water reactor problem .
The PSO algorithm is the most popular nature-inspired swarm-based intelligence algorithm. However, this algorithm is prone to premature convergence, especially when approaching local optima that are difficult to escape . It is therefore important to maintain a sufficiently high particle diversity to avoid premature convergence. As such, several algorithms have been proposed to improve the exploration and exploitation of PSO, such as comprehensive learning PSO (CLPSO) , orthogonal learning PSO (OLPSO) , and diversity-enhanced PSO (DNSPSO) . The GSA has an effective searching strategy for solving optimization problems, which is superior to and faster than the PSO algorithm. The crow search algorithm (CSA) is a recently proposed swarm-based intelligence algorithm  based on the intelligent behavior of crows. The main concept behind the CSA is that crows store excess food in hiding places to retrieve later when required and will attempt to cheat other crows by traveling to other positions in the search space, based on the awareness probability and flight length parameters.
Thus, we herein propose a hybridization algorithm based on the CSA and PSO algorithm, which will be referred to as the crow particle optimization (CPO) algorithm. The CPO algorithm is expected to exhibit the advantages of the CSA search strategy and the fast convergence of the PSO algorithm. The two main mechanisms of the CPO system are hybrid operation and a local search, exchanging individuals selected from the CSA and PSO systems after a specific number of iterations. Moreover, the CSA performs local searching to enhance the solution quality. The CPO process is as follows: Initially, the CPO algorithm simultaneously executes the PSO and CSA systems. Subsequently, the CPO algorithm uses center PSO (CPSO)  to determine the center individual of crow and the particle. The CPO algorithm then enhances the solution quality using the crossover operator , and finally, some individuals are selected from the PSO and CSA systems for exchange if the specific number of iterations is met. In this study, selection methods such as the roulette-wheel approach were employed . Moreover, the performance of the proposed CPO algorithm was compared with those of the PSO, CSA, GSA, and PSGO algorithm using six well-known benchmark test functions. The results indicate that the CPO algorithm outperforms the others with regard to solution quality.
In this paper, the relevant background information is presented in Section 2, the proposed CPO algorithm is described in Section 3, the results of the algorithm performance tests are reported and discussed in Section 4, and the conclusions and future research outlook are given in Section 5.
2. BACKGROUND INFORMATION AND RELATED WORK
2.1. The CSA
Crows are among the most intelligent birds. Indeed, their behavior indicates a high level of intelligence only slightly below that of humans; for example, crows exhibit self-awareness in mirror tests and display tool-making abilities . In fact, each crow has its own hiding place for storing food and takes precautions to protect this location from other crows, who could potentially follow the first crow to steal the stored food. CSA, which was introduced by Askazadeh , is a newly developed stochastic swarm-based intelligence algorithm designed to solve function optimization problems. The concepts underlying CSA are as follows:
Crows live in flocks.
They can memorize hiding-place positions.
Crows will follow one another to steal food.
They protect their hiding spaces from attackers with a probability in the interval [0, 1].
In the CSA system, the individual aggregates are described as crows. There are two main parameters for crows: the flight length fl and the awareness probability AP, respectively. The value of fl corresponds to a local search (small value) or global search (large value), and the AP controls the crow intensity (small value) or diversity (large value). These crows are randomly generated at certain positions by the CSA. The fitness values are computed and the position of each crow in the current population is updated using Equation (1). The position of crows i in iteration t, which provides a potential solution for N crows, is defined as follows:where, is the potential position solution for crow i in dimension j, and d is the dimension number of the solution space.
The current solution for each crow is then updated according to one of two cases. In the first case, it is assumed that crow c does not know that crow i is in pursuit. In the second case, it is assumed that crow c knows that crow i is in pursuit. The updated position for each crow is computed using Equation (2):where denotes the position of crow i in dimension j of iteration t, and denotes the hiding place position of crow c in dimension j of iteration t. Furthermore, fl denotes the flight length of crow i in iteration t, AP denotes the awareness probability of crow c in iteration t, and randi and randp are random variables in the interval [0, 1].
The CSA algorithm is described in Figure 1.
|1.||Initialize all crow positions with randomization|
|2.||Initialize memories of all crows|
|3.||Obtain fitness values for all crows|
|4.||Obtain memories of all crows|
|5.||Update all crow positions according to Equation 2|
|6.||Repeat Steps 35 until termination criterion is reached|
|7.||Output the best solution|
Standard crow search algorithm (CSA).
2.2. Particle Swarm Optimization
The PSO algorithm, which was introduced by Kennedy and Eberhart [8, 31] is a stochastic swarm-based intelligence algorithm that is a widely known because of its efficient searching strategy. Similar to the genetic algorithm (GA), PSO is inspired by the collective behavior of schools of fish or bird flocks. In the PSO algorithm, the positions and velocities of N particles in the d-dimensional space offer randomly initialized solutions. The solution of particle i in iteration t is as given by Equation (3). The current solution of each particle is then updated with regard to the local and global optima, which are computed using Equations (4) and (5), respectively.where and denote the position and velocity, respectively, of the particle i in dimension j and ω is an inertia weight that influences the convergence speed. The local optimum and global optimum and , respectively, represent the current best position and the best position in the swarm among all particles over time period t, respectively. The constants c1 and c2 represent the cognitive and social parameters, respectively, and r1 and r2 are random variables in the interval [0, 1].
The PSO algorithm is detailed in Figure 2.
|1.||Initialize solution with randomization.|
|2.||Obtain fitness values for all particles|
|3.||Obtain personal best solution for each particle|
|4.||Obtain global best solution for all particles|
|5.||Update positions and velocities of all particles according to Equations 4 and 5|
|6.||Repeat Steps 2–5 until maximum iteration is reached|
|7.||Output best solution|
Standard PSO algorithm.
2.3. Center Particle Swarm Optimization
Liu et al.  proposed an improved PSO approach known as center particle swam optimization (CPSO). In this study, we employed the concepts to improve the PSO and CSA systems. The main concept behind CPSO is that a population of N particles is considered, and their positions represent potential solutions. After the position values are updated for N − 1 particles, a center particle cp is added to the population, as follows Equation (6):where is the position of the center particle in dimension j in iteration t + 1. The CPSO algorithm is detailed in Figure 3.
|1.||Initialize solution with a randomization|
|2.||Calculate center particle cp based on all particles to Equation (6)|
|3.||Obtain fitness values for all particles|
|4.||Obtain personal best solution for each particle|
|5.||Obtain global best solution for all particles|
|6.||Update positions and velocities of all particles according to Equations (4) and (5)|
|7.||Repeat Steps 2–6 until maximum iteration is reached|
|8.||Output best solution|
Center particle swarm optimization (CPSO) algorithm .
3. PROPOSED CPO ALGORITHM
We herein present our proposed CPO algorithm, which couples the PSO and CSA systems. More specifically, CPO involves simultaneously executing the PSO and CSA systems and guiding the solution toward the global optimum using the CPSO algorithm. Some individuals are selected from the PSO and CSA systems using selection approaches and are exchanged following the processing of a specific number of iterations. Finally, a local search operator is used to improve the solution quality.
3.1. Individual Velocity
During successive iterations, the solution space is searched for each particle and its solution is updated using Equation (4). Oscillations in the PSO algorithm are controlled by a time-varying maximum velocity Vmax. The velocity thresholds are given by the expressions presented in the literature , as shown in Equations (7) and (8):where the exponent h is a positive constant, α controls the bounds of the search space at each velocity, the xmin and xmax are the position thresholds, t is the iteration t, and tmax is the maximum iteration.
3.2. Hybrid Operator
A hybrid operator is called at specific iterations. Some individuals are selected from the CSA and PSO systems and exchanged using the selection approaches. In this study, random selection was employed along with the roulette-wheel approach  with probabilities depending on the fitness values. The roulette-wheel approach is expressed as Equation (9):where f iti is the fitness value of individual i in the population.
An example of the hybrid operator is shown in Figure 4. In the CSA system, the random number is 0.23 and is located in the region Cl, while the random number of the PSO algorithm is 0.30, located in the region P2. Thus, in the roulette-wheel operator, the particle number C1 and agent number P2 are selected for exchange between the two systems.
3.3. Local Search Operator
The local search operator proposed in this study is similar to the DE crossover operator . Denoting crow c as the best of individual crow, , and particle p as the best one of PSO particles, , the local search operator performs a recombination between the original best solution for the crow (particle) in each dimension as follows Equation (10):where xi,j represents the position of the i-th crow (particle) in dimension j.
An example of the local operator is shown in Figure 5. Iteration t, assuming the PSO solutions for each dimension are 2.3, 1.5, 0.5, 0.8, 5.5, and 1.7, the CSA solutions for each corresponding dimension are 3.7, 0.3, 1.6, 0.1, 3.7, and 4.8, respectively. According to Equation (10), the new best solution is 2.3, 0.3, 0.5, 0.1, 3.7, and 1.7, respectively.
3.4. Summary of CPO Algorithm
Figure 6 shows the procedure of the proposed CPO algorithm. In the initial step, each crow (particle) is generated at random. Upon implementation of the CPSO algorithm to determine a central crow or particle, the CPO algorithm simultaneously executes the CSA and PSO algorithm to update the solutions of the two systems. After a specific number of iterations and exchange of a crow and a particle, it becomes necessary to trigger the hybrid operator. Finally, the quality of the best solution is improved using the local search operator.
|1.||Initialize each agent with a randomized position and velocity in the CSA and PSO|
|2.||Obtain the center crow and particle according to Equation 6|
|3.||Execute CSA process according to Figure 1|
|4.||Execute PSO process according to Figure 2|
|5.||Rim the local operator to increase the best solutions among both systems|
|6.||If specific iteration is reached, implement hybrid operator|
|7.||If terminal criterion is not met, repeat Steps 2–6|
|8.||Best solution is found|
Proposed crow particle optimization (CPO) algorithm.
4. EXPERIMENT AND RESULTS
4.1. Environment Setting
Numerous simulations were conducted to evaluate the performance of the proposed CPO algorithm. All simulation results were obtained using a computer with an i7-6700 3.40-GHz Intel CPU and 8GB of main memory running on Microsoft Windows 7. All programming was implemented using Java language.
4.2. Benchmark Functions
The six benchmark test functions used in our experiments (namely the Sphere, Rosenbrocks, Ackley, Griewanks, Schwefel, and Rastrigin functions) are described in Table 1 . In this case, d is the function dimensions, which was set to 10 for the purpose of study. The optimal solution of each benchmark function is 0d.
|Test Function||Formula||Solution Space||Optimal Value|
4.3. Parameter Settings
The basic parameter settings are listed in Table 2. All experimental results were collected from 30 independent runs, each involving 2000 iterations.
|CSA||Number of crows||20|
|Flight length fl||1.5|
|Awareness probability AP||0.05|
|PSO||Number of particles||20|
|Inertia ω||0.9 to 0.4|
|CPO||Number of individuals||20|
CSA, crow search algorithm; PSO, particle swarm optimization; CPO, crow particle optimization.
Parameter settings for proposed algorithm.
4.4. Comparison of Selection Approaches
Two different selection strategies were compared to determine the optimal strategy for selection of the individuals from the CSA and PSO systems. More specifically, the roulette wheel and random selection methods were considered, and the exchange iterations and individuals were set to 20 and 5, respectively. The simulated best solutions and average best fitness values (labeled Best and Average, respectively), as well as the average computation times (S) tavg are summarized in Table 3. In terms of the best fitness value, the roulette-wheel operator outperformed the random selection operator for test functions f2, f3, f4, f5, and f6. Similarly, for the average fitness value, the roulette-wheel operator outperformed the random selection operator for functions f1, f2, f4, and f6. Both approaches had almost identical computation times. Overall, the roulette-wheel approach was superior to the random selection strategy in the context of this study.
Comparison of different selection operators of the crow particle optimization (CPO) algorithm for d = 10.
4.5. Comparison of CPO With Difference Variants
As mentioned in the previous subsection, the roulette-wheel operator was found to provide the best solutions, so this operator was selected for use in the remaining experiments. Several variants of the CPO algorithm were compared in the subsequent simulations, for which the number of iterations and individuals exchanged among the composite algorithms were varied, as detailed in Table 4. Variant 1 was used for the comparison of selection approaches reported in the previous subsection. In Variant 1, two individuals were exchanged between the two systems every 20 iterations, whereas for Variant 3, 10 individuals were exchanged between the two systems every 20 iterations. In the majority of cases, d was set to 10, the number of iterations was 2000, and the number of simulations was 30.
|Variants||Specific Iterations||Specific Individuals|
Parameters for six variants of proposed algorithm
The simulated best solutions and average best fitness values (labeled Best and Average, respectively), and the average computation times tavg are summarized in Table 5. In terms of best fitness, CPO Variant 4 outperformed all other variants for test functions f3, f4, and f6; Variant 2 outperformed the other variants for functions f2, and f5; and Variant 5 yielded the best solution for f1. The highest average fitness values for functions f1, f2, f5, and f6 were yielded by Variants 6, Variants 2, Variants 1, and Variants 5, respectively, while Variant 4 was the best performer for functions f3 and f4. In contrast, the computation times were comparable among all variants. We therefore concluded that Variant 4 yielded the average case of better solutions among the variants examined herein.
Comparison of different variants of the crow particle optimization (CPO) algorithm for d = 10.
To present the previous experimental results more clearly, the data from Table 5 are depicted visually Figure 7. The x-axis shows the different variants, and the y-axis shows the log values of the best and average fitness values for each test function. In addition, we divided the six functions into two groups due to f2 and f4 having different value ranges, with some fitness values larger than 1.
4.6. Comparison of the CPO With PSO, CSA, GSA, and PSGO Algorithm
As described in the previous subsection, Variant 4 of the CPO algorithm provided the best solutions. Therefore, CPO was employed using the parameters of Variant 4 for comparison with the CSA , PSO , GSA , and PSGO  algorithm for 2000 iterations of the six benchmark test functions. The settings employed for all CSA and PSO algorithms were as described for the CPO, as detailed in Table 2.
Table 6 gives the best solution and average best fitness values (labeled Best and Average, respectively), as well as the average computation time(s) tavg for each simulation. In terms of the best fitness value, the PSO algorithm provided the best fitness for functions f1 and f2, whereas the CPO algorithm outperformed the other algorithms for f3, f4, f5, and f6. For the average fitness values, the GSA provided the average best fitness for function f1, while the CPO algorithm outperformed the other algorithms for f2, f4, f5, and f6. Furthermore, the computational time for the CPO algorithm was only 50% that of for the GSA, and the computational times of CPO and PSGO were comparable.
PSO, particle swarm optimization; CSA, crow search algorithm; CPO, crow particle optimization; GSA, gravitational searching algorithm.
Comparison of CPO with CSA, PSO, GSA, and PSGO.
To present previous experimental result more clearly, the data from Table 6 depicted visually in Figure 8. The x-axis shows the different variants, and the y-axis shows the log values of the best and average fitness values for each test function. In addition, we divided the six functions into two groups due to f2 and f4 having different value ranges, with some fitness values are larger than 1.
4.7. Convergence Rates
Finally, the convergence rates of the CSA, PSO, GSA, PSGO, and CPO were investigated. For each benchmark function from f1 to f6, the convergence rates of the average best fitness values for 30 runs of 2000 iterations, are presented in Figure 9.
As indicated clearly by the obtained results, a relationship exists between the convergence speed and the best solution. Indeed, the GSA outperformed the other algorithms in terms of the convergence rate for f1 and f3, and the GSA is superior to the CPO algorithm for f1 and f3, but the convergence line for the CPO algorithm is still decreasing. The PSO algorithm exhibits the highest convergence speed for f4, f5, and f6. Comparing the results of the CPO algorithm and CSA, it is apparent that CPO is more effective for all test functions. Comparing the results of CPO and PSGO indicates that CPO can outperform PSGO. In summary, the proposed CPO algorithm can yield the best results with the lowest convergence speed. In contrast, the results for the PSO algorithm are unstable, as this algorithm can yield the best solution for one simulation but the worst solution when averaged over all simulations.
4.8. Scalability of CPO and GSA
As apparent from the results, there is a relationship between the convergence speed and best solution. The GSA outperformed the other algorithms in terms of convergence rate for f1 and f3. However, although the GSA can get a better solution than CPO in f1 and f3, the result is in convergence status, and the convergence line of CPO is still decreasing. Thus, in this section, to verify that CPO can provide better solutions than the GSA in large numbers of iterations, we present a comparison of the CPO algorithm with the GSA for scalability using 10,000 iterations. The convergence rates of the average best fitness values for 30 runs, each consisting of 10,000 iterations, are presented in Figure 10.
The GSA yields better solutions using fewer than 2000 iterations, but CPO provides better solutions in terms of convergence rate for f1 to f6 when compared with the GSA for more than 2000 iterations. In summary, the results confirm that the proposed CPO algorithm can yield the lowest convergence speed.
5. CONCLUSIONS AND FUTURE WORK
To improve the global search performance of the CSA, we proposed a CPO algorithm to solve function optimization problems. In this case, the CPO algorithm simultaneously executes the PSO and CSA systems, before using the CPSO algorithm to generate the center individual. Subsequently, in specific iterations, some individuals from the PSO and CSA systems are selected for exchange using the roulette-wheel method. Finally, the local search operator is fine-tuned to yield the best solutions, which include the best individuals among those of the CSA and PSO systems. This CPO approach exhibits significantly better performance than the existing algorithms in terms of the average fitness values and computation times for six benchmark test functions. Future studies will focus on our investigation into application of the CPO algorithm to nondeterministic polynomial hard combinatorial problems such as clustering issues and medical image processing, as well as diversity enhancement of the CPO system to avoid fast convergence.
This work was supported in part by the Ministry of Science and Technology, Taiwan, R.O.C., under grants MOST 107-2218-E-992 -303.
Cite this article
TY - JOUR AU - Ko-Wei Huang AU - Ze-Xue Wu PY - 2019 DA - 2019/02/06 TI - CPO: A Crow Particle Optimization Algorithm JO - International Journal of Computational Intelligence Systems SP - 426 EP - 435 VL - 12 IS - 1 SN - 1875-6883 UR - https://doi.org/10.2991/ijcis.2018.125905658 DO - https://doi.org/10.2991/ijcis.2018.125905658 ID - Huang2019 ER -