Генетические алгоритмы в задачах оптимизации

Манусов В.З, Павлюченко Д.А.
Новосибирский государственный технический университет, Новосибирск

Для решения сложных оптимизационных задач в электроэнергетике при большом количестве узлов и ограничений в форме неравенств применяются специальные методы. К ним относятся методы вариационного исчисления, методы математического программирования и др. Обычно область их применения ограничивается видом целевой функции. Типичная практическая задача, как правило, мультимодальна и многомерна, то есть содержит много параметров. Для проблем такого рода требуется использование эвристических и комбинаторных алгоритмов, в частности эволюционных алгоритмов, поскольку они позволяют получить лучшее решение по сравнению с классическими оптимизационными методами.

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

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

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

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

Ваши комментарии

[Головная страница] [Конференции] [СО РАН]

© 2001, Сибирское отделение Российской академии наук, Новосибирск
© 2001, Объединенный институт информатики СО РАН, Новосибирск
© 2001, Институт вычислительных технологий СО РАН, Новосибирск
© 2001, Институт систем информатики СО РАН, Новосибирск
© 2001, Институт математики СО РАН, Новосибирск
© 2001, Институт цитологии и генетики СО РАН, Новосибирск
© 2001, Институт вычислительной математики и математической геофизики СО РАН, Новосибирск
© 2001, Новосибирский государственный университет
Дата последней модификации Saturday, 01-Sep-2001 20:00:05 NOVST