The proposal of the optimisation time reduction algorithm

Abstract

В багатьох випадках вирішення проблем оптимізації, зокрема динамічних проблем оптимізації, вимагає багато часу. Причиною цього є тривалий період обчислення значення цільової функції. Наприклад, упродовж процесу оптимізації механічних систем може з’явитися необхідність інтегрування динамічних рівнянь руху протягом усього інтервалу часу. В зв’язку з цим, були розроблені спеціалізовані методи, які дозволяють обчислити приблизне значення цільової функції. Ці методи зазвичай ґрунтуються на алгоритмах повної оптимізації та містять методи розрахунку приблизних значень цільової функції. В цій статті запропоновано новий алгоритм EVCA (оцінювання і кешування), призначений зменшити час обчислень під час процесу оптимізації. Важливою особливістю запропонованого алгоритму є те, що він може бути застосований до будь-яких нелінійних методів оптимізації як градієнтних, так і неградієнтних та стохастичних. Для впровадження запропонованого підходу немає необхідності змінювати алгоритми та методи оптимізації, які застосовуються для обчислення значень цільової функції. В алгоритмі використовуються два етапи: оцінювання значень цільової функції та кешування отриманих значень для всіх попередньо розрахованих точок. Такий підхід дозволяє ефективно пришвидшити процес оптимізації, особливо для оптимізації фізичних систем. Представлено результати оптимізації для еталонних функцій та подвійного маятника з рухомою основою із застосуванням алгоритму EVCA.

In many cases, solving optimisation problems and a dynamic optimisation problem, in particular is time-consuming. This is due to the long time of calculation of the objective function value. For example, during optimisation of the mechanical systems it can be necessary to integrate of the dynamic equations of motion in the whole time interval. For this reason, dedicated methods which allow to calculate approximated value of the objective function have been elaborated. These methods usually are full optimisation algorithms which have embedded methods for calculating of approximated value of the objective function. In this paper new EVCA (Evaluating and Caching) algorithm for reduction optimisation calculations time has been proposed. An important feature of the presented algorithm is that it can be applied to any nonlinear optimisation methods both gradient, non-gradient and stochastic. Presented approach doesn’t need to modify of optimisation algorithms and methods which have been used to calculate objective function value. The algorithm uses two mechanisms: estimating of the objective function value and caching its values for all calculated earlier points. Such approach allows to effectively speed up the optimisation process, especially optimisation of the physical systems. The results of the optimisation for the benchmark functions and double pendulum on the cart with using EVCA algorithm have been presented.