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

редактировать
Конкурентный алгоритм поиска проблемного пространства

Антенна космического корабля NASA ST5 2006 года. Эта сложная форма была найдена программой компьютерного дизайна для создания наилучшей диаграммы направленности. Он как известен эволюционировавшая антенна.

В информатике и исследование операций, генетический алгоритм (GA) является метаэвристическим вдохновлены системой естественного отбора, который принадлежит к более широкому классу эволюционных алгоритмов (EA). Генетические алгоритмы обычно используются для создания надежных решений оптимизации и проблем поиска, используя биологически вдохновленные, такие как мутация, кроссовер и выбор.

Содержание

  • 1 Методология
    • 1.1 Проблемы оптимизации
      • 1.1.1 Инициализация
      • 1.1.2 Выбор
      • 1.1.3 Генетические операторы
      • 1.1.4 Эвристика
      • 1.1.5 Завершение
  • 2 Гипотического строительного блока
  • 3 Ограничения
  • 4 Варианты
    • 4.1 Представление хромосом
    • 4.2 Элитарность
    • 4.3 Параллельные реализации
    • 4.4 Адаптивные ГА
  • 5 Проблемные области
  • 6 История
    • 6.1 Коммерческие продукты
  • 7 Связанные методы
    • 7.1 Родительские поля
    • 7.2 Связанные поля
      • 7.2.1 Эволюционные алгоритмы
      • 7.2.2 Интеллект роя
      • 7.2. 3 Другие алгоритмы эволюционных вычислений
      • 7.2.4 Другие метаэвристические методы
      • 7.2.5 Другие методы стохастической оптимизации
  • 8 См.
  • 9 Ссылки
  • 10 Библиография
  • 11 Внешние ссылки
    • 11,1 Ресурсы
    • 11.2 Обучающие программы

Методология

Проблемы оптимизации

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

Эволюция обычно начинается с популяции случайно сгенерированных индивидуумов и представляет собой итерационный процесс, с популяцией в каждой итерации, называемой поколением. В каждом поколении оценивается приспособление каждого человека в популяции; приспособленность обычно представляет собой значение целевые функции в решаемой задаче оптимизации. Более подходящие люди стохастически выбирают из текущей популяции, и геном каждого индивидуума модифицируется (рекомбинируется и, возможно, случайным образом мутируется), чтобы сформировать новое поколение. Новое поколение методов решений используется в следующей итерации алгоритма . Обычно алгоритм завершается, когда либо было произведено максимальное количество поколений, либо был достигнут удовлетворительный уровень приспособления для настройки.

Типичный генетический алгоритм требует:

  1. a генетического представления области решения,
  2. a функции приспособленности для оценки области решения.

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

. После определения генетического представления и функции переходит к инициализации совокупности решений, а затем к ее улучшению путем повторного применения операционной мутации, кроссовера, инверсии и отбора.

Инициализация

Размер популяции зависит от характера проблемы, но обычно содержит несколько сотен или тысяч агентов решений. Часто начальная совокупность генерируется случайным образом, что позволяет использовать весь механизм поиска (область поиска ). Иногда решения могут быть «посеяны» в тех областях, где, вероятно, будут найдены оптимальные решения.

Выбор

В течение каждого последующего поколения часть существующей популяции выбирается для выведения нового поколения. Индивидуальные решения выбираются с помощью процесса, основанного на пригодности, где решения установщика (измеряемые функции приспособленности ) обычно более вероятны. Некоторые методы отбора оценивают пригодность каждого решения и предпочтительно выбирают лучшие решения. Другие методы оценивают только случайную выборку генеральной совокупности, поскольку первый процесс может занять очень много времени.

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

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

Генетические операторы

Следующим шагом является создание популяции решений второго поколения из выбранных с помощью комбинации генетических операторов : кроссовер (также называемая рекомбинацией) и мутация.

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

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

Мнения по поводу важности кроссовера по сравнению с мутацией разделились. В Fogel (2006) есть много полезных документов, подтверждающих поиск на основе мутаций.

Хотя кроссовер и мутация известны как основные генетические операторы, в генетических алгоритмах можно использовать другие операторы, такие как перегруппировка, колонизация-вымирание или миграция.

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

Эвристика

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

Прекращение

Этот процесс генерации повторяется до тех пор, пока не будет достигнуто условие прекращения. Общие условия завершения:

  • Найдено решение, которое удовлетворяет минимальным критериям
  • Достигнуто фиксированное количество поколений
  • Достигнутый выделенный бюджет (время / деньги вычислений)
  • Наивысший соответствие решения ранжирования вычислений или достигло плато, так что последовательные итерации больше не дают лучших результатов
  • Ручная проверка
  • Комбинации вышеперечисленных

Гипотеза строительных блоков

Генетические алгоритмы легко реализовать, но их поведение сложно понять. В частности, трудно понять, почему эти алгоритмы часто преуспевают в создании решений высокой пригодности при применении к практическим задачам. Гипотеза строительных блоков (BBH) из:

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

Голдберг представлен эвристику следующим образом:

«Выбирают короткие, низкоуровневые и хорошо подходящие схемы, рекомбинируют [пересекаются] и повторно дискретизируют, чтобы сформировать строки с более высокой пригодностью. В некотором смысле, используемом с указанными конкретными схемами [строительными блоками], мы снизили сложность нашей проблемы; вместо того, чтобы строить высокие - строки производительности, пробуя все мыслимые комбинации, мы конструируем все более и более совершенные строки из лучших частичных решений прошлых выборок.
«Рабочие места для работы с малыми точками». Так и генетический алгоритм стремится к почти оптимальной производительности сопоставления коротких, низкоуровневых, высокопроизводительных схем или строительных блоков. "

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

Ограничения

Существуют ограничения использования генетического алгоритма по сравнению с альтернативными алгоритмами оптимизации:

  • Повторяющаяся функция пригодности оценка сложных задач часто является наиболее запретительным и ограничивающим сегментом искусственных эволюционных алгоритмов Поиск о птимального решения сложных многомодальных задач большой размерности часто требует очень дорогих вычислений функции пригодности. В реальных задачах, таких как задачи оптимизации конструкции, могут потребоваться отдельные функции от нескольких часов до нескольких дней полного моделирования. Обычные методы оптимизации не могут справиться с такими проблемами. В этом случае может потребоваться использование от точной оценки и использовать приблизительную пригодность. Очевидно, что объединение приближенных моделей может быть одним из наиболее многообещающих подходов к убедительному использованию ГА для решения сложных реальных проблем.
  • Генетические алгоритмы плохо масштабируются со сложностью. То есть там, где количество элементов, подвергшихся мутации, велико, часто встречается экспоненциальное увеличение размера пространства поиска. Это делает очень трудным использование этой техники для решения таких задач, как проектирование двигателя, дома или самолета. Чтобы сделать такие проблемы доступными для эволюционного поиска, они должны быть разбиты на простейшее представление. Следовательно, мы обычно видим эволюционные алгоритмы, кодирующие конструкции лопастей вентилятора вместо двигателей, формы зданий вместо подробных строительных планов и аэродинамические поверхности вместо целых конструкций самолетов. Вторая проблема сложности - это вопрос о том, как защитить части, которые превратились в хорошие решения, особенно когда их пригодность требует, чтобы они сочетались с другими частями.
  • «Лучшее» решение только по сравнению с другими решениями. В результате успеха остановки не ясен для каждой проблемы.
  • Во многих задачах ГА проблемы тенденцию сходиться к локальным оптимумам или произвольным точкам, а не к глобальным другим. Это означает, что он «не умеет» жертвовать краткосрочной пригодностью, чтобы обрести более долгосрочную. Вероятность этого зависит от формы ландшафта пригодности : одни проблемы могут обеспечить легкий подъем к глобальному оптиму, другие облегчить функции поиска локальных оптимумов. Эту проблему можно облегчить, используя разнообразную совокупность решений, хотя теорема о запрете бесплатного обеда доказывает, что решения общего не существует. к этой проблеме. Распространение увеличения численности группы поддержки расширяется, увеличивая возможности увеличения численности группы, увеличивающей размер (менее похожие), воспроизводя в популяции. Однако этот прием может оказаться неэффективным в зависимости от характера проблемы. Другой возможный метод - просто заменить часть населения, созданного случайно, другим, похожа на друга. Разнообразие важно в генетических алгоритмах (и генетическом программировании ), потому что скрещивание однородной популяции не дает новых решений. В стратегиях эволюции и эволюционном программировании разнообразие не является существенным из-за большей зависимости от мутаций.
  • Работа с динамическими наборами данных затруднена, поскольку геномы начинают сходиться на раннем этапе решениям, которые больше не используются для более поздних данных. Было предложено несколько способов исправить это, каким-то увеличенным генетическим разнообразием и предотвратить раннюю конвергенцию, либо методом увеличения вероятности мутации, либо путем временного введения совершенно новых, случайно сгенерированных элементов в генофонд. (так называемые случайные иммигранты). Опять же, стратегии эволюции и эволюционное программирование могут быть реализованы с помощью так называемой «стратегии запятой», в которой родители не поддерживаются, а новые родители выбираются только из потомства. Это может быть более эффективным при решении динамических задач.
  • ГА не могут эффективно решать задачи, в которых единственной мерой пригодности является единственная правильная / неправильная оценка (например, задачи принятия решений ), поскольку нет способа сходиться на решении (нет холма для подъема). В этих случаях случайный поиск может найти решение так же быстро, как и GA. Однако, если ситуация позволяет повторить успешное / неудачное испытание, давая (возможно) разные результаты, то отношение успехов к неудачам обеспечивает подходящую меру пригодности.
  • Для конкретных задач оптимизации и примеров проблем, другие варианты оптимизации алгоритмы могут быть более эффективными, чем генетические алгоритмы, с точки зрения скорости сходимости. Альтернативные и дополнительные алгоритмы включают стратегии эволюции, эволюционное программирование, моделирование отжига, гауссову адаптацию, восхождение на холм, и интеллект роя (например: оптимизация муравьиных колоний, оптимизация роя частиц ) и методы, основанные на целочисленном линейном программировании. Пригодность генетических алгоритмов зависит от объема знаний о проблеме; Для хорошо известных проблем часто используются более специализированные подходы.

Варианты

Представление хромосомы

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

Когда используются представления целых чисел в виде битовой строки, часто используется кодировка Грея. Таким образом, на небольшие изменения целого числа можно легко повлиять посредством мутаций или кроссоверов. Было обнаружено, что это помогает предотвратить преждевременную конвергенцию на так называемых стенках Хэмминга, в которых должно произойти слишком много одновременных мутаций (или событий кроссовера), чтобы изменить хромосому на лучшее решение.

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

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

Элитизм

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

Параллельные реализации

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

Адаптивные ГА

Генетические алгоритмы с адаптивными функциями (адаптивные генетические алгоритмы, AGA) - еще один важный и многообещающий вариант генетических алгоритмов. Вероятности кроссовера (pc) и мутации (pm) во многом определяют точность решения и скорость сходимости, которую можно получить генетические алгоритмы. Вместо использования фиксированных значений pc и pm, AGA использует информацию о населении и адаптивно корректирует pc и pm для поддержания разнообразия населения, а также для поддержания возможностей конвергенции. В AGA (адаптивном генетическом алгоритме) корректировка pc и pm зависит от значений пригодности решений. В CAGA (адаптивный алгоритм алгоритма на основе кластеризации), благодаря использованию кластерного анализа для оценки оптимизации оптимизации, pc и pm зависит от этих состояний оптимизации. Комбинирование ГА с другими методами оптимизации может быть эффективным быть эффективным. GA, как правило, довольно хорош в поиске хороших глобальных решений, но довольно неэффективен в поиске нескольких мутаций, чтобы найти абсолютный оптимум. Другие методы (такие как простоехождение на холм ) довольно эффективны при поиске абсолютного оптимума в ограниченной области. Чередование GA и восхождения на холм может повысить GA, преодололевая эффективность при недостаточной устойчивости восхождения на холм.

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

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

Был разработан ряд вариантов, чтобы попытаться улучшить производительность при решении задачи с высокой степенью пригодности эпистаза, то есть где пригодность решения из участвующих подмножеств его размер. Такие алгоритмы нацелены на изучение (до использования) этих полезных фенотипических взаимодействий. Таким образом, они согласуются с гипотезой о строительных блоках в адаптивном снижении деструктивной рекомбинации. Яркие примеры этого подхода включают mGA, GEMGA и LLGA.

Проблемные области

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

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

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

В своем Руководстве по разработке алгоритмов Скиена советует не использовать генетические алгоритмы для любых задач:

[Я] довольно неестественно моделировать приложения в терминах генетических операторов, таких как мутация и кроссовер на битах. струны. Псевдобиология материн еще один уровень сложности между вами и вашей проблемой. Во-вторых, алгоритмах алгоритма требуется очень много времени для решений нетривиальных задач. [...] [Т] аналогия с эволюцией - где для значительного прогресса требуются [sic] миллионы лет - может быть вполне уместной.

[...]

Я никогда не сталкивался с проблемой, где генетические алгоритмы казались мне правильным способом ее решения. Кроме того, я никогда не видел каких-либо результатов вычислений с использованием генетических алгоритмов, которые произвели бы на меня благоприятное впечатление. Придерживайтесь моделированного отжига для ваших нужд эвристического поиска вуду.

— Стивен Скиена

История

В 1950 году Алан Тьюринг использует «обучающую машину», которая будет соответствовать принципам эволюции. Компьютерное моделирование эволюции началось еще в 1954 году с работы Нильса Алла Барричелли, используя который компьютер в Институте перспективных исследований в Принстоне, Нью-Джерси. Его публикация 1954 года не получила широкого распространения. Начиная с 1957 года, австралийский специалист по количественной генетике Алекс Фрейзер опубликовал серию работ по моделированию искусственного отбора организмов с множественными локусами, контролируемыми измеримым признаком. С тех пор компьютерное моделирование эволюции биологами стало более распространенным в начале 1960-х годов, а методы были методами в книгах Фрейзера и Бернелла (1970) и Кросби (1973). Моделирование Фрейзера включало все основные элементы современных генетических алгоритмов. Ханс-Иоахим Бреманн опубликовал в 1960-х годах серию статей, включая совокупность решений проблем оптимизации, подвергшихся рекомбинации, мутации и отбору. Исследования Бремерманна также включали элементы современных генетических алгоритмов. Среди других заслуживающих внимания пионеров - Ричард Фридберг, Джордж Фридман и Майкл Конрад. Многие ранние статьи перепечатаны Фогелем (1998).

Хотя Барричелли в своей работе 1963 года смоделировал эволюцию способности играть в простую игру, искусственная эволюция Метод стал широко признанным методом оптимизации только в результате работы Инго Рехенберга и Ханса-Пауля Швефеля в 1960-х и начале 1970-х годов - группе Рехенберга удалось решить сложные инженерные проблемы через стратегии развития. Другим подходом была техника эволюционного программирования Лоуренса Дж. Фогеля, которая была предложена для создания искусственного интеллекта. Эволюционное программирование использовало конечные автоматы для прогнозирования среды и использовало варианты и выбор для оптимизации логики прогнозирования. Генетические алгоритмы, в частности, стали популярными благодаря работам Джона Холланда в начале 1970-х годов и в особенности его книги «Адаптация в естественных и искусственных системах» (1975). Его работа началась с исследований клеточных автоматов, проведенных Холландом и его студентами в Мичиганском университете. Холланд представил формулизованную основу для прогнозирования качества следующего поколения, известную как теорема схемы Холланда. Исследования были проведены в основном теоретическими до середины 1980-х, когда в Питтсбурге, штат Пенсильвания, была проведена Первая международная конференция по генетическим алгоритмам..

Коммерческие продукты

В конце 1980-х General Electric начала продавать первый в мире продукт на основе генетического алгоритма, набор инструментов на базе мэйнфреймов, предназначенный для промышленных процессов. В 1989 г. компания Axcelis, Inc. выпустила Evolver, первый в мире коммерческий продукт общего назначения для настольных компьютеров. The New York Times технический писатель Джон Маркофф писал об Evolver в 1990 году, и он оставался единственным интерактивным коммерческим генетическим алгоритмом до 1995 года. Evolver был продан Palisade в 1997 году, переведен на несколько языков, и в настоящее время находится в его 6-й версии. С 1990-х годов в MATLAB были встроены три эвристических оптимизации без производных (имитация отжига, оптимизация роя частиц, генетический алгоритм) и два алгоритма прямого поиска (симплексный поиск, поиск по шаблону)).

Связанные методы

Родительские поля

Генетические алгоритмы являются подполем:

Связанные области

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

Эволюционные алгоритмы - это подполе эволюционных вычислений.

  • Стратегии эволюции (ES, см. Rechenberg, 1994) развивают людей посредством мутации и промежуточной или дискретной рекомбинации. Алгоритмы ES разработаны специально для решения проблем в реальной области. Они используют самоадаптацию для настройки параметров управления поиском. Дерандомизация самоадаптации привела к современной эволюции адаптации ковариационной матрицы (CMA-ES ).
  • Эволюционное программирование (EP), включающее популяции решений, в первую очередь, с мутацией и отбором, а также произвольным программированием. -адаптация для настройки параметров и может включать другие вариативные операции, такие как объединение информации от нескольких родителей.
  • Алгоритм оценки распределения (EDA) заменяет традиционные операторы воспроизведения операторами, управляемыми моделями. Такие модели изучаются у населения с использованием методов машинного обучения и представленных в виде вероятностных графических моделей, из которых могут быть взяты образцы или сгенерированы новые решения путем управляемого кроссовера.
  • Программирование экспрессии генов (GEP) также использует совокупность компьютерных программ. Эти сложные компьютерные программы являются закодированы в более простые линейные хромосомы фиксированной длины, которые впоследствии выражаются в виде деревьев выражений. Дерево выражений Программы или компьютерные программы развиваются, потому что хромосомы подвергаются мутации и рекомбинации аналогично каноническому GA. Но благодаря особой организации хромосом GEP эти генетические модификации всегда приводят к действительным компьютерным программам.
  • Генетическое программирование (GP) - это родственная техника, популяризированная Джоном Козой, в которой компьютерные программы, оптимизированы не параметры функции. В генетическом программировании часто используются древовидные внутренние структуры данных для представления компьютерных программ для адаптации вместо списков структур, типичных для генетических алгоритмов.
  • (GGA) - это эволюция GA, в которой фокус смещается с отдельных элементов, как в классических GA, на группы или подмножества элементов. Идея, лежащая в основе этой эволюции GA, заключается в том, что решение некоторых сложных проблем, таких как задачи кластеризации или разделения, где набор элементов должен быть оптимальным образом разделен на непересекающиеся группы элементов, лучше всего будет достигаться путем создания характеристик групп элементов эквивалент генов. К таким проблемам относятся упаковка бункеров, балансировка линий, кластеризация по отношению к измерению расстояния, равные сваи и т. Д., На которых классические ГА показали плохие результаты. Приведение генов к группам подразумевает наличие хромосом переменной длины и специальных генетических операторов, управляющих целыми группами элементов. В частности, для упаковки в контейнеры GGA, гибридизированный с критерием доминирования Мартелло и Тота, возможно, является лучшим методом на сегодняшний день.
  • Интерактивные эволюционные алгоритмы - это эволюционные алгоритмы, использующие человеческую оценку. Обычно они применяются в тех областях, где сложно разработать функцию вычислительной пригодности, например, развитие изображений, музыки, художественного дизайна и форм в соответствии с эстетическими предпочтениями пользователей.

Интеллект роя

Интеллект роя - это подполе эволюционных вычислений.

  • Ant Оптимизация колонии (ACO ) использует множество муравьев (или агентов), оснащенных феромонной моделью, для пересечения пространств решений и поиска локальных продуктивных продуктов. Считается, что алгоритм оценки распределения,
  • Оптимизация роя частиц (PSO) - это вычислительный метод для многопараметрической оптимизации, который также использует популяционный подход. Популяция (рой) влияет на наиболее известное положение в мире. Подобно генетическим алгоритмам, метод PSO зависит от обмена информацией между населением. В некоторых задачах PSO часто более вычислительно эффективен, чем GA, особенно в неограниченных задачах с непрерывными переменными.

Другие алгоритмы эволюционных вычислений

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

  • - это эволюционный алгоритм, моделирующий явление потока электронов и электропроводности. Некоторые текущие исследования показывают, что Electimize более эффективен в решении сложных сложных задач оптимизации, чем традиционные эволюционные алгоритмы. Алгоритм расширенного масштабного поиска пространств и определения глобальных оптимальных альтернатив. В отличие от других эволюционных алгоритмов, Electimize независимо оценивает качество значений в строке решения.
  • Меметический метод алгоритма (MA), часто называемый, среди прочего, гибридным генетическим алгоритмом, это популяционный алгоритм, в котором решения также подлежат этапам. локального улучшения. Идея меметических алгоритмов исходит от мемов, которые, в отличие от генов, могут приспосабливаться. Показано, что в некоторых проблемных областях они более эффективны, чем традиционные эволюционные алгоритмы.
  • (BA), вдохновленные эволюционной экологией и, в частности, бактериологической адаптацией. Эволюционная - это изучение живых организмов в контексте их окружающей среды с целью того, как они адаптируются. Его основная концепция заключается в том, что в неоднородной среде одного человека, который подходил бы для всей среды. Итак, нужно рассуждать на уровне населения. Также, что BA могут быть успешно применены к сложным задачам позиционирования (антенны для мобильных телефонов, городское планирование и т. Д.) Или интеллектуальному анализу данных.
  • Культурный алгоритм (CA) состоит из компонента населения, почти идентичного этому генетического алгоритма и, кроме того, компонент знаний, называемый пространством алгоритмов.
  • Дифференциальная эволюция (DS), вдохновленная миграцией суперорганизмов.
  • Гауссовская адаптация (нормальная или естественная адаптация, чтобы избежать путаницы с GA) предназначенная для увеличения производительности систем обработки сигналов. Его также можно использовать для обычной параметрической оптимизации. Он основан на настоящем теореме, справедливой для всех областей приемлемости и всех гауссовых распределений. Эффективность NA основывается на теории информации и большей теореме эффективности. Его эффективность определяется как информация, разделенная на работу, специальное получение. Ландшафт сглаживается, так что впадины между пиками исчезнуть. Поэтому у него есть «амбиции» - исключены локальные пиков в фитнес-ландшафтах. NA также хорош при взбирании на крутые гребни за счет адаптации матрицы моментов, потому что NA может максимизировать беспорядок (средняя информация ) гауссианы, одновременно сохраняя постоянным среднее соответствие.

Другие метаэвристические методы

Метаэвристические методы в целом к ​​стохастическим методам оптимизации.

  • Имитация отжига (SA) - это связанный метод глобальной оптимизации, который пересекает пространство поиска, проверяя случайные мутации в отдельном решении. Всегда принимается мутация, повышающая физическую форму. Мутация, которая снижает приспособленность, принимается вероятностно на основании разницы в приспособления и уменьшения температуры. На языке SA о поиске минимальной энергии говорят вместо максимальной физической подготовки. SA также местный в стандартном алгоритме GA, начиная с относительно высокой скорости мутации и уменьшая ее с течением времени в соответствии с заданным расписанием.
  • Табу-поиск (TS) аналогичен моделированному отжигу тем, что оба проходят через пространство тестирования мутаций отдельного решения. В то время как имитация отжига генерирует только одно измененное решение, запретный поиск генерирует множество измененных решений и переходит к решению с наименьшей энергией из сгенерированных. Чтобы предотвратить цикличность и стимулировать большее движение в коммерческих решениях, используйте список запретов частичных полных решений. Запрещается переходить к решению, содержащему элементы списка запретов.
  • Экстремальная оптимизация (EO) В отличие от ГА, которые работают с совокупностью решений, EO разрабатывает единое решение и вносит локальные модификации в худшие компоненты. Для этого необходимо выбрать подходящее представление, позволяющее использовать компонент решения показатель качества («соответствие»). Управляющий принцип, лежащий в основе этого алгоритма, заключается в проверенном улучшении путем выбора низкокачественных компонентов и их замены случайно выбранным компонентом. Это явно расходится с GA, который выбирает хорошие решения в попытке найти лучшие решения.

Другие методы стохастической оптимизации

Последняя правка сделана 2021-05-21 14:56:22
Содержание доступно по лицензии CC BY-SA 3.0 (если не указано иное).
Обратная связь: support@alphapedia.ru
Соглашение
О проекте