gamultiobj Алгоритм
Введение
В этом разделе описываются алгоритм это gamultiobj использование, чтобы создать набор точек на передней стороне Парето. gamultiobj использует управляемый, элитарный генетический алгоритм (вариант NSGA-II [3]). Элитарный GA всегда способствует индивидуумам с лучшим значением фитнеса (ранг). Управляемый элитарный GA также способствует индивидуумам, которые могут помочь увеличить разнообразие населения, даже если у них есть более низкое значение фитнеса.
Многоцелевая терминология
Большая часть терминологии для gamultiobj алгоритм совпадает с Терминологией Генетического алгоритма. Однако существуют некоторые дополнительные условия, описанные в этом разделе. Для получения дополнительной информации о терминологии и алгоритме, смотрите Деб [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 th предыдущее поколение.
Целочисленные и линейные ограничения
Когда проблема имеет целочисленные или линейные ограничения (включая границы), алгоритм изменяет эволюцию населения.
Когда проблема имеет и целочисленные и линейные ограничения, программное обеспечение изменяет всех сгенерированных индивидуумов, чтобы быть выполнимым относительно тех ограничений. Можно использовать любое создание, мутацию, или перекрестно соединить функцию, и целое население остается выполнимым относительно целочисленных и линейных ограничений.
Когда проблема имеет только линейные ограничения, программное обеспечение не изменяет индивидуумов, чтобы быть выполнимым относительно тех ограничений. Необходимо использовать создание, мутацию и перекрестные функции, которые обеспечивают выполнимость относительно линейных ограничений. В противном случае население может стать неосуществимым, и результат может быть неосуществимым. Операторы по умолчанию обеспечивают линейную выполнимость:
gacreationlinearfeasibleилиgacreationnonlinearfeasibleдля создания,mutationadaptfeasibleдля мутации иcrossoverintermediateдля перекрестного соединения.
Внутренние алгоритмы для целочисленной и линейной выполнимости похожи на тех для surrogateopt. Когда проблема имеет целочисленные и линейные ограничения, алгоритм сначала создает линейно допустимые точки. Затем алгоритм пытается удовлетворить целочисленным ограничениям путем округления линейно допустимых точек до целых чисел с помощью эвристики, которая пытается сохранить точки линейно выполнимыми. Когда этот процесс неудачен в получении достаточного количества допустимых точек для построения населения, вызовов алгоритма intlinprog пытаться найти больше точек, которые выполнимы относительно границ, линейных ограничений и целочисленных ограничений.
Позже, когда мутация или перекрестное соединение создают новые члены населения, алгоритмы гарантируют, что новые члены являются целым числом и линейный выполнимый путем делания подобных шагов. Каждый новый член изменяется, при необходимости, чтобы быть максимально близким к его исходному значению, также удовлетворяя целочисленным и линейным ограничениям и границам.
Библиография
[1] Цензор, Y. “Оптимальность Парето в Многоцелевых проблемах”, Прикладная Математика. Optimiz., Издание 4, стр 41–59, 1977.
[2] Da Cunha, N. O. и Э. Полак. “Ограниченная Минимизация Под Критериями с векторным знаком на Конечномерных Пробелах”, J. Математика. Анальный. Прикладной, Издание 19, стр 103–124, 1967.
[3] Деб, Kalyanmoy. “Многоцелевая Оптимизация с помощью Эволюционных Алгоритмов”, John Wiley & Sons, Ltd, Чичестер, Англия, 2001.
[4] Zadeh, L. A. “Оптимальность и Критерии Эффективности с нескалярным знаком”, Автомат Сделки IEEE. Противоречие, издание AC-8, p. 1, 1963.