close

Вход

Забыли?

вход по аккаунту

?

Вероятностный генетический алгоритм для задач многокритериальной оптимизации.

код для вставкиСкачать
Вестник Сибирского государственного аэрокосмического университета имени академика М. Ф. Решетнева
Библиографический список
шетнева / под ред. проф. Г. П. Белякова ; Сиб. гос. аэрокосмич. ун-т. Красноярск, 2006. Вып. № 4(11). С. 32–37.
3. Подиновский, В. В. Парето-оптимальные решения
многокритериальных задач / В. В. Подиновский,
В. Д. Ногин. М. : Наука, 1982. 256 с.
4. Штойер, Р. Многокритериальная оптимизация: теория,
вычисления, приложения / P. Штойер. М. : Наука, 1982. 600 с.
5. Линейная динамика: программа для ЭВМ. Свидетельство о регистрации № 2004611491 от 17.06.2004. Правообладатели А. В. Медведев, П. Н. Победаш.
1. Медведев, А. В. Теоретическое и численное исследование двухкритериальной модели оптимизации реальных инвестиций / А. В. Медведев // Вестник Томс. гос. унта. Томск, 2006. С. 315–321.
2. Медведев, А. В. Применение z-преобразования и
дискретного принципа максимума к анализу модели реальных инвестиций / А. В. Медведев, П. Н. Победаш //
Вестник Сиб. гос. аэрокосмич. ун-та им. акад. М. Ф. Ре-
А. V. Medvedev
TO THE Z-TRANSFORMATION APPLY FOR THE ANALYSIS OF THE
MULTYCRITERIAL LINE OPTIMAL CONTROL PROBLEM OF ECONOMIC DYNAMICS
The generalization of the z-transformation approach for the analysis of the multycriterial line optimal control problem
is suggested. The z-transformation is applied for the proof of decision existing and receiving of the sufficient conditions
of noneffectivity of the regional investment projects on the example of two-criterial model of a regional economics.
УДК 519.68
А. Ю. Ворожейкин, Е. С. Семенкин
ВЕРОЯТНОСТНЫЙ ГЕНЕТИЧЕСКИЙ АЛГОРИТМ ДЛЯ ЗАДАЧ
МНОГОКРИТЕРИАЛЬНОЙ ОПТИМИЗАЦИИ1
Для решения задач условной многокритериальной оптимизации предложен вероятностный генетический
алгоритм. Проведен сравнительный анализ его эффективности на тестовых задачах. Показано, что вероятностный генетический алгоритм не уступает по эффективности стандартному генетическому алгоритму.
Постановка задачи и описание подхода. В общем виде
многокритериальная задача оптимизации включает набор N параметров (переменных), множество K целевых
функций и множество M ограничений. Целевые функции и ограничения являются функциями переменных.
Таким образом, при решении многокритериальной
задачи необходимо найти оптимум по K критериям, а
сама задача формально записывается следующим образом:
кую оптимизационную процедуру, основанную на имитации процессов естественной эволюции. Е. С. Семенкиным и Е. А. Соповым был предложен вероятностный генетический алгоритм (ВГА) безусловной оптимизации [2].
Работу ВГА в общем виде можно представить следующим образом.
1. Инициализировать случайным образом популяцию
решений.
2. С помощью оператора селекции выбрать r наиболее пригодных индивидов текущей популяции (родителей). Вычислить распределение
P = { p1, , pn } ,
y = f ( x ) = ( f1( x ), f 2 ( x ),..., f K ( x)) ? opt ,
g ( x) = ( g1( x), g 2 ( x),..., g r ( x)) ? 0 ,
h( x ) = (hr +1( x),
, hM ( x )) = 0 ,
{
где x = ( x1, x2 ,..., xN ) ? X – вектор решений, удовлетворяющий M ограничениям, y = ( y1, y2 ,..., y K ) ? Y – вектор целевых функций. При этом X означает пространство решений, а Y – пространство целей или критериальное пространство.
Последние десятилетия получили развитие и продемонстрировали свою универсальность и применимость
в сложных практических задачах так называемые эволюционные алгоритмы, в частности – генетический алгоритм (ГА) [1], которые представляют собой стохастичес-
r
} 1r ? xij , j = 1, n ,
pj = P xj =1 =
i =1
где n – длина хромосомы; xij – j-й бит i-го индивида.
1. В соответствии с полученным распределением
P = { p1, , pn } сформировать популяцию потомков с помощью датчика псевдослучайных чисел.
2. Новые решения (потомки) подвергнуть мутации.
3. Из популяции родителей и потомков сформировать
новую рабочую популяцию.
4. Повторять шаги 2–5 пока не выполнится условие
остановки.
Работа выполнялась при поддержке ФЦНТП по теме 2006-РИ-19.0/001/377 (государственный контракт № 02.442.11.7337)
и Фонда содействия развитию малых форм предприятий в научно-технической сфере.
1
41
Математика, механика, информатика
? g ( x, y ) = ( x ? 2)2 + ( y ? 2) 2 ? 10, 24
? 1
?
2
2
? g 2 ( x, y ) = ( x ? 5) + ( y ? 1) ? 16 .
?
2
2
?? g3 ( x, y ) = ( x ? 3) + ( y ? 4) ? 9
Для решения задач условной многокритериальной
оптимизации генетические алгоритмы должны быть оснащены методами учета ограничений и наличия многих
целевых функций.
В данной работе для учета ограничений использовался
метод динамического штрафа [3], выбранный после проведения сравнительного анализа эффективности различных
методов учета ограничений в генетических алгоритмах.
Рассмотрим следующую задачу условной оптимизации для i-го критерия:
fi ( x) ? opt , i = 1, K ,
Задача 3.
f 2 ( x, y ) = ( x + 2)2 + ( y ? 2)2 ? min
f3 ( x, y ) = ( x ? 3) 2 + ( y ? 4) 2 ? min
f 4 ( x, y ) = ( x ? 4)2 + ( y ? 2) 2 ? min
? g ( x, y ) = ( x + 1.8) 2 + ( y ? 2)2 ? 4
? 1
? g ( x, y ) = ( x ? 1)2 + ( y ? 4.5)2 ? 4
? 2
?
2
2
? g3 ( x, y ) = ( x ? 5.2) + ( y ? 2) ? 9 .
?
2
2
? g 4 ( x, y ) = ( x ? 1) + ( y + 2) ? 9
?
2
2
?? g5 ( x, y ) = ( x ? 1) + ( y ? 2) ? 6, 25
? g j ( x) ? 0, j = 1, r ,
?
?
??h j ( x) = 0, j = r + 1, M .
В методе динамического штрафа пригодность индивида x вычисляется по формуле
M
fitnessi ( x ) = fi ( x ) + ?? (t ) ? f j? ( x ) ,
j =1
Задача 4.
где t – номер текущего поколения; ? = 1, если решается
задача минимизации; ? = ?1, если решается задача максимизации; f j ( x) – штраф за нарушение j-го ограничения;
б
в – вещественное число; л(t ) = (C ? t ) .
Штрафы f j ( x) вычисляются динамически, в зависимости от степени нарушения ограничений, по формуле [3]
{
f1( x, y ) = ( x ? 1) 2 + ( y + 1) 2 ? min
f 2 ( x, y ) = ( x + 2)2 + ( y ? 2)2 ? min
f3 ( x, y ) = ( x ? 3) 2 + ( y ? 4) 2 ? min
f 4 ( x, y ) = ( x ? 4)2 + ( y ? 2) 2 ? min
?? g ( x, y ) = x 2 + ( y ? 6) 2 ? 4
1
?
?? g 2 ( x, y ) = ( x + 2)2 + ( y ? 5)2 ? 4 .
}
?max 0, g j ( x) , j = 1, r
?
.
f j ( x) = ?
?? h j ( x) , j = r + 1, M
Параметры C , б, в подбираются на практике для каж-
Особенность последней задачи состоит в том, что допустимая область лежит вне множества Парето.
В качестве исследуемых характеристик были выбраны: разброс точек в пространствах X и Y, процент Паретовских точек (%), процент допустимых точек (% доп.). В
задачах 1 и 4 множество Парето представляет собой отрезок и части окружностей соответственно, поэтому для
этих задач дополнительно исследовалось среднее расстояние (Ср.р) до отрезка и окружностей. Поскольку алгоритмы являются стохастическими, то для каждой настройки алгоритмов эксперименты проводились по 50 раз и
исследуемые характеристики усреднялись. Для проверки того, являются ли различия между алгоритмами случайными, применялся тест Колмогорова–Смирнова
(Kstest) с 5 % уровнем значимости. Kstest = 0, если различия случайны, иначе Kstest = 1.
Тестирование проводилось при наилучших и наихудших настройках генетических операторов алгоритмов, для
того чтобы установить диапазон влияния вносимых изменений на качество работы (например, эти изменения,
возможно, и не улучшают работу алгоритма при наилучших настройках, но улучшают при наихудших, что дает
положительный эффект в условиях произвольного выбора настроек неподготовленным в области эволюционной
оптимизации пользователем).
Метод SPEA представлен в табл. 1–4.
Различия между наихудшими настройками ГА и ВГА
во всех случаях носят случайный характер. Различия между
наилучшими настройками в большинстве случаев носят
случайный характер. В тех случаях, когда различие не случайно, абсолютные значения отличаются не существенно.
Метод NPGA представлен в табл. 5–8.
дой задачи индивидуально. Рекомендованные значения
C = 0,5 , б = в = 2 [3].
Процедура штрафования, переводит элемент y из критериального пространства Y, в оштрафованное критери~
альное пространство, которое обозначим Y.
Для анализа эффективности многокритериальной
оптимизации вероятностными генетическим алгоритмом
были выбраны четыре наиболее распространенные известные схемы: VEGA (Vector Evaluated Genetic Algorithm)
[4], FFGA (Fonseca and Fleming’s Multiobjective Genetic
Algorithm) [5], NPGA (Niched Pareto Genetic Algorithm) [6],
SPEA (Strength Pareto Evolutionary Algorithm) [7].
Для задач условной оптимизации принцип Паретодоминирования следует применять в оштрафованном
~
критериальном пространстве Y.
Сравнение эффективности стандартного ГА и ВГА.
Сравнение эффективности алгоритмов проводилось на
следующих тестовых задачах условной оптимизации
Задача 1.
f1( x, y ) = ( x ? 6)2 + ( y ? 4)2 ? min
f 2 ( x, y ) = ( x + 2)2 + ( y ? 5)2 ? min
?? g ( x, y ) = ( x ? 1) 2 + ( y ? 4) 2 ? 4
1
?
2
2
?? g 2 ( x, y ) = ( x ? 3) + ( y ? 4) ? 6, 25.
Задача 2.
f1( x, y ) = ( x ? 1) 2 + ( y + 1) 2 ? min
f1( x, y ) = ( x ? 6)2 + ( y ? 4)2 ? min
f 2 ( x, y ) = ( x + 2)2 + ( y ? 5)2 ? min
f3 ( x, y ) = ( x ? 4)2 + ( y + 4)2 ? min
42
Вестник Сибирского государственного аэрокосмического университета имени академика М. Ф. Решетнева
Различия между наилучшими настройками в половине случаев носят случайных характер. В тех случаях, когда
различие не случайно, стандартный ГА обеспечил луч-
ший разброс точек, а ВГА лучший процент допустимых
точек. Различия между наихудшими настройками также
в половине случаев носят случайный характер. В тех слуТаблица 1
Численные характеристики наилучших настроек
№
X
0,025 3
0,055 3
0,036 8
0,008 2
1
2
3
4
Y
0,020 5
0,034 8
0,022 0
0,006 5
Стандартный ГА
%
% доп.
0
95,933 3
94,933 3
98,533 3
86,560 9
86,496 6
0
73,835 2
Ср.р
0,107 8
X
0,025 4
0,055 4
0,036 4
0,007 7
0,003 1
Вероятностный ГА
%
% доп.
Y
0,020 5
0
96,328 7
0,035 0
93,400 0
98,600 0
0,021 7
83,240 9
84,664 4
0,006 1
0
74,591 6
Ср.р
0,107 4
0,004 2
Таблица 2
Статистические характеристики наилучших настроек
№
X
0
0
0
0
1
2
3
4
Y
0
0
0
0
Kstest
% Парето
% доп.
0
0
0
0
0
1
Ср.р
0
1
Таблица 3
Численные характеристики наихудших настроек
№
X
0,024 2
0,054 2
0,035 2
0,005 5
1
2
3
4
Стандартный ГА
Y
%
% доп.
0,020 2
0
94,933 3
0,034 7
93,800 0
97,533 3
0,021 0
84,726 4
83,031 2
0,004 5
0
60,943 4
X
0,024 0
0,054 4
0,034 9
0,006 3
Ср.р
0,136 2
0,005 0
Вероятностный ГА
Y
%
% доп.
0,020 2
0
94,666 7
0,035 0
93,866 7
97,933 3
0,020 8
82,213 8
82,793 1
0,005 1
0
65,531 1
Ср.р
0,130 6
0,004 9
Таблица 4
Статистические характеристики наихудших настроек
№
X
0
0
0
0
1
2
3
4
Kstest
% Парето
Y
0
0
0
0
% доп.
0
0
0
0
0
0
Ср.р
0
0
Таблица 5
Численные характеристики наилучших настроек
№
1
2
3
4
X
0,032 5
0,048 9
0,031 6
0,003 3
Y
0,017 0
0,030 8
0,018 1
0,003 3
Стандартный ГА
%
% доп.
0
93,790 9
47,862 1
92,894 0
92,713 8
92,713 8
0
61,908 2
Ср.р
0,183 8
0,026 7
X
0,030 7
0,047 6
0,023 1
0,001 5
Y
0,016 6
0,030 1
0,013 2
0,001 5
Вероятностный ГА
%
% доп.
0
95,732 1
61,698 0
92,847 7
23,072 0
93,590 5
0
63,961 8
Ср.р
0,286 4
0,051 1
Таблица 6
Статистические характеристики наилучших настроек
№
X
1
0
1
0
1
2
3
4
Y
1
0
1
0
% Парето
Kstest
1
1
% доп.
1
1
1
0
Ср.р
1
0
Таблица 7
Численные характеристики наихудших настроек
№
1
2
3
4
X
0,019 3
0,042 3
0,022 4
0,000 0
Стандартный ГА
%
Y
0,015 8
0
0,026 8
91,391 9
0,012 3
80,422 6
0,000 0
0
% доп.
38,418 6
48,436 9
17,824 8
0,343 1
Ср.р
0,523 0
0,224 0
43
X
0,015 1
0,041 6
0,020 6
0,000 0
Вероятностный ГА
%
% доп.
Y
0,013 1
0
48,683 7
0,026 5
92,685 5
62,506 5
0,011 3
85,478 0
23,072 0
0,000 0
0
0,445 3
Ср.р
0,453 7
0,121 2
Математика, механика, информатика
чаях, когда различие не случайно, стандартный ГА обеспечил лучший разброс точек, а ВГА лучший процент
допустимых и Паретовских точек.
Метод FFGA представлен в табл. 9–12.
Различия между показателями разброса по X и Y среди наилучших настроек в большинстве случаев не случайно. Стандартный ГА обеспечил наилучший разброс
точек, в то время как ВГА обеспечил наилучший процент Паретовских точек, и эти различия также не случайны. Различия между показателями разброса среди наихудших настроек в большинстве случаев случайны. В тех
случаях, когда различия не случайны, стандартный ГА
обеспечивает наилучший разброс. ВГА обеспечил наилучший процент допустимых и Паретовских точек, и это
различие не случайно.
Метод VEGA представлен в табл. 13–16.
Для наилучших настроек стандартный ГА обеспечил
наилучший разброс точек, и наилучшее расстояние до
множества Парето в задачах 1 и 4, эти различия не слу-
чайны. По проценту допустимых и Паретовских точек в
половине случаев различия случайны. В тех же случаях,
когда различия не случайны, ВГА обеспечивает наилучшее значение этих показателей. Для наихудших настроек
стандартный ГА также обеспечил наилучший разброс
точек. По проценту допустимых точек различия случайны, а по проценту Паретовских точек различия не случайны в половине случаев в пользу ВГА.
Суммируя выводы по каждой схеме, можно сделать
общее заключение: в большинстве случаев стандартный ГА
обеспечивает наилучший разброс точек в критериальном
пространстве и пространстве решений. Однако в абсолютном выражении различие между этими показателями несущественно. ВГА в большинстве случаев обеспечивает наилучший процент Паретовских и допустимых точек.
Таким образом, показано, что ВГА справляется с решением тестовых задач не хуже стандартного ГА, а в некоторых случаях превосходит его. Кроме того, ВГА содержит меньше настраиваемых параметров (отсутствует
Таблица 8
Статистические характеристики наихудших настроек
№
X
0
0
1
1
1
2
3
4
Y
0
0
1
1
% Парето
Kstest
% доп.
1
0
1
0
1
1
Ср.р
1
1
Таблица 9
Численные характеристики наилучших настроек
№
X
0,028 7
0,051 2
0,029 9
0,003 2
1
2
3
4
Y
0,016 1
0,032 7
0,017 3
0,002 7
Стандартный ГА
%
% доп.
0
96,649 8
50,188 8
95,267 4
28,852 3
94,275 2
0
74,899 6
Ср.р
0,075 0
0,018 9
X
0,025 3
0,049 7
0,022 7
0,001 4
Y
0,015 9
0,031 4
0,012 6
0,001 4
Вероятностный ГА
%
% доп.
0
97,279 4
56,878 9
95,781 2
44,398 4
93,823 7
0
72,016 0
Ср.р
0,150 5
0,045 8
Таблица 10
Статистические характеристики наилучших настроек
№
1
2
3
4
X
1
1
1
1
Y
0
1
1
1
% Парето
Kstest
1
1
% доп.
0
0
0
0
Ср.р
1
0
Таблица 11
Численные характеристики наихудших настроек
№
1
2
3
4
X
0,014 4
0,038 2
0,018 0
0
Y
0,012 4
0,023 9
0,009 7
0
Стандартный ГА
%
% доп.
0
52,834 1
94,255 7
48,656 6
92,991 7
23,082 7
0
1,044 2
Ср.р
0,385 9
0,212 2
X
0,012 1
0,033 7
0,015 4
0,000 5
Вероятностный ГА
Y
%
% доп.
0,010 7
0
65,999 3
0,021 0
95,679 6
57,555 4
0,008 3
92,135 5
37,728 5
0,000 3
0
2,949 1
Ср.р
0,303 2
0,160 2
Таблица 12
№
1
2
3
4
X
1
1
0
0
Статистические характеристики наихудших настроек
Kstest
Y
% Парето
% доп.
0
1
1
1
1
0
0
1
0
0
44
Ср.р
1
0
Вестник Сибирского государственного аэрокосмического университета имени академика М. Ф. Решетнева
J. J. Grefenstette // Proceedings of an International
Conference on Genetic Algorithms and Their Applications.
Pittsburgh : PA, 1985. P. 93–100.
5. Fonseca, C. M. Multiobjective optimization and multiple
constraint handling with evolutionary algorithms. P I. A
unified formulation. Technical report 564 / C. M. Fonseca,
P. J. Fleming ; University of Sheffield. Sheffield, 1995.
6. Horn, J. A niched Pareto genetic algorithm for
multiobjective optimization / J. Horn, N. Nafpliotis,
D. E. Goldberg // Proceedings of the First IEEE Conference
on Evolutionary Computation. Vol. 1. Piscataway, 1994.
P. 82–87.
7. Zitzler, E. Multiobjective evolutionary algorithms: A
comparative case study and the strength Pareto approach /
E. Zitzler, L. Thiele // IEEE Transactions on Evolutionary
Computation. Vol. 3. 1999. No. 4. P. 257–271.
8. Семенкин, Е. С. Модели и алгоритмы поддержки
принятия решений инвестиционного аналитика /
Е. С. Семенкин, А. В. Медведев, А. Ю. Ворожейкин //
Вестник Томск. гос. ун-та. Вып. 293. 2006. С. 63–70.
оператор скрещивания), за счет чего уменьшается время
работы алгоритма.
Все это делает ВГА перспективным для решения реальных практических задач [8].
Библиографический список
1. Goldberg, D. Genetic algorithms in search, optimization
and machine learning / D. Goldberg. Reading, MA, AddisonWesly, 1989.
2. Семенкин, Е. С. Вероятностные эволюционные алгоритмы оптимизации сложных систем / Е. С. Семенкин,
Е. А. Сопов // Труды Международных научно-практических
конференций AIS’05/CAD-2005. М. : Физматлит, 2005. С. 77–78.
3. Michalewicz, Z. Genetic algorithms, numerical
optimization and constraints / Z. Michalewicz // Proc. of the
Sixth Int. Conf. on Genetic Algorithms and their Applications.
Pittsburgh : PA, 1995.
4. Schaffer, J. D. Multiple objective optimization with
vector evaluated genetic algorithms / J. D. Schaffer ; ed. by
Таблица 13
Численные характеристики наилучших настроек
№
X
0,035 8
0,052 9
0,031 0
0,003 0
1
2
3
4
Y
0,016 9
0,033 7
0,018 1
0,002 6
Стандартный ГА
%
% доп.
0
95,800 5
26,620 0
95,446 6
32,166 2
94,515 7
0,000 0
30,162 8
Ср.р
0,181 0
0,010 3
X
0,029 6
0,049 5
0,023 4
0,001 4
Вероятностный ГА
%
% доп.
Y
0,015 8
0
94,718 0
0,030 9
26,217 5
96,308 3
0,013 1
41,749 2
90,589 3
0,001 2
0,000 0
33,045 9
Ср.р
0,281 1
0,025 5
Таблица 14
Статистические характеристики наилучших настроек
№
1
2
3
4
X
1
0
1
1
Y
1
0
1
1
% Парето
Kstest
0
1
% доп.
0
0
1
1
Ср.р
1
1
Таблица 15
Численные характеристики наихудших настроек
№
1
2
3
4
X
0,017 4
0,028 6
0,013 5
0
Y
0,012 5
0,017 8
0,007 5
0
Стандартный ГА
%
% доп.
0
24,324 1
94,383 1
16,462 3
93,382 0
9,331 5
0
0,000 0
Ср.р
0,674 2
0,356 1
X
0,022 7
0,023 4
0,010 5
0
Вероятностный ГА
Y
%
% доп.
0,011 0
0
24,526 2
0,014 8
96,308 3 18,520 8
0,005 9
92,353 9 11,043 6
0
0
0,581 6
Ср.р
0,635 0
0,250 9
Таблица 16
№
1
2
3
4
X
1
1
1
Статистические характеристики наихудших настроек
Kstest
Y
% Парето
% доп.
1
0
1
1
0
1
0
0
0
Ср.р
0
0
A. Y. Vorozheykin, E. S. Semenkin
PROBABILISTIC GENETIC ALGORITHM FOR MULTI-OBJECTIVE OPTIMIZATION
The probabilistic genetic algorithm for solving constrained multi-objective optimization problems is suggested.
Effectiveness analysis on test problems is fulfilled. It is demonstrated that probabilistic genetic algorithm outperforms
conventional genetic algorithm.
45
Документ
Категория
Без категории
Просмотров
4
Размер файла
237 Кб
Теги
алгоритм, оптимизация, вероятностный, генетический, задачи, многокритериальной
1/--страниц
Пожаловаться на содержимое документа