6533b822fe1ef96bd127ced8
RESEARCH PRODUCT
A genetic system based on simulated crossover of sequences of two-bit genes
Marco Carpentierisubject
Discrete mathematicseducation.field_of_studyGeneral Computer SciencePopulation sizeCrossoverPopulationState (functional analysis)Upper and lower boundsQuantitative Biology::GenomicsTheoretical Computer ScienceMarginal distribution genetic algorithmsChromosome (genetic algorithm)Genetic modelGenetic algorithmMax-cut problemeducationAlgorithmComputer Science(all)Mathematicsdescription
AbstractWe introduce a genetic model based on simulated crossover of fixed sequences of two-bit genes. Results are(1)a lower bound on population size is exhibited such that a transition takes the stochastic finite population genetic system near the next state of the deterministic infinite population genetic system (provided both begin in the same state);(2)states and dynamics of the deterministic infinite population genetic system are derived for arbitrary (finite) fitness functions (expressed in terms of multivariate polynomials);(3)in the case of quadratic fitness defined by weight matrices with m nonnull entries it is shown that each state transition can be implemented in time O(m+l), where l is the chromosome length;(4)the genetic algorithm (implementing the proposed infinite population system) is experimentally compared with the infinite population genetic algorithm with bit-based simulated crossover for the max-cut problem; the results show that the extension to sequences of genes with four alleles is useful to improve performances.
| year | journal | country | edition | language |
|---|---|---|---|---|
| 2006-12-01 | Theoretical Computer Science |