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

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



prev             next


(c) Marek Obitko, 1998
Bulgarian translation (c) Todor Balabanov
- Terms of use