ДВА АЛГОРИТМА ГЛОБАЛЬНОЇ ОПТИМІЗАЦІЇ ФУНКЦІЙ ОДНІЄЇ ЗМІННОЇ, ЗАСНОВАНІ НА ВІДСТАНІ МІЖ ЕКСТРЕМУМАМИ ЇХНЬОЇ КІЛЬКОСТІ

Autor: Kodnyanko, V. A.
Jazyk: angličtina
Rok vydání: 2020
Předmět:
Zdroj: Radio Electronics, Computer Science, Control; № 2 (2020): Radio Electronics, Computer Science, Control; 36-43
Радиоэлектроника, информатика, управление; № 2 (2020): Радиоэлектроника, информатика, управление; 36-43
Радіоелектроніка, iнформатика, управління; № 2 (2020): Радіоелектроніка, інформатика, управління; 36-43
ISSN: 1607-3274
2313-688X
Popis: Contex. Making managerial decisions is often associated with solving one-dimensional global optimization problems. The most important property of global optimization methods is their speed, which is determined by the number of calls to the objective function in the optimization process.Objective. Development of high-performance algorithms global for optimizing the function of one variable, based on conditions that allow you to bring the problem to a form that opens up the practical possibility of obtaining a solution with a given accuracy.Method. Two algorithms of conditional global optimization of a function of one variable are considered. The first is based on estimating the smallest distance between neighboring local extrema and allows you to find the global minimum of the goal function and, if necessary, all its local extrema. The second is suitable for finding the global minimum of a function if the number of local extrema in the uncertainty interval is known in advance. Both algorithms are based on segmentation methods of the initial uncertainty segment. The local extremum on a segment is determined by three or four points. An approach is proposed that, in most cases, allows localization of the extremum at three points, which provides savings in the calculation of digital filters, thereby contributing to an increase in the speed of the algorithm.Results. The results of solving optimization problems and data on the effectiveness of the proposed algorithms are presented. A comparative analysis of the speed of the developed algorithms and well-known algorithms is carried out on the example of solving test problems used in world practice to assess the effectiveness of global optimization algorithms. Examples of the practical use of algorithms are given. The analysis of the data obtained showed that according to the number of calls to the objective function, the algorithms in the sequential computing mode work several times faster than modern high-speed algorithms with which they were compared.Conclusions. The data presented indicate the efficiency and high speed of the proposed algorithms. Their speed will be even higher if the stated ideas of algorithmization are extended to parallel computations. This suggests that the proposed algorithms can find practical application in the global optimization of functions of the considered classes of problems.
Актуальность. Принятие управленческих решений часто связано с решением задач одномерной глобальной оптимизации. Важнейшим свойством методов глобальной оптимизации является их быстродействие, которое определяется количеством обращений к целевой функции в процессе оптимизации.Цель. Разработка алгоритмов высокого быстродействия для глобальной оптимизации функции одной переменной, основанных на условиях, которые позволяют привести задачу к виду, открывающему практическую возможность получения решения с заданной точностью.Метод. Рассмотрено два алгоритма условной глобальной оптимизации функции одной переменной. Первый основан на оценке наименьшего расстояния между соседними локальными экстремумами и позволяет найти глобальный минимум целевой функции и при необходимости все ее локальные экстремумы. Второй пригоден для поиска глобального минимума функции, если наперед известно количество локальных экстремумов на отрезке неопределенности. Оба алгоритма базируются на методах сегментации исходного отрезка неопределенности. Локальный экстремум на сегменте определяется по трем или по четырем точкам. Предложен подход, который в большинстве случаев позволяет выполнить локализацию экстремума по трем точкам, что дает экономию при вычислениях ЦФ, способствуя тем самым повышению быстродействия алгоритма.Результаты. Приведены результаты решения оптимизационных задач и данные об эффективности предложенных алгоритмов. Проведен сравнительный анализ быстродействия разработанных алгоритмов и известных алгоритмов на примере решения тестовых задач, используемых в мировой практике для оценки эффективности алгоритмов глобальной оптимизации. Даны примеры практического использования алгоритмов. Анализ полученных данных показал, что по числу обращений к целевой функции алгоритмы в режиме последовательных вычислений работают в несколько раз быстрее современных быстродействующих алгоритмов, с которыми производилось сравнение.Выводы. Приведенные данные свидетельствуют об эффективности и высоком быстродействии предложенных алгоритмов. Их быстродействие будет еще выше, если изложенные идеи алгоритмизации распространить на параллельные вычисления. Это позволяет предположить, что предложенные алгоритмы могут найти практическое применение при глобальной оптимизации функций рассмотренных классов задач.
Актуальність. Прийняття управлінських рішень часто пов’язане з вирішенням завдань одновимірної глобальної оптимізації. Найважливішим властивістю методів глобальної оптимізації є їхня швидкодія, яке визначається кількістю звернень до цільової функції (ЦФ) в процесі оптимізації.Мета. Розробка алгоритмів високої швидкодії для глобальної оптимізації функції однієї змінної, заснованих на умовах, які дозволяють привести задачу до виду, що відкриває практичну можливість отримання рішення із заданою точністю.Метод. Розглянуто два алгоритми умовної глобальної оптимізації функції однієї змінної. Перший заснований на оцінці найменшої відстані між сусідніми локальними екстремумами і дозволяє знайти глобальний мінімум цільової функції і при необхідності ці її локальні екстремуми. Другий придатний для пошуку глобального мінімуму функції, якщо наперед відома кількість локальних екстремумів на відрізку невизначеності. Обидва алгоритми базуються на методах сегментації вихідного відрізка невизначеності. Локальний екстремум на сегменті визначається за трьома або по чотирьох точках. Запропоновано підхід, який у більшості випадків дозволяє виконати локалізацію екстремуму по трьох точках, що дає економію при обчисленнях ЦФ, сприяючи тим самим підвищенню швидкодії алгоритму.Результати. Наведено результати розв’язання оптимізаційних задач і дані про ефективність запропонованих алгоритмів. Проведено порівняльний аналіз швидкодії розроблених алгоритмів і відомих алгоритмів на прикладі рішення тестових завдань, що використовуються у світовій практиці для оцінки ефективності алгоритмів глобальної оптимізації. Наведені приклади практичного використання алгоритмів. Аналіз отриманих даних показав, що за кількістю звернень до цільової функції алгоритми у режимі послідовних обчислень працюють у кілька разів швидше сучасних швидкодіючих алгоритмів, з якими проводилося порівняння.Висновки. Наведені дані свідчать про ефективність і високу швидкодію запропонованих алгоритмів. Їх швидкодія буде ще вище, якщо викладені ідеї алгоритмізації поширити на паралельні обчислення. Це дозволяє припустити, що запропоновані алгоритми можуть знайти практичне застосування при глобальної оптимізації функцій розглянутих класів задач.
Databáze: OpenAIRE
Externí odkaz: