stringtranslate.com

Генетическое представление

В компьютерном программировании генетическое представление — это способ представления решений/людей в эволюционных методах вычислений. Этот термин охватывает как конкретные структуры данных и типы данных, используемые для реализации генетического материала возможных решений в форме генома, так и отношения между пространством поиска и пространством проблем. В простейшем случае пространство поиска соответствует проблемному пространству (прямое представление). [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] С другой стороны, существуют и другие проверенные меры по борьбе с преждевременной конвергенцией .

Местонахождение

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

Масштабирование

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

Пример: Число 90 записывается в двоичном формате (т.е. по основанию два) как 1011010. Если теперь в двоичной записи изменить одну из передних цифр, это окажет значительно большее влияние на кодированное число, чем любые изменения задних цифр. ( давление отбора оказывает экспоненциально большее влияние на передние пальцы).

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

Гибридизация и репарация при картировании генотипа-фенотипа

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

Примеры

Пример прямого представления

Очевидным и часто используемым кодированием для задачи коммивояжера и связанных с ней задач является последовательное нумерование городов, которые необходимо посетить, и сохранение их в виде целых чисел в хромосоме . Генетические операторы должны быть соответствующим образом адаптированы, чтобы они меняли только порядок городов (генов) и не вызывали делеций или дупликаций. [30] [31] Таким образом, порядок генов соответствует порядку города, и существует простое взаимно-однозначное сопоставление.

Пример сложного картирования генотип-фенотип.

В задаче планирования с гетерогенными и частично альтернативными ресурсами, которые должны быть назначены набору подзадач, геном должен содержать всю необходимую информацию для отдельных операций планирования или должна быть возможность получить ее из него. Помимо порядка выполнения подзадач сюда входит информация о выборе ресурса. [32] Фенотип тогда состоит из списка подзадач с указанием времени их начала и назначенных ресурсов. Для этого необходимо создать столько матриц распределения , сколько ресурсов можно выделить максимум для одной подзадачи. В простейшем случае это один ресурс, например одна машина, которая может выполнить подзадачу. Матрица распределения представляет собой двумерную матрицу, в которой одно измерение представляет собой доступные единицы времени, а другое — ресурсы, которые необходимо выделить. Пустые ячейки матрицы указывают на доступность, а запись указывает номер назначенной подзадачи. Создание матриц распределения гарантирует, во-первых, отсутствие недопустимых множественных распределений. Во-вторых, из него можно прочитать время начала подзадач и назначенные ресурсы. [33]

Общее ограничение при планировании ресурсов для подзадач заключается в том, что ресурс может быть выделен только один раз за единицу времени и что резервирование должно осуществляться на непрерывный период времени. [34] Чтобы достичь этого своевременно, что является общей целью оптимизации, а не ограничением, можно использовать простую эвристику : выделить требуемый ресурс на желаемый период времени как можно раньше, избегая дублирования резервирований. Преимущество этой простой процедуры двоякое: она позволяет избежать ограничений и помогает оптимизации.

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

Пример эвристического сопоставления генотип-фенотип

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

В качестве переменных, подлежащих определению, можно рассматривать координаты центров объектов и угол поворота, приведенный к возможным изоморфизмам геометрии объектов. Если это будет сделано непосредственно советником, вероятно, будет много совпадений. Чтобы этого избежать, советник определяет только угол и координату одной стороны прямоугольника. Каждый объект теперь поворачивается и размещается на краю этой стороны, при необходимости сдвигая его так, чтобы он находился внутри прямоугольника при последующем перемещении. Затем его перемещают параллельно другой стороне, пока он не коснется другого объекта или не достигнет противоположного конца прямоугольника. Таким образом избегаются дублирования и уменьшается неиспользуемая площадь для каждого места размещения, а не в целом, что остается на усмотрение оптимизации. [37]

Рекомендации

  1. ^ Эйбен, А.Э.; Смит, Дж. Э. (2015). Введение в эволюционные вычисления. Серия естественных вычислений. Берлин, Гейдельберг: Springer. п. 40. дои : 10.1007/978-3-662-44874-8. ISBN 978-3-662-44873-1. S2CID  20912932.
  2. ^ Ротлауф, Франц (2002). Представления для генетических и эволюционных алгоритмов. Исследования нечеткости и мягких вычислений. Том. 104. Гейдельберг: Physica-Verlag HD. п. 31. дои : 10.1007/978-3-642-88094-0. ISBN 978-3-642-88096-4.
  3. ^ Эйбен, А.Э.; Смит, Дж. Э. (2015). «Представление и роли операторов вариации». Введение в эволюционные вычисления. Серия естественных вычислений. Берлин, Гейдельберг: Springer. стр. 49–51. дои : 10.1007/978-3-662-44874-8. ISBN 978-3-662-44873-1. S2CID  20912932.
  4. ^ Эйбен, А.Э.; Смит, Дж. Э. (2015). «Популярные варианты эволюционных алгоритмов». Введение в эволюционные вычисления. Серия естественных вычислений. Берлин, Гейдельберг: Springer. стр. 99–118. дои : 10.1007/978-3-662-44874-8. ISBN 978-3-662-44873-1. S2CID  20912932.
  5. ^ Фогель, Д.Б. (1995). «Фенотипы, генотипы и операторы в эволюционных вычислениях». Материалы Международной конференции IEEE 1995 года по эволюционным вычислениям . Том. 1. Перт, Вашингтон, Австралия: IEEE. стр. 193–198. doi : 10.1109/ICEC.1995.489143. ISBN 978-0-7803-2759-7. S2CID  17755853.
  6. ^ Томаш Кутан и Ян Лански. «Генетические алгоритмы слогового сжатия текста». 2007. с. 26.
  7. ^ Эйбен, А.Э.; Смит, Дж. Э. (2015). «Представление, мутация и рекомбинация». Введение в эволюционные вычисления. Серия естественных вычислений. Берлин, Гейдельберг: Springer. стр. 49–78. дои : 10.1007/978-3-662-44874-8. ISBN 978-3-662-44873-1. S2CID  20912932.
  8. ^ Голдберг, Дэвид Э. (1989). Генетические алгоритмы в поиске, оптимизации и машинном обучении . Ридинг, Массачусетс: Аддисон-Уэсли. ISBN 0-201-15767-5. ОСЛК  17674450.
  9. ^ Михалевич, Збигнев (1996). Генетические алгоритмы + Структуры данных = Программы эволюции . 3-е, исправленное и дополненное издание. Берлин, Гейдельберг: Springer. ISBN 978-3-662-03315-9. ОСЛК  851375253.
  10. ^ аб Уитли, Даррелл (1994). «Урок по генетическому алгоритму». Статистика и вычисления . 4 (2). дои : 10.1007/BF00175354. ISSN  0960-3174. S2CID  3447126.
  11. ^ Эррера, Ф.; Лозано, М.; Вердегей, Дж. Л. (1998). «Решение генетических алгоритмов реального кода: операторы и инструменты для поведенческого анализа». Обзор искусственного интеллекта . 12 (4): 265–319. дои : 10.1023/А: 1006504901164. S2CID  6798965.
  12. ^ Блюм, Кристиан; Якоб, Уилфрид (2002), «GLEAM - эволюционный алгоритм планирования и контроля, основанный на стратегии эволюции», Conf. Учеб. конференции по генетическим и эволюционным вычислениям (GECCO 2002) , том. Late Breaking Papers, стр. 31–38 , получено 1 января 2023 г.
  13. ^ Хитоми, Нозоми; Сельва, Дэниел (2018), «Оптимизация созвездия с использованием эволюционного алгоритма с хромосомой переменной длины», Аэрокосмическая конференция IEEE 2018 , IEEE, стр. 1–12, doi : 10.1109/AERO.2018.8396743, ISBN 978-1-5386-2014-4, S2CID  49541423
  14. ^ Де Йонг, Кеннет А. (2006). "Представление". Эволюционные вычисления: единый подход. Нью-Дели: Прентис-Холл Индии. стр. 72–75. ISBN 978-81-203-3002-3. ОСЛК  276452339.
  15. ^ Павар, Сунил Нилкант; Бичкар, Раджанкумар Садашиврао (2015). «Генетический алгоритм с хромосомами переменной длины для обнаружения сетевых вторжений». Международный журнал автоматизации и вычислений . 12 (3): 337–342. дои : 10.1007/s11633-014-0870-x . ISSN  1476-8186. S2CID  255346767.
  16. ^ Швефель, Ханс-Пол (1995). Эволюция и поиск оптимального. Нью-Йорк: Wiley & Sons. ISBN 0-471-57148-2. ОСЛК  30701094.
  17. ^ Коза, Джон Р. (1989), Шридхаран, Н.С. (редактор), «Иерархические генетические алгоритмы, работающие с популяциями компьютерных программ», Труды одиннадцатой международной совместной конференции по искусственному интеллекту IJCAI-89 , том. 1, Сан-Матео, Калифорния, США: Морган Кауфманн, стр. 768–774.
  18. ^ Ротлауф, Франц (2002). Представления для генетических и эволюционных алгоритмов. Исследования нечеткости и мягких вычислений. Том. 104. Гейдельберг: Physica-Verlag HD. дои : 10.1007/978-3-642-88094-0. ISBN 978-3-642-88096-4.
  19. ^ Уигэм, Питер А.; Дик, Грант; Маклорен, Джеймс (2017). «О сопоставлении генотипа с фенотипом в эволюционных алгоритмах». Генетическое программирование и развивающиеся машины . 18 (3): 353–361. doi : 10.1007/s10710-017-9288-x. ISSN  1389-2576. S2CID  254510517.
  20. ^ Каруана, Ричард А.; Шаффер, Дж. Дэвид (1988), «Представление и скрытая предвзятость: Грей против двоичного кодирования для генетических алгоритмов», Machine Learning Proceedings 1988 , Elsevier, стр. 153–161, doi : 10.1016/b978-0-934613-64- 4.50021-9, ISBN 978-0-934613-64-4, получено 19 января 2023 г.
  21. ^ Лиепиньш, Гунар Э.; Восе, Майкл Д. (1990). «Репрезентативные проблемы в генетической оптимизации». Журнал экспериментального и теоретического искусственного интеллекта . 2 (2): 101–115. дои : 10.1080/09528139008953717. ISSN  0952-813Х.
  22. ^ Коли, М.; Палаццари, П. (1995), «Поиск оптимального кодирования в генетических алгоритмах», Материалы Международной конференции IEEE по эволюционным вычислениям 1995 г. , IEEE, doi : 10.1109/ICEC.1995, ISBN 978-0-7803-2759-7
  23. ^ Эйбен, Агостон Э. (2015). «Представительство (Определение физических лиц)». Введение в эволюционные вычисления . Дж. Э. Смит (2-е изд.). Берлин, Гейдельберг: Springer. стр. 28–30. ISBN 978-3-662-44874-8. ОКЛК  913232837.
  24. ^ Ротлауф, Франц (2006). «Три элемента теории представлений». Представления для генетических и эволюционных алгоритмов (2-е изд.). Гейдельберг: Спрингер. стр. 33–96. ISBN 978-3-540-32444-7. ОСЛК  262692044.
  25. ^ Гальван-Лопес, Эдгар; Дигнум, Стивен; Поли, Риккардо (2008), О'Нил, Майкл; Ваннески, Леонардо; Густафсон, Стивен; Эспарсия Алькасар, Анна Изабель (ред.), «Влияние постоянной нейтральности на производительность и сложность задач в общей практике», Генетическое программирование , Конспекты лекций по информатике, том. 4971, Берлин, Гейдельберг: Springer, стр. 312–324, номер документа : 10.1007/978-3-540-78671-9_27, ISBN. 978-3-540-78670-2, S2CID  6803107 , получено 21 января 2023 г.
  26. ^ Гальван-Лопес, Эдгар; Поли, Риккардо; Каттан, Ахмед; О'Нил, Майкл; Брабазон, Энтони (2011). «Нейтралитет в эволюционных алгоритмах… Что мы знаем?». Развивающиеся системы . 2 (3): 145–163. дои : 10.1007/s12530-011-9030-5. hdl : 10197/3532 . ISSN  1868-6478. S2CID  15951086.
  27. ^ Ноулз, Джошуа Д.; Уотсон, Ричард А. (2002), Гервос, Хуан Хулиан Мерело; Адамидис, Панайотис; Бейер, Ханс-Георг; Швефель, Ханс-Пауль (ред.), «О полезности избыточных кодировок в эволюционном поиске на основе мутаций», Параллельное решение проблем из природы - PPSN VII , том. 2439, Берлин, Гейдельберг: Springer, стр. 88–98, номер документа : 10.1007/3-540-45712-7_9, ISBN. 978-3-540-44139-7, получено 21 января 2023 г.
  28. ^ Эйбен, А.Э.; Смит, Дж. Э. (2015). «Гибридизация во время картирования генотипа и фенотипа». Введение в эволюционные вычисления. Серия естественных вычислений. Берлин, Гейдельберг: Springer. стр. 177–178. дои : 10.1007/978-3-662-44874-8. ISBN 978-3-662-44873-1. S2CID  20912932.
  29. ^ Харт, Эмма; Росс, Питер; Нельсон, Джереми (1998). «Решение реальной проблемы с использованием развивающегося эвристически управляемого построителя расписания». Эволюционные вычисления . 6 (1): 61–80. дои : 10.1162/evco.1998.6.1.61. ISSN  1063-6560. PMID  10021741. S2CID  6898505.
  30. ^ Эйбен, А.Э.; Смит, Дж. Э. (2015). «Представление перестановок». Введение в эволюционные вычисления. Серия естественных вычислений. Берлин, Гейдельберг: Springer. стр. 67–74. дои : 10.1007/978-3-662-44874-8. ISBN 978-3-662-44873-1. S2CID  20912932.
  31. ^ Ларраньяга, П.; Куиджперс, CMH; Мурга, Р.Х.; Инза, И.; Диздаревич, С. (1999). «Генетические алгоритмы решения задачи коммивояжера: обзор представлений и операторов». Обзор искусственного интеллекта . 13 (2): 129–170. дои : 10.1023/А: 1006529012972. S2CID  10284682.
  32. ^ Брунс, Ральф (1 января 1997 г.). «Эволюционные вычислительные подходы к планированию». В Бек, Томас; Фогель, Д.Б.; Михалевич, З. (ред.). Справочник по эволюционным вычислениям. ЦРК Пресс. дои : 10.1201/9780367802486. ISBN 978-0-367-80248-6.
  33. ^ Аб Якоб, Уилфрид; Страк, Сильвия; Квинт, Александр; Бенгель, Гюнтер; Стаки, Карл-Уве; Зюсс, Вольфганг (22 апреля 2013 г.). «Быстрое перепланирование нескольких рабочих процессов для ограниченных гетерогенных ресурсов с использованием многокритериальных меметических вычислений». Алгоритмы . 6 (2): 245–277. дои : 10.3390/a6020245 . ISSN  1999-4893.
  34. ^ Брукер, Питер (2007). Алгоритмы планирования. Берлин, Гейдельберг: Springer. дои : 10.1007/978-3-540-69516-5. ISBN 978-3-540-69515-8.
  35. ^ Сакеллариу, Ризос; Чжао, Хэнань; Циаккури, Элени; Дикаякос, Мариос Д. (2007), Горлач, Сергей; Данелутто, Марко (ред.), «Планирование рабочих процессов с бюджетными ограничениями», Комплексные исследования в области GRID-вычислений , Бостон, Массачусетс: Springer US, стр. 189–202, doi : 10.1007/978-0-387-47658-2_14, ISBN 978-0-387-47656-8, получено 20 января 2023 г.
  36. ^ Фудзита, Кикуо; Акаги, Синсуке; Хирокава, Нориясу (19 сентября 1993 г.). «Гибридный подход к оптимальному вложению с использованием генетического алгоритма и алгоритма локальной минимизации». Материалы технических конференций по проектированию ASME 1993 г. 19-я конференция по автоматизации проектирования: Том 1 — Динамика механических систем; Параллельное и надежное проектирование; Проектирование для сборки и производства; Генетические алгоритмы в проектировании и структурной оптимизации . Альбукерке, Нью-Мексико, США: Американское общество инженеров-механиков. стр. 477–484. дои : 10.1115/DETC1993-0337. ISBN 978-0-7918-1181-8.
  37. ^ Якоб, Уилфрид (2021), «Планирование компоновки как пример разумного управления сложными ограничениями», Успешное применение эволюционных алгоритмов - руководство, полученное на основе реальных приложений. , KIT Scientific Work Papers, том 170, Карлсруэ: KIT Scientific Publishing, стр. 12–14, arXiv : 2107.11300 , doi : 10.5445/IR/1000135763, S2CID  236318422