Генетичне програмування

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

Генетичні операції

■ Схрещення

■ Мутація

■ Репродукція

■ Генне дублювання

■ Генне видалення

Підготовчий етап генетичного програмування

1. Встановлення набору терміналів

2. Встановлення набору примітивних функцій

3. Визначення коефіцієнту наближеності до результату (фітнес)

4. Параметри для контролю виконання

5. Критерій виходу з програми

Етап виконання

1. Рандомне створення початкової популяції (покоління 0) окремих комп’ютерних програм, створених з можливих функцій та терміналів.

2. Ітеративне виконання послідовних кроків (поколінь) на популяції, поки не буде досягнутий критерій виходу:

a) Виконання кожної програми популяції на вхідних даних

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

с) Створення нової індивідуальної програми використовуючи наступні генетичні операції із встановленими ймовірностями:

i. Репродукція

ii. Схрещення

iii. Мутація

iv. Архітектурно-змінюючі операції

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

Приклад виконання програми

■ Ціль – автоматично створити комп’ютерну програму, вивід якої рівний значенню квадратного поліному x2+x+1 в діапазоні від -1 до 1.

■ На практиці, операція схрещення відбувається у 90% випадків, операція дублювання у 8% випадків, операція мутації – 1% випадків, а операція зміни архітектури майже в 1% випадків.

Процес виконання

■ Оскільки у результаті передбачається квадратне рівняння, початкова множина терміналів складатиметься з х та простих чисел діапазоном від -5 до 5.

■ Потім потрібно визначити множину функцій, яка у даному випадку складатиметься з додавання, віднімання, множення та ділення.

■ Кожний індивід в популяції – це набір терміналів та функцій.

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

■ Оскільки в даному прикладі мала популяція, то буде покрите використання операції схрещення на двох індивідах, а операції мутації та дублювання поодинці на кожному що лишилися. Для спрощення, операція зміни архітектури не буде використовуватися.

■ Критерій завершення буде шукатися протягом генерування кожного нового покоління, поки не буде знайдений такий індивід, в якого значення фітнесу буде меншим за 0,01.

■ Після завершення проведення початкового етапу, можна розпочинати виконавчий етап.

■ Генетичне програмування розпочинається із створення рандомної початкової генерації з чотирьох індивідів.

Покоління 0

Перший індивід відповідає математичному виразу x+1, другий – x2+1, третій – 2, четвертий – x. Тобто із дерева утворюється математичний вираз у стилі LISP, в глибину зліва направо.

Покоління 1

Для утворення нової популяції, потрібно провести операцію дублювання найкращого індивіда (а) з попереднього покоління.

Далі