Из Википедии, бесплатной энциклопедии
Перейти к навигации Перейти к поиску
Часть серии о
Эволюционный алгоритм
Генетический алгоритм
Генетическое программирование

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

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

Методология [ править ]

Проблемы оптимизации [ править ]

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

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

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

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

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

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

Инициализация [ править ]

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

Выбор [ править ]

Основная статья: Отбор (генетический алгоритм)

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

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

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

Генетические операторы [ править ]

Основные статьи: Кроссовер (генетический алгоритм) и Мутация (генетический алгоритм)

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

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

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

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

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

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

Эвристика [ править ]

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

Прекращение действия [ править ]

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

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

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

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

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

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

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

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

Ограничения [ править ]

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

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

Варианты [ править ]

Представление хромосомы [ править ]

Основная статья: генетическое представление

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

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

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

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

Элитизм [ править ]

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

Параллельные реализации [ править ]

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

Адаптивные ГА [ править ]

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

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

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

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

Проблемные домены [ править ]

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

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

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

В своем руководстве Алгоритм проектирования , Skiena советует генетических алгоритмов для любой задачи:

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

[...]

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

-  Стивен Скиена [31] : 267

История [ править ]

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

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

Коммерческие продукты [ править ]

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

Связанные методы [ править ]

См. Также: Список приложений генетического алгоритма

Родительские поля [ править ]

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

  • Эволюционные алгоритмы
  • Эволюционные вычисления
  • Метаэвристика
  • Стохастическая оптимизация
  • Оптимизация

Связанные поля [ править ]

Эволюционные алгоритмы [ править ]

Основная статья: Эволюционный алгоритм

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

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

Рой разведки [ править ]

Основная статья: Разведка роя

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

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

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

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

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

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

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

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

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

  • Метод кросс-энтропии (CE) генерирует возможные решения через параметризованное распределение вероятностей. Параметры обновляются посредством минимизации кросс-энтропии, чтобы на следующей итерации генерировать лучшие образцы.
  • Реактивная поисковая оптимизация (RSO) выступает за интеграцию субсимвольных методов машинного обучения в эвристику поиска для решения сложных задач оптимизации. Слово «реактивный» намекает на готовность реагировать на события во время поиска через внутреннюю онлайн-петлю обратной связи для самонастройки критических параметров. Методологии, представляющие интерес для реактивного поиска, включают машинное обучение и статистику, в частности обучение с подкреплением , активное обучение или обучение по запросу , нейронные сети и метаэвристику .

См. Также [ править ]

  • Генетическое программирование
  • Список приложений генетического алгоритма
  • Генетические алгоритмы в обработке сигналов (также известные как фильтры частиц)
  • Распространение схемы
  • Универсальный дарвинизм
  • Метаэвристика
  • Система обучающих классификаторов
  • Машинное обучение на основе правил

Ссылки [ править ]

  1. Перейти ↑ Mitchell 1996 , p. 2.
  2. ↑ a b Whitley 1994 , p. 66.
  3. ^ Eiben, AE et al (1994). «Генетические алгоритмы с рекомбинацией нескольких родителей». PPSN III: Труды Международной конференции по эволюционным вычислениям. Третья конференция по параллельному решению проблем с натуры: 78–87. ISBN  3-540-58484-6 .
  4. Перейти ↑ Ting, Chuan-Kang (2005). «О среднем времени сходимости многопородных генетических алгоритмов без отбора». Успехи в искусственной жизни: 403–412. ISBN 978-3-540-28848-0 . 
  5. ^ Деб, Kalyanmoy; Спирс, Уильям М. (1997). «C6.2: Методы видообразования». Справочник по эволюционным вычислениям . Издательский институт Физики. S2CID 3547258 . 
  6. ^ Шир, Офер М. (2012). «Ничинг в эволюционных алгоритмах». В Розенберге, Гжегоже; Бэк, Томас; Кок, Йост Н. (ред.). Справочник по естественным вычислениям . Springer Berlin Heidelberg. С. 1035–1069. DOI : 10.1007 / 978-3-540-92910-9_32 . ISBN 9783540929093.
  7. Перейти ↑ Goldberg 1989 , p. 41.
  8. ^ Харик, Жорж Р .; Лобо, Фернандо Дж .; Састри, Кумара (1 января 2006 г.). Связанное обучение с помощью вероятностного моделирования в расширенном компактном генетическом алгоритме (ECGA) . Масштабируемая оптимизация с помощью вероятностного моделирования . Исследования в области вычислительного интеллекта. 33 . С. 39–61. DOI : 10.1007 / 978-3-540-34954-9_3 . ISBN 978-3-540-34953-2.
  9. ^ Пеликан, Мартин; Голдберг, Дэвид Э .; Канту-Пас, Эрик (1 января 1999 г.). BOA: байесовский алгоритм оптимизации . Труды 1-й ежегодной конференции по генетическим и эволюционным вычислениям - Том 1 . Gecco'99. С. 525–532. ISBN 9781558606111.
  10. ↑ Гроб, Дэвид; Смит, Роберт Э. (1 января 2008 г.). Связное обучение в оценке алгоритмов распределения . Связь в эволюционных вычислениях . Исследования в области вычислительного интеллекта. 157 . С. 141–156. DOI : 10.1007 / 978-3-540-85068-7_7 . ISBN 978-3-540-85067-0.
  11. ^ Echegoyen, Карлос; Мендибуру, Александр; Сантана, Роберто; Лозано, Хосе А. (8 ноября 2012 г.). «О систематике задач оптимизации при оценке алгоритмов распределения». Эволюционные вычисления . 21 (3): 471–495. DOI : 10.1162 / EVCO_a_00095 . ISSN 1063-6560 . PMID 23136917 . S2CID 26585053 .   
  12. ^ Sadowski, Krzysztof L .; Босман, Питер А.Н.; Тиранс, Дирк (1 января 2013 г.). О полезности обработки связей для решения MAX-SAT . Труды 15-й ежегодной конференции по генетическим и эволюционным вычислениям . Gecco '13. С. 853–860. DOI : 10.1145 / 2463372.2463474 . hdl : 1874/290291 . ISBN 9781450319638. S2CID  9986768 .
  13. ^ Тахердангку, Мохаммад; Пазиреш, Махса; Язди, Мехран; Багери, Мохаммад Хади (19 ноября 2012 г.). «Эффективный алгоритм оптимизации функций: модифицированный алгоритм стволовых клеток» . Центральноевропейский инженерный журнал . 3 (1): 36–50. DOI : 10,2478 / s13531-012-0047-8 .
  14. ^ Wolpert, DH, Macready, WG, 1995. Нет теорем о бесплатном обеде для оптимизации. Институт Санта-Фе, SFI-TR-05-010, Санта-Фе.
  15. ^ Голдберг, Дэвид Э. (1991). «Теория виртуальных алфавитов». Параллельное решение задач с натуры . Параллельное решение задач из природы, конспект лекций по информатике . Конспект лекций по информатике. 496 . С. 13–22. DOI : 10.1007 / BFb0029726 . ISBN 978-3-540-54148-6.
  16. ^ Яников, Чехия; Михалевич, З. (1991). «Экспериментальное сравнение представлений двоичных и с плавающей запятой в генетических алгоритмах» (PDF) . Труды Четвертой Международной конференции по генетическим алгоритмам : 31–36 . Проверено 2 июля 2013 года .
  17. ^ Patrascu, M .; Stancu, AF; Поп, Ф. (2014). «HELGA: гетерогенный кодирующий реалистичный генетический алгоритм для моделирования и моделирования популяционной эволюции». Мягкие вычисления . 18 (12): 2565–2576. DOI : 10.1007 / s00500-014-1401-у . S2CID 29821873 . 
  18. ^ Балуджа, Шумеет; Каруана, Рич (1995). Удаление генетики из стандартного генетического алгоритма (PDF) . ICML .
  19. ^ Srinivas, M .; Патнаик, Л. (1994). «Адаптивные вероятности кроссовера и мутации в генетических алгоритмах» (PDF) . IEEE Transactions по системе, человеку и кибернетике . 24 (4): 656–667. DOI : 10.1109 / 21.286385 .
  20. ^ Zhang, J .; Chung, H .; Ло, WL (2007). «Адаптивный кроссовер на основе кластеризации и вероятности мутаций для генетических алгоритмов». IEEE Transactions по эволюционным вычислениям . 11 (3): 326–335. DOI : 10.1109 / TEVC.2006.880727 . S2CID 2625150 . 
  21. ^ См, например , Evolution-в-скорлупа архивации 15 апреля 2016 в Wayback Machine или пример задачи коммивояжера , в частности, использование оператора края рекомбинации .
  22. ^ Голдберг, Делавэр; Корб, Б .; Деб, К. (1989). «Беспорядочные генетические алгоритмы: анализ мотивации и первые результаты» . Сложные системы . 5 (3): 493–530.
  23. ^ Выражение гена: недостающее звено в эволюционных вычислениях
  24. ^ Харик, Г. (1997). Связь обучения для эффективного решения проблем ограниченной сложности с использованием генетических алгоритмов (PhD). Отделение компьютерных наук, Мичиганский университет, Анн-Арбор.
  25. ^ Томоягэ Б., Чиндриш М., Сампер А., Судрия-Андреу А., Виллафафила-Роблес Р. Оптимальная реконфигурация по Парето систем распределения энергии с использованием генетического алгоритма на основе NSGA-II. Энергии. 2013; 6 (3): 1439-1455.
  26. ^ Noetel М, Ciarrochi Дж, Sahdra В, С Лонсдейл (2019). «Использование генетических алгоритмов для сокращения перечня внимательности для спорта: содержательно-методологический синтез» . Психология спорта и физических упражнений . 45 (101545): 101545. DOI : 10.1016 / j.psychsport.2019.101545 .
  27. ^ Валовой, Билл. «Солнечная энергетическая система, отслеживающая солнце» . TED . Проверено 20 ноября 2013 года .
  28. ^ Хорнби, GS; Linden, DS; Лон, Дж. Д., Автоматизированное проектирование антенн с использованием эволюционных алгоритмов (PDF)
  29. ^ "Гибкое движение мышц на основе двуногих существ" .
  30. ^ Evans, B .; Уолтон, СП (декабрь 2017 г.). «Аэродинамическая оптимизация гиперзвукового НЗ на основе решения уравнения Больцмана – БГК и эволюционной оптимизации» . Прикладное математическое моделирование . 52 : 215–240. DOI : 10.1016 / j.apm.2017.07.024 . ISSN 0307-904X . 
  31. ^ Skiena, Стивен (2010). Руководство по разработке алгоритмов (2-е изд.). Springer Science + Business Media . ISBN 978-1-849-96720-4.
  32. ^ Тьюринг, Алан М. (октябрь 1950 г.). «Вычислительная техника и интеллект» . Разум . LIX (238): 433–460. DOI : 10.1093 / разум / LIX.236.433 .
  33. ^ Барричелли, Нильс Алл (1954). "Esempi numerici di processi di evoluzione". Methodos : 45-68.
  34. ^ Barricelli, Nils Aall (1957). «Симбиогенетические процессы эволюции, реализуемые искусственными методами». Methodos : 143-182.
  35. ^ Фрейзер, Алекс (1957). «Моделирование генетических систем автоматическими цифровыми вычислительными машинами. I. Введение» . Aust. J. Biol. Sci . 10 (4): 484–491. DOI : 10.1071 / BI9570484 .
  36. ^ Фрейзер, Алекс ; Бернелл, Дональд (1970). Компьютерные модели в генетике . Нью-Йорк: Макгроу-Хилл. ISBN 978-0-07-021904-5.
  37. ^ Кросби, Джек Л. (1973). Компьютерное моделирование в генетике . Лондон: Джон Вили и сыновья. ISBN 978-0-471-18880-3.
  38. ^ 27.02.96 - Ганс Бремерманн из Калифорнийского университета в Беркли, почетный профессор и пионер математической биологии, умер в возрасте 69 лет.
  39. ^ Фогель, Дэвид Б. (редактор) (1998). Эволюционные вычисления: летопись окаменелостей . Нью-Йорк: IEEE Press. ISBN 978-0-7803-3481-6.CS1 maint: extra text: authors list (link)
  40. ^ Барричелли, Нильс Алл (1963). «Численное тестирование эволюционных теорий. Часть II. Предварительные тесты производительности, симбиогенеза и земной жизни». Acta Biotheoretica . 16 (3–4): 99–126. DOI : 10.1007 / BF01556602 . S2CID 86717105 . 
  41. ^ Rechenberg, Инго (1973). Evolutionsstrategie . Штутгарт: Хольцманн-Фробуг. ISBN 978-3-7728-0373-4.
  42. ^ Schwefel, Ханс-Поль (1974). Numerische Optimierung von Computer-Modellen (кандидатская диссертация) .
  43. ^ Schwefel, Ханс-Поль (1977). Numerische Optimierung von Computor-Modellen mittels der Evolutionsstrategie: mit einer vergleichenden Einführung in die Hill-Climbing- und Zufallsstrategie . Базель; Штутгарт: Биркхойзер. ISBN 978-3-7643-0876-6.
  44. ^ Schwefel, Ханс-Поль (1981). Численная оптимизация компьютерных моделей (перевод 1977 Numerische Optimierung von Computor-Modellen mittels der Evolutionsstrategie . Chichester; New York: Wiley. ISBN 978-0-471-09988-8.
  45. ^ Aldawoodi, Namir (2008). Подход к проектированию автопилота беспилотного вертолета с использованием генетических алгоритмов и имитации отжига . п. 99. ISBN 978-0549773498 - через Google Книги.
  46. ^ Markoff, Джон (29 августа 1990). «Какой лучший ответ? Это выживание сильнейшего» . Нью-Йорк Таймс . Дата обращения 13 июля 2016 .
  47. ↑ Ruggiero, Murray A .. (1 августа 2009 г.) Пятнадцать лет и считая. Архивировано 30 января 2016 г. в Wayback Machine . Futuresmag.com. Проверено 7 августа 2013.
  48. ^ Evolver: сложная оптимизация электронных таблиц . Палисад. Проверено 7 августа 2013.
  49. ^ Тесты для оценки алгоритмов оптимизации и тестирования оптимизаторов MATLAB без производных для быстрого доступа практиков , IEEE Access, том 7, 2019.
  50. ^ Кохун, Дж; и другие. (2002). Эволюционные алгоритмы для физического проектирования схем СБИС (PDF) . Достижения в эволюционных вычислениях: теория и приложения . Springer, стр. 683-712, 2003. ISBN  978-3-540-43330-9.
  51. ^ Пеликан, Мартин; Голдберг, Дэвид Э .; Канту-Пас, Эрик (1 января 1999 г.). BOA: байесовский алгоритм оптимизации . Труды 1-й ежегодной конференции по генетическим и эволюционным вычислениям - Том 1 . Gecco'99. С. 525–532. ISBN 9781558606111.
  52. ^ Пеликан, Мартин (2005). Иерархический алгоритм байесовской оптимизации: к новому поколению эволюционных алгоритмов (1-е изд.). Берлин [ua]: Springer. ISBN 978-3-540-23774-7.
  53. ^ Thierens, Dirk (11 сентября 2010). «Генетический алгоритм дерева сцепления». Параллельное решение проблем с натуры, PPSN XI . С. 264–273. DOI : 10.1007 / 978-3-642-15844-5_27 . ISBN 978-3-642-15843-8. Отсутствует или пусто |title=( справка )
  54. ^ Феррейра, C. «Программирование экспрессии генов: новый адаптивный алгоритм для решения проблем» (PDF) . Сложные системы, Vol. 13, выпуск 2: 87-129.
  55. ^ Falkenauer, Эмануэль (1997). Генетические алгоритмы и проблемы группировки . Чичестер, Англия: ISBN John Wiley & Sons Ltd. 978-0-471-97150-4.
  56. ^ Злочин, Марк; Бираттари, Мауро; Мёло, Николя; Дориго, Марко (1 октября 2004 г.). "Модельно-ориентированный поиск комбинаторной оптимизации: критический обзор". Анналы исследований операций . 131 (1–4): 373–395. CiteSeerX 10.1.1.3.427 . DOI : 10,1023 / Б: ANOR.0000039526.52305.af . ISSN 0254-5330 . S2CID 63137 .   
  57. ^ Рания Хассан, Бабак Коханим, Оливье де Век, Герхард Вентер (2005) Сравнение оптимизации роя частиц и генетического алгоритма
  58. ^ Khalafallah Ахмед; Абдель-Рахим Мохамед (1 мая 2011 г.). «Electimize: новый эволюционный алгоритм оптимизации с применением в строительстве». Журнал вычислительной техники в гражданском строительстве . 25 (3): 192–201. DOI : 10.1061 / (ASCE) CP.1943-5487.0000080 .
  59. ^ Бодри, Бенуа; Франк Флёри; Жан-Марк Жезекель ; Ив Ле Траон (март – апрель 2005 г.). «Автоматическая оптимизация тестовых случаев: бактериологический алгоритм» (PDF) . Программное обеспечение IEEE . 22 (2): 76–82. DOI : 10.1109 / MS.2005.30 . S2CID 3559602 . Проверено 9 августа 2009 года .  
  60. ^ Civicioglu, P. (2012). «Преобразование геоцентрических декартовых координат в геодезические координаты с помощью алгоритма дифференциального поиска». Компьютеры и науки о Земле . 46 : 229–247. Bibcode : 2012CG ..... 46..229C . DOI : 10.1016 / j.cageo.2011.12.011 .
  61. ^ Kjellström, G. (декабрь 1991). «Об эффективности гауссовой адаптации». Журнал теории оптимизации и приложений . 71 (3): 589–597. DOI : 10.1007 / BF00941405 . S2CID 116847975 . 

Библиография [ править ]

  • Банцаф, Вольфганг; Нордин, Питер; Келлер, Роберт; Франконе, Франк (1998). Генетическое программирование - Введение . Сан-Франциско, Калифорния: Морган Кауфманн. ISBN 978-1558605107.
  • Bies, Роберт Р .; Малдун, Мэтью Ф .; Поллок, Брюс Дж .; Манук, Стивен; Смит, Гвенн; Продажа, Марк Э. (2006). «Основанный на генетическом алгоритме, гибридный подход машинного обучения к выбору модели». Журнал фармакокинетики и фармакодинамики . 33 (2): 196–221. DOI : 10.1007 / s10928-006-9004-6 . PMID  16565924 . S2CID  39571129 .
  • Ча, Сон Хёк; Тапперт, Чарльз С. (2009). «Генетический алгоритм для построения компактных двоичных деревьев решений». Журнал исследований распознавания образов . 4 (1): 1–13. CiteSeerX  10.1.1.154.8314 . DOI : 10.13176 / 11.44 .
  • Фрейзер, Алекс С. (1957). «Моделирование генетических систем с помощью автоматических цифровых компьютеров. I. Введение» . Австралийский журнал биологических наук . 10 (4): 484–491. DOI : 10.1071 / BI9570484 .
  • Голдберг, Дэвид (1989). Генетические алгоритмы в поиске, оптимизации и машинном обучении . Ридинг, Массачусетс: Аддисон-Уэсли Профессионал. ISBN 978-0201157673.
  • Гольдберг, Дэвид (2002). Дизайн инноваций: уроки и для компетентных генетических алгоритмов . Norwell, MA: Kluwer Academic Publishers. ISBN 978-1402070983.
  • Фогель, Дэвид (2006). Эволюционные вычисления: к новой философии машинного интеллекта (3-е изд.). Пискатауэй, Нью-Джерси: IEEE Press. ISBN 978-0471669517.
  • Холланд, Джон (1992). Адаптация в естественных и искусственных системах . Кембридж, Массачусетс: MIT Press. ISBN 978-0262581110.
  • Коза, Джон (1992). Генетическое программирование: о программировании компьютеров посредством естественного отбора . Кембридж, Массачусетс: MIT Press. ISBN 978-0262111706.
  • Михалевич, Збигнев (1996). Генетические алгоритмы + структуры данных = программы эволюции . Springer-Verlag. ISBN 978-3540606765.
  • Митчелл, Мелани (1996). Введение в генетические алгоритмы . Кембридж, Массачусетс: MIT Press. ISBN 9780585030944.
  • Poli, R .; Лэнгдон, ВБ; Макфи, Н.Ф. (2008). Полевое руководство по генетическому программированию . Lulu.com, свободно доступный в Интернете. ISBN 978-1-4092-0073-4.[ самостоятельно опубликованный источник? ]
  • Рехенберг, Инго (1994): Evolutionsstrategie '94, Штутгарт: Fromman-Holzboog.
  • Schmitt, Lothar M .; Неханив, Кристофер Л .; Fujii, Роберт Х. (1998). «Линейный анализ генетических алгоритмов» . Теоретическая информатика . 208 : 111–148.
  • Шмитт, Лотар М. (2001). «Теория генетических алгоритмов». Теоретическая информатика . 259 (1–2): 1–61. DOI : 10.1016 / S0304-3975 (00) 00406-0 .
  • Шмитт, Лотар М. (2004). «Теория генетических алгоритмов II: модели для генетических операторов над строковым тензорным представлением популяций и сходимость к глобальным оптимумам для произвольной функции приспособленности при масштабировании». Теоретическая информатика . 310 (1–3): 181–231. DOI : 10.1016 / S0304-3975 (03) 00393-1 .
  • Schwefel, Hans-Paul (1974): Numerische Optimierung von Computer-Modellen (докторская диссертация). Перепечатано Биркхойзером (1977).
  • Восе, Майкл (1999). Простой генетический алгоритм: основы и теория . Кембридж, Массачусетс: MIT Press. ISBN 978-0262220583.
  • Уитли, Даррелл (1994). «Учебник по генетическому алгоритму» (PDF) . Статистика и вычисления . 4 (2): 65–85. CiteSeerX  10.1.1.184.3999 . DOI : 10.1007 / BF00175354 . S2CID  3447126 .
  • Хингстон, Филипп; Бароне, Луиджи; Михалевич, Збигнев (2008). Дизайн Evolution: достижения в эволюционном дизайне . Springer. ISBN 978-3540741091.
  • Эйбен, Агостон; Смит, Джеймс (2003). Введение в эволюционные вычисления . Springer. ISBN 978-3540401841.

Внешние ссылки [ править ]

Ресурсы [ править ]

  • [1] Предоставляет список ресурсов в области генетических алгоритмов.
  • Обзор истории и разновидностей эволюционных алгоритмов

Учебники [ править ]

  • Генетические алгоритмы - компьютерные программы, которые «развиваются» способами, напоминающими естественный отбор, могут решать сложные проблемы, которые даже их создатели не до конца понимают . Отличное введение в ГА, написанное Джоном Холландом, и приложение для решения дилеммы заключенного.
  • Интерактивное онлайн-руководство по генетическому алгоритму для читателя, чтобы попрактиковаться или узнать, как работает ГА : изучать шаг за шагом или наблюдать глобальную конвергенцию в пакетном режиме, изменять размер популяции, частоту / границы кроссовера, частоту / границы мутаций и механизмы отбора, а также добавлять ограничения .
  • Учебное пособие по генетическому алгоритму от Даррелла Уитли, Департамент компьютерных наук, Государственный университет штата Колорадо . Отличное учебное пособие с большим количеством теории.
  • «Основы метаэвристики» , 2009 г. (225 с). Свободный открытый текст Шона Люка.
  • Алгоритмы глобальной оптимизации - теория и применение
  • Генетические алгоритмы в Python Учебное пособие с интуицией, лежащей в основе реализации GA и Python.
  • Генетические алгоритмы развиваются, чтобы решить дилемму заключенного. Автор Роберт Аксельрод.