V. Операции в GA

Преглед

Както може да се забележи от скицирането на генетичния алгоритъм, кръстосването и мутацията са най-важната част от генетичния алгоритъм. Изпълнението е повлияно основно тези две операции. Преди да се даде обяснение за к ръстосването и мутацията, ще бъде дадена някаква информация за хромозимите.

Кодиране на Хромозомите

Хромозомите трябва по някакъв начин да съдържат информация за решението което представляват. Най-използвания начин за кодиране е двоичният низ. Хромозомите тогава изглеждат по следния начин:

Хромозома 1	1101100100110110
Хромозома 2	1101111000011110

Всяка хромозома има един бинарен низ. Всеки бит в този низ може да представя някаква характеристика на решението. Или целия низ може да представя число - това бе използвано в основният GA аплет.

Разбира се, има много други начини за кодиране. Това зависи основно от проблема който се разрешава. Примерно, може да се кодира директно integer или real число, понякога е полезно да се кодира някакви пермутации, и т.н.

Кръстосване

След като се реши какво кодиране ще се използва, може да се пристъпи към кръстосване. Кръстосването избира гени от родителските хромозоми и създава ново поколение. Най-простия начин по който може да се извърши това е да се избере случайна точка на кръсто сване и всичко преди тази точка е копие от първия родите, а всичко останало след точката на кръстосване е копие на от втория родител.

Кръстосването тогава може да изглежда по следния начин ( | е точката на кръстосване):

Хромозома 1	11011 \| 00100110110
Хромозома 2	11011 \| 11000011110
Поколение 1	11011 \| 11000011110
Поколение 2	11011 \| 00100110110

Има и други начин по които да се извърши кръстосване, примерно може да се изберат повече точки на кръстосване. Кръстосването може да бъде доста усложнено и много зависи от кодирането на хромозомата. Конкретно кръстосване за конкретен проблем, може да под обри изпълнението на генетичния алгоритъм.

Мутация

След като кръстосването бъде изпълнено идва време за мутацията. Това е за предпазване всички решения в популацията да не попаднат в локален оптимум на решавания проблем. Мутацията променя случайно новото поколение. За двоично кодиране може да се "преобър нат" няколко случайно избрани бита от 1 в 0 или от 0 в 1. Мутацията тогава може да бъде следната:

Оригинално поколение 1	110 1 111000011110
Оригинално поколение 2	110110 0 1001101 1 0
Мутирало поколение 1	110 0 111000011110
Мутирало поколение 2	110110 1 1001101 1 0

Мутацията зависи от кодирането толкова силно колкото и кръстосването. Примерно когато се кодират пермутации, мутацията може да бъде размяна на два гена.