Software & Systems

При решении практических задач нахождения оптимальных параметров какого-либо процесса или настроек системы требуется соблюдение ряда ограничений, накладываемых на диапазоны их изменения, обусловленные физической природой объекта или экономическими требованиями. Кроме того, зачастую нельзя с достаточной точностью описать реальную систему без использования алгоритмических выражений, что приводит к невозможности ее оптимизации только математическими методами. Одним из способов решения таких задач, относящихся к задачам условной оптимизации, является аппарат эволюционных алгоритмов, в частности генетические алгоритмы (ГА). Для этого к ним применяется ряд методов, воздействующих как на итоговое значение целевой функции, отражающей качество найденного решения, так и на состав множества решений, которыми оперирует ГА. Следовательно, разработка новых, более эффективных методов учета ограничений в эволюционных алгоритмах и решения задач условной оптимизации является актуальной для научных и технических исследований.

Методы решения задач условной оптимизации

Рассмотрим два метода назначения штрафов целевой функции, уменьшающих пригодность найденного вектора решений при нарушении заданных ограничений. Пусть решается задача условной оптимизации:

                                         (1)

где f(x) – целевая функция; gj(x)£0, hj(x)=0 – ограничения задачи; m – общее количество ограничений. Тогда итоговая пригодность индивида x может быть вычислена по формуле

,               (2)

где t – номер текущего поколения; d=1, если решается задача минимизации; d= –1, если решается задача максимизации; fj(x) – штраф за нарушение j-го ограничения; β – вещественное число.

В методе динамических штрафов [1] вычисление значения fj(x) происходит динамически, в зависимости от степени нарушения ограничений, по формуле для t-й итерации, а значение l(t)=(C×t)a:

                        (3)

Рекомендуемые значения параметров C=0,5, a=b=2 могут изменяться в зависимости от зада- чи и влияют на эффективность нахождения решения [2].

Развитием данного метода является метод адаптивных штрафов [1, 2], в котором λ(t) зависит не только от номера итерации, но и от количества попаданий лучшего представителя популяции на каждом шаге в допустимую или недопустимую область:

         (4)

где  – лучший индивид i-й популяции; b1, b2>1 и b1¹b2.

В данном методе происходит уменьшение штрафа на следующем шаге, если лучший индивид популяции (в терминах функции пригодности) на протяжении последних k итераций принадлежал допустимой области. Если же лучший индивид популяции в течение того же промежутка времени выходил за границы допустимой области, происходит увеличение штрафа.

Описанные методы универсальны и подходят для применения в любом ГА без его существенной модификации. Кроме данного вида методов, воздействующих непосредственно на итоговое значение целевой функции, существует ряд механизмов, влияющих на структуру и порядок работы самого алгоритма для повышения его эффективности при решении задач условной оптимизации [2–4]. Одним из них является метод поведенческой памяти [5]. Суть его в последовательном увеличении количества критериев, которым будет удовлетворять заданная часть популяции, при итеративной работе генетических операторов поиска.

Модификации дифференцированного адаптивного ГА для решения задач условной оптимизации

Поскольку решение задач условной однокритериальной оптимизации является более трудоемким, чем однокритериальных безусловных задач, целесообразно использовать эволюционные алгоритмы, обладающие большей эффективностью, чем классический ГА. В работе [6] предлагается новый метод взаимодействия с пространством поиска и способом накопления информации о решении задачи. На его основе разработан дифференцированный адаптивный ГА (ДАГА), обобщенная схема которого представлена на рисунке.

Перед описанием предлагаемых модификаций ДАГА для решения задач условной оптимизации приведем его алгоритм, используемый при решении однокритериальных безусловных задач оптимизации. На первом этапе общая популяция решений делится на две субпопуляции в отношении Sk/So, определяемом пользователем. Задачей Sk-субпопуляции является накопление хороших, апробированных в процессе работы алгоритма решений, а So – активное исследование поискового пространства и тестирование качества найденных решений. Вводится параметр Tlife, определяющий количество раундов алгоритма, в которых индивид содержался в популяции в неизменном состоянии. В изначальной случайно сгенерированной популяции выделяются N/Sk лучших индивидов, формирующих Sk-субпопуляцию, остальные переходят в So. В каждом раунде алгоритма  раз формируется потомок в So. Для этого случайно выбирается -индивид из Sk. Второй -индивид выбирается по турнирной схеме из So, то есть формируется выборка из n индивидов, среди которых выбирается один индивид с наилучшим значением целевой функции. При ее равных значениях – с наибольшим значением Tlife. После определения пары  формируется потомок путем скрещивания хромосом и применения оператора мутации. Далее происходит сравнение по значению по целевой функции потомка и . Если потомок лучше, то он замещает , а его параметр Tlife обнуляется. Если лучше , то потомок отбрасывается, а Tlife  увеличивается на 1.

По завершении процедуры формирования потомков изменяется соотношение количества индивидов Sk/So по периодическому закону. Далее осуществляется поиск индивидов для сохранения их генетической информации в Sk нового поколения. Для этого просматриваем всех индивидов  и отбираем тех, у которых время жизни больше значения параметра Tlife, установленного пользователем, и наихудшее значение целевой функции. После этого сравниваем значение пригодности найденного -индивида со значением -индивида. Если у -индивида лучшее значение, заменяем им -индивида, при этом обнуляем у него Tlife. После проверки всех -индивидов увеличиваем время жизни у всех -индивидов на 1. При недостатке индивидов в Sk они добавляются из So только по критерию пригодности.

При применении рассмотренных выше методов условной оптимизации к ДАГА были получены два способа его модификаций.

Первый способ предусматривает использование классических схем статических, динамических или адаптивных штрафов. В этом случае к вычисленному значению целевой функции добавляется некоторая величина, соответствующая степени нарушения заданных ограничений текущим вектором решений. При таком подходе не требуется доработка самого алгоритма оптимизации и эффективность решения задачи условной оптимизации сводится к выбору правильных коэффициентов штрафных функций.

Второй способ предполагает внесение изменений в сам алгоритм оптимизации. Поскольку в ДАГА применяется разделение на две субпопуляции, переход между которыми возможен при доказанной в течение нескольких поколений успешности найденного решения, к нему может быть применена идея, заложенная в методе поведенческой памяти [5]. А именно, в субпопуляцию Sk индивиды будут отбираться по следующим параметрам: удовлетворение наибольшему количеству критериев, наибольшее значение параметра Tlife.

В то же время к субпопуляции So для формирования значений целевых функций могут применяться рассмотренные штрафные функции.

Исследование эффективности ГА решения задач условной оптимизации

Внесенные модификации были проверены на тестовых функциях (табл. 1), для которых ин- тервал изменения значений переменных равен [–10, 10], а шаг дискретизации – 0,001.

При проведении исследований были определены следующие начальные условия и параметры алгоритма: для метода динамических и адаптивных штрафов коэффициенты С=0,5, α=β=2, коэффициенты для адаптивных штрафов: β1=1,4, β2=1,2, k=3. Использовалась генерация начальных популяций множеством допустимых решений. Общее количество индивидов в субпопуляциях Sk и So составляло 100, количество поколений также равнялось 100, использовалось одноточечное и двухточечное скрещивание. Проводилось исследование штраф­ных функций отдельно и в сочетании их с модификацией алгоритма.

Оценка эффективности алгоритма производилась по параметрам надежности и скорости поиска решений. Под надежностью понимается доля запусков из 100, при которых был найден глобальный оптимум функции на интервале, удовлетворяющий заданным ограничениям. Скорость определяется как усредненный номер поколения, на котором был найден глобальный оптимум. Результаты исследования эффективности ДАГА при решении однокритериальных задач условной оптимизации на множестве тестовых функций (табл. 1) приведены в таблице 2.

Проведем сравнение эффективности ДАГА с результатами исследований из [7] (табл. 3), которые были получены при тех же параметрах тестирования алгоритмов и для тех же функций.

По полученным результатам и их сравнительному анализу с [7] можно сделать следующие выводы:

–      для ДАГА наибольшую эффективность показывает сочетание метода динамического штрафа и модификации алгоритма; сниженная эффективность адаптивных штрафов связана с наличием двух субпопуляций и частого изменения состава подмножества So;

–      при сравнении с классическим ГА можно заключить, что ДАГА лучше усредненного по эффективности классического алгоритма, но может уступать лучшему при неоптимальных настройках;

–      при сравнении с коэволюционным алгоритмом, являющимся также развитием классического ГА, можно сказать, что данные алгоритмы сравнимы по эффективности.

Таким образом, в работе предложен и обоснован новый подход к решению задачи условной оптимизации, основная идея которого заключается в дифференциации и специализации субпопуляций, с целью повышения эффективности (устойчивости) ГА как эволюционирующей системы. Разработанный алгоритм по эффективности решения задачи условной оптимизации на множестве тестовых данных превосходит классический ГА и сопоставим с коэволюционным алгоритмом.

Литература

1.     Michalewicz Z., Schoenauer M. Evolutionary algorithms for constrained parameter optimization problems. Evolutionary Computation, no. 4 (1), 1996, pp. 1–32.

2.      Mezura-Montes E., Coello Coello C.A. Constraint-handling in nature-inspired numerical optimization: Past, present and future. Swarm and Evolutionary Computation. 2011, vol. 1, no. 4, pp. 173–194.

3.     Yeniay Ö. Penalty function methods for constrained  optimization with genetic algorithms. Mathematical and Computational Applications. 2005, vol. 10, no. 1, pp. 45–56.

4.     Can M., Kusakci O.A. Constrained optimization with evolutionary algorithms: a comprehensive review. Southeast Europe journal of soft computing. 2012, vol. 1, no. 2, pp. 16–24.

5.     Schoenauer M., Xanthakis S. Proc. 5th Int. Conf. on Gene­tic Algorithms, Urbana-Champaign, IL, USA, 1993, pp. 473–580.

6.     Жуков В.Г., Паротькин Н.Ю. Дифференцированный адаптивный генетический алгоритм // Вестн. НГУ: сер. Информационные технологии. Новосибирск, 2011. Т. 9. Вып. 1. С. 5–11.

7.     Сергиенко Р.Б. Автоматизированное формирование нечетких классификаторов самонастраивающимися коэволюционными алгоритмами: автореф. дис. … канд. техн. наук. Красноярск: СФУ, 2010. 20 с.

References

1.     Michalewicz Z., Schoenauer M. Evolutionary algorithms for constrained parameter optimization problems. Evolutionary Computation, 1996, no. 4 (1), pp. 1–32.

2.      Mezura-Montes E., Coello Coello C.A. Constraint-hand­ling in nature-inspired numerical optimization: Past, present and future. Swarm and Evolutionary Computation. 2011, vol. 1, no. 4, pp. 173–194.

3.     Yeniay Ö. Penalty function methods for constrained  optimization with genetic algorithms. Mathematical and Computational Applications. 2005, vol. 10, no. 1, pp. 45–56.

4.     Can M., Kusakci O.A. Constrained optimization with evolutionary algorithms: a comprehensive review. Southeast Europe journal of soft computing. 2012, vol. 1, no. 2, pp. 16–24.

5.     Schoenauer M., Xanthakis S. Constrained GA optimization. Proc. of the 5th Int. Conf. on Genetic Algorithms. Urbana-Champaign, IL, USA, 1993, pp. 473–580.

6.     Zhukov V.G., Parotkin N.Yu. A differential adaptive genetic algorithm. Vestnik NGU [Bulletin of the Novosibirsk State Univ.]. Novosibirsk, 2011, vol. 9, iss. 1, pp. 5–11 (in Russ.).

7.     Sergienko R.B. Avtomatizirovannoe formirovanie nechet­kikh klassifikatorov samonastraivayushchimisya koevolyutsionnymi algoritmami [Automated forming of fuzzy classificators by self-adjusting coevolution algorithms]. Extended abstract of PhD diss. (Engineering), Siberian Fed. Univ. Publ., Krasnoyarsk, 2010, 20 p. (in Russ.).