< prev

Page 1Page 2Page 3Page 4Page 5Page 6Page 7Page 8Page 9Page 10Page 11Page 12

Page 4 of 12
next >

Majalah Ilmiah UNIKOM

Vol.8, No. 1

4

H a l a m a n

produce a new population. Each succes-

sive population is called a new genera-

tion.

 Parents and Children. To create the next

generation, the genetic algorithm selects

certain individuals in the current popula-

tion, called parents, and uses them to

create individuals in the next generation,

called children. Typically, the algorithm is

more likely to select parents that have

better fitness values.

The genetic algorithm uses three main

types of rules at each step to create the next

generation from the current population.

 Selection rules select the individuals,

called parents, that contribute to the

population at the next generation.

 Crossover rules combine two parents to

form children for the next generation.

 Mutation rules apply random changes to

individual parents to form children.

The algorithm creates crossover children

by combining pairs of parents in the current

population. At each coordinate of the child

vector, the default crossover function ran-

domly selects an entry, or gene, at the same

coordinate from one of the two parents and

assigns it to the child. The algorithm creates

mutation children by randomly changing the

genes of individual parents. By default, the

algorithm adds a random vector from a

Gaussian distribution to the parent.

The genetic algorithm uses the following

conditions to determine when to stop:

 Generations — The algorithm stops when

the number of generations reaches the

value of Generations.

 Time limit — The algorithm stops after

running for an amount of time in sec-

onds equal to Time limit.

 Fitness limit — The algorithm stops when

the value of the fitness function for the

best point in the current population is

less than or equal to Fitness limit.

Stall generations — The algorithm stops

when the weighted average change in

the fitness function value over Stall gen-

erations is less than Function tolerance.

 Stall time limit — The algorithm stops if

there is no improvement in the objective

function during an interval of time in sec-

onds equal to Stall time limit.

 Function Tolerance — The algorithm runs

until the weighted average change in the

fitness function value over Stall genera-

tions is less than Function tolerance.

 Nonlinear constraint tolerance — The

Nonlinear constraint tolerance is not

used as stopping criterion. It is used to

determine the feasibility with respect to

nonlinear constraints.

normalized path repre-

sentation

is, a list (1,2,3,4) means the tour going from

city 1 to city 2, 3, 4, and back to city 1. With

the traditional path representation, different

lists such as (4,1,2,3), (3,4,1,2), and

(2,3,4,1) all represent the same tour as

(1,2,3,4).

Simple GA have their own problems. Vary-

ing the amount of disruption of good subso-

lutions by mutation and crossover operators

presents a tradeoff between diversity and

performance (exploration and exploitation).

GA using selection alone can not generate

solutions outside the population. Crossover

and mutation generate new solutions, but

with certain limitations. Crossing nearly

identical string yields offspring similar to the

parent strings. Consequently, crossover can

not reintroduce diversity. Mutation, on the

other hand, can generate the full solution

space, but may take an excessively long

time to yield a desirable solution.

In addition, it is not easy to regulate a GA

convergence. Tuning global parameters

such as population size, mutation probability

and crossover probability, has been the

most recommended technique for control-

ling premature convergence in the GA. A

generally effective method for setting pa-

rameters has not yet been demonstrated.

Ideal parameters are likely problem-

dependent.

Muhammad Aria