Математичні моделі та метаевристичні алгоритми розв’язання оптимізаційних задач в просторі перестановок

Размещено на http://www.allbest.ru//

Размещено на http://www.allbest.ru//

Національна академія наук України

Інститут кібернетики імені В.М. Глушкова

01.05.02 - Математичне моделювання та обчислювальні методи

Автореферат

дисертації на здобуття наукового ступеня кандидата технічних наук

Математичні моделі та метаевристичні алгоритми розв'язання оптимізаційних задач в просторі перестановок

Гобов Денис Андрійович

Київ - 2010

Дисертацією є рукопис.

Робота виконана в Інституті кібернетики ім. В.М. Глушкова НАН України.

Науковий керівник

доктор технічних наук, старший науковий співробітник

Гуляницький Леонід Федорович,

Інститут кібернетики ім. В.М. Глушкова НАН України, провідний науковий співробітник відділу методів дискретної оптимізації, математичного моделювання та аналізу складних систем

Офіційні опоненти

доктор фізико-математичних наук, старший науковий співробітник

Донець Георгій Панасович,

Інститут кібернетики ім. В.М. Глушкова НАН України,

завідувач відділу економічної кібернетики

кандидат технічних наук, доцент

Кулян Віктор Романович

Київський Національний університет ім. Тараса Шевченка, доцент кафедри моделювання складних систем факультету кібернетики

Захист відбудеться ” 28 ” травня 2010 р. о 1200 годині на засіданні спеціалізованої вченої ради Д 26.194.02 в Інституті кібернетики ім. В.М. Глушкова НАН України за адресою: 03680 МСП Київ 187, проспект Академіка Глушкова, 40.

З дисертацією можна ознайомитись в науково-технічному архіві Інституту кібернетики ім. В.М. Глушкова НАН України за адресою: 03680 МСП Київ 187, проспект Академіка Глушкова, 40.

Автореферат розісланий ” 22 ” квітня 2010 р.

Вчений секретар спеціалізованої вченої ради Д 26.194.02 О.А. Вагіс

Размещено на http://www.allbest.ru//

ЗАГАЛЬНА ХАРАКТЕРИСТИКА РОБОТИ

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

Одним з найбільш важливих класів оптимізаційних проблем є задачі комбінаторної оптимізації (ЗКО), які зустрічаються в багатьох галузях практичної діяльності - як приклади можна привести задачі проектування, прогнозування, планування, управління ресурсами та транспортними засобами, складання бюджету, мережевої маршрутизації та багато інших. Питанням розв'язання прикладних задач даного типу присвячено багато робіт, серед яких варто відзначити роботи зарубіжних авторів Х. Пападімітріу, К. Стайґліца, Д. Голланда, Ф. Ґловера, М. Доріґо, М. Ґері, Д. Джонсона, Г. Гооса, Т. Штютцля, П. Пардалоса, П. Хансена, Н. Младеновича, Е. Альба, E. Талбі та інших. В ході досліджень була розвинена теорія комбінаторної оптимізації, яка включає дослідження властивостей задач різних класів, точних та наближених методів розв`язання, підходів до побудови оцінки збіжності і трудомісткості алгоритмів оптимізації та інших аспектів. Вагомий внесок у розвиток теорії та методів оптимізації рішень у скінченних просторах внесли В.С. Михалевич, І.В. Сергієнко, Н.З. Шор, В.Л. Волкович, Л.Ф. Гуляницький, Г.О. Донець, Ю.І. Журавльов, В.К. Леонтьєв, О.А. Павлов, В.О. Перепелиця, Ю.Г. Стоян, Ю.Ю. Червак, В.П. Шило,

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

Одним із перспективних напрямків розвитку алгоритмів розв'язання ЗКО є розробка нових метаевристичних (комбінованих) алгоритмів. Більшість відомих метаевристик базуються на поєднанні популяційних алгоритмів - перш за все генетичних алгоритмів (ГА) - та алгоритмів пошуку в околах (детермінований та стохастичний локальний пошук, табу-пошук, імітаційний відпал (ІВ)).

В області дослідження математичних моделей та наближених алгоритмів розв'язання ЗКО існує ряд недостатньо вивчених на сьогодні проблем, до яких відносяться:

розробка математичних моделей та дослідження ефективності застосування наближених алгоритмів для розв'язання прикладних задач розміщення та передпроектного аналізу при побудові складних автоматизованих систем;

розробка ефективних підходів до диверсифікації пошуку в просторі розв'язків для метаевристичних алгоритмів;

отримання теоретичних оцінок збіжності траєкторних алгоритмів стохастичного локального пошуку; метаевристичний алгоритм гібридний

отримання оцінок практичної ефективності та теоретичних оцінок збіжності гібридних метаевристик.

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

Зв`язок роботи з науковими програмами, планами, темами. Робота виконувалась у відповідності до науково-дослідних тем Інституту кібернетики імені В.М. Глушкова НАН України:

В.Ф.К.135.13 «Розробка нових методів розв`язання складних дискретних та багатоекстремальних задач оптимізації та їх застосування» (2002-2006 рр.), номер держреєстрації 0102U009213;

В.Ф.135.16 «Розробити, обґрунтувати методи та програмно-алгоритмічні засоби для створення нових інформаційних технологій та систем» (2003-2007 рр.), номер держреєстрації 0103U000712.

Мета і завдання дослідження. Метою дисертаційної роботи є розробка та обґрунтування нових математичних моделей та метаевристичних алгоритмів розв'язання оптимізаційних задач в просторі перестановок, їх практична реалізація та апробація у прикладних областях.

Досягнення мети роботи пов`язане із постановкою та розв`язанням таких задач:

аналіз існуючих наближених алгоритмів комбінаторної оптимізації;

дослідження теоретичної збіжності алгоритмів прискореного ймовірнісного моделювання;

розробка метаевристичних алгоритмів, що поєднують в собі переваги алгоритмів із різних класів;

дослідження ефективності наближених алгоритмів комбінаторної оптимізації при розв'язанні задач розміщення одного класу;

побудова математичної моделі, практична реалізація та дослідження ефективності наближених алгоритмів комбінаторної оптимізації при розв'язанні задачі вибору порядку з'єднання таблиць бази даних в ході передпроектного дослідження складних автоматизованих систем.

Об'єктом дослідження є математичні моделі задач комбінаторної оптимізації та чисельні методи розв'язання таких задач.

Предметом дослідження є математичні моделі оптимізаційних задач в просторі перестановок, а також наближені стохастичні і гібридні метаевристичні методи їх розв'язання.

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

Наукова новизна одержаних результатів полягає в наступному.

Запропоновано новий ймовірнісний механізм для алгоритмів прискореного ймовірнісного моделювання. Використання цього механізму дозволило розробити нову обчислювальну схему алгоритмів цього класу

(G2-алгоритм) та отримати теоретичну оцінку збіжності до глобального оптимуму.

Запропоновано та теоретично обґрунтовано алгоритми побудови метричних відрізків в просторі перестановок, що включають дві задані точки. Розроблені алгоритми дозволили провести практичні дослідження реалізацій Н-методу при розв'язанні задач на просторі перестановок.

Запропоновано нові метаевристичні алгоритми Н-методу, побудовані на основі ідей VNS-алгоритму та G2-алгоритму, що дозволило підвищити ефективність розв'язання ряду ЗКО.

На основі Н-методу та мультиагентного підходу до дослідження простору допустимих розв'язків запропоновано новий метаевристичний моделеорієнтований метод розв'язання ЗКО, який в процесі розв'язання будує спеціальну модель задачі. Комбінування механізму глобального сканування простору та процедур навчання дозволило побудувати новий ефективний метаевристичний алгоритм.

Розроблено математичну модель задачі вибору порядку з'єднання таблиць бази даних, яка приводить до спеціальної ЗКО, та ряд наближених алгоритмів для її розв'язання.

Досліджено ефективність запропонованих алгоритмів при розв'язанні задачі розміщення прямокутних об'єктів вздовж смуг напівнескінченної стрічки з забороненими ділянками та задачі вибору порядку з'єднання таблиць бази даних.

Практичне значення одержаних результатів. Практична цінність роботи полягає у створенні ефективних прикладних алгоритмів комбінаторної оптимізації, які можуть бути застосовані для розв'язання широкого кола оптимізаційних задач в довільних локально скінченних просторах. Запропонована математична модель задачі вибору порядку з'єднання таблиць бази даних, яка виникає на етапі передпроектного дослідження при побудові складних автоматизованих систем, дозволяє, ґрунтуючись на експертних оцінках, провести аналіз вузьких місць системи, що проектується, до початку її розробки. Розроблена модель задачі та методи розв'язання використані при проектуванні автоматизованої системи інформаційно-аналітичного забезпечення фінансової системи АІС «Держбюджет», виконаної на замовлення міністерства фінансів України, та інтегрованої системи керування підприємством, розробленої на замовлення агропромислового холдингу «Ландгут-Україна». Розроблені та досліджені в дисертаційній роботі методи розв'язання задачі розміщення використані під час впровадження автоматизованої системи управління пасажирськими перевезеннями «Експрес-УЗМ», розробленої на замовлення Укрзалізниці.

Особистий внесок здобувача. Всі наукові результати дисертаційної роботи одержані особисто або за участі автора. В роботах, опублікованих у співавторстві, дисертантом отримано наступне: [1] - розроблені алгоритми розв'язання задач розміщення одного класу, проведено дослідження їх ефективності, розроблений генератор псевдовипадкових задач розміщення; проведено дослідження ефективності запропонованих алгоритмів при розв'язанні ряду задач розміщення; [2, 6] - розроблені та обґрунтовані алгоритми побудови відрізків та променів в просторі перестановок, реалізований один із алгоритмів запропонованого класу, проведено дослідження його ефективності при розв`язанні відомих квадратичних задач про призначення (КЗП) та серії тестових задач; [5] - запропоновані варіанти реалізації ймовірнісного механізму побудови відрізків та променів в просторі перестановок, реалізований один алгоритм з запропонованого класу, проведено дослідження його ефективності при розв'язанні задач комівояжера (ЗК) та КЗП.

Апробація результатів дисертації. Основні результати дисертації доповідались на:

7-й, 9-11-й Міжнародних науково-технічних конференціях «Системний аналіз та інформаційні технології» (м. Київ, 2005, 2007-2009 р.);

5-й Міжнародній науково-практичній конференції «Математичне та програмне забезпечення інтелектуальних систем» (м. Дніпропетровськ, 2007 р.);

Міжнародних симпозіумах «Питання оптимізації обчислень» ПОО-ХХХІІІ та ПОО-ХХХV (смт. Кацівелі, Крим, 2007, 2009 рр.);

Міжнародній науковій конференції «Knowledge-Dialogue-Solution» - KDS-2009 (м. Варна, Болгарія, 2009 р.).

Публікації. Основні результати дисертації опубліковано в 12 наукових працях. Серед них 5 наукових статей, у тому числі 3 у фахових виданнях, що входять у перелік видань затверджених ВАК України, 7 публікацій у матеріалах міжнародних конференцій.

Структура та об'єм роботи. Дисертаційна робота складається із вступу, шести розділів, висновків, списку використаної літератури та одного додатку. Повний обсяг дисертації становить 151 сторінку, з них 41 рисунок по тексту і 7 рисунків на окремих сторінках, 27 таблиць по тексту та 3 таблиці на окремих сторінках, 1 додаток на 3 сторінках, список літератури з 96 найменувань на 9 сторінках.

ОСНОВНИЙ ЗМІСТ

У вступі обґрунтовано актуальність теми дисертації, сформульовані мета і задачі дослідження, визначено об'єкт, предмет і методи дослідження. Подано коротку характеристику результатів дослідження та ступінь їх апробації.

Перший розділ присвячено огляду літератури за темою дисертаційної роботи та обґрунтуванню вибору напрямків досліджень.

Другий розділ присвячено дослідженню збіжності алгоритмів прискореного ймовірнісного моделювання (G-алгоритмів), що довели свою високу ефективність при розв'язанні широкого кола задач як при автономному застосуванні, так і у складі метаевристик. Метою дослідження є отримання теоретично обґрунтованих оцінок швидкості збіжності для алгоритмів даного класу.

Означення 2.1 Околом # з центром в точці x та радіусом r>0 називається множина #, де d(y, x) - метрика, визначена на просторі .

G-алгоритм починає роботу із деякого початкового наближення та на кожному кроці опрацьовує певний окіл поточного розв'язку. Подібно до методу ІВ, перехід можливий не лише до точок, яким відповідає краще значення цільової функції, але й з певною ймовірністю до точок, в яких цільова функція має гірше значення, аніж в поточному варіанті (центрі околу). Для побудови обчислювального процесу в G-алгоритмі формується строго монотонно зростаюча послідовність дійсних чисел 0??0 < ?1 <… ? 1, які відіграють роль, подібну до значень температури в методі ІВ. Нехай p(x,y) - імовірність переходу від точки x до y. Тоді, якщо x* - поточний варіант розв'язку, то варіант уO( x*, r), для якого f(y)>f(x*), може бути обраний як новий поточний варіант розв'язку, якщо p(x*, y) перевищить поточне значення h, збільшене на деяку випадкову величину.

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

Для розв'язання даної проблеми розроблено нову обчислювальну схему алгоритмів цього класу, що отримала назву G2-алгоритм, яка дозволяє надати теоретичне обґрунтування збіжності до глобального розв'язку. Суть модифікації полягає в новому імовірнісному механізмі, який застосовується для відсіву точок в околі поточного розв'язку. Нехай z - константа, яка задовольняє нерівності . Не обмежуючи загальності, вважаємо, що цільова функція на скінченній множині задовольняє наступній умові: #.

Введемо наступні позначення: #.

Враховуючи обмеження на значення f(x), маємо #, де # - верхня, а # - нижня межа для на просторі .

Нехай Г(V, E) орієнтований сильно зв'язний граф, що співвідноситься з задачею оптимізації наступним чином: вершина і в Г відповідає точці xi , а ребра з'єднують вершину i з точками, що входять до заданого околу O(xi, r). Позначимо ступінь та діаметр графа Г(V, E) як d та D відповідно.

В дослідженні використовувався наступний підхід до визначення збіжності алгоритму.

Означення 2.2 Алгоритм оптимізації збігається, якщо траєкторія, яку він будує в просторі розв'язків, включає глобальний оптимальний стан.

Теорема 2.1. G2-алгоритм збігається за кількість кроків, яка не перевищує величини # з імовірністю, не меншою ніж (1-2-k) при будь-якому початковому стані, де k - натуральне число.

Розглянемо простір перестановок #.

Означення 2.3. Відстанню # між двома довільними перестановками # називається мінімальна кількість транспозицій, що перетворюють перестановку a в b.

Наслідок 2.1. G2-алгоритм на просторі перестановок P з радіусом околу 1 збігається за кількість кроків, яка не перевищує величини з імовірністю, не меншою ніж (1-2-k), при будь-якому початковому стані, де k - натуральне число.

Результати проведених експериментальних досліджень ефективності G2-алгоритму у порівнянні з G-алгоритмом з розв'язання відомих ЗК та КЗП дозволяють стверджувати, що G2-алгоритм демонструє вищу ефективність ніж типовий представник класу алгоритмів прискореного ймовірнісного моделювання для більшості розглянутих задач.

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

Означення 3.1. d-відрізком між перестановками # та # називається впорядкована послідовність перестановок #, де #.

Означення 3.2. Променем, що виходить з довільної точки x, називається кожний такий d-відрізок /x, /, для якого не існує такої точки z, z, що /x, z/.

Виходячи з означення 3.2 можемо сказати, що - точка, максимально віддалена в просторі варіантів розв`язку від початкової точки х.

Твердження 3.1. Для того, щоб при перетворенні перестановки а в перестановку b, здійснити переміщення шляхом транспозиції всіх елементів, які належать одному циклу розмірності k, необхідно виконати щонайменше k-1 кроків.

Твердження 3.2. Процедура перетворення перестановки a в перестановку b шляхом транспозицій елементів перестановки a, при умові, що задача перетворення містить t циклів розмірності #, де #, містить щонайменше кроків, де n - кількість елементів в перестановці.

Для розробленого алгоритму побудови послідовності перестановок доведено, що справедлива наступна теорема.

Теорема 3.1. Запропонований алгоритм будує послідовність перестановок найменшої довжини, тобто будує d-відрізок між перестановками a та b.

На основі алгоритму побудови відрізків розроблено алгоритм побудови променів в просторі перестановок. Це дозволило провести дослідження практичної ефективності Н-методу при розв'язанні задач, що визначені на просторі перестановок.

Для запропонованої реалізації Н-методу, що передбачає використання G2-алгоритму в ролі вбудованої евристики, доведено наступну теорему.

Теорема 3.2. Н-алгоритм збігається з імовірністю #, де - імовірність збіжності G2-алгоритму, що використовується при побудові початкової популяції, - імовірність збіжності G2-алгоритму на ітерації і, що застосовується до нових точок, які додаються при побудові тимчасової популяції, h - кількість ітерацій алгоритму, m - кількість точок в популяції, k - кількість пар точок, що обираються для дослідження на кожній ітерації, l - кількість точок, що підлягають мутації на одній ітерації.

Для аналізу ефективності запропонованого алгоритму Н-методу використовувались як тестові задачі, так і прикладні задачі із відомих Інтернет-бібліотек QAPLIB та TSPLIB, в яких для кожної задачі наведений найкращий відомий на даний час розв'язок. При розв`язанні відомих КЗП розмірністю від 19 до 150 ефективність запропонованого алгоритму Н-методу порівнювалась з алгоритмами метода вектора спаду (МВС), ІВ, ГА, меметичним алгоритмом (МА), ГА з вбудованим G2-алгоритмом, мультистартовим G2-алгоритмом, стандартним комбінаторним методом деформованих многогранників та його реалізацією з вбудованим G2-алгоритмом. При розв'язанні тестових КЗП розмірністю від 20 до 100 Н-метод порівнювався з МВС, ІВ, G2-алгоритмом. Для всіх задач запропонований алгоритм Н-методу показав найвищу ефективність.

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

Важливу роль для Н-методу відіграє спосіб побудови променів # в комбінаторних просторах. При реалізації Н-методу необхідно розрізняти випадок, коли з множини допустимих d-відрізків #, завжди за деяким конкретним правилом/способом побудови обирається лише один d-відрізок, та випадок, коли можуть розглядатися всі можливі d-відрізки. Перший варіант призводить до порівняно швидкої збіжності алгоритму та потребує менше часу, другий варіант забезпечує більш якісний аналіз простору розв'язків, але відрізняється підвищеною трудомісткістю. Для розв'язання даної проблеми й використання переваг мультиагентних методів запропоновано будувати агентами декілька променів одночасно, використовуючи при цьому спеціальну модель задачі, та обирати найкращу точку для продовження пошуку з врахуванням всіх побудованих променів. В ролі агента в даному випадку виступає алгоритм покрокової побудови променів, який при виборі наступної точки з допустимої множини використовує певне ймовірнісне правило. Для простору перестановок запропонований наступний підхід. Ймовірність вибору для точки # чергової точки # такої, що #, де # - оператор транспозиції (або подібний до нього у випадку іншої метрики), за допомогою якого генеруються точки з околу #, розраховується на підставі евристичних проблемно-залежних значень, наприклад, з використанням значень цільової функції за формулою # , та ступеня «бажаності» оператора #, який розраховується на основі моделі задачі та з врахуванням накопиченого досвіду.

Для розрахунку ступеня «бажаності» оператора # транспозиції для перестановки # запропоновано два варіанти.

Варіант 1. Модель задачі подається у вигляді матриці # розмірності # (n - розмірність задачі), де елемент визначає «бажаність» слідування j після i (у варіанті розв'язку задачі). Тоді транспозиція компонентів # та # перестановки х визначає наступну величину ступеня «бажаності»

Варіант 2. Модель задачі подається у вигляді матриці # розмірності # (n - розмірність задачі), де елемент # визначає «бажаність» перебування елемента i на позиції j (в варіанті розв'язку задачі). Тоді транспозиція компонентів # та # перестановки x визначає наступну величину ступеня «бажаності»:

Обидва варіанти передбачають однакову процедуру оновлення значень матриці . Вона схожа з процедурою оновлення слідів феромону в циклічному алгоритмі оптимізації мурашиними колоніями (ОМК) і складається з двох етапів:

збільшення елементів матриці #, що певним чином асоціюються зі знайденим розв'язком, пропорційно цьому розв'язку;

застосування коефіцієнту, що зменшує значення, до всіх елементів матриці # (в термінах ОМК - випаровування феромону).

Запропоновано використовувати такі процедури оновлення матриці # на першому етап

Нехай та - задані вагові коефіцієнти # та #, а #, де # - точки з #, які належать променю. Тоді вибір оператора транспозиції #, застосування якого призводить до створення чергової точки з допустимої множини #, в процесі побудови променя визначається на підставі ймовірності #, для обрахування якої запропонований наступний вираз

На основі запропонованих процедур розроблений метаевристичний моделеорієнтований метод, що отримав назву мультиагентний Н-метод (МН-метод).

Для визначення ефективності порівняно з найкращими реалізаціями Н-методу проведено серію експериментів з розв'язання ЗК (розмірності від 33 до 100) та КЗП (розмірності від 19 до 100). Як і в попередніх дослідженнях, використано задачі з Інтернет-бібліотек QAPLIB та TSPLIB. Це дозволило не тільки отримати оцінки в порівнянні з Н-методом, але і оцінити власне точність МН-методу. Результати експериментів із розв'язання ЗК та КЗП підтвердили, що комбінування механізму сканування простору розв'язків та процедур навчання дозволило підвищити ефективність в порівнянні з Н-методом.

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

Розглянуто задачу розміщення в наступній постановці. Нехай є напівнескінченна стрічка, що складається зі скінченого числа смуг однакової ширини (рівнів). Ширина стрічки дорівнює Kh, де h - ширина одного рівня; K - кількість рівнів. На цій стрічці необхідно розмістити задані N прямокутників з однаковою шириною h та різною довжиною. При розміщенні повинні виконуватись наступні обмеження: кожен прямокутник повинен бути розташованим лише на одному рівні; сторона прямокутника, що дорівнює h, повинна бути паралельною до сторони стрічки скінченої довжини; прямокутники розміщуються без перетинів. На стрічці знаходиться скінченна кількість заборонених ділянок (в подальшому будемо називати їх дірками), на які не можуть накладатися прямокутники. Дірки задані у вигляді скінченного числа прямокутників, розташування яких зафіксовано, що задовольняють вимогам описаних вище правил розміщення.

Введемо наступні позначення: A={a1,…, aN} - множина прямокутників, що підлягають розміщенню; M - максимальна кількість дірок на одному рівні стрічки; хkj - відстань від початку стрічки до j-ї дірки, що знаходиться на k-му рівні; k=1,…,K, j=1,…, M; bkj - довжина j-ї дірки, що знаходиться на k-му рівні, k=1,…,K, j=1,…, M; i - довжина i-го прямокутника, i=1,…, N; zi - відстань від початку стрічки до початку i-го прямокутника, i=1,…, N; yi - номер рівня, на якому розташований i-й прямокутник, i=1,…,N. Нехай , .

Розв'язок поставленої задачі (розміщення) можна однозначно описати векторами Z=(zi) і Y=(yi), i=1,…,N. Якщо R(Z,Y) - деяке розміщення, а l-й прямокутник у ньому розташований останнім на k-му рівні, то величина Fk=zl+l дорівнює довжині k-го рівня, зайнятого прямокутниками. Завдання полягає в пошуку варіанта розміщення R*(Z,Y), при якому довжина зайнятої частини стрічки була б мінімальною:

Через специфіку обмежень (5) - (6) застосування традиційних методів нелінійного програмування для розв'язання задачі (2) - (7) найчастіше неможливо або нераціонально. Для даної задачі використовується математична модель у вигляді спеціальної ЗКО вигляду (1) на просторі перестановок: Pk={p=(p1,…,pN): ps{1…N}, pspt, st, s,t=1,.....,N}, де елементи перестановки p визначаються згідно рівності ps=i, i - номер прямокутника, s - місце i-го прямокутника в перестановці p, i,s=1,…,N, і задаються алгоритми, які забезпечують однозначну відповідність перестановок і розміщень. Тоді зазначена задача формулюється в просторі перестановок у такий спосіб: знайти таку перестановку p*PN, що #.

Оскільки сформульована ЗКО є NP-повною, то доцільною є розробка наближених алгоритмів.

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

Доведено, що справедлива наступна теорема.

Теорема 5.2. На класі всіх задач розміщення вказаного типу величина С, отримана за розробленим алгоритмом знаходження нижньої межі, є точною нижньою межею цільової функції.

Використовуючи отримане значення нижньої межі, перелік критеріїв завершення роботи ітераційних алгоритмів (таких, наприклад, як МВС, ІВ, G2-алгоритм) при розв`язанні задачі доповнено наступним критерієм: якщо на кроці h визначено варіант розв`язку ph, то обчислення припиняються в разі виконання умови #, де >0 - задане значення точності, а С - розраховане значення нижньої межі. При виконанні обчислювального експерименту реалізовано наступні алгоритми: МВС з повним перебором точок в околі; МВС з вибором до першого покращення з лінійним генератором; МВС з вибором до першого покращення і кільцевим генератором; ІВ; G2-алгоритм. Обчислювальний експеримент проводився в два етапи. На першому етапі розв'язувались наступні підкласи задач: розміщення без дірок; розміщення з малою кількістю дірок, які розташовані на початку смуг; розміщення з малою кількістю дірок, які розташовані всередині смуг; розміщення з дірками, які рівномірно розташовані вздовж смуг. Результати розв'язання відомих модельних задач розміщення із значеннями N від 12 до 200 дозволили отримати початкові оцінки ефективності та трудомісткості кожного алгоритму. Результати засвідчили, що G2-алгоритм дозволяє отримати достатньо точні результати (для задач з N до 150 відхилення від нижньої межі становило від 0 до 0,05%). Також виявлено необхідність порівняння ефективності алгоритмів з урахуванням обмеження на час роботи, оскільки на практиці в більшості випадків є необхідність отримання розв'язку в реальному часі. Другий етап передбачав розв'язанні серії задач (загальна кількість задач - 800) із значеннями N від 50 до 150 (для розмірностей до 100 розв`язувалось по 100 задач, для більших - по 50). Також розраховано довірчі інтервали та інші статистичні характеристики.

Обчислювальний експеримент показав, що найбільш ефективним є G2-алгоритм. Для задач великих розмірностей та обмеженні на час роботи кожного алгоритму в 1 с. ефективність G2-алгоритму і ІВ розрізнялися відносно мало (але в усіх задачах G2-алгоритм давав результат не гірше ІВ), при збільшенні часу роботи алгоритмів до 3 с. перевага G2-алгоритму зростала. Також потрібно відзначити, що для задач всіх розмірностей G2-алгоритм та ІВ знаходили більш точні розв`язки, ніж методи детермінованої локальної оптимізації

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

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

Введемо наступні позначення: n - кількість відношень, що підлягають з'єднанню; #, - множина відношень, що підлягають з'єднанню; # - результат з'єднання відношень R1 та R2; # - кількість атрибутів відношення #; ,- множина атрибутів відношень, що підлягають з'єднанню; # - атрибути відношення #; # - множина ребер графа з'єднання; # - відношення, які з'єднує ребро #; # - потужність (кількість кортежів) відношення ; # - коефіцієнт селективності для з'єднання #; # - розмір кортежу відношення (у байтах); bs - розмір блоку на диску (у байтах).

Виходячи із цих параметрів можемо показати, що вартість запису результату з'єднання відношень і дорівнює

При розрахунку вартості виконання з'єднання двох відношень враховано наступні механізми виконання з'єднання: з'єднання методом вкладених циклів (з врахування випадків відсутності індексів, наявності первинного індексу за атрибутами з'єднання, наявності вторинного індексу за атрибутами з'єднання, наявності хеш-індексу за атрибутами з'єднання), з'єднання із сортуванням (з врахуванням випадків, коли відношення відсортовані за атрибутом з'єднання, є вторинний ключ на атрибут з'єднання, відсутнє сортування за атрибутами з'єднання), з'єднання за хешем.

Для подання густих дерев використаний впорядкований перелік ребер графа з'єднання. В ролі простору розв'язків запропоновано використовувати простір перестановок #, де елементи перестановки x визначаються згідно рівності #, де i - номер ребра; w - місце i-го ребра в перестановці, #.

Для розрахунку значення цільової функції для графа запиту, що поданий у вигляді перестановки , запропоновано такий алгоритм.

Алгоритм розрахунку вартості виконання з'єднання

begin

#

for i:=1 to k do

Визначення і , для яких виконується: #;

#;

#;

if # then #;

for h:=1 to n do

if # then

#;

endif

endfor;

endfor;

end;

Тоді поставлена задача формулюється в заданому просторі таким чином: знайти таку перестановку #, що #.

Для розв`язання задачі вибору порядку з'єднання таблиць бази даних реалізовано чотири алгоритми: ГА, МА, Н-метод та МН-метод. Обчислювальний експеримент передбачав розв'язанні серії задач (загальна кількість задач - 210) із значеннями n від 15 до 45 (для всіх розмірностей розв`язувалось по 30 задач). Також розраховано довірчі інтервали та інші статистичні характеристики. Найкращі результати отримано за допомогою МН-методу. При цьому слід відзначити, що при збільшенні розмірності задачі час роботи цього алгоритму зростає швидше, ніж час роботи ГА та МА.

Розроблена математична модель та запропоновані алгоритми застосовано при проектуванні автоматизованої системи інформаційно-аналітичного забезпечення фінансової системи АІС «Держбюджет» та автоматизованої системи керування підприємством ІАСК «Ландгут-1».

ВИСНОВКИ

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

В ході проведених досліджень отримані наступні основні результати:

Розроблено нову обчислювальну схему алгоритмів методу прискореного ймовірнісного моделювання (G2-алгоритм). Побудовані на її основі алгоритми можуть використовуватись як автономно, так і у складі метаевристик для розв'язання широкого кола практичних ЗКО. Обчислювальна схема побудована на основі нового ймовірнісного механізму опрацювання точок з околу поточного розв'язку. Результати експериментальних досліджень засвідчили високу практичну ефективність розробленої схеми при розв'язанні ряду відомих ЗКО.

Розроблено новий ефективний гібридний метаевристичний алгоритм розв'язання ЗКО на перестановках, побудований на основі комбінаторного методу деформованих многогранників (Н-метод) та G2-алгоритму. Запропоновано та теоретично обґрунтовано алгоритми побудови метричних відрізків у просторі перестановок, що проходять через дві задані точки. Досліджено ефективність запропонованого методу при розв`язанні ряду відомих прикладних квадратичних задач про призначення та тестових задач у порівнянні з методами детермінованого та стохастичного локального пошуку, модифікаціями ГА та МА.

Отримані теоретичні оцінки швидкості збіжності до глобального оптимуму для G2-алгоритму та запропонованого алгоритму Н-методу.

Запропоновано нову схему методу локального пошуку зі змінними околами та на її основі побудовано гібридний алгоритм Н-методу. Проведено експериментальні дослідження запропонованого гібридного алгоритму Н-методу, які підтвердили його високу ефективність.

На основі мультиагентного підходу запропоновано новий метаевристичний моделеорієнтований алгоритм розв'язання ЗКО - МН-метод. Комбінування механізму сканування простору розв'язків та процедур навчання дозволило підвищити ефективність розв'язання ЗКО в порівнянні з Н-методом, що проілюстровано на прикладі ряду відомих задач комівояжера та квадратичних задач про призначення.

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

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

Розроблені математичні моделі та методи використано при розробці автоматизованої системи управління пасажирськими перевезеннями «Експрес-УЗМ», автоматизованої системи інформаційно-аналітичного забезпечення фінансової системи АІС «Держбюджет» та автоматизованої системи керування підприємством ІАСК «Ландгут-1».

СПИСОК ОПУБЛІКОВАНИХ ПРАЦЬ ЗА ТЕМОЮ ДИСЕРТАЦІЇ

Гуляницкий Л. Ф. О сравнении эффективности алгоритмов решения одного класса задач размещения прямоугольников на полубесконечной ленте /

Л. Ф. Гуляницкий, Д. А. Гобов //Компьютерная математика. - 2003. - № 1. -

С. 88-97.

Гуляницький Л. Ф. Застосування Н-методу для розв'язання задач комбінаторної оптимізації на перестановках / Л. Ф. Гуляницький, Д. А. Гобов // Системні дослідження та інформаційні технології. - 2007. - № 2. - С. 74-86.

Гобов Д. А. О сходимости модифицированного алгоритма ускоренного вероятностного моделирования / Д. А. Гобов // Кибернетика и системный анализ. - 2008. - № 1. - С. 173-179.

Гобов Д. А. Решение задачи выбора порядка соединений таблиц базы данных методами комбинаторной оптимизации / Д. А. Гобов // Управляющие системы и машины. - 2008. - № 3. - С. 85-91.

Гуляницький Л. Ф. Мультиагентный Н-метод в комбинаторной оптимизации / Л. Ф. Гуляницкий, Д. А. Гобов // Intelligent Support of Decision Making: Intern. Book Series «INFORMATION SCIENCE & COMPUTING», No. 10 / K. Markov, K. Ivanova, I. Mitov (Ed.). - Sofia: Institute of Information Theories and Applications FOI ITHEA, 2009. - P. 97-103.

Гуляницький Л. Ф. Про один гібридний алгоритм комбінаторної оптимізації /

Л. Ф. Гуляницький, Д. А. Гобов // Мат. VII Міжн. наук.-тех. конф. «Системний аналіз та інформаційні технології» (28 червня - 2 липня 2005 р., Київ). - К.: НТУУ «КПІ», 2005. - С. 26.

Гобов Д. А. Про збіжність одного методу стохастичної локальної оптимізації / Д. А. Гобов // Пр. Міжн. симп. «Питання оптимізації обчислень (ПОО-ХХХІІІ)», (23-28 вересня, 2007р., смт. Кацівелі, Крим,). - К.: Інститут кібернетики ім. В.М. Глушкова НАН України, 2007. - С. 77-78.

Гобов Д. А. Про збіжність модифікованого алгоритму прискореного імовірнісного моделювання (G-алгоритму) / Д. А. Гобов // Мат. ІХ Міжн. наук.-тех. конф. «Системний аналіз та інформаційні технології» (15-19 травня 2007 р., Київ). - К.: НТУУ «КПІ», 2007. - С. 39.

Гобов Д. А. Розв'язання однієї задачі проектування складних систем методами комбінаторної оптимізації / Д. А. Гобов // Мат. V Міжн. наук.-практ. конф. «Математичне та програмне забезпечення інтелектуальних систем» (14-16 листопада 2007 р., Дніпропетровськ). - Д.: ДНУ, 2007. - С. 39-40.

Гобов Д. А. О сходимости одного метаэвристического алгоритма комбинаторной оптимизации / Д. А. Гобов // Мат. Х Міжн. наук.-тех. конф. «Системний аналіз та інформаційні технології» (20-24 травня 2008 р., Київ). - К.: НТУУ «КПІ», 2008. - С. 67.

Гобов Д. А. Застосування методу локального пошуку зі змінними околами в метаевристичних алгоритмах / Д. А. Гобов // Мат. ХІ Міжн. наук.-тех. конф. «Системний аналіз та інформаційні технології» (26-30 травня 2009 р., Київ). - К.: ННК «ІПСА» НТУУ «КПІ», 2009. - С. 39.

Гобов Д. А. Про одну модифікацію Н-методу / Д. А. Гобов // Пр. Міжн. симпозіуму «Питання оптимізації обчислень (ПОО-ХХХV)», (24-29 вересня, 2009р., смт. Кацівелі, Крим,). - К.: Інститут кібернетики ім. В.М. Глушкова НАН України, 2009. - Т. 1. - С. 146-150.

АНОТАЦІЯ

Гобов Д.А. Математичні моделі та метаевристичні алгоритми розв'язання оптимізаційних задач в просторі перестановок. - Рукопис.

Дисертація на здобуття наукового ступеня кандидата технічних наук за спеціальністю 01.05.02 - математичне моделювання та чисельні методи. - Інститут кібернетики ім. В.М. Глушкова НАН України, Київ, 2010.

Робота присвячена розробці, обґрунтуванню та апробації нових математичних моделей і наближених методів розв`язання оптимізаційних задач, які визначені в просторі перестановок. Для розв`язання задач комбінаторної оптимізації (ЗКО) запропоновані нові алгоритми стохастичного локального пошуку - G2-алгоритм і VNSG-алгоритм, та метаевристичний Н-метод. Отримана теоретично обґрунтована оцінка швидкості збіжності до глобального оптимуму для G2-алгоритму та запропонованого алгоритму Н-методу. На основі мультиагентного підходу запропонований новий метаевристичний моделеорієнтований метод розв'язання ЗКО - МН-метод. Ефективність запропонованих алгоритмів підтверджена результатами обчислювального експерименту. Розглянуто математичну модель, розроблено алгоритм розрахунку точної нижньої межі цільової функції та ряд алгоритмів для розв'язання одного класу задач розміщення. Запропоновано математичну модель та розроблено алгоритми для розв'язання задачі вибору порядку з'єднання таблиць бази даних, що виникає на етапі передпроектного дослідження при побудові складних автоматизованих систем.

Ключові слова: комбінаторна оптимізація, перестановка, математична модель, наближений алгоритм, метаевристика, розміщення, вибір порядку з'єднання.

АННОТАЦИЯ

Гобов Д.А. Математические модели и метаэвристические алгоритмы решения оптимизационных задач в пространстве перестановок. - Рукопись.

Диссертация на соискание научной степени кандидата технических наук по специальности 01.05.02 - математическое моделирование и численные методы. - Институт кибернетики им. В.М. Глушкова НАН Украины, Киев, 2010.

Работа посвящена вопросам разработки, обоснования и апробации новых математических моделей и приближенных методов решения оптимизационных задач, сформулированных в пространстве перестановок. Для решения задач комбинаторной оптимизации (ЗКО) предложен новый вероятностный механизм поиска в окрестности текущего решения, на основании которого разработаны новая вычислительная схема алгоритмов ускоренного вероятностного моделирования (G2-алгоритм) и модифицированный алгоритм локального поиска с изменяющимися окрестностями (VNSG-алгоритм). На основе комбинаторного метода деформированных многогранников (Н-метод) и G2-алгоритма разработан новый метаэвристический алгоритм. Реализована схема Н-метода для решения ЗКО в пространстве перестановок на основе предложенных подходов к построению отрезков и лучей в данном пространстве. Для G2-алгоритма и Н-метода теоретически обоснованны оценки скорости сходимости к глобальному решению.

В роботе предложен новый метаэвристический моделеориентированный метод решения ЗКО - МН-метод, построенный с использованием мультиагентного подхода к исследованию пространства допустимых решений. В роли агента выступает алгоритм пошагового построения интервала и луча в пространстве решений. При работе агенты используют специальную модель решаемой задачи, что позволяет учитывать наряду с содержательной информацией о задаче и опыт, накопленный на предыдущих шагах алгоритма. Предложен ряд вариантов реализации механизмов, обеспечивающих самоорганизацию агентов при решении ЗКО в пространстве перестановок.

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

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

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

Разработанные математические модели и методы нашли применение при разработке ряда автоматизированных систем, таких как автоматизированная система управления пассажирскими перевозками на железнодорожном транспорте «Экспресс-УЗМ», автоматизированная система информационно-аналитического обеспечения финансовой системы АИС «Госбюджет» и автоматизированная система управления предприятием ИАСУ «Ландгут-1».

Ключевые слова: комбинаторная оптимизация, перестановка, математическая модель, приближенный алгоритм, метаэвристика, размещение, выбор порядка соединения.

ABSTRACT

Gobov D.A. Mathematical models and metaheuristics algorithms for solving optimization problem in permutation space. - Manuscript.

Thesis submitted for the candidate's degree in the field of technical science by specialty 01.05.02 - mathematical modelling and numerical methods. - V.M. Glushkov Institute of Cybernetics, National Academy of Science of Ukraine, Kyiv, 2010.

The thesis is dedicated to the problem of development, substantiation and approbation of the new mathematical models and approximation methods used to solve optimization problems in permutation space. To solve combinatorial optimization problems new algorithms of stochastic local search G2-algorithm and VNSG-algorithms, metaheuristic algorithm of Н-method are proposed. For G2-algorithm and new algorithm of H-method rate of convergence estimation is theoretically proved. Based on multi-agent approach new metaheuristic method solving combinatorial optimization problem - MH-method - is proposed. The computational experimental results are given and they show an efficiency of developed algorithms. The mathematical model is considered, algorithm for calculating low bound of goal function and a set of algorithms used to solve one class of allocation problem is developed. The mathematical model and a set of algorithms used to solve join order problems in a predesign research context at construction of the complex automated systems are proposed.

Key words: combinatorial optimization, permutation, mathematical model, approximation algorithm, metaheuristic, allocation, join order problem.

Размещено на Allbest.ru

...