IX. Селекция

Увод

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

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



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

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

Roulette wheel selection graph

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

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

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

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



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

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

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

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

Rank-based selection before sorting

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

Rank-based selection after sorting

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

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



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

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

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



Прехвърляне

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

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

·