Современные подходы к решению сложных задач дискретной оптимизации

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

Повний опис

Збережено в:

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

Репозитарії

Digital Library of Periodicals of National Academy of Sciences of Ukraine

id	irk-123456789-208062
record_format	dspace
spelling	irk-123456789-2080622025-10-19T00:18:23Z Современные подходы к решению сложных задач дискретной оптимизации Сучасні підходи до розв'язання складних задач дискретної оптимізації Modern approaches to solving complex discrete optimization problems Сергиенко, И.В. Шило, В.П. Оптимальное управление и методы оптимизации Запропоновано підходи до розв’язання складних задач дискретної оптимізації в послідовному і паралельному режимах. Вони базуються на використанні ідей методу глобального рівноважного пошуку та специфіки задач, що розглядаються. Розпаралелювання процесу розв’язання задач здійснюється за допомогою запропонованої методології побудови об’єднання (портфелів і команд) алгоритмів. Результати численних обчислювальних експериментів, проведених на ПК та суперкомп’ютері СКІТ-4 ІК НАНУ, підтверджують ефективність розроблених підходів. The approaches to solving complex discrete optimization problems in sequential and parallel modes are considered. They are based on the use of the ideas of global equilibrium search method and the specific features of problems under consideration. Parallelization problem solving process is carried out using the proposed methodology associations (portfolios and teams) algorithms. The results of extensive computational experiments carried out on the PC and SKIT-4 supercomputer of ICyb NASU, confirm the effectiveness of the developed approaches. 2016 Article Современные подходы к решению сложных задач дискретной оптимизации / И.В. Сергиенко, В.П. Шило // Проблемы управления и информатики. — 2016. — № 1. — С. 32-40. — Бібліогр.: 21 назв. — рос. 0572-2691 https://nasplib.isofts.kiev.ua/handle/123456789/208062 519.854 10.1615/JAutomatInfScien.v48.i1.30 ru Проблемы управления и информатики application/pdf Інститут кібернетики ім. В.М. Глушкова НАН України
institution	Digital Library of Periodicals of National Academy of Sciences of Ukraine
collection	DSpace DC
language	Russian
topic	Оптимальное управление и методы оптимизации Оптимальное управление и методы оптимизации
spellingShingle	Оптимальное управление и методы оптимизации Оптимальное управление и методы оптимизации Сергиенко, И.В. Шило, В.П. Современные подходы к решению сложных задач дискретной оптимизации Проблемы управления и информатики
description	Запропоновано підходи до розв’язання складних задач дискретної оптимізації в послідовному і паралельному режимах. Вони базуються на використанні ідей методу глобального рівноважного пошуку та специфіки задач, що розглядаються. Розпаралелювання процесу розв’язання задач здійснюється за допомогою запропонованої методології побудови об’єднання (портфелів і команд) алгоритмів. Результати численних обчислювальних експериментів, проведених на ПК та суперкомп’ютері СКІТ-4 ІК НАНУ, підтверджують ефективність розроблених підходів.
format	Article
author	Сергиенко, И.В. Шило, В.П.
author_facet	Сергиенко, И.В. Шило, В.П.
author_sort	Сергиенко, И.В.
title	Современные подходы к решению сложных задач дискретной оптимизации
title_short	Современные подходы к решению сложных задач дискретной оптимизации
title_full	Современные подходы к решению сложных задач дискретной оптимизации
title_fullStr	Современные подходы к решению сложных задач дискретной оптимизации
title_full_unstemmed	Современные подходы к решению сложных задач дискретной оптимизации
title_sort	современные подходы к решению сложных задач дискретной оптимизации
publisher	Інститут кібернетики ім. В.М. Глушкова НАН України
publishDate	2016
topic_facet	Оптимальное управление и методы оптимизации
url	https://nasplib.isofts.kiev.ua/handle/123456789/208062
citation_txt	Современные подходы к решению сложных задач дискретной оптимизации / И.В. Сергиенко, В.П. Шило // Проблемы управления и информатики. — 2016. — № 1. — С. 32-40. — Бібліогр.: 21 назв. — рос.
series	Проблемы управления и информатики
work_keys_str_mv	AT sergienkoiv sovremennyepodhodykrešeniûsložnyhzadačdiskretnojoptimizacii AT šilovp sovremennyepodhodykrešeniûsložnyhzadačdiskretnojoptimizacii AT sergienkoiv sučasnípídhodidorozvâzannâskladnihzadačdiskretnoíoptimízacíí AT šilovp sučasnípídhodidorozvâzannâskladnihzadačdiskretnoíoptimízacíí AT sergienkoiv modernapproachestosolvingcomplexdiscreteoptimizationproblems AT šilovp modernapproachestosolvingcomplexdiscreteoptimizationproblems
first_indexed	2025-10-19T01:10:43Z
last_indexed	2025-10-20T01:14:07Z
_version_	1846461435644739584
fulltext	© И.В. СЕРГИЕНКО, В.П. ШИЛО, 2016 32 ISSN 0572-2691 ОПТИМАЛЬНОЕ УПРАВЛЕНИЕ И МЕТОДЫ ОПТИМИЗАЦИИ УДК 519.854 И.В. Сергиенко, В.П. Шило СОВРЕМЕННЫЕ ПОДХОДЫ К РЕШЕНИЮ СЛОЖНЫХ ЗАДАЧ ДИСКРЕТНОЙ ОПТИМИЗАЦИИ Введение Известно, что многие задачи принятия оптимальных решений, возникающие в различных сферах человеческой деятельности, могут быть сформулированы в тер- минах дискретного программирования. Класс задач дискретной оптимизации весьма многообразен и включает целочисленное программирование, экстремальные комби- наторные задачи, оптимизационные задачи на графах, булево программирование. Численные методы решения задач этого класса, как правило, имеют трудоем- кость, экспоненциально зависящую от их размерности. Поэтому их точное решение при больших размерностях становится невозможным. Альтернативой является приближенное решение таких задач. При постоянно возрастающей сложности оптимизируемых объектов естественно усложнение их математических моделей, что значительно затрудняет поиск решений таких задач. В связи с этим актуальны разработка, исследование новых и усовершенствование существующих при- ближенных методов решения и соответствующих программных средств для дискретных оптимизационных задач. Следует отметить, что необходимый элемент исследования различных классов задач дискретной оптимизации и методов реше- ния — их экспериментальное исследование. Известно, что алгоритмы с различной эффективностью решают отдельные клас- сы задач. Поэтому, чем шире их набор у пользователя, тем больше вероятность полу- чения приемлемых решений с минимумом затрат. Настоящая статья посвящена результатам, полученным в последнее время в Институте кибернетики им. В.М. Глушкова НАН Украины под руководством и непосредственном участии авторов, в области решения дискретных оптимизаци- онных задач сложной природы в последовательном и параллельном режимах. Теоретические исследования моделей, методов и свойств различных классов за- дач дискретной оптимизации ведутся в Институте кибернетики с 60-х годов ХХ ст. Накоплен большой опыт их практического использования. В 1961 г. в работе [1] был предложен метод последовательного анализа вариантов для решения вариа- ционных задач управления, планирования и проектирования, основанный на тео- ретико-множественном подходе к поиску решения. Этот метод получил дальней- шее развитие в многочисленных публикациях [2, 3 и др.]. В [4] предложен подход к решению задач дискретной оптимизации общего вида: найти },)({min Gxxf  60 1956 2016 - Международный научно-технический журнал «Проблемы управления и информатики», 2016, № 1 33 где G — конечное или счетное множество допустимых решений задачи, )(xf — определенная на нем функция. Эта алгоритмическая схема названа методом век- тора спада. На основе данной схемы разработаны алгоритмы локального поиска для различных классов задач дискретного программирования (например, [5–9]), которые нашли применение при решении практических задач. Разработанные алгоритмы использовались в созданных в Институте кибер- нетики пакетах прикладных программ (ППП) серии ДИСПРО, ориентированных на решение широкого спектра общих и специальных задач дискретного програм- мирования; ППП ДИСНЕЛ — задач дискретной и нелинейной оптимизации; ППП ПЛАНЕР — специальных классов задач производственно-транспортного пла- нирования большой размерности и др. С помощью этих пакетов были решены прикладные задачи. Следует отметить также интересные результаты [10 и др.], полученные при решении специальных классов задач дискретной оптимизации. Некоторые применения метода глобального равновесного поиска Расширение сфер применения и постоянно возрастающая сложность объек- тов, процессов, структур, которые оптимизируются, усложняет математические модели, существенно увеличивает размерность задач (до сотен тысяч переменных и ограничений) и затрудняет поиск решений. Это обстоятельство стимулировало дальнейшее развитие научных исследований, касающихся создания новых подхо- дов к решению дискретных оптимизационных задач сложной природы. Один из таких подходов предложен в работе [11] — это вероятностный метод глобального равновесного поиска (ГРП) для решения сложных дискретных опти- мизационных задач вида: найти },)({min nBGxxf  где ,nRG  nR — множество n-мерных действительных векторов; nB — мно- жество n-мерных векторов, компоненты которых принимают значения 0 или 1. В этом методе получили дальнейшее развитие идеи методов вектора спада и от- жига. Метод ГРП (GES) широко применяется при решении различных классов задач дискретной оптимизации сложной природы, в том числе задач на графах. В последние годы он все больше привлекает внимание исследователей. Рассмотрим вкратце некоторые конкретные применения метода GES. Из- вестно, что задача о максимальном взвешенном разрезе графа (WMAXCUT) — классическая проблема дискретного программирования с многочисленными прак- тическими приложениями, среди них: проектирование сетей связи, сверхбольших интегральных схем, фазированных антенных решеток, моделирование нейронных сетей, распознавание образов, анализ больших массивов данных, задачи физики твердого тела и др. Задача о максимальном взвешенном разрезе графа имеет такую теоретико- графовую интерпретацию. Пусть задан неориентированный граф ),( EVGG  с множествами вершин V и ребер .E Каждому ребру Eji ),( графа соответ- ствует вес .0ijw Разрезом графа G называется разбиение ),( 21 VV множества V на два непересекающихся подмножества: 1V и ,2V такие, что ,1Vi .2Vj Очевидно, что любое такое разбиение порождает разрез графа. Задача о макси- мальном взвешенном разрезе неориентированного графа G состоит в нахождении разреза максимального суммарного веса .),( ),(,, 21 21 ij EjiVjVi wVVw    34 ISSN 0572-2691 Задача WMAXCUT NP-трудная даже в случае, когда все ребра имеют еди- ничный вес. Для ее решения предложены алгоритмы [12–14], базирующиеся на использовании метода GES [9, 11]. Ключевыми моментами данного метода явля- ются: генерация решения и поиск локального экстремума в окрестности этого ре- шения. В процедуре поиска локального экстремума использовались различные варианты алгоритмов локального типа и табу. При проведении вычислительных экспериментов было рассмотрено множе- ство тестовых задач из сайта http://www.stanford.edu/~yyye/yyye/Gset/, которые широко используются для проверки эффективности алгоритмов решения задач WMAXCUT. Эти задачи включают тороидальные, планарные и случайные графы с числом вершин V от 800 до 20000 и весами 1, 0 или – 1. По результатам многочисленных экспериментальных исследований разрабо- танные алгоритмы [12–14] имеют полное преимущество перед лучшими, извест- ными для таких задач, алгоритмами. В частности, с их помощью улучшены ре- корды (наилучшие значения целевой функции) для 37 из 74 решавшихся задач большой размерности, для остальных задач найдены известные рекорды, как пра- вило, с меньшими затратами времени. Рассмотрим задачу булевого квадратичного программирования без ограниче- ний (UBQP) вида: найти ,)(max 11            n jiij n j n i Bxxxqxf (1) где ijq — элементы симметричной действительной матрицы Q порядка n, nB — множество n-мерных векторов с компонентами 0 или 1. К модели (1) сводятся фундаментальные задачи медицины, экономики, инжене- рии, физики, химии и др., в частности области, связанной с освоением космоса. Мно- гие задачи теории графов можно представить в виде булевого квадратичного програм- мирования, в частности хорошо изученные задачи нахождения максимальной клики и максимального взвешенного разреза графа. Например, задачу о максимальном взве- шенном разрезе графа можно сформулировать таким образом: найти ,)()(max 2 ),(            n jiij Eji Bxxxwxf где ijw — вес, отвечающий каждому ребру Eji ),( графа. Кроме того, задача UBQP — общая модель для широкого круга дискретных оптимизационных задач. Известны примеры ее использования при рассмотрении задач раскраски вершин графа, упаковки, разбиения, линейного упорядочения и др. Для решения задач вида (1) разработаны и исследованы алгоритмы глобаль- ного равновесного поиска [15, 16]. На основании экспериментальных расчетов проведено сравнение результатов, полученных с помощью алгоритмов GES, с ре- зультатами лучших известных алгоритмов. Оно показало превосходство алгорит- мов GES как по качеству найденных решений, так и по времени счета. На основе метода GES разработаны алгоритмы решения многомерной задачи о ранце, задач нахождения максимального независимого множества вершин графа, о максимальной выполнимости, о покрытии множества, об упаковке множества максимального веса, раскраски графа, о p-медиане, составления расписания и др. С применением алгоритма GES создано также программно-алгоритмическое обеспечение для решения задачи коммивояжера. Результаты экспериментальных расчетов В последнее время на основе метода глобального равновесного поиска нами разработаны серия алгоритмов GESPR нового поколения и соответствующее про- Международный научно-технический журнал «Проблемы управления и информатики», 2016, № 1 35 граммное обеспечение, с помощью которых решались задачи WMAXCUT и UBQP очень большой размерности. Отличительная особенность этих алгоритмов — про- ведение осцилляции на основе методологии Path Relinking [17] вокруг наилучше- го найденного решения .bestx Все вычислительные эксперименты проводились с использованием PC с Intel® Core QUAD CPU Q9550 2.83GHz и 8.0GB оперативной памяти в режиме реального времени. Было рассмотрено множество те- стовых задач из сайта http://www.stanford . edu/~yyye/yyye/Gset/, которые ранее не рас- сматривались авторами. В таблице отражены некоторые резуль- таты сравнительного исследования рекордов, найденных одним из алгоритмов GESPR и ал- горитмом BLS [18]. В первуй колонке табли- цы указан номер задачи, во второй V — мощность множества V (число вершин гра- фа G). Следует отметить, что на период пуб- ликации работы [18] алгоритм BLS был луч- шим для задачи WMAXCUT, а в дальнейшем таким стал алгоритм GESPR [19]. Для всех задач из таблицы алгоритмом GESPR найде- ны новые рекорды. Подходы к распараллеливанию процесса оптимизации При решении дискретных оптимизационных задач большой размерности, в част- ности задач WMAXCUT и UBQP, возникает необходимость обработки больших объе- мов данных за приемлемое время. Эффективное решение таких задач возможно на параллельных компьютерах. Распараллеливание вычислений не только эффективно, но часто и единственно возможный способ решения сложных задач дискретного про- граммирования большой размерности во многих отраслях. Кроме того, в ближайшие годы ожидается появление высокопроизводительных настольных ПК (high-end desk- top — HEDT) и задачи, решаемые сейчас на многопроцессорных комплексах типа СКИТ, смогут эффективно решаться на этих ПК. В связи с этим возрастает потребность в создании эффективных алгоритмов дискретной оптимизации и соответствующих программных средств для парал- лельных вычислений на многопроцессорных вычислительных комплексах. С этим перспективным направлением и связаны наши дальнейшие исследования. Распараллеливание процесса оптимизации имеет свою специфику. Так, если некоторый вычислительный алгоритм распараллеливается на P процессоров, обычно лучшее, на что можно надеяться, это ускорение в P раз, т.е. линейное. Например, P землекопов, если не будут мешать друг другу, выроют P ям в P раз быстрее, чем один. Но обычно очень трудно так построить работу, чтобы земле- копы не мешали друг другу. Процесс оптимизации не связан с обработкой какого- то заданного объема вычислений, как в случае вычислительных алгоритмов. Объ- ем вычислений зависит от хода процесса оптимизации. Возвращаясь к аналогии с землекопами, предположим, что цель землекопа — найти клад. Для этого он дол- жен проверить (выкопав ямы) P мест. Если клад лежит на поверхности, то земле- Таблица Задача V BLS GES G55 5000 10294 10299 G56 5000 4012 4017 G57 5000 3492 3494 G58 5000 19263 19293 G59 5000 6078 6086 G60 7000 14176 14188 G61 7000 5789 5796 G62 7000 4868 4870 G63 7000 26997 27045 G64 7000 8735 8751 G65 8000 5558 5562 G66 9000 6360 6364 G67 10000 6940 6950 G70 10000 9541 9591 G72 10000 6998 7006 G77 14000 9926 9938 G81 20000 14030 14056 36 ISSN 0572-2691 копы вообще не будут копать, так как один из них сразу же обнаружит его. В этом случае на поиск клада уйдет времени меньше, чем в P раз. Можно выделить следующие основные типы распараллеливания: операций, декомпозиционное, копий алгоритма. Под распараллеливанием операций, выполняемых оптимизационным алго- ритмом, понимается представление алгоритма в виде последовательности групп операций. Все операции одной группы должны быть независимыми и обладать возможностью выполняться одновременно на имеющихся в системе процессорах. Группы операций должны быть упорядочены так, что каждая операция любой группы зависит либо от исходных данных, либо от результатов выполнения опе- раций из предыдущих групп. Заметим, что с ростом числа процессоров могут воз- никать проблемы с выбором групп операций и организацией обмена информацией между ними. Обмен информацией и ее обработка могут забирать очень много времени и понижать эффективность распараллеливания. Под декомпозиционным распараллеливанием понимается разбиение задачи на множество подзадач, каждую из которых можно независимо решать на выде- ленных для этого процессорах. Интересные, на наш взгляд, подходы связаны с вероятностной декомпозицией [9]. Весьма перспективным, с нашей точки зрения, является подход, когда вместо операций, выполняемых алгоритмом, распараллеливаются его копии [9]. Это име- ет смысл, когда речь идет о рандомизированных алгоритмах, где каждый экзем- пляр (копия) одного и того же алгоритма использует некоторое начальное значе- ние для инициализации его генератора псевдослучайных чисел. В этом случае разные начальные значения будут давать различающиеся между собой траектории поиска решений. В работах [19–21] предложен и развит новый подход к построению объеди- нения (портфелей и команд) алгоритмов глобального равновесного поиска для распараллеливания процесса решения задач WMAXCUT и UBQP, который обоб- щает и развивает исследования по распараллеливанию копий алгоритмов. Пусть имеется множество алгоритмов },...,,{ 1 nAAA  которые работают параллельно на P разных процессорах. Каждый алгоритм должен решать одну и ту же задачу. Любой процессор может использоваться одним алгоритмом мно- жества A, а один и тот же алгоритм использоваться на разных процессорах. Объединением алгоритмов }...,,{ 11 mmAnAnunion для P процессоров, где , 1 i m i nP    будем называть список независимых алгоритмов AAi  с указанием количества ,...,,1, mini  используемых ими процессоров. Объединение алгоритмов, которые не обмениваются между собой информа- цией, будем называть портфелем алгоритмов },...,,{ 11 mmAnAnportfolio а объеди- нение алгоритмов, которые обмениваются между собой информацией, — коман- дой алгоритмов }....,,{ 11 mmAnAnteam Заметим, что время решения задачи с по- мощью объединения алгоритмов (портфеля или команды) определяется временем самого быстрого ее решения на одном из процессоров, т.е. , min ,...,1 j Pj union tt   где jt — время решения задачи на j-м процессоре. В команду может входить и управляющий алгоритм, который осуществ- ляет выбор подмножества алгоритмов для проведения оптимизации, составле- ние схемы и формата обмена информацией между ними, возможную коррек- Международный научно-технический журнал «Проблемы управления и информатики», 2016, № 1 37 тировку выбранной схемы или формата в зависимости от хода решения и, наконец, проведение необходимой замены алгоритмов в процессе оптимиза- ции. Алгоритм команды должен уметь, прежде всего, воспринимать информа- цию, использовать ее. Например, если задача решается с помощью команды алгоритмов локального поиска, то какой-либо обмен информацией между ни- ми не имеет смысла, поскольку эти алгоритмы не приспособлены к использо- ванию внешней информации. Отметим, что кроме вычислительной эффективности главное преимущество метода глобального равновесного поиска — его командные свойства, под кото- рыми понимаем способность эффективно использовать решения, полученные другими алгоритмами. Обмен информацией дает возможность усилить лучшие качества алгоритма, который приводит как к уменьшению времени счета, так и к улучшению качества решения. Экспериментальные исследования с использованием суперкомпьютера СКИТ-4 В дальнейшем экспериментальные исследования по распараллеливанию про- цесса решения задач WMAXCUT и UBQP проводились на многопроцессорном вычислительном комплексе СКИТ-4 ИК НАН Украины. Для их проведения ис- пользовались тестовые задачи G77 и G81 из вышеупомянутого множества тесто- вых задач о максимальном взвешенном разрезе графа с числом вершин соответ- ственно 14000 и 20000, которые, как отмечалось выше, формулируются в терми- нах булевого квадратичного программирования. Ускорение процесса решения задачи G77 с помощью портфелей алгоритмов GESPR по сравнению с одним алгоритмом показано на рис. 1. На оси абсцисс ука- заны достигнутые значения целевой функции, а на оси ординат — коэффициенты ускорения этого процесса. 1 alg 2 alg 4 alg 8 alg 16 alg 32 alg 64 alg 128 alg 9900 9904 9908 9912 9916 9920 9924 9928 9932 9936 5 15 25 35 45 55 65 75 Рис. 1 На рис. 2 показано ускорение процесса решения задачи G81 с помощью портфелей и команд алгоритмов GESPR по сравнению с одним алгоритмом. Обо- значения рис. 2 и рис. 3 совпадают с соответствующими обозначениями рис. 1. 38 ISSN 0572-2691 Полученные результаты свидетельствуют о том, что портфель из 128 алго- ритмов GESPR в 80 раз быстрее находит решение задачи G77 со значением целе- вой функции 9938 и в 123 раза быстрее находит решение задачи G81 со значением целевой функции 14054, чем один алгоритм. Команда из 32 алгоритмов в 95 раз быстрее, чем один алгоритм, находит решение с таким же значением целевой функции. Как видим, при использовании команд алгоритмов достигается сверхлинейное ускорение. Такие же результаты имеют место для команд, состав- ленных из восьми и шестнадцати алгоритмов. Очевидно, что при построении портфеля из четырех команд алгоритмов, в которые входит по 32 алгоритма, можно получить ускорение относительно одного алгоритма больше, чем в 289 раз. port8 port16 port32 port128 team8 team16 team32 14030 14032 14034 14036 14038 14040 14042 14044 14046 14048 10 20 30 40 50 60 70 80 14050 14052 14054 90 100 110 120 Рис. 2 port8 vs team8 port16 vs team16 port32 vs team32 14030 14032 14034 14036 14038 14040 14042 14044 14046 14048 0,8 1,0 1,2 1,4 1,6 1,8 2,0 2,2 14050 14052 14054 2,4 2,6 2,8 3,0 Рис. 3 Ускорение работы команд относительно портфелей алгоритмов GESPR для задачи G81 показано на рис. 3. Из этого рисунка видно, что команда, составленная Международный научно-технический журнал «Проблемы управления и информатики», 2016, № 1 39 из 32 алгоритмов, в три раза быстрее, чем портфель из 32 алгоритмов, находит решение со значением целевой функции 14054. Графики рис. 3 показывают, что команды алгоритмов всегда находят решения высокого качества быстрее, чем портфели алгоритмов. Заключение Таким образом, проведенные исследования показали, что подходы к ре- шению сложных задач дискретной оптимизации, основанные на использова- нии метода глобального равновесного поиска, являются в настоящее время практически эффективными средствами дискретного программирования, причем их эффективность особенно проявляется при решении задач большой размерности. Анализ полученных результатов распараллеливания процесса решения сложных задач WMAXCUT и UBQP с использованием предложенной автора- ми методологии построения объединения (портфелей и команд) алгоритмов показал существенное ускорение (иногда более, чем в 100 раз) процесса их решения с помощью объединения алгоритмов глобального равновесного поис- ка по сравнению с одним алгоритмом. Он свидетельствует о перспективности дальнейших исследований по созданию команд алгоритмов, в частности по разработке эффективных протоколов обмена информацией между алгоритма- ми, которые входят в состав команд. І.В. Сергієнко, В.П Шило СУЧАСНІ ПІДХОДИ ДО РОЗВ’ЯЗАННЯ СКЛАДНИХ ЗАДАЧ ДИСКРЕТНОЇ ОПТИМІЗАЦІЇ Запропоновано підходи до розв’язання складних задач дискретної оптимізації в послідовному і паралельному режимах. Вони базуються на використанні ідей методу глобального рівноважного пошуку та специфіки задач, що розглядаються. Розпаралелювання процесу розв’язання задач здійснюється за допомогою за- пропонованої методології побудови об’єднання (портфелів і команд) алгорит- мів. Результати численних обчислювальних експериментів, проведених на ПК та суперкомп’ютері СКІТ-4 ІК НАНУ, підтверджують ефективність розробле- них підходів. I.V. Sergienko, V.P. Shylo MODERN APPROACHES TO SOLVING COMPLEX DISCRETE OPTIMIZATION PROBLEMS The approaches to solving complex discrete optimization problems in sequential and parallel modes are considered. They are based on the use of the ideas of global equi- librium search method and the specific features of problems under consideration. Parallelization problem solving process is carried out using the proposed methodolo- gy associations (portfolios and teams) algorithms. The results of extensive computa- tional experiments carried out on the PC and SKIT-4 supercomputer of ICyb NASU, confirm the effectiveness of the developed approaches. 1. Михалевич В.С., Шор Н.З. Метод последовательного анализа вариантов при решении вари- ационных задач управления, планирования и проектирования // Докл. на IV Всесоюз. мат. съезде. — М., 1961. — 91 с. 40 ISSN 0572-2691 2. Вычислительные методы выбора оптимальных проектных решений / Под ред. В.С. Миха- левича. — Киев : Наук. думка, 1977. — 178 с. 3. Михалевич В.С., Волкович В.Л. Вычислительные методы исследования и проектирования сложных систем. — М. : Наука, 1982. — 286 с. 4. Сергієнко І.В. Один метод розв’язування задач на відшукання екстремальних значень // Ав- томатика. — 1964. — № 5. — С. 15–21. 5. Сергиенко И.В. Математические модели и методы решения задач дискретной оптимиза- ции. — Киев : Наук. думка, 1988. — 471 с. 6. Sergienko Ivan V. Methods of optimization and systems analysis for problems of transcomputa- tional complexity. — New York; Heidelberg; Dordrecht; London : Springer, 2012. — 226 p. 7. Сергиенко И.В., Лебедева Т.Т., Рощин В.А. Приближенные методы решения дискретных за- дач оптимизации. — Киев : Наук. думка, 1980. — 276 с. 8. Сергиенко И.В., Каспшицкая М.Ф. Модели и методы решения на ЭВМ комбинаторных за- дач оптимизации. — Киев : Наук. думка, 1981. — 288 с. 9. Сергиенко И.В., Шило В.П. Задачи дискретной оптимизации: проблемы, методы решения, исследования. — Киев : Наук. думка, 2003. — 262 с. 10. Михалевич В.С., Трубин В.А., Шор Н.З. Оптимизационные задачи производственно- транспортного планирования. — М. : Наука, 1986. — 264 с. 11. Шило В.П. Метод глобального равновесного поиска // Кибернетика и системный анализ. — 1999. — № 1. — С. 74–81. 12. Шило В.П., Шило О.В. Решение задачи о максимальном разрезе графа методом глобально- го равновесного поиска // Там же. — 2010. — № 5. — С. 68–79. 13. Shylo V.P., Shylo O.V. Path relinking scheme for the max-cut problem within global equilibrium // International Journal of Swarm Intelligence Research (IJSIR). — 2011. — 2, N 2. — P. 42–51. 14. Шило В.П., Шило О.В., Рощин В.А. Метод глобального равновесного поиска решения зада- чи о максимальном взвешенном разрезе графа // Кибернетика и системный анализ. —2012. — № 4. —С. 101–105. 15. Global equilibrium search applied to the unconstrained binary quadratic optimization problem / P.M. Pardalos, O.A. Prokopyev, O.V. Shylo, V.P. Shylo // Optimization Methods and Software. — 2008. — 23. — P. 129–140. 16. Шило В.П., Шило О.В. Решение задачи булева квадратичного программирования без огра- ничений методом глобального равновесного поиска // Кибернетика и системный анализ. — 2011. — № 6. — С. 68–78. 17. Glover F., Laguna M., Marti R. Fundamentals of scatter search and path relinking // Control and Cybernetics. — 2000. — 39. — P. 653–684. 18. Benlic U., Hao J.K. Breakout local search for the max-cut problem // J. Engineering Applications of Artificial Intelligence . — 2013. — 26(3). — P. 1162–1173. 19. Shylo V.P., Glover F., Sergienko I.V. Teams of global equilibrium search algorithms for solving weighted MAXIMUM CUT problem in parallel // Кибернетика и системный анализ. — 2015. — № 1. — C. 20–29. 20. Шило В.П., Рощин В.А., Шило П.В. Построение портфеля алгоритмов для распараллелива- ния процесса решения задачи о максимальном взвешенном разрезе графа // Компьютерная математика. — 2014. — № 2. — C. 163–170. 21. Шило В.П., Рощин В.О., Шило П.В. Паралельні алгоритми розв'язання задач булевого квад- ратичного програмування // Там же. — 2015. — № 2. — C. 12–20. Получено 30.11.2015

Современные подходы к решению сложных задач дискретной оптимизации

Репозитарії

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