Другие журналы
|
научное издание МГТУ им. Н.Э. БауманаНАУКА и ОБРАЗОВАНИЕИздатель ФГБОУ ВПО "МГТУ им. Н.Э. Баумана". Эл № ФС 77 - 48211. ISSN 1994-0408![]()
Глобальная оптимизация методом биогеографии
# 10, октябрь 2013 DOI: 10.7463/1013.0605836
Файл статьи:
![]() Россия, МГТУ им. Н.Э. Баумана ООО МТЦ «САУРУС-ЭНЕРГО»
Биогеографию определяют как науку на стыке биологии и географии, которая изучает закономерности географического распространения и распределения животных, растений и микроорганизмов. Математическая теория биогеографии начала развиваться в 60-е годы прошлого века с фундаментальной работы Роберта МакАртура (RobertMacArthur) и Эдварда Вилсона (EdwardWilson) «Теория островной биогеографии» [1]. Здесь под островом (island) понимается среда обитания, географически изолированная от других сред. Качество острова с точки зрения его пригодности для обитания видов определяет индекс пригодности (Habitat Suitability Index, HSI). Значения этого индекса полагают зависящими от набора параметров острова (SuitabilityIndexVariables, SIVs), примерами которых являются температура, влажность, разнообразие растительности и т.д. Острова, обладающие более высоким индексом пригодности, имеют большое число населяющих их видов. Для таких островов характерно, во-первых, большое число индивидов, которые эмигрируют на соседние острова. Во-вторых, в силу насыщенности этих островов видами, они имеют низкий уровень иммиграции. Напротив, системы с малыми значениями HSI имеют, как правило, небольшое число видов. Для этих островов характерным является низкий уровень эмиграции и высокий уровень иммиграции. Важно, что процесс иммиграции на «бедные» острова может повысить пригодность этих островов (поскольку пригодность острова пропорциональна разнообразию ее форм жизни). Если пригодность острова остается низкой, то проживающие на этом острове виды приобретают тенденцию к исчезновению, которая, однако, далее открывает путь к дополнительной иммиграции с «богатых» островов. Таким образом, острова с низкой пригодностью оказываются более динамичными с точки зрения числа населяющих их видов, чем острова, имеющие высокую пригодность. Модели биогеографии могут быть использованы и используются для решения задач оптимизации на основе следующей аналогии. Полагаем, что значение целевой функции есть индекс пригодности соответствующего острова-решения. Хорошее решение отождествляем с островом, имеющим высокий индекс пригодности, а плохое – наоборот, с островом с низким значением этого индекса. Хорошие решения подвержены изменениям в гораздо меньшей степени, чем плохие. К тому же хорошие решения могут использовать плохие решения для повышения своего качества. Аналогично, плохие решения могут повышать свое качество с использованием хороших решений. Указанный подход к решению задачи оптимизации с использованием модели биогеографии называют BBO (Biogeography-BasedOptimization). BBOотносится к классу методов, вдохновленных природой, к которым принадлежат также такие широко известные методы, как генетический, роя частиц (PSO) [2], муравьиной колонии (ACO) [3], пчел (BCO) [4] и большое число других методов [5]. Работа преследует три цели. Во-первых, поскольку нам незнакомы публикации на русском языке по методу BBO, представить русскоязычному читателю этот новый метод глобальной оптимизации. Во-вторых, показать эффективность метода на одной из классических тестовых задач глобальной непрерывной многомерной оптимизации. В-третьих, исследовать эффективность метода при решении актуальной практической задачи об оптимальном размещении устройств регулирования напряжения в электроэнергетической сети. В первом разделе представляем элементы теории биогеографии, используемые в дальнейшем изложении. Во втором разделе приводим постановку задачи глобальной непрерывной оптимизации и даем схему метода BBO. Третий раздел посвящен исследованию эффективности метода на одной из трудных тестовых задач глобальной оптимизации. В четвертом разделе рассматриваем решение задачи об оптимальном размещении устройств регулирования напряжения в электрической сети. В Заключении формулируем основные результаты работы и перспективы ее развития.
1. Элементы теории биогеографии Элементы теории биогеографии представляем, следуя публикации [6]. Простейшую модель распространения видов на одном из островов иллюстрирует рисунок 1, показывающий уровни иммиграции Рисунок 1 показывает, что максимум иммиграции Для эмиграции имеет место противоположная тенденция. При нулевом числе видов острова эмиграция равна, очевидно, нулю. С увеличением числа видов вследствие переполненности острова большее число видов получает стимулы для того, чтобы покинуть этот остров и исследовать другие острова. Эмиграция достигает максимального значения, равного Равенство уровней иммиграции и эмиграции достигается при некотором числе видов В действительности зависимости уровней иммиграции и эмиграции от числа видов, конечно, не являются линейными. Однако канонический метод BBOиспользует рассмотренные линейные модели.
Рисунок 1 – Простейшая модель распространения видов на острове:
Обозначим
Справедливость выражения вытекает из того факта, что для получения 1) в момент времени 2) в момент времени 3) в момент времени В пределе при
В векторной форме эта система приобретает классический для теории биогеографии вид
где
Для линейной модели распространения видов, представленной на рисунке 1, уровни иммиграции и эмиграции определяют, соответственно, выражения
Ограничимся случаем, когда максимальные уровни эмиграции и иммиграции равны, то есть когда
и матрица
Известно [6], что установившееся решение системы ОДУ (2) при ее любых допустимых начальных условиях определяет формула
где
Здесь В работе [6] показано, что в соответствие с уравнением (2) в установившемся состоянии острова, как с низким, так и с высоким числом видов имеют относительно низкую вероятность изменения этого числа. Напротив, острова, имеющие среднее число видов, подвержены изменениям своей численности видов с высокой вероятностью. Из выражения (8) вытекает, что сумма элементов вектора
2. Простановка задачи и схема метода биогеографии Рассматриваем задачу целочисленной глобальной условной оптимизации
где
Введем следующие обозначения [6].
Рисунок 2 – Псевдокод оператора
Заметим, что приведенное определение оператора
Рисунок 3 – Псевдокод оператора
Из приведенного определения оператора мутации следует, что он не нарушает ограничений на SIVs.
где Во введенных обозначениях алгоритм биогеографии определяет триплет Полагаем размер Общая схема метода BBO имеет следующий вид. 1) Представляем задачу оптимизации в терминах остров и их SIVsи HSI. Инициализируем максимальное число островов 2) С помощью оператора 3) В соответствие с функцией перехода экосистемы 4) С помощью оператора модификации 5) Обновляем для каждого из островов вероятность соответствующего числа видов и с этой вероятностью применяем к каждому из неэлитных островов оператор мутации 6) Проверяем выполнение условия окончания итераций После шагов 2, 4, 5 проверяем допустимость полученных решений. Недопустимые решения соответствующим образом изменяем. Поясним схемы операторов модификации Оператор модификации Заметим, что, например, в отличие от генетического алгоритма и алгоритма эволюционных стратегий, в методе BBO миграция не создает новых решений, но лишь адаптивно модифицирует их [7]. Оператор мутации
где
3. Исследование эффективности метода биогеографии Метод биогеографии реализован нами в программной системе Matlab [8]. Метод реализован для непрерывной задачи глобальной безусловной оптимизации. Исследование эффективности метода выполнено на известной тестовой функции Растригина
которая имеет один глобальный минимум, в котором значение функции равно нулю. Если не оговорено противное, исследование выполнено при следующих значениях свободных параметров метода: ‑ размер экосистемы ‑ вероятность модификации острова ‑ коэффициент мутации ‑ параметр элитизма В качестве условия окончания итераций используем стагнацию вычислений в течение Используем следующие критерии, определяющие эффективность метода: · · · · · Некоторые результаты исследования представлены в таблицах 1, 2.
Таблица 4.1. Эффективность алгоритма:
Таблица 4.2. Эффективность алгоритма:
Результаты таблицы 4.1 иллюстрируют рисунки 4 – 8, а таблицы 4.2 ‑ рисунки 9 – 12.
Рисунок 4 − Оценка вероятности локализации глобального минимума
Из рисунка 4 видно, что с увеличением значения коэффициента мутации
Рисунок 5 − Среднее достигнутое значение фитнесс
Рисунок 5 показывает наличие четкого минимума в зависимости
Рисунок 6 − Среднеквадратическое отклонение
Из рисунка 6 вытекает, что по критерию минимума среднеквадратического отклонения
Рисунок 7 − Среднее число итераций
Рисунок 7 иллюстрирует тот факт, что зависимость среднего числа итераций
Рисунок 8 − Среднее число испытаний
Характер зависимости среднего числа испытаний Рисунки 9 – 12 соответствуют высокой размерности вектора варьируемых параметров функции Растригина (
Рисунок 9 − Вероятности локализации глобального минимума
Рисунок 10 − Среднее достигнутое значение фитнесс
Рисунок 11 − Среднеквадратичное отклонение
Рисунок 12 − Средне число итераций
Из рисунков 9 – 12 следует, что при высокой размерности вектора варьируемых параметров Результаты сравнения эффективности метода BBOс эффективностью значительного числа эволюционных и популяционных методов на широком классе тестовых задач глобальной оптимизации представлены в работе [6].
4. Оптимизация размещения компенсаторов реактивной мощности в электросетях Вследствие интенсификации и усложнения технологических процессов на современных производствах, в настоящее время все большую долю в общем объеме суммарных электрических нагрузок занимают нагрузки с повышенным потреблением реактивной мощности. Такие нагрузки оказывают отрицательное влияние на качество электроэнергии питающих сетей. С другой стороны, нормальная работа электрооборудования зависит от качества электроэнергии этих сетей. Взаимовлияние электрооборудования и питающей электрической сети называют их электромагнитной совместимостью. Основным средством обеспечения электромагнитной совместимости электрооборудования и питающей сети является компенсация реактивной мощности в этой сети. Проблема компенсации реактивной мощности включает в себя задачи выбора целесообразных компенсирующих источников реактивной мощности (компенсаторов), определение требуемой мощности этих источников, а также их размещение в системе электроснабжения. Решение проблемы компенсации реактивной мощности позволяет существенно снизить потери мощности в сетях [9]. В последние годы опубликовано значительное число работ, посвященных исследованию эффективности решения задачи об оптимальном размещении компенсаторов [10]. Использование метода BBOдля решения этой задачи предложено в 2009 году [11] (см. также работы [12, 13]). 5.1. Постановка задачи. Активную и реактивную мощности электрического потока из соответственно. Здесь Изменение реактивной мощности на
где Рассматриваем компенсаторы двух типов ‑ конденсаторная батарея и шунтирующий реактор (индуктивность). Полагаем заданными величины
Введем в рассмотрение Ставится задача найти типы, мощности и места расположения компенсаторов, которые обеспечивают минимум суммарных потерь мощности электрической сети
Здесь Поскольку допустимы только целочисленные значения компонентов При заданных значениях компонентов вектора Общую структуру используемого программного обеспечения иллюстрирует рисунок 13.
Рисунок 13 – Структура программного обеспечения 5.2. Оптимизация электросети IEEE 9[16] Схема электросети IEEE 9 в интерфейсе системы PowerFactory представлена на рисунках 14, 15.
Рисунок 14 − Схема девятишинной электрической сетиIEEE 9: интерфейс системы PowerFactory
а) б) в) г) д)
Рисунок 15 – Условные обозначения: а) генератор; б) шина; в) линия электропередач; г) нагрузка; д) трансформатор
На реактивную мощность компенсаторов и их число накладываем ограничения, определяемые следующими равенствами:
Поскольку число шин в рассматриваемой системе равно девяти, размерность вектора варьируемых параметров Задача решена при следующих значениях свободных параметров алгоритма:
Сходимость алгоритма иллюстрирует рисунок 16; результаты решения задачи представлены в таблице 3.
Рисунок 16 − Сходимость алгоритма биогеографии при оптимизации тестовой электрической сети IEEE 9: интерфейс системы PowerFactory Таблица 3. Результаты решения задачи оптимизации электрической сети IEEE 9
Потери активной мощности в сети IEEE 9 без использования компенсаторов составляют 4,63 МВт. Представленному в таблице 3 решению соответствуют потери мощности, равные 4,2 MВт. Таким образом, за счет оптимизации набора и размещения компенсаторов удалось снизить потери активной мощности в рассматриваемой сети примерно на 9,2%. 5.3. Оптимизация электрической сети Кубани Электрическая сеть Кубани включает в себя 45 генераторов, 614 шин; 483 линии электропередач, 100 трансформаторов. Рассматриваем задачу расстановки компенсаторов в 110 киловольтной части этой сети, в которой числа шин, линий передач и трансформаторов равны 488, 419, 20 соответственно. Моделирование этой сети в системе PowerFactory показывает, что без использования компенсаторов потери активной мощности в сети составляют 148,8 МВт. Оптимизация данной сети выполнена при ограничениях, определяемых равенствами
Размерность вектора варьируемых параметров Сходимость алгоритма иллюстрирует рисунок 17, аналогичный рисунку 16.
Рисунок 17 −Сходимость алгоритма биогеографии при оптимизации электрической сети Кубани: интерфейс системы PowerFactory
Результат решения задачи представлены в таблице 4.
Таблица 4. Результаты решения задачи оптимизации электрической сети Кубани
Решению задачи, которое представлено в таблице 4 соответствуют потери активной мощности, равные 145,07 MВт. Таким образом, применение указанных в таблице 4 пяти компенсаторов и их оптимальное размещение позволяют снизить потери мощности на 2,5%.
В работе представлен перспективный метод глобальной оптимизации – метод биогеографии. Эффективность метода и разработанного программного обеспечения продемонстрирована на примере известной сложной задачи минимизации многомерной функции Растригина. Выполнена интеграция разработанного в системе MatLab программного обеспечения, реализующего BBOметод, с известным программным продуктом PowerFactory компании DlgSilent, который предназначен для решения широкого круга задач электроэнергетики и используется нами для расчета суммарных потерь мощности в исследуемой электрической сети. С помощью программного комплекса MatLabBBO+ PowerFactory проведено исследование эффективности метода биогеографии при решении задач оптимизации электрической сети IEEE 9 и сети Кубани. За счет оптимизации набора и размещения компенсаторов удалось снизить потери активной мощности в указанных сетях примерно на 9,2% и 2,5% соответственно. Как и в работе [6] метод биогеографии показал свою высокую эффективность. В развитие работы авторы предполагают исследовать природу этого факта. Предполагается также синтез и исследование эффективности гибридных популяционных методов, построенных на основе метода биогеографии. Работа поддержана грантом РФФИ 12-07-00222а «Управление знаниями, извлекаемыми из текстовых документов, на основе кластеризации онтологий».
Список литературы1. MacArthur R.H., Wilson E.O. The Theory of Island Biogeography. Princeton University Press, 1967. 224 p. 2. Карпенко А.П., Селиверстов Е.Ю. Глобальная оптимизация методом роя частиц. Обзор // Информационныетехнологии. 2010. № 2. С. 25-34. 3. Dréo J., Siarry P. Continuous interacting ant colony algorithm based on dense heterarchy // Future Generation Computer Systems. 2004. No. 20. P. 841-856. 4. Karaboga D., Basturk B. Artificial Bee Colony (ABC) optimization algorithm for solving constrained optimization problems // In: Foundations of Fuzzy Logic and Soft Computing. Springer Verlag, 2007. P. 789-797. (Ser. Lecture Notes in Computer Science; vol. 4529). DOI: 10.1007/978-3-540-72950-1_77 5. Карпенко А.П. Популяционные алгоритмы глобальной поисковой оптимизации. Обзор новых и малоизвестных алгоритмов // Приложение к журналу «Информационные технологии». 2012. № 7. С. 1-32. 6. Simon D. Biogeography-Based Optimization // IEEE Transactions on Evolutionare Computation. December 2008. Vol. 12, no. 6. P. 702-713. DOI: 10.1109/TEVC.2008.919004 7. Holland J.H. Adaptation in Natural and Artificial Systems. Cambridge: MIT Press, 1992. 228 p. 8. Потемкин В.Г. Введение в MATLAB. М.: Диалог-МИФИ, 2000. 256 с. 9. FACTS (Flexible Alternative Current Transmission Systems) - гибкиесистемыпередачипеременноготокакакфизическаяосноваумныхсетей. Режим доступа: http://energyfuture.ru/facts-flexible-alternative-current-transmission-systems (дата обращения 23.08.2013). 10. Subramanian A., Ravi G. Multi-type FACTS placement for loss minimization using biogeography based optimization // Archives of Electrical Engineering. 2012. Vol. 61, no. 4. P. 517-531. 11. Rarick R., Simon D., Villaseca F.E., Vakaranam B. Biogeography-based optimization and the solution of the power flow problem // Proceedings of the IEEE International Conference on Systems, Man and Cybernetics (San Antonio TX, USA, October 2009). SMC 2009. P. 1003-1008. DOI: 10.1109/ICSMC.2009.5346046 12. Bhattachary A., Chattopadhyay P.K. Solution of optimal reactive power flow using Biogeographybased optimization // International Journal of Energy and Power Engineering. 2010. Vol. 3, no. 4. P. 269-277. 13. Bhattacharya A., Chattopadhyay P.K. Biogeography - base optimization for different economic load dispatch problems // IEEE Transactions on Power Systems. 2010. Vol. 25, iss. 2. P. 1064-1077. DOI: 10.1109/TPWRS.2009.2034525 14. Groenwold A.A., Stander N., Snyman J.A. A pseudo-discrete rounding method for structural optimization // Structural Optimization. 1996. No. 11. P. 218-227. 15. DIgSILENT. PowerFactory. Available at: http://www.digsilent.de/index.php/products-powerfactory.html , accessed 23.08.2013. 16. Nallagalva S.K., Kumar Kirar M.K., Agnihotri G. Transient Stability Analysis of the IEEE 9 Bus Electric Power System // International Journal of Scientific Engineering and Technology. 2012. Vol. 1, no. 3. P. 161-166. Публикации с ключевыми словами: задача глобальной оптимизации, метод биогеографии, задача оптимизации электрической сети Публикации со словами: задача глобальной оптимизации, метод биогеографии, задача оптимизации электрической сети Смотри также: Тематические рубрики: Поделиться:
|
|
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|