Genetic Cuckoo Optimization Algorithm (GCOA)

 Radiologie

 4 views
of 6
All materials on our website are shared by users. If you have any questions about copyright issues, please report us to resolve them. We are always happy to assist you.
Description
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
Share
Transcript
   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. El-Dosuky 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 meta-heuristic 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 large-size  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 meta-heuristic 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 meta-heuristic 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. Meta-heuristics use the information collected during the search to direct the search process (like g-best 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 nature-inspired meta-heuristic algorithms make it used in a widespread range of optimization problems, including NP-hard 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 meta-heuristic 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 meta-heuristics: 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. Meta-heuristics works with support to heuristic. Very good solutions can be obtained combining good heuristics with classical meta-heuristics for many  problems. Also genetic algorithms Concept is easy to understand,  building blocks can be used in hybrid applications. It supports multi-objective 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; intra-specific  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 egg-laying 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 non-linear 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 meta-heuristic 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 neighbor-hood 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 complex-valued 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 self-weight of real size structures is simply  performed in the form of parallel computing [9]. Hongqing Zheng et. al. proposed a hybrid Genetic-Cuckoo 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 flights. 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´evy-flight-style intermittent scale-free search  pattern. Studies on human behavior such as the Ju hoansi hunter gatherer searching patterns also show the typical feature of L´evy flights. Even light can be related to L´evy flights.  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 flight 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 (1-10 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 fitness 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 fitness 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 fitness 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 fitness of each individual in the population. The fitness will be used to bias the next generation towards better genes. For an empirical density functional, the fitness might be a weighted RMS deviation from experimental values.    = −  (   −  ) 2    “–” used because it is always wanted to maximize the fitness.  3-   Select parents for reproduction. The parents must be selected based on their fitness . The individuals with a higher fitness 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 6-a: 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]   Xin-She 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 Meta-heuristic and Heuristic Algorithms for a 2D Packing Problem”, European Journal of Operational Research 128/1, 34-57, 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.
Related Search
Similar documents
View more...
We Need Your Support
Thank you for visiting our website and your interest in our free products and services. We are nonprofit website to share and download documents. To the running of this website, we need your help to support us.

Thanks to everyone for your continued support.

No, Thanks