V. Operators of GA

둜듡

댿�`밒귺깑긕깏긛궻둜뾴귩귒궲귦궔귡귝궎궸갂 뚴뜵궴벺멢빾댶궼댿�`밒귺깑긕깏긛�궳귖궯궴귖뢣뾴궶븫빁궳궥갃 긬긲긅�[�}깛긚궼갂롥궸궞궻괧궰궻긆긻깒�[�^궸귝궯궲뎓떯궠귢귏궥갃 뚴뜵궴벺멢빾댶귩귖궯궴먣뼻궥귡멟궸갂먺륡뫬궸듫궥귡궋궘궰궔궻륃뺪귩�^궑궫궋궴럙궋귏궥갃

As you can see from the genetic algorithm outline, the crossover and mutation are the most important part of the genetic algorithm. The performance is influenced mainly by these two operators. Before we can explain more about crossover and mutation, some information about chromosomes will be given.

먺륡뫬궻댠뜂돸(Encoding of a Chromosome)

먺륡뫬궼궋귣궋귣궶뺴�@궳갂궩귢궕�\뙸궥귡됶궸듫궥귡륃뺪귩듵귪궳궋귏궥갃 귖궯궴귖귝궘럊귦귢귡댠뜂돸궻뺴�@궼긫귽긥깏�[빒럻쀱궳궥갃 궩궻먺륡뫬궼궞궻귝궎궸뙥궑귏궥갃

먺륡뫬 1	1101100100110110
먺륡뫬 2	1101111000011110

The chromosome should in some way contain information about solution which it represents. The most used way of encoding is a binary string. The chromosome then could look like this:

Chromosome 1	1101100100110110
Chromosome 2	1101111000011110

궵궻먺륡뫬귖긫귽긥깏�[빒럻쀱귩괦궰귖궯궲궋귏궥갃 궞궻빒럻쀱궻뭷궻궵궻긮긞긣귖됶궻벫뮙귩�\뙸궢궲궋귏궥갃 귏궫궼갂빒럻쀱멣뫬궳괦궰궻릶귩�\귦궢귏궥갃�|궞귢궼딈�{GA applet.궳럊귦귢궲궋귏궥갃

Each chromosome has one binary string. Each bit in this string can represent some characteristic of the solution. Or the whole string can represent a number - this has been used in the basic GA applet.

귖궭귣귪갂뫜궸귖궫궘궠귪궻댠뜂돸궻뺴�@궕궇귟귏궥갃 궞귢궼됶뙂궥귊궖뽦묋궸귝귟귏궥갃 쀡궑궽갂뮳먝맢릶귘렳릶궸댠뜂돸궥귡궞궴귖궳궖귏궥궢갂룈쀱궶궵궸댠뜂돸궥귡궻귖뽴뿧궭귏궥갃

Of course, there are many other ways of encoding. This depends mainly on the solved problem. For example, one can encode directly integer or real numbers, sometimes it is useful to encode some permutations and so on.

뚴뜵

궵궻귝궎궶댠뜂돸귩궥귡궔귩뙂귕궫뚣갂뚴뜵궻롨뭝귩뙂귕귡궞궴궕궳궖귏궥갃 뚴뜵궼뿼릂궻먺륡뫬궔귞댿�`럔귩멗귂갂륷궢궋럔뫕귩띿귟귏궥갃 궞귢귩뛱궎귖궯궴귖뭁룂궶뺴�@궼갂깋깛�_�궸뚴뜵�_귩궑귞귂갂궞궻�_귏궳귩븗릂걁먺륡뫬괦걂궔귞갂궞궻�_댥�~귩뺢릂걁먺륡뫬괧걂궔귞긓긯�[궥귡궞궴궳궥갃

After we have decided what encoding we will use, we can make a step to crossover. Crossover selects genes from parent chromosomes and creates a new offspring. The simplest way how to do this is to choose randomly some crossover point and everything before this point point copy from a first parent and then everything after a crossover point copy from the second parent.

뚴뜵궼궞궻귝궎궸궶귟귏궥갃 뚴뜵�_궼 | 궳�\귦궠귢귏궥

먺륡뫬 1	11011 \| 00100110110
먺륡뫬 2	11011 \| 11000011110
럔뫕 1	11011 \| 11000011110
럔뫕 2	11011 \| 00100110110

Crossover can then look like this ( | is the crossover point):

Chromosome 1	11011 \| 00100110110
Chromosome 2	11011 \| 11000011110
Offspring 1	11011 \| 11000011110
Offspring 2	11011 \| 00100110110

뫜궸귖뚴뜵귩뛱궎뺴�@궼궇귟귏궥갃 쀡궑궽귖궯궴뫝궘궻뚴뜵�_귩멗귆궞궴궕궳궖귏궥갃 뚴뜵궼 귝귟븸랦궳갂먺륡뫬궻댠뜂돸궻뺴�@궸뷄륂궸댨뫔궢귏궥갃 벫롪궶뽦묋궸뫮궥귡벫롪궶뚴뜵궼댿�`밒귺깑긕깏긛�궻긬긲긅�[�}깛긚귩둂멠궢귏궥갃

There are other ways how to make crossover, for example we can choose more crossover points. Crossover can be rather complicated and very depends on encoding of the encoding of chromosome. Specific crossover made for a specific problem can improve performance of the genetic algorithm.

벺멢빾댶(Mutation)

뚴뜵궕뛱귦귢궫뚣궳갂벺멢빾댶궕궓궞귟귏궥갃 궞귢궼뙿뫬똒궻궥귊궲궻됶궕궕됶뙂궥귊궖뽦묋궻떿룋됶궸뿇궭뜛귪궳궢귏궎궞궴귩뻞궗귏궥갃 벺멢빾댶궼륷궢궋럔뫕궸깋깛�_�궸빾뛛귩돿궑귏궥갃 긫귽긥깏�[댠뜂돸궶귞궽갂깋깛�_�궸멗궽귢궫궋궘궰궔궻긮긞긣귩괥궔귞괦귉갂귏궫괦궔귞괥귉궴뵿�]궠궧귡궞궴궕궳궖귏궥갃 벺멢빾댶궼렅궻귝궎궸궶귟귏궥

뙰궻럔뫕 1	1101111000011110
뙰궻럔뫕 2	1101100100110110
벺멢빾댶궢궫럔뫕 1	1100111000011110
벺멢빾댶궢궫럔뫕 2	1101101100110110

After a crossover is performed, mutation take place. This is to prevent falling all solutions in population into a local optimum of solved problem. Mutation changes randomly the new offspring. For binary encoding we can switch a few randomly chosen bits from 1 to 0 or from 0 to 1. Mutation can then be following:

Original offspring 1	1101111000011110
Original offspring 2	1101100100110110
Mutated offspring 1	1100111000011110
Mutated offspring 2	1101101100110110

벺멢빾댶귖뚴뜵벏뾩댠뜂돸궻뺴�@궸댨뫔궢귏궥갃 쀡궑궽갂룈쀱귩댠뜂돸궢궫궻궳궇귢궽갂벺멢빾댶궼괧궰궻댿�`럔귩뚴듂궥귡궞궴궳뛱귦귢귏궥갃

The mutation depends on the encoding as well as the crossover. For example when we are encoding permutations, mutation could be exchanging two genes.