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

Набор параметров для генетического или эволюционного алгоритма

В генетических алгоритмах (ГА) или, в более общем смысле, эволюционных алгоритмах (ЭА), хромосома (также иногда называемая генотипом ) представляет собой набор параметров, которые определяют предлагаемое решение проблемы, которую пытается решить эволюционный алгоритм. Совокупность всех решений, также называемых особями в соответствии с биологической моделью, известна как популяция . ^{[1] [2]} Геном особи состоит из одной, реже из нескольких, ^{[3] [4]} хромосом и соответствует генетическому представлению решаемой задачи. Хромосома состоит из набора генов, причем ген состоит из одного или нескольких семантически связанных параметров , которые часто также называют переменными решения . Они определяют одну или несколько фенотипических характеристик личности или, по крайней мере, оказывают на них влияние. ^[2] В базовой форме генетических алгоритмов хромосома представлена ​​в виде двоичной строки , ^[5] в то время как в более поздних вариантах ^{[6] [7]} и в EA в целом используется широкий спектр других структур данных . ^{[8] [9] [10]}

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

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

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

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

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

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

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

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

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

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

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

Хромосомы с вещественными или целочисленными генами

Для обработки задач с вещественными или смешанно-целочисленными переменными решения подходят такие советники, как стратегия эволюции ^[15] или вещественно-кодированные ГА ^{[16] [17] [18] .} В случае смешанно-целых значений часто используется округление, но это представляет собой некоторое нарушение требования избыточности . Если необходимую точность реальных значений можно разумно сузить, это нарушение можно исправить с помощью ГА с целочисленным кодированием. ^{[19] [20]} Для этой цели действительные цифры действительных значений преобразуются в целые числа путем умножения на подходящий коэффициент. Например, 12,380 становится целым числом 12380 при умножении на 1000. Это, конечно, необходимо учитывать при картировании генотипа-фенотипа для оценки и представления результатов. Распространенной формой является хромосома, состоящая из списка или массива целых или вещественных значений.

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

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

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

Хромосомы для коэволюции

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

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

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

Представленные выше хромосомы хорошо подходят для обработки задач непрерывной, смешанно-целочисленной, чистоцелочисленной или комбинаторной оптимизации. С другой стороны, при сочетании этих областей оптимизации становится все труднее сопоставить их с простыми строками значений, в зависимости от задачи. С этой целью EA GLEAM (General Learning Evolutionary Algorithm and Method) предлагает следующее расширение концепции гена: ^[25] Геном считается описание элемента или элементарного признака фенотипа, который может иметь множественные параметры. Для этого определяются типы генов, содержащие столько параметров соответствующего типа данных, сколько требуется для описания конкретного элемента фенотипа. Хромосома теперь состоит из генов как объектов данных типов генов, при этом, в зависимости от применения, каждый тип гена встречается как ген ровно один раз или может содержаться в хромосоме любое количество раз. Последнее приводит к появлению хромосом динамической длины, поскольку они необходимы для решения некоторых задач. ^{[26] [27]} Определения типов генов также содержат информацию о допустимых диапазонах значений параметров гена, которые наблюдаются при генерации хромосом и при соответствующих мутациях, поэтому они не могут привести к летальным мутациям. Для задач с комбинаторной частью существуют подходящие генетические операторы , способные перемещать или переставлять гены целиком, т.е. с их параметрами.

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

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

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

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

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

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

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

• Томас Бек (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 

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

1. «Введение в генетические алгоритмы: IV. Генетический алгоритм» . Проверено 12 августа 2015 г.
2. Эйбен, AE; Смит, Дж. Э. (2015). «Компоненты эволюционных алгоритмов». Введение в эволюционные вычисления. Серия естественных вычислений. Берлин, Гейдельберг: Springer. стр. 28–34. дои : 10.1007/978-3-662-44874-8. ISBN 978-3-662-44873-1. S2CID  20912932.
3. Бейн, Николас (2008), «Простая оптимизация многохромосомного генетического алгоритма контроллера нечеткой логики пропорционально-плюс-производной», Ежегодное собрание Североамериканского общества обработки нечеткой информации NAFIPS 2008–2008 , IEEE, стр. 1– 5, номер домена : 10.1109/НАФИПС.2008.4531273, ISBN 978-1-4244-2351-4, S2CID  46591432
4. Пэн, Джин; Чу, Чжан Шу (2010), «Гибридный многохромосомный генетический алгоритм для проблемы сокращения запасов», 3-я Международная конференция по управлению информацией, менеджменту инноваций и промышленной инженерии , IEEE, стр. 508–511, doi : 10.1109/ICIII. 2010.128, ISBN 978-1-4244-8829-2, S2CID  15608610
5. Холланд, Джон Х. (1992). Адаптация в естественных и искусственных системах . Кембридж, Массачусетс: MIT Press. ISBN 0-585-03844-9. ОСЛК  42854623.
6. Яников, Чехия; Михалевич З. (1991), Белью, Ричард К.; Букер, Лэшон Б. (ред.), «Экспериментальное сравнение двоичных представлений и представлений с плавающей запятой в генетических алгоритмах» (PDF) , Материалы четвертой международной конференции по генетическим алгоритмам , Сан-Франциско, Калифорния: Morgan Kaufmann Publishers, стр. 31 –36, ISBN 1-55860-208-9
7. Уитли, Даррелл (июнь 1994 г.). «Урок по генетическому алгоритму». Статистика и вычисления . 4 (2). CiteSeerX 10.1.1.184.3999 . дои : 10.1007/BF00175354. S2CID  3447126. 
8. Уитли, Даррелл (2001). «Обзор эволюционных алгоритмов: практические проблемы и распространенные ошибки». Информационные и программные технологии . 43 (14): 817–831. дои : 10.1016/S0950-5849(01)00188-4. S2CID  18637958.
9. Бэк, Томас; Хоффмайстер, Франк; Швефель, Ханс-Пол (1991), Белью, Ричард К.; Букер, Лэшон Б. (ред.), «Обзор стратегий эволюции», Труды Четвертой Международной конференции по генетическим алгоритмам , Сан-Франциско, Калифорния: Morgan Kaufmann Publishers, стр. 2–9, ISBN 1-55860-208-9
10. Коза, Джон Р. (1992). Генетическое программирование: о программировании компьютеров посредством естественного отбора. Кембридж, Массачусетс: MIT Press. ISBN 0-262-11170-5. ОСЛК  26263956.
11. «Генетические алгоритмы». Архивировано из оригинала 22 октября 2019 года . Проверено 12 августа 2015 г.
12. Ротлауф, Франц (2002). Представления для генетических и эволюционных алгоритмов. Исследования нечеткости и мягких вычислений. Том. 104. Гейдельберг: Physica-Verlag HD. п. 31. дои : 10.1007/978-3-642-88094-0. ISBN 978-3-642-88096-4.
13. Эйбен, А.Э.; Смит, Дж. Э. (2015). «Представление и роли операторов вариации». Введение в эволюционные вычисления. Серия естественных вычислений. Берлин, Гейдельберг: Springer. стр. 49–51. дои : 10.1007/978-3-662-44874-8. ISBN 978-3-662-44873-1. S2CID  20912932.
14. Гальван-Лопес, Эдгар; Макдермотт, Джеймс; О'Нил, Майкл; Брабазон, Энтони (07 июля 2010 г.). «На пути к пониманию локальности в генетическом программировании». Материалы 12-й ежегодной конференции по генетическим и эволюционным вычислениям (PDF) . Портленд, Орегон, США: ACM. стр. 901–908. дои : 10.1145/1830483.1830646. ISBN 978-1-4503-0072-8. S2CID  15348983.
15. Швефель, Ханс-Пол (1995). Эволюция и поиск оптимума. Нью-Йорк: Джон Уайли и сыновья. ISBN 0-471-57148-2. ОСЛК  30701094.
16. Эшельман, Ларри Дж.; Шаффер, Дж. Дэвид (1993), «Генетические алгоритмы с реальным кодированием и интервальные схемы», Основы генетических алгоритмов , том. 2, Elsevier, стр. 187–202, doi : 10.1016/b978-0-08-094832-4.50018-0, ISBN. 978-0-08-094832-4, получено 26 января 2023 г.
17. Михалевич, Збигнев (1996). Генетические алгоритмы + Структуры данных = Программы эволюции . Третье, переработанное и дополненное издание. Берлин, Гейдельберг: Springer. ISBN 978-3-662-03315-9. ОСЛК  851375253.
18. Глубокий, Кусум; Сингх, Кришна Пратап; Кансал, ML; Мохан, К. (июнь 2009 г.). «Настоящий генетический алгоритм для решения целочисленных и смешанно-целочисленных задач оптимизации». Прикладная математика и вычислительная техника . 212 (2): 505–518. дои : 10.1016/j.amc.2009.02.044.
19. Ван, Фучан; Цао, Хуйжун; Цянь, Сяоши (2011), Лю, Баосян; Чай, Чунлай (ред.), «Генетический алгоритм с десятично-целочисленным кодированием для усеченной оценки множественных линейных ошибок в модели переменных», Information Computing and Applications , LNCS 7030, Берлин, Гейдельберг: Springer, стр. 359–366, doi :10.1007/978-3-642-25255-6_46, ISBN 978-3-642-25254-9, получено 23 января 2023 г.
20. Ченг, Сюэли; Ан, Линчао; Чжан, Чжэньхуа (2019). «Генетический алгоритм целочисленного кодирования для оптимизации распределения избыточности в последовательно-параллельных системах». Журнал инженерных наук и технологий. Обзор . 12 (1): 126–136. дои : 10.25103/JESTR.121.15 . S2CID  149497992.
21. Эйбен, А.Э.; Смит, Дж. Э. (2015). «Представление перестановок». Введение в эволюционные вычисления. Серия естественных вычислений. Берлин, Гейдельберг: Springer. стр. 67–74. дои : 10.1007/978-3-662-44874-8. ISBN 978-3-662-44873-1. S2CID  20912932.
22. Ларраньяга, П.; Куиджперс, CMH; Мурга, Р.Х.; Инза, И.; Диздаревич, С. (1999). «Генетические алгоритмы решения задачи коммивояжера: обзор представлений и операторов». Обзор искусственного интеллекта . 13 (2): 129–170. дои : 10.1023/А: 1006529012972. S2CID  10284682.
23. Уитли, Даррелл (2000). «Перестановки». В Фогеле, Дэвид Б.; Бэк, Томас; Михалевич, Збигнев (ред.). Эволюционные вычисления. Том. 1. Основные алгоритмы и операторы . Бристоль: Паб Института физики. стр. 139–150. ISBN 0-585-30560-9. ОСЛК  45730387.
24. Якоб, Уилфрид; Страк, Сильвия; Квинт, Александр; Бенгель, Гюнтер; Стаки, Карл-Уве; Зюсс, Вольфганг (22 апреля 2013 г.). «Быстрое перепланирование нескольких рабочих процессов для ограниченных гетерогенных ресурсов с использованием многокритериальных меметических вычислений». стр.253-255. Алгоритмы . 6 (2): 245–277. дои : 10.3390/a6020245 . ISSN  1999-4893.
25. Блюм, Кристиан; Якоб, Вильфрид (2002), «GLEAM - эволюционный алгоритм планирования и контроля, основанный на стратегии эволюции», Conf. Учеб. конференции по генетическим и эволюционным вычислениям (GECCO 2002) , том. Late Breaking Papers, стр. 31–38 , получено 1 января 2023 г.
26. Павар, Сунил Нилкант; Бичкар, Раджанкумар Садашиврао (июнь 2015 г.). «Генетический алгоритм с хромосомами переменной длины для обнаружения сетевых вторжений». Международный журнал автоматизации и вычислений . 12 (3): 337–342. дои : 10.1007/s11633-014-0870-x . ISSN  1476-8186. S2CID  255346767.
27. Блюм, Кристиан (2000), Каньони, Стефано (редактор), «Оптимизированное создание операторов движения робота без столкновений с помощью эволюционного программного обеспечения GLEAM», Реальные приложения эволюционных вычислений , Конспекты лекций по информатике, том. 1803, Берлин, Гейдельберг: Springer Berlin Heidelberg, стр. 330–341, doi : 10.1007/3-540-45561-2_32, ISBN 978-3-540-67353-8, получено 25 июня 2023 г.
28. Эйбен, А.Э.; Смит, Дж. Э. (2015). «Представление дерева». Введение в эволюционные вычисления. Серия естественных вычислений. Берлин, Гейдельберг: Springer. стр. 75–78. дои : 10.1007/978-3-662-44874-8. ISBN 978-3-662-44873-1. S2CID  20912932.