Функция фитнеса

Целевая функция эволюционного алгоритма

Функция пригодности — это особый тип целевой функции , которая используется для обобщения, как единого показателя качества , того, насколько близко данное проектное решение к достижению поставленных целей. Функции пригодности используются в архитектуре программного обеспечения и эволюционных алгоритмах (EA) , таких как генетическое программирование и генетические алгоритмы, для руководства моделированием в направлении оптимальных проектных решений. ^[1]

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

В области ЭА каждое проектное решение обычно представляется в виде строки чисел (называемой хромосомой ). После каждого раунда тестирования или моделирования идея состоит в том, чтобы удалить n худших проектных решений и вывести n новых из лучших проектных решений. Поэтому каждому проектному решению необходимо присвоить показатель качества, чтобы указать, насколько близко оно подошло к соответствию общей спецификации, и это генерируется путем применения функции пригодности к результатам теста или моделирования, полученным из этого решения. ^[3]

Существуют два основных класса функций приспособленности: один, где функция приспособленности не меняется, как при оптимизации фиксированной функции или тестировании с фиксированным набором тестовых случаев; и один, где функция приспособленности изменчива, как при дифференциации ниши или совместной эволюции набора тестовых случаев. ^{[4] [5]} Другой способ рассмотрения функций приспособленности — с точки зрения ландшафта приспособленности , который показывает приспособленность для каждой возможной хромосомы. В дальнейшем предполагается, что приспособленность определяется на основе оценки, которая остается неизменной во время прогона оптимизации.

Функция приспособленности не обязательно должна иметь возможность вычислять абсолютное значение, так как иногда достаточно сравнить кандидатов, чтобы выбрать лучшего. Относительное указание приспособленности (кандидат a лучше, чем b) достаточно в некоторых случаях, ^[6] таких как турнирный отбор или оптимизация Парето .

Требования к оценке и функции пригодности

Качество оценки и расчета функции приспособленности имеет основополагающее значение для успеха оптимизации EA. Она реализует принцип Дарвина «выживает наиболее приспособленный». Без механизмов отбора на основе приспособленности для выбора партнера и принятия потомства поиск EA был бы слепым и едва ли отличимым от метода Монте-Карло . При настройке функции приспособленности всегда нужно осознавать, что речь идет не только о описании желаемого целевого состояния. Напротив, эволюционный поиск на пути к оптимуму также должен поддерживаться в максимально возможной степени (см. также раздел о вспомогательных целях), если и в той мере, в какой это еще не сделано одной функцией приспособленности. Если функция приспособленности спроектирована плохо, алгоритм либо сойдется к неподходящему решению, либо вообще столкнется с трудностями при сходимости.

Определение функции пригодности во многих случаях не является простым и часто выполняется итеративно, если наиболее подходящие решения, созданные EA, не являются желаемыми. Интерактивные генетические алгоритмы решают эту проблему, передавая оценку внешним агентам, которыми обычно являются люди.

Эффективность вычислений

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

Аппроксимация пригодности ^{[7] [8]} может быть уместной, особенно в следующих случаях:

• Время расчета пригодности одного решения чрезвычайно велико
• Точная модель для расчета пригодности отсутствует
• Функция приспособленности неопределенна или шумная. ^[9]

В качестве альтернативы или также в дополнение к приближению пригодности, вычисления пригодности также могут быть распределены на параллельный компьютер, чтобы сократить время выполнения. В зависимости от модели популяции используемого EA, как сам EA, так и вычисления пригодности всех потомков одного поколения могут выполняться параллельно. ^{[10] [11] [12]}

Многоцелевая оптимизация

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

Взвешенная сумма и штрафные функции

При оптимизации с помощью взвешенной суммы сначала нормализуются отдельные значения целей, чтобы их можно было сравнить. Это можно сделать с помощью затрат или путем указания целевых значений и определения текущего значения как степени выполнения. Затем затраты или степени выполнения можно сравнить друг с другом и, при необходимости, также можно сопоставить с единой шкалой приспособленности. Без потери общности предполагается, что приспособленность представляет собой значение, которое необходимо максимизировать. Каждой цели присваивается вес в виде процентного значения, чтобы общая сырая приспособленность могла быть рассчитана как взвешенная сумма: ${\displaystyle O}$ ${\displaystyle o_{i}}$ ${\displaystyle w_{i}}$ ${\displaystyle f_{raw}}$

${\displaystyle f_{raw}=\sum _{i=1}^{O}{o_{i}\cdot w_{i}}\quad {\mathsf {with}}\quad \sum _{i=1}^{O}{w_{i}}=1}$

Нарушение ограничений может быть включено в приспособленность, определенную таким образом, в форме штрафных функций . Для этой цели можно определить функцию для каждого ограничения, которая возвращает значение между и в зависимости от степени нарушения, с результатом, если нарушения нет. Ранее определенная сырая приспособленность умножается на штрафную функцию(и), и результатом затем является окончательная приспособленность : ^[14] ${\displaystyle R}$ ${\displaystyle r_{j}}$ ${\displaystyle pf_{j}(r_{j})}$ ${\displaystyle 0}$ ${\displaystyle 1}$ ${\displaystyle 1}$ ${\displaystyle f_{final}}$

${\displaystyle f_{final}=f_{raw}\cdot \prod _{j=1}^{R}{pf_{j}(r_{j})}=\sum _{i=1}^{O}{(o_{i}\cdot w_{i})}\cdot \prod _{j=1}^{R}{pf_{j}(r_{j})}}$

Этот подход прост и имеет преимущество в возможности объединения любого количества целей и ограничений. Недостатком является то, что разные цели могут компенсировать друг друга, и что веса должны быть определены до оптимизации. ^[13] Кроме того, некоторые решения могут не быть получены, см. раздел о сравнении обоих типов оптимизации .

оптимизация Парето

Решение называется оптимальным по Парето, если улучшение одной цели возможно только при ухудшении хотя бы одной другой цели. Набор всех оптимальных по Парето решений, также называемый набором Парето, представляет собой набор всех оптимальных компромиссов между целями. На рисунке ниже справа показан пример набора Парето из двух целей и , которые необходимо максимизировать. Элементы набора образуют фронт Парето (зеленая линия). Из этого набора человек, принимающий решения, должен впоследствии выбрать желаемое компромиссное решение. ^[13] Ограничения включены в оптимизацию Парето, поскольку решения без нарушений ограничений по сути лучше, чем те, которые имеют нарушения. Если два сравниваемых решения имеют нарушения ограничений, решающим фактором является соответствующая степень нарушений. ^[15] ${\displaystyle f_{1}}$ ${\displaystyle f_{2}}$

На раннем этапе было признано, что ЭА с их одновременно рассматриваемым набором решений хорошо подходят для поиска решений за один запуск, которые достаточно хорошо покрывают фронт Парето. ^{[15] [16]} Помимо SPEA2, ^[17] в качестве стандартных методов зарекомендовали себя NSGA-II ^[18] и NSGA-III ^{[19] [20] .}

Преимущество оптимизации Парето в том, что, в отличие от взвешенной суммы, она предоставляет все альтернативы, которые эквивалентны с точки зрения целей, как общее решение. Недостаток в том, что визуализация альтернатив становится проблематичной или даже невозможной, начиная с четырех целей. Более того, усилия увеличиваются экспоненциально с числом целей. ^[14] Если целей больше трех или четырех, некоторые из них необходимо объединить с помощью взвешенной суммы или других методов агрегации. ^[13]

Сравнение обоих типов оценки

Связь между фронтом Парето и взвешенной суммой. Множество допустимых решений частично ограничено фронтом Парето (зеленый). ^[14] ${\displaystyle Z}$

Пример невыпуклого фронта Парето ^[14]

С помощью взвешенной суммы общий фронт Парето может быть получен путем подходящего выбора весов, при условии, что он выпуклый . ^[21] Это иллюстрируется соседним рисунком слева. Точка на зеленом фронте Парето достигается весами и , при условии, что ЭА сходится к оптимуму. Направление с наибольшим приростом приспособленности в наборе решений показано нарисованными стрелками. ${\displaystyle {\mathsf {P}}}$ ${\displaystyle w_{1}}$ ${\displaystyle w_{2}}$ ${\displaystyle Z}$

Однако в случае невыпуклого фронта невыпуклые фронтальные секции не достижимы с помощью взвешенной суммы. На соседнем изображении справа это секция между точками и . Это можно исправить в ограниченной степени, используя расширение взвешенной суммы, каскадную взвешенную сумму . ^[14] ${\displaystyle {\mathsf {A}}}$ ${\displaystyle {\mathsf {B}}}$

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

Вспомогательные цели

Пример двух графиков заказа, состоящего из пяти рабочих этапов от a до e , которые должны соответствовать наиболее позднему сроку завершения ^[22]

В дополнение к основным целям, вытекающим из самой задачи, может потребоваться включить в оценку вспомогательные цели для поддержки достижения одной или нескольких основных целей. Пример задачи планирования используется для иллюстрации. Цели оптимизации включают не только общую быструю обработку всех заказов, но и соблюдение самого позднего времени завершения. Последнее особенно необходимо для планирования срочных заказов. Вторая цель не достигается примерным начальным графиком, как показано на соседнем рисунке. Последующая мутация не меняет этого, но планирует рабочий шаг d раньше, что является необходимым промежуточным шагом для более раннего начала последнего рабочего шага e заказа. Однако, пока оценивается только самое позднее время завершения, пригодность измененного графика остается неизменной, хотя он представляет собой важный шаг к цели своевременного завершения заказа. Это можно исправить, например, путем дополнительной оценки задержки рабочих шагов. Новая цель является вспомогательной, поскольку она была введена в дополнение к фактическим целям оптимизации для поддержки их достижения. Более подробное описание этого подхода и другой пример можно найти в ^{[22] .}

Смотрите также

• Эволюционные вычисления
• Программирование выводов
• Тестовые функции для оптимизации
• Функция потерь

Внешние ссылки

• Хорошее введение в адаптивную нечеткую грануляцию фитнеса (AFFG) ( PDF ), многообещающий подход к ускорению скорости сходимости ЭА.
• Киберхижина адаптивной нечеткой фитнес-грануляции (AFFG), которая предназначена для ускорения скорости сходимости ЭА.
• Функции приспособленности в эволюционной робототехнике: обзор и анализ (AFFG) ( PDF ), обзор функций приспособленности, используемых в эволюционной робототехнике .
• Форд, Нил; Ричардс, Марк, Садалаге, Прамод; Дехгани, Жамак. (2021) Архитектура программного обеспечения: сложные детали O'Reilly Media, Inc. ISBN  9781492086895 .

Ссылки

1. Eiben, AE; Smith, JE (2015). "Функция оценки (функция приспособленности)". Введение в эволюционные вычисления. Серия Natural Computing (2-е изд.). Берлин, Гейдельберг: Springer. стр. 30. doi :10.1007/978-3-662-44874-8. ISBN 978-3-662-44873-1. S2CID  20912932.
2. Основы архитектуры программного обеспечения: инженерный подход . O'Reilly Media. 2020. ISBN 978-1492043454.
3. Эйбен, AE; Смит, JE (2015). «Что такое эволюционный алгоритм?». Введение в эволюционные вычисления. Серия Natural Computing. Берлин, Гейдельберг: Springer. С. 25–48. doi :10.1007/978-3-662-44874-8. ISBN 978-3-662-44873-1. S2CID  20912932.
4. Поповичи, Елена; Буччи, Энтони; Виганд, Р. Пол; Де Йонг, Эдвин Д. (2012), Розенберг, Гжегож; Бэк, Томас; Кок, Йост Н. (ред.), «Коэволюционные принципы», Справочник по естественным вычислениям , Берлин, Гейдельберг: Springer Berlin Heidelberg, стр. 987–1033, doi :10.1007/978-3-540-92910-9_31, ISBN 978-3-540-92909-3, получено 2023-01-08
5. Эйбен, AE; Смит, JE (2015). «Коэволюционные системы». Введение в эволюционные вычисления. Серия Natural Computing. Берлин, Гейдельберг: Springer Berlin Heidelberg. стр. 223–230. doi :10.1007/978-3-662-44874-8. ISBN 978-3-662-44873-1. S2CID  20912932.
6. Бэк, Томас; Фогель, Дэвид; Михалевич, Збигнев, ред. (2000-11-20). Эволюционные вычисления 2: Расширенные алгоритмы и операторы. Тейлор и Фрэнсис. doi :10.1201/9781420034349. ISBN 978-0-7503-0665-2.
7. Jin, Y. (январь 2005 г.). «Комплексный обзор приближения пригодности в эволюционных вычислениях». Soft Computing . 9 (1): 3–12. doi :10.1007/s00500-003-0328-5. ISSN  1432-7643. S2CID  7626092.
8. Jin, Yaochu; Wang, Handing; Chugh, Tinkle; Miettinen, Kaisa (июнь 2019 г.). «Управляемая данными эволюционная оптимизация: обзор и примеры». IEEE Transactions on Evolutionary Computation . 23 (3): 442–458. doi : 10.1109/TEVC.2018.2869001. hdl : 10871/34011 . ISSN  1089-778X. S2CID  55809527.
9. Эйбен, AE; Смит, JE (2015). «Нестационарная и шумная оптимизация функций». Введение в эволюционные вычисления. Серия «Естественные вычисления» (2-е изд.). Берлин, Гейдельберг: Springer. С. 185–194. doi :10.1007/978-3-662-44874-8. ISBN 978-3-662-44873-1. S2CID  20912932.
10. Судхольт, Дирк (2015), Кацпшик, Януш; Педриц, Витольд (ред.), «Параллельные эволюционные алгоритмы», Springer Handbook of Computational Intelligence , Берлин, Гейдельберг: Springer, стр. 929–959, doi :10.1007/978-3-662-43505-2_46, ISBN 978-3-662-43504-5, получено 2023-02-27
11. Халлуф, Хатем; Мохаммад, Мохаммад; Шахуд, Шади; Дюпмайер, Клеменс; Хагенмейер, Вайт (2020-11-02). «Универсальная гибкая и масштабируемая структура для иерархической распараллеливания метаэвристик на основе населения». Труды 12-й Международной конференции по управлению цифровыми экосистемами . Виртуальное мероприятие Объединенные Арабские Эмираты: ACM. стр. 124–131. doi :10.1145/3415958.3433041. ISBN 978-1-4503-8115-4. S2CID  227179748.
12. Яне, Пол (2016). Майр, Генрих Кристиан; Пинцгер, Мартин (ред.). Обзор текущего состояния исследований по распараллеливанию эволюционных алгоритмов на графических картах (PDF) . Бонн: Gesellschaft für Informatik, ФРГ. ISBN 978-3-88579-653-4. OCLC  962381748. {{cite book}}: |work=проигнорировано ( помощь )
13. Miettinen, Kaisa (2008). "Введение в многоцелевую оптимизацию: неинтерактивные подходы". В Branke, Jürgen; Deb, Kalyanmoy; Miettinen, Kaisa; Słowiński, Roman (ред.). Многоцелевая оптимизация: интерактивные и эволюционные подходы. Lecture Notes in Computer Science. Vol. 5252. Berlin, Heidelberg: Springer. pp. 1–26. doi :10.1007/978-3-540-88908-3. ISBN 978-3-540-88907-6. S2CID  15375227.
14. Якоб, Вильфрид; Блюм, Кристиан (2014-03-21). «Оптимизация по Парето или каскадная взвешенная сумма: сравнение концепций». Алгоритмы . 7 (1): 166–185. arXiv : 2203.02697 . doi : 10.3390/a7010166 . ISSN  1999-4893.
15. Deb, Kalyanmoy (2008). "Введение в эволюционную многоцелевую оптимизацию". В Branke, Jürgen; Deb, Kalyanmoy; Miettinen, Kaisa; Słowiński, Roman (ред.). Многоцелевая оптимизация: интерактивные и эволюционные подходы. Lecture Notes in Computer Science. Vol. 5252. Berlin, Heidelberg: Springer. pp. 58–96. doi :10.1007/978-3-540-88908-3. ISBN 978-3-540-88907-6. S2CID  15375227.
16. Фонсека, Карлос М.; Флеминг, Питер Дж. (1995). «Обзор эволюционных алгоритмов в многоцелевой оптимизации». Эволюционные вычисления . 3 (1): 1–16. doi :10.1162/evco.1995.3.1.1. ISSN  1063-6560. S2CID  8530790.
17. Эккарт, Цицлер; Марко, Лауманнс; Лотар, Тиле (2001). "SPEA2: Улучшение эволюционного алгоритма прочности Парето". Технический отчет, № 103. Лаборатория компьютерной инженерии и сетей (TIK) . ETH Zürich 2001. doi :10.3929/ethz-a-004284029. S2CID  16584254.
18. Деб, К.; Пратап, А.; Агарвал, С.; Мейариван, Т. (2002). «Быстрый и элитарный многоцелевой генетический алгоритм: NSGA-II». Труды IEEE по эволюционным вычислениям . 6 (2): 182–197. doi :10.1109/4235.996017. S2CID  9914171.
19. Деб, Кальянмой; Джейн, Химансю (2014). «Эволюционный алгоритм многокритериальной оптимизации с использованием подхода к недоминируемой сортировке на основе опорных точек, часть I: решение проблем с ограничениями ящиков». Труды IEEE по эволюционным вычислениям . 18 (4): 577–601. doi : 10.1109/TEVC.2013.2281535. ISSN  1089-778X. S2CID  206682597.
20. Джейн, Химансю; Деб, Кальянмой (2014). «Эволюционный алгоритм многокритериальной оптимизации с использованием подхода к недоминируемой сортировке на основе опорных точек, часть II: обработка ограничений и расширение до адаптивного подхода». Труды IEEE по эволюционным вычислениям . 18 (4): 602–622. doi :10.1109/TEVC.2013.2281534. ISSN  1089-778X. S2CID  16426862.
21. Миеттинен, Кайса (1998). Нелинейная многокритериальная оптимизация. Международная серия по исследованию операций и науке управления. Том 12. Бостон, Массачусетс: Springer US. doi : 10.1007/978-1-4615-5563-6. ISBN 978-1-4613-7544-9.
22. Jakob, Wilfried (2021), Успешное применение эволюционных алгоритмов: руководство, полученное из реальных приложений (KIT Scientific Working Papers, т. 170), Карлсруэ, Германия: Технологический институт Карлсруэ (KIT), arXiv : 2107.11300 , doi : 10.5445/ir/1000135763, S2CID  236318422