Сравнивайте с английским: нажмите на абзац — оригинал откроется в окне. Кнопка EN под абзацем показывает его прямо в тексте.
Содержание
Введение
Набор параметров генетического или эволюционного алгоритма
Set of parameters for a genetic or evolutionary algorithm
В генетических алгоритмах (GA) или, в более общем смысле, эволюционных алгоритмах (EA), хромосома (также иногда называемая генотипом) представляет собой набор параметров, определяющих предлагаемое решение проблемы, которую алгоритм пытается решить. Совокупность всех решений, также называемых индивидуумами в соответствии с биологической моделью, известна как популяция. Геном индивидуума состоит из одной, реже нескольких хромосом и соответствует генетическому представлению задачи, которую необходимо решить. Хромосома состоит из набора генов, где ген состоит из одного или нескольких семантически связанных параметров, которые часто также называют переменными принятия решений. Они определяют одну или несколько фенотипических характеристик индивидуума или, по крайней мере, влияют на них. В то же время, в более поздних вариантах и в EA в целом используется большое разнообразие других структур данных.
In genetic algorithms (GA), or more general, evolutionary algorithms (EA), a chromosome (also sometimes called a genotype) is a set of parameters which define a proposed solution of the problem that the evolutionary algorithm is trying to solve. The set of all solutions, also called individuals according to the biological model, is known as the population. The genome of an individual consists of one, more rarely of several, chromosomes and corresponds to the genetic representation of the task to be solved. A chromosome is composed of a set of genes, where a gene consists of one or more semantically connected parameters, which are often also called decision variables. They determine one or more phenotypic characteristics of the individual or at least have an influence on them. while in later variants and in EAs in general, a wide variety of other data structures are used.
Хромосомы с генами с реальными значениями или целыми числами
Для обработки задач с действительными или смешанными целочисленными переменными решения хорошо подходят эволюционные алгоритмы, такие как стратегия эволюции или генетические алгоритмы с действительным кодированием. В случае смешанных целочисленных значений часто используется округление, однако это приводит к некоторому нарушению требования избыточности. Если требуемую точность действительных значений можно разумно ограничить, это нарушение можно устранить, используя генетические алгоритмы с целочисленным кодированием. Для этого значащие цифры действительных значений преобразуются в целые числа путем умножения на подходящий множитель. Например, число 12.380 становится целым числом 12380 при умножении на 1000. Это, разумеется, необходимо учитывать при отображении генотипа в фенотип для оценки и представления результатов. Распространенная форма представления – хромосома, состоящая из списка или массива целых или действительных значений.
For the processing of tasks with real valued or mixed integer decision variables, EAs such as the evolution strategy or the real coded GAs are suited. In the case of mixed integer values, rounding is often used, but this represents some violation of the redundancy requirement. If the necessary precisions of the real values can be reasonably narrowed down, this violation can be remedied by using integer coded GAs. For this purpose, the valid digits of real values are mapped to integers by multiplication with a suitable factor. For example, 12.380 becomes the integer 12380 by multiplying by 1000. This must of course be taken into account in genotype phenotype mapping for evaluation and result presentation. A common form is a chromosome consisting of a list or an array of integer or real values.
Хромосомы для коэволюции
Когда генетическое представление содержит, помимо переменных решения, дополнительную информацию, влияющую на эволюцию и/или отображение генотипа в фенотип и сама подвергается эволюции, это называется коэволюцией. Типичным примером является стратегия эволюции (ES), которая включает один или несколько размеров шага мутации в качестве параметров стратегии в каждой хромосоме. Этот подход основан на предположении, что хорошие решения достигаются благодаря соответствующему выбору параметров стратегии или контрольных генов, влияющих на отображение генотипа в фенотип. Успех стратегии ES подтверждает это предположение.
When a genetic representation contains, in addition to the decision variables, additional information that influences evolution and/or the mapping of the genotype to the phenotype and is itself subject to evolution, this is referred to as co evolution. A typical example is the evolution strategy (ES), which includes one or more mutation step sizes as strategy parameters in each chromosome. This approach is based on the assumption that good solutions are based on an appropriate selection of strategy parameters or on control gene(s) that influences genotype phenotype mapping. The success of the ES gives evidence to this assumption.
Хромосомы для сложных представлений
Представленные выше хромосомы хорошо подходят для решения задач непрерывной, смешанной целочисленной, чисто целочисленной или комбинаторной оптимизации. Однако, для комбинации этих областей оптимизации становится все сложнее отобразить их на простые строки значений, в зависимости от конкретной задачи. Для решения этой проблемы в EA GLEAM (Общий эволюционный алгоритм обучения и метод) предлагается следующее расширение концепции гена: ген рассматривается как описание элемента или элементарного признака фенотипа, который может иметь несколько параметров. Для этого определяются типы генов, содержащие столько параметров соответствующего типа данных, сколько необходимо для описания конкретного элемента фенотипа. Хромосома теперь состоит из генов как объектов данных соответствующих типов генов, при этом, в зависимости от области применения, каждый тип гена может встречаться в хромосоме ровно один раз или содержаться в ней любое количество раз. Последнее приводит к хромосомам динамической длины, что необходимо для решения некоторых задач. Определения типов генов также содержат информацию о допустимых диапазонах значений параметров гена, которые учитываются при генерации хромосом и в ходе мутаций, чтобы избежать летальных мутаций. Для задач с комбинаторной составляющей существуют подходящие генетические операторы, способные перемещать или перепозиционировать гены целиком, вместе с их параметрами. В качестве примера приводится задача планирования, в которой необходимо спланировать рабочие процессы, требующие различного количества разнородных ресурсов. Рабочий процесс определяет, какие этапы работы могут выполняться параллельно, а какие последовательно. В данном контексте разнородные ресурсы подразумевают различные сроки выполнения и стоимость, а также различные вычислительные возможности.
The chromosomes presented above are well suited for processing tasks of continuous, mixed integer, pure integer or combinatorial optimization. For a combination of these optimization areas, on the other hand, it becomes increasingly difficult to map them to simple strings of values, depending on the task. The following extension of the gene concept is proposed by the EA GLEAM (General Learning Evolutionary Algorithm and Method) for this purpose: A gene is considered to be the description of an element or elementary trait of the phenotype, which may have multiple parameters. For this purpose, gene types are defined that contain as many parameters of the appropriate data type as are required to describe the particular element of the phenotype. A chromosome now consists of genes as data objects of the gene types, whereby, depending on the application, each gene type occurs exactly once as a gene or can be contained in the chromosome any number of times. The latter leads to chromosomes of dynamic length, as they are required for some problems. The gene type definitions also contain information on the permissible value ranges of the gene parameters, which are observed during chromosome generation and by corresponding mutations, so they cannot lead to lethal mutations. For tasks with a combinatorial part, there are suitable genetic operators that can move or reposition genes as a whole, i. e. with their parameters. A scheduling task is used as an illustration, in which workflows are to be scheduled that require different numbers of heterogeneous resources. A workflow specifies which work steps can be processed in parallel and which have to be executed one after the other. In this context, heterogeneous resources mean different processing times at different costs in addition to different processing capabilities.