Генетические алгоритмы: конкурентный поиск в пространстве решений

Введение

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

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

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

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

Выбор

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

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

Следующий шаг — создание популяции решений второго поколения из выбранных, путём сочетания генетических операторов: кроссовера (также называемого рекомбинацией) и мутации. Для каждого нового решения, которое предстоит создать, из ранее выбранного пула выбирается пара "родительских" решений для скрещивания. Получение "потомка" с использованием вышеуказанных методов кроссовера и мутации создаёт новое решение, которое обычно наследует многие характеристики своих "родителей". Новые родители выбираются для каждого нового потомка, и процесс продолжается до тех пор, пока не будет сформирована новая популяция решений требуемого размера. Хотя методы размножения, основанные на использовании двух родителей, больше вдохновлены биологией, некоторые исследования показывают, что использование более двух "родителей" позволяет получить хромосомы более высокого качества. Эти процессы в конечном итоге приводят к формированию следующего поколения популяции хромосом, отличающегося от исходного поколения. Как правило, в результате этой процедуры средняя приспособленность популяции возрастает, поскольку для скрещивания отбираются только лучшие особи первого поколения, а также небольшая доля менее приспособленных решений. Эти менее приспособленные решения обеспечивают генетическое разнообразие в генетическом пуле родителей и, следовательно, генетическое разнообразие последующего поколения потомков. Существуют разные точки зрения на важность кроссовера по сравнению с мутацией. В работе Фогеля (2006) приведено множество ссылок, подтверждающих важность поиска на основе мутаций. Хотя кроссовер и мутация известны как основные генетические операторы, в генетических алгоритмах можно использовать и другие операторы, такие как перегруппировка, вымирание колоний или миграция. Рекомендуется настраивать такие параметры, как вероятность мутации, вероятность кроссовера и размер популяции, чтобы найти оптимальные значения для решаемого класса задач. Слишком низкая скорость мутации может привести к генетическому дрейфу (который по своей природе не является эргодическим). Слишком высокая скорость рекомбинации может привести к преждевременной сходимости генетического алгоритма. Слишком высокая скорость мутации может привести к потере хороших решений, если не используется элитарный отбор. Адекватный размер популяции обеспечивает достаточное генетическое разнообразие для решаемой задачи, но может привести к нерациональному использованию вычислительных ресурсов, если задано значение, превышающее необходимое.

The next step is to generate a second generation population of solutions from those selected, through a combination of genetic operators: crossover (also called recombination), and mutation. For each new solution to be produced, a pair of "parent" solutions is selected for breeding from the pool selected previously. By producing a "child" solution using the above methods of crossover and mutation, a new solution is created which typically shares many of the characteristics of its "parents". New parents are selected for each new child, and the process continues until a new population of solutions of appropriate size is generated. Although reproduction methods that are based on the use of two parents are more "biology inspired", some research suggests that more than two "parents" generate higher quality chromosomes. These processes ultimately result in the next generation population of chromosomes that is different from the initial generation. Generally, the average fitness will have increased by this procedure for the population, since only the best organisms from the first generation are selected for breeding, along with a small proportion of less fit solutions. These less fit solutions ensure genetic diversity within the genetic pool of the parents and therefore ensure the genetic diversity of the subsequent generation of children. Opinion is divided over the importance of crossover versus mutation. There are many references in Fogel (2006) that support the importance of mutation based search. Although crossover and mutation are known as the main genetic operators, it is possible to use other operators such as regrouping, colonization extinction, or migration in genetic algorithms. It is worth tuning parameters such as the mutation probability, crossover probability and population size to find reasonable settings for the problem class being worked on. A very small mutation rate may lead to genetic drift (which is non ergodic in nature). A recombination rate that is too high may lead to premature convergence of the genetic algorithm. A mutation rate that is too high may lead to loss of good solutions, unless elitist selection is employed. An adequate population size ensures sufficient genetic diversity for the problem at hand, but can lead to a waste of computational resources if set to a value larger than required.

Эвристика

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

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

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

The simplest algorithm represents each chromosome as a bit string. Typically, numeric parameters can be represented by integers, though it is possible to use floating point representations. The floating point representation is natural to evolution strategies and evolutionary programming. The notion of real valued genetic algorithms has been offered but is really a misnomer because it does not really represent the building block theory that was proposed by John Henry Holland in the 1970s. This theory is not without support though, based on theoretical and experimental results (see below). The basic algorithm performs crossover and mutation at the bit level. Other variants treat the chromosome as a list of numbers which are indexes into an instruction table, nodes in a linked list, hashes, objects, or any other imaginable data structure. Crossover and mutation are performed so as to respect data element boundaries. For most data types, specific variation operators can be designed. Different chromosomal data types seem to work better or worse for different specific problem domains. When bit string representations of integers are used, Gray coding is often employed. In this way, small changes in the integer can be readily affected through mutations or crossovers. This has been found to help prevent premature convergence at so called Hamming walls, in which too many simultaneous mutations (or crossover events) must occur in order to change the chromosome to a better solution. Other approaches involve using arrays of real valued numbers instead of bit strings to represent chromosomes. Results from the theory of schemata suggest that in general the smaller the alphabet, the better the performance, but it was initially surprising to researchers that good results were obtained from using real valued chromosomes. This was explained as the set of real values in a finite population of chromosomes as forming a virtual alphabet (when selection and recombination are dominant) with a much lower cardinality than would be expected from a floating point representation. An expansion of the Genetic Algorithm accessible problem domain can be obtained through more complex encoding of the solution pools by concatenating several types of heterogenously encoded genes into one chromosome. This particular approach allows for solving optimization problems that require vastly disparate definition domains for the problem parameters. For instance, in problems of cascaded controller tuning, the internal loop controller structure can belong to a conventional regulator of three parameters, whereas the external loop could implement a linguistic controller (such as a fuzzy system) which has an inherently different description. This particular form of encoding requires a specialized crossover mechanism that recombines the chromosome by section, and it is a useful tool for the modelling and simulation of complex adaptive systems, especially evolution processes.

Элитизм

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

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

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

Адаптируемые газовые системы

Генетические алгоритмы с адаптивными параметрами (адаптивные генетические алгоритмы, АГА) – еще один значимый и перспективный вариант генетических алгоритмов. Вероятности кроссинговера (pc) и мутации (pm) во многом определяют степень точности решения и скорость сходимости, которой могут достичь генетические алгоритмы. Исследователи аналитически изучили сходимость ГА. Вместо использования фиксированных значений pc и pm, АГА используют информацию о популяции в каждом поколении и адаптивно корректируют pc и pm для поддержания разнообразия популяции и сохранения способности к сходимости. В АГА (адаптивном генетическом алгоритме) корректировка pc и pm зависит от значений пригодности решений. Существует множество примеров вариантов АГА: метод последовательного приближения – ранний пример улучшения сходимости. В CAGA (кластерном адаптивном генетическом алгоритме) корректировка pc и pm зависит от состояний оптимизации популяции, определяемых с помощью кластерного анализа. Современные подходы используют более абстрактные переменные для определения pc и pm. Примеры включают принципы доминирования и кодоминирования, а также LIGA (уровневый интерполятивный генетический алгоритм), который сочетает гибкий ГА с модифицированным поиском A* для решения проблемы анизотропии пространства поиска. Комбинирование ГА с другими методами оптимизации может быть весьма эффективным. ГА, как правило, хорошо находит хорошие глобальные решения, но неэффективен в поиске последних нескольких мутаций для достижения абсолютного оптимума. Другие методы (например, простое восхождение по склону) достаточно эффективны в поиске абсолютного оптимума в ограниченной области. Чередование ГА и восхождения по склону может повысить эффективность ГА, преодолевая при этом недостаточную устойчивость восхождения по склону. Это означает, что правила генетической вариации могут иметь иной смысл в естественных условиях. Например, если шаги хранятся последовательно, кроссинговер может суммировать ряд шагов из материнской ДНК, добавляя ряд шагов из отцовской ДНК и так далее. Это аналогично сложению векторов, которые, вероятно, будут следовать по гребню в фенотипическом ландшафте. Таким образом, эффективность процесса может быть увеличена на несколько порядков. Кроме того, оператор инверсии может располагать шаги последовательно или в любом другом подходящем порядке для повышения выживаемости или эффективности. Вариация, при которой эволюционирует вся популяция, а не отдельные ее члены, известна как рекомбинация генофонда. Разработано несколько вариаций для повышения производительности ГА при решении задач с высокой степенью эпистаза пригодности, то есть когда пригодность решения зависит от взаимодействующих подмножеств его переменных. Эти алгоритмы стремятся изучить (прежде чем использовать) эти полезные фенотипические взаимодействия. Таким образом, они соответствуют гипотезе строительных блоков, адаптивно снижая разрушительную рекомбинацию. Яркими примерами этого подхода являются mGA, GEMGA и LLGA.

Genetic algorithms with adaptive parameters (adaptive genetic algorithms, AGAs) is another significant and promising variant of genetic algorithms. The probabilities of crossover (pc) and mutation (pm) greatly determine the degree of solution accuracy and the convergence speed that genetic algorithms can obtain. Researchers have analyzed GA convergence analytically. Instead of using fixed values of pc and pm, AGAs utilize the population information in each generation and adaptively adjust the pc and pm in order to maintain the population diversity as well as to sustain the convergence capacity. In AGA (adaptive genetic algorithm), the adjustment of pc and pm depends on the fitness values of the solutions. There are more examples of AGA variants: Successive zooming method is an early example of improving convergence. In CAGA (clustering based adaptive genetic algorithm), through the use of clustering analysis to judge the optimization states of the population, the adjustment of pc and pm depends on these optimization states. Recent approaches use more abstract variables for deciding pc and pm. Examples are dominance & co dominance principles and LIGA (levelized interpolative genetic algorithm), which combines a flexible GA with modified A* search to tackle search space anisotropicity. It can be quite effective to combine GA with other optimization methods. A GA tends to be quite good at finding generally good global solutions, but quite inefficient at finding the last few mutations to find the absolute optimum. Other techniques (such as simple hill climbing) are quite efficient at finding absolute optimum in a limited region. Alternating GA and hill climbing can improve the efficiency of GA while overcoming the lack of robustness of hill climbing. This means that the rules of genetic variation may have a different meaning in the natural case. For instance – provided that steps are stored in consecutive order – crossing over may sum a number of steps from maternal DNA adding a number of steps from paternal DNA and so on. This is like adding vectors that more probably may follow a ridge in the phenotypic landscape. Thus, the efficiency of the process may be increased by many orders of magnitude. Moreover, the inversion operator has the opportunity to place steps in consecutive order or any other suitable order in favour of survival or efficiency. A variation, where the population as a whole is evolved rather than its individual members, is known as gene pool recombination. A number of variations have been developed to attempt to improve performance of GAs on problems with a high degree of fitness epistasis, i. e. where the fitness of a solution consists of interacting subsets of its variables. Such algorithms aim to learn (before exploiting) these beneficial phenotypic interactions. As such, they are aligned with the Building Block Hypothesis in adaptively reducing disruptive recombination. Prominent examples of this approach include the mGA, GEMGA and LLGA.

История

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

In 1950, Alan Turing proposed a "learning machine" which would parallel the principles of evolution. Computer simulation of evolution started as early as in 1954 with the work of Nils Aall Barricelli, who was using the computer at the Institute for Advanced Study in Princeton, New Jersey. His 1954 publication was not widely noticed. Starting in 1957, the Australian quantitative geneticist Alex Fraser published a series of papers on simulation of artificial selection of organisms with multiple loci controlling a measurable trait. From these beginnings, computer simulation of evolution by biologists became more common in the early 1960s, and the methods were described in books by Fraser and Burnell (1970) and Crosby (1973). Fraser's simulations included all of the essential elements of modern genetic algorithms. In addition, Hans Joachim Bremermann published a series of papers in the 1960s that also adopted a population of solution to optimization problems, undergoing recombination, mutation, and selection. Bremermann's research also included the elements of modern genetic algorithms. Other noteworthy early pioneers include Richard Friedberg, George Friedman, and Michael Conrad. Many early papers are reprinted by Fogel (1998). Although Barricelli, in work he reported in 1963, had simulated the evolution of ability to play a simple game, artificial evolution only became a widely recognized optimization method as a result of the work of Ingo Rechenberg and Hans Paul Schwefel in the 1960s and early 1970s – Rechenberg's group was able to solve complex engineering problems through evolution strategies. Another approach was the evolutionary programming technique of Lawrence J. Fogel, which was proposed for generating artificial intelligence. Evolutionary programming originally used finite state machines for predicting environments, and used variation and selection to optimize the predictive logics. Genetic algorithms in particular became popular through the work of John Holland in the early 1970s, and particularly his book Adaptation in Natural and Artificial Systems (1975). His work originated with studies of cellular automata, conducted by Holland and his students at the University of Michigan. Holland introduced a formalized framework for predicting the quality of the next generation, known as Holland's Schema Theorem. Research in GAs remained largely theoretical until the mid 1980s, when The First International Conference on Genetic Algorithms was held in Pittsburgh, Pennsylvania.

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

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

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

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

Evolutionary algorithms is a sub field of evolutionary computing. Evolution strategies (ES, see Rechenberg, 1994) evolve individuals by means of mutation and intermediate or discrete recombination. ES algorithms are designed particularly to solve problems in the real value domain. They use self adaptation to adjust control parameters of the search. De randomization of self adaptation has led to the contemporary Covariance Matrix Adaptation Evolution Strategy (CMA ES). Evolutionary programming (EP) involves populations of solutions with primarily mutation and selection and arbitrary representations. They use self adaptation to adjust parameters, and can include other variation operations such as combining information from multiple parents. Estimation of Distribution Algorithm (EDA) substitutes traditional reproduction operators by model guided operators. Such models are learned from the population by employing machine learning techniques and represented as Probabilistic Graphical Models, from which new solutions can be sampled or generated from guided crossover. Genetic programming (GP) is a related technique popularized by John Koza in which computer programs, rather than function parameters, are optimized. Genetic programming often uses tree based internal data structures to represent the computer programs for adaptation instead of the list structures typical of genetic algorithms. There are many variants of Genetic Programming, including Cartesian genetic programming, Gene expression programming, grammatical evolution, Linear genetic programming, Multi expression programming etc. Grouping genetic algorithm (GGA) is an evolution of the GA where the focus is shifted from individual items, like in classical GAs, to groups or subset of items. The idea behind this GA evolution proposed by Emanuel Falkenauer is that solving some complex problems, a. k. a. clustering or partitioning problems where a set of items must be split into disjoint group of items in an optimal way, would better be achieved by making characteristics of the groups of items equivalent to genes. These kind of problems include bin packing, line balancing, clustering with respect to a distance measure, equal piles, etc., on which classic GAs proved to perform poorly. Making genes equivalent to groups implies chromosomes that are in general of variable length, and special genetic operators that manipulate whole groups of items. For bin packing in particular, a GGA hybridized with the Dominance Criterion of Martello and Toth, is arguably the best technique to date. Interactive evolutionary algorithms are evolutionary algorithms that use human evaluation. They are usually applied to domains where it is hard to design a computational fitness function, for example, evolving images, music, artistic designs and forms to fit users' aesthetic preference.

Разумный рой

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

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

Эволюционные вычисления являются подполем метаэвристических методов. Меметический алгоритм (МА), часто называемый гибридным генетическим алгоритмом, представляет собой метод, основанный на популяции, в котором решения также подвергаются фазам локального улучшения. Идея меметических алгоритмов происходит от мемов, которые, в отличие от генов, способны к самоадаптации. В некоторых областях они показали более высокую эффективность по сравнению с традиционными эволюционными алгоритмами. Бактериологические алгоритмы (БА) вдохновлены эволюционной экологией и, в частности, бактериологической адаптацией. Эволюционная экология – это изучение живых организмов в контексте их среды обитания с целью выяснения механизмов их адаптации. Её основная концепция заключается в том, что в гетерогенной среде не существует единого организма, оптимально приспособленного ко всей среде. Поэтому необходимо рассматривать задачу на уровне популяции. Также предполагается, что БА могут быть успешно применены для решения сложных задач позиционирования (антенны для сотовых телефонов, градостроительство и т.д.) или интеллектуального анализа данных. Культурный алгоритм (КА) состоит из компонента популяции, почти идентичного генетическому алгоритму, и дополнительного компонента знаний, называемого пространством убеждений. Дифференциальная эволюция (ДЭ) вдохновлена миграцией суперорганизмов. Гауссова адаптация (нормальная или естественная адаптация, сокращенно NA для избежания путаницы с GA) предназначена для максимизации выхода при производстве систем обработки сигналов. Она также может использоваться для обычной параметрической оптимизации. Она опирается на определенную теорему, справедливую для всех областей допустимости и всех гауссовских распределений. Эффективность NA основана на теории информации и определенной теореме об эффективности. Её эффективность определяется как информация, деленная на работу, необходимую для получения этой информации. Поскольку NA максимизирует среднюю приспособленность, а не приспособленность отдельного индивида, ландшафт сглаживается, что может привести к исчезновению долин между пиками. Таким образом, NA обладает определенной "стремлением" избегать локальных максимумов в пространстве приспособленности. NA также хорошо справляется с подъемом на острые гребни за счет адаптации матриц моментов, поскольку NA может максимизировать беспорядок (среднюю информацию) гауссовского распределения, одновременно поддерживая постоянную среднюю приспособленность.

Evolutionary computation is a sub field of the metaheuristic methods. Memetic algorithm (MA), often called hybrid genetic algorithm among others, is a population based method in which solutions are also subject to local improvement phases. The idea of memetic algorithms comes from memes, which unlike genes, can adapt themselves. In some problem areas they are shown to be more efficient than traditional evolutionary algorithms. Bacteriologic algorithms (BA) inspired by evolutionary ecology and, more particularly, bacteriologic adaptation. Evolutionary ecology is the study of living organisms in the context of their environment, with the aim of discovering how they adapt. Its basic concept is that in a heterogeneous environment, there is not one individual that fits the whole environment. So, one needs to reason at the population level. It is also believed BAs could be successfully applied to complex positioning problems (antennas for cell phones, urban planning, and so on) or data mining. Cultural algorithm (CA) consists of the population component almost identical to that of the genetic algorithm and, in addition, a knowledge component called the belief space. Differential evolution (DE) inspired by migration of superorganisms. Gaussian adaptation (normal or natural adaptation, abbreviated NA to avoid confusion with GA) is intended for the maximisation of manufacturing yield of signal processing systems. It may also be used for ordinary parametric optimisation. It relies on a certain theorem valid for all regions of acceptability and all Gaussian distributions. The efficiency of NA relies on information theory and a certain theorem of efficiency. Its efficiency is defined as information divided by the work needed to get the information. Because NA maximises mean fitness rather than the fitness of the individual, the landscape is smoothed such that valleys between peaks may disappear. Therefore it has a certain "ambition" to avoid local peaks in the fitness landscape. NA is also good at climbing sharp crests by adaptation of the moment matrix, because NA may maximise the disorder (average information) of the Gaussian simultaneously keeping the mean fitness constant.

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

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

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

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