Вам бонус- начислено 1 монета за дневную активность. Сейчас у вас 1 монета

Эволюционное программирование и Эволюционные алгоритмы, эволюционные вычисления , пример генетического алгоритма

Лекция



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

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

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

эволюционные вычисления не гарантируют обнаружения глобального экстремума целевой функции (оптимального решения) за определенное время. Основное их преимущество в том, что они позволяют найти «хорошие» решения очень трудных задач за меньшее время, чем другие методы. Методы эволюционных вычислений оказались достаточно эффективными для решения ряда реальных задач инженерного проектирования, планирования, маршрутизации и размещения, управления портфелями ценных бумаг, прогнозирования, а также во многих других областях.
*Системы символьного обучения ориентированы на добычу знаний (англ. Data-mining), поиск скрытых правил и закономерностей в компьютерных базах данных (англ. Knowledge Discovery), автоматические рассуждения, доказательство теорем и т.д. Для последних систем задача (проблема) и относящаяся к ней информация описывается в виде логических аксиом. В дальнейшем система рассматривает различные варианты задачи как теоремы, которые следует доказать.
*В нейросетевых системах, построенных на принципах нервной системы биологических организмов, используются методы обучения, направленные на модификацию собственной структуры (структуры сети) и весовых коэффициентов связей между элементами.
*Эволюционные системы построены на принципах генетических и эволюционных процессов в природе, когда из набора кандидатов (популяции), получаемого посредством скрещивания и мутаций, по принятому критерию отбираются лучшие, наиболее приспособленные для решения задачи.
Основные направления эволюционных вычислений
  • эволюционное программирование;
  • эволюционные стратегии;
  • генетические алгоритмы.

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

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

В то время искусственный интеллект был ограничен двумя основными направлениями исследований: моделированием человеческого мозга (нейронные сети) и моделированием решения проблем поведения человека (эвристическое программирование). Альтернативный вариант, предусмотренный доктором Фогелем, должен был отказаться от моделирования конечного продукта эволюции, и, скорее, моделировать процесс эволюции, используя себя в качестве транспортного средства для получения разумного поведения (Фогель, 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. Классификационная схема (таксономия) эволюционных вычислений

эволюционные стратегия

*автор Инго Рехенберг, 1964 год
*каждая из альтернатив представляется вектором действительных чисел.
*В качестве мутации часто используется добавление нормально распределенной случайной величины к каждой компоненте вектора.
*параметры нормального распределения самоадаптируются в процессе выполнения алгоритма. Другой отличительной особенностью эволюционных стратегий является детерминированный отбор лучших особей из родителей и порожденных потомков без повторений

Виды эволюционных алгоритмов

  • генетические алгоритмы — эвристический алгоритм поиска, используемый для решения задач оптимизации и моделирования путем случайного подбора, комбинирования и вариации искомых параметров;
  • генетическое программирование — автоматическое создание или изменение программ с помощью генетических алгоритмов;
  • эволюционное программирование — аналогично генетическому программированию, но структура программы постоянна, изменяются только числовые значения;
  • программирование экспрессии генов
  • эволюционные стратегии — похожи на генетические алгоритмы, но в следующее поколение передаются только положительные мутации;
  • дифференциальная эволюция
  • нейроэволюция — аналогично генетическому программированию, но геномы представляют собой искусственные нейронные сети, в которых происходит эволюция весов при заданной топологии сети, или помимо эволюции весов также производится эволюция топологии;
  • системы классификаторов;

Основной (классический) генетический алгоритм (также называемый элементарным или простым генетическим алгоритмом) состоит из следующих шагов:

1) инициализация, или выбор исходной популяции хромосом;

2) оценка приспособленности хромосом в популяции;

3) проверка условия остановки алгоритма;

4) селекция хромосом;

5) применение генетических операторов;

6) формирование новой популяции;

7) выбор «наилучшей» хромосомы.

генетические алгоритмы

*автор Джон Холланд, 1975 год
*представление любой альтернативы решения в виде кодовой (как правило, битовой) строки фиксированной длины,
*манипуляции с которой производятся в отсутствие всякой связи с ее смысловой интерпретацией
*Ген (свойство) – атомарный элемент хромосомы. Об этом говорит сайт https://intellect.icu . Ген может быть битом, числом или неким другим объектом.
*Аппель – значение конкретного гена.
*Локус – положение конкретного гена в хромосоме.
*Хромосома (цепочка) – упорядоченная последовательность генов.
*Генотип (код) – упорядоченная последовательность хромосом.
*Особь (индивидуум) – конкретный экземпляр генотипа.
*Фенотип – аргумент (набор аргументов) целевой функции, соответствующий генотипу (т.е. интерпретация генотипа с точки зрения решаемой задачи).
*генотип состоит из одной хромосомы и представляется в виде битовой строки.
*Тогда ген – это бит;
*генотип (хромосома) – битовая строка, заданной размерности и с определенным положением битов; особь – конкретный набор битов (0 и 1).
*На каждом шаге работы генетический алгоритм использует несколько точек поиска решения одновременно.
*Совокупность этих точек является набором особей, который называется популяцией.
*Количество особей в популяции называют размером популяции.
На каждом шаге работы генетический алгоритм обновляет популяцию путем создания новых особей и уничтожения ненужных.
Чтобы отличать популяции на каждом из шагов и сами эти шаги, их называют поколениями и обычно идентифицируют по номеру.
популяция, полученная из исходной популяции после первого шага работы алгоритма, будет первым поколением, после следующего шага - вторым и т. д.
Генерация новых особей происходит на основе моделирования процесса размножения с помощью оператора скрещивания.
порождающие особи называются родителями,
порожденные - потомками.
Выбор родителей для скрещивания выполняется случайным образом.
При этом, один родитель может участвовать в нескольких скрещивания и необязательно, чтобы все родители участвовали в размножении.
выбор родителей выполняется случайным образом, то может получиться, что одна особь скрещивается сама с собой.
Родительская пара, как правило, порождает пару потомков. Непосредственная генерация новых кодовых строк из двух выбранных происходит за счет обмена между родителями случайно выбранными наборами генов
Моделирование процесса мутации новых особей осуществляется за счет работы оператора мутации, применяемого к случайно выбранным потомкам за счет изменения случайного выбранного гена.
размер популяции фиксирован, то порождение потомков должно сопровождаться уничтожением особей.
Выбор лучших («жизнеспособных») особей из числа родителей и потомков выполняется в операторе редукции, который уничтожает худшие («малоприспособленные») особи.
Основным правилом отбора является закон эволюции: «выживает сильнейший», который обеспечивает улучшение искомого решения. В некоторых источниках процесс приведения расширенной популяции к исходному размеру рассматривается не с точки зрения уничтожения худших особей (редукции), а с точки зрения выбора лучших.
Операторы скрещивания, мутации и редукции называют генетическими операторами. Скрещивание и мутация выполняются с использованием элементов случайности, а редукция - по строго детерминированным правилам.

Блок-схема основного генетического алгоритма изображена на рис. 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, что можно перевести как эволюционные вычисления.

К эволюционным алгоритмам также применяется понятие технология эволюционных вычислений. Можно добавить, что название генетические алгоритмы используется как в узком смысле, т.е. для обозначения классических генетических алгоритмов и их несущественных модификаций, так и в широком смысле - подразумевая любые эволюционные алгоритмы, значительно отличающиеся от «классики»

Критерий остановки работы генетического алгоритма

*- сформировано заданное число поколений;
*- исчерпано время, отведенное на эволюцию;
*- популяция достигла заданного качества (значение критерия одной (нескольких, всех) особей превысило заданный порог);
*- достигнут некоторый уровень сходимости (особи в популяции стали настолько подобными, что дальнейшее их улучшение происходит чрезвычайно медленно);

Пример работы генетического алгоритма при поиске максимума функции одной переменной

*Пусть имеется набор натуральных чисел от 0 до 31 и функция, определенная на этом наборе чисел, f(х) = х. Требуется найти максимальное значение функции. Задача, конечно, тривиальна и не требует применения столь изощренных методов поиска, но мы решаем ее лишь для иллюстрации работы генетического алгоритма
*В качестве кодовой строки использовать двоичное представление аргументов функции.
*Таким образом, ген - это отдельный бит строки, хромосома - последовательность битов (для чисел от 0 до 31 длина длина кодовой строки - 5 бит), генотип состоит из одной хромосомы (генотип = хромосома), фенотип - десятичное представление кодовой (битовой) строки (он же и является значением целевой функции).
*Определить некоторые характеристики генетического алгоритма. Пусть размер популяции будет 4 особи, число скрещиваний - 2, число мутаций - 1 на поколение. Процесс мутации заключается в инверсии одного из битов строки, выбирается случайно.
*случайным образом создана исходная популяция из четырех особей
Эволюционное программирование и Эволюционные алгоритмы, эволюционные вычисления , пример генетического алгоритма
*оператор отбора выбрал для производства потомков две пары строк (1, 2) и (2, 4). Работа оператора скрещивания

При этом в каждой паре разбиение на подстроки происходит независимо и случайным образом

Эволюционное программирование и Эволюционные алгоритмы, эволюционные вычисления , пример генетического алгоритма

*Пусть оператор мутации сработал для младшего бита потомка в строке 3 и данный код изменился с 10000 на 10001.
*Таким образом, популяция за счет порожденных потомков расширилась до восьми особей
Эволюционное программирование и Эволюционные алгоритмы, эволюционные вычисления , пример генетического алгоритма
*Оператор редукции далее сократит популяцию до исходного числа особей, исключив из нее те, значение целевой функции которых минимально.
* То есть будут исключены строки 1, 3, 4 и 5, и популяция первого поколения примет вид,
Эволюционное программирование и Эволюционные алгоритмы, эволюционные вычисления , пример генетического алгоритма
*даже за одну итерацию качество популяции значительно возросло. Если в исходной популяции среднее значение целевой функции было 10.75, а ее минимальное значение составляло 2, то в популяции первого поколения среднее значение возросло до 19, а минимальное значение составило 14. Лучшее же решение увеличилось с 18 до 27 при оптимальном решении 31.

Пример работы генетического алгоритма при поиске решения задачи коммивояжера

*Постановка задачи – коммивояжеру требуется посетить N городов. Для каждой пары городов по маршруту следования установлена стоимость (расстояние, время) проезда. Требуется найти путь минимальной стоимости, который начинается из некоторого города, обеспечивает посещение всех остальных городов ровно по одному разу и возврат в точку отправления.
Эволюционное программирование и Эволюционные алгоритмы, эволюционные вычисления , пример генетического алгоритма

Задача коммивояжера относиться к категории NP-полных задач, т.е. задач решаемых методов полного перебора всех вариантов

Формализация задачи

*Ген – число, характеризующее номер посещаемого города.
*Хромосома – строка из чисел длиной N, характеризующая порядок посещения городов.
*Генотип состоит из одной хромосомы.
*Фенотип - порядок посещения городов (совпадает с генотипом).
*Особь – конкретная строка из чисел (допустимый вариант решения задачи).
*Предположим N = 9.
*Особи «231586479» и «147523869» - примеры допустимых вариантов решения задачи.
*Классическое скрещивание приведет к генерации недопустимых вариантов, например
Эволюционное программирование и Эволюционные алгоритмы, эволюционные вычисления , пример генетического алгоритма
*потомках посещение некоторых городов будет дублироваться или проигнорировано.
*Рядом исследователей предложены различные варианты решения данной проблемы, в частности Л. Девис предлагает следующую модификацию оператора скрещивания.
*1) Случайным образом выбираются два сечения генотипа
*Р1 = 231 | 586 | 479
*Р2 = 147 | 523 | 869
*2) Для потомков копируются участки кода, расположенные между сечениями
*П1 = ххх | 586 | ххх
*П2 = ххх | 523 | ххх
*3) Из родителей генерируются вспомогательные строки, у которых участки кода циклически смещаются вправо.
*B1 = 479 231 586
*В2 = 869 147 523

*4) Свободные гены потомков последовательно заполняются генами из перекрестных вспомогательных строк с пропуском уже имеющихся в потомке генов
*П1 = 914 | 586 | 723
*П2 = 479 | 523 | 186
*Оператор мутации также может быть реализован различными способами, например:
*1) перестановка пары, случайным образом выбранных генов местами: 479523186 → 473529186;
*2) инверсия случайным образом выбранной последовательности генов: 479 | 523 | 186 → 479 | 325 | 186.

Основные отличия генетических алгоритмов от традиционных методов поиска решений

*1. Генетические алгоритмы работают с кодовыми строками, от которых зависят значения аргументов целевой функции и, соответственно, значение самой целевой функции. Интерпретация этих кодов выполняется только в операторе редукции. В остальном работа алгоритма не зависит от смысловой интерпретации кодов (фенотипа), т.е. никак не связана с сущностью (спецификой) рещаемой задачи.
*2. Для поиска лучшего решения генетический алгоритм на отдельном шаге использует сразу несколько точек поискового пространства (несколько вариантов решения задачи) одновременно, а не переходит от точки к точке, как это делается в традиционных методах математического программирования. Это позволяет преодолеть один из их недостатков - опасность попадания в локальный экстремум целевой функции, если она не является унимодальной (т.е. имеет несколько экстремумов). Использование нескольких точек одновременно значительно снижает такую возможность.
*3. Генетический алгоритм использует как вероятностные правила для порождения новых точек для анализа, так и детерминированные для перехода от одних точек к другим

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

Изучение эволюционного программирования было продолжено в 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 пытается смоделировать макроэволюционную динамику.

Вау!! 😲 Ты еще не читал? Это зря!

А как ты думаешь, при улучшении эволюционное программирование, будет лучше нам? Надеюсь, что теперь ты понял что такое эволюционное программирование, эволюционные алгоритмы, эволюционные вычисления и для чего все это нужно, а если не понял, или есть замечания, то не стесняйся, пиши или спрашивай в комментариях, с удовольствием отвечу. Для того чтобы глубже понять настоятельно рекомендую изучить всю информацию из категории Эволюционные алгоритмы

создано: 2014-08-20
обновлено: 2021-12-18
132699



Рейтиг 7 of 10. count vote: 3
Вы довольны ?:


Найди готовое или заработай

С нашими удобными сервисами без комиссии*

Как это работает? | Узнать цену?

Найти исполнителя
$0 / весь год.
  • У вас есть задание, но нет времени его делать
  • Вы хотите найти профессионала для выплнения задания
  • Возможно примерение функции гаранта на сделку
  • Приорететная поддержка
  • идеально подходит для студентов, у которых нет времени для решения заданий
Готовое решение
$0 / весь год.
  • Вы можите продать(исполнителем) или купить(заказчиком) готовое решение
  • Вам предоставят готовое решение
  • Будет предоставлено в минимальные сроки т.к. задание уже готовое
  • Вы получите базовую гарантию 8 дней
  • Вы можете заработать на материалах
  • подходит как для студентов так и для преподавателей
Я исполнитель
$0 / весь год.
  • Вы профессионал своего дела
  • У вас есть опыт и желание зарабатывать
  • Вы хотите помочь в решении задач или написании работ
  • Возможно примерение функции гаранта на сделку
  • подходит для опытных студентов так и для преподавателей



Комментарии


Оставить комментарий
Если у вас есть какое-либо предложение, идея, благодарность или комментарий, не стесняйтесь писать. Мы очень ценим отзывы и рады услышать ваше мнение.
To reply

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

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