Авторитетность издания
Добавить в закладки
Следующий номер на сайте
Исследование дифференцированного адаптивного генетического алгоритма решения задач условной оптимизации
Аннотация:Рассмотрены стандартные методы решения задач условной оптимизации на основе искусственного ухудшения значения целевой функции при нарушении заданных ограничений, а именно методов назначения динамических и адаптивных штрафов. Дано описание модификации селекции в дифференцированном адаптивном генетическом алгоритме на базе метода поведенческой памяти для его адаптации к данному классу задач. Приводятся результаты ис-следования эффективности решения задач условной оптимизации дифференцированным адаптивным генетическим алгоритмом в сочетании со стандартными методами учета ограничений на тестовом множестве функций. По результатам исследования делается вывод о том, что наибольшую эффективность показывает комбинация динамического штрафа и модификации алгоритма, выраженной в переходе в подмножество S k только тех решений, которые удовлетворяют заданным критериям. Это также обусловливает низкую эффективность применения метода адаптивных штрафов в сочетании с дифференцированным адаптивным генетическим алгоритмом. По результатам сравнительно-го анализа эффективности делается вывод о том, что дифференцированный адаптивный генетический алгоритм лучше усредненного по эффективности классического генетического алгоритма, но может уступать лучшему при неоптимальных настройках, а также сравним с коэволюционным алгоритмом, что позволяет применять его при решении практических задач оптимизации.
Abstract:The article discusses standard methods for solving constrained optimization problems based on artificial dete-rioration of the objective function value when violating given constraints. The methods of assigning dynamic and adaptive penalties are described. The paper considers selection modifications in a differential adaptive genetic algorithm based on the behavioral memory method for adapting it to this class of problems. The paper presents the results of study a combination of standard methods and observable differential algorithm on a test functions set that show the most efficient combination of dynamic penalty and algorithm modification. The algorithm modification is presented in the possibility of a transition to S k subset only solutions that satisfy all the constraints. Allocation of two subsets determines low efficiency of adaptive penalties due to inability to obtain complete information on the entire set of decisions and frequent changes in S o subset. Based on a comparison of the data and test results of other genetic algorithms, it is concluded that the differential algorithm is better av-eraged performance of the classical algorithm, but can yield better at non-optimal settings, as well as comparable to the co-evolutionary algorithm. This allows using differentiated adaptive genetic algorithm to solve practical optimization problems.
Авторы: Жуков В.Г. (vadimzhukov@mail.ru) - Сибирский государственный аэрокосмический университет им. академика М.Ф. Решетнева, г. Красноярск (доцент), Красноярск, Россия, кандидат технических наук, Паротькин Н.Ю. (U-571_sos@mail.ru) - Сибирский государственный аэрокосмический университет им. академика М.Ф. Решетнева, г. Красноярск, Красноярск, Россия, Аспирант | |
Ключевые слова: поведенческая память, штрафные функции, дифференцированный адаптивный генетический алгоритм, условная оптимизация |
|
Keywords: behavioral memory, penalty functions, differentiated adaptive genetic algorithm, constrained optimization |
|
Количество просмотров: 8010 |
Версия для печати Выпуск в формате PDF (7.83Мб) Скачать обложку в формате PDF (1.01Мб) |
При решении практических задач нахождения оптимальных параметров какого-либо процесса или настроек системы требуется соблюдение ряда ограничений, накладываемых на диапазоны их изменения, обусловленные физической природой объекта или экономическими требованиями. Кроме того, зачастую нельзя с достаточной точностью описать реальную систему без использования алгоритмических выражений, что приводит к невозможности ее оптимизации только математическими методами. Одним из способов решения таких задач, относящихся к задачам условной оптимизации, является аппарат эволюционных алгоритмов, в частности генетические алгоритмы (ГА). Для этого к ним применяется ряд методов, воздействующих как на итоговое значение целевой функции, отражающей качество найденного решения, так и на состав множества решений, которыми оперирует ГА. Следовательно, разработка новых, более эффективных методов учета ограничений в эволюционных алгоритмах и решения задач условной оптимизации является актуальной для научных и технических исследований. Методы решения задач условной оптимизации Рассмотрим два метода назначения штрафов целевой функции, уменьшающих пригодность найденного вектора решений при нарушении заданных ограничений. Пусть решается задача условной оптимизации:
где f(x) – целевая функция; gj(x)£0, hj(x)=0 – ограничения задачи; m – общее количество ограничений. Тогда итоговая пригодность индивида x может быть вычислена по формуле
где t – номер текущего поколения; d=1, если решается задача минимизации; d= –1, если решается задача максимизации; fj(x) – штраф за нарушение j-го ограничения; β – вещественное число. В методе динамических штрафов [1] вычисление значения fj(x) происходит динамически, в зависимости от степени нарушения ограничений, по формуле для t-й итерации, а значение l(t)=(C×t)a:
Рекомендуемые значения параметров C=0,5, a=b=2 могут изменяться в зависимости от зада- чи и влияют на эффективность нахождения решения [2]. Развитием данного метода является метод адаптивных штрафов [1, 2], в котором λ(t) зависит не только от номера итерации, но и от количества попаданий лучшего представителя популяции на каждом шаге в допустимую или недопустимую область:
где В данном методе происходит уменьшение штрафа на следующем шаге, если лучший индивид популяции (в терминах функции пригодности) на протяжении последних k итераций принадлежал допустимой области. Если же лучший индивид популяции в течение того же промежутка времени выходил за границы допустимой области, происходит увеличение штрафа. Описанные методы универсальны и подходят для применения в любом ГА без его существенной модификации. Кроме данного вида методов, воздействующих непосредственно на итоговое значение целевой функции, существует ряд механизмов, влияющих на структуру и порядок работы самого алгоритма для повышения его эффективности при решении задач условной оптимизации [2–4]. Одним из них является метод поведенческой памяти [5]. Суть его в последовательном увеличении количества критериев, которым будет удовлетворять заданная часть популяции, при итеративной работе генетических операторов поиска. Модификации дифференцированного адаптивного ГА для решения задач условной оптимизации Поскольку решение задач условной однокритериальной оптимизации является более трудоемким, чем однокритериальных безусловных задач, целесообразно использовать эволюционные алгоритмы, обладающие большей эффективностью, чем классический ГА. В работе [6] предлагается новый метод взаимодействия с пространством поиска и способом накопления информации о решении задачи. На его основе разработан дифференцированный адаптивный ГА (ДАГА), обобщенная схема которого представлена на рисунке. Перед описанием предлагаемых модификаций ДАГА для решения задач условной оптимизации приведем его алгоритм, используемый при решении однокритериальных безусловных задач оптимизации. На первом этапе общая популяция решений делится на две субпопуляции в отношении Sk/So, определяемом пользователем. Задачей Sk-субпопуляции является накопление хороших, апробированных в процессе работы алгоритма решений, а So – активное исследование поискового пространства и тестирование качества найденных решений. Вводится параметр Tlife, определяющий количество раундов алгоритма, в которых индивид содержался в популяции в неизменном состоянии. В изначальной случайно сгенерированной популяции выделяются N/Sk лучших индивидов, формирующих Sk-субпопуляцию, остальные переходят в So. В каждом раунде алгоритма По завершении процедуры формирования потомков изменяется соотношение количества индивидов Sk/So по периодическому закону. Далее осуществляется поиск индивидов для сохранения их генетической информации в Sk нового поколения. Для этого просматриваем всех индивидов При применении рассмотренных выше методов условной оптимизации к ДАГА были получены два способа его модификаций. Первый способ предусматривает использование классических схем статических, динамических или адаптивных штрафов. В этом случае к вычисленному значению целевой функции добавляется некоторая величина, соответствующая степени нарушения заданных ограничений текущим вектором решений. При таком подходе не требуется доработка самого алгоритма оптимизации и эффективность решения задачи условной оптимизации сводится к выбору правильных коэффициентов штрафных функций. Второй способ предполагает внесение изменений в сам алгоритм оптимизации. Поскольку в ДАГА применяется разделение на две субпопуляции, переход между которыми возможен при доказанной в течение нескольких поколений успешности найденного решения, к нему может быть применена идея, заложенная в методе поведенческой памяти [5]. А именно, в субпопуляцию Sk индивиды будут отбираться по следующим параметрам: удовлетворение наибольшему количеству критериев, наибольшее значение параметра Tlife. В то же время к субпопуляции So для формирования значений целевых функций могут применяться рассмотренные штрафные функции. Исследование эффективности ГА решения задач условной оптимизации
При проведении исследований были определены следующие начальные условия и параметры алгоритма: для метода динамических и адаптивных штрафов коэффициенты С=0,5, α=β=2, коэффициенты для адаптивных штрафов: β1=1,4, β2=1,2, k=3. Использовалась генерация начальных популяций множеством допустимых решений. Общее количество индивидов в субпопуляциях Sk и So составляло 100, количество поколений также равнялось 100, использовалось одноточечное и двухточечное скрещивание. Проводилось исследование штрафных функций отдельно и в сочетании их с модификацией алгоритма.
Проведем сравнение эффективности ДАГА с результатами исследований из [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 Genetic 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-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. 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 nechetkikh 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.). |
Постоянный адрес статьи: http://swsys.ru/index.php?id=3763&page=article |
Версия для печати Выпуск в формате PDF (7.83Мб) Скачать обложку в формате PDF (1.01Мб) |
Статья опубликована в выпуске журнала № 1 за 2014 год. [ на стр. 82-86 ] |
Возможно, Вас заинтересуют следующие статьи схожих тематик: