Biomedical Engineering Reference
In-Depth Information
4
Theoretical Analysis of Jumping
Gene Opera
tions
4.1 OverviewofSchemaModels
4.1.1 Schema
A.schema.ξ.is.a.subset.of.the.search.space.in.which.all.the.strings.share.a.par-
ticular.set.of.defined.values..In.the.context.of.a.genetic.algorithm.(GA).that.
operates.with.binary.strings,.a.schema.is.a.string.of.symbols.taken.from.the.
set.of.three.symbols.{0,.1,.*},.where.0.and.1.are.called.definite.bits.or.actual.
bits,. and. the. wild. character. *. is. interpreted. as. a. don't-care. bit. that. can. be.
either.0.or.1..With.the.introduction.of.the.don't-care.bit,.a.single.schema.can.
represent.several.bit.strings..A.similar.concept.is.also.applicable.for.represen-
tations.in.other.bases.
Take.a.simple.example.of.three.bits;.a.schema.**1.represents.four.strings:.
001,.011,.101,.111..This.indicates.a.two-dimensional.(2D).surface,.as.shown.
in.
Figure 4.1
,.
while. ***. represents. all. the. possible. solutions. or. the. three-
dimensional.(3D).cube.
To.study.a.scheme,.two.of.its.attributes.are.of.importance..One.is.called.the.
order.of.a.schema.
o
(ξ),.representing.the.number.of.actual.bits.in.the.schema..
The. next. is. the. deining. length. of. a. schema,. denoted.
L
d
( )
,. deined. as. the.
distance. between. the. leftmost. and. the. rightmost. actual. bits.. For. example,.
o
(*0.*.*.10) = 3.and.
ξ
L
d
(*0 * *10)
=
4
..Further.explanation.of.schema.can.be.found.
in.References.8.and.9.
4.1.2 Holland's Model
The.most.well-known.mathematical.model.based.on.a.schema.must.be.the.
Holland. schema. theorem. [9].. It. is. a. typical. approximate. schema. theorem,.
having.the.same.level.of.coarse.graining.on.both.sides.of.the.model.equation..
It.predicts.the.expected.number.of.strings.belonging.to.a.schema.in.a.popu-
lation.being.evolved.from.one.generation.to.the.next,.under.the.operations.
53
Search WWH ::
Custom Search