Theoretical Analysis of Jumping Gene Operations - Multiobjective Optimization Methodology: A Jumping Gene Approach - page 54

B 2

010

110

011 111

B 1

000

100

001

101

B 3

**1

Figure 4.1
An.example.of.a.three-bit.schemata..(From.Tang,.K..S.,.Yin,.R..J.,.Kwong,.S.,.Ng,.K..T.,.Man,.K..F.,.
A.theoretical.development.and.analysis.of.jumping.gene.genetic.algorithm,. IEEETransactions
onIndustrialInformatics ,.7(3),.2011,.408-418.)

of.selection,.one-point.crossover,.and.bit.mutation..The.schema.growth.equa-
tion.is.summarized.as.follows:

L
L

( )
1

ξ

( )

o ξ d

E m t [ ( , 1)] N p ( , ) (1 t p ) 1 p

ξ + ≥ ⋅ ξ ⋅ − ⋅ − . (4.1) m x

−

.

where. p m .and. p x .are.the.operational.probabilities.of.mutation.and.crossover,.
respectively;. L . is. the. length. of. the. chromosome;. N is. the. population. size;.
ξ [ ( , 1)] . is. the. expected. number. of. chromosomes. matching. with. the.

schema.ξ.at.generation. (

E m t +

1 ;.and. (

)

)

p t

t + ξ , .is.the.probability.of.selecting.the.

schema.ξ.as.parent.
The.term.

( )

p m o

ξ

(1 − )

.gives.the.probability.that.a.schema.survives.after.muta-

L
L

( )
1

d ξ
− . expresses. the. case. that. crossover. is. performed. at. the.
crossover.point.in.between.the.actual.bits..It.thus.approximates.the.destruc-
tive.rate.of.a.schema.due.to.crossover.
Assuming.that.the.fitness.proportionate.selection.is.used.for.selecting.par-
ents,.it.can.be.derived.that

tion.. The. term. p x

m t f ( , ) ( , )

( )

ξ ξ t

. (4.2)

p ( , ) ξ t =

N f t

.

( , ) .is.the.number.of.chromosomes.belonging.to.schema.ξ.at.gen-
er ation t ,.

m t

where.

f ( , ) ).is.the.average.fitness.of.the.chromosomes.belonging.to.ξ,.and. ξ t

( )

f t .is.the.average.fitness.of.the.population.
The.inequality.(4.1).can.only.provide.a.lower.bound.on.the.expected.num-
ber.of.chromosomes.that.belong.to.a.specific.schema.in.the.next.generation;.
hence.it.is.an.approximation..It.is.also.pessimistic. in.the.sense.that.it.only.
considers.the.destruction.of.a.schema,.neglecting.the.possible.reconstruction.
of.the.schema,.which.certainly.plays.an.equally.important.role.as.destruction.
during.evolution..Due.to.this.shortcoming,.the.usefulness.of.schemata.and.
the.schema.theorem.has.been.widely.criticized.[1,6,7]..The.main.criticism.is.