stringtranslate.com

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

В компьютерном программировании генетическое представление — это способ представления решений/индивидуумов в эволюционных методах вычислений . Этот термин охватывает как конкретные структуры данных , так и типы данных, используемые для реализации генетического материала кандидатов на решения в форме генома, а также отношения между пространством поиска и пространством задач. В простейшем случае пространство поиска соответствует пространству задач (прямое представление). [1] Выбор представления задачи связан с выбором генетических операторов , оба из которых оказывают решающее влияние на эффективность оптимизации. [2] [3] Генетическое представление может кодировать внешность, поведение, физические качества индивидуумов. Различие в генетических представлениях является одним из основных критериев, проводящих границу между известными классами эволюционных вычислений. [4] [5]

Терминология часто аналогична естественной генетике . Блок компьютерной памяти, представляющий одно возможное решение, называется индивидуумом. Данные в этом блоке называются хромосомой . Каждая хромосома состоит из генов. Возможные значения конкретного гена называются аллелями . Программист может представлять всех индивидуумов популяции, используя двоичное кодирование , перестановочное кодирование , кодирование деревом или любое из нескольких других представлений. [6] [7]

Представления в некоторых популярных эволюционных алгоритмах

Генетические алгоритмы (ГА) обычно являются линейными представлениями; [8] они часто, но не всегда, [9] [10] [11] двоичными. [10] Первоначальное описание ГА Холланда использовало массивы битов . Массивы других типов и структур могут использоваться по сути таким же образом. Основное свойство, которое делает эти генетические представления удобными, заключается в том, что их части легко выравниваются из-за их фиксированного размера. Это облегчает простую операцию кроссинговера. В зависимости от приложения, представления переменной длины также успешно использовались и тестировались в эволюционных алгоритмах (ЭА) [12] [13] в целом и генетических алгоритмах [14] [15] в частности, хотя реализация кроссинговера в этом случае более сложна.

Стратегия эволюции использует линейные вещественные представления, например, массив вещественных значений. Она использует в основном гауссовскую мутацию и смешивание/усреднение кроссовера. [16]

Генетическое программирование (ГП) стало пионером в области древовидных представлений и разработало генетические операторы, подходящие для таких представлений. Древовидные представления используются в ГП для представления и развития функциональных программ с желаемыми свойствами. [17]

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

Общие генетические представления

Различие между пространством поиска и пространством проблем

Аналогично биологии, ЭА различают проблемное пространство (соответствует фенотипу ) и поисковое пространство (соответствует генотипу ). Проблемное пространство содержит конкретные решения решаемой проблемы, в то время как поисковое пространство содержит закодированные решения. Отображение из поискового пространства в проблемное пространство называется отображением генотип-фенотип . Генетические операторы применяются к элементам поискового пространства, и для оценки элементы поискового пространства отображаются на элементы проблемного пространства с помощью отображения генотип-фенотип. [18] [19]

Взаимоотношения между пространством поиска и пространством проблем

Важность правильного выбора поискового пространства для успеха приложения EA была осознана на раннем этапе. [20] [21] [22] Следующие требования могут быть предъявлены к подходящему поисковому пространству и, следовательно, к подходящему сопоставлению генотипа и фенотипа: [23] [24]

Полнота

Все возможные допустимые решения должны содержаться в пространстве поиска.

Избыточность

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

В биологии Нейтральная теория молекулярной эволюции утверждает, что этот эффект играет доминирующую роль в естественной эволюции. Это побудило исследователей в сообществе ЭА изучить, могут ли нейтральные мутации улучшить функционирование ЭА [25] , предоставив популяциям, которые сошлись к локальному оптимуму, способ избежать этого локального оптимума посредством генетического дрейфа . Это обсуждается спорно, и нет никаких окончательных результатов по нейтральности в ЭА. [26] [27] С другой стороны, существуют другие проверенные меры для управления преждевременной конвергенцией .

Местность

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

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

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

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

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

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

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

Примеры

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

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

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

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

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

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

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

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

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

Ссылки

  1. ^ Эйбен, AE; Смит, JE (2015). Введение в эволюционные вычисления. Серия «Естественные вычисления». Берлин, Гейдельберг: Springer. стр. 40. doi :10.1007/978-3-662-44874-8. ISBN 978-3-662-44873-1. S2CID  20912932.
  2. ^ Ротлауф, Франц (2002). Представления для генетических и эволюционных алгоритмов. Исследования по нечеткости и мягким вычислениям. Т. 104. Гейдельберг: Physica-Verlag HD. стр. 31. doi :10.1007/978-3-642-88094-0. ISBN 978-3-642-88096-4.
  3. ^ Эйбен, AE; Смит, JE (2015). «Представление и роль операторов вариации». Введение в эволюционные вычисления. Серия «Естественные вычисления». Берлин, Гейдельберг: Springer. С. 49–51. doi :10.1007/978-3-662-44874-8. ISBN 978-3-662-44873-1. S2CID  20912932.
  4. ^ Эйбен, AE; Смит, JE (2015). «Популярные варианты эволюционных алгоритмов». Введение в эволюционные вычисления. Серия Natural Computing. Берлин, Гейдельберг: Springer. стр. 99–118. doi :10.1007/978-3-662-44874-8. ISBN 978-3-662-44873-1. S2CID  20912932.
  5. ^ Fogel, DB (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. ^ Эйбен, AE; Смит, JE (2015). «Представление, мутация и рекомбинация». Введение в эволюционные вычисления. Серия «Естественные вычисления». Берлин, Гейдельберг: Springer. С. 49–78. doi :10.1007/978-3-662-44874-8. ISBN 978-3-662-44873-1. S2CID  20912932.
  8. ^ Голдберг, Дэвид Э. (1989). Генетические алгоритмы в поиске, оптимизации и машинном обучении . Рединг, Массачусетс: Эддисон-Уэсли. ISBN 0-201-15767-5. OCLC  17674450.
  9. ^ Михалевич, Збигнев (1996). Генетические алгоритмы + структуры данных = программы эволюции . 3-е, исправленное и расширенное издание. Берлин, Гейдельберг: Springer. ISBN 978-3-662-03315-9. OCLC  851375253.
  10. ^ ab Whitley, Darrell (1994). "Учебник по генетическому алгоритму". Статистика и вычисления . 4 (2). doi :10.1007/BF00175354. ISSN  0960-3174. S2CID  3447126.
  11. ^ Herrera, F.; Lozano, M.; Verdegay, JL (1998). «Tackling Real-Coded Genetic Algorithms: Operators and Tools for Behavioural Analysis». Artificial Intelligence Review . 12 (4): 265–319. doi :10.1023/A:1006504901164. S2CID  6798965.
  12. ^ Блюм, Кристиан; Якоб, Вильфрид (2002), «GLEAM — эволюционный алгоритм планирования и управления на основе эволюционной стратегии», Conf. Proc. of Genetic and Evolutionary Computation Conference (GECCO 2002) , т. Late Breaking Papers, стр. 31–38 , получено 01.01.2023
  13. ^ Хитоми, Нозоми; Сельва, Дэниел (2018), «Оптимизация созвездия с использованием эволюционного алгоритма с хромосомой переменной длины», 2018 IEEE Aerospace Conference , IEEE, стр. 1–12, doi :10.1109/AERO.2018.8396743, ISBN 978-1-5386-2014-4, S2CID  49541423
  14. ^ Де Йонг, Кеннет А. (2006). «Представление». Эволюционные вычисления: единый подход. Нью-Дели: Prentice-Hall of India. С. 72–75. ISBN 978-81-203-3002-3. OCLC  276452339.
  15. ^ Павар, Сунил Нилкант; Бичкар, Раджанкумар Садашиврао (2015). «Генетический алгоритм с хромосомами переменной длины для обнаружения сетевых вторжений». Международный журнал автоматизации и вычислений . 12 (3): 337–342. doi : 10.1007/s11633-014-0870-x . ISSN  1476-8186. S2CID  255346767.
  16. ^ Швефель, Ганс-Пауль (1995). Эволюция и поиск оптимума. Нью-Йорк: Wiley & Sons. ISBN 0-471-57148-2. OCLC  30701094.
  17. ^ Коза, Джон Р. (1989), Шридхаран, Н.С. (ред.), «Иерархические генетические алгоритмы, работающие с популяциями компьютерных программ», Труды Одиннадцатой международной совместной конференции по искусственному интеллекту IJCAI-89 , т. 1, Сан-Матео, Калифорния, США: Morgan Kaufmann, стр. 768–774
  18. ^ Ротлауф, Франц (2002). Представления для генетических и эволюционных алгоритмов. Исследования по нечеткости и мягким вычислениям. Т. 104. Гейдельберг: Physica-Verlag HD. doi :10.1007/978-3-642-88094-0. ISBN 978-3-642-88096-4.
  19. ^ Whigham, Peter A.; Dick, Grant; Maclaurin, James (2017). «О сопоставлении генотипа с фенотипом в эволюционных алгоритмах». Genetic Programming and Evolvable Machines . 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, получено 2023-01-19
  21. ^ Лиепинс, Гунар Э.; Восе, Майкл Д. (1990). «Проблемы представления в генетической оптимизации». Журнал экспериментального и теоретического искусственного интеллекта . 2 (2): 101–115. doi :10.1080/09528139008953717. ISSN  0952-813X.
  22. ^ Coli, M.; Palazzari, P. (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. OCLC  913232837.
  24. ^ Ротлауф, Франц (2006). «Три элемента теории представлений». Представления для генетических и эволюционных алгоритмов (2-е изд.). Гейдельберг: Springer. С. 33–96. ISBN 978-3-540-32444-7. OCLC  262692044.
  25. ^ Гальван-Лопес, Эдгар; Дигнум, Стивен; Поли, Риккардо (2008), О'Нил, Майкл; Ваннески, Леонардо; Густафсон, Стивен; Эспарсия Алькасар, Анна Изабель (ред.), «Влияние постоянной нейтральности на производительность и сложность задач в GP», Генетическое программирование , Конспект лекций по информатике, т. 4971, Берлин, Гейдельберг: Springer, стр. 312–324, doi :10.1007/978-3-540-78671-9_27, ISBN 978-3-540-78670-2, S2CID  6803107 , получено 21.01.2023
  26. ^ Гальван-Лопес, Эдгар; Поли, Риккардо; Каттан, Ахмед; О'Нил, Майкл; Брабазон, Энтони (2011). «Нейтральность в эволюционных алгоритмах… Что мы знаем?». Evolving Systems . 2 (3): 145–163. doi :10.1007/s12530-011-9030-5. hdl : 10197/3532 . ISSN  1868-6478. S2CID  15951086.
  27. ^ Ноулз, Джошуа Д.; Уотсон, Ричард А. (2002), Гервос, Хуан Хулиан Мерело; Адамидис, Панайотис; Бейер, Ханс-Георг; Швефель, Ханс-Пауль (ред.), «О пользе избыточных кодировок в эволюционном поиске на основе мутаций», Параллельное решение проблем из природы — PPSN VII , т. 2439, Берлин, Гейдельберг: Springer, стр. 88–98, doi :10.1007/3-540-45712-7_9, ISBN 978-3-540-44139-7, получено 21.01.2023
  28. ^ Эйбен, AE; Смит, JE (2015). «Гибридизация во время сопоставления генотипа с фенотипом». Введение в эволюционные вычисления. Серия «Естественные вычисления». Берлин, Гейдельберг: Springer. С. 177–178. doi :10.1007/978-3-662-44874-8. ISBN 978-3-662-44873-1. S2CID  20912932.
  29. ^ Харт, Эмма; Росс, Питер; Нельсон, Джереми (1998). «Решение проблемы реального мира с использованием эволюционирующего эвристически управляемого построителя расписаний». Эволюционные вычисления . 6 (1): 61–80. doi :10.1162/evco.1998.6.1.61. ISSN  1063-6560. PMID  10021741. S2CID  6898505.
  30. ^ Эйбен, AE; Смит, JE (2015). «Представление перестановки». Введение в эволюционные вычисления. Серия «Естественные вычисления». Берлин, Гейдельберг: Springer. С. 67–74. doi :10.1007/978-3-662-44874-8. ISBN 978-3-662-44873-1. S2CID  20912932.
  31. ^ Larrañaga, P.; Kuijpers, CMH; Murga, RH; Inza, I.; Dizdarevic, S. (1999). «Генетические алгоритмы для задачи коммивояжера: обзор представлений и операторов». Artificial Intelligence Review . 13 (2): 129–170. doi :10.1023/A:1006529012972. S2CID  10284682.
  32. ^ Брунс, Ральф (1997-01-01). "Подходы эволюционных вычислений для планирования". В Baeck, Thomas; Fogel, DB; Michalewicz, Z (ред.). Справочник по эволюционным вычислениям. CRC Press. doi :10.1201/9780367802486. ISBN 978-0-367-80248-6.
  33. ^ ab Якоб, Вильфрид; Штрак, Сильвия; Квинте, Александр; Бенгель, Гюнтер; Штуки, Карл-Уве; Зюсс, Вольфганг (2013-04-22). "Быстрое перепланирование нескольких рабочих процессов для ограниченных гетерогенных ресурсов с использованием многокритериальных меметических вычислений". Алгоритмы . 6 (2): 245–277. doi : 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, получено 2023-01-20
  36. ^ Фудзита, Кикуо; Акаги, Синсукэ; Хирокава, Нориясу (1993-09-19). «Гибридный подход к оптимальному вложению с использованием генетического алгоритма и алгоритма локальной минимизации». Труды технических конференций по проектированию ASME 1993 года. 19-я конференция по автоматизации проектирования: том 1 — Динамика механических систем; Параллельное и надежное проектирование; Проектирование для сборки и производства; Генетические алгоритмы в проектировании и структурной оптимизации . Альбукерке, Нью-Мексико, США: Американское общество инженеров-механиков. стр. 477–484. doi :10.1115/DETC1993-0337. ISBN 978-0-7918-1181-8.
  37. ^ Якоб, Вильфрид (2021), «Планирование компоновки как пример интеллектуальной обработки сложных ограничений», Успешное применение эволюционных алгоритмов — руководство, полученное из реальных приложений. , KIT Scientific Working Papers, т. 170, Карлсруэ: KIT Scientific Publishing, стр. 12–14, arXiv : 2107.11300 , doi : 10.5445/IR/1000135763, S2CID  236318422