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

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

Повний опис

Збережено в:

Бібліографічні деталі
Дата:	2015
Автор:	Семенов, В.В.
Формат:	Стаття
Мова:	Russian
Опубліковано:	Інститут кібернетики ім. В.М. Глушкова НАН України 2015
Назва видання:	Компьютерная математика
Теми:	Теория и методы оптимизации
Онлайн доступ:	https://nasplib.isofts.kiev.ua/handle/123456789/168371
Теги:	Додати тег Немає тегів, Будьте першим, хто поставить тег для цього запису!
Назва журналу:	Digital Library of Periodicals of National Academy of Sciences of Ukraine
Цитувати:	Алгоритми розпаралелювання обчислень для векторних задач дискретної оптимізації / В.В. Семенов // Компьютерная математика. — 2015. — № 1. — С. 134-141. — Бібліогр.: 9 назв. — рос.

Репозитарії

Digital Library of Periodicals of National Academy of Sciences of Ukraine

id	nasplib_isofts_kiev_ua-123456789-168371
record_format	dspace
spelling	nasplib_isofts_kiev_ua-123456789-1683712025-02-09T20:45:56Z Алгоритми розпаралелювання обчислень для векторних задач дискретної оптимізації Алгоритмы распараллеливания вычислений для векторных задач дискретной оптимизации Algorithms of paralleling calculations for vector problems of discrete optimization Семенов, В.В. Теория и методы оптимизации Розроблено підхід до розв’язання векторних задач дискретної оптимізації, в якому для знаходження Парето-оптимальних розв’язків використовується множина опорних точок. Даний підхід орієнтовано для виконання паралельних обчислень. Побудовано паралельний алгоритм, що використовує ідеї методу вектора спаду, в результаті роботи якого знаходиться множина недомінованих розв’язків, що апроксимують множину Парето розв’язуваної задачі, і відповідна їй недомінована множина оцінок у просторі критеріїв. Разработан подход к решению векторных задач дискретной оптимизации, в котором для нахождения Парето-оптимальных решений используется множество опорных точек. Данный подход ориентирован для выполнения параллельних вычислений. Построен параллельный алгоритм, использующий идеи метода вектора спада, в результате работы которого находится множество недоминируемых решений, которые аппроксимируют множество Парето решаемой задачи, и соответствующее ему недоминируемое множество оценок в пространстве критериев. 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. 2015 Article Алгоритми розпаралелювання обчислень для векторних задач дискретної оптимізації / В.В. Семенов // Компьютерная математика. — 2015. — № 1. — С. 134-141. — Бібліогр.: 9 назв. — рос. 2616-938Х https://nasplib.isofts.kiev.ua/handle/123456789/168371 519.8 ru Компьютерная математика application/pdf Інститут кібернетики ім. В.М. Глушкова НАН України
institution	Digital Library of Periodicals of National Academy of Sciences of Ukraine
collection	DSpace DC
language	Russian
topic	Теория и методы оптимизации Теория и методы оптимизации
spellingShingle	Теория и методы оптимизации Теория и методы оптимизации Семенов, В.В. Алгоритми розпаралелювання обчислень для векторних задач дискретної оптимізації Компьютерная математика
description	Розроблено підхід до розв’язання векторних задач дискретної оптимізації, в якому для знаходження Парето-оптимальних розв’язків використовується множина опорних точок. Даний підхід орієнтовано для виконання паралельних обчислень. Побудовано паралельний алгоритм, що використовує ідеї методу вектора спаду, в результаті роботи якого знаходиться множина недомінованих розв’язків, що апроксимують множину Парето розв’язуваної задачі, і відповідна їй недомінована множина оцінок у просторі критеріїв.
format	Article
author	Семенов, В.В.
author_facet	Семенов, В.В.
author_sort	Семенов, В.В.
title	Алгоритми розпаралелювання обчислень для векторних задач дискретної оптимізації
title_short	Алгоритми розпаралелювання обчислень для векторних задач дискретної оптимізації
title_full	Алгоритми розпаралелювання обчислень для векторних задач дискретної оптимізації
title_fullStr	Алгоритми розпаралелювання обчислень для векторних задач дискретної оптимізації
title_full_unstemmed	Алгоритми розпаралелювання обчислень для векторних задач дискретної оптимізації
title_sort	алгоритми розпаралелювання обчислень для векторних задач дискретної оптимізації
publisher	Інститут кібернетики ім. В.М. Глушкова НАН України
publishDate	2015
topic_facet	Теория и методы оптимизации
url	https://nasplib.isofts.kiev.ua/handle/123456789/168371
citation_txt	Алгоритми розпаралелювання обчислень для векторних задач дискретної оптимізації / В.В. Семенов // Компьютерная математика. — 2015. — № 1. — С. 134-141. — Бібліогр.: 9 назв. — рос.
series	Компьютерная математика
work_keys_str_mv	AT semenovvv algoritmirozparalelûvannâobčislenʹdlâvektornihzadačdiskretnoíoptimízacíí AT semenovvv algoritmyrasparallelivaniâvyčisleniidlâvektornyhzadačdiskretnoioptimizacii AT semenovvv algorithmsofparallelingcalculationsforvectorproblemsofdiscreteoptimization
first_indexed	2025-11-30T15:34:47Z
last_indexed	2025-11-30T15:34:47Z
_version_	1850230061751336960
fulltext	134 Компьютерная математика. 2015, № 1 Розроблено підхід до розв’язання векторних задач дискретної оп- тимізації, в якому для знаходжен- ня Парето-оптимальних розв’яз- ків використовується множина опорних точок. Даний підхід оріє- нтовано для виконання паралель- них обчислень. Побудовано пара- лельний алгоритм, що використо- вує ідеї методу вектора спаду, в результаті роботи якого знахо- диться множина недомінованих розв’язків, що апроксимують мно- жину Парето розв’язуваної за- дачі, і відповідна їй недомінована множина оцінок у просторі критеріїв.  В.В. Семенов, 2015 УДК 519.8 В.В. СЕМЕНОВ АЛГОРИТМИ РОЗПАРАЛЕЛЮВАННЯ ОБЧИСЛЕНЬ ДЛЯ ВЕКТОРНИХ ЗАДАЧ ДИСКРЕТНОЇ ОПТИМІЗАЦІЇ Вступ. Розв’язання задач дискретної оптимі- зації у наш час важливе й актуальне. З рос- том розмірності розв’язуваних задач вини- кають принципові обчислювальні труднощі при знаходженні точного або наближеного розв’язку. Ці труднощі значно збільшуються при оперативному розв’язанні задач, особли- во задач великої розмірності [1, 2]. Розв’язання однокритеріальних та вектор- них задач дискретної оптимізації на послі- довних обчислювальних машинах вимагає істотних обчислювальних ресурсів (часу, пам'яті), що пов’язано з перебором великої кількості варіантів. Як показано в [3] навіть для задачі про ранець з n булевими змінни- ми, цей перебір може виявитися близьким до повного та мати порядок 2 /n n . Традицій- но застосовувані послідовні обчислювальні технології розв’язання задач великої розмір- ності, як правило, не дозволяють знайти розв’язки за прийнятний час. Звідси природ- но виникає необхідність застосування пара- лельних методів для прискорення процесу розв’язання задач дискретної оптимізації. Спроби розв’язання звичайними послідов- ними алгоритмами задач дискретної оптимі- зації на багатопроцесорних обчислювальних системах зазвичай не приводять до збіль- шення швидкодії. Для реального зменшення часу розв’язання задач потрібно застосуван- ня спеціальних паралельних обчислювальних алгоритмів, що враховують архітектурні особливості багатопроцесорних обчислю- вальних систем. АЛГОРИТМИ РОЗПАРАЛЕЛЮВАННЯ ОБЧИСЛЕНЬ ДЛЯ ВЕКТОРНИХ ЗАДАЧ ... Компьютерная математика. 2015, № 1 135 Розроблено підхід до розв’язання векторних задач дискретної оптимізації, в якому для знаходження Парето-оптимальних розв’язків використовується множина опорних точок. Даний підхід орієнтовано для виконання паралельних обчислень. Він базується на побудові множини точок, які автоматично визнача- ються таким чином, щоб критеріальний простір був рівномірно розподілений, але повністю покритий. Задача багатокритеріальної оптимізації полягає в оптимізації множини ці- льових функцій 1 2( ), ( ),... ( )f x f x f x , де 2 . Кожна функція мінімізується або максимізується. Припустимо, без втрати загальності, що всі функції мають бути мінімізовані. Вектор розв’язків 1 2( , ,..., )nx x x x представлений у вигляді n змінних. Позначимо X множину допустимих розв’язків. На основі векторної функції кожному вектору розв’язків поставимо у відповідність вектор оцінок 1 2( , ,..., ),y y y y  ( ),i iy f x 1,...,i   , y Y R   , де Y – множина векторів оцінок допустимих точок x X у просторі критеріїв. Отже, представимо задачу багатокритеріальної оптимізації у такий спосіб:   1 2min ( ) \| , ( ) ( ( ), ( ),..., ( )).F x x X F x f x f x f x   (1) Як відомо, розв’язання задачі однокритеріальної оптимізації, в основному приводить до єдиного оптимального розв’язку, задача багатокритеріальної оптимізації знаходить множину розв’язків, відому як множина Парето- оптимальних розв’язків. Розв’язання задачі (1) полягає у знаходженні вектора Парето-оптимальних (ефективних) точок [4, 5]. Нехай допустима множина X задачі (1) обмежена і дискретна. У цьому випадку множина ефективних розв’язків не порожня [5]. Множина всіх недомінованих векторів оцінок є Парето-границею. Один із можливих підходів для розв’язання задач багатокритеріальної оптимізації полягає у знаходженні Парето-границі або апроксимації Парето-границі. Це залежить від практичної обчислювальної складності задачі, оскільки знаходження всієї Парето-границі практично можливе, якщо обчислювальна складність задачі є досить низькою. Припустимо, що існує оптимальний розв’язок задачі багатокритеріальної оптимізації, який може бути знайдений шляхом перетворення багатокритеріальної задачі у відповідну скаляризовану (однокритеріальну) задачу. Передбачається, що для кожної цільової функції  ( ), 1,2,...,if x i L   відомий оптимум на допустимій множині. Тоді можна визначити поняття ідеального вектора. Означення. Ідеальним називається вектор 1 2 ( , ,... ),y y y y    , де    min \| , .і iy f x x X i L  Верхні межі всіх критеріїв Парето-границі можуть бути представлені точкою 1 2=( , ..., , ),n n n ny y y y   max .\| ,і n iz f x x X i L  Звичайно, ідеальний вектор рідко є допустимим, оскільки цілі часто суперечать одна одній. Правило вибору компромісу в цьому випадку полягає В.В. СЕМЕНОВ Компьютерная математика. 2015, № 1136 у знаходженні альтернативи, яка має оцінку найближчу до ідеального вектора в деякій метриці. Визначимо відстань 1 1 ( , ) ( )s s s i i i y y y y      між точками , y y у метричних просторах sR з показником метрики 1s  . Тоді згідно з ме- тодом ідеальної точки знайдемо компромісну оцінку як розв’язок, так званої, скаляризованої задачі 1 1 arg min( * )s s i iy Y i y y y      . Значення показника метрики s вибирається в залежності від предметної області. На практиці в основному ви- користовують значення 1, 2, .s   Вибирають 2s  у випадках, коли критерії мають зміст відстані чи інших фізичних величин, для яких Евклідова метрика є змістовною. В цьому випадку компромісна альтернатива x знаходиться як розв’язок скаляризованої задачі: 2min ( ( ) ) \| .i i i L f x y x X           При 1,s   критерії можуть мати будь-який інший зміст (наприклад, вартість, надійність, тривалість та ін.) і скаляризовані задачі приймають відповідно вигляд: min ( ) * max ( ),i i ix X x Xi L i L f x y f x       (2)  min max ( ) * max min ( ) i i i ix X i Li L x X f x y f x y       . (3) Задача (2) вибирається, коли особа, що приймає рішення (ОПР), оцінює відстань до ідеалу як сумарну нев’язку за всіма критеріями і така оцінка має певний зміст у предметній області, в якій розв’язується задача (наприклад, у двохкритеріальній задачі, де максимізуються прибуток фірми і заробітна платня її працівників цільова функція задачі (2) має зміст частини доходу фірми). Задача (3) вибирається, коли ОПР оцінює відстань до ідеалу як максимальну нев’язку за всіма критеріями (тобто за найгіршим за значенням показником). Підходи, засновані на побудові функцій скаляризації [4 – 6, 7], запропоно- вані Вержбицьким [8], добре підходять для роботи з опорними точками. Опорна точка дає бажані або прийнятні значення для кожного з критеріїв. Ці значення функцій критерію називаються рівнями прагнення, а утворений вектор оцінок – опорною точкою і може бути визначений у допустимій або в недопустимій об- ласті критеріального простору. Одну із сімейства скаляризаційних функцій, що може бути використана для розв’язання задачі (1), запишемо таким чином: 0 0 0 1,2,..., 1 ( , , , ) max { ( )} ( ),i i i j j ji j y y y y y y              (4) де 1 0 0 0 2( , ,..., )y y y y  – опорна точка, 1 2( , ,..., )     – вектор вагових коефіцієнтів,  – випадкове мале число (0 1)  . За допомогою варіацій АЛГОРИТМИ РОЗПАРАЛЕЛЮВАННЯ ОБЧИСЛЕНЬ ДЛЯ ВЕКТОРНИХ ЗАДАЧ ... Компьютерная математика. 2015, № 1 137 вагових коефіцієнтів і опорних точок можна знаходити різні Парето-оптимальні розв’язки. Отже, маємо наступну однокритеріальну задачу:  0min ( , , , ) \| .y y y Y    (5) Задача (5) полягає у знаходженні альтернативи x X , яка має оцінку * ( )y F x Y  , найближчу до опорної точки 0y в деякій метриці. Для заданої точки 0y мають виконуватись такі дві властивості: 1) якщо  0 arg min ( ( ), , , ) \|x F x y x X     , то x – ефективний розв’язок за- дачі (1); 2) якщо x – ефективний розв’язок задачі (1), то існує функція 0( ( ), , , ),F x y   така, що x – оптимальний розв’язок задачі (5). Вагові вектори можуть бути нормалізовані, а множина всіх допустимих нормалізованих вагових векторів може бути представлена наступним чином:  1 1 ,..., , \| 1, 0, .j j j j L                    Використання різних векторів  навіть для однієї й тієї ж опорної точки 0y може привести до різних оптимальних розв’язків задачі (5). Це дозволяє викону- вати обчислення паралельно, оскільки задача оптимізації кожної даної функції з однією й тією ж опорною точкою та різними ваговими векторами може бути розв’язана незалежно від інших задач. Слід зазначити, що для будь-якого [1, ), ( ) ( );s R Y P Y   для ,s   ( ) ( );R Y S Y якщо множина Y строго опукла, то ( ) 1.R Y  За допомогою ідей методу вектора спаду [1, 2] та використанні розглянутих вище скаляризаційних функцій, де вибіркова інформація враховується за допо- могою опорних точок, запропоновано алгоритм розв’язання задачі багатокрите- ріальної дискретної оптимізації. Він спрямований на знаходження множин ефек- тивних розв’язків, що відповідають 0y і  . Паралельний підхід, заснований на використанні множини опорних точок, може бути розділений на два послідовні етапи. Перший, який називається етапом підготовки, присвячений розробці декіль- кох версій алгоритму вектора спаду шляхом: оцінки меж Парето-границі; утво- рення множини опорних точок; розроблення версії алгоритму розв’язання задачі (5) для кожної опорної точки. Другий – етап виконання, полягає у запуску версії алгоритму вектора спаду для кожної опорної точки на кожному процесорі, доки умова зупинки не буде задоволена. Етап підготовки. На цьому етапі підготовки призначається кількість проце- сорів, що дорівнює числу опорних точок. Далі виконуються такі дії: 1. Отримання наближеної оцінки нижніх та верхніх границь для всіх цільо- вих функцій. Ця оцінка може бути надана ОПР або апроксимована автоматично. В.В. СЕМЕНОВ Компьютерная математика. 2015, № 1138 2. Можливе встановлення зупинки алгоритму наступним чином. Спочатку визначити зовнішній діаметр (відстань у метриці Чебишева між поточними ни- жньою та верхньою границями) для поточної апроксимації ефективної множини. Потім порівняти його з попередньою оцінкою зовнішнього діаметру. Якщо різ- ниця між обома величинами залишається постійною більше ітерацій, ніж задана користувачем кількість повторень, зупинити виконання алгоритму. 3. Опис площини відтинання в області (нормалізованих діапазонів критеріїв) та визначення рівномірного розподілу опорних точок у цій площині. 4. Призначення кожному процесору комп’ютера версії алгоритму вектора спаду з функцією показника якості, що описується функцією скаляризації ви- гляду (4), яка визначається опорною точкою 0y та ваговим вектором λ. Етап виконання полягає у паралельному виконанні версії алгоритму вектора спаду доки не буде задоволена умова зупинки. В цьому випадку результати ви- конання на кожному процесорі для всіх опорних точок об’єднуються для отри- мання апроксимації ефективної множини. Загальний паралельний алгоритм, заснований на використанні множи- ни опорних точок, складається з наступних кроків: 1) почати з апроксимації діапазонів критеріїв, наданої ОПР; використати цю апроксимацію як початкову оцінку меж Парето-границі для визначення почат- кового наближення ідеальної та надирної точок Ay та ;nAy 2) встановити d– зовнішній діаметр цих меж, обчислених за формулою \|\| \|\|;nA Ad y y   3) покласти  1/ , 1 / ,...,1 /     , де  – кількість критеріїв; 4) утворити m початкових опорних точок 0(1) 0(2) 0( ), ,..., my y y використову- ючи апроксимовані межі Парето-границі; 5) утворити m початкових множин 1 2, , . . . , mP P P потужності N; 6) для 1,2,...,i m виконувати паралельно на m процесорах алгоритм векто- ра спаду: 0( ), ,λ,ρ( )i i iA P y , доки умова зупинки алгоритму не буде виконана; 7) об’єднати недоміновані розв’язки 1 2 .mA A A  У результаті виконання алгоритму знаходяться множина недомінованих розв’язків, що апроксимують множину Парето розв’язуваної задачі, та відповід- на їй недомінована Парето-границя. З представленої множини розв’язків, у разі потреби, ОПР може вибрати один або декілька варіантів розв’язків задачі. Реалізація паралельного алгоритму. При реалізації алгоритму можуть бути використані два рівні паралельних обчислень: рівень опорних точок та рівень еволюційного алгоритму. На першому рівні використання множини опорних точок звичайно може бути реалізовано в паралельній алгоритмічній моделі, оскільки побудовані алгоритми для однієї опорної точки можуть бути запущені незалежно. Більш того, множини векторів вагових коефіцієнтів також АЛГОРИТМИ РОЗПАРАЛЕЛЮВАННЯ ОБЧИСЛЕНЬ ДЛЯ ВЕКТОРНИХ ЗАДАЧ ... Компьютерная математика. 2015, № 1 139 можуть бути використані для тих самих опорних точок, що є приводом для другого рівня паралельних обчислень. Далі, на рівні алгоритму вектора спаду можна виділити три моделі [9]. Перша з них полягає в інсталяції різних алгоритмів вектора спаду одночасно. Друга, паралельне обчислення сукупності, полягає у розподіленні обчислення значень цільових функцій розв’язків, які містяться у сукупності в різних робочих процесорах. Остання – це розподілене обчислення одного розв’язку, яке розпаралелене (коли це можливо зробити). Заради простоти сконцентруємо увагу лише на паралельному обчисленні на рівні опорних точок. В останні десятиріччя для розв’язання дискретних задач розроблено різні наближені методи, в тому числі методи локальної оптимізації [1, 2]. Метод век- тора спаду є родиною алгоритмів, об’єднаних загальною схемою. Ці алгоритми призначені для розв’язання дискретних оптимізаційних задач і знаходять локальний розв’язок. Метод вектора спаду − ітераційний метод направленого перебору, що належить до типу градієнтних методів. Наведемо загальну схему методу вектора спаду. Нехай X − деякий дискрет- ний метричний простір з метрикою .r На підмножині R X визначена функція ( )f x . Тоді задача може бути сформульована таким чином. Визначити еле- мент x R X  , що доставляє екстремум функції ( )f x . У застосуванні до цієї задачі схема методу вектора спаду полягає в наступному. 1. Визначимо початкове значення 0 0; .ix x x 2. Побудуємо множини ( )iL x R  , де ( )iL x − окіл радіусу  з центром у точці ix . 3. Знаходимо розв’язок (точний або наближений) локальної задачі  1( ) ext ( ) \| ( )i if x f x x L x R    . 4. Якщо 1i ix x  , то обчислення припиняємо, приймаючи ix за локальний розв’язок; інакше переходимо до п. 2 алгоритму, замінюючи i на 1i  і т. д., поки на деякому кроці k не виконається рівність 1.k kx x  Ця схема є деякою сукупністю алгоритмів. Дійсно: 1) ( )i   ; зокрема, можна прийняти const  , допустима також багато- значність ( )i , що дозволяє уточнювати отримані розв’язки; 2) локальна задача в п. 3 може розв’язуватися різними методами. Зазначимо, що ця схема в застосуванні до кожної конкретної задачі або кла- су задач має враховувати її конкретні властивості або властивості класу задач, тому метод у застосуванні до вужчого класу задач вимагає спеціальних додатко- вих досліджень, що враховують властивості простору ,R його метрики і мно- жини, а також властивості функції ( ).f x Перспективним напрямком у створенні методів дискретної оптимізації є також використання в їх обчислювальних схемах певних імовірнісних механізмів. В.В. СЕМЕНОВ Компьютерная математика. 2015, № 1140 До цього напрямку належить відомий метод відпалу, для теоретичного обґрун- тування якого використані ланцюги Маркова, що надало можливість довести при достатньо загальних припущеннях його збіжність до глобального розв’язку з ймовірністю, яка прямує до одиниці. Однак проведені чисельні експерименти показали, що для багатьох прикладних задач не можна досягти глобального ек- стремуму при прийнятному обсязі обчислень. У зв’язку з цим були запропоновані наближені алгоритми розв’язання дискретних задач оптимізації, загальна обчислювальна схема яких може бути інтерпретована як певне розши- рення схеми методу вектора спаду [2] за рахунок включення в неї на кожній ітерації можливостей випадкового переходу не тільки до кращих за значенням цільової функції, але й до гірших розв’язків, що властиве методу відпалу. Це дозволяє уникати «поганих» локальних оптимумів і знаходити розв’язки, близькі до глобального оптимуму. Проведені обчислювальні експерименти [2] продемонстрували досить високу ефективність нових алгоритмів для задач комівояжера, квадратичних задач про призначення, ряду задач оптимального проектування та інших прикладних задач. У зв’язку з необхідністю створення нових оптимізаційних методів, які в по- вній мірі використовують можливості сучасних багатопроцесорних комплексів, слід особливо відзначити можливість створення на основі описаних методів пара- лельних алгоритмів, призначених для багатопроцесорних ЕОМ, в яких досягаєть- ся суттєве зменшення часу розв’язування із збільшенням кількості процесорів. Висновки. Наведений підхід до розв’язання багатокритеріальних задач дис- кретної оптимізації та побудований паралельний алгоритм дозволяють отриму- вати більш точні розв’язки за менший час. Такі результати досягнуті на основі підходу, заснованому на побудові функцій скаляризації, що використовують множини опорних точок, та за рахунок застосування паралельних обчислень. В результаті роботи алгоритму знаходиться множина недомінованих розв’язків, що апроксимують множину Парето розв’язуваної задачі, і відповідна їй недомі- нована множина оцінок у просторі критеріїв. З представленої множини розв’язків, у разі потреби, ОПР може вибрати один або декілька варіантів розв’язків задачі, що видаються алгоритмом. В.В. Семенов АЛГОРИТМЫ РАСПАРАЛЛЕЛИВАНИЯ ВЫЧИСЛЕНИЙ ДЛЯ ВЕКТОРНЫХ ЗАДАЧ ДИСКРЕТНОЙ ОПТИМИЗАЦИИ Разработан подход к решению векторных задач дискретной оптимизации, в котором для на- хождения Парето-оптимальных решений используется множество опорных точек. Данный подход ориентирован для выполнения параллельних вычислений. Построен параллельный алгоритм, использующий идеи метода вектора спада, в результате работы которого находит- ся множество недоминируемых решений, которые аппроксимируют множество Парето ре- шаемой задачи, и соответствующее ему недоминируемое множество оценок в пространстве критериев. АЛГОРИТМИ РОЗПАРАЛЕЛЮВАННЯ ОБЧИСЛЕНЬ ДЛЯ ВЕКТОРНИХ ЗАДАЧ ... Компьютерная математика. 2015, № 1 141 V.V. Semenov ALGORITHMS OF PARALLELING CALCULATIONS FOR VECTOR PROBLEMS OF DISCRETE OPTIMIZATION 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 par- allel 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. 1. Сергиенко И.В. Математические модели и методы решения задач дискретной оптимиза- ции (2-е изд., доп. и перераб.).  Киев: Наук. думка, 1988.  472 с. 2. Сергиенко И.В., Шило В.П. Задачи дискретной оптимизации: проблемы, методы решения, исследования. – Киев: Наук. думка, 2003. – 264 с. 3. Финкельштейн Ю.Ю. Приближенные методы и прикладные задачи дискретного про- граммирования. – М.: Наука, 1976.  266 с. 4. Семенова Н.В., Колєчкіна Л.М. Векторні задачі дискретної оптимізації на комбінаторних множинах: методи дослідження та розв’язання. – К.: Наук. думка, 2009. – 266 с. 5. Подиновский В.В., Ногин В.Д. Парето-оптимальные решения многокритериальных задач. – М.: Наука, 1982.  256 с. 6. Штойер Р. Многокритериальная оптимизация. Теория, вычисления и приложения. – М.: Радио и связь, 1992. – 504 с. 7. Семенов В.В., Семенова Н.В. Розпаралелювання процесу розв’язання векторних задач комбінаторної оптимізації за умов невизначеності та ризику // Компьютерная математи- ка. – 2014. – № 1. – C. 83 – 92. 8. Wierzbicki A. The use of reference objectives in multiobjective optimization / In G. Fandel and T. Gal, editors // Multiple Objective Decision Making, Theory and Application, Springer- Verlag, 1980. – Vol. 177 in Lecture Notes in Economics and Mathematical Systems. – P. 468 – 486. 9. Melab N., Talbi E.-G., Cahon S., Alba E., Luque G. Parallel metaheuristics: Models and frameworks / E.-G. Talbi, editor // Parallel Combinatorial Optimization. – Chichester, UK: John Wiley & Sons, 2006. – chapter 6. – P. 149 – 162. Одержано 25.01.2015 Про автора: Семенов Віктор Вікторович, молодший науковий співробітник Інституту кібернетики імені В.М. Глушкова НАН України. Е-mail: hunt.semen@gmail.com

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

Репозитарії

Схожі ресурси