ИЗВЕСТИЯ РАН. ТЕОРИЯ И СИСТЕМЫ УПРАВЛЕНИЯ, 2014, № 1, с. 114-120
КОМПЬЮТЕРНЫЕ ^^^^^^^^^^^^^^ МЕТОДЫ
УДК 004.8.023 + 621.311.22
УМНОЕ ДИСПЕТЧИРОВАНИЕ И МЕТАЭВРИСТИЧЕСКИЙ РОЕВОЙ ПОТОКОВЫЙ АЛГОРИТМ* © 2014 г. С. И. Родзин
Таганрог, Южный федеральный ун-т Поступила в редакцию 21.12.12 г., после доработки 24.06.13 г.
Целью ресурсосберегающего диспетчирования является нахождение оптимального сочетания мощности генерируемых энергоресурсов, при котором минимизируются общие затраты с учетом существующих ограничений. Предлагается метаэвристический потоковый алгоритм роевого типа. Представлены результаты сравнительного анализа эффективности алгоритма на тестовых задачах (бенчмарках). Сравнение проводилось с алгоритмом роя частиц, генетическим и биогеографическим алгоритмами на примерах системы из 6 и 20 энергоблоков. Потоковый алгоритм сходится к оптимальному решению с меньшими вычислительными затратами.
10.7868/80002338814010107
Введение. Термин "метаэвристический алгоритм" обозначает алгоритм поиска, направленный на автоматизацию процесса выбора, комбинирования, обобщения или адаптации нескольких более простых эвристик для эффективного решения вычислительной задачи. Основное преимущество метаэвристических алгоритмов заключается в построении эффективных процедур для решения целого класса проблем, а не отдельной конкретной задачи из класса. Метаэвристи-ки направлены на уменьшение количества информации из предметной области в алгоритмах. Результирующий метаэвристический алгоритм должен быть быстрым и удобным для реализации, но в то же время и достаточно надежным для решения класса задач. В [1] были выделены следующие свойства метаэвристик: они организуют процесс поиска субоптимальных решений, иногда включая достаточно сложные процедуры обучения; являются приближенными и, как правило, недетерминированными процедурами; могут использовать предметно-ориентированные знания.
Данная работа посвящена метаэвристическому потоковому алгоритму [2], применимому для решения задачи ресурсосберегающего диспетчирования, цель которого — нахождение оптимального сочетания мощности генерируемых энергоресурсов при минимизации общих затрат с учетом существующих эксплуатационных ограничений. Для решения этой задачи затруднительно использовать традиционные подходы [3]. Основными причинами трудностей являются следующие: пространство возможных решений в области поиска настолько велико, что традиционные методы не позволяют получить ответ за приемлемое время; целевая функция "зашумлена" и может меняться во времени; возможности получения допустимых решений сильно ограничены, не говоря уже о поиске оптимальных решений; лицо, принимающее решение (диспетчер), не в состоянии обнаружить оптимальное решение.
1. Постановка задачи. Диспетчирование современных систем в электроэнергетике является сложной инженерной задачей. В частности, пусть имеется система электростанций с п энергоблоками, каждый из которых генерирует мощность Щ , МВт. Энергоблоки должны быть загружены таким образом, чтобы общий расход (стоимость) топлива V был минимальным с учетом эксплуатационных ограничений. Цель ресурсосберегающего диспетчирования — нахождение оптимального сочетания мощности генерируемых энергоресурсов, при котором минимизируются общие затраты с учетом существующих ограничений. Целевая функция стандартной задачи ресурсосберегающего диспетчирования имеет вид:
* Работа выполнена при финансовой поддержке РФФИ (проект № 13-07-00204-а).
V = ^V(W) ^ min,
i = 1
где V, — расход топлива ,-го энергоблока. Как правило, расход топлива для теплогенераторов
описывается квадратичной функцией V(W) = ai + bWi + cWi , где а,, b ,, c, — некоторые коэффициенты в функции расхода топлива ,-го энергоблока [4]. Однако к функции V(W) рекомендуется добавить синусоидальную составляющую [5]:
V-(Wi) = at + bW + cWi2 + \di sin(ei(Wimin - W))|,
где d¡ и г1 — коэффициенты, отражающие это сезонное добавление, Щшш — величина минимальной выходной мощности ¡-го энергоблока.
Кроме того, необходимо учесть условия энергетического баланса и ограничения рабочих зон энергоблоков. С учетом этого общая целевая функция принимает следующий вид:
V = YViWi) + Y{Wi - W^ - потери} +Yхк,
I = 1 I = 1 I = 1
где ^ и Х2 — положительные константы (штрафы), связанные с нарушением условия баланса или ограничений для рабочих зон энергоблоков соответственно; Щптз — полная требуемая загрузка
энергоблока, №^отери — общие потери при передаче электроэнергии по сетям, а переменная хк является булевской и равна:
к (1, если ограничения нарушены для Ж,,
X] Н
[0 в противном случае.
Если условия баланса и ограничения выполняются, то ^ = Х2 = 0. Для рассматриваемой задачи начальная установка этих констант определяется эмпирически: 1, Х2 = 5п. Ограничения в задаче определяются следующим образом [4]. 1. Условие баланса
ZW- = W + W
'r t 'г п.т.з + '' И(
i = 1
причем расчет Щпотери производится с помощью симметричной матрицы коэффициентов потерь Ь порядка (п х п):
п п п
ЖПотери = ^^ЖЖ] + £ Ж + ¡О,
I = 1 ] = 1 I = 1
где ¡у — элемент матрицы потерь Ь, ¡^ — ¡-й элемент п-мерного вектора I коэффициентов потерь, ¡0 — коэффициент постоянных потерь.
2. Ограничения на мощность, генерируемую ¡-м энергоблоком,
Ж;т'П < < Ж;ШаХ,
где Ж и Ж — соответственно величины минимальной и максимальной выходной мощности ¡-го энергоблока.
3. Ограничения на рабочие зоны энергоблоков Щ:
W
Wmin < W < Wn,
WU-1 < W < wlk, к = 2, m,,,
w,um. < w < wmax,
где Wik и W"k — нижняя и верхняя границы запрещенных зон W энергоблока, m, — число рабочих зон.
n
n
При таких условиях и ограничениях традиционные методы математического программирования (Лагранжа, динамического или нелинейного программирования, градиента) не в состоянии обеспечить быстрый поиск глобально оптимального решения, так как "застревают" в локальном оптимуме. В связи с этим исследователи обращают внимание на современные эвристические методы оптимизации, такие как моделирование отжига [6], нейронные сети [7], роя частиц [8], та-буированного поиска [9], генетические алгоритмы [10], алгоритмы генетического программирования [11], эволюционные стратегии [12] и эволюционное программирование [13], которые способны достаточно быстро находить решения, близкие к глобальному оптимуму.
Большинство из перечисленных выше методов относятся к разновидностям так называемых метаэвристических эволюционных вычислений — математических преобразований, трансформирующих входной поток информации в выходной и основанных на правилах имитации механизмов, инспирированных природными системами, а также на статистическом подходе к исследованию ситуаций и итерационном приближении к искомому решению. Их применение не требует углубленного математического знания проблемы, они не гарантируют получение оптимального решения, однако способны быстро найти локально оптимальное решение.
2. Отличительные особенности метаэвристического потокового алгоритма оптимизации. Оптимизационные задачи весьма разнообразны: одномерные и многомерные, непрерывные и дискретные, линейного, квадратичного и нелинейного программирования, полиномиальные, NP-полные и экспоненциальной сложности, выпуклые и вогнутые, одно- и многомодальные. Математически задача нахождения оптимального решения определяется как процесс поиска такой комбинации переменных задачи, называемых решением, которая минимизирует или максимизирует целевую функцию задачи при выполнении некоторого набора ограничений.
Малоподходящими для решения поставленной задачи являются традиционные подходы к решению оптимизационных задач, такие как метод Ньютона, градиентные методы, симплекс-метод, методы Нелдера—Мида, Хука—Дживса и др.
Для метаэвристических алгоритмов справедлива No Free Lunch (NFL) теорема Вольперта— Макрида [14], согласно которой все метаэвристические алгоритмы "в среднем" (по всевозможным целевым функциям) являются идентичными, т.е. для всех алгоритмов, ищущих экстремум целевой функции, производительность их одинакова, если усреднить результаты по всевозможным целевым функциям. Теорема устанавливает, что в любом возможном ландшафте целевой функции лучшей стратегией будет хаотичное движение. Чтобы выработать более перспективную стратегию поиска оптимума, необходимо иметь некоторую информацию о характере исследуемого ландшафта. Метаэвристический алгоритм, хорошо зарекомендовавший себя для некоторого класса задач, может потерпеть неудачу для другого класса задач с другими целевыми функциями. Иными словами, без использования каких-либо знаний о свойствах целевой функции никакой алгоритм, в общем случае, не может быть эффективнее, чем алгоритм случайного поиска. Именно это блестяще показали своей теоремой Вольперт и Макрид. Согласно следствию теоремы, единственным способом сокращения времени и повышения качества метаэвристического поиска является специализация схемы поиска. Как правило, она выражается в настройке основных параметров алгоритма под конкретный класс целевых функций, что означает для каждой специфической области необходимость проводить исследования и отыскивать тот алгоритм, который подходит ей более всего.
Предлагаемый потоковый алгоритм относится к роевым алгоритмам, инспирированным природными системами и процессами [15]. Путь воды в реке от истока до устья является оптимальным или близким к нему. Идея потокового алгоритма состоит в том, что капли воды, объединившись в поток, находят русло из самых низких точек почвы. Алгоритм характеризуется двумя важными свойствами:
площадь Р потока воды;
скорость s, с которой движется водный поток в данный момент времени.
Обычно существует много путей от источника до цели. Пункт назначения может быть как известным, так и неизвестным. Если мы знаем, где находится пункт назначения, то зачастую лучшим является кратчайший путь от источника к месту назначения. Если координаты пункта назначения неизвестны, то оптимальное решение ищется с учетом затрат или некоторых других характеристик задачи.
Моделирование движения потока воды в алгоритме осуществляется дискретными шагами. Скорость движения воды от текущего мест
Для дальнейшего прочтения статьи необходимо приобрести полный текст. Статьи высылаются в формате PDF на указанную при оплате почту. Время доставки составляет менее 10 минут. Стоимость одной статьи — 150 рублей.