IX. Селекция


Увод

Както вече се знае от скицирането на GA, хромозомите се избират от популацията за кръстосване. Проблема е в това как да бъдат подбрани тези хромозоми. Съгласно еволюционната теория на Дарвин най-добрите т рябва да оцелеят и да създадат ново потомство. Има много методи за избор на най-добрите хромозоми, примерно селекция по кръгова рулетка, селекция на Boltzman, състезателна селекция, селекция по ранг, селекция на устойчивите състояния и някои други.

Някои от тях ще бъдат описани в тази глава.




Селекция по Кръгова Рулетка

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

Тогава топчето се хвърля и избира хромозома. Хромозома с по-голяма жизнеспособност ще бъде избирана повече пъти.

Това може да бъде симулирано чрез следния алгоритъм.

  1. [Сума] Изчислява се сумата от жизнезпособността на всички хромозоми в популацията - сума S.
  2. [Избор] Генериране на случайно число в интервала (0,S) - r.
  3. [Цикъл] Обхожда се популацията и се сумира жизнеспособностите 0 - сума s. Когато сумата s е по голяма от r, се спира и се връща хромозомата която се разглежда в момента.

Разбира се, стъпка 1 се извършва само веднъж за всяка популация.




Селекция по Ранг

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

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

На следващата фигура може да се види, как се променя ситуацията след промяна жизнеспособността при пореден номер.

Ситуацията преди подредбата (графика на жизнеспособност)

Ситуацията след подредбата (графика на поредните номера)

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




Селекция на Устойчивите-Състояние

Това не е особен метод за избор на родители. Основната идея на тази селекция е че голяма част от хромозомите би трябвало да оцелеят до следващото поколени.

GA тогава работи по следния начин. Във всяко поколение се избират няколко (добри - с висока жизнеспособност) хромозоми за създаването на новото потомство. След това няколко (лоши - с ниска жизнеспособност) хромозоми се премахват и новото потомство се пос тавя на тяхно място. Останалата част от популацията оцелява и в новото поколение.




Прехвърляне

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

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



prev             next


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