В компьютерном программировании генетическое представление — это способ представления решений/людей в эволюционных методах вычислений. Этот термин охватывает как конкретные структуры данных и типы данных, используемые для реализации генетического материала возможных решений в форме генома, так и отношения между пространством поиска и пространством проблем. В простейшем случае пространство поиска соответствует проблемному пространству (прямое представление). [1] Выбор представления задачи связан с выбором генетических операторов , оба из которых оказывают решающее влияние на эффективность оптимизации. [2] [3] Генетическая репрезентация может кодировать внешний вид, поведение, физические качества особей. Различие в генетических представлениях является одним из основных критериев, проводящих грань между известными классами эволюционных вычислений. [4] [5]
Терминология часто аналогична естественной генетике . Блок компьютерной памяти, представляющий один вариант решения, называется индивидуальным. Данные в этом блоке называются хромосомой . Каждая хромосома состоит из генов. Возможные значения конкретного гена называются аллелями . Программист может представлять всех особей популяции, используя двоичное кодирование , перестановочное кодирование , кодирование деревом или любое из нескольких других представлений. [6] [7]
Генетические алгоритмы (ГА) обычно представляют собой линейные представления; [8] они часто, но не всегда, [9] [10] [11] бинарные. [10] В первоначальном описании ГА Холландом использовались массивы битов . Массивы других типов и структур можно использовать по существу таким же образом. Основное свойство, делающее эти генетические представления удобными, заключается в том, что их части легко выравниваются благодаря фиксированному размеру. Это облегчает простую работу кроссовера. В зависимости от применения представления переменной длины также успешно используются и тестируются в эволюционных алгоритмах (ЭА) [12] [13] в целом и генетических алгоритмах [14] [15] в частности, хотя реализация кроссовера более сложна. в этом случае.
Стратегия эволюции использует линейные вещественные представления, например, массив действительных значений. Он использует в основном гауссову мутацию и кроссовер смешивания/усреднения. [16]
Генетическое программирование (GP) стало пионером в древовидных представлениях и разработало генетические операторы, подходящие для таких представлений. Древовидные представления используются в GP для представления и развития функциональных программ с желаемыми свойствами. [17]
Генетический алгоритм, основанный на человеке (HBGA), предлагает способ избежать решения сложных проблем представления путем передачи всех генетических операторов внешним агентам, в данном случае людям. Алгоритму не требуется знание конкретного фиксированного генетического представления, если имеется достаточно внешних агентов, способных обрабатывать эти представления, что позволяет создавать генетические представления в свободной форме и развивать их.
Аналогично биологии, ЭА различают проблемное пространство (соответствует фенотипу ) и пространство поиска (соответствует генотипу ). Пространство проблем содержит конкретные решения решаемой проблемы, а пространство поиска содержит закодированные решения. Отображение пространства поиска в пространство проблем называется отображением генотипа-фенотипа . Генетические операторы применяются к элементам пространства поиска, и для оценки элементы пространства поиска сопоставляются с элементами проблемного пространства посредством сопоставления генотип-фенотип. [18] [19]
Важность правильного выбора пространства поиска для успеха приложения EA была признана на раннем этапе. [20] [21] [22] К подходящему пространству поиска и, следовательно, к подходящему сопоставлению генотип-фенотип могут быть предъявлены следующие требования: [23] [24]
Все возможные допустимые решения должны содержаться в пространстве поиска.
Когда существует больше возможных генотипов, чем фенотипов, генетическое представление EA называется избыточным . В природе это называется вырожденным генетическим кодом . В случае избыточного представления возможны нейтральные мутации . Это мутации, которые изменяют генотип, но не влияют на фенотип. Таким образом, в зависимости от использования генетических операторов потомство может быть фенотипически неизмененным, что, среди прочего, может привести к ненужным определениям приспособленности. Поскольку на оценку в реальных приложениях обычно приходится львиная доля времени вычислений, это может замедлить процесс оптимизации . Кроме того, это может привести к тому, что генотипическое разнообразие популяции будет выше фенотипического, что также может препятствовать эволюционному прогрессу.
В биологии нейтральная теория молекулярной эволюции утверждает, что этот эффект играет доминирующую роль в естественной эволюции. Это побудило исследователей из сообщества EA изучить, могут ли нейтральные мутации улучшить функционирование EA [25] , давая популяциям, которые достигли локального оптимума, способ избежать этого локального оптимума посредством генетического дрейфа . Этот вопрос обсуждается противоречиво, и окончательных результатов по нейтральности советников нет. [26] [27] С другой стороны, существуют и другие проверенные меры по борьбе с преждевременной конвергенцией .
Локальность генетического представления соответствует степени, в которой расстояния в пространстве поиска сохраняются в проблемном пространстве после картирования генотип-фенотип. То есть представление имеет высокую локальность именно тогда, когда соседи в пространстве поиска также являются соседями в проблемном пространстве. Чтобы успешные схемы не были уничтожены картированием генотипа-фенотипа после незначительной мутации , локальность репрезентации должна быть высокой.
При картировании генотипа-фенотипа элементы генотипа могут масштабироваться (взвешиваться) по-разному. Самый простой случай — равномерное масштабирование: все элементы генотипа имеют одинаковый вес в фенотипе. Обычное масштабирование является экспоненциальным. Если целые числа закодированы в двоичном формате, отдельные цифры результирующего двоичного числа имеют экспоненциально разные веса при представлении фенотипа.
По этой причине экспоненциальное масштабирование приводит к случайной фиксации «задних» положений генотипа до того, как популяция приблизится достаточно близко к оптимуму, чтобы можно было приспособиться к этим тонкостям.
При сопоставлении генотипа с оцениваемым фенотипом можно использовать знания, специфичные для предметной области, для улучшения фенотипа и/или обеспечения соблюдения ограничений. [28] [29] Это широко используемый метод улучшения производительности советника с точки зрения времени выполнения и качества решения. Ниже это проиллюстрировано двумя из трех примеров.
Очевидным и часто используемым кодированием для задачи коммивояжера и связанных с ней задач является последовательное нумерование городов, которые необходимо посетить, и сохранение их в виде целых чисел в хромосоме . Генетические операторы должны быть соответствующим образом адаптированы, чтобы они меняли только порядок городов (генов) и не вызывали делеций или дупликаций. [30] [31] Таким образом, порядок генов соответствует порядку города, и существует простое взаимно-однозначное сопоставление.
В задаче планирования с гетерогенными и частично альтернативными ресурсами, которые должны быть назначены набору подзадач, геном должен содержать всю необходимую информацию для отдельных операций планирования или должна быть возможность получить ее из него. Помимо порядка выполнения подзадач сюда входит информация о выборе ресурса. [32] Фенотип тогда состоит из списка подзадач с указанием времени их начала и назначенных ресурсов. Для этого необходимо создать столько матриц распределения , сколько ресурсов можно выделить максимум для одной подзадачи. В простейшем случае это один ресурс, например одна машина, которая может выполнить подзадачу. Матрица распределения представляет собой двумерную матрицу, в которой одно измерение представляет собой доступные единицы времени, а другое — ресурсы, которые необходимо выделить. Пустые ячейки матрицы указывают на доступность, а запись указывает номер назначенной подзадачи. Создание матриц распределения гарантирует, во-первых, отсутствие недопустимых множественных распределений. Во-вторых, из него можно прочитать время начала подзадач и назначенные ресурсы. [33]
Общее ограничение при планировании ресурсов для подзадач заключается в том, что ресурс может быть выделен только один раз за единицу времени и что резервирование должно осуществляться на непрерывный период времени. [34] Чтобы достичь этого своевременно, что является общей целью оптимизации, а не ограничением, можно использовать простую эвристику : выделить требуемый ресурс на желаемый период времени как можно раньше, избегая дублирования резервирований. Преимущество этой простой процедуры двоякое: она позволяет избежать ограничений и помогает оптимизации.
Если проблема планирования меняется на планирование рабочих процессов вместо независимых подзадач, по крайней мере, некоторые рабочие этапы рабочего процесса должны выполняться в заданном порядке. [35] Если ранее описанная эвристика планирования теперь определяет, что предшественник рабочего шага не завершен, когда он должен быть запущен сам, может помочь следующий механизм восстановления: отложить планирование этого рабочего шага до тех пор, пока не будут завершены все его предшественники. [33] Поскольку генотип остается неизменным и репарация осуществляется только на уровне фенотипа, ее также называют фенотипической репарацией .
Следующая задача планирования компоновки [36] призвана проиллюстрировать другое использование эвристики при картировании генотипа-фенотипа: на прямоугольной поверхности различные геометрические типы объектов должны быть расположены таким образом, чтобы как можно меньшая площадь оставалась неиспользованной. Объекты можно вращать, они не должны перекрываться после размещения и должны полностью располагаться на поверхности. Аналогичным применением может быть минимизация отходов при резке деталей из стальной пластины или тканевого листа.
В качестве переменных, подлежащих определению, можно рассматривать координаты центров объектов и угол поворота, приведенный к возможным изоморфизмам геометрии объектов. Если это будет сделано непосредственно советником, вероятно, будет много совпадений. Чтобы этого избежать, советник определяет только угол и координату одной стороны прямоугольника. Каждый объект теперь поворачивается и размещается на краю этой стороны, при необходимости сдвигая его так, чтобы он находился внутри прямоугольника при последующем перемещении. Затем его перемещают параллельно другой стороне, пока он не коснется другого объекта или не достигнет противоположного конца прямоугольника. Таким образом избегаются дублирования и уменьшается неиспользуемая площадь для каждого места размещения, а не в целом, что остается на усмотрение оптимизации. [37]