close

Вход

Забыли?

вход по аккаунту

?

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

код для вставкиСкачать
НАУЧНЫЙ ВЕСТНИК МГТУ ГА
2013
№ 195
УДК 519.6
ПРИМЕНЕНИЕ МЕТОДОВ ПЧЕЛИНОЙ КОЛОНИИ И ПОИСКА
ГАРМОНИИ К ЗАДАЧЕ НАХОЖДЕНИЯ ОПТИМАЛЬНОГО УПРАВЛЕНИЯ
ДИСКРЕТНЫМИ ДЕТЕРМИНИРОВАННЫМИ СИСТЕМАМИ
А.В. ПАНТЕЛЕЕВ, Е.А. АЛЁШИНА
Рассмотрена проблема применения методов поиска гармонии, роя пчел и искусственной пчелиной колонии к
задачам оптимизации нелинейных дискретных детерминированных систем. Разработано программное обеспечение, с помощью которого произведено сравнение указанных методов на тестовом примере, содержащем систему
управления сложной структуры.
Ключевые слова: метод пчелиной колонии, метод поиска гармонии, оптимальное управление.
Введение
Метаэвристические методы являются актуальным направлением теории оптимизации [1-6].
Использование таких методов целесообразно для решения прикладных задач оптимального
управления летательными аппаратами (самолетами, ракетами, космическими аппаратами) на
различных участках полета со сложной структурой математических моделей, ввиду того, что
традиционные методы оптимизации не способны справиться с подобными проблемами. В данной работе на примере оптимизации нелинейной дискретной детерминированной системы
управления [5] сравниваются метод поиска гармонии, метод искусственной пчелиной колонии
и метод роя пчел [1-4].
1. Постановка задачи
Поведение модели объекта управления описывается разностным уравнением
x(t + 1) = f (t , x(t ), u (t )) ,
(1)
где t – дискретное время, t ∈ T = [0, 1,..., N − 1] ; x – вектор состояния системы, x ∈ R ; u – вектор управления, u ∈ U (t ) ⊆ R q ; U (t ) – множество допустимых значений управления, для каждого значения t представляющее собой прямое произведение отрезков [ai (t ), bi (t )] , i = 1, 2,..., q ;
n
число шагов дискретного времени N задано; f (t , x, u ) = ( f1 (t , x, u ),..., f n (t , x, u ))T – непрерывная
вектор-функция.
Начальное состояние задано
x(0) = x0 .
(2)
Правый конец траектории x( N ) свободен. Предполагается, что при управлении используется информация только о дискретном времени t , т.е. применяется программное управление.
Таким образом, рассматриваемая система управления является разомкнутой по состоянию.
Множество допустимых процессов D(0, x0 ) – это множество пар d = ( x(⋅), u (⋅)) , включающих траекторию x(⋅) = {x0 , x(1),..., x( N )} и допустимое управление u (⋅) = {u (0), u (1),..., u ( N − 1)} ,
где u (t ) ∈ U (t ) , удовлетворяющих уравнению состояния (1) и начальному условию (2).
На множестве допустимых процессов D(0, x0 ) определен функционал качества управления
N −1
I (d ) = ∑ f 0 ( t , x(t ), u (t ) ) + F ( x( N ) ) ,
t =0
(3)
14
А.В. Пантелеев, Е.А. Алёшина
где f 0 ( t , x(t ), u (t ) ) , F ( x ) – заданные непрерывные функции.
Требуется найти такую пару d * = ( x *(⋅), u *(⋅) ) ∈ D(0, x0 ) , что
I (d *) = min I (d ) .
d ∈D (0, x0 )
(4)
Искомые элементы пары d * : траектория x *(⋅) = {x0 , x * (1),..., x * ( N )} и управление
u *(⋅) = {u *(0), u *(1),..., u *( N − 1)} называются соответственно оптимальной траекторией и оптимальным управлением.
2. Идея решения задачи
При использовании метаэвристических методов для решения задачи (1)-(4) будем оптимизировать управление u (⋅) . Позиция частицы (пчелы) с номером j на k -й итерации будет представлять собой вектор-строку u j ,k = ( u j ,k (0), u j ,k (1),..., u j , k ( N − 1) ) . На каждой итерации будет
формироваться новая позиция частицы u j ,k +1 = ( u j ,k +1 (0), u j ,k +1 (1),..., u j ,k +1 ( N − 1) ) , ее необходимо
будет оценить с помощью критерия (3), который будет целевой функцией. Для получения значения
целевой
функции
потребуется:
а)
найти
траекторию
системы
j , k +1
j , k +1
j , k +1
j , k +1
x
= ( x0 , x
(1),..., x
( N ) ) , соответствующую управлению u
, из уравнения состояния
(1) с учетом условия (2); б) вычислить значение критерия (3), соответствующее u j ,k +1 и x j ,k +1 .
Выпишем формулу в явном виде
N −1
I ( d j , k +1 ) = ∑ f 0 ( t , x j ,k +1 (t ), u j ,k +1 (t ) ) + F ( x j ,k +1 ( N ) ) ,
где
d
j , k +1
= (x
j , k +1
(⋅), u
j , k +1
(⋅) )
t =0
– процесс из множества допустимых процессов D (0, x0 ) ,
x j ,k +1 (t ), t = 0,..., N определяется уравнением состояния (1) и начальным условием (2)
 f ( t − 1, x j ,k +1 (t − 1), u j ,k +1 (t − 1) ) , t = 1,..., N ,
x j ,k +1 (t ) = 
 x0 , t = 0.
3. Метод поиска гармонии
Стратегия поиска решения. Метод имитирует процесс импровизации музыкантаисполнителя [1]. В процессе поиска каждое решение из множества допустимых порождает значение функции с целью достижения глобального экстремума. При этом используются идеи метода имитации отжига, метода частиц в стае, стохастического градиента.
Метод поиска гармонии сконструирован таким образом, что процедура генерирования нового решения позволяет выходить из области притяжения локального экстремума.
Алгоритм
Шаг 1. Задать параметры метода:
hms
– размер памяти гармонии;
hmcr
– частоту выбора значений из памяти гармонии;
par
– частоту выбора соседнего значения;
fw
– вектор максимального изменения приращения;
– максимальное число итераций.
K
Положить число итераций k = 0 .
Применение методов пчелиной колонии и поиска гармонии …
15
Шаг 2. На множестве допустимых решений генерировать hms решений u1 ,..., u hms ,
u j = ( u j (0), u j (1),..., u j ( N − 1) ) . Используя уравнение состояния (1), получить допустимые про-
цессы d j = ( x j , u j ) ,
j = 1,..., hms и найти соответствующие значения целевой функции
I ( d 1 ) ,..., I ( d hms ) . Сохранить их в памяти гармонии ( HM )
 u11 L u1n
f (u1 ) 


HM =  M O M
M .
 u hms L u hms f (u hms ) 
n
 1

worst
Найти наихудшее решение в памяти u
.
new
Шаг 3. Генерировать новый вектор u . Для всех i = 1,..., n :
Шаг 3.1. Получить значения ui′ следующим образом:
– с вероятностью hmcr выбрать элемент из памяти HM с номером int[r (0,1) ⋅ hms ] + 1 ,
ui′ = uiint[ r (0,1) ⋅hms ]+1 ,
где r (0,1) – равномерно распределенное число от 0 до 1; int[⋅] – операция нахождения целого
числа;
– с вероятностью 1 − hmcr выбрать значение внутри промежутка [ai , bi ] : ui′ ∈ [ai , bi ] .
Шаг 3.2. Если значение ui′ выбрано из памяти, то
– с вероятностью par найти
uinew = ui′ + fwi ⋅ r (−1, 1) ,
где r (−1, 1) – равномерно распределенное число на [−1, 1] ;
– с вероятностью 1 − par положить
uinew = ui′ .
Шаг 4. Если новое решение u new лучше наихудшего решения u worst в памяти, то заменить
u worst на u new . Иначе – не заменять.
Шаг 5. Проверка условий окончаний процесса поиска:
− если k < K , положить k = k + 1 и перейти к шагу 3;
− если k = K , процесс завершить, найти наилучшее решение u best в памяти и положить
u* = u best .
Для сравнения с другими методами использовалась модификация метода поиска гармонии,
в которой величины fwi экспоненциально убывают.
4. Метод роя пчел
Стратегия поиска решения. Идея метода состоит в моделировании поведения пчёл при
поиске нектара [2]. На основе информации, полученной от других пчёл, пчела может двигаться
к предполагаемой точке экстремума; выбраться из области притяжения локального экстремума;
исследовать ранее неисследованные области.
Алгоритм
Шаг 1. Задать максимальное число итераций K , число пчёл-разведчиков s , пороговое значение расстояния между пчёлами в начальный момент threshold , параметр области локального
поиска ∆ , числа пчёл B и P , посылаемых в «наилучшие» и «перспективные» области; числа b
16
А.В. Пантелеев, Е.А. Алёшина
и p = s − b отбираемых наилучших и перспективных значений целевой функции. Положить
число итераций k = 0 .
Шаг 2. Сформировать начальное положение s пчёл-разведчиков при помощи равномерного
распределения на множестве U . Если расстояние (евклидово) между двумя пчёламиразведчиками меньше порогового значения threshold , остаётся пчела с большим значением
функции. Недостающие пчёлы-разведчики генерируются заново.
Для всех пчёл-разведчиков подсчитываются значения функционала качества управления.
Шаг 3. Все значения критерия (для всех пчёл, находящихся на множестве U ) упорядочить
по убыванию: I ( d 1 ) ≥ I (d 2 ) ≥ ... ≥ I ( d s ) . Из них выбрать b наилучших значений и p перспективных значений, наиболее близких к наилучшим.
Шаг 4. Выбранным на шаге 3 значениям ставятся в соответствие области локального поиска, каждая из которых представляет собой гиперкуб; центр области определяется координатами
пчелы-разведчика, длины сторон равны 2∆ . Результатом шага 4 является нахождение b
«наилучших областей» и p перспективных областей.
Шаг 5. В каждой из «наилучших областей» случайным образом (используя равномерное
распределение) генерируется B новых решений, а в каждой из «перспективных областей» генерируется P новых решений. Для всех новых решений подсчитываются значения целевой
функции.
Шаг 6. Проверяется выполнение условия окончания:
− если k < K − 1 , то положить k = k + 1 и перейти к шагу 3;
− если k = K − 1 , процесс завершить и в качестве u * выбрать наилучшее решение из достигнутых.
При решении задачи поиска оптимального управления использовалась модификация метода, в которой области сжимаются с ростом числа итераций ∆ = ∆ ⋅ R , где 0 < R ≤ 1 . В начальный
момент времени значение ∆ = ∆ 0 задано.
Важная особенность алгоритма состоит в том, что новые решения, генерируемые в процессе поиска, не могут выйти за границы множества допустимых решений. Для этого достаточно
при задании «наилучших» и «перспективных» областей корректировать их границы с учетом
границ множества допустимых решений.
5. Метод искусственной пчелиной колонии
Стратегия поиска решения. В методе искусственной пчелиной колонии (ABC – artificial
bee colony algorithm) [3; 4] в качестве основы взяты особенности поведения пчёл при поиске источников пищи (нектара). Основное отличие от метода роя пчел – другой способ генерации нового решения.
Алгоритм
Шаг 1. Инициализация алгоритма и генерация начальных позиций источников питания.
Шаг 1.1. Задать параметры метода: максимальное число итераций K ; количество источников
питания, количество рабочих пчёл, количество пчёл-наблюдателей SN ; предельное количество
итераций, по прошествии которых решение считается забытым, если оно не было улучшено,
limit .
Шаг 1.2. Для каждой рабочей пчелы находятся координаты её положения
uij = ai + rand ⋅ (bi − ai ) , i = 1,..., n , j = 1,..., SN ,
где rand – равномерное распределённое случайное число на отрезке [0;1] .
17
Применение методов пчелиной колонии и поиска гармонии …
Шаг 1.3. Для всех полученных решений (для всех пчёл-разведчиков) находятся соответствующие допустимые процессы d j = ( x j , u j ) и значения критерия I ( d j ) , j = 1,..., SN .
Шаг 1.4. Положить k = 0 .
Шаг 2. Получение новых решений для рабочих пчёл
Шаг 2.1. Сгенерировать новые решения v j
vij = uij + ϕij ⋅ (uij − uir ) , i = 1,..., n , j = 1,..., SN ,
где ϕij – равномерное распределённое случайное число на отрезке [−1; 1] , номер r выбирается
случайным образом из {1,..., SN } , но при этом r отличается от j .
Шаг 2.2. Рассчитать значения критерия I ( d
j
) , где d = ( x , v ) ,
j
j
j
j = 1,..., SN .
Шаг 3. Произвести селекцию среди новых решений v j и существующих решений u j :
− если I ( d j ) < I ( d j ) , заменить u j на новое решение v j ;
− иначе u j не заменять.
Шаг 4. Рассчитать вероятности выбора p j для решений u j
p =
j
I (d j )
∑ I (d )
SN
, j = 1,..., SN .
s
s =1
Шаг 5. Получение новых решений для пчёл-наблюдателей аналогично решениям рабочих
пчёл на шаге 2.
Шаг 5.1. Сгенерировать новые решения v j
vij = uij + ϕij ⋅ (uij − uir ) , i = 1,..., n , j = 1,..., SN ,
где ϕij – равномерное распределённое случайное число на отрезке [−1; 1] , номер r выбирается
случайным образом на основе вероятностей p j , но при этом r отличается от j .
Шаг 5.2. Рассчитать значения критерия I ( d
j
), d = (x ,v ),
j
j
j
j = 1,..., SN .
Шаг 6. Произвести селекцию среди новых решений v j и существующих решений u j , таким же образом, как на шаге 3.
Шаг 7. Генерация новых решений вместо «забытых». Решения, для которых количество
итераций без изменения значения превысило limit , считаются «забытыми». Среди всех забытых решений выбирается одно с наихудшим значением целевой функции. Это решение исключается из рассмотрения, а вместо него генерируется новое случайным образом на множестве U :
uij = ai + rand ⋅ (bi − ai ) , i = 1,..., n , j = 1,..., SN ,
где rand – равномерное распределённое случайное число на отрезке [0;1] .
Шаг 8. Определить и сохранить в памяти лучшее к данному моменту решение u best .
Шаг 9. Проверить условие окончания процесса поиска:
− если k < K − 1 , то перейти к шагу 2.
− иначе процесс завершить. В качестве u * выбрать наилучшее решение u best .
6. Программное обеспечение
На основе разработанного алгоритма сформировано программное обеспечение на языке C#
в среде Microsoft Visual Studio 2005, включающее графический пользовательский интерфейс.
С помощью программного обеспечения пользователь может выполнять следующие действия:
18
А.В. Пантелеев, Е.А. Алёшина
вводить параметры постановки задачи; задавать параметры метода; просматривать результат
решения задачи в виде графиков; анализировать полученный результат; сохранять результат в
памяти компьютера для последующего анализа.
7. Решение тестовых примеров
Пример 1. Рассмотрим задачу оптимального управления, описанную в [5].
Модель дискретной системы управления описывается конечно-разностными уравнениями:
x1 (t )
x1 (t + 1) =
;
1 + 0, 01 u1 (t ) ( 3 + u2 (t ) )
x2 (t + 1) =
x3 (t + 1) =
x2 (t ) + u1 (t ) x1 (t + 1)
;
1 + u1 (t ) (1 + u2 (t ) )
x3 (t )
;
1 + 0, 01 u2 (t ) (1 + u3 (t ) )
t = 0,1,..., N − 1 .
Начальные условия x(0) = [ 2 5 7 ] .
T
Ограничения на управление: 0 ≤ u1 (t ) ≤ 4 , 0 ≤ u2 (t ) ≤ 4 , 0 ≤ u3 (t ) ≤ 0,5 .
Критерий оценки качества управления
1
2
 N
 N

I = ∑ xi2 (t N ) +  ∑ x12 (t − 1) + x22 (t − 1) + 2u32 (t − 1)  ∑ x32 (t − 1) + 2u12 (t − 1) + 2u22 (t − 1)   .
i =1
 t =1

 t =1
Необходимо минимизировать критерий.
В [5] рассмотрены случаи N = 20 , N = 50 и N = 100 .
Разработанное программное обеспечение позволяет провести серию опытов и рассчитать
статистические характеристики получаемой выборки значений. При проведении опытов запускалась серия из 100 решений (для N = 20 ) или 30 решений (для N = 50 и N = 100 ) одной и той
же задачи с одними и теми же значениями параметров. Для полученной выборки { I 1 , I 2 ,..., I 100 }
3
вычислялись выборочное среднее I =
(
1 100 i
∑ I и среднеквадратическое отклонение σ I = S 100 ,
100 i =1
)
2
1 100 i
I −I .
∑
99 i =1
В табл. 1 сведены результаты серий опытов при разных значениях времени функционирования системы N , а также для сравнения приведены результаты из [5], полученные с использованием метода итерационного динамического программирования. Использовались следующие обозначения: HS (Harmony Search) – метод поиска гармонии; BA (Bees Algorithm) – метод роя пчел;
ABC (Artificial Bee Colony) – метод искусственной пчелиной колонии; n f – требуемое количе-
S 100 =
ство вычислений значения целевой функции. Параметры методов подбирались таким образом,
чтобы реальное количество расчетов значений целевой функции было приблизительно равно n f .
По результатам, представленным в табл. 1, делаем вывод, что в целом наиболее близкие к
оптимальным решения получаются при использовании метода роя пчел, однако в случае ограниченных вычислительных ресурсов иногда оказывается лучше использовать метод поиска
гармонии (случаи N = 50 и N = 100 , когда количество вычислений значений функции не должно превышать 25000).
19
Применение методов пчелиной колонии и поиска гармонии …
Таблица 1
N
nf
Метод
I
I наим
σI
HS
209,563
209,3048
212,8299
208,672
208,4255
209,3878
208,4796
208,4369
208,471
243,0316
246,4545
253,5078
241,2325
240,2685
248,8643
240,5671
239,9008
242,3185
275,5493
297,3412
313,3766
267,8703
259,8398
303,2857
264,0494
258,1714
281,2116
210,6242
209,9043
215,3463
209,2445
208,6678
209,9216
208,802
208,6077
208,6318
243,781
247,9878
258,0076
241,8219
240,4086
250,3288
240,9298
239,975
242,8575
278,9272
301,2077
320,3505
269,732
260,1668
307,3917
265,1362
258,3441
284,0097
0,524269
0,311183
0,887809
0,216007
0,124801
0,315238
0,157133
0,097741
0,053726
0,484859
0,617528
1,948513
0,27996
0,071366
0,687646
0,189076
0,034119
0,325716
1,515548
1,720014
3,291568
0,936816
0,233011
1,860283
0,583137
0,09873
1,72876
20
5000
BA
ABC
20
25000
BA
ABC
HS
HS
20
100000
BA
ABC
25000
BA
ABC
HS
50
HS
50
100000
BA
ABC
50
250000
BA
ABC
HS
HS
100
25000
BA
ABC
100000
BA
ABC
HS
100
HS
100
250000
BA
ABC
Значение из
[5]
209,26937
240,917
258,33922
Заключение
Рассмотренные метаэвристические методы позволяют решать задачи поиска оптимального
управления нелинейными дискретными детерминированными системами сложной структуры.
Наилучшие результаты дает применение метода роя пчел, однако следует отметить, что в [4]
приведены данные, полученные одним из вариантов метода искусственной пчелиной колонии
(описанным недостаточно подробно), который несколько отличается от алгоритма, используемого авторами в данной статье.
При решении тестовой задачи подбор параметров осуществлялся эмпирическим образом.
Такой подход не гарантирует оптимальность подобранных значений. В связи с этим интерес
представляет реализация адаптивных версий метаэвристических методов, которая позволит
провести более корректное сравнение.
ЛИТЕРАТУРА
1. Lee K.S., Geem Z.W. A new meta-heuristic algorithm for continuous engineering optimization: harmony search
theory and practice // Computer Methods in Applied Mechanics and Engineering, 194, pp.3902-3933, 2005.
2. Pham D.T., Ghanbarzadeh A., Koc E., Otri S., Rahim S., Zaidi M. The Bees Algorithm – A Novel Tool for
Complex Optimization Problems // Proceedings of IPROMS 2006 Conference, pp. 454–461, 2006.
3. Basturk B. An artificial bee colony (abc) algorithm for numeric function optimization / D. Karaboga, In IEEE
20
А.В. Пантелеев, Е.А. Алёшина
Swarm Intelligence Symposium 2006, Indianapolis, Indiana, USA, May 2006.
4. Karaboga D., Akay B. A comparative study of artificial bee colony algorithm. Applied Mathematics and Computation, In Press, 2009.
5. Luus R. Iterative Dynamic Programming.- Monographs and Surveys in Pure and Applied Mathematics, London,
UK: Chapman & Hall/CRC, 2000.
6. Пантелеев А.В. Метаэвристические алгоритмы поиска глобального экстремума. - М.: Изд-во МАИПРИНТ, 2009.
BEES OPTIMIZATION AND HARMONY SEARCH APPLIED
TO OPTIMAL CONTROL OF DISCRETE TIME DETERMINISTIC SYSTEM
Panteleyev A.V., Alyoshina E.A.
We consider the application of bees, artificial bee colony and harmony search algorithms to process of searching the
optimal control of discrete deterministic system. The special software for solving such problems was developed. We performed the comparison of the methods considered on test problem containing control system of complex structure.
Key words: artificial bee colony algorithm, harmony search, optimal control.
Сведения об авторах
Пантелеев Андрей Владимирович, 1955 г.р., окончил МГТУ им. Н.Э. Баумана (1978), доктор физико-математических наук, профессор, заведующий кафедрой математической кибернетики МАИ, автор
более 150 научных работ, область научных интересов – методы синтеза оптимальных нелинейных систем управления, методы оптимизации.
Алёшина Екатерина Александровна, окончила МАИ (2010), аспирантка МАИ, автор 14 научных
работ, область научных интересов – методы оптимизации, численные методы.
1/--страниц
Пожаловаться на содержимое документа