Distributed Quasi Steady-State Genetic Algorithm

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 (mal

International Journal of Computational Intelligence Research. ISSN 0973-1873 Vol.3, No.2 (2007), pp. 155-164 © Research India Publications doc.xuehai.net

Distributed Quasi Steady-State Genetic Algorithm

with Niches and Species

M.M. Raghuwanshi1 and O.G. Kakde2

1

RCERT, Chandrapur. (M.S.), India. m_raghuwanshi@rediffmail.com 2

VNIT, Nagpur. (M.S.), India. ogkakde@vnitnagpur.ac.in

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

第1页下一页