 Open Access
 Total Downloads : 603
 Authors : Maheshwar, Sapna Bhatt, Ramesh Lathwal
 Paper ID : IJERTV3IS070708
 Volume & Issue : Volume 03, Issue 07 (July 2014)
 Published (First Online): 31072014
 ISSN (Online) : 22780181
 Publisher Name : IJERT
 License: This work is licensed under a Creative Commons Attribution 4.0 International License
Firefly Algorithm Based Improved Genetic Algorithm: A Proposed Approach
Maheshwar
Department of CSE,
MVN University, Palwal, Haryana
Sapna Bhatt
Department of CSE,
MVN University,Palwal, Haryana
Ramesh Kumar Department of CSE, NIT, Jalandhar, Punjab
Abstract Genetic algorithms are heuristic algorithms that have been applied to many optimization problems. Genetic algorithms follow the process of natural selection and work in iterative manner, generating new population from the old one. The initial population is randomly initialized. The whole iterative process is influenced by the initial values selected at start. So, the proper selection also affect optimization problem.
In our novel approach we have proposed an approach where the initial population is selected from a pool of population on the basis of firefly algorithms. Firefly algorithms are also biologically inspired algorithm and are used to optimization problem.
Keywords Genetic algorithms, firefly algorithms.

INTRODUCTION
Genetic algorithms are the computational models that are based on biological evolution [1], [2]. Genetic algorithms come under the categories of evolutionary algorithms and are generic population based metaheuristic optimization algorithms [3]. Genetic algorithm [4] was first proposed and developed by John Holland in 1970. Genetic algorithm based approach has been used for classification task in data mining [5]. It has been used to extract features [6], [7]. It is also used to discover knowledge from database by combining with neural network [8]. Fuzzy classification based models have been proposed in paper [9], [10] which are based on genetic algorithms. Genetic algorithms are used to develop face recognition systems and discovering rules from biological data [11], [12], and [13]. Genetic algorithms are also used for clustering task of data mining [14].
Genetic algorithm basically works in iterative manner and generates the new population from the old population. Each string in the population is represented in binary form. Genetic algorithm involves three genetic operators named selection, crossover, and mutation and applies these operators on the initial population strings to produce a new generation of strings. This iterative process improves the quality of the solution successively. The process ends when an optimal solution is found. Figure 1 shows how genetic algorithm iteratively finds the solution to a problem. The three basic operators perform the following functionalities:

Selection: Selection operator selects a proportion of the existing population to produce a new population. Selection criteria is based on the value of the fitness function i.e. population with good fitness value is selected for crossover at next step. Fitness function is the problem dependent heuristic function and measures the quality of the solution.

Crossover: This operator is used to generate the new population when the parent population is crossover. In crossover, a random point along the length of chromosomes is selected and genes of one chromosome after this point are swapped with the genes of another chromosome. Different methods are used for selection of chromosomes before applying crossover operator like roulette wheel selection, rank selection, tournament selection etc. Many crossover techniques are used depending on the selection of point along the length of chromosome e.g. single point crossover, two point crossover, cut and slice etc [15].

Mutation: Mutation operator is used to provide stochasticity to the solution and maintain genetic diversity between the two generations. In mutation, an arbitrary bit is changed from its initial state. Different mutation types involve bit string mutation, gaussian mutation, nonuniform mutation etc [16]. Mutation operator prevents the local minima by avoiding the chromosome population from being similar.
Fig. 1. Genetic Algorithm
These three operators are applied iteratively until the optimized solution is found, starting from the initial population which is selected at random. We have proposed an approach to select the initial population using firefly algorithm rather than selecting it randomly. In this approach, some sets of representative are chosen that represent the whole population and provide better solution.
The rest of the paper is organized as follows: Section II gives the overview of the firefly algorithm. Section III includes the proposed algorithm followed by conclusion and future work in section IV.


FIREFLY ALGORITHM
Firefly algorithm (FA) proposed by XinShe Yang is meta heuristic algorithm which is a biologically inspired and is inspired from the flashing behavior of fireflies [17]. This optimization technique is based on the fact that the each firefly attracts to other firefly on the basis of the brightness
i.e. firefly with low brightness is attracted toward firefly with more brightness and hence search space is explored efficiently. Yang applied the FA algorithm for solving linear design problem [18] and multimodal optimization problem [19].
A firefly algorithm follows three basic rules: 1) It considers that all fireflies are unisex. Thus, they attract each other without regarding their sex. 2) Each firefly attracts to other firefly which is proportional to the brightness of individual firefly. So, less bright firefly attracts toward brighter firefly and hence decrease the distance between them. 3) This brightness is a measure of objective function. The objective function is problem dependent function and changes problem to problem. Pseudo code 1 shows the process how firefly algorithm works.
Firefly algorithm
Figure 1.Genetic Algorithm
Parameters Initialization: t=1;
Max_Generation: the maximum number of generations; Objective function: f(x), where x=(x1,……..,xd);
Initial population of fireflies or xi (i=1, 2,…, n); Light intensity Ii for each firefly at xi via f (xi); While (t<Max_Generation)
For i = 1 to n) For j=1 to n
If (Ij > Ii), move firefly i towards j; end if Evaluate new solutions and update light intensity; End for j;
End for i;
Rank the fireflies and find the current best;
End while;
Pseudo code 1: Firefly algorithm
The light intensity of each firefly determine its brightness and hence its attractiveness. Attractiveness of the firefly is calculated using equation 1.
(r) = 0er2 (1)
Where 0 measures the attractiveness at r = 0 and is usually selected as 1. represents light absorption coefficient. ri,j is the Cartesian distance between two fireflies i and j at location xi and xj respectively in the space. The movement of the firefly i in the space which is attracted toward another firefly j is defined by using equation 2.
Xi = xi + 0er2 + (rand 1/2) (2)
Where is the randomization parameter in interval [0, 1] and rand is random number generator with numbers uniformly distributed in range [0, 1]. Parameter controls the variation in attractiveness and define convergence. In most of cases, its values lie in range [0.01, 100].

FIREFLY BASED GENETIC ALGORITHM
As discussed in introduction section, genetic algorithm iteratively finds the optimum solution to a problem starting using a random population of chromosome. This random population selection step is performed using firefly algorithm where the representative chromosomes from the initially selected random population are chosen as very first population to start the geneti algorithm process. These representative chromosomes are selected globally using firefly algorithm. Fireflies with global best position constitute the initial population of chromosomes.
The initial population is partitioned into different sets or cluster and the firefly algorithm is used to compute the center of each cluster. This center will represent the whole cluster or
set of population and will participate in the genetic algorithm process. Pseudo code 2 shows how the whole process is performed:
Start
Parameter initialization:
Define s sets of initial random selected population. t=1;
Max_Generation: the maximum number of generations; Objective function: f(x), where x=(x1,……..,xd);
Initial population of fireflies or xi (i=1, 2,…, n); Light intensity Ii for each firefly at xi via f (xi); For each set 1 to s
While (t<Max_Generation) For i = 1 to n
For j=1 to n
If (Ij > Ii), move firefly i towards j; end if Evaluate new solutions and update light intensity; End for j;
End for i;
Rank the fireflies and find the global best and find the position of the firefly with global best;
End while;
End for each
Apply genetic algorithm with the calculated new representative chromosomes
End
Pseudo code 2: Improved Genetic Algorithm
Pseudo code 2 gives an abstract idea of the proposed approach. Firefly algorithm (FA) is applied to different sets of initially selected random population. This results into the generation of chromosome that represents whole set. These chromosomes are nothing but the firefly with global best position calculated using FA algorithm. These chromosomes now placed in the mating pool from where the take part in crossover and mutation process of the genetic algorithm. To calculate the global best position the attractiveness of one firefly toward another is defined using equation 3 given below [18]:

CONCLUSION AND FUTURE WORK
In this paper, we have proposed a novel approach for selecting the initial population taking participation in genetic algorithm and detailed how firefly algorithm can be used to improve the genetic algorithm by using it to select initial random population of chromosome. This novel approach also results in global optimization at initial state of genetic algorithm and prevent from get trapped in local minima.
Future work: There are a number of directions to future work. First, it would be interesting to apply the proposed approach to publically available dataset from uci learning repository [18]. Second, the proposed approach can be used to solve different optimization problems and different task of data mining like clustering, classification.
REFERENCES

Wikipedia.org/evolutionary algorithm

Stuart J. Russell, Peter Norvig (2008) Artificial Intelligence: A Modern Approach

D.E. Goldberg, Genetic algorithms in search, optimiazation and machine learning, Addison Wesley, Reading, MA, 1989.

Pei M., Goodman E.D., Punch F. (2000) Feature Extraction using genetic algorithm, Case Center for ComputerAided Engineering and Manufacturing W. Department of Computer Science.

Classification task using genetic algorithm

Kermani, B.G.; White, M.W.; Nagle, H.T., "Feature extraction by genetic algorithms for neural networks in breast cancer classification," Engineering in Medicine and Biology Society, 1995., IEEE 17th Annual Conference , vol.1, no., pp.831,832 vol.1, 2025 Sep 1995

Kannan, A.; Maguire, G.Q.; Sharma, A.; Schoo, P., "Genetic Algorithm Based Feature Selection Algorithm for Effective Intrusion Detection in Cloud Networks," Data Mining Workshops (ICDMW), 2012 IEEE 12th International Conference on , vol., no., pp.416,423, 1010 Dec. 2012.

Zhou Yuanhui; Lu Yuchang; Shi Chunyi, "Combining neural network, genetic algorithm and symbolic learning approach to discover knowledge from databases," Systems, Man, and Cybernetics, 1997. Computational Cybernetics and Simulation., 1997 IEEE International Conference on , vol.5, no., pp.4388,4393 vol.5, 1215 Oct 1997.

Kromer, P.; Platos, J.; Snasel, V.; Abraham, A., "Fuzzy classification by evolutionary algorithms," Systems, Man, and Cybernetics (SMC), 2011 IEEE International Conference on , vol., no., pp.313,318, 912 Oct. 2011

Bozorgnia, Arezoo; Zargar, Samaneh Hajy Mahdizadeh; Yaghmaee, Mohammad H., "Fuzzy improved genetic kmeans algorithm," Electrical Engineering (ICEE), 2011 19th Iranian Conference on , vol., no., pp.1,6, 1719 May 2011

Bozorgtabar, B.; Noorian, F.; Rezai Rad, G.A., "A Genetic Programming approach to face recognition," GCC Conference and Exhibition (GCC), 2011 IEEE , vol., no., pp.194,197, 19 22Feb.2011doi: 10.1109/IEEEGCC.2011.5752477

Dash, Satya Ranjan; Dehuri, Satchidananda; Rayaguru, Susil, "Discovering interesting rules from biological data using parallel genetic algorithm," Advance Computing Conference (IACC), 2013 IEEE 3rd International, vol., no., pp.631, 636, 2223 Feb. 2013.
x =x +( e2i,j (x x )+ e2i,gbest(x
– x ))+(rand 1/2)

AlMaqaleh, B.M.A., "Genetic Algorithm Approach to Automated
i i 0
j i 0
best i
(3)
Discovery of Comprehensible Production Rules," Advanced Computing & Communication Technologies (ACCT), 2012 Second International Conference on , vol., no., pp.69,71, 78 Jan. 2012.
where gbest is the global optimal and xbest is the global best position of the firefly.

Dutta, D.; Dutta, P.; Sil, J., "Clustering by multi objective genetic algorithm," Recent Advances in Information Technology (RAIT), 2012 1st International Conference on , vol., no., pp.548,553, 1517 March 2012

http://en.wikipedia.org/wiki/Crossover_%28genetic_algorithm%29

http://en.wikipedia.org/wiki/Mutation_%28genetic_algorithm%29

X. S. Yang, Firefly algorithm stochastic Test Functions and Design ptimization.Int. J. bioinspired computation .2010

A. Asuncion and D. Newman. (2010). UCI Machine Learning Repository, School Inform. Comput. Sci, Univ. California, Irvine[Online].Available: http://www.ics.uci.edu/$\sim$mlearn/{MLR}epository.html