Хромосома (генетический алгоритм)

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

Хромосомный дизайн

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

Хорошо подходящая хромосома должна отвечать следующим требованиям:

• Он должен обеспечивать доступность всех допустимых точек в пространстве поиска.
• Спроектируйте хромосому таким образом, чтобы она охватывала только пространство поиска и не содержала дополнительных областей. так, чтобы не было избыточности или избыточность была настолько минимальной, насколько это возможно.

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

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

Примеры хромосом

Хромосомы для двоичного кодирования

В своей классической форме ГА используют битовые строки и отображают в них переменные решения, подлежащие оптимизации. Пример для одной логической и трех целочисленных переменных решения с диапазонами значений $0\leq D_{1}\leq 60$, $28\leq D_{2}\leq 30$ и $-12\leq D_{3}\leq 14$ может проиллюстрировать это:

Пример представления четырех переменных решения в битовой строке

переменная решения:	$D_{1}=22$						$D_{2}=29$					$D_{3}=-4$					$D_{4}=0$
биты:	0	1	0	1	1	0	1	1	1	0	1	1	1	1	0	0	0
позиция:	17	16	15	14	13	12	11	10	9	8	7	6	5	4	3	2	1

Обратите внимание, что здесь отрицательное число задается в дополнении до двух . Это прямое представление использует пять бит для представления трех значений $D_{2}$, хотя двух битов будет достаточно. Это значительная избыточность. Улучшенная альтернатива, в которой для картирования генотипа-фенотипа необходимо добавить 28, может выглядеть так:

Пример улучшенного представления четырех переменных решения

переменная решения:	$D_{1}=22$						$D'_{2}=1$		$D_{3}=-4$					$D_{4}=0$
биты:	0	1	0	1	1	0	0	1	1	1	1	0	0	0
позиция:	14	13	12	11	10	9	8	7	6	5	4	3	2	1

с $D_{2}=28+D'_{2}=29$.

с вещественными или

Для обработки задач с вещественными или смешанно-целочисленными переменными решения используются советники, такие как стратегия эволюции. или реальные кодированные GA подходят. В случае смешанно-целых значений часто используется округление, но это представляет собой некоторое нарушение требования избыточности . Если необходимую точность реальных значений можно разумно сузить, это нарушение можно исправить с помощью ГА с целочисленным кодированием. Для этого действительные цифры действительных значений преобразуются в целые числа путем умножения на подходящий коэффициент. Например, 12,380 становится целым числом 12380 при умножении на 1000. Это, конечно, необходимо учитывать при картировании генотипа-фенотипа для оценки и представления результатов. Распространенной формой является хромосома, состоящая из списка или массива целых или вещественных значений.

Хромосомы для перестановок

Комбинаторные задачи в основном связаны с поиском оптимальной последовательности набора элементарных элементов. В качестве примера рассмотрим задачу коммивояжера , который хочет посетить заданное количество городов ровно один раз за максимально короткий тур. Самое простое и очевидное отображение на хромосоме — это последовательно пронумеровать города, интерпретировать полученную последовательность как перестановку и сохранить ее непосредственно в хромосоме, где один ген соответствует порядковому номеру города. Однако тогда операторы вариации могут только изменять порядок генов, но не удалять или дублировать какие-либо гены. Таким образом, хромосома содержит путь возможного путешествия в города. Например, последовательность $3,5,7,1,4,2,9,6,8$ может служить девять городов, которым соответствует следующая хромосома:

3

5

7

1

4

2

9

6

8

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

Хромосомы для совместной эволюции

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

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

Хромосомы для сложных представлений

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

Три типичных гена, соответствующие определениям соседних типов генов в хромосоме, организованные в виде списка.

Три типичных гена, соответствующие определениям соседних типов генов в хромосоме, организованные в виде списка.

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

Синтаксическое дерево примера формулы

Хромосомы для древовидных представлений

Древовидные представления в хромосоме используются генетическим программированием , типом ЭА для создания компьютерных программ или схем . Деревья соответствуют синтаксическим деревьям, генерируемым компилятором в качестве внутреннего представления при переводе компьютерной программы. На соседнем рисунке в качестве примера показано синтаксическое дерево математического выражения. Операторы мутации могут переупорядочивать, изменять или удалять поддеревья в зависимости от представленной синтаксической структуры. Рекомбинация осуществляется путем замены подходящих поддеревьев.

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

• Томас Бек (1996): Эволюционные алгоритмы в теории и практике: стратегии эволюции, эволюционное программирование, генетические алгоритмы , Оксфордский университет. Нажимать. ISBN   978-0-19-509971-3
• Вольфганг Банцхаф, П. Нордин, Р. Келлер, Ф. Франконе (1998): Генетическое программирование – Введение , Морган Кауфманн, Сан-Франциско. ISBN   1-55860-510-X
• Кеннет А. де Йонг (2006): Эволюционные вычисления: единый подход. MIT Press, Кембридж, Массачусетс. ISBN   0-262-04194-4
• Мелани Митчелл (1996): Введение в генетические алгоритмы. MIT Press, Кембридж, Массачусетс. ISBN   978-0-262-63185-3
• Ханс-Поль Швефель (1995): Эволюция и поиск оптимума . Уайли и сыновья, Нью-Йорк. ISBN   0-471-57148-2