Генетика - кал алгоритъм - ТМ
Целевата функция (функция фитнес, фитнес функция)
Някои обикновено случаен начин създава множество генотипове на първоначалния населението. Те се оценяват с помощта на "фитнес функция", в резултат на което всеки генотип е свързан с определена стойност ( "фитнес"), който определя колко добре фенотипа, те описват, решава проблема.
Схема на генетичния алгоритъм
Проблемът е оформен по такъв начин, че неговото решение може да се кодира като вектор ( "генотип") гени където всеки ген може да бъде малко, няколко или друг обект. В класическите изпълнения GA се приема, че генотипът има фиксирана дължина. Все пак, има варианти на HA без това ограничение.
Създаване на първоначалното население
Преди първата стъпка е да се създаде случайно първоначално населението; дори ако това би било напълно неконкурентоспособни то е вероятно, че генетичен алгоритъм е все още доста бързо да го превърне в жизнеспособна популация. По този начин, първата стъпка може да бъде особено не се опитвайте да правите твърде силния, достатъчно, за да съответстват на формата на лицата от населението, както и да ги е било възможно да се изчисли функцията за фитнес (Фитнес). Резултатът от първата стъпка е популация Н, състояща се от N индивиди.
Възпроизвеждането на генетични алгоритми обикновено сексуални - да произвеждат потомство, се нуждаем от няколко родители, обикновено две.
Възпроизвеждането на различни алгоритми, определени по различни начини - това е, разбира се, зависи от представянето на данните. Основното изискване да се възпроизведе - за наследник или наследници имат възможност да наследи чертите на двамата родители, "смесване" тях по никакъв начин.
Защо физически лица за възпроизвеждане обикновено са избрани от цялото население на H и оцелелите не са посочени в първата стъпка елементи H0 (въпреки че последната опция също има право да съществува)? Фактът, че основният проблем на много генетични алгоритми - липсата на разнообразие (разнообразие) в индивиди. единичен генотип се откроява достатъчно бързо, което е локален максимум, а след това всички елементи на населението губят своята селекция, а цялото население "изкован" копия на този индивид. Има различни начини да се справят с този нежелан ефект; Един от тях - изборът за разплод, не са по-силния, но като цяло на всички индивиди.
Мутациите включват всички едно и също нещо, че да възпроизвежда: имат определено количество на мутант м, е параметър на генетичен алгоритъм, и по-стъпка мутации изберете Mn лица, а след това ги променя според операции предварително определени мутации
На етапа на подбор на необходимостта от цялото население, за да изберете определена част от него, която остава "жив" на този етап на еволюция. Има различни начини за извършване на селекцията. з индивидуален вероятността за оцеляване ще зависи от стойността на фитнес функция фитнес (з). Самата съотношение оцеляване те обикновено параметъра на генетичен алгоритъм, и то само определени предварително. Според резултатите от селекция на N индивиди от популацията трябва да остане Н SN лица да бъдат включени в населението на крайния H ". Останалите птици, убити
При избора на турнир (турнир избор) от популация, съдържаща N лица са случайно избрани лица т, и най-доброто от тях е на индивидуалната междинен масив (фиг. 5). Тази операция се повтаря N пъти. Лица в получения междинен масив след това се използват за чифтосване (като произволно). Размерът на избора на линия група на турнира, често равно на 2. В този случай говорим за двоичен (удвоява) на турнира. Като цяло, номер Т се нарича турнир. Предимството на този метод е, че той не се нуждае от допълнителни изчисления.
В метода на рулетката (избор рулетка колела) екземпляри избран чрез N «работи" рулетка, където N - броя на населението. Колелото на рулетката съдържа един сектор за всеки член от населението. Размерът на сектор-тото е пропорционална на вероятността от изпадане в нова популация P (и),
изчислява по следната формула:
където F (I) - пригодността на аз-ти индивида. Очаквано брой копия на аз-ти хромозома след оператор рулетка определя по формулата Ni = P (I) N. С такъв избор на членовете на населението с висше адаптивност по-вероятно да бъде избран по-често от хората с ниско фитнес (табл. 7). Други техники за подбор могат да бъдат получени от по-горе споменатите модификации. Така например, в подбора на рулетка, можете да промените формулата за вероятността на дадено лице да въведете нова популация.