P - розмір популяції. Величина W (Р) = 1 означає, що ціла попередня популяція переміщається в нову в кожній генерації. При подальшій реалізації алгоритму кращі елементи з батьків і нащадків будуть вибиратися, для формування нової популяції [5,6].
.2 Прості генетичні алгоритми
Еволюційний процес реалізується за рахунок здатності В«кращихВ» хромосом чинити більший вплив на склад нової популяції допомогою тривалого виживання і більше численного потомства. Основні етапи процесу еволюції, на основі якого створюються необхідні схеми генетичного пошуку, згідно Д. Холланду наступні:
. Конструювання початкової популяції. Ввести точку звіту поколінь t = 0. Обчислити пристосованість хромосом популяції, а потім середню пристосованість популяції. p align="justify">. Встановлення t = t + 1. Вибрати двох батьків (хромосом) для кросинговеру. Він виконується випадковим чином пропорційно пристосовності батьків. p align="justify">. Формування генотипу нащадка. З заданою вірогідністю здійснити над генотипами обраних хромосом кросинговер. Вибрати з імовірністю 0,5 один з нащадків p (t) і зберегти його як члена нової популяції. Послідовно застосувати до р (t) оператор інверсії, а потім мутації із заданими ймовірностями. Отриманий генотип нащадка зберегти як p '(t). p align="justify">. Відбір хромосоми випадковим чином для виключення її з популяції. Оновлення поточної популяції заміною відібраної хромосоми на p '(t). p align="justify">. Визначення пристосованості (цільової функції) p '(t) і перерахунок середньої пристосованості популяції. p align="justify">. ЯКЩО t = t заданому , то перехід до 7, якщо ні, то перехід до 2.
. Кінець роботи. p align="justify"> Ми привели так званий репродуктивний план Д. Холланда в дещо спрощеному вигляді. Зауважимо, що в технічних завданнях оптимізації часто замість поняття В«пристосованістьВ» використовують поняття В«цільова функціяВ». Біологи називають цю функцію - fitnessfunction. Простий генетичний алгоритм (ПГА) був вперше описаний Д. Гольдбергом на основі робіт Д. Холланда. Його механізм нескладний. Він копіює послідовності і переставляє їх частини. Попередньо ПГА випадково генерує популяцію послідовностей - хромосом (альтернативних впорядкованих та невпорядкованих рішень). Потім він застосовує безліч простих операцій до початкової популяції і генерує нові популяції. p align="justify"> ПГА складається з трьох операторів:
репродукції;
кросинговеру (ОК);
мутації (ОМ).
.3 Приклад
В
Розглянемо класичну винахідницьку завдання про запаювання ампули з ліками. Мається ампула з рідким ліками, яка встановлена ​​вертикальн...
