Генетичні алгоритми; Лабораторія 3

Лабораторія 3

зміст

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

Метод натхненний еволюційною теорією Дарвіна. Робота з a сукупність рішень-кандидатів, який еволюціонує та адаптується до середовища (у цьому випадку середовище - це функція, яку слід оптимізувати). Зміни генотипу:

лабораторія

  • наступна мутація (модифікація гена в кодуванні особини)
  • після рекомбінації генетичного коду двох особин)

Відповідно до еволюційного принципу природний відбір, від одного покоління до іншого сприятиме виживанню найкращих (добре пристосованих) людей.

Термінологія

  • індивідуальний (хромосома) = рішення кандидата, кодоване як у лабораторії 2
  • хромосоми складаються з гени (ознаки)
  • кожен ген знаходиться в хромосомі в одному положенні (локус/локуси)
  • називаються різні значення, які може приймати ген алель

псевдо

компоненти

Особи відбираються у новій популяції з імовірністю, пропорційною фізичній формі.

Деякі особи можуть мати більше дітей у новій популяції, інші можуть мати 0. тур

Особи "б'ються" групами по m, обраних навмання. Вибираються найкращі n у кожній групі.

На основі ієрархії

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

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

    перетин

    Він поєднує в собі ознаки двох батьківських хромосом, що призводить до потомства, яке частково успадковує ці ознаки. Впливає на хромосоми з імовірністю ПК. Кількість особин, які беруть участь у схрещуванні протягом покоління, оцінюється за pc * pop_size.

    Відбір особин, які зазнають схрещування:

    • Перетин із випадково обраною точкою різання. Приклад:
    • Перетин з n випадково сформованими точками зрізу. Приклад (n = 3):
    • Рівномірне схрещування: для кожного локусу імовірнісно відбирається ген одного з батьків.
  • мутація

    Він змінює один або кілька довільно обраних генів хромосоми. Імовірність мутації задається параметром вечора. Кількість мутованих генів оцінюється за pm * довжина хромосоми * розмір_поп. Застосування мутації:

    Якщо подання використовується як рядок бітів, мутація полягає у зміні значення відповідного біта від 0 до 1 або навпаки.

    "Стандартні" параметри pop_size = 50 особин ймовірність мутації pm = 0,01 ймовірність кросоверу pc = 0,25 Критерії зупинки досягнення кількості ітерацій TMAX відсутність вдосконалення рішення в останніх ітераціях TW (або TW (t)) .

    Впровадити генетичний алгоритм для пошуку кінцевих точок функцій, запропонованих у лабораторії 1.

    Нанесіть графік того, як розвиваються рішення. Діаграма повинна відображати максимальну, мінімальну та середню підготовленість кожного покоління.

    Складіть короткий звіт (текстовий формат) із зазначенням:

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