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

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

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

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

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

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

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

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

Вычислительная эффективность

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

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

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

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

Многокритериальная оптимизация

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

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

При оптимизации с использованием взвешенной суммы отдельные значения целей сначала нормализуются, чтобы их можно было сравнить. Это можно сделать с помощью затрат или путем указания целевых значений и определения текущего значения как степени выполнения. Затем затраты или степень выполнения можно сравнить друг с другом и, при необходимости, отобразить на единой шкале пригодности. Без потери общности предполагается, что приспособленность представляет собой ценность, которую необходимо максимизировать. Каждой цели присваивается вес в виде процентного значения, так что общую исходную пригодность можно рассчитать как взвешенную сумму: ${\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}$

Нарушение ограничений может быть включено в определяемую таким образом приспособленность в виде штрафных функций . С этой целью для каждого ограничения можно определить функцию , которая возвращает значение между степенью нарушения и в зависимости от него, а результатом является отсутствие нарушения. Ранее определенная необработанная пригодность умножается на штрафную функцию(и), и результатом становится окончательная пригодность : ^[13] ${\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})}}$

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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