Метод рою частинок для розв’язання задач нелінійної оптимізації

Abstract

UK: Оптимальне проектування будівель та споруд потребує вирішення низки важливих проблем, пов'язаних з визначенням найкращої топології і геометричної форми конструкцій, фізичних властивостей елементів, зв'язків елементів між собою тощо. При цьому необхідно враховувати вплив багатьох чинників: розподіл статичних і динамічних навантажень, корозійні процеси, характер умов експлуатації, вимоги до надійності та довговічності об'єкту. Складність розв’язання таких задач пов'язана з тим, що у більшості випадків цільові функції є нелінійними, залежать від великої кількості параметрів, а також можуть мати багато локальних екстремумів. Метою роботи є розвиток нових методів для розв’язання задач нелінійної оптимізації. Методика. У роботі використовується метод рою частинок, який імітує поведінку децентралізованих біологічних систем та належить до методів штучного колективного інтелекту. Результати. Запропонована нова програмна реалізація методу рою частинок у системі комп'ютерної алгебри з відкритим кодом Maxima. На прикладах тестових функцій Розенброка та Растрігіна, показана висока обчислювальна ефективність методу та досліджено вплив його параметрів на швидкість практичної збіжності. Наукова новизна. У порівнянні з класичними алгоритмами, метод рою частинок може бути особливо ефективним для знаходження екстремумів нелінійних мультимодальних функцій, а також для розв’язання задач високої розмірності. Практичне значення. Розвинутий метод може бути застосований для розв’язання задач оптимального проектування будівель та споруд.

RU: Оптимальное проектирование зданий и сооружений требует решения ряда важных задач, связанных с определением наилучшей топологии и геометрической формы конструкций, физических свойств элементов, связей элементов между собой, прочее. При этом необходимо учитывать влияние многих факторов: распределение статических и динамических нагрузок, коррозионное воздействие, характер условий эксплуатации, требования к надежности и долговечности объекта. Сложность решения таких задач связана с тем, что во многих случаях целевые функции являются нелинейными, зависят от большого количества параметров, а также могут иметь несколько локальных экстремумов. Целью работы является развитие новых методов для решения задач нелинейной оптимизации. Методика. В работе используется метод роя частиц, который имитирует поведение децентрализованных биологических систем и является одним из методов искусственного коллективного интеллекта. Результаты. Предложена новая программная реализация метода роя частиц в системе компьютерной алгебры с открытым кодом Maxima. На примерах тестовых функций Розенброка и Растригина показана высокая вычислительная эффективность метода и исследовано влияние его параметров на скорость практической сходимости. Научная новизна. По сравнению с классическими алгоритмами, метод роя частиц может быть особенно эффективным для нахождения экстремумов нелинейных мультимодальных функций, а также для решения задач высокой размерности. Практическое значение. Развитый метод может быть использован для решения задач оптимального проектирования строительных конструкций, зданий и сооружений.

EN: The optimal design of buildings and structures requires solving a number of important tasks related to determining the best topology and geometric shape of structures, physical properties of elements, connections of elements among themselves, etc. In this case, it is necessary to take into account the influence of many factors: the distribution of static and dynamic loads, corrosive effects, the nature of the operating conditions, the requirements for the reliability and durability of the unit. The complexity of solving such problems is connected with the fact that, as a rule, the objective functions of such problems are nonlinear. Methods. Various approaches are used to solve nonlinear optimization problems: stochastic search (Monte Carlo method); search methods in which the step is successively reduced, following to the given relation (halving, golden ratio, inverse Fibonacci numbers); gradient descent method; evolutionary algorithms; penalty function method and others. In recent years, a new class of methods of numerical optimization has been intensively developed, in various works it is called social-behavioral, population, or swarm. For practical verification of the particle swarm method, the finding of the extrema of the test functions of Rosenbrock and Rastrigin is considered. Results. A new software implementation of one of the methods of artificial collective intelligence, the particle swarm method, is proposed for solving nonlinear optimization problems in the Maxima open-source computer algebra system. The high computational efficiency of this method for finding global extrema of “ravine” and multimodal functions in those cases where the application of many classical algorithms can be difficult is shown. Scientific novelty. Compared to classical methods, swarm intelligence methods are especially effective for finding extrema of nonlinear multimodal functions, as well as for solving high-dimensional problems. Practical significance. The effect of the method parameters (particle number and weight coefficients) on the rate of practical convergence is investigated. The developed method can be used, inter alia, to solve the problems of optimal design of building structures, buildings and structures.