Лекция
Сразу хочу сказать, что здесь никакой воды про эволюционное программирование, и только нужная информация. Для того чтобы лучше понимать что такое эволюционное программирование, эволюционные алгоритмы, эволюционные вычисления , настоятельно рекомендую прочитать все из категории Эволюционные алгоритмы.
эволюционное программирование было изобретено доктором Лоуренсом Дж. Фогелем в Национальном Научном Фонде в 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) описали, как эволюционное программирование может быть использовано для развития компьютерных программ.
Гипотезы о виде зависимости целевой переменной от других переменных формулируются системой в виде программ на некотором внутреннем языке программирования. Если это универсальный язык, то теоретически на нем можно выразить зависимость любого вида. Процесс построения таких программ строится как эволюция в мире программ (этим метод немного похож на генетические алгоритмы). Если система находит программу, которая точно выражает искомую зависимость, она начинает вносить в нее небольшие модификации и отбирает среди построенных таким образом дочерних программ те, которые повышают точность. Система "выращивает" несколько генетических линий программ, конкурирующих между собой в точности нахождения искомой зависимости. Специальный транслирующий модуль, переводит найденные зависимости с внутреннего языка системы на понятный пользователю язык (математические формулы, таблицы и др.), делая их легкодоступными. Для того, чтобы сделать полученные результаты более понятными для пользователя-нематематика, существует большой арсенал разнообразных средств визуализации выявленных зависимостей.
Поиск зависимости целевых переменных от других проводится в форме функций какого-нибудь определенного вида. Например, в одном из наиболее удачных алгоритмов этого типа - методе группового учета аргументов (МГУА) зависимость ищут в форме полиномов. Причем сложные полиномы заменяются несколькими простыми, учитывающими лишь некоторые признаки (группы аргументов). Обычно используются попарные объединения признаков. Этот метод не имеет больших преимуществ по сравнению с нейронными сетями с готовым набором стандартных нелинейных функций, но, полученные формулы зависимости, в принципе, поддаются анализу и интерпретации (хотя на практике это все-таки сложно).
Рис. 1. Классификационная схема (таксономия) эволюционных вычислений
Основной (классический) генетический алгоритм (также называемый элементарным или простым генетическим алгоритмом) состоит из следующих шагов:
1) инициализация, или выбор исходной популяции хромосом;
2) оценка приспособленности хромосом в популяции;
3) проверка условия остановки алгоритма;
4) селекция хромосом;
5) применение генетических операторов;
6) формирование новой популяции;
7) выбор «наилучшей» хромосомы.
Блок-схема основного генетического алгоритма изображена на рис. 4.3. Рассмотрим конкретные этапы этого алгоритма более подробно с использованием дополнительных подробностей, представленных на рис. 4.4.
Рис. 4.3. Блок-схема генетического алгоритма.
Последовательность работы генетического алгоритма
Рис. 4.4. Схема выполнения генетического алгоритма.
Все они моделируют базовые положения в теории биологической эволюции — процессы отбора, мутации и воспроизводства. Поведение агентов определяется окружающей средой. Множество агентов принято называть популяцией. Такая популяция эволюционирует в соответствии с правилами отбора в соответствии с целевой функцией, задаваемой окружающей средой. Таким образом, каждому агенту (индивидууму) популяции назначается значение его пригодности в окружающей среде. Размножаются только наиболее пригодные виды. Рекомбинация и мутация позволяют изменяться агентам и приспособляться к среде. Такие алгоритмы относятся к адаптивным поисковым механизмам.
Эволюционные алгоритмы успешно использовались для задач типа функциональной оптимизации и могут легко быть описаны на математическом языке.
Эволюционные программы можно считать обобщением генетических алгоритмов. Классический генетический алгоритм выполняется при фиксированной длине двоичных последовательностей и в нем применяются операторы скрещивания и мутации Эволюционные программы обрабатывают более сложные структуры (не только двоичные коды) и могут выполнять иные «генетические» операции. Например, эволюционные стратегии могут трактоваться в качестве эволюционных программ, в которых хромосомы представляются вещественными (не двоичными) числами, а мутация используется как единственная генетическая операция.
Структуру эволюционной программы довольно точно отображает блок-схема, приведенная на рис. 4.3. Она совпадает со структурой генетического алгоритма, поскольку идеи эволюционной программы целиком заимствованы из теории генетических алгоритмов. Различия имеют глубинный характер, они касаются способов представления хромосом и реализации генетических операторов. Эволюционные программы допускают большее разнообразие структур данных, поскольку возможно не только двоичное кодирование хромосом, а также предоставляют расширенный набор генетических операторов.
Согласно З. Михалевичу [33], эволюционная программа - это вероятностный алгоритм, применяемый на -й итерации к популяции особей
.
Каждая особь представляет потенциальное решение задачи, которое в произвольной эволюционной программе может отображаться некоторой (в том числе и достаточно сложной) структурой данных . Любое решение оценивается по значению его «приспособленности». Далее в процессе селекции на -й итерации из наиболее приспособленных особей формируется очередная популяция. Некоторые особи этой новой популяции трансформируются с помощью «генетических операторов», что позволяет получать новые решения. Существуют преобразования (типа мутации), которые изменяют конкретные хромосомы , а также трансформации более высокого порядка (типа скрещивания), создающие новые особи путем комбинирования фрагментов нескольких (двух или более) хромосом, т.е. . От эволюционной программы ожидается, что после смены некоторого количества поколений наилучшая особь будет представлять решение, близкое к оптимальному. Структура эволюционной программы может быть представлена в виде псевдокода [33] так, как это изображено на рис. 4.65 (рекомендуется сравнить ее с рис. 4.3).
Рис. 4.65. Представление эволюционной программы в виде псевдокода.
Рассмотрим обобщенный пример эволюционной программы [33]. Допустим, что ищется граф, который удовлетворяет определенным ограничениям (например, производится поиск топологии коммуникационной сети, оптимальной по конкретным критериям, например, по стоимости передачи и т.п.). Каждая особь в эволюционной программе представляет одно из потенциальных решений, т.е. в данном случае некоторый граф. Исходная популяция графов , формируемая случайным образом либо создаваемая при реализации какого-либо эвристического процесса, считается отправной точкой эволюционной программы. Функция приспособленности, которая обычно задается, связана с системой ограничений решаемой задачи. Эта функция определяет «приспособленность» каждого графа путем выявления «лучших» и «худших» особей. Можно предложить несколько различных операторов мутации, предназначенных для трансформации отдельных графов, и несколько операторов скрещивания, которые будут создавать новый граф в результате рекомбинации структур двух или более графов. Очень часто такие операторы обусловливаются характером решаемой задачи. Например, если ищется граф типа «дерево», то можно предложить оператор мутации, который удаляет ветвь из одного графа и добавляет новую ветвь, объединяющую два отдельных подграфа. Другие возможности заключаются в проектировании мутации независимо от семантики задачи, но с включением в функцию приспособленности дополнительных ограничений - «штрафов» для тех графов, которые не являются деревьями.
Принципиальную разницу между классическим генетическим алгоритмом и эволюционной программой, т.е. эволюционным алгоритмом в широком смысле, иллюстрируют рис. 4.66 и 4.67.
Рис. 4.66. Решение задачи с помощью классического генетического алгоритма.
Рис. 4.67. Решение задачи с помощью эволюционного алгоритма (эволюционной программы).
Классический генетический алгоритм, который оперирует двоичными последовательностями, требует представить решаемую задачу в строго определенном виде (соответствие между потенциальными решениями и двоичными кодами, декодирование и т.п.). Сделать это не всегда просто.
Эволюционные программы могут оставить постановку задачи в неизменном виде за счет модификации хромосом, представляющих потенциальные решения (с использованием «естественных» структур данных), и применения соответствующих «генетических» операторов.
Другими словами, для решения нетривиальной задачи можно либо преобразовать ее к виду, требуемому для использования генетического алгоритма (рис. 4.66), либо модифицировать генетический алгоритм так, чтобы он удовлетворял задаче (рис. 4.67). При реализации первого подхода применяется классический генетический алгоритм, а при реализации второго подхода - эволюционная программа. Таким образом, модифицированные генетические алгоритмы можно в общем случае называть эволюционными программами [33]. Однако чаще всего встречается термин эволюционные алгоритмы. Эволюционные программы также могут рассматриваться как эволюционные алгоритмы, подготовленные программистом для выполнения на компьютере. Основная задача программиста заключается при этом в выборе соответствующих структур данных и «генетических» операторов. Именно такая трактовка понятия эволюционная программа представляется наиболее обоснованной.
Все понятия, применяемые в настоящем разделе и относящиеся главным образом к методам, основанным на эволюционном подходе, можно сопоставить главному направлению исследований - компьютерному моделированию эволюционных процессов. Эта область информатики называется Evolutionary Computation, что можно перевести как эволюционные вычисления.
К эволюционным алгоритмам также применяется понятие технология эволюционных вычислений. Можно добавить, что название генетические алгоритмы используется как в узком смысле, т.е. для обозначения классических генетических алгоритмов и их несущественных модификаций, так и в широком смысле - подразумевая любые эволюционные алгоритмы, значительно отличающиеся от «классики»
При этом в каждой паре разбиение на подстроки происходит независимо и случайным образом
Пример работы генетического алгоритма при поиске решения задачи коммивояжера
Задача коммивояжера относиться к категории NP-полных задач, т.е. задач решаемых методов полного перебора всех вариантов
Формализация задачи
Изучение эволюционного программирования было продолжено в 1980-х в использовании произвольных представлений данных и применялось к обобщенной проблеме оптимизации. Эволюционное программирование, основанное на случайной изменчивости и отборе, было применено к таким структурам, как вещественные векторы (Фогель и Атмар, 1990; Фогель , 1990; Дэвис, 1994), перестановки (Фогель, 1998), матрицы (Фогель, 1993), векторы переменной длины (Фогель, 1990), бинарные строки (Фогель, 1989) и так далее. Дэвид Фогель (1988) представил форму отбора эволюционного программирования при помощи турнира. Фогель (1991, 1992) также выдвинул идею самостоятельной адаптации изменения параметров, в которых содержится информация о путях решения проблемы, а также информация о том, как создать потомство.
Эволюционное программирование было применено к различным инженерным задачам, включая маршрутизацию трафика и планирование (Макдоннелл, 1997), фармацевтические дизайны (Дункан и Олсон, 1996; Фогель, 1996), эпидемиологию (Фогель , 1986), выявление рака (Фогель 1997, 1998), военное планирование (Фогель, 1993), системы управления (Чон, 1997), системы идентификации (Фогель, 1990), обработки сигналов (Порто, 1990), энергетику (Лай Ма, 1996), обучение в играх (Фогель и Бургин, 1969) и т. д.
Эволюционные алгоритмы используются при комбинаторной оптимизации, в частности при решении классических NP-полных проблем, таких как задача коммивояжера, задача упаковки ранца, разбитие чисел, максимально независимое множество и зарисовка графов.
Возможность использования эволюционных алгоритмов в музыке активно исследуется в Австрии, в первую очередь при попытках моделирования игры на музыкальных инструментах известными людьми разных эпох.
В 2020 году Google заявил, что их AutoML-Zero может успешно заново открыть для себя классические алгоритмы, такие как концепция нейронных сетей. [12]
Компьютерное моделирование Tierra и Avida пытается смоделировать макроэволюционную динамику.
А как ты думаешь, при улучшении эволюционное программирование, будет лучше нам? Надеюсь, что теперь ты понял что такое эволюционное программирование, эволюционные алгоритмы, эволюционные вычисления и для чего все это нужно, а если не понял, или есть замечания, то не стесняйся, пиши или спрашивай в комментариях, с удовольствием отвечу. Для того чтобы глубже понять настоятельно рекомендую изучить всю информацию из категории Эволюционные алгоритмы
Комментарии
Оставить комментарий
Эволюционные алгоритмы
Термины: Эволюционные алгоритмы