X. Encoding

긫귽긥깏�[긄깛긓�[긢귻깛긐궸귝귡먺륡뫬궻쀡

긫귽긥깏�[긄깛긓�[긢귻깛긐궼 Binary encoding gives many possible chromosomes even with a small number of alleles. On the other hand, this encoding is often not natural for many problems and sometimes corrections must be made after crossover and/or mutation.

쀡묋: 긥긞긵긗긞긏뽦묋
뽦묋: 븸릶궻됖븿궸뫮궢궲갂궩귢궪귢묈궖궠궴뭠궕궇궫귞귢귏궥갃 긥긞긵긗긞긏궻뾢쀊궕�^궑귞귢귏궥갃 긥긞긵긗긞긏궻뭷궻됖븿궻뭠귩띍묈돸궥귡귝궎궸됖븿귩멗귂귏궥갃 궢궔궢갂긥긞긵긗긞긏궻뾢쀊귩둮뮗궥귡궞궴궼궳궖귏궧귪갃
긄깛긓�[긢귻깛긐: 둫긮긞긣궼긥긞긵긗긞긏궻뭷궻됖븿궸뫮돒궢귏궥갃

Example of chromosomes with binary encoding

Binary encoding gives many possible chromosomes even with a small number of alleles. On the other hand, this encoding is often not natural for many problems and sometimes corrections must be made after crossover and/or mutation.

Example of Problem: Knapsack problem
The problem: There are things with given value and size. The knapsack has given capacity. Select things to maximize the value of things in knapsack, but do not extend knapsack capacity.
Encoding: Each bit says, if the corresponding thing is in knapsack.

룈쀱긓�[긢귻깛긐궻쀡

Example of chromosomes with permutation encoding

룈쀱긓�[긢귻깛긐궼룈룜궸듫궥귡뽦묋궸궻귒뾎뚼궳궥갃

Permutation encoding is only useful for ordering problems. Even for this problems for some types of crossover and mutation corrections must be made to leave the chromosome consistent (i.e. have real sequence in it).

쀡묋: 룄됷긜�[깑긚�}깛뽦묋 (TSP)
뽦묋: 뱒럖궴궩귢궪귢궻뱒럖듩궻떁뿣궕�^궑귞귢궲궋귏궥갃룄됷긜�[깑긚�}깛궼�^궑귞귢궫뱒럖귩궥귊궲됷귡뷠뾴궕궇귟귏궥갃궢궔궢붯궼궇귏귟뿷궕뛆궖궳궼궇귟귏궧귪갃귖궯궴귖뿷뛱궥귡떁뿣궕뭒궋룈붥귩뭈궢귏궥갃 긓�[긤돸: 먺륡뫬궼뱒럖궻룈붥귩�\귦궢귏궥갃긜�[깑긚�}깛궼궩궻룈붥궳귏귦귟귏궥.
Example of Problem: Travelling salesman problem (TSP)
The problem: There are cities and given distances between them.Travelling salesman has to visit all of them, but he does not to travel very much. Find a sequence of cities to minimize travelled distance.
Encoding: Chromosome says order of cities, in which salesman will visit them.

Example of chromosomes with value encoding

렳릶뭠긓�[긢귻깛긐궼궇귡롰궻뽦묋궸뫮궢궲뷄륂궸뾎뚼궳궥갃 덇뺴궳갂궞궻긓�[긢귻깛긐궼뽦묋궸밙궢궫륷궢궋뚴뜵궴벺멢빾댶귩뛩궑귡뷠뾴궕궢궽궢궽궇귟귏궥갃
Value encoding is very good for some special problems. On the other hand, for this encoding is often necessary to develop some new crossover and mutation specific for the problem.

쀡묋: 긦깄�[깋깑긨긞긣깗�[긏궻뢣귒븊궚귩뭈궥
뽦묋: There is some neural network with given architecture. Find weights for inputs of neurons to train the network for wanted output.
긓�[긤돸: 먺륡뫬궻렳릶궼볺쀍궸뫮돒궥귡뢣귒귩�\뙸궢궲궋귏궥갃

---

Example of Problem: Finding weights for neural network
The problem: There is some neural network with given architecture. Find weights for inputs of neurons to train the network for wanted output.
Encoding: Real values in chromosomes represent corresponding weights for inputs.

---

뽜긓�[긢귻깛긐궻쀡

Example of chromosomes with tree encoding

뽜긓�[긤돸궼릋돸밒긵깓긐깋�궸밙궢궲궋귏궥갃 굂괿굍굊궴궋궎긵깓긐깋�뙻뚭궼궞귢궸뫮궢궲갂궢궽궢궽럊귦귢귏궥갃 궶궨궶귞궽갂궩귢궻뭷궻긵깓긐깋�궼궞궻�^귩�\뙸궢귏궥갃 귏궫듗뭁궸됶뻌궥귡궞궴궕궳궖귏궥갃 궳궥궔귞갂뚴뜵귘벺멢빾댶귩몜뫮밒궸듗뭁궸뛱궎궞궴궕궳궖귏궥갃

쀡묋: �^궑귞귢궫뭠궔귞듫릶귩뙥궰궚귡
뽦묋: 볺쀍궴뢯쀍궻뭠궕�^궑귞귢귏궥갃뽦묋궼궥귊궲궻볺쀍궸뫮궢궲띍귖쀇궋걁귌궢궋귖궻궸귖궯궴귖궭궔궋귖궻걂귩�^궑귡듫릶귩뭈궥궞궴궳궥갃
긓�[긤돸: 먺륡뫬궼뽜궳�\뙸궠귢궫듫릶궳궥갃

Tree encoding is good for evolving programs. Programing language LISP is often used to this, because programs in it are represented in this form and can be easily parsed as a tree, so the crossover and mutation can be done relatively easily.

Example of Problem: Finding a function from given values
The problem: Some input and output values are given. Task is to find a function, which will give the best (closest to wanted) output to all inputs.
Encoding: Chromosome are functions represented in a tree.