Селекция (генетичен оператор)

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

В най-простия си вид, процедурата по селекция в генетичните алгоритми може да се реализира по следния начин:

Фитнес функцията на всеки индивид (геном, решение) от текущата популация се оценява. Съвкупността от всички стойности на фитнес функцията за индивидите, се нормализира. (Нормализацията означава всяка отделна фитнес стойност на индивид да се раздели на сбора от стойностите на всички индивиди, така че нормализиран този сбор се приравнява на 1, а всяка от отделните фитнес стойности се нормализира до число в интервала [0, 1].)
Популацията от индивиди се сортира по намаляващ ред на техните фитнес стойности.
Изчисляват се акумулираните нормализирани фитнес стойности (акумулираната фитнес стойност на индивид е сборът от неговата собствена фитнес стойност плюс фитнес стойностите на сортираните преди него индивиди; за последно сортирания индивид акумулираната фитнес стойност трябва да бъде точно 1).
На случаен принцип се избира число R между 0 и 1.
Избраният индивид е първият, чиято акумулирана нормализирана фитнес функция е по-голяма от R.

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

Видове селекция

Ако процедурата бъде повторена, докато се изберат достатъчно на брой индивиди от популацията, този метод на селекция се нарича „пропорционална на фитнеса селекция“ (fitness proportionate selection, FPS) или „селекция на принципа на рулетката“ (roulette-wheel selection, RWS) по аналогия с въртенето на рулетка, която спира на един определен „показалец“ и се взима съответстващата срещу „показалеца“ стойност. Ако вместо да се върти много пъти рулетката и всеки път да се взима стойността срещу единия „показалец“, има много на брой равноотстоящи „показалци“ на рулетката, и тя се завърта еднократно, то този метод на селекция се нарича стохастично универсално семплиране (stochastic universal sampling, SUS).

Повтарящото се избиране на най-добрия индивид от случайно подбрано подмножества от индивидите в популацията се нарича „турнирна селекция“ (tournament selection). Избирането на най-добрата половина, третина или друга пропорционална част от индивидите от популацията се нарича „селекция с очистване“ (truncation selection).

Има и други процедури по селекция, които не отчитат всички индивиди като годни за селекция, а само онези, чиято фитнес стойност надвишава определена (произволна) прагова константа. Други алгоритми избират от ограничен набор индивиди, където само определен процент от индивидите са допустими на база фитнес стойностите им.

Запазването без промяна на най-добрите индивиди от едно поколение в следващото, се нарича „елитизъм“ или „елитарна селекция“.

Вижте също

Външни препратки

Тази страница частично или изцяло представлява превод на страницата Selection (genetic algorithm) в Уикипедия на английски. Оригиналният текст, както и този превод, са защитени от Лиценза „Криейтив Комънс – Признание – Споделяне на споделеното“, а за съдържание, създадено преди юни 2009 година – от Лиценза за свободна документация на ГНУ. Прегледайте историята на редакциите на оригиналната страница, както и на преводната страница, за да видите списъка на съавторите.

ВАЖНО: Този шаблон се отнася единствено до авторските права върху съдържанието на статията. Добавянето му не отменя изискването да се посочват конкретни източници на твърденията, които да бъдат благонадеждни.