Технология ядра для решения задач дискретной оптимизации

• Опубліковано в: : Кибернетика и системный анализ
• Дата: 2017
• Автори: Сергиенко, И.В., Шило, В.П.
• Формат: Стаття
• Мова: Російська
• Опубліковано: Інститут кібернетики ім. В.М. Глушкова НАН України 2017
• Теми: Системний аналіз
• Онлайн доступ: https://nasplib.isofts.kiev.ua/handle/123456789/144809
• Назва журналу: Digital Library of Periodicals of National Academy of Sciences of Ukraine
• Цитувати: Технология ядра для решения задач дискретной оптимизации / И.В. Сергиенко, В.П. Шило // Кибернетика и системный анализ. — 2017. — Т. 53, № 6. — С. 73–83. — Бібліогр.: 15 назв. — рос.

Предложена новая технология для решения задач дискретной оптимизации, формирующая «ядро» решения, что позволяет эффективно случайно возмущать это решение в схемах итерирования. Проведено сравнительное исследование двух версий нового алгоритма решения квадратичной задачи о назначениях (с технологией выделения ядра и без неё) с современными алгоритмами, которое показало перспективность использования этой технологии как по быстродействию, так и по возможности получения лучших решений. Технологию ядра легко инкорпорировать в уже существующие алгоритмы. Запропоновано нову технологію для розв’язання задач дискретної оптимізації, яка формує «ядро» розв’язку, що дозволяє ефективно випадково збурювати цей розв’язок у схемах ітерування. Проведено порівняльне дослідження двох версій нового алгоритму розв’язання квадратичної задачі про призначення (з технологією виділення ядра і без неї) з сучасними алгоритмами. Воно показало перспективність використання цієї технології як за швидкодією, так і за можливістю отримання кращих розв’язків. Технологію ядра легко інкорпорувати в наявні алгоритми. A kernel technology is proposed for a wide class of discrete optimization problems. Based on the notion of kernel, the technology implements stochastic perturbations for the iterative algorithmic schemes. Computational study of the proposed technology for the quadratic assignement problem demonstrated efficiency of this technology in terms of speed and solution quality. The kernel method can be easily incorporated into the available algorithms.