-Optimization problems are used in different areas of our life. Very often the functions that are optimized are so complex that classic methods can not deal with them. The solution for it are heuristic techniques that do not guarantee the correct solution in a finite time. In this work, the classic version of Cuckoo Search Algorithm and proposed modifications that allow to increase the precision of obtained solutions are described. The proposal was presented and tested on nine different test functions, and the obtained solutions were discussed in terms of advantages and disadvantages.
More and more often, contemporary problems are described by mathematical equations, which makes it possible to minimize variables in such a way that the cost of production is as low as possible and the highest quality. The large space of solutions, the number of variables or even the landscape of functions can be a big challenge for computers. For this type of tasks, besides the classic methods of finding the best values of the functions are heuristic algorithms. These techniques are inspired by a certain action of physics or nature.
Mathematical models describing the action of nature are
created all the time, which is evident in numerous scientific
works. In [
In the case of practical applications, such techniques have
been used primarily in decision-making systems [
Heuristic approach has also found use in location-based
social networks [
Copyright held by the author(s).
Important features describing different lungs diseases on the
X-RAY images were detected by heuristic [
The optimization problem is understood as searching for a point whose function value reaches the global extreme, more precisely the minimum or maximum. The choice of maximization or minimization is insignificant because in the case of a function having a maximum, it is enough to negate the function. The same applies to the opposite case. To define the problem formally, let us introduce some signs. For a continuous function f (x) : Rn ! R, the point x = (x1; x2; : : : ; xn) will be a global extreme if the following condition is satisfied min f (x) x or max f (x): x (1)
Optimization functions are usually n-dimensional, for which the extreme is hard to locate. Moreover, classic and numerical methods mostly will not be able to do this. They are called artificial landscape because in three dimensions they resemble familiar shapes from nature or physics. A set of such a functions is presented in Table I, where are defined the most known and representing the basic shapes like bowl-shaped, plate-shaped, valley-shaped, steep ridges and others.
To find the best solution, it is necessary to use heuristic algorithm. It is a technique inspired by the nature, which does not guarantee an accurate solution in a finite time (only approximate).
Cuckoo Search Algorithm (CSA) was presented in [
The above-mentioned assumptions cause that these birds has a specific environment. Each cuckoo moves in each iteration in search of a better nest for its offspring. The flight is carried out in accordance with the Levy’s equations (often called Levy’s flight), which is continuous probability distribution defined as L(xi; ; c) = r c 2 exp (x c
3 ) 2 2(x ) ; where is location coefficient and c is scale parameter. Using Levy’s equation, we can move birds on each spatial coordinates as xt+1 = xit + i
L(xit; ; c); where is the length of Levy’s flight, t is the current iteration.
After the move of cuckoo, the egg is subjected to a certain test depending on whether it will remain in the nest. In case the host notices that he has not his egg, he can throw it away. The probability of discovery is pa, and it’s modeled as H(xit+1) = ( < pa drop the egg pa leave the egg ; (4) (2) (3) (0; : : : ; 0) (0; : : : ; 0) (0; : : : ; 0) (0; : : : ; 0) (0; : : : ; 0) (0; : : : ; 0) (0; : : : ; 0) (0; : : : ; 0)
Global minimum 0 0 0 0 0 0 0 0 ( 2:903534; : : : ; 2:903534) 39:16599n where is a random value in range h0; 1i. In most cases, pa = 0:5 what gives the equal likelihood of staying and throwing the egg out of the nest.
Proposition is based on modification host decision to prevent the remove eggs that represents good solutions for a given problem. Moreover, every move that cuckoo does is corrected by using a local search method.
1) Gradient method: One of the classic local search technique is gradient descent. It is based on the analysis direction of search space by the calculating the negative gradient of function f . Let assume, that the algorithm starts at position x = (x0; : : : ; xn 1). Then, the negative gradient for each spatial coordinates is calculated as rfxi = @f (x0; : : : ; xn 1) ; @xi what means the direction of the fastest descent. Then, the value of xi is recalculated as
xit = xit + ( rfxit ); where is the length of step and t is the current iteration for these method. After T iterations, if function value in point xT is better then before local search, it is replaced.
2) Proposed modification: A cuckoo moving in search of a nest goes to one point and then the host’s decision follows. Let us assume that the egg-laying cuckoo looks for such a place in the nest to minimize the discovery of a new egg. In practice, it can be realized through the local search like method of the smallest gradient described in Algorithm 1.
The second modification is remodeling the host’s decision. In the original version depends on the randomness (5) (6) Algorithm 1 Gradient Descent of parameter . This type solution allows to remove wellmatched egg in the nest. It is possible to delete the best solution in the whole population, and it leads to a jump in the convergence. Removing the worse solutions by finding the opportunity to the location a better one is justified and therefore remodeling the decision condition is so important – the best solutions should remain, and only the worse ones should be removed. Moreover, the decision must depend on the optimization function. In addition, it would be good if the decision depended also on the quality of the current point with respect to the best in whole population. An example of such a model is presented by the following equation
8> f (xtbest) < pa drop the egg H (xit+1) = >< f (xtcurrent) ; (7) f (xtbest) pa
leave the egg > > : f (xtcurrent) t where xbest is the best solution in current iteration in whole population.
Algorithm 2 Modified Cuckoo Search Algorithm 1: Start, 2: Define p , c, , number of individuals N and number of iteration T , 3: Define test function f ( ), 4: Generate N cuckoos at random, 5: t:=0, 6: while t T do 7: Move each cuckoo using Eq. (3), 8: Find the best position in nest using Algorithm 1, 9: Hosts decision is made by Eq. (7), 10: t + +, 11: end while 12: Return the best cuckoo in population, 13: Stop.
For all test function are presented in Table I. Both versions (classic and modified) were implemented in Mathematica 9.
Calculation were made using two sets of basic parameters which are (the size of population, the number of iterations) and were set as (50; 50) and (100; 100). In addition, the algorithm parameter setting was as follows pa = 0:7, c = 0:4, = 0:3 and the step size for gradient descent was 15.
All presented results are the average value from 100 tests calculated as f (fx0; : : : ; x99g) = The obtained averaged solutions are presented in II. From these table, it is clearly to see that for each function, the accuracy is at least slightly better. In the case of function with many local extremes like Rastrigin or Schwefel, the solution is better more then 10% which is a good result considering the possibility of getting stuck. Especially when the algorithm uses local search and this can increase accuracy, but only by finding a better point in a given part of the function.
Not only the accuracy was measured, but also average trajectory in each iteration defined as where xideal is the exactly solution for a given function and j xbest is the best point in j-th test, and jj jj is an Euclidean metric defined as the distance between two given points p and q in n-dimensions jjp v u n qjj = tuX(pi i=0 qi)2: (10) (8) (9) (11) And the last measurement coefficient is rate of convergence in each iteration from the first to the t 1 calculated as jf (xk+1) jf (xk)
f (xideal)j ; f (xideal)j where k is the number of the given iteration. All of these values were measured during tests for a population of 100 individuals and 100 iterations. For each iteration, data was saved, then averaged and coefficients calculated in accordance with the above formulas. The illustration of the obtained results are shown in Fig. 1 (for classic version) and in Fig. 2 (for modified version). At first glance, both sets of charts look similar. However, the values on the axes are much smaller in the case of the algorithm with proposed modifications.
In almost all cases, the curves have been slightly smoothed with the introduction of modifications. One of the most interesting cases is the Schwafel function, for which the graph of the average value of the fitness function slowed down to zero. The reason is primarily the landscape (that is, many local minimums) and the use of local search technique which deepened the falling into this minimum. Hence, the function graph is more bulged compared to the original. In other functions, there can be seen improvement.
In this paper, two modification were presented to improve the performance of Cuckoo Search Algorithm. The first one is the introduction of a local search as finding the best position in the nest to reduce the probability of being detected by the host. The second modification is the remodeling of the host’s decision regarding the egg. This is important because in the original algorithm, it was possible to remove the best solutions in a given iteration. And now, the decision depends on the quality of the position relative to the best individual in whole population.
Both versions of CSA were tested in terms of accuracy, quality of adaptation, trajectory, convergence of solution in each iteration. Comparison of results indicates the advantage of modification because the accuracy is more than 10% higher than the original. Moreover, in most cases, convergence was faster except the cases of functions with many local minima. The reason is faster move to the minimum through local search. An important element for future work is to design the exit mechanism from the minimum and to analyze other local search techniques.