stringtranslate.com

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

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

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

Методология

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

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

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

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

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

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

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

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

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

Выбор

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

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

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

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

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

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

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

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

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

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

Эвристика

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

Прекращение действия

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

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

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

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

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

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

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

Ограничения

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

Варианты

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

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

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

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

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

Элитизм

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

[...]

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

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

История

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Рекомендации

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

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

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

Ресурсы

Учебники