Генетическое программирование (Iyuymncyvtky hjkijgbbnjkfguny)

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

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

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

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

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

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

Древовидное

В древовидном кодировании каждый узел дерева содержит функцию, а каждый лист — операнд. Выражение, представленное в виде дерева, может быть легко рекурсивно посчитано. Традиционное ГП легче использовать для выращивания программ, написанных на языках, естественным образом воплощающих древовидную структуру: 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)
Сопов Е. А. (2004), Эволюционные алгоритмы моделирования и оптимизации сложных систем, диссертация на соискание учёной степени кандидата технических наук, Красноярск

Ссылки

Искусственный интеллект
История	История искусственного интеллекта Зима искусственного интеллекта Дартмутский семинар Регламент ЕС об искусственном интеллекте
Философия	Тест Тьюринга Китайская комната Сильный и слабый искусственные интеллекты Дружественный искусственный интеллект Этика искусственного интеллекта Проблема контроля
Направления	Агентный подход Адаптивное управление Инженерия знаний Модель жизнеспособной системы Машинное обучение Нейронная сеть Нечёткая логика Обработка естественного языка Персональный искусственный интеллект Распознавание образов Роевой интеллект Символический ИИ Эволюционные алгоритмы Экспертная система
Применение	Голосовое управление Задача классификации Классификация документов Кластеризация документов Кластерный анализ Локальный поиск Машинный перевод Оптическое распознавание символов Распознавание речи Распознавание рукописного ввода Игровой ИИ
Исследователи	Чарлз Бэббидж Владимир Вапник Джозеф Вейценбаум Норберт Винер Виктор Глушков Владимир Городецкий Ян Лекун Алексей Ляпунов Джон Маккарти Марвин Мински Аллен Ньюэлл Сеймур Пейперт Джуда Перл Гермоген Поспелов Дмитрий Поспелов Фрэнк Розенблатт Герберт Александер Саймон Алан Тьюринг Патрик Уинстон Виктор Финн Сергей Фомин Демис Хассабис Джеффри Хинтон Ноам Хомский Клод Шеннон Эндрю Ын Элиезер Юдковский

Машинное обучение и data mining
Задачи	Задача классификации Обучение без учителя Обучение с частичным привлечением учителя Регрессионный анализ AutoML Ассоциативные правила Выделение признаков Обучение признакам Обучение ранжированию Грамматический вывод Онлайновое обучение
Обучение с учителем	Метод k ближайших соседей Наивный байесовский классификатор Дерево решений Метод опорных векторов Линейная регрессия Логистическая регрессия Перцептрон Ансамблевое обучение Бэггинг Бустинг Метод случайного леса Метод релевантных векторов
Кластерный анализ	Метод k-средних Метод нечёткой кластеризации Иерархическая кластеризация EM-алгоритм BIRCH CURE DBSCAN OPTICS Mean-shift
Снижение размерности	Факторный анализ Метод главных компонент CCA ICA LDA Неотрицательное матричное разложение t-SNE
Структурное прогнозирование	Графовая вероятностная модель Байесовская сеть Скрытая марковская модель CRF
Выявление аномалий	Метод k ближайших соседей Локальный уровень выброса
Графовые вероятностные модели	Байесовская сеть Марковская сеть Скрытая марковская модель
Нейронные сети	Ограниченная машина Больцмана Самоорганизующаяся карта Функция активации Сигмоида Softmax Радиально-базисная функция Метод обратного распространения ошибки Глубокое обучение Многослойный перцептрон Рекуррентная нейронная сеть Долгая краткосрочная память Управляемый рекуррентный блок Свёрточная нейронная сеть U-Net Автокодировщик
Обучение с подкреплением	Марковский процесс Уравнение Беллмана Жадный алгоритм Q-обучение SARSA Temporal difference (TD)
Теория	Размерность Вапника — Червоненкиса Дилемма смещения–дисперсии Теория вычислительного обучения Минимизация эмпирического риска Оккамово обучение PAC learning Статистическая теория обучения
Журналы и конференции	NeurIPS ICML ML JMLR ArXiv:cs.LG