Исследование и разработка алгоритмов и комплекса программ для реализации модифицированного метода поиска глобального экстремума функции многих переменных тема диссертации и автореферата по ВАК РФ 05.13.18, кандидат технических наук Жадан, Игорь Витальевич

• Жадан, Игорь Витальевич
• кандидат технических наук
• 2011

Оглавление диссертации кандидат технических наук Жадан, Игорь Витальевич

ВВЕДЕНИЕ.

ГЛАВА 1. ОБЗОР МЕТОДОВ ГЛОБАЛЬНОЙ ОПТИМИЗАЦИИ, НЕДОСТАТКИ И ПЕРСПЕКТИВЫ РАЗВИТИЯ.

1.1 Задача глобальной оптимизации и практическая ценность

1.2 Обзор методов глобальной оптимизации. Преимущества и недостатки.

1.3 Задача поиска глобального экстремума функции многих переменных методов половинных делений и его недостатки.

Выводы по главе

ГЛАВА 2. РАЗРАБОТКА И ТЕХНИКА ПРОГРАММНОЙ РЕАЛИЗАЦИИ МОДИФИКАЦИЙ МЕТОДА ПОЛОВИННЫХ ДЕЛЕНИЙ ДЛЯ ПОИСКА ГЛОБАЛЬНОГО ЭКСТРЕМУМА.

2.1 Модификация метода половинных делений (деление на 2т параллелепипеда).

2.2 Модификация метода половинных делений - использование метода сопряженных градиентов в методе половинных делений

2.3 Общая схема работы программного комплекса для поиска глобального экстремума функции многих переменных (для однопроцессорной ЭВМ).

2.4 Архитектура систем параллельной обработки данных.

2.5 Алгоритм распараллеливания вычислительного процесса реализованного метода.

Выводы по главе 2.

ГЛАВА 3. ЭКСПЕРИМЕНТАЛЬНЫЕ ИССЛЕДОВАНИЯ ПРОГРАММНОГО КОМПЛЕКСА И ЕГО ПРАКТИЧЕСКОЕ ИСПОЛЬЗОВАНИЕ В АКУСТООПТИКЕ.

3.1 Особенности работы программного комплекса в среде параллельных вычислений.

3.2 Тестирование программного комплекса.

3.3 Задача о минимизации функционала качества для обгонного и обменного взаимодействия солитонов.

Выводы по главе 3.

Введение диссертации (часть автореферата) на тему «Исследование и разработка алгоритмов и комплекса программ для реализации модифицированного метода поиска глобального экстремума функции многих переменных»

Актуальность темы. В настоящее время одной из актуальных задач математического моделирования являются задачи рационального выбора, и в частности, задачи оптимизации [1-8]. Многоэкстремальная оптимизация и поиск глобального экстремума функции многих переменных занимает важное мето среди задач оптимизации [9-30].

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

На сегодняшний день существует значительное число различных подходов к решению задач глобальной оптимизации. Среди них можно отметить методы: случайного поиска; представления функций в виде суммы выпуклой и вогнутой составляющих; неравномерного покрытия; различные варианты метода ветвей и границ; методы, основанные на одномерной глобальной оптимизации и многие другие. Отечественные и зарубежные ученные, такие как Ю.Г. Евтушенко, С.Н. Пиявский, В.П. Булатов, Р.Г. Стронгин, Я.Д. Сергеев, А.Г. Жилинскас, A.C. Стрекаловский, Р. Хорст, X. Туй, A.M. Рубинов, И. Торн, П. Пардалос, К. Флоудас внесли значительный вклад в развитие теории и методов глобальной оптимизации.

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

Одним из наиболее плодотворных направлений глобальной оптимизации является идея неравномерных покрытий допустимого множества. В 1971 году опубликовал одну из первых научных работ Евтушенко Ю.Г. "Численный метод поиска глобального экстремума функций (перебор на неравномерной сетке)" ЖВМ и МФ, 1971. 11 (6). С. 1390-1400, посвященную поиску глобального экстремума функций многих переменных с помощью неравномерных покрытий допустимого множества. Это направление в дальнейшем нашло плодотворное развитие. В статье Евтушенко Ю.Г. "Численный метод отыскания наилучших гарантированных оценок." ЖВМ и МФ, 1972. 12 (1). С. 89— 104, метод был перенесен на нахождение гарантированных оценок в многошаговых играх, в статье Евтушенко Ю.Г., Потапов М. А. "Методы решения многокритериальных задач."Доклады Академии наук СССР, 1986. Т. 291. N 1, С. 25-39.- на построение эпсилон-сети Паретовского множества. В статье Евтушенко Ю.Г., Ратькин В. А. "Метод половинных делений для глобальной оптимизации функции многих переменных." Техническая кибернетика, 1987, (1). С. 119-127, развивавшей метод неравномерных покрытий, был получен метод бисекций. Интерес к этому направлению значительно возрос в последнее время в связи с разработкой новых высокопроизводительных ЭВМ, основанных на параллельной и конвейерной организации расчётов.

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

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

Стоит отдельно отметить задачи нахождения глобального экстремума липшицевой функции, как один из наиболее важных классов задач, рассматриваемых в глобальной оптимизации. В последние десятилетия для решения этих задач были предложены несколько эффективных численных методов, в частности, Ю.Г.Евтушенко был разработан метод половинных делений; A.M. Рубиновым, М.Андрамоновым, Б.Гловером — метод секущих углов. С помощью метода половинных делений были разработаны также варианты модификации метода половинных делений, предназначенные для решения задач с ограничениями. В перечисленных выше методах всегда возникает проблема выбора штрафных коэффициентов: при их увеличении возрастает константа Липшица, снижая тем самым эффективность большинства методов поиска глобального экстремума, в том числе и метода половинных делений.

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

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

Целью работы является повышение производительности вычислений при поиске глобального экстремума функции многих переменных на основе совершенствования метода половинного деления для нахождения безусловного и условного глобального экстремума функций при решении задач в распределенной вычислительной среде. Для достижения цели необходимо решить следующие задачи: 1. Модифицировать метод половинного деления для решения задачи условной глобальной оптимизации на основе использования специальной вспомогательной функции с целью достижения возможности дальнейшего использования алгоритмов распределенной обработки данных при его реализации.

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

3. Реализовать предложенный алгоритм модифицированного метода поиска глобального экстремума в программном комплексе.

4. Протестировать и применить разработанные алгоритмы на практических и прикладных задачах.

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

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

2. Предложен алгоритм реализации модифицированного метода половинного деления для решения задачи глобальной оптимизации, позволяющий использовать параллельную обработку данных, что приводит к сокращению времени вычислений по сравнению с существующими аналогами в 1,3-1,5 раза.

3. С помощью разработанного программного комплекса проведена минимизация, функционала качества для обменного и обгонного взаимодействия солитонов.

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

Апробация работы. Основные результаты диссертации докладывались и обсуждались на Международной научно-технической конференции «Международный форум молодых ученых и студентов» (Турция, 2004г.), Научной конференции «Современные наукоемкие технологии» (Испания, 2005г.), Юбилейной конференции РАЕ «Современные проблемы науки и образования» (Москва, 2005г.), Международных XXX, XXXI НТК «Гагаринские чтения» (Москва, 2006, 2009 г.).

Заключение диссертации по теме «Математическое моделирование, численные методы и комплексы программ», Жадан, Игорь Витальевич

ВЫВОДЫ ПО РАБОТЕ

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

1. Модифицирован метод поиска глобального экстремума путем разбиения на п - параллелепипедов (п кратное 2).

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

3. Разработан алгоритм распараллеливания модифицированных методов поиска глобального экстремума.

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

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

Список литературы диссертационного исследования кандидат технических наук Жадан, Игорь Витальевич, 2011 год

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

2. Пиявский С.А. Один алгоритм отыскания абсолютного экстемума функции // Журнал вычисл. матем. и матем. физики, 1972. Т. 12. № 4. С. 888-896.

3. Черноусько Ф. JI. Об оптимальном поиске экстремума унимодальных функций // Журнал вычислительной математики и математической физики. 1970, т. 10.

4. Черноусько Ф. Л. Об оптимальном поиске минимума выпуклых функций // Журнал вычислительной математики и математической физики. 1970, т. 10.

5. Кузнецов А. Г., Черноусько Ф. Л. Об оптимальном управлении, минимизирующем экстремум функции фазовых координат //Кибернетика. 1968. № 3. С. 50 -55.

6. Стронгин Р.Г. Численные методы в многоэкстремальных задачах. М.: Наука, 1978.

7. Нефедов В.Н. Отыскание глобального максимума функции нескольких переменных на множестве, заданном ограничениями типа неравенств // Журнал вычисл. математики и матем. физики, 1987. Т. 27. № 1.С. 35-51.

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

9. Гергель В.П. Алгоритм глобального поиска, использующий производные // Динамика систем и оптимизация. Нижний Новгород: ННГУ, 1992. С. 161-178.

10. Я.Д.Сергеев, Д.Е.Квасов. Диагональные методы глобальной оптимизации. //ФИЗМАТЛИТ 2008. стр.9-14.

11. A.M.Rubinov and B.M.Glover. Increasing convex along rays functions with applications to global optimization. — Research Report 21/96, University of Ballarat, 1996.

12. Rinnoy Kan, A.H.G., Timmer, G.T. Stocactic global optimization methods //Mathematical programming. 39, 27-28, 1987.

13. Torn A. Global Optimization as a Combination of Global and Local Search // Turku, Abo Akademi University, HHAA A: 13, 1974.

14. Torn A., Viitanen S. Topographical Global Optimization // Floudas C.A., Pardalos P.M. (eds): Recent Advances in Global Optimization. Princeton University Press, 384-398, 1992.

15. T6rn A., Viitanen S. Topographical Global Optimization Using Pre-Sampled Points // Journal of Global Optimization, Vol 5, No 3, 267-276, 1994.

16. Evtushenko Yu. G., Potapov M. A., Korotkich V. V. Recent Advances in Global Optimization // Prinston, Princeton University Press, 274-297, 1992.

17. Moore R. Interval Analysis // New Jersey, Prentice-Hall, 1966.

18. Nemhauster G.L., Pruul E.A., Rushmeier R.A. Branch-and-bound and Parallel Computation: a Historical Note // Oper. Res. Let., 7, 65-69, 1988.

19. Gomez S., Levy A.V. The Tunneling Method Applied to Global Optimization // SIAM, Numerical Optimization (Boggs, P.T., ed.), 213244, 1985.

20. Metropolis N., Rosenbluth A., Rosenbluth M., Teller A., Teller E. Equation of State Calculations by Fast Computing Machines // J. Chem. Phys. Vol. 21, No. 6, 1087-1092, 1953.

21. Aarts E.H.L., van Laarhoven PJ.M. Simulated Annealing: Theory and Applications // London, Kluwer, 1987.

22. АИ M., Storey C. Aspiration Based Simulated Annealing Algorithm // J. of Global Optimization 11, 181-191, 1996.

23. Hamma В., Viitanen S., A. Torn. Parallel Continuous Simulated Annealing for Global Optimization // Optimization Methods and Software, Vol. 13, №2, 93-116, 2000.

24. Michalewicz Z. Genetic Algorithms + Data Structures = Evolution Programs (3rd Edn.) // New York, Springer-Verlag, 1996.

25. Price W.L. A Controlled Random Search Procedure for Global Optimization // The Computer Journal, 20, 367-370, 1977.

26. AH M., Torn A., Viitanen S. A Numerical Comparison of Some Modified Controlled Random Search Algorithms // J. of Global Optimization 11, 377-385, 1997.

27. Rubinov A. Andramonov M. Lipschitz programming via increasing convex-along-rays functions // Optimization Methods and Software, 1999. V. 10. P. 763-781.

28. С.С.Кутателадзе, А.М.Рубинов. Двойственность Минковского и ее приложения. ~ Новосибирск: Наука, 1976.

29. Pallachke D., Rolewicz S. Foundations of Mathematical Optimization (Convex Analysis without Linearity). Kluwer Academic Publishers, Dordrecht, 1997.

30. Singer I. Abstract Convex Analysis. New York: Willey \& Sons, 1997.

31. A.M.Rubinov. Abstract Convexity and Global Optimization. Dordrecht, Kluwer Academic Publishers, 2000.

32. J. Kelley. The cutting plane method for solving convex programs // SIAM Journal, 1960. V. 8, № 4. P. 703-712.

33. Анциферов Е.Г., Ащепков Л.Е., Булатов В.П. Методы оптимизации и их приложения. 4.1. Математическое программирование. Новосибирск: Наука, 1990.

34. Хамисов О.В. Глобальная оптимизация функций с вогнутой минорантой // Журнал вычисл. математики и матем. физики. 2004. Т. 44. №9. С. 1552-1563.

35. А.Р.Ершов, О.В.Хамисов. Автоматическая глобальная оптимизация //. Дискретный анализ и исследование операций. 2004. Серия 2. T.l 1, № 2. С 45-68.

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

37. Гроссман К., Каплан А.А. Нелинейное программирование на основе без условной минимизации. Новосибирск: Наука, 1981.

38. Сухарев А.Г., Тимохов А.В., Федоров В.В. Курс методов оптимизации. М.: Наука, 1986.

39. D.D. Morrison, Optimization by least squares // SIAM J. Numer. Analysis, 1968. № 5. P. 83-88.

40. J. Kowalik, M.R. Osborn and D.M. Ryan, A new method for constrained optimization problems // Operat. Res., 1969. V. 17. P. 973-989.

41. Докл. АН СССР. 1967. Т.-173, №-4. С.-748-751. 46.Евтушенко Ю.Г., Жадан В.Г. Точные вспомогательные функции в задачах оптимизации // Журнал вычисл. матем. и матем. физики,1990. Т. 30. № 1. С.31-42.

42. Evtushenko Yu.G., Rubinov A.M. and Zhadan V.G. General Lagrangetype functions in constrained global optimization. Part II: Exact auxiliary functions // Optimization ' 48.Methods and Software, 2002. Vol. 16, № 1-4. P. 231-256.

43. A.M.Bagirov and A.M.Rubinov. Global minimization of increasing positively homogeneous functions over the unit simplex, Research Report 99/37, University of Ballarat, 1999.

44. Gourdine E., Jaumard В., Ellaia R. Global optimization of Holder functions // J. Global Optim. 1996. V.8, N 4. P.323-348.

45. Сухарев А.Г. Минимаксные алгоритмы в задачах численного анализа. М.: Наука, 1989.

46. Hansen P., Jaumard В., Lipschitz optimization // Handbook of global optimization. Dordrecht: Kluwer Acad. Publ., 1995. P. 407-494

47. Horst R., Nast M., Thoai N.Y. New LP bound in multivariable Lipschitz optimization: theory and applications // J. Optim. Theory Appl. 1995. V. 86, №2. P. 369-388

48. Pinter J. Global optimization in action. Dordrecht: Kluwer Acad. Publ., 1996.

49. Sergeev Ya.D. An one-dimensional deterministic global optimization algorithm. // Журн. вычисл. математики и матем. физики. 1995. Т. 35, №5. Р. 705-717

50. Wood G.R., Zhang В.Р. Estimation of the Lipschitz constant of a function // J. Global Optim. 1996. V.8, N 1. P. 91-103.

51. Baritompa W. Accelerations for a variety of global optimization methods // J. Global Optim. 1994. V.4, N 1. P. 37-45.

52. Breiman L., Cutler A. A deterministic algorithm for global optimization // Math. Program. 1993. V. 58, N 2, P. 179-199.

53. Gergel V.P. A global optimization algorithm for multivariable functions with Lipschitzian first derivatives // J. Global Optim. 1997. V.10, N 3. P. 257-281.

54. Коршунов Ю.М., Коршунов Ю.М. Математические основы кибернетики. — М.: Энергоатомиздат, 1972.Максимов Ю.А.,Филлиповская Е.А. Алгоритмы решения задач нелинейного программирования. — М.: МИФИ, 1982.

55. Сухарев А.Г., Подобедов В.Е., Алгоритм поиска глобального максимума функции нескольких переменных. // Вычислительные комплексы и моделирование сложных систем. М.: МГУ, 1989. С. 124-134.

56. Брайсон А., Хо Ю-Ши. Прикладная теория оптимального управления

57. Шнитман В., Отказоустойчивые компьютеры компании Stratus // Открытые Системы № 1 1998

58. Дубова Н., Суперкомпьютеры nCube // Открытые Системы № 2 1995

59. Макстеник М., Сравнение сетевых архитектур // Сети № 2 1997

60. Французов Д., Оценка производительности вычислительных систем // Открытые Системы № 2 1996

61. Французов Д., Оценка производительности суперкомпьютеров // Открытые Системы № 6 19956 8. Воеводин В.В., Параллельная обработка данных, htlp://w\vw.parallel.ru/wv/

62. Комолкин A.B., Немнюгин С.А., Программирование для высокопроизводительных ЭВМ, http://vvww.hpc.nw.ru/COURSES/HPC/

63. Кркжов В.А., Операционные системы распределенных вычислительных систем (распределенные ОС), http://www.parallel.ru/krukov/

64. Ian Foster, Designing and Building Parallel Programs, http://rsusu 1 .rnd.runnet.ru/tutor/design/dbpp/text/book.html

65. Booth S., MacDonald N., Perfomance Optimization, http://www.hpc.nw.ru/COURSES/

66. Спыну С.К. Поиск глобального экстремума с использованием параллельных вычислений. Сб. трудов Международной НТК «XXX Гагаринские чтения», (Москва, 6-10 апреля 2004 г.). — М.: «МАТИ» -РГТУ им. К.Э.Циолковского, 2004, т.5, с.101

67. Спыну С.К. Поиск глобального экстремума с использованием параллельных вычислений. «Успехи современного естествознания» 2004, №7, с. 94,94.

68. Беневоленский Д.С., Жадан И.В., Спыну С.К. Использование параллельных вычислений при расчете метода половинных делений для глобальной оптимизации функции многих переменных. «Успехи современного естествознания» 2005, №7, с. 94,94.

69. Беневоленский Д.С., Жадан И.В., Спыну С.К. Виртуальная суперЭВМ на основе использования распределенных вычислений в локальной вычислительной сети для решения сложных научно-технических задач. «Успехи современного естествознания» 2005, №7, с. 94,94.

70. Беневоленский С.Б., Жадан В.Г., Жадан И.В., Истомина Н.Л., Спыну М.В., Спыну С.К. Принципы создания программного обеспечения для систем распределенного вычисления. «Успехи современного естествознания» 2005, №7, с. 94,94.

71. Свидетельство об отраслевой регистрации разработки №5383 «Программное обеспечение для поиска глобального экстремума функции многих переменных С1оЬех», Дата регистрации 16 ноября 2005г.

72. Беневоленский Д.С., Жадан В.Г., Жадан И.В. Технология вычислений в распределенной среде при расчете метода половинных делений для глобальной оптимизации функции многих переменных // Нейрокомпьютеры, 2007, 5, С. 8-11.

73. Свидетельство о государственной регистрации программы для ЭВМ №2009616922 «Программное обеспечение для поиска глобального экстремума методом половинных делений при неравномерном покрытии», Дата регистрации 14 декабря 2009г.

74. Беневоленский С.Б., Жадан И.В. Модификация метода половинных делений путем использования метода сопряженных градиентов. XXXV Гагаринские чтения: материалы Международной молодежной научной конференции в 8 томах, Москва, 2009, т.4, с. 7677.

75. MPI: The Message Passing Interface http://parallel.ru/tech/techdev/mpi.html.

76. Александр Каленюк, "Нестандартные алгоритмы сортировки".

77. Подбельский В.В. Язык Си++. М.: Финансы и статистика, 2000. -560с.

78. В. В. Воеводин, Вл. В. Воеводин, Параллельные вычисления. 2002, с.600

79. Корнеев В. В., Параллельные вычислительные системы. 1999, с.320

80. В.Ф.Кравченко, О.В.Лазаренко, В.И.Пустовойт, Л.Ф.Черногор. Вейвлет -анализ поведения солитонов при обгонном и обменном взаимодействиях. Доклады академии наук, 2007, том 412, №2 с. 179184.

81. Кравченко В.Ф., Пустовойт В.И., Чуриков Д.В. Цифровая обработка нелинейных сигналов на основе преобразования Кравченко-Котельникова Вигнера. Успехи современной радиоэлектроники. Зарубежная радиоэлектроника. 2007, №8, с.67-71.