Firefly Algorithm Based Improved Genetic Algorithm: A Proposed Approach

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 fire-fly algorithms. Fire-fly algorithms are also biologically inspired algorithm and are used to optimization problem.

Keywords- Genetic algorithms, fire-fly algorithms.

1. 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 meta-heuristic 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:

   1. 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.

   2. 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].

   3. 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, non-uniform 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.

2. FIREFLY ALGORITHM

   Firefly algorithm (FA) proposed by Xin-She 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) = 0e-r2 (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 + 0e-r2 + (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].

3. 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]:

4. 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

1. Wikipedia.org/evolutionary algorithm

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

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

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

5. Classification task using genetic algorithm

6. 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, 20-25 Sep 1995

7. 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, 10-10 Dec. 2012.

8. 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, 12-15 Oct 1997.

9. 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, 9-12 Oct. 2011

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

11. 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

12. 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, 22-23 Feb. 2013.

    x =x +( e-2i,j (x x )+ e-2i,gbest(x

    – x ))+(rand 1/2)

13. Al-Maqaleh, 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, 7-8 Jan. 2012.

    where gbest is the global optimal and xbest is the global best position of the firefly.

14. 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, 15-17 March 2012

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

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

17. X. S. Yang, Firefly algorithm stochastic Test Functions and Design ptimization.Int. J. bio-inspired computation .2010

18. 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