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

Матеріал з Вікіпедії — вільної енциклопедії.
Перейти до: навігація, пошук

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

Історія[ред.ред. код]

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

У 1964 році Лавренс Джером Фоджел застосував генетичні алгоритми для вивчення скінченного автомату.Пізніше роботи пов'язані з ГП пішли з групи людей що займалась системою класифікації навчання, котрі розробили систему складних правил описуючих оптимальну стратегію для Марківський процес приймання рішень. Перше визначення сучасного (базованого на теорії дерев) ГП дав Нічел Л.Грамер(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 році. Дуг Ленат Еуріско також робив раніше дослідження в цій темі. Це рекурсивний, але кінчений алгоритм, який не зациклюється.

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

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

Приклад тривіальної реалізації на 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] + = 1;
      else
        a [i] - = 1
    / / Тепер вибираємо кращих, відсортувавши за зростанням ...
    sort (a, a + N);
    //... і тоді кращі виявляться в другій половині масиву.
    / / Скопіюємо кращих в першу половину, куди вони залишили потомство, а перші померли:
    copy (a + N / 2, a + N, a / * куди * /);
    / / Тепер подивимося на середній стан популяції. Як бачимо, воно все краще і краще.
    cout <<Accumulate (a, a + N, 0) / N <<endl;
}
}

Посилання[ред.ред. код]

Література[ред.ред. код]

  • 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. 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)

.