Regional Controllability with Cellular Automata Models - Cellular Automata - page 360

2.4￿Cellular￿Automata￿in￿Systems￿Theory
CA's￿ models￿ have￿ been￿ extensively￿ used￿ as￿ a￿modelling￿ tool￿ to￿ approximate
nonlinear￿discrete￿and￿continuous￿dynamical￿systems￿in￿a￿wide￿range￿of￿appli-
cations.￿However￿the￿inverse￿problem￿of￿determining￿the￿CA￿that￿satisfies￿some
specified￿constraints￿has￿received￿a￿little￿attention.￿Identification￿is￿one￿of￿these
inverse￿problem￿which￿was￿thoroughly￿studied￿for￿CA's￿models￿by￿Adamatzky
[1].￿It￿is￿understood￿as￿extracting￿an￿adequate￿CA￿model￿from￿a￿given￿set￿of
consecutive￿configurations￿(snapshots)￿of￿a￿completely￿unknown￿automaton￿in
order￿to￿produce￿the￿same￿observed￿evolution.￿Few￿works￿dealing￿with￿struc-
tural￿identification￿or￿parameter￿estimation￿problem￿of￿CA's￿models￿have￿been
developed￿in￿[9].￿Another￿interesting￿inverse￿problem￿is￿to￿find￿an￿appropriate
CA￿ rule￿capable￿of￿steering￿a￿given￿system￿from￿an￿initial￿state￿to￿a￿desired
configuration￿during￿a￿time￿horizon￿ T .￿In￿a￿previous￿work￿[8],￿we￿considered￿an
exemple￿of￿controllability￿problem￿from￿a￿numerical￿point￿of￿view￿using￿genetic
programming￿techniques￿in￿the￿case￿of￿additive￿CA's.￿The￿obtained￿results￿are
quite￿promising￿and￿stimulate￿further￿research￿in￿this￿direction.
3￿Genetic￿Algorithms
Evolutionary￿computation￿techniques￿have￿received￿in￿the￿last￿two￿decades￿in-
creasing￿attention￿regarding￿their￿potential￿as￿optimization￿tools￿for￿engineering
problems￿[10, 11, 14].￿The￿different￿developed￿methodologies￿are￿focussed￿on￿the
possibility￿of￿solving￿problems￿by￿evolving￿an￿initially￿random￿population￿of￿can-
didate￿solutions,￿through￿the￿application￿of￿operators￿inspired￿by￿natural￿selec-
tion.￿Genetic￿algorithms￿constitue￿a￿very￿important￿evolutionary￿method￿which
has￿been￿successfully￿implemented￿for￿various￿problems￿including￿optimization,
machine￿learning,￿operation￿research,￿immune￿systems,￿ecology,￿ population￿ge-
netics￿and￿so￿on￿[15].￿A￿standard￿genetic￿algorithm￿proceeds￿as￿follows:
1.￿ Generating￿a￿random￿initial￿population￿of￿individuals￿in￿a￿space￿of￿potential
solutions￿called￿the￿search￿space.￿Each￿individual￿is￿represented￿by￿a￿finite
string￿of￿symbols￿(known￿as￿the￿genome)￿to￿encode￿a￿possible￿solution￿in
the￿search￿space.
2.￿ At￿generation￿ g (evolutionary￿step),￿individuals￿of￿population￿ P ( g )￿are￿de-
coded￿and￿evaluated￿according￿to￿a￿given￿fitness￿function￿(quality￿criterion).
3.￿ Individuals￿of￿the￿next￿generation￿ P ( g +1)￿are￿selected￿according￿to￿their
computed￿ fitness￿ values￿ and￿ new￿ individuals￿are￿generated￿by￿ genetically
inspired￿operators.￿The￿most￿important￿ and￿well￿known￿genetic￿operators
are￿:
(a)￿ Crossover￿ which￿ operates￿on￿two￿selected￿individuals￿(parents)￿by￿ ex-
changing￿parts￿of￿their￿genomes￿(encodings)￿and￿produces￿two￿new￿in-
dividuals￿called￿offspring.￿It￿is￿performed￿with￿probability￿ p cross which
defines the crossover rate.
(b) Mutation which is carried out by randomly sampling new points in the
search space, with some probability p mut . It is introduced to prevent
premature convergence to local optima.
4.￿ The￿next￿generation￿is￿then￿in￿turn￿evaluated.