Printer Friendly
The Free Library
23,403,340 articles and books


Distributed quasi steady-state 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 steady-state real-coded 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 Parent-centric 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 multi-modal test functions. It got success in solving wide range of problems. Its performance is also compared with the other real-coded genetic algorithms.

Keywords: real-coded genetic algorithms, parent-centric 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.). Co-evolution 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 real-coded GAs (RCGAs), chromosome is a real-parameter decision-variable 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 parent-centric 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 non-random mating in GAs, refers to the incest-prevention 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 sub-populations and let these sub-populations evolve separately. A migration mechanism exchanges individuals between subpopulations, allowing the new diversity to be injected into converging subpopulations. The gradual distributed RCGA (GD-RCGA) [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 multi-resolution with regard to the crossover operator's action. The subpopulations are adequately connected for exploiting this multi-resolution in a gradual way. In the dynamic distributed GA with directed migration [9], the population is divided into sub-populations, but there still exists a central monitor, which observe the performance of each sub-population and adjust their size accordingly after certain generations. The gendered GA [10] divides population in male and female sub-populations. The selection strategy selects male on competitive fitness and female on co-operative fitness basis.

A population of GAs is altered by the four user-defined 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 steady-state 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 inter-species 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 self-adaptive multi-parent 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 multi-parent, parent-centric 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 multi-modal test functions. This Section also gives comparison of GAS3 with other real-coded genetic algorithm and evolutionary strategy proposed in literature. Finally, we draw some conclusions in Section 6.

II. Parent-Centric Crossover Operators

PCCOs assign more probability for creating offspring in neighborhood of the female parent than anywhere in the search space. The neighborhood-based 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 self-adaptive 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

Multi-parent recombination operator combines the features of more than two parents to generate offspring. A family of parent centric multi-parent recombination operator includes parent-centric recombination operator (PCX) [11], multi-parent polynomial distribution recombination operator (MPX) and multi-parent lognormal distribution recombination operator (MLX) [13].

A. MPX and MLX operators

MPX is a multi-parent extension of the simulated binary crossover (SBX) operator. MLX is a multi-parent extension of the simulated binary crossover with lognormal distribution (SBX-l) 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=1-n) 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 steady-state 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 pseudo-code 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 sub-population 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 sup-population 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 sub-population related to the nearest female.

Distributed Quasi Steady-State Genetic Algorithm 159 The time complexity of this algorithm is O ([f.sup.*](N-f)). Many species are constructed dynamically using distance-based clustering algorithm. This method permits us to create clusters of varying size and shape without any parameters.

C. Sexual Selection Scheme

Incest-prevention 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 co-operative 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 inter-species 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 inter-species mating is allowed. The male members are selected randomly from sub-population and mate with the female member of the same sub-population. If the species do not contain any male member, then the female undergo mutation operation instead of recombination operation.

D. Merging of Sub-populations

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 sub-populations 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 sub-populations for dynamic specialization and merge the species to allow one subpopulation per niche. The distributed algorithm with migration and/or merging permits each sub-population 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 age-based 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 non-performing 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 self-adaptive 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 multi-modal functions with or without epistasis among n-variables 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 multi-modal 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 multi-modal functions as the value of R increases, FES also increases. GAS3 has performed better, with unimodal functions for high value of R and with multi-modal 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 well-defined niches in population to solve multi-modal 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 (U-GAS3) is capable to solve unimodal functions very accurately. GAS3 with R=1 (M-GAS3) is capable to solve multi-modal 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 one-hand 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 multi-modal 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 U-GAS3 with pc =0.5 and M-GAS3 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 U-GAS3 and M-GAS3 on test functions. U-GAS3 achieved almost 100% success in solving all unimodal test functions. [f.sub.Ros] is a continuous, non-separable and unimodal function, with the optimum located in a steep parabolic valley with a flat bottom. U-GAS3 struck to strong local minima at 3.98662 in 2 runs out of 50. M-GAS3 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 Local-RCGA to solve unimodal functions accurately and Global-RCGA to offer reliable solution in solving multimodal functions. Finally, they proposed hybridization technique to put together above two specialization algorithms. GL-25 is a hybrid model that runs Global-RCGA during the 25% of the available evolution and then it performs Local-RCGA. For experimentation, stopping criterion is maximum of [10.sup.5] FES. The performance comparison of U-GAS3, M-GAS3 with Local-RCGA, Global-RCGA and GL-25 is shown in table 8. M-GAS3 and Global-RCGA are particularly designed to solve multimodal problems. It is observed that M-GAS3 has outperformed Global-RCGA in almost all functions. Local-RCGA has shown better performance than U-GAS3 in solving uni-modal test functions. M-GAS3 performed better than GL-25 in solving [f.sub.rast] and [f.sub.grie]. M-GAS3 has solved unimodal function except [f.sub.ros], upto accepted level of precision.

We have compared the performance M-GAS3 with G3-MHX [19] and NAM-UFS-PBX-0.8 [6] algorithms. The results of NAM, UFS & PBX based algorithm are taken from literature. Table 9 shows that M-GAS3 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 multi-modal problem to solve. The remarkable achievement of M-GAS3 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 steady-state RCGA. The major contribution of this study is the introduction of Sex Determination Method (SDM), species-formation (clustering) scheme without parameters and species-merging 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 distance-based clustering algorithm. The species migration is a common method used in distributed algorithm for diversity preservation. The proposed species-merging 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 (U-GAS3) is capable in solving unimodal functions very accurately. GAS3 with R=1 (M-GAS3) is capable in solving multi-modal functions very efficiently and reliably. The test result of U-GAS3 has shown that it achieved almost 100% success in solving unimodal test functions. The test result of M-GAS3 has shown that it achieved almost 100% success in solving multi-modal test functions. We have compared performance of U-GAS3 and M-GAS3 with recent RCGA. We have proposed M-GAS3 as a robust GA that is capable to solve a wide range of unimodal and multi-modal 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 self-adaptive 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 self-adaptive 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, "Multi-Objective 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 real-coded genetic algorithms. An experimental study", International Journal of Intelligent Systems, 18(3): 309-338, 2003.

[5] C. Garcia and M. Lozano, "Chromosome Differentiation for the Application of Parent-Centric Real-Parameter 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 real-parameter crossover operators: the case of the parent-centric BLX", Submitted for publication, 2004.

[7] S. Wagner and M. Affenzeller, "SexualGA: Gender-Specific Selection for Genetic Algorithm", Proceedings of the 9th World Multi-Conference on Systemics, Cybernetics and Informatics (WMSCI), vol. 4, pp. 76-81, 2005.

[8] F. Herrera and M. Lozano, "Gradual Distributed Real-Coded Genetic Algorithms", IEEE Transactions On Evolutionary Computation, Vol. 4, No. 1,pp. 43-63, 2000.

[9] W. Yi, Q. Liu and Y. He, "Dynamic Distributed Genetic Algorithm", IEEE Congress on Evolutionary Computation 2000, San Diego, CA, USA, pp. 1132-1136, July 2000.

[10] J. Sanchez-Velazco 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: UKCI-2003, 217-223. 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): 371-395, 2002.

[12] P. J. Ballester and J. N. Carter, "An Effective Real-Parameter Genetic Algorithm with Parent Centric Normal Crossover for Multimodal Optimisation", In proceedings of the Genetic and Evolutionary Computation Conference, Springer, LNCS 3102, pp. 901-913, 2004.

[13] M. M. Raghuwanshi and O. G. Kakde, "Multi-parent Recombination operator with Polynomial or Lognormal Distribution for Real Coded Genetic Algorithm" 2nd Indian International Conference on Artificial Intelligence (IICAI), pp. 3274-3290, 2005.

[14] S. Bandyopadhyay, S. K. Pal and U. Maulik, "Incorporating chromosome differentiation in genetic algorithms", Information Sciences 104: 293-319, 1998.

[15] K. S. Goh, A. Lim and B. Rodrigues, "Sexual selection for genetic algorithms", Artificial Intelligence Reviews 19: 123-152, 2003.

[16] E. Ronald, "When Selection Meets Seduction", Proc. 6th Int. Conf. Genetic Algorithms, pp. 167-173, 1995.

[17] K. Matsui, "New Selection Method to Improve the Population Diversity in Genetic Algorithms", Proc. IEEE Int. Conf. Systems, Man, and Cybernetics, pp. 625-630, 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. 169-180, October 27-30, 2003.

[19] M.M. Raghuwanshi and O.G. Kakde, "Multi-parent Recombination Operators with Multiple Probability Distributions for Real Coded Genetic Algorithm", 10th on-line 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 Real-coded 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.n-1.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)
Two-Axes [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 multi-modal 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 uni-modal 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 U-GAS3 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 M-GAS3 on multi-modal 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 multi-modal test
functions

 No Of Function Evaluations Fitness

Function Best Run Avg. Run Worst Run Best

 U-GAS3
[f.sub.elp] 4071 7331.84 19546 2.57E-11
[f.sub.sch] 17029 36570.7 137041 4.68E-11
[f.sub.sphere] 3427 7786.53 16154 4.53E-11
[f.sub.cigar] 3758 11630.8 25248 5.15E-11
[f.sub.tablet] 4305 13251.4 26751 6.73E-11
[f.sub.twoAxes] 7735 14523.9 46451 4.94E-11
[f.sub.ros] 195748 434632 1000002 9.90E-11
 M-GAS3
[f.sub.rast] 68125 187978 412180 1.18E-11
[f.sub.rastScaled] 59384 145779 294441 5.91E-12
[f.sub.rastSkewed] 62895 216585 1000002 4.43E-12
[f.sub.ack] 54738 62702.8 70121 5.92E-11
[f.sub.gri] 40376 46323.2 49366 3.78E-11
[f.sub.bohachevsky] 42828 50335.9 54937 3.85E-11

 Fitness

Function Average Worst Success

 U-GAS3
[f.sub.elp] 7.43E-11 9.97E-11 100.00%
[f.sub.sch] 8.62E-11 9.97E-11 100.00%
[f.sub.sphere] 8.84E-11 9.98E-11 100.00%
[f.sub.cigar] 8.46E-11 9.96E-11 100.00%
[f.sub.tablet] 8.75E-11 9.86E-11 100.00%
[f.sub.twoAxes] 8.76E-11 9.93E-11 100.00%
[f.sub.ros] 0.0886 3.98662 93.33%
 M-GAS3
[f.sub.rast] 7.48E-11 9.98E-11 100.00%
[f.sub.rastScaled] 6.72E-11 9.98E-11 100.00%
[f.sub.rastSkewed] 0.04422 0.99495 95.56%
[f.sub.ack] 8.96E-11 9.99E-11 100.00%
[f.sub.gri] 8.30E-11 1.00E-10 100.00%
[f.sub.bohachevsky] 8.28E-11 9.99E-11 100.00%

Table 8. Comparison of GAS3 with GL-25

Algorithm U-GAS3 Local-RCGA M-GAS3

 Fitness Fitness

 Average
Functions Best Average Fitness Best

[f.sub.sphere] 0 5.03E-51 9.98E-187 8.02E-49
[f.sub.sch] 1.11E-86 0.58967 1.74E-09 4.44E-11
[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 M-GAS3 Global-RCGA GL-25

 Fitness

 Average Average
Functions Average Fitness Fitness

[f.sub.sphere] 2.66E-32 2.95E-18 3.17E-147
[f.sub.sch] 0.002221 31.2 1.61E-07
[f.sub.ros] 23.0984 19.1 7.61E-01
[f.sub.rast] 3.10518 19.2 3.30
[f.sub.gri] 0 4.93E-04 2.22E-17

Table 9. Comparison of M-GAS3 with G3-MHX and NAM-UFS-PBX-0.8
algorithm PBX-0.8 algorithm

Operator [f.sub.elp] [f.sub.sch] [f.sub.ros.]

M-GAS3 2.66E-32 0.00418 23.098
G3-MHX(.5,5,70:30) 1.63E-114 5.00E-23 3.904
NAM-UFS-PBX-0.8 1.44E-81 6.00E-08 14.7

Operator [f.sub.rast] [f.sub.grie.]

M-GAS3 3.10518 0.0
G3-MHX(.5,5,70:30) 3.85569 0.0424
NAM-UFS-PBX-0.8 30.8 0.0068
COPYRIGHT 2007 Research India Publications
No portion of this article can be reproduced without the express written permission from the copyright holder.
Copyright 2007 Gale, Cengage Learning. All rights reserved.

 Reader Opinion

Title:

Comment:



 

Article Details
Printer friendly Cite/link Email Feedback
Author:Raghuwanshi, M.M.; Kakde, O.G.
Publication:International Journal of Computational Intelligence Research
Geographic Code:9INDI
Date:Apr 1, 2007
Words:7361
Previous Article:Economic power dispatch of power system with pollution control using multiobjective ant colony optimization.
Next Article:An ensemble of cooperative genetic algorithms as an intelligent search tool.
Topics:



Related Articles
Could recombination drive evolution?
Breeding programs.
Ecologic niche modeling and potential reservoirs for Chagas disease, Mexico. (Research).
Of mice and gen. (The Beat).
Ecologic and geographic distribution of filovirus disease.
Using inverse Neural Networks for HIV adaptive control.
An ensemble of cooperative genetic algorithms as an intelligent search tool.
New research on forest ecology.
Ecosystems as superorganisms: the neglected evolutionary implications.

Terms of use | Copyright © 2014 Farlex, Inc. | Feedback | For webmasters