Cuckoo Search (CS) is heuristic search algorithm which is inspired by the reproduction strategy of cuckoos. This paper investigates the applications of Cuckoo algorithm in various domains. The applications of Cuckoo includes optimizing weights of neural networks, parameters of Support vector machines and Radial basis function, job scheduling, finding optimal cluster head in wireless sensor networks, finding shortest path and clustering. The paper also describes the improved version of CS algorithm namely: Binary CS, Modified CS and Improved CS.
Keywords |
| Cuckoo Search, Levy flights, Modified Cuckoo Search, K-means, Classification, Feature Selection. |
INTRODUCTION |
| Nature inspired computation techniques are those computing techniques that are derived from the study of natural
system. Candidate solutions to the optimization problem play the role of individuals in a population, and the fitness
function determines the quality of the solutions [1]. The commonly used nature inspired algorithms are Genetic
algorithm, Firefly, Artificial bee colony, Ant colony optimization, CS, Particle swarm optimization, Bat, Cat,
Dolphins, Elephant and many more. This paper briefs about the CS algorithm and its applications in the various
domains. Section II describes the working of original cuckoo algorithm and variations of Cuckoo algorithm. Section
III briefs about the applications of Cuckoo algorithm in various domain followed by conclusion in Section IV. |
CUCKOO SEARCH ALGORITHM |
| CS algorithm is based on the obligate brood parasitic behaviour of some cuckoo species in combination with the
Levy flight behaviour of some birds and fruit flies. Some species of Cuckoo birds lay their eggs in communal nests. If a
host bird discovers the eggs are not their own, they will either throw these alien eggs away or simply abandon its nest
and build a new nest elsewhere. CS, can be described using following three idealized rules: |
| a) Each cuckoo lays one egg at a time, and dump its egg in randomly chosen nest; |
| b) The best nests with high quality of eggs will carry over to the next generations; |
| c) The number of available host nests is fixed, and the egg laid by a cuckoo is discovered by the host birth a
probability pa Є [0, 1]. |
| Generalized Pseudo code of the Cuckoo Search (CS): |
| begin |
| Objective function f(X), X = (x1, ..., xd)T |
| Generate initial population of |
| n host nests Xi (i = 1, 2, ..., n) |
| while (t <MaxGeneration) or (stop criterion) |
| Get a cuckoo randomly by L´evy flights |
| evaluate its quality/fitness Fi |
| Choose a nest among n (say, j) randomly |
| if (Fi > Fj ), |
| replace j by the new solution; |
| end |
| A fraction (pa) of worse nests |
| are abandoned and new ones are built; |
| Keep the best solutions |
| (or nests with quality solutions); |
| Rank the solutions and find the current best |
| end while |
| Postprocess results and visualization |
| end |
| Variations of Cuckoo Search: |
| Three variation of CS are briefed below: |
| A. Modified Cuckoo Search (MCS) [16]: |
| The modifications were made, with the goal of speeding up the convergence and hence, reducing the number of
objective function evaluations required to find the global minimum. In the CS, α is constant and typically the value α =
1 is employed. In MCS, the value of α was made to decrease as the number of generations increased. An initial value of
the Levy flight coefficient α =A = 1 was selected and, at each generation, a new value is calculated using α = A / √G,
where G is the generation number. This exploratory search is only performed on those nests that are to be abandoned.
The unmodified CS algorithm could be considered as a series of independent Levy flights, where the ineffective flights
are reset each generation. The missing ingredient was crossover between the solutions. The second modification
included the crossover concept. |
| B. Binary Cuckoo Search (BCS) [17]: |
| A binary version of the CS for feature selection purposes called BCS, in which the search space is modeled as a dcube,
where d stands for the number of features. The main idea is to associate for each nest a set of binary coordinates
that denote whether a feature will belong to the final set of features or not, and the function to be maximized is the one
given by a supervised classifier’s accuracy. |
| C. Improved Cuckoo Search (ICS) [15]: |
| The traditional CS algorithm uses fixed value for both pa and α. These values are set in the initialization step and
cannot be altered during new generations. The main drawback of this method appears in the number of iterations to find
an optimal solution. If the value of pa is small and the value of α is large, the performance of the algorithm will be poor
and leads to significant augment in number of iterations. If the value of pa is large and the value of α is small, the speed
of convergence is high but it may be unable to find the best solutions. The key difference between the ICS and CS is in
the way of adjusting pa and α. To improve the performance of the CS algorithm and eradicate the drawbacks lies with
fixed values of pa and α, the ICS algorithm uses variables pa and α. In the early generations, the values of pa and α
must be big enough to enforce the algorithm to increase the diversity of solution vectors. However, these values should
be decreased in final generations to result in a better fine-tuning of solution vectors. The values of pa and α are
dynamically changed with the number of generation. |
APPLICATIONS OF CUCKOO SEARCH |
| CS has been applied as optimization algorithm for various tasks including finding optimal features, optimizing the
parameters of various classifiers including Neural Network, RBF, SVM parameters, finding optimizing cluster centers,
job scheduling, find optimal path and many more in the different domains including industry, health sector, wireless
sensor network, image processing. The applications of Cuckoo in the various domains are briefed below. |
| Davar et.al [2] have modified cuckoo to optimize two parameters namely C and γ for SVM and have applied it for
diabetic data set. They have used Feature Weighted Support Vector Machines (FW-SVMs) and Modified CS (MCS).
First the Diabetes data is collected and Principal Component Analysis (PCA) is applied as a feature selection strategy.
PCA reduces the dimension of Diabetes disease dataset form 8 to 4 features. Consequently, only 4 features in training
and testing is used. Choosing two parameters C (Cost of the Penalty) and γ (Gamma) is very important in using SVMs.
In this model a three-stage method for classification of the Diabetes diseases. At first, PCA is applied to scrap the
redundant and irrelevant features. Then, Mutual Information (MI) is used to calculate the consequent weight for each
feature. Finally, MCS finds the best values for SVM parameters to classify the Diabetes diseases. Finally SVM is used with Radial Basis Function (RBF) kernel function to detect diabetes disease. They have adopted 10-fold cross
validation on UCI Diabetes diseases dataset. The MI-MCS-SVM is able to achieve higher classification rate when
compared to popular models like LS-SVM, PCA-LS-SVM, PCA-MI-LS-SVM and it obtains 93.58% accuracy along
with significantly speeding up the classification procedure. |
| Diabetic Retinopathy (DR) is a severe disease involving damage to the small blood vessels in the retina; results
from chronically high blood glucose levels in people with poorly controlled diabetes. Exudates is a mass of cells and
fluid that has seeped out of blood vessel. So Srishti et.al [3] proposed a method detect exudates in diabetic retinopathy
using multilevel thresholding. DR damages small blood vessels in the retina which may cause loss of vision. Images
can be segmented by means of threshold selection as exudates and non exudates. Here CS is applied for edge detection
and the steps are: Initialization of population, Generate solution via Levy’s flight and when average fitness is obtained
CS stops and gives output in the form of threshold values. The accuracy results of Otsu’s, Kapur’s and CS method are
found to be 96.4%, 3% and 98.4% respectively. |
| Laser cutting is one of the most extensively used non-conventional material removal process for contour cutting of
wide variety of materials. Miloš MADIĆ et.al [4] found that neural network can be used effectively to model the
process parameters relationships and hence make accurate predictions of surface roughness obtained in laser cutting.
Integrating neural networks and CS algorithm offers a simple and effective method for searching of the optimal process
parameter settings in laser cutting. As an experimental set up, CO2 laser cutting of AISI 304 stainless steel by
considering laser power, cutting speed, assist gas pressure, and focus position as input model parameter was developed.
And it is identified that CS was successful in giving optimal parameters and got an accuracy of 90.44%. |
| Thresholding is one of the simplest techniques for performing image segmentation that has many applications in
image processing, including segmentation, classification, clustering and object discrimination. The drawback of the
conventional multilevel thresholding methods is high computational cost since they do exhaustive search among
exponentially growing number of possible thresholds to optimize the objective functions. Ivona et.al [5] have proposed
CS algorithm for multilevel thresholds selection using the maximum entropy criterion. The optimal thresholds provided
by CS Algorithm are compared with those of PSO and Kapur's thresholding function. Experiments have been
conducted for four types of image datasets: House, Barbara, Boats and Living room. CS outperforms PSO in terms of
both time and multilevel thresholding solution. |
| A computational Grid is a hardware and software infrastructure that provides dependable, consistent, pervasive, and
inexpensive access to high-end computational capabilities. Grid computing is effective only when we schedule the
resources optimally. The problems in grid scheduling are difficult to find the completion time of the job, resource
allocation and job scheduling, resource management and fault tolerance, load balancing, considering both user and
application requirement. Resources can be computers, storage space, instruments, software applications, and data, all
connected through the Internet. M. Prakash et.al [6] have proposed a method to schedule the resources optimally using
CS. Cuckoo optimization approach selects the optimal resource from the set of available resources. This system
allocates the job optimally by considering the deadline requirement of the users and also the minimal execution time
using CS Algorithm. |
| Sensor node in Wireless Sensor Networks (WSNs) is a tiny device that includes three basic components: a sensing
subsystem for data acquisition from the physical surrounding environment, a processing subsystem for local data
processing and storage, and a wireless communication subsystem for data transmission. Energy is the major issue for
these nodes as these nodes usually deployed in the remote areas. Manian Dhivya et.al [7] have applied CS for finding
the energy efficient cluster head selection and formation of clusters among the Sensor nodes. This paper proposes a
new optimization based data collection scheme incorporating CS and Generalized Particle Model Algorithm (GPMA)
and is stated as Cuckoo Based Particle Approach (CBPA). Nodes are deployed randomly and organized as static
clusters by CS. Once the cluster heads are selected, the information is collected, aggregated and forwarded to the base
station using generalized particle approach algorithm. The GPMA transforms the network energy consumption problem
into dynamics and kinematics of numerous particles in a force-field. The proposed approach can significantly lengthen the network lifetime when compared to traditional methods namely: Low Energy Adaptive Clustering Hierarchy
(LEACH) and Hybrid Energy Efficient Distributed clustering (HEED). |
| There is little empirical evidence of the influence of design and workstation aesthetics on employees and the
distance between health and safety (HS), psychological factors, and the architectural design process can be
considerable. HS complaints have also been found to be associated with psychosocial factors at work. For big sized
companies with a lot of office workstations it is difficult to study all of the employees. There is a need of an approach
for systematic HS employee risk assessment of whole companies and identification of employees with extreme HS risk
for immediate attention. Koffka Khan et.al [8] collected data for HS risk on employees at their workplaces, analyzed
the data and proposed corrective measures applying this methodology. For the calculation of an HS risk index
employed a neural-swarm CS (NSCS) algorithm. The calculation of individual employee HS risk indices HSs based of
these weights enables the classification of employees into four categories: low, medium, high and extreme HS risk
levels. Employees with extreme and high indices are immediately attended to by the purchasing of re-arrangement of
equipment at their workstation. |
| Automatic clustering of unstructured documents has become an essentially indispensible task, especially when
dealing with the increasing electronic documents is a serious issue. K-means is one of the most popular unsupervised
clustering algorithms, though the quality of its results relies heavily on the number of clusters chosen and the right
selection of the initial cluster centroids. Walid Mohamed Aly et.al [9] have adapted CS so that it can be applied
efficiently to documents clustering problem. In this model two phases are presented. Experiments have been carried out
on standard unstructured documents: Corpus of Contemporary Arabic (CCA) and results are compared with the Kmeans
(with k value = 3,4,5). CS uses dynamic nests so that different values for the number of clusters can be
explored; these nests are initialized with different corresponding Forgy selection of initial centroids. K-means
clustering algorithm gave a purity of 0.810 when compared to CS which resulted in purity of 0.874. The obtained
results revealed that the proposed approach has a good performance and reached higher value of clustering purity when
compared with classical k-means clustering algorithm. In addition Moe Moe Zaw et.al [10] have applied CS
Optimization algorithm in web document clustering area to locate the optimal centroids of the cluster and to find global
solution of the clustering algorithm. The algorithm is tested on 7 sector benchmark data set by using Cosine Similarity
as distance similarity measure of the two documents. Performance is measured using Precision, Recall and F –
measure. |
| A method to forecast flood accurately and timely is important. Here a method based on Radial Basis Function
(RBF) neural network has been applied for flood water level forecasting. The traditional way of training of the neural
network may drive the network to converge in local minima instead of global minimum. So Kullawat Chaowanawatee
et.al [11] have applied CS to train parameters of RBF neural network instead of a normal back propagation. The
problem lies on that training with the back propagation sometimes drive the network to converge in local minima
instead of global minimum. In RBF neural network, the parameters, centers (ci) and weights (wi), are trained using CS
via L´evy flights. Experiments are conducted on the dataset of Little Wabash River of United States. This new method
with Polyharmonic function outperformed the normal method. The experimental results also showed that the errors
between the forecast and the actual values are acceptable for the application that requires an initial approximation to
support a decision making. |
| Biometrics is used to identify an individual as per their some special characteristics as finger print, voice, iris,
handwriting, typing speed. Monica Sood et.al [12] have applied CS for Speaker Recognition systems and voice. The
process of Speaker Recognition is optimized by a fitness function by matching of voices being done on only the
extracted optimized features produced by the CS algorithm. Here voices are classified to recognize the particular voice
belongs to the person by short listening the feature from voice. Initially Speaker speaks and his voice is recorded for
either feature matching or feature selection. Then CS works on only the best feature to extract the feature from the
voice. Now these extracted features will be matched with the inputted voice’s features. For matching purpose,
Correlation has been used. The extracted features closest to the stored features will be the one that will be matched. |
| Based on this the decision is taken, if the features are matched then the speaker will be authenticated else will be
rejected. |
| K-means clustering algorithm performance depends to a great extent on the initial values of the starting centroids
randomly generated each time the algorithm is run. It is known that K-means can easily fall into local optima that do
not produce the best clustering results. A number of bio-inspired optimization methods have recently emerged with
designs imitating swarm behaviour among groups. Intuitively, bio-inspired optimization algorithms should overcome
the limitations of K-means clustering algorithm in finding globally optimum clusters. This integration is significant,
because it will serve as a successful pioneer exemplar for the future development of hybrid bio-inspired data mining
algorithms. Rui Tang et.al [13] have optimized K-means algorithm using CS algorithm. Performance of the CS with
K-means it is applied on the popular datasets namely Iris, Wine, Libras, Haberman’s, Synthetic and mouse. The results
of K-means clustering are compared with Ant, Firefly, Bat, Wolf and Cuckoo. CS outperformed K-means with an
average time of 18.75 seconds compared to the K-mean’s 75.73 seconds. |
| In distributed system, user give some task to the server and the server processes and give it back to the user. But the
problem is that there will be many servers and it will be difficult to locate the best possible server. So the concept of
mobile agent comes into the picture. Whereas, mobile agent will act as an intermediary system between user and
server. Mobile agent will carry job of user and then move around the network of servers to find a suitable location to
process the job. While mobile agent migrates from one server to another, user’s job is paused and will be then resumed
the process upon the next server. Here path finding for the mobile agent is the difficult job. Akajit Saelim et.al [14]
have applied Modified CS for solving mobile agent migration problem. Mobile agent migration planning problem is the
finding path problem of graph theory same as the Travelling Salesman Problem. Hence, data sets from travelling
salesman problem are used rather than actual network data namely: 7 data sets p01 (15 nodes), gr17 (17 nodes), fri26
(26 nodes), dantzig42 (42 nodes), eil51 (51 nodes), eil76 (76 nodes), and rat99 (99 nodes). They have compared MCS
method with the former proposed method (FOR), original CS Algorithm (CS) and Ant Colony System (ACS).
Performance was measured using path length and accuracy. Experimental results prove that shorter path length and
improved accuracy when compared to the above methods for most of the data sets. |
| Ehsan et.al [15] have proposed the Improved Cuckoo Search (ICS) for optimizing the network weights to enhance
accuracy and convergence rate of the CS. ICS is described in section I. To test the improvement of ICS over CS,
experiments are conducted using Iris and breast cancer data sets. The average classification accuracy for CS and ICS
for Iris data set is found to be 92.14% and 94.10% respectively. For breast cancer dataset the average classification
accuracy of CS and ICS is found to be 96.91% and 96.98% respectively. |
| Sean P. Walton [16] proposed Modified Cuckoo Search (MCS), which is a powerful gradient free optimization
algorithm. MCS is a fast optimization algorithm in terms of number of objective function evaluations required to reach
a solution. It is also able to handle functions which are non-smooth, multimodal and have many dimensions. MCS is
described in section I. This new modified version is tested on two applications namely aerodynamic shape optimization
and mesh optimization. This method showed good results as well as the reduced CPU time required to find the solution.
In particular the modified CS shows a high convergence rate to the true global minimum even at high numbers of
dimensions. |
| D.Rodrigues et.al [17] have proposed new feature selection called Binary CS Feature selection(BCS) to find the
most discriminative set of features. BSC is described in section I. The experiments were carried out in the context of
theft detection in power distribution systems in two datasets commercial and industrial obtained from a Brazilian
electrical power company, and have demonstrated the robustness of the proposed technique against with several others
nature-inspired optimization techniques like Binary Bat Algorithm, Binary Firefly Algorithm , Binary Gravitational
Search Algorithm and the Binary Particle Swarm Optimization. Performance is measured in terms of Time and
accuracy. The BCS resulted in the same classification accuracy when compared to other methods but in reduced time. |
CONCLUSION |
| CS is a powerful search algorithm that it inspired by the breeding behaviour of cuckoos. This paper gives the brief
description of the applications of one of nature inspired algorithm – CS algorithm in the various domains including
Industry, Image processing, wireless sensor networks, flood forecasting, document clustering, speaker recognition,
shortest path in distributed system, classification task in health sector, job scheduling. The survey reveals that Cuckoo
algorithm outperforms various nature inspired algorithm in terms of improved performance and less computational
time. |
Tables at a glance |
 |
| Table 1 |
|
References
- X.-S. Yang And S. Deb, “Cuckoo Search Via Levy flights,” In Proceedings Of The Nabic- World Congress On Nature & Biologically Inspired Computing, pp. 210–214, 2009.
- D Giveki, H Salimi, GR Bahmanyar, Y Khademian , Automatic detection of diabetes diagnosis using feature weighted support vector machines based on mutual information and modified cuckoo search, arXiv preprint arXiv:1201.2173, 2012 .
- Srishti, “Technique Based On Cuckoo’s Search Algorithm For Exudates Detection In Diabetic Retinopathy”, Ophthalmology Research: An International Journal Vol.2(1), pp.43-54, 2014, Article No. Or.2014.005.
- MilošMadić, MiroslavRadovanović, Application Of Cuckoo Search Algorithm For Surface Roughness Optimization In Co 2 Laser Cutting. , Annals of the Faculty of Engineering Hunedoara-International Journal of Engineering, Volume 11(1), 2013.
- IvonaBrajevic, Milan Tuba, NebojsaBacanin ,“Multilevel Image Thresholding Selection Based On The Cuckoo Search Algorithm”, Advances in Sensors, Signals, Visualization, Imaging and Simulation, pp. 217-222, 2012.
- M. Prakash, R.Saranya, K. RukmaniJothi And A. Vigneshwaran, “An Optimal Job Scheduling In Grid Using Cuckoo Algorithm”,International Journal Of Computer Science And Telecommunications, Vol. 3(2), pp. 65-69, February 2012.
- ManianDhivya, MurugesanSundarambal, LoganathanNithisshAnand , “Energy Efficient Computation Of Data Fusion In Wireless Sensor Networks Using Cuckoo Based Particle Approach (CBPA)”, Int. J. Communications, Network And System Sciences, Vol.4, pp. 249-255, 2011.
- Koffka Khan & Ashok Sahai , “Neural-Based Cuckoo Search Of Employee Health And Safety (Hs)”, I.J. Intelligent Systems And Applications, Vol.02, pp. 76-83, 2013.
- Walid Mohamed Aly, HanyAtefKelleny, “Adaptation Of Cuckoo Search For Documents Clustering”, International Journal Of Computer Applications, Vol.86(1), pp. 4-10, January 2014.
- Moe MoeZaw And EiEi Mon, “Web Document Clustering Using Cuckoo Search Clustering Algorithm Based On Levy Flight”, International Journal Of Innovation And Applied Studies Issn 2028-9324 Vol. 4(1), pp. 182-188, Sep. 2013.
- KullawatChaowanawatee, ApichatHeednacram, “Implementation Of Cuckoo Search In RBF Neural Network For Flood Forecasting”, Fourth International Conference On Computational Intelligence, Communication Systems And Networks, pp. 22-26, 2012.
- Monica Sood, GurlineKaur , “Speaker Recognition Based On Cuckoo Search Algorithm”, International Journal Of Innovative Technology And Exploring Engineering (Ijitee) Vol. 2(5), pp.311-313, April 2013.
- Rui Tang, Simon Fong, Xin-She Yang, Suash Deb, “Integrating Nature-Inspired Optimization Algorithms To K-Means Clustering”, ICDIM, pp. 116-123, 2012.
- AkajitSaelim, SuwannaRasmequan, PusitKulkasem, KrisanaChinnasarn, AnnupanRodtook, “Migration Planning Using Modified Cuckoo Search Algorithm” , 13th International Symposium On Communications And Information Technologies (Iscit), pp. 621-626, 2013.
- EhsanValian, ShahramMohanna And SaeedTavakoli , “Improved Cuckoo Search Algorithm For Feedforward Neural Network Training”, International Journal Of Artificial Intelligence & Applications (Ijaia), Vol.2(3), pp. 36-43, July 2011.
- S. Walton; O. Hassan, K. Morgan and M.R. Brown, "Modified Cuckoo Search : A new gradient free optimisation algorithm". Chaos, Solitons& Fractals. doi:10.1016/j.chaos.2011.06.004, 30 June 2011.
- D.Rodrigues, L.A.M. Pereira, A. N. Souza, C. C.Ramos, Xin-She Yan “Binary Cuckoo Search : A Binary Cuckoo Search Algorithm For Feature Selection”, IEEE International Symposium on Circuits and Systems (ISCAS), pp. 465 - 468 ,2013
|
Menu