Scientific journal
Fundamental research
ISSN 1812-7339
"Перечень" ВАК
ИФ РИНЦ = 1,674

ON THE APPLICATION OF MULTI-AGENT ALGORITHMS ANT COLONIES TO SOLVE THE PROBLEM OF STRUCTURAL OPTIMIZATION IN POWER SYSTEMS

Eremenko Y.I. 1 Tsukanov M.A. 1 Solovyev A.Y. 1
1 Stary Oskol Technological Institute. AA Ugarov branch NITU «MISiS»
The paper outlines an approach for the structural optimization of energy systems . The basic problem of structural optimization of energy networks . In particular the proposed task with a limited number of connected consumers and the problem with a limited number of power distribution facilities . Both of these tasks are related to a class of discrete optimization problems and are intractable using classical methods and algorithms. Therefore, this paper proposes a novel approach based on artificial intelligence techniques . The approach is based on the method of simulating the behavior of ants , called ant colony algorithm . This modified ant colony algorithm has been developed for all identified problems of structural optimization of energy networks. We consider its implementation as well as comparison of simulation results for problems of different dimensions to the work of the genetic algorithm.
structural optimization
location problem
ant colony algorithm
1. Eremenko Yu.I, Gluschenko A.I. The solution of non-formalizable and plohoformalizuemyh problems by immune algorithms // Information Technology. 2011. no. 7. рр. 2–7
2. Semenov M.E.Algorithms for structural optimization of communication networks / M.E. Semenov, A.Yu. Solovev, O.V. Timchenko // Control Systems and Information Technology, 2009. no. 3.1 (37). pp. 195–199.
3. Shtovba S.D. Ant Algorithms // Exponenta Pro. Mathematics in Applications, 2003. no. 4. pp. 70–75.
4. Merkur’ev GV of the supervisory control power systems / / SPB Edition Training Center Energy 2002. pp. 116.
5. Colorni A., Dorigo M., Maniezzo V. Distributed optimization by Ant Colonies. Proceedings of the First European Conference on Artifical Life. Paris, France, 1991. pp. 134–142.

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

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

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

Алгоритмы муравьиных колоний для решения задач размещения

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

Обозначим через I = (1,...,n) множество конечных потребителей, каждое из которых должно быть подключено только к одному объекту энергораспределения; J = (1,..., m) – множество мест, в которых можно разместить объект энергораспределения; bij ≥ 0, i ∈ I, j ∈ J – стоимость подключения j-го объекта энергораспределения к i-му конечному потребителю. Стоимость прямо пропорциональна стоимости укладки кабеля, стоимости кабеля и расстоянию между объектом и потребителем; qj > 0, j ∈ J – емкость объекта энергораспределения, выраженная в допустимом количестве подключаемых к нему конечных потребителей; cj ≥ 0, j ∈ J – стоимость установки объекта энергораспределения на j-м месте-кандидате; xij ∈ {0, 1} принимает свои значения в зависимости от того, к какому объекту энергораспределения подключен текущий конечный потребитель; yj ∈ {0, 1} принимает значения в зависимости от того, установлен ли объект энергораспределения в текущем месте.

Задача с ограниченным числом подключаемых конечных потребителей. Эта задача формализуется следующим образом:

erem01.wmf (1)

erem02.wmf (2)

Ограничение (2) означает, что возможное число подключаемых потребителей к объекту энергораспределения не будет превышать заданного значения.

Задача с ограниченным числом объектов энергораспределения. Имея множество мест возможной установки объектов энергораспределения J ∈ {1, ..., m}, из всех возможных множеств, формирующих структуру системы, необходимо выбрать такое множество S ⊆ J, чтобы суммарная функция затрат была минимальной, и все конечные потребители, принадлежащие множеству I ∈ {1, ..., n}, были подключены, но при этом число объектов энергораспределения не должно превышать заданного числа p. Теперь задачу можно сформулировать так:

erem03.wmf (3)

<erem04.wmf (4)

Для обеих задач выполняется ограничение

erem05.wmf (5)

Ограничения (5) гарантируют, что все конечные потребители будут подключены, и один конечный потребитель может быть подключен только к одному объекту энергораспределения.

Для поставленной задачи были разработаны алгоритмы, основанные на классическом алгоритме муравьиной колонии, предложенные М. Дориго [3, 4]. В силу специфики задачи классический алгоритм муравьиных колоний был модифицирован.

На рисунке приведена блок-схема предложенных алгоритмов.

Перечислим основные отличия разработанного алгоритма от классического муравьиного алгоритма:

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

2. Формула оценки количества феромона имеет вид

erem06.wmf (6)

здесь erem07.wmf ‒ количество наносимого виртуального феромона на итерации муравья k; Q – регулируемый параметр, значение которого выбирают одного порядка с длиной оптимального маршрута; F – текущее оптимальное решение; Rk – стоимость маршрута, выбранного k-м муравьем-агентом.

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

3. Кроме того, иначе определяется сама формула расчета количества наносимого феромона. Отметим, что первоначально, следуя идее классического муравьиного алгоритма, количество наносимого феромона рассчитывалось по формуле

erem08.wmf (7)

где erem09.wmf есть расстояние между i-м конечным потребителем и j-м объектом энергораспределения. Соблюдая данное условие, алгоритм показывает хорошие результаты в задаче, где стоимость установки объекта энергораспределения не включается. При включении же стоимости целесообразней пользоваться формулой из (6). То есть параметр erem09.wmf был заменен на Rk – стоимость маршрута k-го муравья.

4. Для задачи с ограниченным числом объектов энергораспределения формула вероятности выбора мест установки объектов энергораспределения выглядит следующим образом

erem11.wmf (8)

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

erem12.wmf (9)

где ηij – величина, обратная расстоянию, или так называемая видимость муравья, α и β – два регулируемых параметра, задающие веса следа феромона и видимости при выборе маршрута. Как видим из (8), в формуле вероятности были убраны параметры ηij и β. В самом классическом алгоритме данные параметры играли косвенную роль в минимизации расстояния, и их включение было необходимо. Для данной задачи эти параметры не являются обязательными, также исключение этих параметров позволило сократить время на поиск наилучшего решения при работе алгоритма.

pic_25.tif

Блок-схема алгоритмов для задач размещения

Такие этапы, как нанесение количества феромона и процедура испарения феромона, остались без изменений. Обозначим коэффициент испарения феромона через ρ ∈ [0, 1]. Тогда правило обновления феромона примет вид

τj = τj(1 – ρ). (10)

Проведение экспериментальных тестирований

Для проведения численных экспериментов и моделирования полученных алгоритмов, в частности, алгоритма муравьиной колонии (ACO) использовалась среда для имитационного моделирования AnyLogic.

Наиболее важными параметрами в алгоритме муравьиной колонии помимо числа муравьев являются параметры α, β, ρ. Параметры α и β отвечают за веса следа феромона, тогда как параметр ρ отвечает за скорость испарения феромона. Выбор ключевых параметров излишне большим или, наоборот, маленьким может привести к слишком быстрому вырождению алгоритма и получению одного субоптимального решения.

Для каждой из поставленных задач помимо муравьиного алгоритма использовался генетический алгоритм(GA). Данный алгоритм, как и многие другие направления и методы искусственного интеллекта, такие как иммунные сети [1], нейросети, алгоритмы имитации отжига уже хорошо зарекомендовали себя при решении подобного рода задач и задач дискретной оптимизации.

Алгоритмы тестировались на матрицах одинаковых размерностей, которые были сгенерированы случайным образом. Координаты точек расположения объектов энергораспределения и конечных потребителей были идентичны для обоих алгоритмов.

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

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

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

Таблица 1

n

m

Ограничение мощности

Целевая функция

Время, с

ACO

GA

ACO

GA

12

8

3

976,023

976,023

0,05

0,05

20

15

3

1297,307

1297,307

0,07

0,08

20

20

3

1345,097

1345,097

1,02

1,06

40

20

3

2854,353

2932,598

2,36

4,52

50

20

3

3707,201

3824,268

15,14

36,43

70

30

4

4629,368

4849,276

20,02

114,47

100

50

4

5240,651

5371,423

25,97

151,79

200

60

4

17040,116

19574,281

37,45

202,17

300

80

5

25867,954

26033,17

43,39

231,68

 

Таблица 2

m

n

p

Целевая функция

Время, с

ACO

GA

ACO

GA

1

2

3

4

5

6

7

20

20

5

1574,653

1603,88

0,01

0,01

30

30

5

2564,182

2591,275

0,4

0,73

40

40

5

3173,654

3264,975

1,03

3,15

50

50

5

4234,961

4452,086

6,31

10,18

60

60

5

4924,604

5049,322

8,52

16,39

70

70

5

5573,454

5761,855

17,48

31,11

80

80

5

7034,218

7215,051

23,95

40,54

90

90

5

7875,932

8183,22

29,67

48,75

100

100

5

8812,972

9134,676

36,24

58,43

110

110

5

9867,511

10137,726

41,71

66,14

1

2

3

4

5

6

7

120

120

5

10959,295

11060,058

53,12

87,51

130

130

5

11395,606

12052,505

61,36

101,49

30

30

10

1880,427

1887,564

1,09

7,22

40

40

10

2386,928

2395,599

3,25

15,43

50

50

10

3052,7832

3138,52

7,13

20,28

60

60

10

3554,071

3660,551

15,82

32,43

70

70

10

4100,488

4233,996

23,47

47,19

80

80

10

5052,326

5336,506

29,03

60,38

90

90

10

5679,951

5822,671

33,81

72,15

100

100

10

6261,307

6571,38

37,92

86,09

110

110

10

6870,509

6979,492

44,55

112,11

120

120

10

7364,765

7693,327

59,48

136,1

130

130

10

8132,323

8406,671

62,94

153,72

140

140

10

8643,922

9355,775

66,39

184,63

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

Заключение

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

Рецензенты:

Семенов М.Е., д.ф-м.н., профессор кафедры цифровых технологий Воронежского государственного университета, г. Воронеж;

Кургалин С.Д., д.ф-м.н., профессор, заведующий кафедрой цифровых технологий Воронежского государственного университета, г. Воронеж.

Работа поступила в редакцию 05.12.2013.