Другие журналы

научное издание МГТУ им. Н.Э. Баумана

НАУКА и ОБРАЗОВАНИЕ

Издатель ФГБОУ ВПО "МГТУ им. Н.Э. Баумана". Эл № ФС 77 - 48211.  ISSN 1994-0408

Локальный поиск методом Хука–Дживса в гибридном алгоритме глобальной оптимизации

# 06, июнь 2014
DOI: 10.7463/0614.0716155
Файл статьи: Shkapov_P.pdf (772.40Кб)
авторы: Сулимов В. Д., Шкапов П. М., Носачев С. К.

УДК 519.6

Россия,  МГТУ им. Баумана

Современные методы оптимизационного исследования сложных систем основаны на разработке и последующем уточнении их математических моделей, что связано с решением соответствующих обратных задач. Входные данные, необходимые для решения, получают на основе анализа результатов экспериментального определения следст-венных характеристик для системы или процесса. Искомыми являются причинные характеристики, к которым относятся коэффициенты уравнений математической модели объекта, граничные условия и другие характеристики. Одним из основных подходов к решению обратных задач является оптимизационный, при этом требуется в общем слу-чае найти глобальный экстремум не всюду дифференцируемой критериальной функции. Методы глобальной оптимизации широко используются в задачах идентификации и вычислительной диагностики систем, оптимальном управлении, компьютерной томографии, при восстановления изображений, обучении нейронных сетей, в других интеллектуальных технологиях. Возрастающая сложность оптимизируемых систем, наблюдаемая в последние десятилетия, ведет к усложнению их математических моделей, что значительно затрудняет решение соответствующих экстремальных задач. В значительном числе практических приложений физические условия задачи могут налагать ограничения на моделирование. Как следствие, в обратных задачах критериальные функции могут быть не всюду дифференцируемыми и зашумленными. Наличие шума означает, что вычисление производных является затруднительным и ненадежным. Это приводит к необходимости использования методов оптимизации без вычисления производных.
Эффективность детерминированных алгоритмов глобальной оптимизации существенно ограничена их зависимостью от размерности экстремальной задачи. В случае большого числа переменных применяют алгоритмы стохастической глобальной оптимизации. Основным недостатком, ограничивающим применение стохастических алгоритмов, является высокая вычислительная стоимость получаемых решений. Перспективным направлением можно считать разработку гибридных алгоритмов, объединяющих стохастический алгоритм, используемый при сканировании пространства переменных для определения области, перспективной на глобальный экстремум, и детерминированный метод локального поиска. В работе предложен новый гибридный алгоритм с локальным поиском методом Хука–Дживса, в котором сканирование пространства поиска проводится с использованием кратного алгоритма столкновения частиц. Представлены результаты решения стандартной эталонной тестовой задачи глобальной минимизации.

Список литературы
  1. Pulecchi T., Casella F., Lovera M. Object-oriented modelling for spacecraft dynamics: Tools and applications // Simulation Modelling and Theory. 2010. Vol. 18, no. 1. P. 63-86. DOI: 10.1016/j.simpat.2009.09.010
  2. Fernández-Martinez J.L., Mukerji T., García-Gonzalo E., Fernández-Muñiz Z. Uncertainty assessment for inverse problems in high dimensional spaces using particle swarm optimization and model reduction techniques // Mathematical and Computer Modelling . 2011. Vol. 54, no. 11 -1 2. P. 2889-2899 . DOI: 10.1016/j.mcm.2011.07.009
  3. Nakamura T., Small M. Nonlinear dynamical system identification with dynamic noise and observational noise // Physica D: Nonlinear Phenomena. 2006. Vol. 223, iss. 1. P. 54-68. DOI: 10.1016/j.physd.2006.08.013
  4. Kinelev V.G., Shkapov P.M., Sulimov V.D. Application of global optimization to VVER-1000 reactor diagnostics // Progress in Nuclear Energy. 2003. Vol. 43, no. 1-4. P. 51-56. DOI: 10.1016/S0149-1970(03)00010-6
  5. Mengi E. Nearest linear systems with highly deficient reachable subspaces // SIAM Journal of Matrix Analysis and Applications. 2012. Vol. 33, no. 3. P. 1000-1017. DOI: 10.1137/120867895
  6. Darup M.S., Kastsian M., Mross S., Mönnigmann M. Efficient computation of spectral bounds for Hessian matrices on hyperrectangles for global optimization // Journal of Global Optimization. 2014. Vol. 58, no. 4. P. 631-652. DOI: 10.1007/s10898-013-0099-1
  7. Zhang H., Conn A.R. On the local convergence of a derivative-free algorithm for least-squares minimization // Computational Optimization and Applications. 2012. Vol. 51, no. 2. P. 481-507. DOI: 10.1007/s10589-010-9367-x
  8. Hare W., Macklem M. Derivative-free methods for finite minimax problems // Optimization Methods and Software. 2013. Vol. 28, no. 2. P. 300-312. DOI: 10.1080/10556788.2011.638923
  9. Kvasov D.E., Sergeev Ya. D. Lipschitz global optimization methods in control problems // Automation and Remote Control. 2013. Vol. 74, no. 9. P. 1435-1448. DOI: 10.1134/S0005117913090014
  10. Goncharsky A.V., Romanov S.Y. Supercomputer technologies in inverse problems of ultrasound tomography // Inverse Problems. 2013. Vol. 29, no. 7. P. 1-22. DOI: 10.1088/0266-5611/29/7/075004
  11. Wu C., Zhang J., Duan Y., Tai X.-C. Augmented Lagrangian method for total variation based image restoration and segmentation over triangulated surfaces // Journal of Scientific Computing. 2012. Vol. 50, no. 1. P. 145-166. DOI: 10.1007/s10915-011-9477-3
  12. De Oliveira M.V., de Almeida J.C.S. Applications of artificial intelligence techniques in modeling and control of a nuclear power plant pressurizer system // Progress in Nuclear Energy. 2013. Vol. 63. P. 71-85. DOI: 10.1016/j.pnucene.2012.11.005
  13. Diniz-Ehrhardt M.A., Martínez J.M., Pedroso L.G. Derivative-free methods for nonlinear programming with general lower-level constraints // Computational and Applied Mathematics. 2011. Vol. 30, no. 1. P. 19-52.
  14. Powell M.J.D. On the convergence of trust region algorithms for unconstrained minimization without derivatives // Computational Optimization and Applications. 2012. Vol. 53, no. 3. P. 527-555. DOI: 10.1007/s10589-012-9483-x
  15. Lera D., Sergeev Ya.D. Lipschitz and Hölder global optimization using space-filling curves // Applied Numerical Optimization. 2010. Vol. 60, no. 1-2. P. 115-129. DOI: 10.1016/j.apnum.2009.10.004
  16. Lera D., Sergeev Ya.D. Acceleration of univariate global optimization algorithms working with Lipschitz functions and Lipschitz first derivatives // SIAM Journal on Optimization. 2013. Vol. 23, no. 1. P. 508-529. DOI: 10.1137/110859129
  17. Birgin E.G., Martínez J.M., Prudente L.F. Augmented Lagrangians with possible infeasibility and finite termination for global nonlinear programming // Journal of Global Optimization. 2014. Vol. 58, no. 2. P. 207-242. DOI: 10.1007/s10898-013-0039-0
  18. Voglis C., Parsopoulos K.E., Papageorgiou D.G., Lagaris I.E., Vrahatis M.N. MEMPSODE: A global optimization software based on hybridization of population-based algorithms and local searches // Computer Physics Communications. 2012. Vol. 183, no. 2. P. 1139-1154. DOI: 10.1016/j.cpc.2012.01.010
  19. Źilinskas A., Źilinskas J. A hybrid global optimization algorithm for non-linear least squares regression // Journal of Global Optimization. 2013. Vol. 56, no. 2. P. 265-277. DOI: 10.1007/s10898-011-9840-9
  20. Rios-Coelho A.C., Sacco W.F., Henderson N. A Metropolis algorithm combined with Hooke-Jeeves local search method applied to global optimization // Applied Mathematics and Computation. 2010. Vol. 217, no. 2. P. 843-853. DOI: 10.1016/j.amc.2010.06.027
  21. Sacco W.F., de Oliveira C.R.E. A new stochastic optimization algorithm based on particle collisions // Proceedings of the 2005 ANS Annual Meeting. Transactions of the American Nuclear Society. 2005. Vol. 92. P. 657-659.
  22. Kirkpatrick S., Gelatt Jr. C.D., Vecchi M.P. Optimization by simulated annealing // Science. 1983. Vol. 220, no. 4598. P. 671-680. DOI: 10.1126/science.220.4598.671
  23. Luz E.F.P., Becceneri J.C., de Campos Velho H.F. A new multi-particle collision algorithm for optimization in a high performance environment // Journal of Computational Interdisciplinary Sciences. 2008. Vol. 1, no. 1. P. 3-10. DOI: 10.6062/jcis.2008.01.01.0001
  24. Rios L.M., Sahinidis N.V. Derivative-free optimization: a review of algorithms and comparison of software implementations // Journal of Global Optimization. 2013. Vol. 56, no. 3. P. 1247-1293. DOI: 10.1007/s10898-012-9951-y
  25. Csendes T., Pál L., Sendín J.O.H., Banga J.R. The GLOBAL optimization method revisited // Optimization Letters. 2008. Vol. 2, no. 4. P. 445-454. DOI: 10.1007/s11590-007-0072-3
  26. Hirsch M.J., Pardalos P.M., Resende M.G.C. Speeding up continuous GRASP // European Journal of Operational Research. 2010. Vol. 205, no. 3. P. 507-521. DOI: 10.1016/j.ejor.2010.02.009
  27. Laguna M., Marti R. Experimental testing of advanced scatter search designs for global optimization of multimodal functions // Journal of Global Optimization. 2005. Vol. 33, no. 2. P. 235-255. DOI: 10.1007/s10898-004-1936-z
  28. Hedar A.-R., Fukushima M. Tabu Search directed by direct search methods for nonlinear global optimization // European Journal of Operational Research. 2006. Vol. 170, no. 2. P. 329-349. DOI: 10.1016/j.ejor.2004.05.033
  29. Sulimov V.D., Shkapov P.M. Application of hybrid algorithms to computational diagnostic problems for hydromechanical systems // Journal of Mechanics Engineering and Automation. 2012. Vol. 2, no. 12. P. 734-741.
  30. Gao F., Han L. Implementing the Nelder–Mead simplex algorithm with adaptive parameters // Computational Optimization and Applications. 2012. Vol. 51, no. 1. P. 259-277. DOI: 10.1007/s10589-010-9329-3
Поделиться:
 
ПОИСК
 
elibrary crossref ulrichsweb neicon rusycon
 
ЮБИЛЕИ
ФОТОРЕПОРТАЖИ
 
СОБЫТИЯ
 
НОВОСТНАЯ ЛЕНТА



Авторы
Пресс-релизы
Библиотека
Конференции
Выставки
О проекте
Rambler's Top100
Телефон: +7 (915) 336-07-65 (строго: среда; пятница c 11-00 до 17-00)
  RSS
© 2003-2020 «Наука и образование»
Перепечатка материалов журнала без согласования с редакцией запрещена
 Тел.: +7 (915) 336-07-65 (строго: среда; пятница c 11-00 до 17-00)