Page 35 - 4521

дітей. При цьому дублювання рядків не допускається. У моде-
лі СНС розмір популяції відносно малий — близько 50 особин.
Це виправдовує використання однорідного кросинговера і до-
зволяє алгоритму зійтися до рішення. Для отримання більш
менш однакових рядків (див. визначення збіжності) CHC за-
стосовує cataclysmic mutation: всі рядки, окрім самої пристосо-
ваної, піддаються сильній мутації (змінюється біля третини
бітів). Таким чином, алгоритм перезапускається і далі продов-
жує роботу, застосовуючи тільки кросинговер.

1.7.6 ГА з нефіксованим розміром популяції
У генетичному алгоритмі з нефіксованим розміром по-
пуляції (Genetic Algorithm with Varying Population Size —
GAVaPS) кожній особині приписується максимальний вік,
тобто число поколінь, після яких особина гине. Впровадження
в алгоритм нового параметра — віку — дозволяє виключити
оператора відбору в нову популяцію. Вік кожної особини ін-
дивідуальний і залежить від її пристосованості. У кожному
поколінні t на етапі відтворення звичайним способом створю-
ється додаткова популяція з нащадків. Розмір додаткової по-
пуляції (AuxPopsize(t)) пропорційний розміру основної попу-
ляції (Popsize(t)) і рівний
AuxPopsize (t)  [Popsize(t )p ] (1.7)
с
де p с — вірогідність відтворення. Для відтворення особини
вибираються з основної популяції з рівною ймовірністю неза-
лежно від їх пристосованості. Після застосування мутації і
кросинговера нащадкам приписується вік згідно значенню їх
пристосованості. Вік є константою впродовж всієї еволюції
особини (від народження до загибелі). Потім з основної попу-
ляції віддаляються ті особини, термін життя яких закінчився, і
додаються нащадки з проміжної популяції. Таким чином, роз-
мір після однієї ітерації алгоритму обчислюється за формулою:
PopPopsize (t  1)  Popsize(t)  AuxPopsize (t) - D(t) (1.8)
де D(t) — число особин, які вмирають в поколінні t.

34