АЛГОРИТМИ НА ФРАГМЕНТАРНИХ СТРУКТУРАХ ДЛЯ ЗАДАЧІ ПРО РОЗБИТТЯ МНОЖИНИ НА ДВІ ЧАСТИНИ

Анотація

Досліджується проблема розбиття мультимножини чисел на дві частини у такий спосіб, щоб різниця між сумою чисел у двох частинах розбиття була мінімальною по модулю. Уже згадана задача належить до класу NP-важких задач, для неї невідомі алгоритми поліноміальної трудомісткості. Отже, для задачі виправдане застосування метаевристик різних типів. Показано, що задача має природну фрагментарну структуру, в якій елементарними фрагментами є одноелементні підмножини. Наявність фрагментарної структури дозволяє звести цю задачу до задачі комбінаторної оптимізації на множині перестановок. Множина перестановок розглядається при цьому як метричний простір з метрикою Кендалла. Причому будь-якому допустимому розв’язку вихідної задачі відповідає одна або кілька перестановок. Такий підхід дає можливість застосувати для пошуку наближених рішень задачі ряд алгоритмів пошуку оптимуму на множині перестановок. Найбільш простим і відомим алгоритмом пошуку оптимуму в метричному просторі є алгоритм локального пошуку в -околиці випадково обраної точки. Для забезпечення пошуку глобального оптимуму цей алгоритм застосовується кілька разів з різним вибором початкової точки. Фрагментарна структура задачі дозволяє побудувати універсальні алгоритми, що імітують природні процеси. У цій роботі розглянуті два алгоритми подібного виду. Це еволюційний алгоритм на множині перестановок і алгоритм мурашиної колонії. Для оцінки якості запропонованих метаевристик розроблений генератор випадкових задач розглянутого типу. Згенеровано кілька серій задач. Кожна із задач серії розв’язувалася шляхом використання трьох різних алгоритмів. Причому параметри алгоритмів підібрані у такий спосіб, щоб кількість обчислень значення цільової функції була приблизно однаковою в кожному випадку. На основі множини згенерованих задач проведено порівняння локального, еволюційного і мурашиного алгоритмів.