Оптимизация по нескольким критериям требует применения специальных методов, которые существенно отличаются от стандартной техники, ориентированной на оптимизацию одной функции.
Без потери общности задачу многокритериальной оптимизации можно сформулировать следующим образом:
$$\max \{z_1=f_1(x),z_2=f_2(x),\dots ,z_q=f_q(x)\}\\g_i(x)\le 0,\ i=1,2,\dots ,m\\x\ge 0$$Здесь пространство поиска решений определяется следующим образом
$$S=\{x\in R^n |g_i(x)\le 0,\ i=1,2,\dots,m,\ x\ge0\}$$В случае многокритериальной оптимизации иногда используется графическая интерпретация как пространстве поиска решений $$S$$, так и пространстве критериев $$S$$
$$Z=\{z\in R^q |{z_1=f_1(x),z_2=f_2(x),\dots ,z_q=f_q(x),\ x\in S\}$$где $$z\in R^k$$- вектор значений $$q$$ целевых функций. Другими словами $$Z$$ является множеством образов в $$S$$.
Следует отметить, что многокритериальные задачи принципиально отличаются от однокритериальных. В последнем случае мы пытаемся найти решение, которое лучше всех остальных решений. В случае
Поэтому при
Для этих целей удобно классифицировать потенциальные решения многокритериальной проблемы на
$$f_i(x)\le f_i(y)$$ для всех $$1\le i \le k$$ при максимизации функции $$f_i$$ и
$$f_i(x)\ge f_i(y)$$ для всех $$1\le i \le k$$ при минимизации функции $$f_i$$.
Присущие ГА свойства способствуют их эффективному применению при решении задач
(рис 5.1) Концепция Парето оптимальных решений
Пусть $$P(t)$$ и $$C(t)$$ - родители и потомки текущей популяции $$t$$. Тогда общая структура
Фактически ГА относится к методам мета-стратегии. При применении ГА для решения конкретной задачи необходимо выбрать или разработать основные компоненты, такие как метод кодирования потенциального решения, генетические операторы кроссинговера и мутации, метод отбора родителей, построить фитнесс-функцию, позволяющую оценивать потенциальные решения и т.д.
Поскольку
Далее мы рассмотрим эти методы более подробно.
Этот метод является фактически первым эволюционным алгоритмом для решения задач
(рис 5.2) Векторный выбор особей
Для иллюстрации приведем простой пример оптимизации функций одной переменной относительно двух целевых функций [2,5]:
$$\min\ f_1(x)=x^2\\\min\ f_2(x)=(x-2)^2\\s.t.\ x\in R^1$$На рис.5.3 а) представлены две целевые функции с областью определения [-2,4]. Очевидно, что оптимальные по Парето решения попадают в [0,2]. На рис.5.3 б) этот пример представлен в пространстве критериев.
Для решения этой задачи использовался ГА с
(рис 5.3) Целевые функции в пространствах решений и критериев.
(рис 5.4) Популяции в пространстве критериев для различных поколений
Из рис.5.4 b) видно, что при $$t=10$$ популяция начинает сходиться к недоминируемой области. Далее при $$t=100$$ популяция, в основном, концентрируется в недоминируемой области, что хорошо видно рис.5.4 с). Наконец, при $$t=500$$ популяция сходится только к трем решениям, как показано на рис.5.4 d). Это явление получило название видообразования.
Метод ранжирования по Парето с применением ГА впервые был предложен Голдбергом [2]. Его суть в следующем: сначала присваивается ранг 1 всем недоминируемым особям, которые удаляются из дальнейшего рассмотрения. Далее среди оставшихся особей находятся недоминируемые, которым присваивается ранг 2. Этот процесс продолжается до тех пор, пока не ранжируется вся популяция. Пример представлен на рис.5.5 для простого случая минимизации относительно двух целевых функций.
(рис 5.5) Ранжирование по Голдбергу
Этот подход получил развитие в последующих работах, например, в [6] предложен метод moGA, где ранг особи соответствует числу особей в текущей популяции, над которыми она доминирует. В этом случае всем недоминируемым особям присваивается ранг 1, а остальным особям присваивается ранг так, как указано выше. На рис.5.6 приведен иллюстративный пример данного метода.
Кроме этого, ранжирование применяется в недоминируемом ГА сортировки [7] nsGA (non dominated sorting genetic algorithm). В этом методе недоминируемым решениям, составляющим фронт, присваивается фиктивные значения фитнесс-функции. Такие решения разделяются согласно этим значениям (производится разделение по фенотипу по векторам решений) и игнорируются в дальнейшем процессе классификации. В конце процедуры фиктивным значениям присваиваются значения, меньшие чем самое малое разделенное значение фитнесс-функции в текущем недоминируемом фронте.
(рис 5.6) Ранжирование в moGA
Далее выделяется следующий фронт, и процедура повторяется до тех пор, пока все особи популяции не классифицируются. На рис.5.7 представлен пример для этого метода.
(рис 5.7) Пример ранжирования в методе nsGA
Здесь каждой целевой функции $$f_i(x)$$ присваивается свой вес $$w_i$$ и задача сводится к скалярному случаю. При этом различные веса $$w_i$$ дают разные решения в смысле Парето.
В сочетании с ГА данный поход (random-weight genetic algorithm ) rwGA впервые использован [2] для получения переменного направления поиска фронта Парето. Обычно используется два вида поиска в пространстве целей (критериев): 1) постоянное направление поиска; 2) кратное направление поиска, которые схематически показаны на рис.5.8.
(рис 5.8) Постоянное и кратное направления поиска в пространстве целей
При фиксированных весах в данном подходе ГА отражает тенденцию постоянного направления поиска, в то время как использование случайных весов в ГА отражает тенденцию переменного направления поиска, более приспособленной для поиска фронта решений. В rwGA каждой цели $$f_k(x)$$ присваивается вес $$w_k=\frac{r_k}{\sum_{j=1}^q r_j}$$, где $$r_j$$–случайные положительные числа из отрезка [0,1] и $$q$$ – число целевых функций. Скалярное значение фитнесс-функции вычисляется путем суммирования взвешенных значений целевых функций. Для паралельного поиска кратных решений веса не фиксируются, что дает возможность ГА искать весь фронт по всем направлениям. Укрупненный алгоритм представлен ниже в виде псевдокода.
В [7] предложен "Strength Pareto Evolutionary Algorithm"(spEA), в котором удачно сочетаются некоторые черты
(рис 5.9) Пример метода spEA для случая максимизации
В [8] Gen и Cheng предложен подход на основе адаптивных весов, который использует полезную информацию о текущей популяции для коррекции весов для того, чтобы направить поиск в сторону положительной идеальной точки, что показано на рис.5.10.
(рис 5.10) Адаптивные веса и адаптивная гиперплоскость
Здесь на каждой итерации для исследуемых решений определяются в пространстве критериев две экстремальные точки: 1) максимальная экстремальная точка $$z^+$$; 2) минимальная экстремальная точка $$z^-$$ следующим образом:
$$z^+=\{z_1^{\max},z_2^{\max},\dots,z_q^{\max}\}\\z^-=\{z_1^{\min},z_2^{\min},\dots,z_q^{\min}\}$$где $$z_k^{\min}$$ и $$z_k^{\max}$$ - минимальное и максимальное значение для $$k$$-ого критерия в текущей популяции. Пусть $$P$$ обозначает множество решений текущей популяции. Тогда определим для данной особи $$x$$ максимальное и минимальное значение для каждого критерия следующим образом:
$$z_k^{\max}=\max\{f_k(x)|x\in P\},\ k=1,2,\dots ,q\\z_k^{\min}=\min\{f_k(x)|x\in P\},\ k=1,2,\dots ,q$$Отметим, что гиперплоскость, определяемая двумя экстремальными точками, является минимальным гиперпараллелограммом, который содержит все текущие решения. Указанные две экстремальные точки обновляются на каждой итерации. При этом адаптивный вес $$k$$-ого критерия вычисляется следующим образом
$$w_k=\frac{1}{z_k^{\max}-z_k^{\min}},\ k=1,2,\dots,q$$Тогда для данной особи $$x$$ взвешенная целевая функция определяется согласно следующему выражению:
$$\begin{align*}z(x)=\sum_{k=1}^q w_k(f_k(x)-z_k^{\min})\\=\sum_{k=1}^q\frac{f_k(x)-z_k^{\min}}{z_k^{\max}-z_k^{\min}}\end{align*}$$Поскольку экстремальные точки обновляются на каждой итерации, то соответственно обновляются и веса. Последнее уравнение представляет гиперплоскость, которая определяется следующими экстремальными точками во множестве текущих решений:
$$(z_1^{\max},z_2^{\min},\dots,z_k^{\min},\dots,z_q^{\min})\\\dots\\(z_1^{\min},z_2^{\min},\dots,z_k^{\max},\dots,z_q^{\min})\\\dots\\(z_1^{\min},z_2^{\min},\dots,z_k^{\min},\dots,z_q^{\max})$$Она задает адаптивную движущуюся линию, которая определяется экстремальными точками $$(z_1^{\max},z_2^{\min})$$ и $$(z_1^{\min},z_2^{\max})$$, как показано на рис.5.10. Здесь прямоугольник, определяемый этими экстремальными точками $$(z_1^{\max},z_2^{\min})$$ и $$(z_1^{\min},z_2^{\max})$$, является минимальным прямоугольником, который содержит все текущие решения. Как показано на рис.5.10 гиперплоскость разделяет пространство критериев $$Z$$ на два подпространства: 1) одно подпространство содержит положительную идеальную точку, обозначаемую, $$z^+$$ ;2) второе подпространство содержит отрицательную идеальную точку $$z^-$$. Все исследуемые решения Парето лежат в пространстве $$z^+$$, при этом все точки, лежащие в $$z^+$$, имеют значения фитнесс-функции большие, чем точки из пространства $$z^-$$. Поскольку максимальная экстремальная точка аппроксимирует положительную идеальную точку в течение процесса эволюции, гиперплоскость последовательно приближается к положительной идеальной точке. Таким образом, данный метод позволяет корректировать веса целевой функции и направляет поиск решений в сторону положительной идеальной точки. Укрупненный алгоритм метода представлен ниже.
В этом методе (Non-dominated sorting algorithm - nsGA) [9] авторы (Deb) пытаются преодолеть, по крайней мере, три проблемы: вычислительную сложность; трудности элитизма; необходимость определения параметров разделения [10]. Общая схема метода представлена на рис.5.11.
(рис 5.11) Общая схема недоминируемого ГА на основе сортировки (минимизация)
Здесь для каждой особи выполняется ранжирование Парето. При этом, как обычно, первый фронт Парето содержит полностью недоминируемые решения, второй фронт – особи, доминируемые решениями второго фронта, и т.д. Особям первого фронта присваивается ранг 1, второго -2 и т.д. В дополнение рангу для каждой особи выполняется оценка расстояния Кроудинга (crowding)[2].
Расстояние Кроудинга является мерой близости особи к своим соседям. Большое среднее расстояние Кроудинга характеризует разнообразие особей в популяции. Далее выполняется сортировка особей согласно расстоянию Кроудинга – особь с большим расстоянием получает меньший ранг. Турнирный отбор родительских особей выполняется на основе значений ранга и расстояния Кроудинга. Укрупненный алгоритм представлен ниже.
При определении значения фитнесс-функции для двух особей предпочтение отдается точке с низшим рангом или точке, расположенной в области с меньшим числом точек, если обе точки принадлежат одному фронту. Путем комбинирования быстрого недоминируемого подхода с сортировкой, схемы элитизма и метода разделения без параметров авторам удалось получить лучшие результаты для некоторых тестовых задач.
После вычисления значения фитнесс-функции для каждой $$i$$-ой особи выполняется специальная процедура отбора. Для двух особей с недоминируемыми рангами $$r_1$$ и $$r_2$$ и расстояниями Кроудинга $$d_1$$ и $$d_2$$ предпочтение отдается решению с низшим (лучшим) рангом согласно следующему правилу $$i<if(r_i<r_j)or((r_i=r_j)and(d_i>d_j))$$
Основная идея ранжирования по Парето основана на четкой классификации недоминируемых и доминируемых решений для каждой особи. Однако порой трудно определить разницу между недоминируемыми и доминируемыми решениями по значениям фитнесс-функции, основанной на ранжировании. Это показано на рис.5.12, где, например, на рис.5.12 с) очевидны различия между доминируемыми и недоминируемыми решениями с координатами $$z_1$$, $$z_2$$(2.2) и (8,8) соответственно, но значения фитнесс-функции, получаемые по методу awGA, не отличаются для решений 13/5 и 11/5.
(рис 5.12) Иллюстрация различных значений фитнесс-функции для разных методов
В отличие от методов определения значений фитнесс-функций, основанных на ранжировании по Парето, в методах определения значений фитнесс-функций, базирующиеся на взвешенной фитнесс-функции, часто легче определить разницу между недоминируемыми и доминируемыми решениями. При этом процесс сортировки становится ненужным, что снижает вычислительные затраты. Для эффективного объединения взвешенных целевых функций в единую целевую функцию необходимо присваивать хорошие значения фитнесс-функции для решений, находящихся близко от фронта Парето.
Здесь, во-первых, используются две экстремальные точки, определяемые как максимальная экстремальная точка $$z^+=\{z_1^{\max},z_2^{\max},\dots,z_q^{\max}\}$$, и минимальная экстремальная точка $$z^-=\{z_1^{\min},z_2^{\min},\dots,z_q^{\min}\}$$, где $$z_k^{\min}$$ и $$z_k^{\max}$$- минимальное и максимальное значение для $$k$$-ой цели в текущей популяции. Тогда адаптивный вес для $$k$$-ой цели вычисляется в соответствии со следующей формулой:
$$w_k=\frac{1}{z_k^{\max}-z_k^{\min}},\ k=1,2,\dots,q$$Далее, вычисляется штрафной терм $$p(v_i)=0$$, если $$v_i$$ является недоминируемым решением в недоминируемом множестве $$P$$. Иначе, для доминируемого решения $$v_i$$ присваивается $$p(v_i)=1$$. Наконец, вычисляется значение фитнесс-функции для каждой особи в соответствии с выражением
$$eval(v_i)=\sum_{k-1}^q w_k(f_k(v_i)-z_k^{\min})+p(v_k),\ \forall i\in popSize$$Число полученных решений
В простейшем случае в качестве меры $$S_j$$ можно использовать количество полученных решений $$|S_j|$$.
Отношение недоминируемых решений $$P_{NDS}(S_j)$$
В этой мере подсчитывается число решений $$x$$, которые входят в Парето-оптимальное решение $$S^*$$ и делится на общее число решений следующим образом:
$$P_{NDS}(S_j)=\frac{|S_j-\{x\in S_j|\exists r\in S^*:r\prec x\}|}{|S_j|}$$где $$r\prec x$$ означает, что решение $$x$$ доминируемо решением $$r$$. Отметим, что равенство $$R_{NDS}(S_j)=1$$ означает, что все решения принадлежат Парето- оптимальному решению $$S^*$$. Напротив, равенство $$R_{NDS}(S_j)=0$$ означает, что ни одно решение не принадлежит Парето-оптимальному решению $$S^*$$. Для достоверности данной меры число полученных решений $$|S_j|$$ должно быть достаточно большим. Однако, если некоторое решение не принадлежит $$S^*$$, то оно не может быть подсчитано в $$R_{NDS}(S_j)$$, что является недостатком данной меры.
Среднее расстояние $$D1_R(S_j)$$
В этом случае в качестве меры используется среднее расстояние решений $$S_j$$ от $$S^*$$, которое определяется следующим образом:
$$D1_R(S_j)=\frac{1}{|S^*|}\sum_{r\in S^*}\min\{d_{rx}|x\in S_j\}$$где $$d_{rx}$$- расстояние между текущим решением $$x$$ и базовым (принадлежащим оптимальному фронту Парето) $$r$$, которое в случае двух целей вычисляется так:
$$d_{rx}=\sqrt{(f_1(r)-f_1(x))^2+(f_2(r)-f_2(x))^2}$$Чем меньше величина $$D1_R(S_j)$$, тем лучше решение $$S_j$$. В этой мере явным образом подсчитывается близость решений $$S_j$$ и $$S^*$$.
(рис 5.13) Иллюстрация мер качества
Оптимизация по нескольким критериям требует применения специальных методов, которые существенно отличаются от стандартной техники, ориентированной на оптимизацию одной функции.
Без потери общности задачу многокритериальной оптимизации можно сформулировать следующим образом:
$$\max \{z_1=f_1(x),z_2=f_2(x),\dots ,z_q=f_q(x)\}\\g_i(x)\le 0,\ i=1,2,\dots ,m\\x\ge 0$$Здесь пространство поиска решений определяется следующим образом
$$S=\{x\in R^n |g_i(x)\le 0,\ i=1,2,\dots,m,\ x\ge0\}$$В случае многокритериальной оптимизации иногда используется графическая интерпретация как пространстве поиска решений $$S$$, так и пространстве критериев $$S$$
$$Z=\{z\in R^q |{z_1=f_1(x),z_2=f_2(x),\dots ,z_q=f_q(x),\ x\in S\}$$где $$z\in R^k$$- вектор значений $$q$$ целевых функций. Другими словами $$Z$$ является множеством образов в $$S$$.
Следует отметить, что многокритериальные задачи принципиально отличаются от однокритериальных. В последнем случае мы пытаемся найти решение, которое лучше всех остальных решений. В случае
Поэтому при
Для этих целей удобно классифицировать потенциальные решения многокритериальной проблемы на
$$f_i(x)\le f_i(y)$$ для всех $$1\le i \le k$$ при максимизации функции $$f_i$$ и
$$f_i(x)\ge f_i(y)$$ для всех $$1\le i \le k$$ при минимизации функции $$f_i$$.
Присущие ГА свойства способствуют их эффективному применению при решении задач
(рис 5.1) Концепция Парето оптимальных решений
Пусть $$P(t)$$ и $$C(t)$$ - родители и потомки текущей популяции $$t$$. Тогда общая структура
Фактически ГА относится к методам мета-стратегии. При применении ГА для решения конкретной задачи необходимо выбрать или разработать основные компоненты, такие как метод кодирования потенциального решения, генетические операторы кроссинговера и мутации, метод отбора родителей, построить фитнесс-функцию, позволяющую оценивать потенциальные решения и т.д.
Поскольку
Далее мы рассмотрим эти методы более подробно.
Этот метод является фактически первым эволюционным алгоритмом для решения задач
(рис 5.2) Векторный выбор особей
Для иллюстрации приведем простой пример оптимизации функций одной переменной относительно двух целевых функций [2,5]:
$$\min\ f_1(x)=x^2\\\min\ f_2(x)=(x-2)^2\\s.t.\ x\in R^1$$На рис.5.3 а) представлены две целевые функции с областью определения [-2,4]. Очевидно, что оптимальные по Парето решения попадают в [0,2]. На рис.5.3 б) этот пример представлен в пространстве критериев.
Для решения этой задачи использовался ГА с
(рис 5.3) Целевые функции в пространствах решений и критериев.
(рис 5.4) Популяции в пространстве критериев для различных поколений
Из рис.5.4 b) видно, что при $$t=10$$ популяция начинает сходиться к недоминируемой области. Далее при $$t=100$$ популяция, в основном, концентрируется в недоминируемой области, что хорошо видно рис.5.4 с). Наконец, при $$t=500$$ популяция сходится только к трем решениям, как показано на рис.5.4 d). Это явление получило название видообразования.
Метод ранжирования по Парето с применением ГА впервые был предложен Голдбергом [2]. Его суть в следующем: сначала присваивается ранг 1 всем недоминируемым особям, которые удаляются из дальнейшего рассмотрения. Далее среди оставшихся особей находятся недоминируемые, которым присваивается ранг 2. Этот процесс продолжается до тех пор, пока не ранжируется вся популяция. Пример представлен на рис.5.5 для простого случая минимизации относительно двух целевых функций.
(рис 5.5) Ранжирование по Голдбергу
Этот подход получил развитие в последующих работах, например, в [6] предложен метод moGA, где ранг особи соответствует числу особей в текущей популяции, над которыми она доминирует. В этом случае всем недоминируемым особям присваивается ранг 1, а остальным особям присваивается ранг так, как указано выше. На рис.5.6 приведен иллюстративный пример данного метода.
Кроме этого, ранжирование применяется в недоминируемом ГА сортировки [7] nsGA (non dominated sorting genetic algorithm). В этом методе недоминируемым решениям, составляющим фронт, присваивается фиктивные значения фитнесс-функции. Такие решения разделяются согласно этим значениям (производится разделение по фенотипу по векторам решений) и игнорируются в дальнейшем процессе классификации. В конце процедуры фиктивным значениям присваиваются значения, меньшие чем самое малое разделенное значение фитнесс-функции в текущем недоминируемом фронте.
(рис 5.6) Ранжирование в moGA
Далее выделяется следующий фронт, и процедура повторяется до тех пор, пока все особи популяции не классифицируются. На рис.5.7 представлен пример для этого метода.
(рис 5.7) Пример ранжирования в методе nsGA
Здесь каждой целевой функции $$f_i(x)$$ присваивается свой вес $$w_i$$ и задача сводится к скалярному случаю. При этом различные веса $$w_i$$ дают разные решения в смысле Парето.
В сочетании с ГА данный поход (random-weight genetic algorithm ) rwGA впервые использован [2] для получения переменного направления поиска фронта Парето. Обычно используется два вида поиска в пространстве целей (критериев): 1) постоянное направление поиска; 2) кратное направление поиска, которые схематически показаны на рис.5.8.
(рис 5.8) Постоянное и кратное направления поиска в пространстве целей
При фиксированных весах в данном подходе ГА отражает тенденцию постоянного направления поиска, в то время как использование случайных весов в ГА отражает тенденцию переменного направления поиска, более приспособленной для поиска фронта решений. В rwGA каждой цели $$f_k(x)$$ присваивается вес $$w_k=\frac{r_k}{\sum_{j=1}^q r_j}$$, где $$r_j$$–случайные положительные числа из отрезка [0,1] и $$q$$ – число целевых функций. Скалярное значение фитнесс-функции вычисляется путем суммирования взвешенных значений целевых функций. Для паралельного поиска кратных решений веса не фиксируются, что дает возможность ГА искать весь фронт по всем направлениям. Укрупненный алгоритм представлен ниже в виде псевдокода.
В [7] предложен "Strength Pareto Evolutionary Algorithm"(spEA), в котором удачно сочетаются некоторые черты
(рис 5.9) Пример метода spEA для случая максимизации
В [8] Gen и Cheng предложен подход на основе адаптивных весов, который использует полезную информацию о текущей популяции для коррекции весов для того, чтобы направить поиск в сторону положительной идеальной точки, что показано на рис.5.10.
(рис 5.10) Адаптивные веса и адаптивная гиперплоскость
Здесь на каждой итерации для исследуемых решений определяются в пространстве критериев две экстремальные точки: 1) максимальная экстремальная точка $$z^+$$; 2) минимальная экстремальная точка $$z^-$$ следующим образом:
$$z^+=\{z_1^{\max},z_2^{\max},\dots,z_q^{\max}\}\\z^-=\{z_1^{\min},z_2^{\min},\dots,z_q^{\min}\}$$где $$z_k^{\min}$$ и $$z_k^{\max}$$ - минимальное и максимальное значение для $$k$$-ого критерия в текущей популяции. Пусть $$P$$ обозначает множество решений текущей популяции. Тогда определим для данной особи $$x$$ максимальное и минимальное значение для каждого критерия следующим образом:
$$z_k^{\max}=\max\{f_k(x)|x\in P\},\ k=1,2,\dots ,q\\z_k^{\min}=\min\{f_k(x)|x\in P\},\ k=1,2,\dots ,q$$Отметим, что гиперплоскость, определяемая двумя экстремальными точками, является минимальным гиперпараллелограммом, который содержит все текущие решения. Указанные две экстремальные точки обновляются на каждой итерации. При этом адаптивный вес $$k$$-ого критерия вычисляется следующим образом
$$w_k=\frac{1}{z_k^{\max}-z_k^{\min}},\ k=1,2,\dots,q$$Тогда для данной особи $$x$$ взвешенная целевая функция определяется согласно следующему выражению:
$$\begin{align*}z(x)=\sum_{k=1}^q w_k(f_k(x)-z_k^{\min})\\=\sum_{k=1}^q\frac{f_k(x)-z_k^{\min}}{z_k^{\max}-z_k^{\min}}\end{align*}$$Поскольку экстремальные точки обновляются на каждой итерации, то соответственно обновляются и веса. Последнее уравнение представляет гиперплоскость, которая определяется следующими экстремальными точками во множестве текущих решений:
$$(z_1^{\max},z_2^{\min},\dots,z_k^{\min},\dots,z_q^{\min})\\\dots\\(z_1^{\min},z_2^{\min},\dots,z_k^{\max},\dots,z_q^{\min})\\\dots\\(z_1^{\min},z_2^{\min},\dots,z_k^{\min},\dots,z_q^{\max})$$Она задает адаптивную движущуюся линию, которая определяется экстремальными точками $$(z_1^{\max},z_2^{\min})$$ и $$(z_1^{\min},z_2^{\max})$$, как показано на рис.5.10. Здесь прямоугольник, определяемый этими экстремальными точками $$(z_1^{\max},z_2^{\min})$$ и $$(z_1^{\min},z_2^{\max})$$, является минимальным прямоугольником, который содержит все текущие решения. Как показано на рис.5.10 гиперплоскость разделяет пространство критериев $$Z$$ на два подпространства: 1) одно подпространство содержит положительную идеальную точку, обозначаемую, $$z^+$$ ;2) второе подпространство содержит отрицательную идеальную точку $$z^-$$. Все исследуемые решения Парето лежат в пространстве $$z^+$$, при этом все точки, лежащие в $$z^+$$, имеют значения фитнесс-функции большие, чем точки из пространства $$z^-$$. Поскольку максимальная экстремальная точка аппроксимирует положительную идеальную точку в течение процесса эволюции, гиперплоскость последовательно приближается к положительной идеальной точке. Таким образом, данный метод позволяет корректировать веса целевой функции и направляет поиск решений в сторону положительной идеальной точки. Укрупненный алгоритм метода представлен ниже.
В этом методе (Non-dominated sorting algorithm - nsGA) [9] авторы (Deb) пытаются преодолеть, по крайней мере, три проблемы: вычислительную сложность; трудности элитизма; необходимость определения параметров разделения [10]. Общая схема метода представлена на рис.5.11.
(рис 5.11) Общая схема недоминируемого ГА на основе сортировки (минимизация)
Здесь для каждой особи выполняется ранжирование Парето. При этом, как обычно, первый фронт Парето содержит полностью недоминируемые решения, второй фронт – особи, доминируемые решениями второго фронта, и т.д. Особям первого фронта присваивается ранг 1, второго -2 и т.д. В дополнение рангу для каждой особи выполняется оценка расстояния Кроудинга (crowding)[2].
Расстояние Кроудинга является мерой близости особи к своим соседям. Большое среднее расстояние Кроудинга характеризует разнообразие особей в популяции. Далее выполняется сортировка особей согласно расстоянию Кроудинга – особь с большим расстоянием получает меньший ранг. Турнирный отбор родительских особей выполняется на основе значений ранга и расстояния Кроудинга. Укрупненный алгоритм представлен ниже.
При определении значения фитнесс-функции для двух особей предпочтение отдается точке с низшим рангом или точке, расположенной в области с меньшим числом точек, если обе точки принадлежат одному фронту. Путем комбинирования быстрого недоминируемого подхода с сортировкой, схемы элитизма и метода разделения без параметров авторам удалось получить лучшие результаты для некоторых тестовых задач.
После вычисления значения фитнесс-функции для каждой $$i$$-ой особи выполняется специальная процедура отбора. Для двух особей с недоминируемыми рангами $$r_1$$ и $$r_2$$ и расстояниями Кроудинга $$d_1$$ и $$d_2$$ предпочтение отдается решению с низшим (лучшим) рангом согласно следующему правилу $$i<if(r_i<r_j)or((r_i=r_j)and(d_i>d_j))$$
Основная идея ранжирования по Парето основана на четкой классификации недоминируемых и доминируемых решений для каждой особи. Однако порой трудно определить разницу между недоминируемыми и доминируемыми решениями по значениям фитнесс-функции, основанной на ранжировании. Это показано на рис.5.12, где, например, на рис.5.12 с) очевидны различия между доминируемыми и недоминируемыми решениями с координатами $$z_1$$, $$z_2$$(2.2) и (8,8) соответственно, но значения фитнесс-функции, получаемые по методу awGA, не отличаются для решений 13/5 и 11/5.
(рис 5.12) Иллюстрация различных значений фитнесс-функции для разных методов
В отличие от методов определения значений фитнесс-функций, основанных на ранжировании по Парето, в методах определения значений фитнесс-функций, базирующиеся на взвешенной фитнесс-функции, часто легче определить разницу между недоминируемыми и доминируемыми решениями. При этом процесс сортировки становится ненужным, что снижает вычислительные затраты. Для эффективного объединения взвешенных целевых функций в единую целевую функцию необходимо присваивать хорошие значения фитнесс-функции для решений, находящихся близко от фронта Парето.
Здесь, во-первых, используются две экстремальные точки, определяемые как максимальная экстремальная точка $$z^+=\{z_1^{\max},z_2^{\max},\dots,z_q^{\max}\}$$, и минимальная экстремальная точка $$z^-=\{z_1^{\min},z_2^{\min},\dots,z_q^{\min}\}$$, где $$z_k^{\min}$$ и $$z_k^{\max}$$- минимальное и максимальное значение для $$k$$-ой цели в текущей популяции. Тогда адаптивный вес для $$k$$-ой цели вычисляется в соответствии со следующей формулой:
$$w_k=\frac{1}{z_k^{\max}-z_k^{\min}},\ k=1,2,\dots,q$$Далее, вычисляется штрафной терм $$p(v_i)=0$$, если $$v_i$$ является недоминируемым решением в недоминируемом множестве $$P$$. Иначе, для доминируемого решения $$v_i$$ присваивается $$p(v_i)=1$$. Наконец, вычисляется значение фитнесс-функции для каждой особи в соответствии с выражением
$$eval(v_i)=\sum_{k-1}^q w_k(f_k(v_i)-z_k^{\min})+p(v_k),\ \forall i\in popSize$$Число полученных решений
В простейшем случае в качестве меры $$S_j$$ можно использовать количество полученных решений $$|S_j|$$.
Отношение недоминируемых решений $$P_{NDS}(S_j)$$
В этой мере подсчитывается число решений $$x$$, которые входят в Парето-оптимальное решение $$S^*$$ и делится на общее число решений следующим образом:
$$P_{NDS}(S_j)=\frac{|S_j-\{x\in S_j|\exists r\in S^*:r\prec x\}|}{|S_j|}$$где $$r\prec x$$ означает, что решение $$x$$ доминируемо решением $$r$$. Отметим, что равенство $$R_{NDS}(S_j)=1$$ означает, что все решения принадлежат Парето- оптимальному решению $$S^*$$. Напротив, равенство $$R_{NDS}(S_j)=0$$ означает, что ни одно решение не принадлежит Парето-оптимальному решению $$S^*$$. Для достоверности данной меры число полученных решений $$|S_j|$$ должно быть достаточно большим. Однако, если некоторое решение не принадлежит $$S^*$$, то оно не может быть подсчитано в $$R_{NDS}(S_j)$$, что является недостатком данной меры.
Среднее расстояние $$D1_R(S_j)$$
В этом случае в качестве меры используется среднее расстояние решений $$S_j$$ от $$S^*$$, которое определяется следующим образом:
$$D1_R(S_j)=\frac{1}{|S^*|}\sum_{r\in S^*}\min\{d_{rx}|x\in S_j\}$$где $$d_{rx}$$- расстояние между текущим решением $$x$$ и базовым (принадлежащим оптимальному фронту Парето) $$r$$, которое в случае двух целей вычисляется так:
$$d_{rx}=\sqrt{(f_1(r)-f_1(x))^2+(f_2(r)-f_2(x))^2}$$Чем меньше величина $$D1_R(S_j)$$, тем лучше решение $$S_j$$. В этой мере явным образом подсчитывается близость решений $$S_j$$ и $$S^*$$.
(рис 5.13) Иллюстрация мер качества
Для получения официальных документов о завершении программы дополнительного профессионального образования (удостоверения о повышении квалификации, дипломов о профессиональной переподготовке и MBA) необходимо предоставить:
Внимание! Вы можете не заказывать доставку бумажной версии официального документы, а скачать его в электронном виде и распечатать самостоятельно. Информация о выданном документе в течение 1 месяца загружается в Федеральную информационную систему «Федеральный реестр сведений о документах об образовании и (или) о квалификации, документах об обучении» - ФИС ФРДО.
Доступ на новый сайт осуществляется с использованием адреса электронной почты, который был указан вами при регистрации на "старом". Мы постарались перенести все ваши данные с прежнего ресурса, однако не исключена вероятность потери части информации.
При возникновении проблемы со входом, воспользуйтесь функцией сброса пароля
Если вы обнаружите несоответствия, пожалуйста, сообщите нам.