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

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

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

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

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

Відео: генетичний алгоритм

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

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

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

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

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

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