gamultiobj Алгоритм
Введение
Этот раздел описывает алгоритм, который gamultiobj используется для создания набора точек на фронте Парето. gamultiobj использует управляемый, элитный генетический алгоритм (вариант NSGA-II [3]). Элитный GA всегда отдает предпочтение индивидуумам с лучшим значением соответствия (ранга). Контролируемый элитарный ГА также благоприятствует индивидуумам, которые могут помочь увеличить разнообразие населения, даже если они имеют более низкое значение соответствия.
Мультиобъективная терминология
Большая часть терминологии для gamultiobj алгоритм совпадает с терминологией генетического алгоритма. Однако существуют некоторые дополнительные термины, описанные в этом разделе. Для получения дополнительной информации о терминологии и алгоритме см. Deb [3].
Dominance - точка, x доминирует над точкой, y для векторно значимой целевой функции, f когда:
fi (x) ≤ fi (y) для всех i.
fj (x) < fj (y) для некоторых j.
Термин «доминирование» эквивалентен термину «неполноценное:» x доминирует y именно тогда, когда y уступает x.
nondominated set среди множества точек P является набор точек, Q в P, в которых не доминируют никакие точки в P.
Ранг - Для допустимых индивидуумов существует итеративное определение ранга индивидуума. В индивидуумов ранга 1 не доминируют никакие другие индивидуумы. В ранге 2 индивидуумов преобладает только ранг 1 индивидуум. В целом ранжируйте
kв индивидуумах преобладают только лица в рангеk - 1или ниже.
Индивидуумы с более низким рангом имеют более высокие шансы на отбор (более низкий ранг лучше).
Все недопустимые индивидуумы имеют более худший ранг, чем любой допустимый индивидуум. В недопустимом населении ранг является порядком по отсортированной мере недопустимости, плюс самый высокий ранг для допустимых представителей.
gamultiobjиспользует ранг для выбора родительских элементов.Расстояние скученности - расстояние скученности является мерой близости индивидуума к ближайшим соседям.
gamultiobjалгоритм измеряет расстояние среди индивидуумов одного ранга. По умолчанию алгоритм измеряет расстояние в пространстве целевой функции. Однако можно измерить расстояние в пространстве переменных принятия решений (также названном пространством переменных проекта), установивDistanceMeasureFcnопция для{@distancecrowding,'genotype'}.Алгоритм устанавливает расстояние индивидуумов в крайних положениях на
Inf. Для остальных индивидуумов алгоритм вычисляет расстояние как сумму по размерностям нормализованных абсолютных расстояний между отсортированными соседями индивидуума. Другими словами, для размерныхmи отсортированные, масштабированные отдельныеi:distance(i) = sum_m(x(m,i+1) - x(m,i-1)).Алгоритм сортирует каждую размерность отдельно, поэтому термин neighbors означает соседей в каждой размерности.
Индивидуумы того же ранга с более высоким расстоянием имеют более высокие шансы на отбор (более высокое расстояние лучше).
Можно выбрать другое измерение расстояния скученности, чем значение по умолчанию
@distancecrowdingфункция. См. «Мультиобъективные опции».Расстояние скученности является одним из факторов при вычислении спреда, который является частью критерия остановки. Скученная дистанция также используется в качестве разрывателя при выборе турнира, когда два выбранных индивидуумов имеют одинаковый ранг.
Спред - спред является мерой движения набора Парето. Чтобы вычислить спред,
gamultiobjалгоритм сначала оценивает σ, стандартное отклонение меры расстояния скученности точек, которые находятся на фронте Парето с конечным расстоянием. Q - количество этих точек, а d - средняя мера расстояния среди этих точек. Алгоритм затем оценивает μ, сумму по k индексам целевой функции нормы различия между текущей минимальной точкой Парето для этого индекса и минимальной точкой для этого индекса в предыдущей итерации. Спред тогдаspread= (μ + σ) / (μ + Qd).Разброс невелик, когда значения экстремальной целевой функции не сильно изменяются между итерациями (то есть μ мала) и когда точки на фронте Парето распределены равномерно (то есть σ мала).
gamultiobjиспользует спред в условиях остановки. Итерации останавливаются, когда разброс не сильно меняется, и конечный разброс меньше, чем в среднем последние спреды. См. «Остановка Условий».
Инициализация
Первый шаг в gamultiobj алгоритм создает начальную генеральную совокупность. Алгоритм создает население, или можно задать начальную генеральную совокупность или частичную начальную генеральную совокупность при помощи InitialPopulationMatrix опция (см. «Опции населения»). Количество индивидуумов в население устанавливается в значение PopulationSize опция. По умолчанию, gamultiobj создает население, которая является допустимой относительно границ и линейных ограничений, но не обязательно является допустимой относительно нелинейных ограничений. Алгоритм создания по умолчанию является @gacreationuniform когда нет ограничений или только связанных ограничений, и @gacreationlinearfeasible при наличии линейных или нелинейных ограничений.
gamultiobj оценивает целевую функцию и ограничения для населения и использует эти значения для создания счетов для населения.
Итерации
Основная итерация gamultiobj алгоритм протекает следующим образом.
Выберите родительские элементы для следующей генерации с помощью функции выбора для текущего населения. Единственная встроенная функция выбора, доступная для
gamultiobjявляется двоичным турниром. Можно также использовать пользовательскую функцию выбора.Создайте детей от выбранных родительских элементов по мутации и кроссоверу.
Оцените дети путем вычисления их значений целевой функции и выполнимости.
Объедините текущее население и дети в одну матрицу, расширенное население.
Вычислите ранг и расстояние скученности для всех индивидуумов в расширенном населении.
Обрезка расширенного населения, чтобы иметь
PopulationSizeиндивидуумы путем сохранения соответствующего количества индивидуумов каждого ранга.
Условия остановки
Применяются следующие условия остановки. Каждое условие остановки связано с выходным флагом.
| exitflag Значение | Условие остановки |
|---|---|
1 | Геометрическое среднее значение относительного изменения значения спреда по |
0 | Превышено максимальное количество поколений |
-1 | Оптимизация завершается выходной функцией или функцией построения графика |
-2 | Допустимая точка не найдена |
-5 | Превышен предел времени |
Для выходного флага 1 геометрическое среднее относительное изменение спреда имеет множитель ½k для относительного изменения в k-м предыдущей генерации.
Библиография
[1] Censor, Y. «Pareto Optimality in Multiobjective Problems», Appl. Math. Optimiz., Vol. 4, pp 41-59, 1977.
[2] Да Кунья, Н. О. и Е. Полак. «Ограниченная минимизация при векторно-оцененных критериях в конечных размерных пространствах», J. Math. Anal. Appl., Vol. 19, pp 103-124, 1967.
[3] Дэб, Калянмой. «Мультиобъектная оптимизация с использованием эволюционных алгоритмов», John Wiley & Sons, Ltd, Chichester, England, 2001.
[4] Zadeh, L. A. «Optimality and Nonscalar-Valued Performance Criteria», IEEE Trans. Automat. Contr., Vol. AC-8, p. 1, 1963.