Алгоритми розпаралелювання обчислень для векторних задач дискретної оптимізації

Abstract

Розроблено підхід до розв’язання векторних задач дискретної оптимізації, в якому для знаходження Парето-оптимальних розв’язків використовується множина опорних точок. Даний підхід орієнтовано для виконання паралельних обчислень. Побудовано паралельний алгоритм, що використовує ідеї методу вектора спаду, в результаті роботи якого знаходиться множина недомінованих розв’язків, що апроксимують множину Парето розв’язуваної задачі, і відповідна їй недомінована множина оцінок у просторі критеріїв.

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

Approach to the solution of vector problems of discrete optimization is developed. For finding of Pareto-optimum solutions the sets of reference points is used. This approach implemented in a parallel algorithm. A parallel algorithm which uses the ideas of method of vector of decrease is built. A result of work of parallel algorithm is a set of the nondomined solutions, which is approximating the set of Pareto of the initial problem, and nondomined set of estimations in the objective space.