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

Генети́чне програмува́ння (ГП) — підхід у штучному інтелекті до створення алгоритмів, натхнених еволюцією біологічних видів, щоб знайти програму, яка якнайкраще буде виконувати поставленні завдання. ГП являє собою набір інструкцій програми з функціями допасованості (англ. fitness function), які характеризують, наскільки добре дана програма справилась із завданням. ГП є одним з випадків генетичних алгоритмів, де "індивідом" є комп'ютерна програма, яка буде піддаватись мутаціям. У машинному навчанні цю техніку використовують, щоб оптимізувати покоління комп'ютерних програм відповідно до адаптивного ландшафту визначеного з даних того, як добре програми виконують обчислювальне завдання.

Історія

У 1964 році ГП почалось з генетичних алгоритмів, вперше використаних для симуляції еволюції Нілсьом Аль Баріселлі. У 60-x і на початку 70-x, генетичні алгоритми вже добре зарекомендували себе, як методи оптимізації. Інго Реченберг і його група вирішувала складні інженерні завдання за допомогою еволюційних стратегій, як було задокументовано в його дисертації у 1971 році і книзі у 1973 році. Також дуже важливу роль відіграв Джон Холланд (en: John Henry Holland), який вважається одним із основоположників генетичних алгоритмів. Його книга «Адаптація в природних і штучних системах» (1975) є базовою працею в цій галузі досліджень.

У 1964 році Лавренс Джером Фоджел застосував генетичні алгоритми для вивчення скінченного автомату. Пізніше роботи пов'язані з ГП пішли з групи людей, що займалась системою класифікації навчання^[en], котрі розробили систему складних правил, що описують оптимальну стратегію для марківських процесів вирішування. Перше визначення сучасного (базованого на теорії дерев) ГП дав Нічел Л.Грамер (Nichael L. Cramer). Пізніше цю тему значно розширив Джон Коза, головний прихильник ГП, хто один з перших застосував ГП в сферах оптимізації і пошуку. Пізніше Гіана Гіавеллі (Gianna Giavelli), студент Джона Кози, один з перших почав застосовувати ГП для моделювання ДНК послідовностей.

У 90-х, ГП в основному використовувалось для відносно простих завдань, бо воно було ресурсоємне для тодішніх комп'ютерів. Останнім часом, у зв'язку з вдосконаленням ГП і експоненціальним ростом потужностей центрального процесора (закон Мура), ГП почало застосовуватись і дало гарні результати у сферах квантових обчислень, проектуванні електросхем, комп'ютерних іграх, сортуванні і пошуку. ГП також застосовується у сфері еволюціонуючого успадкування так як і у сфері програмного забезпечення.

У 85-х років з'явилися перші теоретичні обґрунтування цього підходу, зараз ГП розглядають, як один з пошукових методів. На сьогоднішній день генетичні алгоритми довели свою конкурентноздатність при вирішенні багатьох NP-повних задач і особливо в практичних додатках, де математичні моделі мають складну структуру і застосування стандартних методів, таких як метод гілок і меж, динамічного або лінійного програмування вкрай ускладнено.

Програмна реалізація

ГП традиційно зберігаються у пам'яті комп'ютера у деревоподібних структурах. Дерева можна легко обійти за допомогою рекурсивних алгоритмів. Кожне дерево має внутрішні вершини дерева, котрі представляють собою функцію оператор і кожен листок має операнд — це робить обчислення легкі у вдосконаленні і в оцінюванні. Таким чином ГП найкраще реалізовувати на мовах програмування у яких є природним використання деревоподібних структур (для прикладу LISP, чи інша функціональна мова програмування).

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

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

Основні оператори, які використовуються в ГП — це оператор схрещування і оператор мутації.

Функція, представлена в деревоподібній формі

Оператор схрещування

Оператор схрещування

У деревоподібному представленні оператор схрещування реалізовується обміном між двома деревами будь-якими вузлами разом з їхніми синами (піддеревами). Дерево отримане після цієї операції може суттєво відрізнятись від батьківських дерев.

Приклад:

individual.Children[randomChildIndex] = otherIndividual.Children[randomChildIndex];

Оператор мутації

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

Приклад:

individual.Information = randomInformation();

або

individual = generateNewIndividual();

Кодування алгоритму

Вибір способу кодування програми в генетичному алгоритмі — це одне з основних питань генетичного програмування. Програма повинна бути написана так, щоб було легко автоматично вносити випадкові зміни (оператор мутації) і об'єднати два алгоритми в один (оператор схрещування).

Всі способи написання генетичного алгоритму можна поділити на дві групи:

• Пряме кодування — генетичний алгоритм працює з програмою в наявному вигляді.
• Опосередковане кодування — генетичний алгоритм працює не з самим кодом програми, а з правилами його побудови. Тобто, генетичний алгоритм працює з програмою, яка генерує потрібну нам підпрограму.

Інші підходи

Базові ідеї генетичного програмування, змінені і доповнені, були використанні у багатьох підходах:

• Розширене компактне генетичне програмування(ECGP)
• Вбудоване декартове генетичне програмування(ECGP)
• Імовірнісно зростаюче генетичне програмування

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

Мета-генетичне програмування пропонує використовувати алгоритми генетичного програмування на сам генетичний алгоритм, котрий шукає розв'язок певної задачі.

Пропонується застосовувати еволюційні алгоритми на хромосоми, алгоритми схрещування і мутації. Їм, як відповідним живим прототипам, має бути дозволено змінювати самих себе, а не бути наперед визначеними програмістом. Мета-ГП було формально запропоноване Юргеном Шмідхубером у 1987 році. Дуглас Ленат з допомогою програми Eurisko^[en] також робив раніше дослідження в цій темі. Це рекурсивний, але кінчений алгоритм, який не зациклюється.

Критики цього підходу кажуть, що він є занадто масштабний. Тим не менше, може бути можливим: обмежити критерій функції допасованості на загальну множину результатів і таким чином отримувати еволюціонуючий алгоритм ГП, що буде більш ефективно продукувати результати для підмножин. Алгоритм для генерування людської ходьби, стрибків може бути створений за допомогою мета-генетичного програмування. Мета-генетичне програмування — один з найкращих підходів для вирішення цієї проблеми.

Для загального класу проблем немає способу показати, що мета-ГП дасть кращі результати, ніж уже створені жадібні алгоритми. Це саме стосується стандартних алгоритмів ГП і інших пошукових алгоритмів.

Приклад тривіальної реалізації на C++

#include <iostream>
#include <algorithm>
#include <numeric>

int main() {
  using namespace std;
  srand((unsigned)time(NULL));
  const int N = 1000;
  int a[N];
  // Заповнюємо нулями
  fill(a, a + N, 0);
  for (;;) {
    // Мутація в випадкову сторону кожного елемента:
    for (int i = 0; i < N; ++i) {
      if (rand() % 2 == 1)
        a[i]++;
      else
        a[i]--;
    }
    // Тепер вибираємо кращих, відсортувавши за зростанням ...
    sort(a, a + N);
    //... і тоді кращі виявляться в другій половині масиву.
    // Скопіюємо кращих у першу половину, куди вони залишили потомство, а перші померли:
    copy(a + N / 2, a + N, a / * куди * /);
    // Тепер подивимося на середній стан популяції. Як бачимо, він все кращий і кращий.
    cout << Accumulate (a, a + N, 0) / N << endl;
  }
}

Див. також

• Мутаційне тестування

Посилання

• geneticprogramming.us [Архівовано 4 квітня 2010 у Wayback Machine.]
• Огляд методів еволюції нейронних мереж [Архівовано 25 грудня 2011 у Wayback Machine.]
• Генерування автоматів [Архівовано 19 червня 2014 у Wayback Machine.]
• www.genetic-programming.org [Архівовано 20 березня 2022 у Wayback Machine.]

Література

• Banzhaf, W., Nordin, P., Keller, R.E., Francone, F.D. (1997), Genetic Programming: An Introduction: On the Automatic Evolution of Computer Programs and Its Applications, Morgan Kaufmann
• Cramer, Nichael Lynn (1985), „A representation for the Adaptive Generation of Simple Sequential Programs“ in Proceedings of an International Conference on Genetic Algorithms and the Applications, Grefenstette, John J. (ed.), CMU
• Koza, J.R. (1990), Genetic Programming: A Paradigm for Genetically Breeding Populations of Computer Programs to Solve Problems, Stanford University Computer Science Department technical report STAN-CS-90-1314 [Архівовано 6 листопада 2020 у Wayback Machine.]. A thorough report, possibly used as a draft to his 1992 book.
• Koza, J.R. (1992), Genetic Programming: On the Programming of Computers by Means of Natural Selection, MIT Press
• Koza, J.R. (1994), Genetic Programming II: Automatic Discovery of Reusable Programs, MIT Press
• Koza, J.R., Bennett, F.H., Andre, D., and Keane, M.A. (1999), Genetic Programming III: Darwinian Invention and Problem Solving, Morgan Kaufmann
• Koza, J.R., Keane, M.A., Streeter, M.J., Mydlowec, W., Yu, J., Lanza, G. (2003), Genetic Programming IV: Routine Human-Competitive Machine Intelligence, Kluwer Academic Publishers
• Langdon, W. B., Poli, R. (2002), Foundations of Genetic Programming, Springer-Verlag
• Poli, R., Langdon, W. B., McPhee, N. F. (2008), A Field Guide to Genetic Programming, Lulu.com, freely available from the internet ISBN 978-1-4092-0073-4
• Smith, S.F. (1980), A Learning System Based on Genetic Adaptive Algorithms, PhD dissertation (University of Pittsburgh).