Cybernetics and Systems Analysis, Vol. 49, No. 6, November, 2013

A REVIEW OF NICHING GENETIC ALGORITHMS FOR MULTIMODAL FUNCTION OPTIMIZATION N. N. Glibovetsa† and N. M. Gulayeva a‡

UDC 004.023

Abstract. In this paper, a comprehensive review of approaches to solve multimodal function optimization problems via genetic niching algorithms is provided. These algorithms are presented according to their space–time classification. Methods based on fitness sharing and crowding methods are described in detail as they are the most frequently used. Keywords: genetic algorithm, multimodal function optimization, niching methods. INTRODUCTION Genetic algorithms, which are based on the ideas of evolution theory, are efficient in solving a wide range of optimization problems. As a rule, only one optimum of the objective function is found using traditional genetic algorithms. At the same time, there are problems where not one but k optima of a multimodal function should be found, which, first, increases the probability of finding the global optimum and, second, makes it possible for decision-maker to choose from a set of alternative solutions [1]. The most simple approach to determining the set of optima of a multimodal function using genetic algorithms is to carry out multiple independent runs of the traditional genetic algorithm and save the results of the current run if the next run yields a new solution. An analog of such approach is implementing simultaneous runs of the traditional genetic algorithm on different processors that do not interact and each of them operates with its subpopulation. The approaches described above are called partitioned genetic algorithms. Their shortcoming is a repeated search on the same sections of space. More efficient are niching genetic algorithms, which promote the formation of stable subpopulations in the search space so that each subpopulation is formed around one of the unknown optima. Since the information about these algorithms is contained in many publications and is not brought together, let us present a review of the currently known niching methods. GENERAL CHARACTERISTIC OF NICHING GENETIC ALGORITHMS Niching genetic algorithms are based on the phenomenon of speciation and specialization in natural ecosystems. In ecology, by a niche is understood a complex of specific living conditions, a subset of environmental resources, and a species is a set of individuals consuming the resources of a specific niche. Thus, niches are a part of the environment and species are a part of the set of all possible individuals. By analogy, in genetic algorithms the term niche is used for the search space domain, and species for the set of individuals with similar characteristics. In niching genetic algorithms, individuals of a population are divided into several subpopulations–species, each of which occupies its niche, is related to it during the run of the algorithm, and specializes on the solution of a certain subproblem of the original problem (searches for the optimum in the niche). Such an approach preserves the variety of individuals in the population and allows the genetic algorithm to analyze several optima simultaneously. In the majority of algorithms, this effect is attained due to the modification of the process of selection of individuals, which takes into account not only the value of the fitness function but also the distribution of individuals in the space of genotypes or phenotypes. It is a

National University of Kyiv-Mohyla Academy, Kyiv, Ukraine, †[email protected]; ‡[email protected]. Translated from Kibernetika i Sistemnyi Analiz, No. 6, November–December, 2013, pp. 15–22. Original article submitted October 23, 2012. 1060-0396/13/4906-0815

©

2013 Springer Science+Business Media New York

815

important in niching algorithms both to find the necessary optimum and not to lose them during the run of the algorithm, i.e., it is necessary not only to form niches but also to preserve them for a long time. Such requirement is due to the necessity to distinguish cases where the found solution represents a new niche and a niche localized earlier. The most popular is the spatial–temporal classification of niching methods according to which these methods are divided into two classes: — spatial or parallel methods, which create and support the set of subpopulations (species) simultaneously in the space of the uniform population (in such algorithms, the result is due to a wide scatter of the population in the search space); — temporal or sequential methods, which iteratively find the set of subpopulations (species), with time. This classification is not related to the number of the involved processors. Let us consider the spatial–temporal classification of the currently known niching methods: — temporal, including the niching sequential method and hierarchical niching methods; — spatial, including methods based on fitness sharing, clearing, clustering, crowding, mating restriction, and hierarchical niching. SEQUENTIAL NICHING METHOD The method of sequential location of niches (sequential niching, SN) carries out multiple sequential starts of the traditional genetic algorithm [2]. After each run of this algorithm, the best solution is brought to the global bank of solutions; in the subsequent runs the fitness level of all the individuals near this solution decreases. Such a modification of the fitness level at the subsequent runs of the genetic algorithm prevents repeated analysis of the same domain of the search space and hence the convergence of the algorithm to the already known optima. The modified fitness function f m is often defined iteratively: f m ,0 ( X ) º f ( X ) ; f m ,i + 1 ( X ) = f m ,i ( X )* g ( X , S i ) ; f m ( X ) º f m ,n ( X ) , where f ( X ) is the initial unmodified fitness function, S i is the best individual found as a result of the ith run of the algorithm, and n is the number of the current run of the algorithm. Function g ( X , S i ) is called fitness derating function; it is often a power or exponential function. One of the modifications of sequential niching is saving, after each run, not one but all the unique solutions found by the genetic algorithm [3]. Another interesting modification is the propagation of the fitness derating effect outside the niche radius and application of clearing to eliminate solutions within the radius [4]. METHODS BASED ON FITNESS SHARING The idea to construct sharing-based methods employs the fact that only a limited amount of a renewable resource (water, food, sunlight) is available in each ecological niche; hence, individuals occupying this niche compete for the same resources and should share them. In the context of the genetic algorithm of solving optimization problems, the resource allocated for a niche is the value of the objective function or the fitness level of individuals. The main idea of the method of fitness sharing [5] is to share the fitness factor among similar individuals of the population. To this end, in the genetic algorithm before the selection stage the fitness level of each individual is reestimated depending on the number of individuals in one niche with the given individual: the more individuals in one niche, the stronger their pressure on each other. Let us denote by d ij the distance metric or dissimilarity measure between chromosomes X i and X j in the space of genotypes (for example, Hamming distance) or of phenotypes (for example, Euclidean distance). Sharing function S ( d ij ) is the function that determines the level of proximity (involvement) of chromosomes in the population. It should satisfy the following properties: " d ij : 0 £ S ( d ij ) £ 1; S is decreasing; S ( 0) = 1 (returns 1 if elements are identical); and lim S ( d ij ) = 0 . The last property is sometimes written as " d ij ³ s share : S ( d ij ) = 0 . Parameter s share is called niche size, d ij ®¥

816

niche radius, share radius, sharing radius, threshold of dissimilarity, or distance cutoff. Individuals X i and X j , spaced at the distance d ij one from the other, are considered similar and should share the fitness level if d ij < s share (S ( d ij ) > 0). Sharing function S ( d ij ) is often defined as a ì æ d ö ï 1- ç ij ÷ if d ij < s share , (1) S ( d ij ) = í ç s ÷ share ø è ï otherwise, 0 î where a is a constant that determines the form of the sharing function. The influence of the parameter a on the algorithm operation has not been thoroughly studied and the choice of the value of the parameter s share is essential for successful operation of the algorithm. Recommendations for the determination of s share are presented in [6–8]. With the sharing function determined from (1), the fitness level of individuals can be reestimated as follows: ì f ( X j ) if "i : S ( d ij ) = 0, ï fs ( X j ) = í f ( X j ) if $ i : S ( d ij ) ¹ 0, ï m j î N

where m j = å S ( d ij ) is niche count and N is the number of individuals in the population. The original fitness function f i =1

is called prior fitness (raw fitness) or objective fitness, and the function of reestimation of the fitness level f s is called effective fitness or shared fitness. Among the main shortcomings of the fitness sharing method are high computing complexity of the algorithm and difficulties in choosing the value of the parameter s share . Noteworthy are the following modifications of the fitness sharing algorithm: — using a sample of size r<
CLEARING As well as fitness sharing, clearing method [19] is based on the concept of limited resources in the environment and the necessity of sharing them among similar individuals. However, unlike fitness sharing, clearing does not divide resources equally among all individuals of the subpopulation but provides them only to the best representatives. To this end, individual with the best fitness level, called dominant individual, is determined in each subpopulation. The other individuals of this subpopulation are called dominated individuals. After determining all the dominant individuals, clearing procedure is applied immediately before the selection and assigns zero value to the health of all the dominated individuals of the subpopulation. A popular modification of clearing is the use of not one but k dominant individuals. There is also a modification of shifting dominated individuals outside the winner’s neighborhood to find new promising domains of the search space [20].

CLUSTERING To allocate elements of the population in niches, well-known clustering methods are often used in combination with niching methods such as fitness sharing or clearing. For example, in Yin and Germay’s scheme [10], individuals are 817

allocated in niches (clusters) based on the algorithm of k-means and the fitness level of individuals is then recalculated by the formula f (X i ) , fs ( X i ) = aö æ æ d ö n c × ç 1- çç ic ÷÷ ÷ ç è 2d max ø ÷ ø è where n c is the number of individuals in the niche with centroid c ; d ic is the distance between individual X i and centroid c ; d max is the greatest admissible distance between an individual and the centroid of the cluster to which it belongs; a is a constant (it is assumed that individual X i belongs to the cluster with centroid c). Among other methods of the above-mentioned type noteworthy are methods of collective sharing [21], dynamic fitness sharing (DFS) [22], dynamic niche sharing [9], dynamic niche clustering (DNC) [23, 24], and hierarchical clustering technique [25]. Of interest is also the species conserving genetic algorithm (SCGA) [26], where after dividing the population into subpopulations the best individuals of each species, called species seeds, are saved to be transferred to the next generation. Such approach prevents species loss. Among modifications of this method noteworthy are evolutionary algorithm with species-specific explosion (EASE) [27] and topological species conservation algorithm TSC and TSC2 [28, 29]. CROWDING By crowding or restricted replacement methods are meant genetic algorithms with partial replacement of population, where adding a new element to the population crowds out a similar element. Such approach is based on the respective ecological phenomenon: competition among similar individuals of the population for limited resources. Similar individuals, trying to occupy the same niche, are forced to compete for possession of the resources of this niche; hence, when reaching the potential capacity of the niche, weak individuals are crowded out from the population by its stronger members. In the standard crowding method or crowding factor model [30], to generate descendants, individuals are selected from the population at each iteration of the algorithm (proportional selection), whose number is determined by the GG parameter called generation gap. A descendant crowds out from the population the most similar individual from a randomly selected group of individuals of the current population; the size of this group is determined by the parameter ñ f called crowding factor. A shortcoming of the standard crowding method is substitution errors, which are characterized by crowding of an individual from one niche by an individual from another niche and are the reason of the loss of a part of optima by the population. To overcome this problem, modifications of the standard crowding method were developed. In particular, in [31, 32] it is proposed to use the strategy of substitution with additional pressure of selection. In deterministic crowding (DC) [3, 33], all individuals of the population are admitted to generate descendants, and to withdraw individuals from the population, binary tournaments between parents and descendants are held and a descendant is paired with the most similar parent. Probabilistic crowding (PC) [34] is a modification of the method of deterministic crowding where the results of tournaments between parents and descendants are determined by the probability rule: each participant of the tournament can win with the probability proportional to its fitness level. The method of restricted tournament selection (RTS) [35] is a modification of standard crowding where generation gap (parameter GG) is two individuals, and for the decision about withdrawing an individual from the population, adaptation of the standard tournament selection is used. In the multi-niche crowding (MNC) method [36, 37] in shaping a parent pair and determining individuals to be crowded out by descendants, individuals from the same niche are preferred. MATING RESTRICTION METHODS Mating restriction methods impose constraints on descendants generated by parents from different niches. Introducing these restrictions is justified since cross-breeding of such parents can result in very weak descendants. A biological justification of such restrictions is geographical isolation of species, which creates a barrier for gene exchange. To apply mating restrictions, the first parent is often chosen randomly, and for the second the mechanism of constraints should be taken into account (for example, the distance between the second and the first parents should not exceed a prescribed value q). Mating restrictions are sometimes implemented by tagging of individuals, which makes it possible to determine the membership of the individual in a niche based not on evaluations of distances but considering the information about its heredity [14]. Noteworthy is the restricted competition method [3], where constraints on competitions between unlike individuals are imposed in tournament selection of parents. 818

HYBRID NICHING ALGORITHMS Completing the review of the available niching algorithms, let us mention the efficiency of hybridization of different algorithms, namely, species conservation algorithm with the multinational genetic algorithm [28, 29], deterministic crowding with the gene-invariant genetic algorithm [3], methods of mating restrictions with fitness sharing and clustering methods [7, 9, 10], etc. An efficient method of combining different niching algorithms to form an ensemble of niching algorithms (ENA) is proposed in [38]. In the model of hierarchical fair competition (HFC) [39], a hierarchical structure of subpopulations is created based on the fitness level of individuals. If spatial niching algorithms are used at each level of hierarchy, the method of hierarchical niching is meant [40]. One of the improvements of this method is the algorithm of quick hierarchical fair competition (QHFC) [40], which uses deterministic crowding. CONCLUSIONS Problems of the real world stipulate the constant growth of interest in methods of solution of multimodal optimization problems, in particular, a wider use of genetic niching algorithms. In the paper we have reviewed the main genetic niching algorithms and their modifications. Unfortunately, the problem of systematic comparative analysis of niching algorithms has not been solved yet. The studies devoted to the comparative analysis of these algorithms, as a rule, consider two to five algorithms applied to some (sometimes only one) function. An analysis of the well-known publications allows concluding that in the general case spatial (parallel) methods are more efficient than temporal (sequential) ones. Many researchers mark the high efficiency of different modifications of the methods of fitness sharing, clearing, deterministic crowding, restricted tournament selection, and algorithm of quick hierarchical fair competition. REFERENCES 1. 2. 3. 4. 5.

6. 7.

8. 9. 10.

11. 12.

13.

I. V. Sergienko and V. P. Shilo, “Problems of discrete optimization: Challenges and main approaches to solve them,” Cybern. Syst. Analysis, 42, No. 4, 465–482 (2006). D. Beasley, D. R. Bull, and R. R. Martin, “A sequential niche technique for multimodal function optimization,” Evol. Comput., 1, No. 2, 101–125 (1993). S. W. Mahfoud, “Niching methods for genetic algorithms,” Ph.D. Dis., Univ. of Illinois at Urbana-Champaign, Illinois Genetic Algorithms Lab. (1995). J. Vitela and O. Castanos, “A real-coded niching memetic algorithm for continuous multimodal function optimization,” in: Proc. IEEE Congr. on Evol. Comput. (CEC 2008), 22–24 July 2008, Washington (2008), pp. 2170–2177. D. E. Goldberg and J. Richardson, “Genetic algorithms with sharing for multimodal function optimization,” in: J. J. Grefensette (ed.), Genetic Algorithms and their Applications: Proc. Sec. Intern. Conf. on Genetic Algorithms (ICGA-87), Lawrence Erlbaum, Hillsdale, NJ (1987), pp. 41–49. A. Cioppa, C. Stefano, and A. Marcelli, “On the role of population size and niche radius in fitness sharing,” IEEE Trans. Evol. Comput., 8, No. 6, 580–592 (2004). K. Deb and D. E. Goldberg, “An investigation of niche and species formation in genetic function optimization,” in: J. D. Schaffer (ed.), Proc. 3rd Intern. Conf. on Genetic Algorithms (ICGA-89), Morgan Kaufmann, San Mateo, CA (1989), pp. 42–50. K. Deb, Genetic Algorithms in Multimodal Function Optimization: Masters Thesis and TGGA (Rep.), Univ. of Alabama, N 89002, Tuscaloosa (1989). B. L. Miller and M. J. Shaw, “Genetic algorithms with dynamic niche sharing for multimodal function optimization,” in: Proc. 1996 IEEE Intern. Conf. on Evol. Comput. (ICEC’96), New York (1996), pp. 786–791. X. Yin and N. Germay, “A fast genetic algorithm with sharing scheme using cluster analysis methods in multimodal function optimization,” in: R. F. Albrecht, C. Reeves, and N. C. Steele (eds.), Proc. Intern. Conf. on Artificial Neural Networks and Genetic Algorithms, Springer-Verlag, Berlin (1993), pp. 450–457. P. Darwen, P. Darwen, and X. Yao, “A dilemma for fitness sharing with a scaling function,” in: Proc. 1995 IEEE Conf. Evol. Comput., IEEE Press, Piscataway, NJ (1995), pp. 166–171. D. E. Goldberg, K. Deb, and J. Horn, “Massive multimodality, deception and genetic algorithms,” in: R. Manner and B. Manderick (eds.), Proc. Parallel Problem Solving from Nature, 2, Elsevier Sci. Publ. B.V., Amsterdam (1992), pp. 37–46. B. Sareni and L. Krahenbuhl, “Fitness sharing and niching methods revisited,” IEEE Trans. on Evol. Comput., 2, No. 3, 97–106 (1998). 819

14. 15. 16. 17.

18. 19. 20. 21. 22. 23. 24. 25. 26. 27. 28. 29. 30. 31. 32. 33. 34. 35. 36. 37. 38. 39. 40.

820

W. M. Spears, “Simple subpopulation schemes,” in: Proc. 3rd Annual Conf. on Evol. Progr., World Sci. (1994), pp. 296–307. F. Menczer and K. Belew, “Local selection,” in: Proc. 7th Ann. Conf. on Evol. Progr. (1998), pp. 703–712. R. E. Smith, S. Forrest, and A. S. Perelson, “Searching for diverse, cooperative populations with genetic algorithms,” Evol. Comput., 1, No. 2, 127–149 (1993). D. Goldberg, “Adaptive niching via coevolutionary sharing,” in: D. E. Goldberg and Liwei Wang, Quagliarella D. Genetic Algorithms and Evol. Strategy in Eng. and Comput Sci.: Recent Adv. and Industr. Appl., John Wiley and Sons, Ltd. (1998), pp. 21–38. R. K. Ursem, “Multinational evolutionary algorithms,” in: Proc. Congr. of Evol. Comput. (CEC-99), 3, IEEE Press, Piscataway, NJ (1999), pp. 1633–1640. A. PÁtrowski, “A clearing procedure as a niching method for genetic algorithms,” in: Proc. 3rd IEEE Intern. Conf. on Evol. Comput (ICEC’96), Nagoya (Japan), IEEE Press, Piscataway, NJ (1996), pp. 798–803. G. Singh and K. Deb, “Comparison of multi-modal optimization algorithms based on evolutionary algorithms,” in: Proc. 8th Ann. Conf. on Genetic and Evol. Comput., GECCO 2006 (Seattle, WA, 2006), ACM Press, New York (2006), pp. 1305–1312. O. V. Pictet, M. M. Dacarogna, R. D. DavÁ, et al., Genetic Algorithms with Collective Sharing for Robust Optimization in Financial Applications, Olsen & Assoc. Working Paper (1995). A. D. Cioppa, C. D. Stefano, and A. Marcelli, “Where are the niches? Dynamic fitness sharing,” IEEE Trans. on Evol. Comput., 11, No. 4, 453–465 (2007). J. Gan and K. Warwick, “A genetic algorithm with dynamic niche clustering for multimodal function optimisation,” in: Proc. 4th Intern. Conf. on Artificial Neural Networks and Genetic Algorithms, 3, Springer (1998), pp. 248–255. J. Gan and K. Warwick, “Dynamic niche clustering: A fuzzy variable radius niching technique for multimodal optimisation in Gas,” in: Proc. 2001 Congr. on Evol. Comput., 1, IEEE (2001), pp. 215–222. A. PÁtrowski, “An efficient hierarchical clustering technique for speciation: Techn. Rep.,” Inst. Nat. des Telecommunications, Evry, France (1997). J.-P. Li, M. E. Balazs, G. T. Parks, and P. J. Clarkson, “A species conserving genetic algorithm for multimodal function optimization,” Evol. Comput., 10, No. 3, 207–234 (2002). K. C. Wong, K. S. Leung, and M. H. Wong, “An evolutionary algorithm with species-specific explosion for multimodal optimization,” in: Proc. 11th Ann. Conf. on Genetic and Evol. Comput., ACM GECCO (2009), pp. 923–930. C. Stoean, M. Preuss, R. Stoean, and D. Dumitrescu, “Disburdening the species conservation evolutionary algorithm of arguing with radii,” in: Proc. Genetic Evol. Comput. Conf. (GECCO) (2007), pp. 1420–1427. C. Stoean, M. Preuss, R. Stoean, and D. Dumitrescu, “Multimodal optimization by means of a topological species conservation algorithm,” in: IEEE Trans. on Evol. Comput., 14, No. 6, 842–864 (2010). K. A. De Jong, An Analysis of the Behavior of a Class of Genetic Adaptive Systems: Ph.D. Dis., Ann Arbor: Univ. of Michigan (1975). T. A. Sedbrook, H. Wright, and R. Wright, “Application of a genetic classifier for patient triage,” in: Proc. 4th Intern. Conf. on Genetic Algorithms (1991), pp. 334–338. I. Stadnyk, “Schema recombination in a pattern recognition problem,” in: Genetic Algorithms and their Applications, Proc. Sec. Intern. Conf. on Genetic Algorithms (1987), pp. 27–35. S. W. Mahfoud, “Crowding and preselection revisited,” in: R. Manner and B. Manderick (eds.), Proc. of Parallel Problem Solving from Nature, 2, Elsevier Sci. Publ. B.V., Amsterdam (1992), 27–36. O. Mengsheol and D. Goldberg, “Probabilistic crowding: Deterministic crowding with probabilistic replacement,” in: Proc. of Genetic and Evol. Comput Conf. (GECCO 1999, 13–17 July), Orlando, Florida (1999), pp. 409–416. G. Harik, “Finding multimodal solutions using restricted tournament selection,” in: L. J. Eshelman (ed.), Proc. 6th Int. Conf. on Genetic Algorithms (ICGA-95), Pittsburgh, Morgan Kaufmann, San Mateo, CA (1995), pp. 24–31. W. Cedeno and V. Vemuri, “Dynamic multimodal function optimization using genetic algorithms,” in: Proc. XVIII Latin-Amer. Inform. Conf., Las Palmas de Gran Canaria, Spain (1992), pp. 292–301. W. Cedeno, V. R. Vemuri, and T. Slezak, “Multiniche crowding in genetic algorithms and its application to the assembly of DNA restriction-fragments,” Evol. Comput., 2, No. 4, 321–345 (1994). E. L. Yu and P. N. Suganthan, “Ensemble of niching algorithms,” Inform. Sci., 180, No. 15, 2815–2833 (2010). http://garage.cse.msu.edu/hfc/hierarchical_fair_competition.htm. J. Hu and E. D. Goodman, “Robust and efficient genetic algorithms with hierarchical niching and a sustainable evolutionary computation model,” Proc. of GECCO, 1, 1220–1232 (2004).