International Journal of Computer Applications (0975
–
8887) Volume 90
–
No.3, March 2014
7
Genetic Cuckoo Optimization Algorithm (GCOA)
M. Z. Rashad
Faculty of Computer & Information Mansoura University, Egypt
A.E. Keshk
Faculty of Computer & Information Menofia University, Egypt
M. A. ElDosuky
Faculty of Computer & Information Mansoura University, Egypt
M. M. Kamal
CS Department Mansoura University, Egypt
ABSTRACT
In this paper, Optimization is considered as the main impact of insight problem and heuristic methods. A proposed method is represented by using two optimization algorithms; cuckoo optimization; is heuristic method and Genetic algorithm; is metaheuristic method in order to increase the optimization level and speed of calculation as possible. The proposed methodology and technique still a subject for improvements and enhancements for increasing its speeding up more and more. The proposed method is applicable for many industrial fields, agricultural fields and other provided that having optimization problem; just reconfigure problem parameters and have good opportunity to optimize well the problem.
General Terms
Cuckoo, Optimization Algorithms, Genetic Algorithm.
Keywords
Cuckoo, Heuristics Methods, Meta Heuristics Methods, L´evy Flights, Optimization Algorithms, Genetic Algorithm, insight problems.
1.
INTRODUCTION
Heuristics can do best calculations on the cases of largesize problems finding the most acceptable performance at suitable costs. As heuristics can be suitable for a specific problem type, based on experience or latest knowledge to perform good heuristics on an exact problem as it need all the possible solutions of the problem and determine the best of them. The information collected by an algorithm can be used to determine which solution should be tested next or how the next individual can be produced all of this makes heuristic a part of an optimization algorithm. There is no proof on that people like physicists and mathematicians expect so nobody knows if it will always give the best answer to the problem. Heuristics are usually problem class dependent. A classic example of heuristic of TSP Problem is nearest neighbor heuristic. The nearest cities are visited to lastly to obtain good solutions of total TSP's circuit. They are classified as general purpose algorithms which can solve almost any optimization problem. They are considered as a guiding strategy in designing underlying heuristics by means upper level general methodologies. A metaheuristic can be considered as a heuristic, but a more powerful one, since a mechanism to avoid be stuck in a local minimum is present in any good metaheuristic as it is able to service heuristics methods by guiding them over the search space in order to extract its best capabilities to achieve better solutions. Metaheuristics use the information collected during the search to direct the search process (like gbest in PSO) and generate new solutions by combining one or more good solutions. They are embedded with operators to scape a local goals, like mutation in GA (or the notion of topology in PSO). They are more generic and can be applicable to variety of problems with little modifications. Such as Genetic Algorithm which can be used to solve a variety of problems by just modifying the encoding schema. The natureinspired metaheuristic algorithms make it used in a widespread range of optimization problems, including NPhard problems such as the travelling salesman problem [1], [2].as Biological systems evolved from natural selection over millions of years. Most of the optimization problems are nonlinear, relating many different design variables under complex constraints. This will results in multimodal response landscape. And so, local search algorithms are not suitable, only global algorithms should be used so as to obtain optimal solutions. Modern metaheuristic algorithms have been developed with an aim to carry out global search; typical examples are genetic algorithms (Glodberg 1989). There are two critical characteristics of the modern metaheuristics: intensification and diversification [2]. Intensification searches around the current best solutions and select the best solutions, but diversification makes sure the algorithm can explore the search space efficiently. Metaheuristics works with support to heuristic. Very good solutions can be obtained combining good heuristics with classical metaheuristics for many problems. Also genetic algorithms Concept is easy to understand, building blocks can be used in hybrid applications. It supports multiobjective optimization. It is also good
for “noisy”
environment. It performs well with the time, Can easily run in parallel and the fitness function can be changed from iteration to another iteration, which allows incorporating new data in the model if it becomes available. Although it is not too fast, it cover large search space, Capable of quickly finding promising regions of the search space but may take much time to reach the optimal solution. So hybrid algorithms with Good heuristics for combinatorial problems usually emphasize combining information from good parents (crossover). We used genetic algorithm with support to cuckoo search algorithm that is inspired by the reproduction strategy of cuckoos. Because of this method is a simple, efficient and optimal random search path, and effectively applied to practical optimization problems [3].
1.1
Cuckoo Breeding Behavior
Cuckoos are interesting birds because of their aggressive reproduction strategy. Some species of cuckoos lay their eggs
in shared nests, though they may kill others’ eggs to increase
the hatching probability of their own eggs. Quite a number of species engage the obligate brood parasitism by laying their eggs in the nests of other host birds (often other species). There are three basic types of brood parasitism; intraspecific brood parasitism, cooperative breeding, and nest takeover. Some host birds can engage direct conflict with the cuckoos. If a host bird discovers the eggs are not their own, it will
International Journal of Computer Applications (0975
–
8887) Volume 90
–
No.3, March 2014
8 either throw them away or simply leaves its nest and builds a new nest in another place. Also, the timing of egglaying of some species is also amazing. Parasitic cuckoos often choose a nest where the host bird just laid its own eggs. In general, the cuckoo eggs hatch slightly earlier than their host eggs. Once the first cuckoo chick is hatched, it will take action to evict the host eggs by blindly thrusting the eggs out of the
nest, which increases the cuckoo chick’s share of
food provided by its host bird. Studies also show that a cuckoo chick can also mimic the call of host chicks to gain access to more feeding opportunity.
1.2
Genetic Algorithm
Genetic Algorithms are a popular strategy to optimize nonlinear systems with a large number of variables. The search is guided to improvement using the 'survival of the fittest principle'. This is achieved by extracting the most desirable features from a generation of solutions and combining them to form the next generation. The quality of each solution is evaluated and the best individuals are selected for the reproduction process. Performing this process many times through a number of generations will result in optimal or near optimal solutions. The main difference between genetic algorithms and other metaheuristic approaches such as virtual annealing and tabu search is that they deal with a group of solutions rather than a single solution. Operators such as selection, crossover and mutation are used to explore the neighborhood and generate a new generation [4].It is used in many applications such that, Optimization: numerical and combinatorial optimization problems, e.g. traveling salesman, routing, graph coloring and partitioning ,Robotics: trajectory planning, Machine learning: designing neural networks, classification and prediction, e.g. prediction of weather or protein structure, Signal processing: filter design, Design: semiconductor layout, aircraft design, communication networks, Automatic programming: evolve computer programs for specific tasks, design cellular automata and sorting networks, Economics: development of bidding strategies, emergence of economics markets, Immune systems: model somatic mutations, Ecology: model symbiosis, resource flow, Population genetics: gene will be available to recombination under any condition.
2.
RELATED WORKS
Hongqing et. al. presented a novel cuckoo search optimization algorithm base on Gauss distribution (GCS). And then apply the GCS algorithm to solve standard test functions and engineering design optimization problems, the optimal solutions obtained by GCS are far better than the best solutions obtained by CS [5]. K. Najmy et. al. proposed a modified cuckoo search (MCS) algorithm combined with the Roulette wheel selection operator and the inertia weight controlling the search ability towards synthesizing symmetric linear array geometry with minimum side lobe level (SLL) and/or nulls control [6]. Humar K has presented a Modified Cuckoo Optimization Algorithm (MCOA). This applied to two constrained continuous optimization problems. The results indicate that the MCOA is a powerful optimization technique that may yield better solutions to engineering problems [7]. Yongquan Zhou et. al. introduced Cuckoo search based on complexvalued encoding; the algorithm improves the search capabilities of the global optimum. Also a number of standard optimization problems and PID controller parameter tuning are solved using this concept and acceptable results are obtained [8]. A. Kaveh,T. Bakhshpoori and M. Ashoory proposed an integrated optimization procedure with the objective of minimizing the selfweight of real size structures is simply performed in the form of parallel computing [9]. Hongqing Zheng et. al. proposed a hybrid GeneticCuckoo Search (GCS) algorithm for optimization the ALP with runway. Devising is a method for tackling the Aircraft Landing Problem (ALP) in order to optimize the usage of existing runways at airports. The results showed that the proposed GCS algorithm can determine the runway allocation, sequence and landing time for arriving aircraft for the three test cases by minimizing total delays under the separation constraints in comparison with the outcomes yielded by previous studies [10].
3.
BASICS OF USED ALGORITHMS 3.1
L´evy Flights
In nature, animals search for food in a random manner. As the searching path of an animal is a random walks because the next move is based on the current location and the transition probability to the next location. Which direction it chooses depends covertly on a probability which can be modeled mathematically. For example, various studies have shown that the flight behavior of many animals and insects has
demonstrated the typical characteristics of L´evy ﬂights. A
recent study by Reynolds and Frye shows that fruit flies or Drosophila melanogaster; explore their landscape using a series of straight flight paths punctuated by a sudden 90o turn, leading to a L´evyflightstyle intermittent scalefree search pattern. Studies on human behavior such as the Ju hoansi hunter gatherer searching patterns also show the typical
feature of L´evy ﬂights.
Even light can be related to L´evy
ﬂights.
Subsequently, such behavior has been applied to optimization and optimal search, and initial results show its promising capability [1], [11].
4.
CUCKOO SEARCH
Cuckoo search is based on three basic rules: [1]
Each cuckoo lays one egg at a time, and dumps it in a randomly chosen nest. [2]
The best nests with high quality of eggs will carry over to the next generations. [3]
The number of available host nests is fixed, and a host can discover an alien egg with a probability pa
∈
[0,1]. In this case, the host bird can either throw the egg away or abandon the nest so as to build a completely new nest in a new location. For this work, the simplest approach has been chosen where each nest has only a single egg. Based the basic steps of the Cuckoo Search: When generating new solutions x (t+1)
for, say, a cuckoo i,a Le´vy ﬂight is performed
x (t+1) i =x (t) i + α
*
Le´vy(λ)
,[1]
Where
α>0 is the step size which should be related to the
rules of the problem of interests. In most cases, use
α =1.
The above equation is basically the stochastic equation for random walk. The random walk via Le´vy flight is more efficient in exploring the search space as its step length is much longer in the long run. The Le´vy flight basically provides a random walk while the random step length is
International Journal of Computer Applications (0975
–
8887) Volume 90
–
No.3, March 2014
9 drawn from a Le´vy distribution which has an infinite variance with an infinite mean. Le´vy
∼
u = t − λ, (1 <λ≤3),
[1] Some of the new solutions should be generated by Le´vy walk around the best solution obtained so far, this will speed up the local search. However, a substantial fraction of the new solutions should be generated by far field randomization and whose locations should be far enough from the current best solution, this will make sure the system will not be trapped in a local optimum.
5.
THE PROPOSED HYBRID METHOD 5.1
Genetic Algorithm Atomics:
Due to the description of genetic algorithm, fixed refined steps are listed below. These steps reformat the steps based on certain situation and principles of a simple problem to well clarify the GA steps which will be power Cuckoo algorithm to increase its optimization and functionality in efficient manner. 1
Initialize population. Population size is chosen (110 individuals/parameter optimized for most applications. Parameters to be optimized are encoded. (Binary, Base 10). Binary genes could be translated into parameters.
=382
10
−
1
−
+
It is needed to understand the system that will be optimized to determine the suitable parameter range. The initial population can be generated by randomizing the genes for each chromosome of the initial population. 2
Evaluate population.
The ﬁtness function is someh
ow based on the genes of the chromosome and should reflect how good a given set of
parameters is. Evaluation of the ﬁtness is the
computationally intensive of a GA optimization, as chromosome holds the information that uniquely describes an individual. And each chromosome can be evaluated separate from the others. The evaluation of the
chromosomes reduces down to a ﬁtness value for each
individual which will be used in the next step. For every problem, there is something you want to maximize or minimize. The standard convention is to maximize a function with a GA evaluates
the ﬁtness of each individual in the population. The ﬁtness will be used
to bias the next generation towards better genes. For an
empirical density functional, the ﬁtness might be a
weighted RMS deviation from experimental values.
=
−
(
−
)
2
“–” used because it is always wanted to maximize the ﬁtness.
3
Select parents for reproduction.
The parents must be selected based on their ﬁtness
. The
individuals with a higher ﬁtness must have a higher
probability of having children. There are several methods for selection like Roulette Wheel Selection, Rank Selection, and Rank Selection. 4
Perform crossover. Using the chromosomes of the parents, we create the chromosome of the child. With a crossover probability perform crossover or copy parents. 5
Perform mutation. With a mutation probability mutate children at each position in chromosome. 6
Accept new generation. 7
Evaluate the new population.
5.2
The Proposed Genetic Cuckoo Algorithm (GCOA)
The proposed algorithm is considered as genetic derived algorithm powered by fitness function, specification of population member and new population operation specified by srcinal cuckoo optimization algorithm. The power of heuristic comes to the proposed method via using GA that increases the proposed opportunity to find the space interval of optimal solution.
The proposed strategy can be well described as steps; see Fig 2, as follow: 1
The initialization of a population size is performed randomly. 2
Start the genetic algorithm 3
The initial values of the fitness is set to “

” as we want to
maximize the profit.
Fig 1: Flow Chart of Original Genetic Algorithm
Create Initial Population Evaluate the fitness of each individual Select parents based on fitness Create new population Start
End
International Journal of Computer Applications (0975
–
8887) Volume 90
–
No.3, March 2014
10 4
We then use the variables of the cuckoo algorithm as the components of the chromosome in the genetic algorithm which we obtained to apply. 5
Initialize a random chromosome center, number of eggs, radius and radiuses which would be used as chromosome components. 6
The fitness function has been calculated for each individual from this equation:
= 10
∗
+
(
2
−
10
∗
cos
2
) +2
Where
n
: population size.
a)
Get the best chromosome of for the next generation. b)
Set the number of generations equal to zeros. c)
Sort the fitness of each chromosome and get the best chromosome to be copied to the next generation d)
Apply the crossover e)
Make clusters and Determine the best cluster f)
Update the chromosome and copy the best chromosome to the next generation The algorithm can be used in many different applications such as Oil exploration, Land Reclamation, Gas exploration and others. Based on algorithm analysis, the proposed algorithm have the same level of order of growth in two most common states; best case and worst case like the srcinal cuckoo optimization algorithm. The chromosome representation is redefined to be suitable for GA structure, also, in turn the population would be contains chromosome of the redefined structure. The proposed algorithm is based and powered by the same fitness function defined by the srcinal cuckoo algorithm.
6.
IMPLEMENTATION AND EXPERIMENTS
We have done our experiments on windows 7, processor core i7 and RAM 6 GB to obtain high accuracy and performance. The development environment that is used was MATLAB to process the stated srcinal cuckoo algorithm and the proposed algorithm using the same fitness function for each individual/ chromosome:
= 10
∗
+((
2
−
10
∗
cos
2
)+ 2)
To evaluate the best individual/chromosome that intended to be taken for the next generation space. The initial number of population size is set to be only 50 individuals/chromosomes. Each member represents a cuckoo instance which can produce solution contains from 2 to 4 eggs as max. Conceptually, cuckoos will not do more than 100 iterations to find out the best habitat. Global goal is minimization of the cost of the problem at earlier iteration. The cost of the problem is a performance metric represents the benefits to use the solution with lowest cost. In opposite of cost there is an urgent another metric which is the iteration obtains the optimal solution. Finally the optimal solution space, level or interval which is encloses the optimal solution block.
Fig 2: Flow Chart of Genetic Cuckoo Optimization Algorithm (GCOA)
Initialize population size Initialize the initial fitness
Iteration<max &max fitness>accuracy
Calculate center of chromosome Calculate number of eggs Calculate radius Calculate radiuses Determine position of best chromosome to be copied to next generation Apply crossover Make clusters and determine the best clusters
Update the chromosome and copy the best one to the new generation
End
Start
International Journal of Computer Applications (0975
–
8887) Volume 90
–
No.3, March 2014
11
Fig 3: All Iterations of Original Cuckoo Optimization using the sample population Fig 4: All Iterations of GCOA using the sample population
In Figure 3, the srcinal algorithm of cuckoo optimization shows that it finds out the optimal solution in later large number of iterations while reach the optimal solution space, also, in late iterations than the GCOA, see figure4. GCOA is still have improvements more than current but at the moments it's more greater than srcinal one in reaching the optimal solution space, just take few counted iterations doesn't exceeded the first ten iteration in order to locate the optimal solution search space. In turn, a comparison can be made using three factor; listed in early words, between the srcinal and proposed algorithms as follow in table 1:
Table 1: Cuckoo vs. GCOA
Comparison Factors Cuckoo GCOA
Find Optimal Solution
Higher Lower
Reach Optimal Search Space
Lower Higher
Iteration Counted to do
Lower Higher Next Figures; Figure 5, 6, show the prove of state of how each algorithm is really iterate to reach optimal cost compared to final state represented by figure 3 and 4 respectively.
7.
CONCLUSIONS AND FUTURE WORKS
Based on the experimental results and research basis, we can conclude that GCOA is improved version of the srcinal cuckoo optimization algorithm. Because GCOA speeds up the opportunity to reach the optimal search space rapidly rather than Cuckoo optimization.
Fig 5: The Cost =0 at Iteration =32 for Original Cuckoo Optimization approach from 100 iterations Fig 6a: Visiting of Optimal Search Space at early iterations; iteration = 4 using GCOA approach
The proposed algorithm is applicable in many real life problems such as mining, exploration and others. Also, we as authors declare any one can improve and enhance any phase of the proposed approach.
8.
REFERENCES
[1]
XinShe Yang, Suash Deb
,” Cuckoo Search via L´evy Flights”, World Congress on Nature & Biologically
Inspired Computing (NaBIC 2009). [2]
Blum C. and Roli A., Metaheuristics in combinatorial optimization: Overview and concepturalcomparision, ACM Comput. Surv., 35, 268 308 (2003). [3]
X. S. Yang and S. Deb, “Engineering optimization by cuckoo search,” International Journal of Mathematical
Modelling and Numerical Optimization, vol. 4, pp. 330
–
343, 2010. [4]
E. Hopper and B. C. H. Turton,” An Empirical
Investigation of Metaheuristic and Heuristic Algorithms
for a 2D Packing Problem”, European Journal of
Operational Research 128/1, 3457, 2000. [5]
HongqingZHENG ,Yongquan ZHOU ,” A Novel Cuckoo
Search Optimization Algorithm Base on Gauss
Distribution”, Journal of Computational
Information Systems 8: 10 (2012) 4193
–
4200. [6]
KhairulNajmy, Mohd. Fareq, “Nature
inspired Cuckoo Search Algorithm for Side Lobe Suppression in a
Symmetric Linear Antenna Array”,
RADIOENGINEERING, VOL. 21, NO. 3, SEPTEMBER 2012.