Эволюционное программирование | это... Что такое Эволюционное программирование? (original) (raw)

Содержание

Эволюционное программирование

Эволюционное программирование было изобретено доктором Лоуренсом Дж. Фогелем в Национальном Научном Фонде в 1960 году. Ему было поручено представить доклад Конгрессу США на сумму инвестиций в фундаментальные исследования. Одним из вопросов рассмотрения был искусственный интеллект.

В то время искусственный интеллект был ограничен двумя основными направлениями исследований: моделированием человеческого мозга (нейронные сети) и моделированием решения проблем поведения человека (эвристическое программирование). Альтернативный вариант, предусмотренный доктором Фогелем, должен был отказаться от моделирования конечного продукта эволюции, и, скорее, моделировать процесс эволюции, используя себя в качестве транспортного средства для получения разумного поведения (Фогель, 1962, 1963). Фогель рассматривает интеллект как составную часть способности делать предсказания окружающей среды в сочетании с переводом каждого прогноза в подходящий ответ в свете заданной цели (например, для максимизации функции выигрыша). Таким образом, по его мнению прогнозирование является необходимым условием для разумного поведения. Моделирование эволюции как оптимизации процесса явилось следствием опыта доктора Фогеля в новых областях «биотехнологии», кибернетики и техники. Доктор Фогель провел серию экспериментов, в которых автоматы представляли отдельные организмы. Автоматы - это графические модели, используемые для описания поведения или программного обеспечения и аппаратных средств, поэтому он назвал свой подход эволюционным программированием.

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

В 1964 году Фогель получил докторскую степень в области электротехники в университете Калифорнии в Лос-Анджелесе. Его диссертация «О происхождении Интеллекта», была посвящена искусственному интеллекту путем имитации эволюции. Ранние работы также привели доктора Фогеля, д-ра Аль Оуэнса, и д-ра Майкла Уолша к созданию решений для Science, Inc в 1965 году. Это была первая компания в мире, занимавшаяся исключительно коммерциализацией эволюционных алгоритмов.

В 1970, благодаря в первую очередь руководству профессора Дональда Дэрхольта в государственном университете Нью-Мехико, было опубликовано более широкое исследование вычислений для эволюционного программирования, чем для любых других форм моделируемой эволюции. Большинство этих исследований использовали эволюционные программы для распознавания образов (Root, 1970; Корнетт, 1972; Lyle, 1972; Holmes, 1973; Trellue, 1973; Монтес, 1974; Атмар, 1976; Винсент, 1976; Вильямс, 1977; Dearholt, 1976). В качестве примера для распознавания использовались главным образом рукописные символы. В эксперименты включили параметры адаптивных мутаций. Работа Атмара (1976) — один из ранних примеров имитации эволюции в обстановке искусственной жизни. Атмар (1976), возможно, первый предложил и описал, как эволюционное программирование может быть рассчитано на то, что сейчас известно как «расширенная база оборудования». Ангелине и Поллак (1993) описали, как эволюционное программирование может быть использовано для развития компьютерных программ.

Гипотезы о виде зависимости целевой переменной от других переменных формулируются системой в виде программ на некотором внутреннем языке программирования. Если это универсальный язык, то теоретически на нем можно выразить зависимость любого вида. Процесс построения таких программ строится как эволюция в мире программ (этим метод немного похож на генетические алгоритмы). Если система находит программу, которая точно выражает искомую зависимость, она начинает вносить в нее небольшие модификации и отбирает среди построенных таким образом дочерних программ те, которые повышают точность. Система "выращивает" несколько генетических линий программ, конкурирующих между собой в точности нахождения искомой зависимости. Специальный транслирующий модуль, переводит найденные зависимости с внутреннего языка системы на понятный пользователю язык (математические формулы, таблицы и др.), делая их легкодоступными. Для того, чтобы сделать полученные результаты более понятными для пользователя-нематематика, существует большой арсенал разнообразных средств визуализации выявленных зависимостей.

Поиск зависимости целевых переменных от других проводится в форме функций какого-нибудь определенного вида. Например, в одном из наиболее удачных алгоритмов этого типа - методе группового учета аргументов (МГУА) зависимость ищут в форме полиномов. Причем сложные полиномы заменяются несколькими простыми, учитывающими лишь некоторые признаки (группы аргументов). Обычно используются попарные объединения признаков. Этот метод не имеет больших преимуществ по сравнению с нейронными сетями с готовым набором стандартных нелинейных функций, но, полученные формулы зависимости, в принципе, поддаются анализу и интерпретации (хотя на практике это все-таки сложно).

Современное эволюционное программирование

Изучение эволюционного программирования было продолжено в 1980-х в использовании произвольных представлений данных и применялось к обобщенной проблеме оптимизации. Эволюционное программирование, основанное на случайной изменчивости и отборе, было применено к таким структурам, как вещественные векторы (Фогель и Атмар, 1990; Фогель , 1990; Дэвис, 1994), перестановки (Фогель, 1998), матрицы (Фогель, 1993), векторы переменные длины (Фогель, 1990), бинарные строки (Фогель, 1989) и так далее. Дэвид Фогель (1988) представил форму отбора эволюционного программирования при помощи турнира. Фогель (1991, 1992) также выдвинул идею самостоятельной адаптации изменения параметров, в которых содержится информация о путях решения проблемы, а также информация о том, как создать потомство.

Области применения

Эволюционное программирование было применено к различным инженерным задачам, включая маршрутизацию трафика и планирование (Макдоннелл, 1997), фармацевтические дизайны (Дункан и Олсон, 1996; Фогель, 1996), эпидемиологию (Фогель , 1986), выявление рака (Фогель 1997, 1998), военное планирование (Фогель, 1993), системы управления (Чон, 1997), системы идентификации (Фогель, 1990), обработки сигналов (Порто, 1990), энергетику (Лай Ма, 1996), обучение в играх (Фогель и Бургин, 1969) и т. д.

Литература

См. также

Эволюционные алгоритмы

Просмотр этого шаблона Искусственный интеллект
Философия Тест Тьюринга • Китайская комната Nuvola apps Talk.PNG Портал
Направления Агентный подход • Адаптивное управление • Инженерия знаний • Модель жизнеспособной системы • Машинное обучение • Нейронные сети • Нечёткая логика • Обработка естественного языка • Распознавание образов • Роевой интеллект • Эволюционные алгоритмы • Экспертная система
Применение Голосовое управление • Задача классификации • Классификация документов • Кластеризация документов • Кластерный анализ • Локальный поиск • Машинный перевод • Оптическое распознавание символов • Распознавание речи • Распознавание рукописного ввода • Игровой ИИ
Исследователи Норберт Винер • Алан Тьюринг • В. М. Глушков • Г. С. Осипов • Д. Э. Попов • Д. А. Поспелов • М. Г. Гаазе-Рапопорт • Т. А. Гаврилова • В. Ф. Хорошевский • Г. С. Поспелов • Марвин Мински • Джон Маккарти • Фрэнк Розенблатт • Чарльз Бэббидж • Аллен Ньюэлл • Герберт Саймон • Ноам Хомский • Джуда Перл • Сеймур Паперт • Клод Шеннон • Джозеф Уайзенбаум • Патрик Винстон • В. К. Финн
Организации Государственный университет информатики и искусственного интеллекта • Singularity Institute for Artificial Intelligence