#algorithm #optimization #selection #genetic-algorithm #evolutionary-algorithm
#алгоритм #оптимизация #выбор #генетический алгоритм #эволюционный алгоритм
Вопрос:
Мне было интересно, какие различия существуют между алгоритмами векторного генетического алгоритма (VEGA) и генетического алгоритма недоминированной сортировки (NSGA) в контексте выбора при многоцелевой оптимизации?
(Я знаю, что NSGA основан на Парето, в то время как VEGA не основана на Парето.)
Ответ №1:
Различия довольно велики. Как вы говорите, один основан на Парето, а другой — нет. В MOO это огромная вещь. VEGA работает, разбивая совокупность на непересекающиеся множества и заставляя разные наборы эволюционировать для достижения разных целей. Там есть немного механизмов, которые помогают объединить их в осмысленное представление множества Парето, но по сути это просто объединение решений в отношении разных целей. Выбор осуществляется путем выбора решений, которые лучше с точки зрения их индивидуально заданных целевых функций.
NSGA и другие методы, основанные на Парето, полностью отличаются. Они делают выбор не на основе какого-либо конкретного выбора цели, а на свойствах решений по сравнению друг с другом. Каждый такой алгоритм делает несколько разные варианты того, как они выполняют эти сравнения, и NSGA-II (вам определенно следует использовать вторую версию алгоритма) выполняет это путем сортировки без доминирования. По сути, вы находите все решения без доминирования и называете их набором # 1. Затем вы находите все решения, которые не были бы доминирующими, если бы вы удалили элементы набора # 1 — они становятся набором # 2. Вы продолжаете до тех пор, пока все решения не будут учтены, и результатом будет что-то вроде очистки слоев лука. Процедура выбора заключается в том, что вы всегда выбираете членов более низких классов (установите # 1, затем # 2 и так далее). Если вы не можете использовать все элементы определенного уровня, вы разрываете связи, выбирая решения на этом уровне, которые дальше от других, идея в том, что если вы не можете использовать их все, вам следует, по крайней мере, попытаться не выбирать те, которые вы берете из одного крошечного кластера.
В общем, вам следует обратить внимание на методы, основанные на Парето. Они были проверенным выбором по крайней мере 10-15 лет. В частности, вам следует сосредоточиться на элитных методах, основанных на Парето, таких как NSGA-II, SPEA2, epsilon-MOEA и нескольких более поздних претендентах.