Разработка алгоритмического и программного обеспечения метода частиц в стае

Тип работы:
Реферат
Предмет:
Физико-математические науки


Узнать стоимость

Детальная информация о работе

Выдержка из работы

2009
НАУЧНЫЙ ВЕСТНИК МГТУ ГА серия Прикладная математика. Информатика
№ 145
УДК 519. 6
РАЗРАБОТКА АЛГОРИТМИЧЕСКОГО И ПРОГРАММНОГО ОБЕСПЕЧЕНИЯ МЕТОДА ЧАСТИЦ В СТАЕ
А.В. ПАНТЕЛЕЕВ, Е.А. АЛЕШИНА
Рассмотрена задача поиска условного глобального минимума функций многих переменных с помощью метода частиц в стае. Сформирован детальный алгоритм решения поставленной задачи и на его основе создано программное обеспечение, эффективность которого продемонстрирована на типовых примерах.
Ключевые слова: поиск глобального экстремума, метод частиц в стае, алгоритмическое обеспечение.
Введение
Метод частиц в стае, предложенный в [1], относится к группе метаэвристических методов поиска глобального экстремума. В группу входят генетические алгоритмы с бинарным и вещественным кодированием, методы дифференциальной эволюции, имитации отжига, муравьиной колонии и др. Эти методы, имитируя некоторые свойства живой природы, позволяют отыскать приемлемое, с точки зрения практики, решение, несколько отличающееся от оптимального.
Формирование алгоритмического обеспечения перечисленных методов является актуальным не только для решения непосредственно задачи поиска глобального экстремума многоэкстремальных функций нескольких переменных, но и для решения разнообразных прикладных задач, в частности, проблемы параметрической оптимизации систем управления. Соответствующее программное обеспечение должно быть эффективно как для решения типовых задач, так и для оптимизации специальным образом сконструированных типовых функций [2,3], имеющих сложный рельеф поверхностей уровня.
1. Постановка задачи
Дана функция /(х) = /(х1,х2,…, хп), определенная на множестве допустимых решений В с Яп, где х = (х1,х2,…, хп) т, В = {х | х{ е [а-, Ь ], / = 1,2,…, п}.
Требуется найти условный глобальный минимум функции /(х) на множестве В, т. е. такую точку х* е В, что /(х*) = шт /(х).
хеВ
2. Стратегия поиска решения
Основная идея метода состоит в моделировании поведения стаи животных при поиске пищи. Если один из членов стаи видит путь к цели, то остальные особи очень быстро последуют его примеру. В [1] приведен следующий иллюстрирующий пример. Если повесить за окном кормушку, то за несколько часов к ней слетится много птиц, даже если до этого кормушку никогда не вешали. Как же птицы узнают о еде? Предполагается, что птица, увидев, что ее «соплеменник» начинает куда-то быстро перемещаться, подражает его поведению, т. е. перемещается в том же направлении и примерно с той же скоростью. Другой член стаи, обнаружив, что его сосед, который до этого отдыхал на ветке, куда-то улетает, также поднимется в воздух и полетит за соседом. Таким образом, животные, следуя довольно простым правилам, избегают опасности и находят пищу.
Каждый член стаи рассматривается как частица в многомерном пространстве, которая имеет положение и скорость (она появляется в процессе движения). Каждая частица изменяет свое положение, запоминая наилучшее, которому соответствовало наименьшее значение целевой функции. Члены стаи сообщают информацию о хороших позициях друг другу и используют ее для корректировки своего положения и скорости на каждой итерации. Каждая частица, используя свой прошлый опыт, ищет свое решение задачи.
Известно несколько способов выбора «соседей» для обмена информацией между частицами. Можно использовать расстояние, но практика показывает, что у «близких» соседей, как правило, нет ценной информации. Идея использовать наилучший результат среди членов стаи возможна, но далека от реальной ситуации. Поэтому предполагается, что частица случайным образом выбирает заданное число «соседей» (также случайное в заданном диапазоне) и собирает от них желаемую информацию.
Процедура поиска заканчивается при достижении максимального числа итераций. В качестве приближенного решения выбирается наилучшее среди всех членов стаи.
При реализации метода частиц в стае используются следующие основные принципы: для достижения цели используется множество особей (частиц) — каждая особь получает информацию о передвижении соседей- движение к цели осуществляется путем подражания действиям соседа- учитывается информация о цели (величина целевой функции / (х)), получаемая через органы чувств (например, запах пищи) —
используется собственный прошлый опыт.
При этом моделируются тенденции живого организма повторять успешное в прошлом поведение, особенно в случае локальной неудачи- подражать успеху остальных- двигаться за лидером, выбираемым среди соседей.
Пусть имеется стая из ЫР частиц с позициями (х1,х2,…, хЫр}с В с Яп. На каждом этапе (итерации) у частицы с номером у выбирается случайное число Ш1 ~ Я[ЖШП, N1 шах ] соседей, определяемое равномерным (Я) распределением на отрезке [N1 шп, N1 шх ], где N1 шп — минимальное число соседей из членов стаи- N1 шях — максимальное число соседей (не превышающее ЫР). Среди соседей находится частица с номером п. и позицией хп, к, которой соответствует наименьшее значение целевой функции. Каждая частица с номером 1 хранит информацию о своей лучшей позиции х1 к, достигнутой в течение к итераций. Скорость частицы v1, k+1 с уче-
~ 1, к ~ п., к
том текущего положения и скорости, своей наилучшей позиции х в прошлом, позиции х 1 лидера среди соседей вычисляется по формуле:
где к — номер итерации- V1, к, х1, к — скорость и позиция частицы на к -й итерации соответственно- со — весовой параметр, характеризующий инерцию (память) частицы- а и /3 — параметры, учитывающие степень влияния лидера среди соседей и прошлого опыта частицы (весовые коэффициенты) на ее последующую скорость- г1 и г2 — случайные параметры, заданные равно-
Новое положение частицы находится суперпозицией текущего положения и перемещения частицы в единицу времени (т.е. скорости):
(1)
мерным законом распределения ^[0- і].
Если новая позиция х1, к+1 оказалась лучше, чем х1, к, необходимо в качестве наилучшей
/у 1 к+1 1 к+1
позиции х принять х.
Расчет новой скорости и новой позиции по формулам (1) и (2) производится для всех у = 1,…, ЫР частиц стаи. Далее выполняется следующая итерация и так до выполнения условий окончания расчета. В качестве условия окончания обычно выбирается равенство числа итераций к некоторому наперед заданному числу N (максимальному числу итераций), но такое условие не гарантирует близости к минимуму целевой функции в конце расчета.
3. Схема алгоритма
Шаг 1. Задать Ы Р — количество частиц в стае- N1 шп, Ы/шах — параметры выбора числа «соседей» в стае- N — максимальное число итераций- весовой коэффициент с, характеризующий инерцию- параметры, а и /, используемые при вычислении скорости частицы.
Шаг 2. Сформировать стаю частиц:
положить число итераций к = 0-
в области В допустимых решений задать ^ частиц с позициями х10, х20,…, х0. Для этого использовать равномерный закон распределения, т. е. для каждой частицы с номером у = 1,…, ^ найти позицию х1 0 = (х/, 0,…, х]п 0), полагая х/ 0 ~ Я [ц, Ь ], / = 1,…, п —
положить начальные скорости равными нулю: V10 = 0, у = 1,… ,^.
Шаг 3. Для каждой частицы 1 = 1,… ,^ найти:
случайное число N11 соседей при помощи равномерного распределения на отрезке [ NIшln,шах ], среди них найти частицу с номером и позицией хп, к, которой соответствует наименьшее среди выбранных соседей значение целевой функции-
наилучшую позицию х1, к в течение к итераций (при к = 0 положить х1,0 = х10).
Шаг 4. Для каждой частицы в стае (1 = 1,… ,^) по выражениям (1) и (2) найти скорость и
положение на следующей итерации. Если /(х1, к+1)& lt- I (^1,к), то запомнить новую наилучшую позицию: х1, к+1 = х1, к+1, / (х], к+1)= / (х1, к+1), положить к = к +1.
Шаг 5. Проверить условие окончания:
а) если к = N, то процесс закончить. Найти частицу в стае с наименьшим значением целевой функции и принять ее положение в качестве приближенного решения задачи-
б) если к & lt- N, то перейти к Шагу 3.
Замечания.
1. Рекомендуемые значения параметров алгоритма: сое [0,01- 0,7]- ^ = (30,50,100} ,
N1 = 15, Жтях = 25, N = 200 500 — а и В близки к 1, но меньше.
Ш1П 1 ШаХ 1 1 • 1
2. В существующих модификациях изложенного метода предлагается [2]:
а) пересчет скорости вместо (1) производить по формуле
V1, к+1 = см1, к + аг1 (х1, к — х1, к)+ со/г2 (хп, к — х1, к)+ соуг3 г, (3)
где г3 — случайное число, заданное равномерным законом распределения на [0- 1] - г — вектор
скорости выбранного случайным образом (на основе равномерного распределения) соседа- у -параметр, меньший 1 (рекомендуется начать с у = 5 • 10−4, а затем увеличивать для преодоления «притяжения» к локальным минимумам) —
б) пересчет положения вместо (2) производить по формуле
хм+1 = ХМ + vM+d, (4)
где d — случайное число, равномерно распределенное на отрезке [-0,5- 0,5]-
в) вместо вычислений по формуле (2) на каждой итерации дополнительно производить локальный поиск по положению, задавая параметр nstep е[5−15], получая последовательность решений:
xlm, k+1 = x1, k + v1, k+1 (m- [nstep/2]-1), m = 1,…, nstep,
где nstep — параметр, определяющий число решений в локальном поиске- [nstep/2] - целая часть числа [nstep/2]. Среди полученных решений x11, k+1,…, xlm, ep, k+1 выбрать то, которому соответствует наименьшее значение целевой функции.
4. Программное обеспечение
На основе разработанного алгоритма сформировано программное обеспечение на языке C# в среде Microsoft Visual Studio 2005.
Разработан интерфейс пользователя, позволяющий вводить параметры постановки задачи, задавать параметры метода, использовать модификации алгоритма, контролировать шаги работы алгоритма с необходимой визуализацией, анализировать полученный результат и проводить серию одинаковых опытов для изучения работы алгоритма.
5. Примеры работы алгоритма
Для анализа эффективности алгоритма и сформированного программного обеспечения выбраны задачи минимизации типовых целевых функций: квадратичной, с линиями уровня в виде эллипсов, и функции Розенброка, с линиями уровня, имеющими овражную структуру.
Пример 1.
Дана функция f (x) = x2 + 2×2, x = (x1, x2) г. Множество допустимых решений
D = [- 1−3]x[-1−3]. Требуется найти минимум f (x) на множестве D.
Пусть NP = 30, N = 50, Mmin = 15, NImax = 25, w = 0,5- a = b = 0,5.
На рис. 1 показан общий вид интерфейса программы. Слева указываются значения параметров задачи (коэффициенты целевой функции, границы множества допустимых решений) и параметров метода (коэффициенты, определяющие пересчет скорости и положения каждой частицы в стае), справа графически отображается ход решения задачи (линии уровня целевой функции и положение частиц в стае), указываются параметры иллюстрации поиска решения. Имеются возможности производить вычисления по шагам с соответствующей иллюстрацией (рис. 2) или выполнить все шаги алгоритма и проанализировать полученное решение. Программа позволяет наблюдать текущую и наилучшую позиции каждой частицы, а
Рис. 1. Ввод параметров задачи
также ее скорость во время поиска решения (рис. 3).
Точное решение задачи известно — это точка х* = (0−0), значение функции в точке минимума I (х*) = 0. Нетрудно оценить точность приближенного решения, которое получается в результате работы алгоритма. Программа дает следующие значения (рис. 4 а): координаты точки минимума (3,110−6- 8 10−7), минимальное значение целевой функции 1,09 10−11. Таким образом, отклонение
решения, полученного программой, от истинного решения задачи имеет порядок 10−11.
к = 5 итераций к = 13 итераций
к = 24 итера- к = 36 итераций
ции
Рис. 3. Текущие данные о положении частиц в стае
Рис. 2. Промежуточные результаты решения примера 1
И М
Н
& gt- ы
1№ м
ы
а
Г& quot-

= _а
Г' п
Л м
— н
ы
м
н
с? | [¦ н
'¦стнтии) май
Рф#(*. «!
¦2. -Г •
В5 Ч И ММ (ДОМ
=з:
б
Рис. 4. Результаты решения примеров при к, а — пример 1- б — пример 2
а
Пример 2. Решим пример 1, но на этот раз будем использовать меньшее число соседей, т. е. N1 ш-п = 5, N1 тах = 10. Процесс поиска решения поясняет рис. 5.
Результат работы программы представлен на рис. 4 б: координаты точки минимума (-1,110−3--1,1 * 10−3), минимальное значение целевой функции равно 3,48 10−6. Таким образом,
отклонение приближенного решения, полученного программой, по величине функции от истинного решения задачи имеет порядок 10−6, т. е. в 105 раз больше, чем отклонение решения примера 1 с большим числом соседей. Рассмотренный пример показывает, что чем больше число опрашиваемых соседей, тем точнее получаемое решение.
Пример 3. Решим задачу минимизации функции Розенброка с рекомендуемыми параметрами метода (п. 1 замечаний и пример 1).
Дана функция I (х) = 100(х2 — х12) +(1 — х1)2, х = (х1, х2). Множество допустимых решений В = [- 1−3]х [-1−3]. Требуется найти минимум I (х) на множестве В.
Пусть Ш = 30, N = 50, Мтш = 15, N1 тах = 25, со = 0,5- а = Ь = 0,5.
Начало поиска к = 1 к = 13 итераций
к = 24 итераций к =36 итераций
Ґ& quot-

. & gt-
^ 002
Рис. 5. Промежуточные результаты решения примера 2
Рис. 6. Промежуточные результаты решения примера 3
Точное решение задачи известно: х* = (и/, /(х*) = 0. Результат работы программы (рис. 7): координаты точки минимума (0,79−0,62), минимальное значение целевой функции равно 0,04. Отклонение приближенного решения, полученного программой, от истинного решения задачи имеет порядок 10−2. Из приведенного примера видно, что овражная структура целевой функции оказывает существенное влияние на точность решения и предъявляет более жесткие требования к алгоритму поиска глобального экстремума, чем квадратичная зависимость. Модификации метода частиц в стае (п. 2 замечаний) повышают точность численного решения задачи.
Разработанное программное обеспечение позволяет сравнить различные модификации метода частиц в стае.
Рис. 7. Результат решения примера 3 при к = 50
Пример 4. Для исследования модификаций метода рассмотрим решение примера 3, но будем выполнять большее число итераций.
Дана функция f (x) = 100(х2 — x2)2 + (1 — хг)2, x = (xj, x2) T. Множество допустимых решений D = [-1- з]х [- 1- 3].
Требуется найти минимум f (x) на множестве D.
Пусть NP = 30, N = 300, Ж. = 15, N/x = 25, w = 0,5- a = B = 0,5.
j ] ] min 1 max 1 1 1 I 1
Задача была решена программой 100 раз методом частиц в стае, а затем его модификациями и комбинациями этих модификаций (табл. 1). Результат оценивался путем сравнения с точным решением x = (1,1)T. Если результат решения попадал в окрестность точки минимума радиусом e, то решение задачи считалось успешным.
Таблица 1
Модификация Параметры модификации Число успехов (из 100), e = 0,01 Число успехов (из 100), e = 0,001
-- -- 39 22
Применение формулы (3) для пересчета скорости g = 0,01 40 19
Применение формулы (4) для пересчета положения -- 21 4
Применение формул (3) и (4) g = 0,01 26 3
Использование локального поиска (5) nstep = 10 100 100
Применение формулы (3) для пересчета скорости и локального поиска (5) g = 0,01, nstep = 10 100 100
Как видно из приведенной табл. 1, использование локального поиска существенно улучшает метод частиц в стае и позволяет «обходить» овражную структуру функции Розенброка. Если повысить точность расчетов, то преимущество метода частиц в стае с локальным поиском над другими модификациями становится еще более очевидным.
При добавлении локального поиска точность повышается сразу на несколько порядков. Если модифицировать процедуру пересчета скорости, то отклонение от истинного решения задачи по величине функции имеет порядок 10−5, а если добавить еще и локальный поиск, то эта величина даже в худшей ситуации будет порядка 10−13, а для более благоприятных исходов она становится неразличимой для компьютера.
Заключение
Рассмотрен алгоритм решения задачи поиска глобального условного минимума функции с помощью метода частиц в стае. Разработано соответствующее программное обеспечение, работоспособность которого продемонстрирована на типовых примерах.
ЛИТЕРАТУРА
1. Eberhart, R.C. and Kennedy, J. A New Optimizer using Particle Swarm Theory, Proceedings Sixth Symposium on Micro Machine and Human Science, IEEE Service Center, Piscataway, NJ, 1995.
2. Mishra, S.K. Global Optimization by Differential Evolution and Particle Swarm Methods: Evaluation on Some Benchmark Functions, Munich Personal RePEc Archive (MPRA), 2006.
3. Пантелеев А. В., Летова Т. А. Методы оптимизации в примерах и задачах: Учеб. пособие. — М.: Высшая школа, 2008.
4. Kennedy, J. and Eberhart, R. Particle Swarm Optimization // Сайт в Интернете http: //www. engr. iupui. edu/~shi/Coference/psopap4. html.
ALGORITHMIC AND PROGRAM SUPPORT ELABORATION OF PARTICLE SWARM OPTIMIZATION
Panteleyev A.V., Alyoshina E.A.
The Particle Swarm Method applied to the conditional global extreme problem of multivariable function was considered. The detailed algorithm was formed and the efficient software based on it was created.
Сведения об авторах
Пантелеев Андрей Владимирович, 1955 г. р., окончил МГТУ им. Н. Э. Баумана (1978), доктор физико-математических наук, профессор, заведующий кафедрой математической кибернетики факультета прикладной математики и физики МАИ им. С. Орджоникидзе, автор более 110 научных работ, область научных интересов — методы синтеза оптимальных нелинейных систем управления, методы оптимизации.
Алешина Екатерина Александровна, 1988 г. р., студентка факультета прикладной математики и физики МАИ им. С. Орджоникидзе, область научных интересов — методы оптимизации, численные методы, статистическое моделирование.

ПоказатьСвернуть
Заполнить форму текущей работой