Генетичні алгоритми

Генетичні алгоритми

Генетичні алгоритми являють собою евристичні, стохастичні методи оптимізації, які були запропоновані вперше в 1975 році Холландом. В їх основу покладена ідея еволюції з природним відбором, яка пропонувалася ще Дарвіном.


Генетичні алгоритми працюють з безліччю особин, тобто популяцією, де кожна особина може послужити вирішенням якоїсь певної проблеми. Кожну особину доводиться оцінювати на ступінь її пристосованості залежно від того, наскільки хорошим є вирішення завдання, відповідне їй. Якщо розглядати це у співвідношенні з природою, то там оцінюється ступінь ефективності організму при конкурентній боротьбі за ресурси. Особи, які помітно сильніше пристосовані, можуть відтворювати потомство за допомогою перехресного схрещування з іншими представниками популяції. Це стає причиною появи нових особин, в яких поєднуються деякі характеристики, що передаються у спадок від батьків.


Менш пристосовані особини зможуть відтворити потомство з меншою ймовірністю, так що властивості, якими вони володіють, будуть поступово зникати в процесі еволюції з усієї популяції. Іноді трапляються спонтанні зміни в генах, або мутації. Виходить, що хороші характеристики з покоління в покоління будуть поширені по всій популяції. Схрещення особин, які є найбільш пристосованими, призводить до того, що досліджуються ділянки пошуку, що представляють найбільшу перспективу. В кінцевому підсумку знаходиться рішення завдання. Генетичні алгоритми мають перевагу, що полягає в тому, що він знаходить за відносно нетривалий проміжок часу приблизні рішення, що представляють собою оптимальні. Варто розглянути це питання щодо програмування.

Генетичні алгоритми складаються з таких компонентів:

- хромосома, що являє собою вирішення розглянутої проблеми, складається з генів. Ця популяція хромосом вважається початковою;

- набір операторів (призначається для генерації нових рішень на основі нових популяцій);

- цільова функція (призначена для того, щоб оцінювати пристосованість рішень).

Для генетичних алгоритмів існує стандартний набір операторів: селекція, мутація і схрещування. Можна розглянути застосування генетичних алгоритмів за допомогою уточнення того, для чого призначений кожен конкретний оператор. Оператор селекції виробляє відбір хромосом відповідно до того, якими є значення їх функцій пристосованості. Тут представлені як мінімум два найбільш популярних оператора: турнір і рулетка. Метод рулетки передбачає здійснення відбору особин за допомогою n запусків. Для кожного члена використовуваної популяції в колесі рулетки міститься по одному сектору необхідної величини. Члени популяції з помітно вищим показником пристосованості при такому відборі будуть частіше вибиратися, ніж представники, що мають низьку пристосованість. При турнірному методі реалізується n турнірів, що дозволяють вибрати n особин. В основу кожного турніру закладена вибірка k елементів з популяції, при цьому серед них повинна бути обрана найкраща особина.


Якщо і далі розглядати алгоритми програмування, то варто сказати про метод, званий схрещування. Оператором схрещування здійснюється обмін частинами хромосом між парою або хромосомами в одній популяції.

 Останній оператор - мутації - стохастична зміна частини хромосом.

Конкретний розгляд застосування генетичних алгоритмів являє собою більш об 'ємний матеріал, ніж може вміститися в статті, тому його варто розглядати окремо.