stringtranslate.com

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

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

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

Методология

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

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

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

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

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

Стандартное представление каждого возможного решения — это массив битов (также называемый набором битов или строкой битов ). [5] Массивы других типов и структур могут использоваться по сути тем же способом. Главное свойство, которое делает эти генетические представления удобными, заключается в том, что их части легко выравниваются благодаря их фиксированному размеру, что облегчает простые операции кроссинговера . Также могут использоваться представления переменной длины, но реализация кроссинговера в этом случае более сложна. Древовидные представления изучаются в генетическом программировании , а представления в форме графа изучаются в эволюционном программировании ; сочетание как линейных хромосом, так и деревьев изучается в программировании экспрессии генов .

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

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

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

Выбор

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

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

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

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

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

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

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

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

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

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

Эвристика

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

Прекращение

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

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

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

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

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

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

Несмотря на отсутствие консенсуса относительно обоснованности гипотезы строительных блоков, она последовательно оценивалась и использовалась в качестве справочного материала на протяжении многих лет. Например, было предложено много оценок алгоритмов распределения в попытке предоставить среду, в которой гипотеза будет иметь силу. [12] [13] Хотя для некоторых классов задач были получены хорошие результаты, скептицизм относительно общности и/или практичности гипотезы строительных блоков как объяснения эффективности ГА все еще сохраняется. Действительно, существует разумное количество работ, которые пытаются понять ее ограничения с точки зрения оценки алгоритмов распределения. [14] [15] [16]

Ограничения

Практическое использование генетического алгоритма имеет ограничения, особенно по сравнению с альтернативными алгоритмами оптимизации:

Варианты

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

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

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

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

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

Элитарность

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

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

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

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

Генетические алгоритмы с адаптивными параметрами (адаптивные генетические алгоритмы, AGA) — еще один важный и многообещающий вариант генетических алгоритмов. Вероятности кроссинговера (pc) и мутации (pm) в значительной степени определяют степень точности решения и скорость сходимости, которую могут получить генетические алгоритмы. Исследователи проанализировали сходимость GA аналитически. [23] [24]

Вместо использования фиксированных значений pc и pm , AGA используют информацию о популяции в каждом поколении и адаптивно корректируют pc и pm для поддержания разнообразия популяции, а также для поддержания способности к конвергенции. В AGA (адаптивном генетическом алгоритме) [25] корректировка pc и pm зависит от значений пригодности решений. Есть и другие примеры вариантов AGA: Метод последовательного масштабирования является ранним примером улучшения конвергенции. [26] В CAGA (адаптивном генетическом алгоритме на основе кластеризации) [27] с помощью кластерного анализа для оценки состояний оптимизации популяции корректировка pc и pm зависит от этих состояний оптимизации. Последние подходы используют более абстрактные переменные для принятия решения о pc и pm . Примерами являются принципы доминирования и кодоминирования [28] и LIGA (уровневый интерполяционный генетический алгоритм), который объединяет гибкий GA с модифицированным поиском A* для решения проблемы анизотропии пространства поиска. [29]

Может быть весьма эффективным объединение GA с другими методами оптимизации. GA, как правило, довольно хорош в поиске в целом хороших глобальных решений, но совершенно неэффективен в поиске последних нескольких мутаций для нахождения абсолютного оптимума. Другие методы (например, простой подъем на холм ) весьма эффективны в поиске абсолютного оптимума в ограниченной области. Чередование GA и подъема на холм может повысить эффективность GA [ требуется цитата ] при преодолении недостатка надежности подъема на холм.

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

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

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

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

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

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

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

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

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

[...]

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

—  Стивен Скиена [39] : 267 

История

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

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

Коммерческая продукция

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

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

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

Генетические алгоритмы — это подраздел:

Связанные поля

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

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

Роевой интеллект

Роевой интеллект — это подраздел эволюционных вычислений .

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

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

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

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

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

Смотрите также

Ссылки

  1. ^ Петровски, Ален; Бен-Хамида, Сана (2017). Эволюционные алгоритмы. John Wiley & Sons. стр. 30.
  2. ^ Митчелл 1996, стр. 2.
  3. ^ Gerges, Firas; Zouein, Germain; Azar, Danielle (12 марта 2018 г.). «Генетические алгоритмы с локальной оптимальной обработкой для решения головоломок судоку». Труды Международной конференции по вычислениям и искусственному интеллекту 2018 г. ICCAI 2018. Нью-Йорк, штат Нью-Йорк, США: Ассоциация вычислительной техники. стр. 19–22. doi :10.1145/3194452.3194463. ISBN 978-1-4503-6419-5. S2CID  44152535.
  4. ^ Беркхарт, Майкл С.; Руис, Габриэль (2023). «Нейроэволюционные представления для изучения эффектов гетерогенного лечения». Журнал вычислительной науки . 71 : 102054. doi : 10.1016/j.jocs.2023.102054 . S2CID  258752823.
  5. ^ ab Whitley 1994, стр. 66.
  6. ^ Луке-Родригес, Мария; Молина-Баэна, Хосе; Хименес-Вильчес, Альфонсо; Араузо-Азофра, Антонио (2022). «Инициализация поиска по выбору признаков для классификации (раздел 3)». Журнал исследований искусственного интеллекта . 75 : 953–983. дои : 10.1613/jair.1.14015 .
  7. ^ Эйбен, А.Е. и др. (1994). «Генетические алгоритмы с многородительской рекомбинацией». PPSN III: Труды Международной конференции по эволюционным вычислениям. Третья конференция по параллельному решению проблем природы: 78–87. ISBN 3-540-58484-6 . 
  8. ^ Тинг, Чуан-Кан (2005). «О среднем времени сходимости многородительских генетических алгоритмов без отбора». Достижения в области искусственной жизни: 403–412. ISBN 978-3-540-28848-0 . 
  9. ^ Деб, Кальянмой; Спирс, Уильям М. (1997). "C6.2: Методы видообразования". Справочник по эволюционным вычислениям . Издательство Института физики. S2CID  3547258.
  10. ^ Шир, Офер М. (2012). «Ниши в эволюционных алгоритмах». В Розенберг, Гжегож; Бэк, Томас; Кок, Йост Н. (ред.). Справочник по естественным вычислениям . Springer Berlin Heidelberg. стр. 1035–1069. doi :10.1007/978-3-540-92910-9_32. ISBN 9783540929093.
  11. ^ Голдберг 1989, стр. 41.
  12. ^ Харик, Жорж Р.; Лобо, Фернандо Г.; Састри, Кумара (1 января 2006 г.). «Обучение связям с помощью вероятностного моделирования в расширенном компактном генетическом алгоритме (ECGA)». Масштабируемая оптимизация с помощью вероятностного моделирования . Исследования по вычислительному интеллекту. Том 33. С. 39–61. doi :10.1007/978-3-540-34954-9_3. ISBN 978-3-540-34953-2.
  13. ^ Пеликан, Мартин; Голдберг, Дэвид Э.; Канту-Пас, Эрик (1 января 1999 г.). BOA: Байесовский алгоритм оптимизации. Гекко'99. стр. 525–532. ISBN 9781558606111. {{cite book}}: |journal=проигнорировано ( помощь )
  14. ^ Коффин, Дэвид; Смит, Роберт Э. (1 января 2008 г.). «Обучение связям в оценке алгоритмов распределения». Связь в эволюционных вычислениях . Исследования в области вычислительного интеллекта. Том 157. С. 141–156. doi :10.1007/978-3-540-85068-7_7. ISBN 978-3-540-85067-0.
  15. ^ Эчегойен, Карлос; Мендибуру, Александр; Сантана, Роберто; Лосано, Хосе А. (8 ноября 2012 г.). «О таксономии задач оптимизации при оценке алгоритмов распределения». Эволюционные вычисления . 21 (3): 471–495. doi :10.1162/EVCO_a_00095. ISSN  1063-6560. PMID  23136917. S2CID  26585053.
  16. ^ Садовски, Кшиштоф Л.; Босман, Питер АН; Тиеренс, Дирк (1 января 2013 г.). «О полезности обработки связей для решения MAX-SAT». Труды 15-й ежегодной конференции по генетическим и эволюционным вычислениям . Gecco '13. стр. 853–860. doi :10.1145/2463372.2463474. hdl :1874/290291. ISBN 9781450319638. S2CID  9986768.
  17. ^ Тахердангку, Мохаммад; Пазиреш, Махса; Язди, Мехран; Багери, Мохаммад Хади (19 ноября 2012 г.). «Эффективный алгоритм оптимизации функций: модифицированный алгоритм стволовых клеток». Central European Journal of Engineering . 3 (1): 36–50. doi : 10.2478/s13531-012-0047-8 .
  18. ^ Вулперт, Д. Х., Макреди, В. Г., 1995. Теоремы о бесплатном обеде для оптимизации. Институт Санта-Фе, SFI-TR-05-010, Санта-Фе.
  19. ^ Голдберг, Дэвид Э. (1991). «Теория виртуальных алфавитов». Параллельное решение задач из природы . Конспект лекций по информатике. Том 496. С. 13–22. doi :10.1007/BFb0029726. ISBN 978-3-540-54148-6. {{cite book}}: |journal=проигнорировано ( помощь )
  20. ^ Janikow, CZ; Michalewicz, Z. (1991). "Экспериментальное сравнение двоичных и плавающих представлений в генетических алгоритмах" (PDF) . Труды Четвертой международной конференции по генетическим алгоритмам : 31–36. Архивировано (PDF) из оригинала 9 октября 2022 г. . Получено 2 июля 2013 г. .
  21. ^ Патраску, М.; Станку, А.Ф.; Поп, Ф. (2014). «HELGA: гетерогенный кодирующий реалистичный генетический алгоритм для моделирования и имитации эволюции популяции». Soft Computing . 18 (12): 2565–2576. doi :10.1007/s00500-014-1401-y. S2CID  29821873.
  22. ^ Балуджа, Шумит; Каруана, Рич (1995). Удаление генетики из стандартного генетического алгоритма (PDF) . ICML . Архивировано (PDF) из оригинала 9 октября 2022 г.
  23. ^ Stannat, W. (2004). «О сходимости генетических алгоритмов – вариационный подход». Probab. Theory Relat. Fields . 129 : 113–132. doi : 10.1007/s00440-003-0330-y . S2CID  121086772.
  24. ^ Шарапов, РР; Лапшин, А.В. (2006). «Сходимость генетических алгоритмов». Pattern Recognition. Image Anal . 16 (3): 392–397. doi :10.1134/S1054661806030084. S2CID  22890010.
  25. ^ Шринивас, М.; Патнаик, Л. (1994). «Адаптивные вероятности кроссинговера и мутации в генетических алгоритмах» (PDF) . IEEE Transactions on Systems, Man, and Cybernetics . 24 (4): 656–667. doi :10.1109/21.286385. Архивировано (PDF) из оригинала 9 октября 2022 г.
  26. ^ Квон, YD; Квон, SB; Джин, SB; Ким, JY (2003). «Генетический алгоритм, улучшенный сходимостью, с методом последовательного масштабирования для решения непрерывных задач оптимизации». Компьютеры и структуры . 81 (17): 1715–1725. doi :10.1016/S0045-7949(03)00183-4.
  27. ^ Чжан, Дж.; Чунг, Х.; Ло, В. Л. (2007). «Адаптивный кроссовер на основе кластеризации и вероятности мутаций для генетических алгоритмов». Труды IEEE по эволюционным вычислениям . 11 (3): 326–335. doi :10.1109/TEVC.2006.880727. S2CID  2625150.
  28. ^ Павай, Г.; Гита, ТВ (2019). «Новые операторы кроссинговера, использующие принципы доминирования и кодоминирования для более быстрой сходимости генетических алгоритмов». Soft Comput . 23 (11): 3661–3686. doi :10.1007/s00500-018-3016-1. S2CID  254028984.
  29. ^ Ли, Дж. К. Ф.; Циммерле, Д.; Янг, П. (2022). «Гибкая сетевая электрификация сельской местности с использованием уравновешенного интерполяционного генетического алгоритма». Энергия и ИИ . 10 : 100186. Bibcode : 2022EneAI..1000186L. doi : 10.1016/j.egyai.2022.100186 . S2CID  250972466.
  30. ^ См., например, Эволюцию в двух словах, архивировано 15 апреля 2016 г. на Wayback Machine или пример из задачи коммивояжера , в частности, использование оператора рекомбинации ребер .
  31. ^ Голдберг, Д.Э.; Корб, Б.; Деб, К. (1989). «Беспорядочные генетические алгоритмы: анализ мотивации и первые результаты». Сложные системы . 5 (3): 493–530.
  32. ^ Экспрессия генов: недостающее звено в эволюционных вычислениях
  33. ^ Харик, Г. (1997). Изучение связей для эффективного решения задач ограниченной сложности с использованием генетических алгоритмов (PhD). Кафедра компьютерных наук, Мичиганский университет, Энн-Арбур.
  34. ^ Томояга Б., Чиндрис М., Сумпер А., Судрия-Андреу А., Виллафафила-Роблес Р. Оптимальная по Парето реконфигурация систем распределения электроэнергии с использованием генетического алгоритма на основе NSGA-II. Энергии. 2013; 6(3):1439-1455.
  35. ^ Гросс, Билл (2 февраля 2009 г.). «Система солнечной энергии, которая отслеживает солнце». TED . Получено 20 ноября 2013 г.
  36. ^ Хорнби, Г.С.; Линден, Д.С.; Лон, Дж.Д., Автоматизированное проектирование антенн с использованием эволюционных алгоритмов (PDF)
  37. ^ «Гибкое мышечное передвижение двуногих существ».
  38. ^ Эванс, Б.; Уолтон, С.П. (декабрь 2017 г.). «Аэродинамическая оптимизация гиперзвукового возвращаемого аппарата на основе решения уравнения Больцмана–БГК и эволюционной оптимизации». Прикладное математическое моделирование . 52 : 215–240. doi : 10.1016/j.apm.2017.07.024 . ISSN  0307-904X.
  39. ^ Скиена, Стивен (2010). Руководство по разработке алгоритмов (2-е изд.). Springer Science+Business Media . ISBN 978-1-849-96720-4.
  40. ↑ Тьюринг, Алан М. (октябрь 1950 г.). «Вычислительная техника и интеллект». Mind . LIX (238): 433–460. doi :10.1093/mind/LIX.236.433.
  41. ^ Барричелли, Нильс Аалл (1954). «Числовые примеры процесса эволюции». Методы : 45–68.
  42. ^ Барричелли, Нильс Аалл (1957). «Симбиогенетические эволюционные процессы, реализуемые искусственными методами». Методос : 143–182.
  43. ^ Фрейзер, Алекс (1957). «Моделирование генетических систем с помощью автоматических цифровых компьютеров. I. Введение». Aust. J. Biol. Sci . 10 (4): 484–491. doi : 10.1071/BI9570484 .
  44. ^ Фрейзер, Алекс ; Бернелл, Дональд (1970). Компьютерные модели в генетике . Нью-Йорк: McGraw-Hill. ISBN 978-0-07-021904-5.
  45. ^ Кросби, Джек Л. (1973). Компьютерное моделирование в генетике . Лондон: John Wiley & Sons. ISBN 978-0-471-18880-3.
  46. ↑ 27.02.96 - Ганс Бремерманн, почетный профессор и пионер математической биологии из Калифорнийского университета в Беркли, скончался в возрасте 69 лет.
  47. ^ Фогель, Дэвид Б., ред. (1998). Эволюционные вычисления: летопись ископаемых . Нью-Йорк: IEEE Press. ISBN 978-0-7803-3481-6.
  48. ^ Барричелли, Нильс Аалл (1963). «Численная проверка теорий эволюции. Часть II. Предварительные проверки производительности, симбиогенеза и наземной жизни». Acta Biotheoretica . 16 (3–4): 99–126. doi :10.1007/BF01556602. S2CID  86717105.
  49. ^ Рехенберг, Инго (1973). Эволюционная стратегия . Штутгарт: Хольцманн-Фробуг. ISBN 978-3-7728-0373-4.
  50. ^ Швефель, Ханс-Пауль (1974). Numerische Optimierung von Computer-Modellen (докторская диссертация) .
  51. ^ Швефель, Ханс-Пол (1977). Числовая оптимизация компьютерных моделей с помощью стратегии эволюции: с помощью Einer vergleichenden Einführung в стратегии Hill-Climbing- und Zufalls . Базель; Штутгарт: Биркхойзер. ISBN 978-3-7643-0876-6.
  52. ^ Швефель, Ханс-Пол (1981). Численная оптимизация компьютерных моделей (перевод Numerische Optimierung von Computor-Modellen mittels der Evolutionsstrategie, 1977 г., Чичестер; Нью-Йорк: Wiley. ISBN) . 978-0-471-09988-8.
  53. ^ Альдавуди, Намир (2008). Подход к проектированию беспилотного вертолетного автопилота с использованием генетических алгоритмов и имитации отжига. стр. 99. ISBN 978-0549773498– через Google Книги.
  54. ↑ Маркофф, Джон (29 августа 1990 г.). «Какой лучший ответ? Выживает сильнейший». New York Times . Получено 13 июля 2016 г.
  55. ^ Руджеро, Мюррей А.. (1 августа 2009 г.) Пятнадцать лет и отсчет продолжается Архивировано 30 января 2016 г. на Wayback Machine . Futuresmag.com. Получено 07.08.2013.
  56. ^ Evolver: Сложная оптимизация для электронных таблиц. Palisade. Получено 07.08.2013.
  57. ^ Ли, Лин; Салдивар, Альфредо Алан Флорес; Бай, Юн; Чен, Йи; Лю, Цюньфэн; Ли, Юн (2019). «Бенчмарки для оценки алгоритмов оптимизации и бенчмаркинга оптимизаторов MATLAB без производных для быстрого доступа практикующих специалистов». Доступ IEEE . 7 : 79657–79670. Бибкод : 2019IEEA...779657L. дои : 10.1109/ACCESS.2019.2923092 . S2CID  195774435.
  58. ^ Cohoon, J; et al. (2002). Эволюционные алгоритмы для физического проектирования схем VLSI (PDF) . Springer, стр. 683-712, 2003. ISBN 978-3-540-43330-9. Архивировано (PDF) из оригинала 9 октября 2022 г. {{cite book}}: |journal=проигнорировано ( помощь )
  59. ^ Пеликан, Мартин; Голдберг, Дэвид Э.; Канту-Пас, Эрик (1 января 1999 г.). BOA: Байесовский алгоритм оптимизации. Гекко'99. стр. 525–532. ISBN 9781558606111. {{cite book}}: |journal=проигнорировано ( помощь )
  60. ^ Пеликан, Мартин (2005). Иерархический байесовский алгоритм оптимизации: к новому поколению эволюционных алгоритмов (1-е изд.). Берлин [ua]: Springer. ISBN 978-3-540-23774-7.
  61. ^ Тиренс, Дирк (11 сентября 2010 г.). «Генетический алгоритм дерева связей». Параллельное решение задач из природы, PPSN XI . стр. 264–273. doi :10.1007/978-3-642-15844-5_27. ISBN 978-3-642-15843-8.
  62. ^ Феррейра, К (2001). «Программирование экспрессии генов: новый адаптивный алгоритм для решения проблем» (PDF) . Сложные системы . 13 (2): 87–129. arXiv : cs/0102027 . Bibcode :2001cs........2027F. Архивировано (PDF) из оригинала 9 октября 2022 г.
  63. ^ Фалькенауэр, Эмануэль (1997). Генетические алгоритмы и проблемы группировки . Чичестер, Англия: John Wiley & Sons Ltd. ISBN 978-0-471-97150-4.
  64. ^ Злочин, Марк; Бираттари, Мауро; Мело, Николас; Дориго, Марко (1 октября 2004 г.). «Поиск на основе моделей для комбинаторной оптимизации: критический обзор». Annals of Operations Research . 131 (1–4): 373–395. CiteSeerX 10.1.1.3.427 . doi :10.1023/B:ANOR.0000039526.52305.af. ISSN  0254-5330. S2CID  63137. 
  65. ^ Рания Хассан, Бабак Коханим, Оливье де Век, Герхард Вентер (2005) Сравнение оптимизации роя частиц и генетического алгоритма
  66. ^ Бодри, Бенуа; Франк Флери; Жан-Марк Жезекель ; Ив Ле Траон (март – апрель 2005 г.). «Автоматическая оптимизация тестовых примеров: бактериологический алгоритм» (PDF) . Программное обеспечение IEEE . 22 (2): 76–82. дои : 10.1109/MS.2005.30. S2CID  3559602. Архивировано (PDF) из оригинала 9 октября 2022 года . Проверено 9 августа 2009 г.
  67. ^ Civicioglu, P. (2012). «Преобразование геоцентрических декартовых координат в геодезические координаты с использованием алгоритма дифференциального поиска». Компьютеры и науки о Земле . 46 : 229–247. Bibcode : 2012CG.....46..229C. doi : 10.1016/j.cageo.2011.12.011.
  68. ^ Кьельстрём, Г. (декабрь 1991 г.). «Об эффективности гауссовой адаптации». Журнал теории оптимизации и приложений . 71 (3): 589–597. doi :10.1007/BF00941405. S2CID  116847975.

Библиография

Внешние ссылки

Ресурсы

Учебники