Information Technology Reference
In-Depth Information
algorithm is widely applied to various domains, such as optimization, machine
learning, parallel processing.
13.6.1
Major steps of genetic algorithm
In order to use genetic algorithm to solve problem, the preparation is divided into
the following four steps:
(1) Confirm the expression scheme;
(2) Confirm method to measure fitness value;
(3) Confirm parameters and variables controlling the algorithm;
(4) Confirm method to get results and criterion of how to terminate the algorithm.
In additional genetic algorithm, expression scheme is to express every
possible point in search space as a string with fixed length. Confirming
expression scheme needs to select character string's length l and alphabet's size
k. Binary bit string is usually used to express chromosome in genetic algorithm.
The measurement of fitness associates a fixed length string with a fitness value.
The main parameters that are used to control genetic algorithm include the size N
of population, the maximum generation number
M
and other parameters
including selection probability p
r
, crossover probability p
c
, mutation probability
p
c
, etc. The criterion of algorithm termination is determined by concrete
problems. Once after these preparation steps are finished, we can utilize genetic
algorithm.
Algorithm 13.3
Basic genetic algorithm
1.
Randomly generate a population which consists of fixed length strings;
2.
Iteratively the following steps on the population until selected criterion is
satisfied:
①
Calculate the fitness value for every individual in population;
②
Use the following three operators(first two operators at least) to
generate new population:
· Reproduction: reproduce the existing individual string to a new
population.
· Crossover: generate new strings by randomly choosing and
recombining two existing individual strings.
· Mutation: randomly select a gene in a string and variate this gene.
