Генетическое программирование


Генетическое программирование

В искусственном интеллекте генетическое программирование (ГП) — автоматическое создание или изменение программ с помощью генетических алгоритмов. С помощью этой методологии «выращиваются» программы, всё лучше и лучше (в соответствии с определенной функцией приспособленности для хромосом) решающие поставленную вычислительную задачу.

Содержание

История

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

Выбор способа кодирования программы в генетическом алгоритме — один из основных вопросов генетического программирования. Программа должна быть закодирована в таком виде, чтобы легко было автоматически вносить случайные изменения (оператор мутации) и объединять два алгоритма в один (оператор скрещивания).

Способы кодирования можно разделить на два класса:

  • Прямое кодирование — генетический алгоритм работает с программой в явном виде.
  • Косвенное кодирование — генетический алгоритм работает не с самим кодом программы, а с правилами его построения. То есть генетический алгоритм работает с программой, которая генерирует нужную нам программу.

Нейронные сети

Древовидное

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

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

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

Оператор скрещивания

Оператор скрещивания для древовидного представления программ


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

Пример:

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

Оператор мутации

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

Пример:

individual.Information = randomInformation();

или

individual = generateNewIndividual();

Метагенетическое программирование

Метагенетическое программирование — это ГП, в котором изменяется и, тем самым, «выращивается» не только заданная компьютерная программа, но и сами применяемые операторы скрещивания и мутации.

Ссылки

Литература

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

.


Wikimedia Foundation. 2010.

Смотреть что такое "Генетическое программирование" в других словарях:

  • Java Evolutionary Computation Toolkit — ECJ Операционная система Кроссплатформенное программное обеспечение Последняя версия 20 Лицензия AFL, BSD Сайт ECJ project ECJ  это свободная исследовательская сис …   Википедия

  • Эволюционные алгоритмы — Эволюционные алгоритмы  направление в искусственном интеллекте (раздел эволюционного моделирования), которое использует и моделирует биологическую эволюцию. Различают различные алгоритмы: генетические алгоритмы, эволюционное программирование …   Википедия

  • Глушков — Глушков, Виктор Михайлович Виктор Михайлович Глушков Дата рождения: 24 августа 1923(1923 08 24) Место рождения: Ростов на Дону Дата смерти …   Википедия

  • Розенблатт — Розенблатт, Фрэнк Фрэнк Розенблатт Frank Rosenblatt известный учёный в области компьютерной науки Дата рожден …   Википедия

  • Эволюционное моделирование — использует признаки теории Дарвина для построения интеллектуальных систем (методы группового учёта, генетические алгоритмы). Является частью более обширной области искусственного интеллекта вычислительного интеллекта. Эволюционное моделирование… …   Википедия

  • Искусственная жизнь — Эта статья или раздел нуждается в переработке. Пожалуйста, улучшите статью в соответствии с правилами написания статей. Искусственн …   Википедия

  • Zero Player Game — В этой статье не хватает ссылок на источники информации. Информация должна быть проверяема, иначе она может быть поставлена под сомнение и удалена. Вы можете отредактировать …   Википедия

  • ZPG — Zero Player Game (жарг. русск. самоиграйка) вид компьютерных игр, в которых вмешательство человека в игровой процесс минимально или отсутствует вовсе. Содержание 1 Игра компьютера против компьютера 2 Применение …   Википедия

  • Тьюринг — Тьюринг, Алан Матисон Алан Тьюринг Alan Mathison Turing Памятник в Сэквиль Парке Дата рождения …   Википедия

  • сети доверия — Обработка фрагмента информации вызывает когнитивный эффект, позволяющий закрепить или пересмотреть некоторые предположения. Байесовские системы и программные продукты для манипуляций с сетями доверия работают с управлением неопределенностью.… …   Словарь технической реальности: Культурная интеллигенция социальный контроль

Книги

  • Набла квадрат, Петр Воробьев. Та самая "Набла квадрат," переизданная к двадцатилетию написания. Злые мертвецы, месть, преступно некомпетентное программирование, фанерные звездолеты, генетическое оружие, стихи, от которых… Подробнее  Купить за 475 руб