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 предыдущее поколение.
[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.