WWW.MASH.DOBROTA.BIZ
БЕСПЛАТНАЯ  ИНТЕРНЕТ  БИБЛИОТЕКА - онлайн публикации
 

«усреднения координат и метода роя частиц В. Д. Кошур Институт космических и информационных технологий, Сибирский федеральный университет, Красноярск, Россия e-mail: ...»

Вычислительные технологии Том 18, № 4, 2013

Глобальная оптимизация на основе гибридного метода

усреднения координат и метода роя частиц

В. Д. Кошур

Институт космических и информационных технологий,

Сибирский федеральный университет, Красноярск, Россия

e-mail: VKoshur@sfu-kras.ru

Представлен гибридный алгоритм глобальной оптимизации, в котором взаимно

дополняющими компонентами являются метод усреднения координат и метод роя

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

Ключевые слова: глобальная оптимизация, метод усреднения координат, метод роя частиц .

Введение Поиск решений нелинейных оптимизационных задач и особенно задач глобальной оптимизации (ГО) является одной из широко востребованных проблем вычислительной математики. В прикладных задачах целевая функция (ЦФ), как правило, имеет большое число переменных, не задана в аналитической форме и вычисляется как некоторая интегральная характеристика сложного динамического процесса (ЦФ-СДП), например, функция аэродинамического сопротивления проектируемого летательного аппарата .

Разработка эффективных методов, в определённой степени адаптивных к характеру изменяемости ЦФ, особенно актуальна в связи с развитием вычислительной техники и возможности использования параллельных вычислительных систем. Общие базовые положения по данной тематике приведены в работах [1 – 6], где рассмотрены оригинальные подходы и обзоры различных численных методов и их модификаций для решения задач оптимизации и ГО, а также в [7, 10], в которых представлены методы на основе неравномерных покрытий, реализованные как параллельные вычислительные алгоритмы ГО. Кроме того, необходимо отметить относительно новое направление исследований и построения алгоритмов ГО на основе методов интервального анализа, подробно изложенное в монографии [11] .



В настоящей работе основное внимание уделено ряду методов “нулевого порядка”, согласно которым путём вычислительного алгоритма определяются значения ЦФ только в пробных точках, с ориентацией в дальнейшем на решение задач с ЦФ-СДП при минимальных требованиях к непрерывности и ограниченности ЦФ. Для приближённых оценок изменяемости ЦФ используются значения максимумов величин, полученных как отношения разности значений ЦФ к расстоянию для всех пар пробных точек (нижняя оценка константы Липшица) .

Глобальная оптимизация на основе гибридного метода... 37

Наиболее востребованными в практических приложениях, по мнению автора, являются следующие детерминированные, стохастические и эвристические методы:

методы на основе различных вариантов генетического алгоритма (ГА), эволюционных вычислений и их модификаций [12 – 18];

методы на основе роя частиц Particle Swarm Optimization (PSO) с введением адаптационных модификаций [19 – 22];

методы случайного поиска и моделирования отжига [23 – 26];

метод усреднения координат [5] и методы на основе инверсных регрессий [27 – 31];

методы, основанные на оценках константы Липшица, неравномерных покрытий [6 – 10] и диагональные методы [32 – 36] .

Перечисленные методы имеют как сильные, так и слабые стороны. В настоящей работе предлагается гибридный метод ГО на основе сочетания метода усреднения координат и PSO. Это позволяет в методе усреднения координат перейти от случайного выбора пробных точек к использованию текущих координат роя частиц, коллективное движение которых происходит адаптивно, подстраиваясь под характер изменения ЦФ, а при движении роя частиц учитывать их смещения в направлении найденного усреднённого центра на основе метода усреднения координат. Таким образом, осуществляется взаимодействие двух методов. Дополнительным приёмом, ускоряющим процесс сходимости гибридного алгоритма, является включение в процесс вычислений нескольких шагов процедуры Хука Дживса, уточняющих текущие координаты лучшей и/или худшей частицы в рое .



Следует отметить, что предлагаемый гибридный метод, как и одна из его составляющих, PSO, не дает 100%-й гарантии нахождения глобального минимума ЦФ. Его результаты носят вероятностный характер. Данный метод пока не претендует на “промышленное” использование. Для этого необходимо проведение большого объёма вычислений, сравнительного анализа, статистической обработки результатов с использованием стандартизованных каталогов тестовых функций. Ниже описываются один из вариантов реализации гибридного метода и результаты проведённых вычислительных экспериментов для трёх специально выбранных тестовых функций. Эти численные результаты носят главным образом иллюстративный характер и позволяют в определённой степени оценить работоспособность метода .

1. Гибридный метод Рассматривается ограниченная непрерывная функция f (x) : R, где x = (x1, x2,..., xn ) Rn. Множество является областью допустимых значений переменных и в простейшем случае представляет n-мерный параллелепипед с заданными [0] [0] сторонами xi di, xi + di, i = 1, 2,..., n. Необходимо найти приближённое значение глобального минимума f и хотя бы одну точку x, в которой это значение достигается с заданной допустимой погрешностью f для значений целевой функции:

–  –  –

Предполагая, что для пробных точек текущих координат роя частиц в формулах (4), (5) при реализации приближённого интегрирования можно выбрать подобласти так, чтобы величины их объёмов V (j)[k], j = 1, 2,..., M [k], были приблизительно равными, расчётные формулы упрощаются к виду

–  –  –

Следует отметить, что для вычислительного алгоритма усреднения координат [5] конкретный вид подобластей дискретизации области интегрирования [k] является не существенным, поэтому использование более простых при численной реализации соотношений (7), (8) вместо (4), (5) вполне оправданно .

Адаптивное изменение координат роя частиц при переходе на (k + 1)-й шаг проводится по схеме PSO [19 – 22], и дополнительно вводится составляющая движения к усреднённому центру координат x[k] для каждой j-й частицы роя в следующей форме:

–  –  –

2. Результаты вычислительных экспериментов Для наглядного представления работы предлагаемого гибридного алгоритма ниже в графической форме приведены результаты вычислительного процесса поиска глобального минимума для трёх тестовых функций .

На рис. 1 показаны результаты процесса минимизации функции двух переменных вида Рис. 1. Результаты процесса минимизации целевой функции (12) гибридным алгоритмом Глобальная оптимизация на основе гибридного метода... 41

–  –  –





в прямоугольной области [12, 8] [15, 5] после 100 итераций (здесь точки и пунктирные линии соответственно промежуточные положения и траектории 25 частиц в рое) .

Стартовые координаты частиц задавались в узлах регулярной сетки 5 5 расчётной области, значения коэффициентов = 0, 0 = 0.1, 1 = 0, 2 = 0, 3 = 0.2; при этом достигнутое значение параметра селективности s = 212. Сплошной ломаной линией с маркерами показаны положения точек на поверхности функции для последовательно уточняемых значений усреднённых координат x[k]. Проведено 100 запусков программы, приемлемая точность (порядка 102 ) по значениям координат лучшей частицы достигалась за 10–15 итераций, в дальнейшем происходила последовательная концентрация частиц в окрестности глобального минимума. Следует отметить, что метод является статистическим и для получения “надежного результата по вероятности” необходимо проведение многократных запусков программы с измененными значениями случайных векторов U[0, ] .

На рис. 2 представлены карта изолиний целевой функции (12) и результаты поиска глобального минимума при аддитивной случайной помехе с равномерным распределением, составляющей 20 % амплитуды изменения значений ЦФ (здесь пунктирные линии траектории частиц, сплошная линия изменение усреднённых координат) .

В расчёте использовано 36 частиц со стартовыми значениями в узлах регулярной сетки 6 6 расчётной области .

–  –  –

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

Переход к большим размерностям варьируемых переменных приводит к необходимости экспоненциального роста количества пробных точек или частиц в рое. Возможность проведения параллельных вычислений указывает на целесообразность использования в алгоритме нескольких семейств роев частиц. На рис. 4 показаны результаты итерационного процесса вычисления глобального минимума после 10 итераций для размерности n = 50 негладкой четырехэкстремальной функции вида

–  –  –

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

–  –  –

уточнялись процедурой Хука Дживса с начальным шагом h0 = 1.1 и числом внутренних итераций, равным пяти, параметры гибридного алгоритма приняты следующими:

= 0.4, 0 = 1.0, 1 = 0, 2 = 1.0, 3 = 2.0 .

Для данного варианта расчёта на рис. 5 представлены распределение значений целевой функции по частицам одного роя и значения координат лучшей частицы (с номером 37), которая достигла глобального минимума в точке x = 0 .

Рис. 4. Минимизация функции (14) при n = 50: 1 изменение максимальных значений ЦФ в списке частиц, 2 изменение значений ЦФ в улучшаемых усреднённых координатах, 3 изменение минимальных значений ЦФ в списке частиц a

–  –  –

Рис. 6. Движение 36 частиц одного роя и изменение усреднённых координат в вычислительном процессе минимизации функции (14) для двух переменных Проведённые вычислительные эксперименты по минимизации функции (14) при n = 100 показали, что если общее количество частиц не увеличивать, то гибридный алгоритм приводит к одному из локальных минимумов, чаще всего попадая в точку, где все координаты равны 2. Это объясняется тем, что данный локальный минимум имеет наиболее широкую область притяжения (последнее слагаемое в формуле (14)), в силу чего с большей вероятностью хотя бы одна из частиц попадает в указанную область и оказывает максимальное влияние на дальнейшее поведение роя частиц .

Для наглядности вид поверхности ЦФ (14) и вычислительный процесс минимизации для двух переменных показан на рис. 6. В этом вычислительном эксперименте было использовано 36 частиц одного роя с начальным положением частиц в узлах регулярной сетки 6 6 .

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

Заключение Представлены гибридный метод глобальной оптимизации на основе сочетания методов роя частиц и усреднения координат и его модификации с использованием нескольких роев частиц и включением процедуры Хука Дживса. Для целевых функций с большим количеством переменных и высоким значением константы Липшица, как правило, Глобальная оптимизация на основе гибридного метода... 45 требуется эффективный выбор параметров алгоритма [37]. Предполагается дальнейшая разработка гибридного метода с нейросетевой подстройкой изменения параметров алгоритма, т. е. адаптивное управление этими параметрами, в частности, когда каждый из роев частиц осуществляет поиск самостоятельно и в то же время периодически обменивается информацией об успешном поиске с другими роями частиц по аналогии с компьютерной технологией мультиагентных систем [38]. Это направление исследований может стать определённой альтернативой экспоненциальному увеличению количества пробных точек при решении оптимизационных задач большой размерности .

Список литературы [1] Растригин Л.А. Статистические методы поиска. М.: Наука, 1968 .

[2] Сухарев А.Г. Глобальный экстремум и методы его отыскания. М.: Изд. МГУ, 1981 .

[3] Жиглявский А.А., Жилинскас А.Г. Методы поиска глобального экстремума. М.:

Наука, 1991 .

[4] Horst R., Pardalos P.M., et al. Handbook of Global Optimization. Dordrecht: Kluwer, 1995 .

[5] Рубан А.И. Глобальная оптимизация методом усреднения координат. Красноярск: ИПЦ КГТУ, 2004. 302 с .

[6] Евтушенко Ю.Г. Методы решения экстремальных задач и их применение в системах оптимизации. М.: Наука, 1982. 432 с .

[7] Евтушенко Ю.Г., Малкова В.У., Станевичюс А.А. Параллельный поиск глобального экстремума функций многих переменных // Журн. вычисл. математики и матем .

физики. 2009. Т. 49, № 2. С. 255–269 .

[8] Евтушенко Ю.Г., Жадан В.Г. Об одном подходе реализации численных методов нелинейного программирования // Изв. АН СССР. Техническая кибернетика. 1983. № 1 .

С. 47–59 .

[9] Евтушенко Ю.Г., Посыпкин М.А. Применение метода неравномерных покрытий для глобальной оптимизации частично целочисленных нелинейных задач // Журн. вычисл .

математики и матем. физики. 2011. Т. 51, № 8. С. 1376–1389 .

[10] Евтушенко Ю.Г. Численный метод поиска глобального экстремума функций (перебор на неравномерной сетке) // Там же. 1971. Т. 11, № 6. С. 1390–1403 .

[11] Хансен Э., Уолстер Дж.У. Глобальная оптимизация с помощью методов интервального анализа. М.; Ижевск: НИЦ “Регулярная и хаотическая динамика”, Институт компьютерных исследований, 2012. 516 с .

[12] Holland J.H. Adaptation in Natural and Articial System. Ann Arbor: Univ. of Michigan Press, 1975 .

[13] Goldberg D.E. Genetic Algorithms in Search, Optimization, and Machine Learning .

Addison-Wesley, 1989 .

[14] Курейчик В.М. Генетические алгоритмы. Состояние. Проблемы. Перспективы // Изв .

РАН. Теория и системы управления. 1999. № 1. С. 144–160 .

[15] Michalewicz Z. Genetic Algorithm + Data Structures = Evolution Programs. 3rd Edn. New York: Springer-Verlag, 1996 .

46 В. Д. Кошур [16] Stom R., Price K. Dierential evolution a simple and ecient heuristic for global optimization over continuous spaces // J. of Global Optimizat. 1997. Vol. 11. P. 341–359 .

[17] Кошур В.Д., Ильин В.А. Нейронная сеть Хопфилда как кроссовер генетического алгоритма // V Всероссийская научно-техн. конф. “Нейроинформатика-2003”. Сб. науч. тр .

Ч. 1. М.: МИФИ, 2003. С. 92–100 .

[18] Рутковская Д., Пилинский М., Рутковский Л. Нейронные сети, генетические алгоритмы и нечеткие системы. М.: Горячая линия Телеком, 2004 .

[19] Kennedy J., Eberhard R. Particle swarm optimization // Proc. of IEEE Intern. Conf. on Neural Networks. 1995. Vol.4. P. 1942–1948 .

[20] Mendes R., Kennedy J., Neves J. The fully informed particle swarm: Simpler, maybe better // IEEE Trans. on Evolutionary Comput. 2004. Vol. 8. P. 204–210 .

[21] Kennedy J., Mendes R. Neighborhood topologies in fully informed and best-of-neighborhood particle swarms // Systems, Man, and Cybernetics. 2006. Vol. 36. P. 515–519 .

[22] Карпенко А.П., Селиверстов Е.Ю. Обзор методов роя частиц (particle swarm optimization) // Электронное научно-техн. издание “Наука и образование”. 2009. № 3 .

http://technomag.edu.ru/doc/116072.html .

[23] Aarts E.N.L., Laarhoven P.J.M. Simulated Annealing: Theory and Applications. London:

Kluwer, 1987 .

[24] Ali M., Storey C. Aspiration based simulated annealing algorithm // J. of Global Optimizat .

1996. No. 11. P. 181–191 .

[25] Hamma B., Viitanen S., Torn A. Parallel continuous simulated annealing for global optimization // Optimization Methods and Software. 2000. Vol. 13, No. 2. P. 93–116 .

[26] Орлянская И.В. Современные подходы к построению методов глобальной оптимизации // Электронный журнал “Исследовано в России”. 2002. С. 2097–2108 .

http://zhurnal.ape.relarn/ru/articles/2002/189.pdf .

[27] Кошур В.Д. Адаптивный алгоритм глобальной оптимизации на основе взвешенного усреднения координат и нечётко-нейронных сетей // Нейроинформатика. Электронный рецензируемый журнал. 2006. Т. 1, № 2. С. 106–124 .

http://www.niisi.ru/iont/ni/Journal/N2/Koshur.pdf .

[28] Кошур В.Д., Пушкарёв К.В. Глобальная оптимизация на основе инверсных соотношений и обобщённо регрессионных нейронных сетей // X Всероссийская научно-техн. конф .

“Нейроинформатика-2008”. Сб. науч. тр. Ч. 2. М.: МИФИ, 2008. С. 182–192 .

[29] Koshur V., Kuzmin D., Legalov A., Pushkaryov K. Solution of large-scale problems of global optimization on the basis of parallel algorithms and cluster implementation of computing processes // Parallel Comput. Technolog. 10th Intern. Conf., PaCT 2009. Springer, 2009 .

P. 121–125 .

[30] Кошур В.Д., Пушкарёв К.В. Дуальные обобщённо-регрессионные нейронные сети для решения задач глобальной оптимизации // XII Всероссийская научно-техн. конф .

“Нейроинформатика-2010”. Сб. науч. тр. Ч. 2. М.: НИЯУ МИФИ, 2010. С. 219–227 .

[31] Кошур В.Д., Пушкарёв К.В. Глобальная оптимизация на основе нейросетевой аппроксимации инверсных зависимостей // XIII Всероссийская научно-техн. конф .

“Нейроинформатика-2011”. Сб. науч. тр. Ч. 1. М.: НИЯУ МИФИ, 2011. С. 89–98 .

[32] Стронгин Р.Г. Поиск глобального минимума. М.: Знание, 1990 .

Глобальная оптимизация на основе гибридного метода... 47 [33] Нефёдов В.Н. Некоторые вопросы решения липшицевых задач глобальной оптимизации с использованием метода ветвей и границ // Журн. вычисл. математики и матем. физики .

1992. Т. 32, № 4. С. 512–529 .

[34] Hansen P., Jaumard B. Lipschitz optimization // Handbook of Global Optimization / Eds .

R. Horst, P.M. Pardalos. 1995. Vol. 1. P. 407–493 .

[35] Sergeyev Y.D. On convergence of “Divide the Best” global optimization algorithms // Optimization. 1998. Vol. 44, No. 3. P. 303–325 .

[36] Сергеев Я.Д., Квасов Д.Е. Диагональные методы глобальной оптимизации. М.: ФИЗМАТЛИТ, 2008 .

[37] Pedersen M.E.H. Tuning & Simplifying Heuristical Optimization: Thesis for the degree of Doctor of Philosophy. Univ. of Southampton, School of Eng. Sci., Comput. Eng. and Design Group, 2010. 204 p .

[38] Shoham Y., Leyton-Brown K. Multiagent Systems. Algorithmic, Game-Theoretic, and Logical Foundations. Cambridge Univ. Press, 2009 .

–  –  –






Похожие работы:

«Федеральное государственное бюджетное образовательное учреждение высшего профессионального образования "Тихоокеанский государственный университет" А. С. Зуфарова ПРОГРАММИРОВАНИЕ В VISUAL BASIC. Утверждено издательско-библиотечным советом университета в к...»

«2017-2018 Основы программной инженерии 7-ой семестр Лекции Технологии разработки ПО 9-ый семестр Лекции Курсовой проект 10-ый семестр Лекции Курсовой проект Ицыксон В.М. ТРПО/ОПИ © 2017-2018 Предшествующие дисциплины Алгоритмизация и программир...»

«Вступительное слово В этой книге, первое издание которой стало библиографической редкостью сразу после выхода в 1993 году, выдающийся ученый Валентин Федорович Турчин излагает свою концеп...»

«Информационное обеспечение науки: новые технологии СИСТЕМА УПРАВЛЕНИЯ ЭЛЕКТРОННОЙ БИБЛИОТЕКОЙ LIBMETA * Серебряков В.А., Филиппов В.И., Каленкова А.А. (Вычислительный центр им. А.А. Дородницына РАН) C 2007 года в ВЦ РАН ведутся работы по созданию СУЭБ в рамках ЕНИП под названием LibMeta, которая предлагает библиотекам, архивам и музеям РАН унифициро...»

«А.А.Быков Программирование на языке С++ А.А.Быков Сборник задач по программированию с решениями, часть 2 А.А.Быков Сборник задач по программированию с решениями, часть 2. 1 Общие положения Сентябрь2008-январь 2009 Часть 2, С...»

«МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РОССИЙСКОЙ ФЕДЕРАЦИИ федеральное государственное бюджетное образовательное учреждение высшего образования "РОССИЙСКИЙ ГОСУДАРСТВЕННЫЙ ГИДРОМЕТЕОРОЛОГИЧЕСКИЙ УНИВЕРСИТЕТ" Кафедра промысловой океанологии и охраны природных в...»

«УТВЕРЖДАЮ Директор ИК Д. М. Сонькин "_" 09 2017 г. РАБОЧАЯ ПРОГРАММА ДИСЦИПЛИНЫ БАЗОВАЯ ЦИФРОВАЯ ОБРАБОТКА СИГНАЛОВ 09.03.01 Направление ООП Информатика и вычислительная техника Информационно-коммуникационные Профили подготовки технологии Квалификация Бакалавр Базовый учебный план приема (год)...»




 
2019 www.mash.dobrota.biz - «Бесплатная электронная библиотека - онлайн публикации»

Материалы этого сайта размещены для ознакомления, все права принадлежат их авторам.
Если Вы не согласны с тем, что Ваш материал размещён на этом сайте, пожалуйста, напишите нам, мы в течении 1-2 рабочих дней удалим его.