课件遗传算法原理英文

Graduate

School

of

Information,

Production

and

Systems,

Waseda

UniversityEvolutionary

Algorithms

andOptimization:Theory

and

itsApplicationsTsinghua

University

UniversityMarch

14

–

18,

2005Mitsuo

GenGraduate

School

of

Information,Production

&

SystemsWaseda

Universitygen@waseda.jpEvolutionary

Algorithms

andOptimization:Theory

and

its

ApplicationsSoft

Computing

Lab.2WASEDA

UNIVERSITY

,

IPSPart

1:

Evolutionary

OptimizationIntroduction

to

Genetic

AlgorithmsConstrainedOptimizationCombinatorial

OptimizationMulti-objectiveOptimizationFuzzyLogicand

FuzzyOptimizationEvolutionary

Algorithms

andOptimization:Theory

and

its

ApplicationsSoft

Computing

Lab.3WASEDA

UNIVERSITY

,

IPSPart

2:

Network

DesignNetwork

Design

ProblemsMinimum

Spanning

TreeLogistics

Network

DesignCommunication

Network

and

LANDesignEvolutionary

Algorithms

andOptimization:Theory

and

its

ApplicationsSoft

Computing

Lab.4WASEDA

UNIVERSITY

,

IPSPart3:

ManufacturingProcess

Planning

and

its

ApplicationsLocation-Allocation

ProblemsReliability

Optimization

and

DesignLayout

Design

and

Cellular

ManufacturingDesignEvolutionaryAlgorithms

andOptimization:Theory

and

its

ApplicationsSoft

Computing

Lab.5WASEDA

UNIVERSITY

,

IPSPart

4:

SchedulingMachine

Scheduling

and

Multi-processorSchedulingFlow-shop

Scheduling

andJob-shopSchedulingResource-constrained

Project

SchedulingAdvanced

Planning

and

SchedulingMultimedia

Real-time

Task

SchedulingGraduate

School

of

Information,

Production

and

Systems,

Waseda

University1.IntroductiontoGenetic

Algorithms“Genetic

Algorithms

and

Engineering

Design”“Genetic

Algorithms

and

Engineering

Design”by

Mitsuo

Gen,

Runwei

Cheng

(Contributor)List

Price:

$140.00Our

Price:

$140.00Used

Price:

$124.44Availability:

Usually

ships

within

2

to

3

daysHardcover

-

January

7,

1997:

432

pages,

John

Wiley

&

Sons,

NYAbout

the

Author：MITSUO

GEN,

PhD,

is

a

professor

in

the

Department

of

Industrial

and

Systems

Engineering

atthe

Ashikaga

Institute

of

Technology

in

Japan.

An

associate

editor

of

the

Engineering

Designand

Automation

Journal

and

Journal

of

Engineering

Valuation

&

Cost

Analysis,

he

is

also

amember

of

the

international

editorial

advisory

board

of

Computers

&

Industrial

Engineering.He

is

the

author

of

two

other

books,

Linear

Programming

Using

Turbo

C

and

GoalProgramming

Using

Turbo

C.RUNWEI

CHENG,

PhD,

is

a

visiting

associate

professor

at

the

Ashikaga

Institute

of

Technologyin

Japan

and

also

an

associate

professor

at

the

Institute

of

Systems

Engineering

at

NortheastUniversity

in

China.

Both

authors

are

internationally

known

experts

in

the

application

ofgenetic

algorithms

and

artificial

intelligence

to

the

field

of

manufacturing

systems.汪定偉・唐加福・黄敏訳：遺伝算法与工程設計，科学出版社，1999Soft

Computing

Lab.7WASEDA

UNIVERSITY

,

IPSGenetic

Algorithms

and

EngineeringDesignSoft

Computing

Lab.8WASEDA

UNIVERSITY

,

IPSBook

News,

Inc.Describes

thecurrentapplication

of

genetic

algorithms

toproblems

in

industrialengineering

and

operations

research.

Introduces

thefundamentals

ofgeneticalgorithmsand

their

use

in

solving

constrained

and

combinatorial

optimization

problems.

Then

looks

at

problems

in

specific

areas,

including

sequencing,

scheduling

and

productionplans,

transportation

and

vehicle

routing,facility

layout,

and

location

allocation.

Theexplanation

are

intuitive

rather

than

highly

technical,

and

are

supported

with

numericalexamples.

Suitable

forself-study

or

classrooms.

--

Copyright

©

1999

Book

News,

Inc.,Portland,

OR

All

rights

reservedBook

InfoProvides

a

comprehensive

surveyof

selection

strategies,

penalty

techniques,

andgenetic

operators

used

for

constrained

and

combinatorial

problems.

Shows

how

touse

genetic

algorithms

to

make

production

schedules

and

enhance

system

reliability.The

publisher,

John

Wiley

&

SonsThis

self-contained

reference

explains

genetic

algorithms,

the

probabilistic

searchtechniques

based

on

the

principles

of

biological

evolution

which

permit

engineerstoanalyze

large

numbers

of

variables.

It

addresses

this

important

advance

in

AI,

whichcan

be

used

to

better

design

and

producehigh

quality

products.

The

book

presents

thestate-of-the-art

in

this

field

as

applied

to

the

engineering

designprocess.

All

algorithmshave

beenprogrammed

inC

and

source

codes

are

available

in

the

appendix

tohelpreaderstailortheprogramstofit

theirspecific

needs.“Genetic

Algorithms

and

Engineering

Optimization”“Genetic

Algorithms

and

Engineering

Optimization”(Wiley

Series

in

Engineering

Design

and

Automation)by

Mitsuo

Gen,

Runwei

ChengList

Price:

$125.00Our

Price:

$125.00Used

Price:

$110.94Availability:

Usually

ships

within

24

hoursHardcover

-

January

2000;

512

pages,

John

Wiley

&

Sons,

NYBook

DescriptionGenetic

algorithms

are

probabilistic

search

techniques

based

on

the

principles

of

biologicalevolution.

As

abiological

organism

evolves

to

more

fully

adapt

toits

environment,a

geneticalgorithm

follows

a

path

ofanalysis

from

which

adesign

evolves,one

thatis

optimal

for

theenvironmental

constraints

placed

upon

it.

Written

by

two

internationally-known

expertsongenetic

algorithms

and

artificial

intelligence,

this

important

book

addresses

one

of

the

mostimportant

optimization

techniques

in

the

industrial

engineering/manufacturing

area,

the

useof

genetic

algorithms

to

betterdesign

and

produce

reliableproducts

of

highquality.

The

book

covers

advanced

optimization

techniques

as

applied

to

manufacturing

and

industrialengineering

processes,

focusing

on

combinatorial

and

multiple-objectiveoptimizationproblems

that

are

most

encountered

in

industry.于歆杰・周根貴訳：遺伝算法与工程優化，清華大学出版社，2004Soft

Computing

Lab.9WASEDA

UNIVERSITY

,

IPS“Genetic

Algorithms

and

Engineering

Optimization”Soft

Computing

Lab.10WASEDA

UNIVERSITY

,

IPSFrom

the

Back

CoverA

comprehensive

guide

to

a

powerful

new

analytical

tool

by

two

of

its

foremost

innovatorsThe

past

decade

has

witnessed

many

exciting

advances

in

the

use

of

genetic

algorithms(GAs)

to

solve

optimization

problems

in

everything

from

product

design

to

scheduling

andclient/server

networking.

Aided

by

GAs,

analysts

and

designers

now

routinely

evolve

solutionsto

complex

combinatorial

and

multiobjective

optimization

problems

with

an

ease

and

rapidityunthinkable

with

conventional

methods.

Despite

the

continued

growth

and

refinement

of

thispowerful

analytical

tool,

there

continues

to

be

a

lack

of

up-to-date

guides

to

contemporary

GAoptimization

principles

and

practices.

Written

by

two

of

the

world's

leading

experts

in

the

field,this

book

fills

that

gap

in

the

literature.Taking

an

intuitive

approach,

Mitsuo

Gen

and

Runwei

Cheng

employ

numerous

illustrationsand

real-world

examples

to

help

readers

gain

a

thorough

understanding

of

basic

GA

concepts-including

encoding,

adaptation,

and

genetic

optimizations-and

to

show

how

GAs

can

be

used

tosolve

an

array

of

constrained,

combinatorial,

multiobjective,

and

fuzzy

optimization

problems.Focusing

on

problems

commonly

encountered

in

industry-especially

in

manufacturing-Professors

Gen

and

Cheng

provide

in-depth

coverage

of

advanced

GA

techniques

for:Reliabilitydesign

Manufacturing

cell

design

Scheduling

Advanced

transportation

problems

Network

design

and

routingGenetic

Algorithms

and

Engineering

Optimization

is

an

indispensable

working

resource

forindustrial

engineers

and

designers,

as

well

as

systems

analysts,

operations

researchers,

andmanagement

scientists

working

in

manufacturing

and

related

industries.

It

also

makes

anexcellent

primary

or

supplementary

text

for

advanced

courses

in

industrial

engineering,management

science,

operations

research,

computer

science,

and

artificial

intelligence.1.

Introduction

of

Genetic

AlgorithmsSoft

Computing

Lab.11WASEDA

UNIVERSITY

,

IPSFoundations

of

Genetic

AlgorithmsIntroduction

of

Genetic

AlgorithmsGeneral

Structure

of

Genetic

AlgorithmsMajor

AdvantagesExample

withSimple

Genetic

AlgorithmsRepresentationInitial

PopulationEvaluationGenetic

OperatorsEncoding

IssueCoding

Space

and

Solution

SpaceSelection1.

Introduction

of

Genetic

AlgorithmsSoft

Computing

Lab.12WASEDA

UNIVERSITY

,

IPSGenetic

OperatorsConventional

OperatorsArithmetical

OperatorsDirection-based

OperatorsStochastic

OperatorsAdaptation

ofGenetic

AlgorithmsStructure

AdaptationParameters

AdaptationHybrid

Genetic

AlgorithmsAdaptive

Hybrid

GA

ApproachParameter

Control

Approach

of

GAParameter

Control

Approach

using

Fuzzy

Logic

ControllerDesign

of

aHGA

using

Conventional

Heuristics

and

FLC1.

Introduction

of

Genetic

AlgorithmsSoft

Computing

Lab.13WASEDA

UNIVERSITY

,

IPSFoundations

of

Genetic

AlgorithmsIntroduction

of

Genetic

AlgorithmsGeneral

Structure

of

Genetic

AlgorithmsMajor

AdvantagesExample

withSimple

Genetic

AlgorithmsEncoding

IssueGenetic

OperatorsAdaptation

ofGenetic

AlgorithmsHybrid

Genetic

Algorithms1.1

Introduction

of

Genetic

AlgorithmsSoft

Computing

Lab.14WASEDA

UNIVERSITY

,

IPSSince

1960s,

there

has

been

being

an

increasing

interest

in

imitating

livingbeings

to

develop

powerful

algorithms

for

NP

hard

optimization

problems.A

common

term

accepted

recently

refers

to

such

techniques

as

EvolutionaryComputation

or

Evolutionary

Optimization

methods.The

best

known

algorithms

in

this

class

include:Genetic

Algorithms

(GA),

developed

by

Dr.

Holland.Holland,

J.:

Adaptation

in

Natural

and

Artificial

Systems,

University

of

Michigan

Press,Ann

Arbor,

MI,1975;

MIT

Press,Cambridge,

MA,1992.Goldberg,

D.:

Genetic

Algorithms

in

Search,

Optimization

and

Machine

Learning,Addison-Wesley,Reading,MA,

1989.Evolution

Strategies

(ES),

developed

by

Dr.

Rechenberg

and

Dr.

Schwefel.Rechenberg,

I.:

Evolution

strategie:

Optimierung

technischer

Systeme

nachPrinzipien

der

biologischen

Evolution,

Frommann-Holzboog,

1973.Schwefel,

H.:

Evolution

and

Optimum

Seeking,

John

Wiley

&

Sons,1995.Evolutionary

Programming

(EP),

developed

by

Dr.

Fogel.Fogel,

L.

A.

Owens

&

M.

Walsh:

Artificial

Intelligence

through

Simulated

Evolution,John

Wiley&

Sons,1966.Genetic

Programming

(GP),

developed

by

Dr.

Koza. Koza,

J.

R.:

Genetic

Programming,

MIT

Press,

1992. Koza,

J.

R.:

Genetic

Programming

II,

MIT

Press,

1994.1.1

Introduction

of

Genetic

AlgorithmsThe

Genetic

Algorithms

(GA),

as

powerful

and

broadly

applicable

stochasticsearch

and

optimization

techniques,

are

perhaps

the

most

widely

known

typesof

Evolutionary

Computation

methods

today.In

past

few

years,

the

GA

community

has

turned

much

of

its

attention

to

theoptimization

problems

of

industrial

engineering,

resulting

in

a

fresh

body

ofresearch

and

applications.Goldberg,

D.:

Genetic

Algorithms

in

Search,

Optimization

and

Machine

Learning,Addison-Wesley,

Reading,MA,

1989.Fogel,

D.:

Evolutionary

Computation:

Toward

a

New

Philosophy

of

Machine

Intelligence,IEEE

Press,

Piscataway,NJ,

1995.Back,

T.:

Evolutionary

Algorithms

inTheory

andPractice,

Oxford

University

Press,

NewYork,

1996.Michalewicz,

Z.:

Genetic

Algorithm

+Data

Structures

=

Evolution

Programs.3rd

ed.,

NewYork:

Springer-Verlag,

1996.Gen,

M.

&

R.

Cheng:Genetic

Algorithms

andEngineering

Design,

John

Wiley,New

York,1997.Gen,

M.

&

R.

Cheng:Genetic

Algorithms

and

Engineering

Optimization,

John

Wiley,

NewYork,

2000.Deb,

K.:

Multi-objective

optimization

Using

Evolutionary

Algorithms,

John

Wiley,

2001.A

bibliography

on

genetic

algorithms

has

been

collected

by

Alander.Alander,J.:

Indexed

Bibliography

of

Genetic

Algorithms:

1957-1993,

Art

of

CADLtd.,Espoo,

Finland,

1994.Soft

Computing

Lab.15WASEDA

UNIVERSITY

,

IPS1.2

General

Structure

of

Genetic

AlgorithmsIn

general,

a

GA

has

five

basic

components,

assummarized

byMichalewicz.Michalewicz,

Z.:

Genetic

Algorithm

+

Data

Structures

=

EvolutionPrograms.

3rd

ed.,

New

York:

Springer-Verlag,

1996.A

genetic

representation

of

potential

solutions

to

the

problem.A

way

to

create

a

population

(an

initial

set

of

potentialsolutions).Anevaluationfunction

rating

solutions

in

terms

of

theirfitness.Genetic

operators

that

alter

the

genetic

composition

ofoffspring

(selection,

crossover,

mutation,

etc.).Parameter

valuesthat

genetic

algorithm

uses

(populationsize,probabilities

of

applying

genetic

operators,

etc.).Soft

Computing

Lab.16WASEDA

UNIVERSITY

,

IPS1.2

General

Structure

of

Genetic

AlgorithmsSoft

Computing

Lab.17WASEDA

UNIVERSITY

,

IPSGenetic

Representation

and

Initialization:The

genetic

algorithm

maintains

a

population

P(t)

of

chromosomes

orindividuals

vk(t),

k=1,

2,

…,

popSize

for

generation

t.Each

chromosome

represents

a

potential

solution

to

the

problem

at

hand.Evaluation:Each

chromosome

is

evaluated

to

give

some

measure

of

its

fitness

eval(vk).Genetic

Operators:Some

chromosomes

undergo

stochastic

transformations

by

means

of

geneticoperators

to

form

new

chromosomes,

i.e.,

offspring.There

are

two

kinds

of

transformation:Crossover,

which

creates

new

chromosomes

by

combining

parts

from

twochromosomes.Mutation,

which

creates

new

chromosomes

by

making

changes

in

a

singlechromosome.New

chromosomes,

called

offspring

C(t),

are

then

evaluated.Selection:A

new

population

is

formed

by

selecting

the

more

fit

chromosomes

from

theparent

population

and

the

offspring

population.Best

solution:After

several

generations,

the

algorithm

converges

to

the

best

chromosome,which

hopefully

represents

an

optimal

or

suboptimal

solution

to

the

problem.1.2

General

Structure

of

Genetic

AlgorithmsInitialsolutionsstart1100101010101110111011001100011100101010101110111011001011101011101010crossoverchromosomemutation11001011101011101010solutions

candidatesdecodingfitness

computationevaluationroulette

wheelselectionterminationcondition?YNbestsolutionstopnewpopulationThe

general

structure

of

genetic

algorithmsGen,

M.&

R.

Cheng:

Genetic

Algorithms

and

Engineering

Design,

John

Wiley,New

York,

1997.offspringoffspringencodingt

0

P(t)CC

(t)CM(t)P(t)

+

C(t)Soft

Computing

Lab.18WASEDA

UNIVERSITY

,

IPSSoft

Computing

Lab.

WASEDA

UNIVERSITY

,

IPS

191.2

General

Structure

of

Genetic

AlgorithmsProcedure

of

Simple

GA//

t:

generation

number//

P(t):

population

of

chromosomes//

C(t):

offspringprocedure:

Simple

GAinput:

GA

parametersoutput:

best

solutionbegint

0;initialize

P(t)

by

encoding

routine;fitness

eval(P)

by

decoding

routine;while

(not

termination

condition)

docrossover

P(t)

to

yield

C(t);mutation

P(t)

to

yield

C(t);fitness

eval(C)

by

decoding

routine;select

P(t+1)

from

P(t)

and

C(t);t

t+1;endoutput

best

solution;end1.3

Major

Advantagescomputational

steps

which

asymptoticallyconverge

to

optimal

solution.Most

of

classical

optimization

methodsgenerate

a

deterministic

sequence

ofcomputation

based

on

the

gradientorhigher

order

derivatives

of

objectivefunction.The

methods

are

applied

to

a

single

pointin

the

searchspace.The

point

is

then

improved

along

thedeepest

descending

direction

graduallythrough

iterations.This

point-to-point

approach

takes

thedanger

of

falling

in

local

optima.Conventional

Method

(point-to-point

approach)Generally,

algorithm

for

solvingoptimization

problems

is

a

sequence

ofinitial

single

pointimprovement(problem-specific)startConventional

Methodterminationcondition?YesstopNoSoft

Computing

Lab.20WASEDA

UNIVERSITY

,

IPS1.3

Major

Advantagesdirectional

search

by

maintaining

apopulation

of

potential

solutions.The

population-to-population

approachis

hopeful

to

make

the

search

escapefrom

local

optima.Population

undergoes

a

simulatedevolution:

at

each

generationtherelatively

good

solutions

arereproduced,

while

the

relatively

badsolutions

die.Genetic

algorithms

use

probabilistictransition

rules

to

select

someone

to

be

reproduced

and

someone

to

die

soas

to

guide

their

search

toward

regionsof

the

search

space

with

likelyimprovement.Genetic

Algorithm

(population-to-population

approach)Genetic

algorithms

performs

a

multipleinitial

pointinitial

point...initial

pointimprovement(problem-independent)Genetic

AlgorithmstartInitial

populationterminationcondition?YesstopNoSoft

Computing

Lab.21WASEDA

UNIVERSITY

,

IPS1.3

Major

AdvantagesRandom

Search

+

Directed

Searchmax

f

(x)s.

t. 0

£

x

£

ubFitnessf(x)global

optimumlocal

optimumlocal

optimumlocal

optimum0xx1x2x4

x5x3Search

spaceSoft

Computing

Lab.22WASEDA

UNIVERSITY

,

IPS1.3

Major

AdvantagesSoft

Computing

Lab.23WASEDA

UNIVERSITY

,

IPSExample

of

Genetic

Algorithm

for

Unconstrained

NumericalOptimization

(Michalewicz,

1996)max

f

(

x)

=

x

sin(px)

+1-1.0

£

x

£

2.01.3

Major

AdvantagesSoft

Computing

Lab.24WASEDA

UNIVERSITY

,

IPSGenetic

algorithms

have

received

considerable

attention

regarding

theirpotential

as

a

novel

optimization

technique.

There

are

three

major

advantages

when

applying

genetic

algorithms

to

optimization

problems.Genetic

algorithms

do

not

have

much

mathematical

requirements

about

theoptimization

problems.Due

to

their

evolutionary

nature,

genetic

algorithms

will

search

for

solutionswithout

regard

to

the

specific

inner

workings

of

the

problem.Genetic

algorithms

can

handleanykind

of

objective

functionsand

any

kind

ofconstraints,

i.e.,

linear

or

nonlinear,

defined

on

discrete,

continuous

or

mixedsearch

spaces.The

ergodicity

of

evolution

operators

makes

genetic

algorithms

very

effective

at

performing

global

search

(in

probability).The

traditional

approaches

perform

local

search

by

a

convergent

stepwiseprocedure,

which

compares

the

values

of

nearby

points

and

moves

to

therelative

optimal

points.Global

optima

can

be

found

only

if

the

problem

possesses

certain

convexityproperties

that

essentially

guarantee

thatany

local

optima

is

a

globaloptima.Genetic

algorithms

provide

us

a

great

flexibility

to

hybridize

with

domain

dependent

heuristics

to

make

an

efficient

implementation

for

a

specificproblem.1.

Introduction

of

Genetic

AlgorithmsSoft

Computing

Lab.25WASEDA

UNIVERSITY

,

IPSFoundations

of

Genetic

AlgorithmsExample

withSimple

Genetic

AlgorithmsRepresentationInitial

PopulationEvaluationGenetic

OperatorsEncoding

IssueGenetic

OperatorsAdaptation

ofGenetic

AlgorithmsHybrid

Genetic

Algorithms2.

Example

with

Simple

Genetic

AlgorithmsSoft

Computing

Lab.26WASEDA

UNIVERSITY

,

IPSWe

explainindetailabout

how

a

genetic

algorithm

actually

works

withasimpleexamples.We

followtheapproachof

implementation

of

genetic

algorithmsgiven

by

Michalewicz.Michalewicz,

Z.:

Genetic

Algorithm

+

Data

Structures

=

EvolutionPrograms.

3rd

ed.,

Springer-Verlag:

New

York,

1996.The

numerical

example

of

unconstrained

optimization

problemis

given

as

follows:max

f

(x1,x2)

=

21.5

+

x1·sin(4p

x1)

+x2·sin(20p

x2)s.

t.

-3.0

£

x1

£

12.14.1£

x2

£

5.82.

Example

with

Simple

Genetic

AlgorithmsSoft

Computing

Lab.27WASEDA

UNIVERSITY

,

IPSmax

f

(x1,x2)

=

21.5

+

x1·sin(4p

x1)

+

x2·sin(20p

x2)s.t.

-3.0

£

x1

£

12.14.1

£

x2

£

5.8f

=

21.5

+

x1

Sin

[

4

Pi

x1

]

+

x2

Sin

[

20

Pi

x2

];Plot3D[f,

{x1,

-3,

12.1},

{x2,

4.1,

5.8},PlotPoints

->19,AxesLabel

->

{x1,

x2,

“f(x1,

x2)”}];byMathematica

4.12.1

RepresentationBinary

String

RepresentationThe

domain

of

xjis

[aj,

bj]

and

the

required

precision

isfive placesafter

the

decimalpoint.The

precision

requirement

implies

that

the

range

of

domainofeach

variable

should

be

divided

into

at

least

(bj-

aj)·105

size

ranges.The

required

bits

(denoted

with

mj)

for

a

variable

is

calculatedas follows:The

mapping

from

a

binary

string

to

a

real

number

for

variable

xjis

completed

as

follows:5-1jjmj

jm

-12

<

(b

-

a

)·10

£

2-1Soft

Computing

Lab.28WASEDA

UNIVERSITY

,

IPS2mjj

jb

-

ax

j

=

a

j

+decimal(substring

j

)·2.1

Representation18

bitsx115bitsx2m1

=

18

bits217

<151,000

£

218,x2

:

(5.8-4.1)

·

10,000

=

17,000214

<17,000

£

215,m2

=

15

bitsprecision

requirement:

m

=

m1

+

m2

=

18

+15

=

33

bits33

bitsvj:

000001010100101001

101111011111110BinaryString

EncodingThe

precision

requirement

implies

that

the

range

of

domain

of

each

variable

should

be

divided

into

at

least

(bj-

aj)·105

size

ranges.The

required

bits

(denoted

with

mj)

for

a

variable

is

calculatedasfollows:x1

:

(12.1-(-3.0))

·

10,000

=

151,000Soft

Computing

Lab.29WASEDA

UNIVERSITY

,

IPS2.1

RepresentationSoft

Computing

Lab.30WASEDA

UNIVERSITY

,

IPSProcedure

of

Binary

String

Encodinginput:

domain

of

xj

˛[aj,

bj],

(j=1,2)output:

chromosome

vstep

1:

The

domain

of

xj

is

[aj,

bj]

and

the

required

precision

is

fiveplaces

after

the

decimal

point.step

2:The

precision

requirement

implies

that

the

range

of

domain

ofeach

variable

should

be

divided

into

at

least

(bj

-

aj

)·105

size

ranges.step

3:

The

required

bits

(denoted

with

mj)

for

a

variable

is

calculated

asfollows:2mj

-1

<

(b

-a

)·105

£

2mj

-1j

jstep

4:

A

chromosome

v

is

randomly

generated,which

has

the

number

of

genes

m,where

m

issumof

mj

(j=1,2).2.1

Representation18

bitsx115

bitsx2BinaryString

DecodingThe

mapping

from

a

binary

string

to

a

real

number

for

variable

xj

iscompleted

as

follows:33

bitsvj

:

000001010100101001

101111011111110Binary

NumberDecimal

Numberx10000010101001010015417x2101111011111110243181x =

-3.0

+5417

·

12.1-(-3.0)

218

-

1=

-2.6870692x =

4.1

+24318

·

5.8-

4.1

215

-

1=

5.361653-1Soft

Computing

Lab.31WASEDA

UNIVERSITY

,

IPS2m

jjjjjjb

-

ax

=

a

+

decimal(substring

)·-1Soft

Computing

Lab.32WASEDA

UNIVERSITY

,

IPSj

j2mjj

j

jb

-

ax

=

a

+decimal(substring

)·2.1

RepresentationProcedure

of

BinaryString

Decodinginput:

substringjoutput:

a

real

number

xjstep

1:

Convert

a

substring

(a

binary

string)

to

a

decimal

number.step

2:

The

mapping

for

var