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

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

В штучному інтелекті генетичне програмування (ГП) — автоматичне створення або змінна програми за допомогою генетичних алгоритмів. За допомогою цієї методики «вирощування» програми, все краще і краще (у відповідності з визначеною функцією "пристосування" до хромосом) вирішуючи поставлену задачу. Засновником вважається Джон Коза.

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

«Батьком-засновником» генетичних алгоритмів вважається Джон Холланд (en: John Henry Holland), книга якого «Адаптація в природних і штучних системах» (1975) є основоположною працею в цій галузі досліджень. Йому ж належить і ідея генетичних алгоритмів. Сама ідея запозичена у живої природи і полягає в організації еволюційного процесу, кінцевою метою якого є отримання оптимального рішення складної комбінаторної задачі. Розробник генетичних алгоритмів виступає в даному випадку як «творець», який повинен правильно встановити закони еволюції, щоб досягти бажаної мети якомога швидше. Вперше ці нестандартні ідеї були застосовані для вирішення оптимізаційних завдань у середині 70-х років. Приблизно через десять років з'явилися перші теоретичні обгрунтування цього підходу. На сьогоднішній день генетичні алгоритми довели свою конкурентноздатність при вирішенні багатьох NP-повних задач і особливо в практичних додатках, де математичні моделі мають складну структуру і застосування стандартних методів, таких як метод гілок і меж, динамічного або лінійного програмування вкрай ускладнено.

Кодування Алгоритму[ред.ред. код]

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

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

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

Нейронні мережі[ред.ред. код]

Шаблон:Заготовка розділу

Деревоподібну[ред.ред. код]

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

В деревоподібну кодуванні кожний вузол дерева містить функцію, а кожний листок - операнд. Вираз, представлений у вигляді дерева, може бути легко рекурсивно обчислено. Традиційне ГП краще всього використовувати для «вирощування» програми, написане на мовах мовах програмування, де природнім способом реалізовані деревоподібні структури. Маються на увазі Lisp, Haskell, F# і інші функціональні мови програмування.

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

Оператор схрещування[ред.ред. код]

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

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

Приклад:

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

Оператор мутації[ред.ред. код]

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

Приклад:

individual.Information = randomInformation();

або

individual = generateNewIndividual();

Метагенетичне програмування[ред.ред. код]

Метагенетичне програмуванн — це ГП, в якому змінюється і, тим самим , "вирощування" не тільки задана комп'ютерна програма, а й самі оператори схрещування і мутації

Приклад тривіальної реалізації на 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)

.