Distributed quasi steadystate genetic algorithm with niches and species.
Abstract: In this paper, we have proposed a new real coded genetic
algorithm with species and sexual selection (GAS3). GAS3 is a
distributed quasi steadystate realcoded genetic algorithm. GAS3 uses
sex determination method (SDM) to determine the sex (male or female) of
members in population. Each female member is considered as a niche in
population and the species formation takes place around these niches.
Sexual selection strategy selects female and required number of male
members from the species to perform the recombination operation. The
Parentcentric recombination operators are used to generate offspring.
If species is not performing well, then the merging to the nearby
species takes place. Explorative recombination operator is used to
explore a wide range of search space in the beginning, while
exploitative recombination operator is used in the later stages. The
performance of GAS3 is tested on unimodal and multimodal test
functions. It got success in solving wide range of problems. Its
performance is also compared with the other realcoded genetic
algorithms.
Keywords: realcoded genetic algorithms, parentcentric crossover operators, chromosome differentiation, Clustering, sexual selection scheme, distributed genetic algorithm. I. Introduction Darwinian biological evolution, i.e. gradual adaptation through natural selection is a process consisting of three component principles: variation, heredity and individual selection. Variety and diversity, whether fully random or not, are essential because without them there can be no evolution whatsoever. The information driving evolution in actual cases is the distribution of variation in a given population. Variation comes forth via mutations and sexual recombination. Heredity means selected units have some degree of durability and resilience, via a mechanism that passes on characteristics to other units. Individual selection is based on competition between individuals in the face of selection pressure (scarce resources, space, mating partners, etc.). Coevolution in biology can be considered the result of merging (community and population) ecology and evolutionary biology [1]. Genetic algorithms (GAs) are search and optimization procedures that are motivated by the principles of natural selection and natural genetics. Some fundamental ideas of genetics are borrowed and used artificially to construct search algorithms that are robust and required minimum problem information [2]. In GAs, the role of selection and recombination operators is very well defined. Selection operator controls the direction of search and recombination operator generates new regions for search. In realcoded GAs (RCGAs), chromosome is a realparameter decisionvariable vector. The recombination operation is a method of sharing information among chromosomes. The recombination operator has always been regarded as the main search operator in GAs as it exploits the available information in previous samples to influence future searches. The detailed study on recombination operators can be found elsewhere [3] [4]. The parentcentric crossover operators (PCCOs) used in RCGAs; in general, use a probability distribution for creating offspring in a restricted search space around the region marked by one of the parent, the female parent. The range of this probability distribution is controlled by distribution index. Generation of offspring depends on the distance among the female parent and the other parents involved in the recombination operation, the male parents [5]. The sex of individuals in population can be determined either randomly or based on some problem specific knowledge where individuals with certain trails are chosen to be one sex while the rest are chosen to be of another sex. In most of the PCCO's solutions are selected randomly for mating. The work on nonrandom mating in GAs, refers to the incestprevention techniques or assortative mating. Lozano et al. [6] proposed the uniform fertility selection method for the selection of a female parent and the negative assortative mating technique for the selection of a male parent. For male and female parents selection, SexualGA [7] uses two different selection operators. In this way the multiple combination of different selection can be realized. During evolution, the genetic diversity or variety in population makes the search more effective and it also prevents GAs from a premature convergence. The centralized or distributed methods are used to prevent premature convergence. A centralized one, such as incest prevention or assortative mating incurs high overhead in global comparison. A distributed method divides the whole population into small groups or subpopulations and let these subpopulations evolve separately. A migration mechanism exchanges individuals between subpopulations, allowing the new diversity to be injected into converging subpopulations. The gradual distributed RCGA (GDRCGA) [8] applies different crossover operator to each subpopulation. These operators are differentiated according to their associated exploration and exploitation properties and the degree thereof. The effect achieved is a parallel multiresolution with regard to the crossover operator's action. The subpopulations are adequately connected for exploiting this multiresolution in a gradual way. In the dynamic distributed GA with directed migration [9], the population is divided into subpopulations, but there still exists a central monitor, which observe the performance of each subpopulation and adjust their size accordingly after certain generations. The gendered GA [10] divides population in male and female subpopulations. The selection strategy selects male on competitive fitness and female on cooperative fitness basis. A population of GAs is altered by the four userdefined plans in the evolution process. These are selection, generation, replacement and update plans. The population diversity versus selection pressure problem has been tackled, considering both the parent selection and the replacement plans of steadystate GA (SSGA)[11][12]. In the sexual selection scheme based GAs, an individual in the population is identified as male and female. But to our knowledge in GAs, no strategy (except random) for male and female identification is proposed. Methods proposed for artificial niche formation uses sharing, crowding, or other modifications to the selection or replacement process. These methods introduce one or more parameters such as the sharing radius, in fitness sharing or the crowding factor in crowding. These parameters cannot be set easily without prior knowledge of the fitness landscape. The interspecies migration and mating is proposed in many algorithms, which are uncommon in nature. In this paper, we have proposed Genetic Algorithm with Species and Sexual Selection (GAS3). GAS3 is based on the facts that 1. Nature generally differentiates the individuals of an organism into more than one class. 2. In nature, organisms are living in a group. Formation of groups (i.e. species) takes place based on requirements. 3. In nature, sexually reproducing organisms do not mate indiscriminately. 4. In nature, species migrate to regroup for survival. GAS3 uses sex determination method (SDM) to determine the sex (male or female) of members in population. Each female member is considered as a niche in the population and the species formation takes place around these niches. Species formation is based on Euclidean distance between female and male members. Each species contains one female member and zero or more male members. All species gets equal chances to produce offspring using PCCO or mutation operator. The sexual selection strategy selects female and required number of male members, from species to perform recombination operation. After a certain generation the performance of the species is evaluated. If species is not performing well, then the merging to the nearby species takes place. The parent centric selfadaptive multiparent recombination operators are used to explore the search space. The species formation, merging and sexual selection technique helps to exploit a search space. This paper is organized as follows: section 2 introduces multiparent, parentcentric recombination operators MPX and MLX. Section 3 presents the basic framework of GAS3. This section also covers discussion on SDM, species formation scheme, sexual selection strategy and merging of species. The section 4 covers the issues related to experimentation methodology like algorithm, test problems. Section 5 elaborates the discussion on empirical results of proposed algorithm over unimodal and multimodal test functions. This Section also gives comparison of GAS3 with other realcoded genetic algorithm and evolutionary strategy proposed in literature. Finally, we draw some conclusions in Section 6. II. ParentCentric Crossover Operators PCCOs assign more probability for creating offspring in neighborhood of the female parent than anywhere in the search space. The neighborhoodbased crossover operators used in RCGA are based on uniform, polynomial, triangular or lognormal probability distribution. The ranges of these probability distributions depend on the distance among the genes of the female parent and the genes of the male parents. PCCOs have two important features [5]: 1. PCCOs behave like a mutation operator. PCCOs generate solutions that are close to the female parent. In this way, they may be seen as a special type of mutation. Hence most of the RCGA models based on PCCOs do not use additional mutation operators. The operation of PCCOs may become particularly promising when they are applied to highly fit individuals. 2. PCCOs are the selfadaptive crossover operators. PCCOs define a probability distribution of offspring solutions based on some measure of distance among the parent solutions. Depending upon the current level of diversity in the population they may favor the production of additional diversity (divergence) or the refinement of the solutions (convergence). This behavior is achieved without using an external adaptive mechanism. The performance of RCGA on a particular problem strongly determined by the degree of exploration and exploitation associated with the crossover operator being applied. The degree of exploration and exploitation can be controlled by using a proper value of distribution index of probability distribution used by them Multiparent recombination operator combines the features of more than two parents to generate offspring. A family of parent centric multiparent recombination operator includes parentcentric recombination operator (PCX) [11], multiparent polynomial distribution recombination operator (MPX) and multiparent lognormal distribution recombination operator (MLX) [13]. A. MPX and MLX operators MPX is a multiparent extension of the simulated binary crossover (SBX) operator. MLX is a multiparent extension of the simulated binary crossover with lognormal distribution (SBXl) operator. A prototype algorithm for MPX or MLX operator is as follows: a) From the population select the best parent (female parent) and other ([mu]1) random solutions (male parents). The participation of genes or variables in the offspring generation process depends on the crossover probability. If crossover probability ([p.sub.c]) is 0.5 then only 50% out of n variables, undergo recombination. [mu] is the number of participating parents in recombination operation. b) For each gene (i=1n) undergo recombination. Execute the following steps i) Choose [[mu].sub.i] randomly from the interval [0, 1]. ii) Using polynomial or lognormal probability distribution function, find the ordinate [[beta].sub.i] so that the area under the probability curve from 0 to bi is equal to the chosen random number [u.sub.i]. [eta] is a probability distribution index. Compute [[beta].sub.i] for MPX [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (1) Or Compute [[beta].sub.i] for MLX using [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (2) Where z ~ N (0, 1) is standard normal variable. iii) Calculate D = ([[mu].summation over (k = 1)] ([[mu].summation over (j = 1)] [x.sup.j.sub.i]  [x.sup.j.sub.i])/[mu])/[mu] (3) iv) Generate two genes around the gene of female parent (say [x.sub.1]) using [y.sub.i] = [x.sup.1.sub.i] [+ or ] ([[beta].sub.i] * D) (4) It is shown that the MPX operator is more exploitative in nature and the exploitation range decreases with increase in eta. It is also shown [13] that the MLX is more explorative in nature i.e. it is capable to generate genes in the wider range around the parent gene. Its exploration range increases with increase in [eta]. Also it is also observed that the probability of creating genes near the parent gene is almost zero in MLX. III. Genetic Algorithm with Species and Sexual Selection (GAS3) GAS3 is a distributed quasi steadystate genetic algorithm with species and sexual selection scheme. Each iteration generates offspring in each species and updates subpopulation. There is a generation gap but not as wide as in generational GAs that makes GAS3 quasi steady state GA. The pseudocode for GAS3 is as follows 1. Create initial population 2. Use sex determination method to determine the sex of an individual 3. Species evolution phase creates many species around niches 4. Repeat { 4.1 For certain number of evolution with each species in population do { 4.1.1 Selection Plan: Choose one female parent and [mu] male parents from species S (the set M). 4.1.2 Generation Plan: Create the offspring set C from M. 4.1.3 Replacement Plan: Combine solutions in C and M to form set R. Arrange members in R according to their fitness. 4.1.4 Update Plan: if one of the offspring is better than the female parent then replace that female parent with offspring. Otherwise compare offspring with male members and use replace worst strategy for updating. 4.1.5 Increment the performance count of species if offspring replaces female parent. } 4.2 Examine the performance of each species and merge species. } Until (termination condition) This is a generalized framework for GAS3, where one can use his own sex determination method, species evolution scheme, four plans for evolution and scheme for merging of species. A. Sex Determination Method (SDM) Nature generally classifies individuals of an organism, into more than one group. The sexual differentiation is a typical example, where the individual generally belongs to either male or female group. The prevalence of this form of differentiation indicates an associated advantage, which appears to be in terms of cooperation between two dissimilar individuals, who can at the same time specialize in their own fields [2]. Unlike the natural genetics in GAs, the sex of an individual in population is not known. The sex identification method determines the sex of an individual in the initial population. Bandyopadhyay et al. [14] developed GA with chromosome differentiation that distinguishes chromosomes in two categories (M and F). The two populations are generated in such a way that the hamming distance between them is maximized. A crossover takes place between species from different categories. Goh et al. [15] used random selection mechanism for SDM. Garcia et al. [5] proposed female male differentiation method where group of female consists of [N.sub.F] best individuals in population and group of male consists of NM best individuals in population ([N.sub.F]<N and [N.sub.M]<N, N is the population size). In addition, it should be ensured that either [N.sub.F]=N or [N.sub.M]=N is fulfilled. Hence individual in population is either female or male, or both. The method proposed here gives equal chances to all members in initial population to produce offspring. If an individual produces better offspring, then its performance (or fertility) count is incremented. After certain generation of evolution, the performance count of each member is examined. The individuals, who performed better than the average performance count, are treated, as female members and rest of the individuals are male members. The fertility (more fertile is a female) is the criterion used for sex identification. Number of chances (equal for all members) given to each individual to reproduce offspring is a mechanism to handle selection pressure in SDM. The method is outline as follows: Let N is population size. Let R refers to the parameter responsible for setting selection pressure (S) in SDM. 1. S=N/R 2. For i= 1 to S do For j=1 to N do a. Take [j.sup.th] member and select four members randomly form population. b. Perform recombination operation to produce offspring. c. If offspring is better than [j.sup.th] member then it will replace [j.sup.th] member in population and also increments performance count of [j.sup.th] member by one. 3. For i=1 to N do If (fertility count of [i.sup.th] member > average fertility count) then [i.sup.th] Member is female Else [i.sup.th] Member is male Every member in population gets S number of chances to prove its fertility by producing offspring. High value of S (i.e. R is low) gives more chances to an individual to produce offspring. This put a more pressure on the individual to prove its fertility and makes SDM more exploitative. Low value of S makes SDM mild. SDM is deterministic in nature and each female represent an elite solution in the population. B. Species evolution phase The specialization permitted by sexual differentiation is carried further in nature through species and niche exploitation. A niche is an organism's job or role in an environment, and a species is a class of organism with the common characteristics. Each female member is considered as a niche in population and its job is to form the species around it. In the proposed algorithm, species formation is based on Euclidean distance between female and male members. Each species contains one female member and zero or more male members. The proximity is the measure used to quantify the degree of similarity between members. A low value of the proximity between two members means these members are similar. The subpopulation formation algorithm is described as follows: 1. Population P of N members is divided into subpopulations S[P.sub.1], S[P.sub.2] ... S[P.sub.f], where f is number of female members in P. Each suppopulation contains one female member. 2. For each male member in P do Find the nearest female by calculating Euclidean distance between male and each female 3. The male members are added to the subpopulation related to the nearest female. Distributed Quasi SteadyState Genetic Algorithm 159 The time complexity of this algorithm is O ([f.sup.*](Nf)). Many species are constructed dynamically using distancebased clustering algorithm. This method permits us to create clusters of varying size and shape without any parameters. C. Sexual Selection Scheme Incestprevention technique and assortative mating plan are restricted mating strategies. In the work [16], a new selection scheme inspired by the animal mating behavior is proposed. This inspiration causes a new idea to apply dissimilar measurement to the pair of individual. The member with a higher fitness value has more chance to select as first mate. The second mate is selected by consideration of another feature, which can be depended on the first partner (this process is called seduction). Subsequently, in the work [17], the chance to be selected as the second partner is affected from the combination of the fitness value and the difference from the first partner with predefined weights of these two values. Since, the mating procedure depends on the difference in each pair of individual; it can maintain the population diversity in an indirect way. Lozano et al. [6] proposed the uniform fertility selection scheme for female parent and negative assortative mating for the selection of male parent. In gendered GA [10], selection of males based on competitive fitness and female is selected cooperative fitness. In the work [15], male and female populations are formed by selecting members randomly. For each female member in female population mating male is decided by playing a tournament between two members selected from male population randomly. It is observed that the interspecies mating tends to generate low performance offspring. Taking into account that, the species in different ecological niches don't compete for the same resources but evolve independently of each other. However, it is possible to generate fruitful offspring in species by maintaining some selection pressure, when similar individuals do mate with one another. In GAS3, we restricted mating in species only and no interspecies mating is allowed. The male members are selected randomly from subpopulation and mate with the female member of the same subpopulation. If the species do not contain any male member, then the female undergo mutation operation instead of recombination operation. D. Merging of Subpopulations The distributed paradigm enables the searching to be in progress simultaneously in more than one direction, and prevent best fitting individuals to dominate their species. In distributed GAs, migration mechanism exchanges individuals between subpopulations, thus allowing new diversity to be injected into converging subpopulations. For a constant number of generations, these subpopulations evolve independently, evaluating their respective individuals and breeding new ones. At the end of these generations, a central monitor compares the performance of all these subpopulations. The subpopulations isolated for a certain time keeps the diversity of the population high. After migration new promising areas can be discovered by crossing over. Merging of species that converge on the same niche will have the effect that niches with a bigger basin of attraction will be populated by the species with more members. But this mechanism also guarantees, that if an algorithm is converged there exists at most one species per niche. This enables an algorithm to identify global/local optima directly, by returning the best individual of each species. The clustered based niching method (CBN) for evolutionary algorithm [18], splits the subpopulations for dynamic specialization and merge the species to allow one subpopulation per niche. The distributed algorithm with migration and/or merging permits each subpopulation to change their size in response its performance. The better species are encouraged and poorer ones are marginalized Merging of two or more similar species set a synergy, in which hybridization of species may produce better offspring. GAS3 evaluates performance of each species after certain number of generations and the species not performing well are merged into nearest species (similar in phenotype). Phenotype similarity between species is calculated by measuring the Euclidean distance between female of the species not performing well and other female members in population. The agebased strategy can also use to reduce gravity of marginalization i.e. young species may get some chances to survive. Merging of species wipe out its separate existence in the population. Thus its male and female members are become male members in merged species. The duration (number of evolution) is a key feature in merging. If duration is short then species may not get sufficient chance to prove its performance and loss of such species may prevent algorithm to reach to the true optimum. The high value of duration gives nonperforming species unnecessary chance to produce offspring that leads to more number of function evaluations. E. Replacement Plan The fitness value of the evenly produced offspring is compared with the fitness value of its parents in order to decide whether or not the evenly produced offspring is accepted as a member of the next generation. The offspring is accepted as a candidate for the further evolutionary process if and only if the reproduction operator was able to produce an offspring that could outperform the fitness of its parents. This strategy guarantees that evolution is presumed mainly with crossover results that were able to mix the properties of their parents in an advantageous way. Hence, via these means we are in a position to attack one of the reasons for a premature convergence, namely the loss of relevant genetic information due to improper crossover operation. Furthermore, this strategy has proven to act as a precise mechanism for selfadaptive selection pressure steering [7]. An offspring is better than the parents, if it surpasses the fitness of the parent in mating pool. In update plan, it replaces the parent whose fitness is just less than offspring. IV. Experimental Setup GAS3 is a generalized model; hence one can use his own sex determination method, species evolution scheme, four plans for evolution and scheme for merging of species. For the experimentation, fertile female scheme is used for SDM. Different values of R test effect of selection pressure on performance of the algorithm. Explorative recombination operator MLX (with [eta] = 4 is used with five parents ([mu]=5) to generate two offspring. MLX explores wide range of search space in the beginning. Proximity based species evolution scheme has constructed, the species around female parents. The parents, selected by sexual selection scheme undergo recombination or mutation operation. The exploitative recombination operator MPX (with [eta]=1) is used with the male parents selected randomly from species ([mu]<5) and merging is performed after ([N.sup.*]N/R) number of evolution. Any good search algorithm must explore a large search space in the beginning and the search should then narrow down as it converges to the solution. To support this property explorative operator MLX is used in SDM and exploitative operator MPX is used in further evolution. 50 independent runs are executed for all possible combination of parameters R, N and [p.sub.c]. Other parameters in GA are set as given in Table 1. A. Test functions The minimization experiments have been performed on unconstrained unimodal and multimodal functions with or without epistasis among nvariables as shown in Table 2. Using skewed initialization these functions are evaluated for global minima at 0. V. Experimental Results and discussion The experimental results of GAS3 with test function show that, its performance on unimodal and multimodal functions strongly depends on value of R. It is observed that, for unimodal functions as the value of R increases, number of function evaluations (FES) decreases, and for multimodal functions as the value of R increases, FES also increases. GAS3 has performed better, with unimodal functions for high value of R and with multimodal function for low value of R. Since the parameter R plays important role in SDM and merging of species of the algorithm. The low value of R means the population members gets more chance to prove its fertility to become a female member. This creates a high selection pressure that results into welldefined niches in population to solve multimodal functions efficiently. Also the low value of R lengthens the duration (i.e. number of evolutions) to perform the merging, helps the species to prove their survival by exploring/exploiting search space. The high value of R sets a low selection pressure and narrow down the duration of merging that helps in solving unimodal functions. Table 3 shows performance of GAS3 on multimodal functions against R. Table 4 shows performance of GAS3 on unimodal functions against R. The characteristic parameter R allows GAS3 to design two different kinds of specialization algorithms. GAS3 with R=10 (UGAS3) is capable to solve unimodal functions very accurately. GAS3 with R=1 (MGAS3) is capable to solve multimodal functions very efficiently and reliably. The disruptiveness of chromosome depends upon the number of genes changed due to the recombination operation. This disruptiveness on the onehand leads to more diverse exploration that can prevent a premature convergence, but on the other hand, it slows down the convergence speed at the same time. From empirical results it is observed that [p.sub.c]=0.3 or 0.4 is suitable for multimodal function optimization and [p.sub.c]= 0.4 or 0.5 is suitable for unimodal function optimization. The choice of population size has a strong interacting effect on the results. When the population size is too small for the complexity of a particular search space, it lacks the information capacity to provide accurate sampling. However, a larger population results in better solutions but the GA must be run for a greater number of generations. With smaller populations, more disruptive crossover operators are likely to yield better results because they help to overcome the limited information capacity of smaller population. However, with the larger population, providing sufficient sampling accuracy, less disruptive crossover operators are more likely to work better. GAS3 with high value of R, moderated [p.sub.c] and a small population size has shown better results on unimodal test functions. The test result of UGAS3 with pc =0.5 and MGAS3 with [p.sub.c] =0.3, on test functions against different population size is shown in Table 5 and 6. It is observed that the small population size failed to achieve 100% success in solving some of the test functions. Also for most of the functions, increase in population size increases the AFES. Hence, we have selected N=100 for further experimentations. Table 7 displays test result of UGAS3 and MGAS3 on test functions. UGAS3 achieved almost 100% success in solving all unimodal test functions. [f.sub.Ros] is a continuous, nonseparable and unimodal function, with the optimum located in a steep parabolic valley with a flat bottom. UGAS3 struck to strong local minima at 3.98662 in 2 runs out of 50. MGAS3 achieved almost 100% success in solving all multimodal test functions. Garcia et al. [5] proposed Female and Male Differentiation (FMD) method. The Uniform Fertility Selection (UFS) is used to select a female parent and the Negative Assortative Mating (NAM) is to select a male parent. The parent centric crossover operator is used to generate offspring from the selected parent. They proposed LocalRCGA to solve unimodal functions accurately and GlobalRCGA to offer reliable solution in solving multimodal functions. Finally, they proposed hybridization technique to put together above two specialization algorithms. GL25 is a hybrid model that runs GlobalRCGA during the 25% of the available evolution and then it performs LocalRCGA. For experimentation, stopping criterion is maximum of [10.sup.5] FES. The performance comparison of UGAS3, MGAS3 with LocalRCGA, GlobalRCGA and GL25 is shown in table 8. MGAS3 and GlobalRCGA are particularly designed to solve multimodal problems. It is observed that MGAS3 has outperformed GlobalRCGA in almost all functions. LocalRCGA has shown better performance than UGAS3 in solving unimodal test functions. MGAS3 performed better than GL25 in solving [f.sub.rast] and [f.sub.grie]. MGAS3 has solved unimodal function except [f.sub.ros], upto accepted level of precision. We have compared the performance MGAS3 with G3MHX [19] and NAMUFSPBX0.8 [6] algorithms. The results of NAM, UFS & PBX based algorithm are taken from literature. Table 9 shows that MGAS3 performed better than both the algorithms in solving [f.sub.rast] and [f.sub.grie]. The Griewangk function has a product term that introduces strong interdependence among the variables. The optima of the Griewangk function are regularly distributed. It is considered as one the difficult multimodal problem to solve. The remarkable achievement of MGAS3 is it has reached to global minima of this function where other algorithms failed to do it. VI. Conclusions This paper presented genetic algorithm with species and sexual selection (GAS3), a basic framework for distributed quasi steadystate RCGA. The major contribution of this study is the introduction of Sex Determination Method (SDM), speciesformation (clustering) scheme without parameters and speciesmerging scheme. SDM is based on fertile female strategy, to identify sex of an individual in the population. A cluster around each female solution is formed in the species formation scheme using distancebased clustering algorithm. The species migration is a common method used in distributed algorithm for diversity preservation. The proposed speciesmerging scheme sets a synergy in which hybridization of species may produce better offspring and inject diversity into population. The explorative recombination operator, MLX is used to explore a wide range of search space in the beginning and exploitative recombination operator; MPX is used in the later stages. We have proposed two different kinds of specialization algorithms, based on characteristic parameter R. GAS3 with R=10 (UGAS3) is capable in solving unimodal functions very accurately. GAS3 with R=1 (MGAS3) is capable in solving multimodal functions very efficiently and reliably. The test result of UGAS3 has shown that it achieved almost 100% success in solving unimodal test functions. The test result of MGAS3 has shown that it achieved almost 100% success in solving multimodal test functions. We have compared performance of UGAS3 and MGAS3 with recent RCGA. We have proposed MGAS3 as a robust GA that is capable to solve a wide range of unimodal and multimodal problems, very efficiently. GAS3 is a generalized model; hence one can use his own sex determination method, species evolution scheme, four plans for evolution and scheme for merging of species. In extended study we are intended to work on: 1. Design of adaptive population size algorithm, 2. Design of selfadaptive mechanism to adjust the value of parameter R, 3. We have used random selection scheme for selecting male parents for recombination operation, deterministic selection method may offer some selection pressure, 4. Age of species may be considered as another parameter while merging species, 5. Use of selfadaptive mechanism to select recombination operator to generate offspring during evolution. References [1] C. Darwin, "The origin of the species", London: Murray, 1859. [2] D. E. Goldberg, "Genetic Algorithms in Search, Optimization and Machine Learning", Pearson Education Asia, 1989. [3] K. Deb, "MultiObjective Optimization using Evolutionary Algorithms", John Wiley & Sons, New York, 2001. [4] F. Herrera, M. Lozano and A.M. Sanchez, "A taxonomy for the crossover operator for realcoded genetic algorithms. An experimental study", International Journal of Intelligent Systems, 18(3): 309338, 2003. [5] C. Garcia and M. Lozano, "Chromosome Differentiation for the Application of ParentCentric RealParameter Crossover Operators", Technical report, DECSAI, E.T.S. Ingenieria Informatica University of Granada 2005. [6] M. Lozano and F. Herrera, "Diversification techniques as a way to improve the performance of realparameter crossover operators: the case of the parentcentric BLX", Submitted for publication, 2004. [7] S. Wagner and M. Affenzeller, "SexualGA: GenderSpecific Selection for Genetic Algorithm", Proceedings of the 9th World MultiConference on Systemics, Cybernetics and Informatics (WMSCI), vol. 4, pp. 7681, 2005. [8] F. Herrera and M. Lozano, "Gradual Distributed RealCoded Genetic Algorithms", IEEE Transactions On Evolutionary Computation, Vol. 4, No. 1,pp. 4363, 2000. [9] W. Yi, Q. Liu and Y. He, "Dynamic Distributed Genetic Algorithm", IEEE Congress on Evolutionary Computation 2000, San Diego, CA, USA, pp. 11321136, July 2000. [10] J. SanchezVelazco and J. A. Bullinaria, "A Gendered Selection Strategies in Genetic Algorithms for Optimization", In: J.M. Rossiter & T.P. Martin (Eds), Proceedings of the UK Workshop on Computational Intelligence: UKCI2003, 217223. Bristol, UK: University of Bristol, 2003. [11] K. Deb, A. Anand, and D. Joshi, "A computationally efficient evolutionary algorithm for real parameter optimization", Evolutionary Computation Journal 10(4): 371395, 2002. [12] P. J. Ballester and J. N. Carter, "An Effective RealParameter Genetic Algorithm with Parent Centric Normal Crossover for Multimodal Optimisation", In proceedings of the Genetic and Evolutionary Computation Conference, Springer, LNCS 3102, pp. 901913, 2004. [13] M. M. Raghuwanshi and O. G. Kakde, "Multiparent Recombination operator with Polynomial or Lognormal Distribution for Real Coded Genetic Algorithm" 2nd Indian International Conference on Artificial Intelligence (IICAI), pp. 32743290, 2005. [14] S. Bandyopadhyay, S. K. Pal and U. Maulik, "Incorporating chromosome differentiation in genetic algorithms", Information Sciences 104: 293319, 1998. [15] K. S. Goh, A. Lim and B. Rodrigues, "Sexual selection for genetic algorithms", Artificial Intelligence Reviews 19: 123152, 2003. [16] E. Ronald, "When Selection Meets Seduction", Proc. 6th Int. Conf. Genetic Algorithms, pp. 167173, 1995. [17] K. Matsui, "New Selection Method to Improve the Population Diversity in Genetic Algorithms", Proc. IEEE Int. Conf. Systems, Man, and Cybernetics, pp. 625630, 1999. [18] F. Streichert, G. Stein, H. Ulmer and A. Zell, "A Clustering Based Niching EA for Multimodal Search Spaces", Evolution Artificielle 6th International Conference (EA 2003), Marseille, France, Proceedings pp. 169180, October 2730, 2003. [19] M.M. Raghuwanshi and O.G. Kakde, "Multiparent Recombination Operators with Multiple Probability Distributions for Real Coded Genetic Algorithm", 10th online world conference on soft computing in industrial application (WSC10), 2005. M.M. Raghuwanshi (1) and O.G. Kakde (2) (1) RCERT, Chandrapur. (M.S.), India. m_raghuwanshi@rediffmail.com (2) VNIT, Nagpur. (M.S.), India. ogkakde@vnitnagpur.ac.in Author Biographies M.M. Raghuwanshi received M. Tech. (Computer Sc. &DP) degree from Indian Institute of Technology, Kharagpur in 1991. He is pursuing Ph.D. from VNIT, Nagpur under the guidance of Prof. O.G. Kakde. He is an Assistant Professor in the Department of Computer Technology at RCERT, Chandrapur (INDIA). His research interests include Realcoded Genetic Algorithms and Programming languages. O.G. Kakde received the M. Tech. degree in Computer Science in 1988 from Indian Institute of Technology Mumbai, and the Ph.D. degree in 2004, from Nagpur University INDIA. He is Professor of Computer Scienc, and Head of the Department of Electronics and Computer Science Engg., Visvesvaraya National Institute of Technology (deemed university) Nagpur, INDIA. Table 1. GA setup used for experimentation Parameter Values Population size (N) 50,75,100,150,200 Crossover probability 0.3  0.8 in step of 0.1 parameter ([p.sub.c]) R (Related to selection 1  10 in step of 1 pressure) Stopping criteria Maximum [10.sup.6] function evaluations or an objective value of [10.sup.10] Results average over 50 independent runs Parameters for performance 1. Number of function evaluation for evaluation best run and worst run 2. Average number of function evaluation (AFES) 3. Best fitness, Average fitness and Worst fitness 4. Number of runs converged to global minima Initialization of variables Skewed initialization within [10, 5] Number of children ([lambda]) 2 Table 2. Test functions Function Name Function Sphere [f.sub.sph ere] = [[summation].sup.n.sub.i=1] [x.sup.2.sub.i] Tablet [f.sub.tablet] = [10.sup.6][x.sup.2.sub.1] + [[summation].sup.n.sub.i=2][.sup.2.sub.i] Cigar [f.sub.cigar] = [x.sup.2.sub.1] + [[summation].sup.n.sub.i=2][10.sup.6] [x.sup.2.sub.i] Ellipsoidal [f.sub.elp] (x) = [n.summation over (i=1)] [ix.sup.2.sub.i] Schwefel [f.sub.sch] (x) = [n.summation over (i=1)] [([i.summation over (j=1)] [x.sub.j]).sup.2] Rosenbrock [f.sub.ros] (x) = [n  1.summation over (i=1)] [(100 ([x.sup.2.sub.i]  [x.sub.i + 1]).sup.2] + ([x.sub.i  1]).sup.2] Rastrigin [f.sub.rast (x) = 10 n + [n.summation over (i=1] ([x.sup.2.sub.i]  10 cos(2 [pi] [x.sub.i])) Scaled Rastrigin [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] Skew Rastrigin [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] Griewangk [f.sub.gri] = 1/4000 [n.summation over (i=1)] [x.sup.2.sub.i]  [[product].sup.n.sub.i=1] cos([x.sub.i]/[square root of i]) + 1 Ackley [f.sub.ack](x) = 20 x exp(0.2 x [square root of (1/n [n.summation over (i=1)] [x.sup.2.sub.i]) exp(1/n [n.summation over (i=1)] cos([2.0.sup.*] [3.14].sup.*][x.sub.i]))+20+[e.sup.1] Bohachevsky [f.sub.Bohachevaky] (x)=[[summation] .sup.n1.sub.i=1] ([x.sup.2.sub.i]+2 [x.sup.2.sub.i+1] 0.3 cos(3[pi] [x.sub.i]) 0.4 cos(4[pi] [x.sub.i+1])+0.7) TwoAxes [f.sub.two ax] = [[summation].sup.[n/2].sub.i=1] [10.sup.6] [x.sup.2.sub.i] + [[summation].sup.n.sub.i=[n/2]] [x.sup.2.sub.i] Table 3. Performance of GAS3 on multimodal functions against R (with [p.sub.c] =0.3 and N=100) R [f.sub.rast] [f.sub.gri] [f.sub.ack] AFES Success AFES Success AFES Success 1 187978 100.00% 46323.2 100.00% 62702.8 100.00% 2 238721 95.56% 52318.8 97.78% 38410.6 100.00% 3 336292 82.22% 93745.5 93.33% 30351.6 100.00% 4 354303 82.22% 65795.4 95.56% 27768.5 100.00% 5 383453 77.78% 23049.2 100.00% 22949.6 100.00% 6 624075 55.56% 193446 82.22% 62592.5 97.78% 7 606035 53.33% 56333.2 95.56% 24987.2 100.00% 8 602072 53.33% 236330 77.78% 42287.6 97.78% 9 548431 53.33% 171609 84.44% 28569 100.00% 10 594357 51.11% 200258 82.22% 62186.3 95.56% Table 4. Performance of GAS3 on unimodal functions against R (with [p.sub.c] =0.5 and N=100) R [f.sub.elp] [f.sub.sch] [f.sub.ros] AFES Success AFES Success AFES Success 1 37936.1 100.00% 84279.9 100.00% 914960 37.78% 2 22810 100.00% 72139 100.00% 827883 62.22% 3 16860.6 100.00% 80689.4 100.00% 688279 86.67% 4 15473.5 100.00% 56446.3 100.00% 659736 80.00% 5 14136.1 100.00% 53149.3 100.00% 599986 93.33% 6 11668.8 100.00% 49047.1 100.00% 571940 88.89% 7 10866.6 100.00% 50131.8 100.00% 536157 86.67% 8 7825.8 100.00% 36070.6 100.00% 508573 93.33% 9 8672 100.00% 55152.8 100.00% 564036 77.78% 10 7331.84 100.00% 36570.7 100.00% 434632 93.33% Table 5. Performance of UGAS3 on unimodal functions against N N [f.sub.elp] [f.sub.sch] [f.sub.ros] AFES Success AFES Success AFES Success 50 5158.13 100.00% 44060.9 100.00% 401162 86.67% 75 7101.64 100.00% 55176.6 100.00% 541917 66.67% 100 7331.84 100.00% 36570.7 100.00% 434632 93.33% 150 15853.6 100.00% 58657.4 100.00% 608751 91.11% 200 25023.3 100.00% 82566.2 100.00% 856712 48.89% Table 6. Performance of MGAS3 on multimodal functions against N N [f.sub.rast] [f.sub.gri] [f.sub.ack] AFES Success AFES Success AFES Success 50 374398 71.11% 38604.7 97.78% 22308.9 100.00% 75 229172 91.11% 30346.1 100.00% 41447.2 100.00% 100 187978 100.00% 46323.2 100.00% 62702.8 100.00% 150 224996 100.00% 87217 100.00% 118166 100.00% 200 322114 100.00% 138785 100.00% 183287 100.00% Table 7. Test results of GAS3 on unimodal and multimodal test functions No Of Function Evaluations Fitness Function Best Run Avg. Run Worst Run Best UGAS3 [f.sub.elp] 4071 7331.84 19546 2.57E11 [f.sub.sch] 17029 36570.7 137041 4.68E11 [f.sub.sphere] 3427 7786.53 16154 4.53E11 [f.sub.cigar] 3758 11630.8 25248 5.15E11 [f.sub.tablet] 4305 13251.4 26751 6.73E11 [f.sub.twoAxes] 7735 14523.9 46451 4.94E11 [f.sub.ros] 195748 434632 1000002 9.90E11 MGAS3 [f.sub.rast] 68125 187978 412180 1.18E11 [f.sub.rastScaled] 59384 145779 294441 5.91E12 [f.sub.rastSkewed] 62895 216585 1000002 4.43E12 [f.sub.ack] 54738 62702.8 70121 5.92E11 [f.sub.gri] 40376 46323.2 49366 3.78E11 [f.sub.bohachevsky] 42828 50335.9 54937 3.85E11 Fitness Function Average Worst Success UGAS3 [f.sub.elp] 7.43E11 9.97E11 100.00% [f.sub.sch] 8.62E11 9.97E11 100.00% [f.sub.sphere] 8.84E11 9.98E11 100.00% [f.sub.cigar] 8.46E11 9.96E11 100.00% [f.sub.tablet] 8.75E11 9.86E11 100.00% [f.sub.twoAxes] 8.76E11 9.93E11 100.00% [f.sub.ros] 0.0886 3.98662 93.33% MGAS3 [f.sub.rast] 7.48E11 9.98E11 100.00% [f.sub.rastScaled] 6.72E11 9.98E11 100.00% [f.sub.rastSkewed] 0.04422 0.99495 95.56% [f.sub.ack] 8.96E11 9.99E11 100.00% [f.sub.gri] 8.30E11 1.00E10 100.00% [f.sub.bohachevsky] 8.28E11 9.99E11 100.00% Table 8. Comparison of GAS3 with GL25 Algorithm UGAS3 LocalRCGA MGAS3 Fitness Fitness Average Functions Best Average Fitness Best [f.sub.sphere] 0 5.03E51 9.98E187 8.02E49 [f.sub.sch] 1.11E86 0.58967 1.74E09 4.44E11 [f.sub.ros] 0.00081 5.43726 1.56 22.0982 [f.sub.rast] 0 33.2557 290.00 0 [f.sub.gri] 0 0.004262 0.0127 0 Algorithm MGAS3 GlobalRCGA GL25 Fitness Average Average Functions Average Fitness Fitness [f.sub.sphere] 2.66E32 2.95E18 3.17E147 [f.sub.sch] 0.002221 31.2 1.61E07 [f.sub.ros] 23.0984 19.1 7.61E01 [f.sub.rast] 3.10518 19.2 3.30 [f.sub.gri] 0 4.93E04 2.22E17 Table 9. Comparison of MGAS3 with G3MHX and NAMUFSPBX0.8 algorithm PBX0.8 algorithm Operator [f.sub.elp] [f.sub.sch] [f.sub.ros.] MGAS3 2.66E32 0.00418 23.098 G3MHX(.5,5,70:30) 1.63E114 5.00E23 3.904 NAMUFSPBX0.8 1.44E81 6.00E08 14.7 Operator [f.sub.rast] [f.sub.grie.] MGAS3 3.10518 0.0 G3MHX(.5,5,70:30) 3.85569 0.0424 NAMUFSPBX0.8 30.8 0.0068 

Reader Opinion