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

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

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

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

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

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

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

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

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

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

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

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