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

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

УДК 519.854

ГУЛЯНИЦЬКИЙ Леонід Федорович

РОЗРОБКА МОДЕЛЕЙ І НАБЛИЖЕНИХ МЕТОДІВ

КОМБІНАТОРНОЇ ОПТИМІЗАЦІЇ

ТА ЇХ ЗАСТОСУВАННЯ В ІНФОРМАЦІЙНИХ ТЕХНОЛОГІЯХ

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

Автореферат

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

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

Київ – 2005

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

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

Науковий консультант: | доктор фізико-математичних наук,

професор, академік НАН України

Сергієнко Іван Васильович,

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

Офіційні опоненти: | доктор фізико-математичних наук, професор Асельдеров Зайнутдін Макашаріпович,

НТУУ "Київський політехнічний інститут", професор,

доктор технічних наук, професор

Бейко Іван Васильович,

Інститут кібернетики Президентського університету МАУП, директор,

доктор технічних наук, професор,

член-кореспондент НАН України

Парасюк Іван Миколайович,

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

НАН України, завідувач відділу.

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

Захист відбудеться 25.11.2005 р. о 14 годині на засіданні

спеціалізованої вченої ради Д 26.194. 02 при Інституті кібернетики

ім. В.М.Глушкова НАН України за адресою:

03680 МСП Київ 187, проспект Академіка Глушкова, 40.

З дисертацією можна ознайомитися в науково-технічному архіві інституту.

Автореферат розісланий 20.10.2005 р.

Учений секретар

спеціалізованої вченої ради СИНЯВСЬКИЙ В.Ф.

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

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

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

Комбінаторним проблемам оптимізації та підтримки прийняття рішень присвячено багато робіт, серед яких у першу чергу варто зазначити монографії Х. Пападімітріу і К. Стайґліца; М. Ґері і Д. Джонсона; Д. Голланда; А.О. Корбута і Ю.Ю. Фінкельштейна; А. Кофмана і А. Анрі Лабордера; В.О. Ємелічева, М.М. Ковальова і М.К. Кравцова; М. Ґрьотчела, Л. Ловаша і А. Шрійвера; Ф. Ґловера і М. Лагуни; В. Кука, Г. Райфа; О.І. Ларічева; М. Доріґо, Г. Гооса і Т. Штютцля; Х. Сигала, а також роботи Ю.І. Журавльова, Е. Аартса, Р. Буркарда, Н. Крістофідеса, Я. Ленстри, П. Пардалоса та ін.

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

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

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

1) Р.Г.Е. 135.01 "Розробка і дослідження математичного забезпечення програмних комплексів, що допускають паралельну організацію обчислень і орієнтованих на розв'язання окремих класів задач прикладної математики на сучасних ЕОМ" (1985–1989 рр.);

2) С.Г.110.03 "Розробити програмні засоби оптимізації з урахуванням можливостей розпаралелювання обчислень" (1986–1990 рр.);

3) І.П.135.12 "Розробити методи і програмні засоби розв'язання окремих класів задач прикладної математики для різних типів сучасних ЕОМ" (1990 – 1994 рр.);

4) В.Ф.135.01 “Розробити та дослідити інтегровані наукомісткі програмно-алгоритмічні засоби розв’язування окремих класів задач прикладної математики на сучасних ЕОМ (1995–1998 рр., № держреєстрації 0109V027578);

5) М.Н.135.05 “Розробка інформаційної технології та програмних засобів підтримки прийняття рішень в умовах невизначеності та ризику на основі групових експертних оцінок” (1997–2000 рр., № держреєстрації 0197U005628);

6) І.П.135 09 “Розробити математичну теорію методи та програмні засоби розв’язування окремих класів задач прикладної математики” (1998 – 2001 рр., № держреєстрації 0198V005043);

7) ВФ.135.02 “Розробка та обґрунтування проблемно-орієнтованих методів та програмно-алгоритмічних засобів для розв’язування деяких класів задач прикладної математики на ПЕОМ” (1999 – 2002 рр., № держреєстрації 0199V001031).

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

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

розробка нових ефективних наближених алгоритмів пошуку в околах, призначених як для автономного використання, так і як вбудованих алгоритмів у гібридних (комбінованих) обчислювальних схемах КО;–

створення методології побудови гібридних алгоритмів КО з використанням існуючих та нових підходів;–

дослідження теоретичних та прикладних аспектів застосування запропонованих алгоритмів КО, зокрема, шляхом проведення обчислювальних експериментів із використанням як пропонованих алгоритмів, так і ряду відомих в літературі;–

обґрунтований вибір алгоритмів для розв`язання даної задачі оптимізації, настройка їх змінюваних параметрів;–

побудова й обґрунтування адекватності нових математичних моделей ряду оптимізаційних проблем розміщення об`єктів різної природи, управління матеріальними і фінансовими запасами і ресурсами;–

створення алгоритмів КО з розпаралелюванням обчислювального процесу, призначених для використання на сучасних багатопроцесорних обчислювальних комплексах;–

розробка й обґрунтування нового підходу до формалізації і розв`язання проблем оптимального вибору за наявності якісних критеріїв;–

розробка принципів побудови нових інформаційних технологій та оптимізації обчислювального процесу у програмно-алгоритмічних засобах, призначених для їх підтримки;–

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

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

У рамках цих досліджень отримані такі основні результати:

- запропонований новий підхід до використання стохастичних механізмів в алгоритмах КО, на його основі розроблені алгоритми прискореного імовірнісного моделювання (названі G-алгоритмами), які мають здатність до адаптації своїх параметрів у ході обчислювального процесу;

- на основі синтезу обчислювальних схем G-алгоритмів та ряду інших методів (оригінального методу деформованих многогранників, генетичних алгоритмів) розроблені нові гібридні алгоритми КО;

- проведені теоретичні дослідження та дослідження практичної ефективності запропонованих алгоритмів, які підтвердили можливість їх застосування для розв`язання широкого кола прикладних задач КО;

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

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

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

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

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

- на основі розробленої інформаційної технології, алгоритмічних та програмних засобів здійснена реалізація системи підтримки прийняття рішень (СППР) "Прогноз-ВВП". Її застосування дозволило отримати унікальний прогноз розвитку економіки України на шість років, точність якого перевищила всі відомі варіанти прогнозів на той же період, що були розроблені багатьма провідними вітчизняними і міжнародними дослідницькими організаціями та колективами.

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

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

Окремі аспекти розробок впроваджені в учбовий процес. Вони включені в спецкурси, які автор читає в Київському національному університеті імені Тараса Шевченка та НТУУ "Київський політехнічний інститут".

СППР “Альтернатива”, “Конкурс”, “Прогноз–ВВП” створені за замовленням і використовувалися в Фонді державного майна та Мінекономіки України. Вони демонструвались, зокрема, на Міжнародній виставці "Айдекс-95" (Абу-Дабі, ОАЕ, 1995) і на Виставках досягнень НАН України (Київ, 1996 та 2001). Розроблена система ВЕКТОР була впроваджена в ряді організації СРСР, демонструвалась на п`яти міжнародних та багатьох всесоюзних виставках.

Особистий внесок здобувача. Всі наукові результати дисертаційної роботи отримані особисто або за участі автора. У працях, виконаних у співавторстві, автором отримано наступні результати: в роботі [1] дисертант є автором розділу з паралельних наближених алгоритмів розв’язання комбінаторних задач оптимізації. У роботах, що написані у співавторстві, автору дисертації належать: [2] – визначення поняття метричних відрізків та розвиток теорії опуклості в дискретних просторах; [4, 21, 23, 24, 38, 40] – методологія формалізації і технологія розв`язання задач, принципи побудови і функціонування програмних систем оптимізації; [7, 12, 14, 32] – розробка комбінаторної моделі проблеми розміщення та імовірнісних методів розв`язання; [9, 15, 36] – паралельні алгоритми методу гілок і меж та їх дослідження; [18, 20, 25] – методологія використання експертних оцінок в задачах вибору; [22] – доведення теорем про збіжність; [26] – розробка математичної моделі агрегації групових експертних оцінок та її дослідження; [28, 31] – методологія використання "золотого перерізу" в G-алгоритмах; [33, 43] – розробка технології синтезу обчислювальних схем G-алгоритмів та генетичних алгоритмів; [41] – система моделей макроекономічного прогнозування.

Апробація результатів дисертації. Основні ідеї, принципи, положення і результати досліджень були подані на наукових семінарах, конференціях, нарадах, школах, серед яких: Республіканські семінари Наукової ради з проблеми Кібернетика НАН України (Київ, 1980–2002), Республіканський семінар по дискретній оптимізації (Ужгород, 28–30 травня 1985), I Всесоюзна конференція “Проблеми створення супер-ЕОМ, супер-систем та ефективність їх застосування” (Мінськ, 15–17 квітня 1987), Всесоюзний семінар “Питання оптимізації обчислень” (Алушта, 6–8 жовтня 1987), Міжнародна школа-семінар “Методи оптимізації та їх застосування” (Іркутськ, 10–19 вересня 1989), Міжнародний Симпозіум “INFO-89” (Мінськ, 10–14 жовтня 1989), Міжнародна конференція "Теорія програмування 90-х" (Київ, 5–8 вересня 1991), 4th International Symposium "Systems Analysis and Simulation" (Berlin, August 25–28, 1992), Україно-британські слухання "Проблеми прогнозування та розвитку технологій в Україні та Великобританії" в Комітеті Верховної Ради України з питань науки та народної освіти за участю представників Комітетів Палати Лордів та Палати Громад Парламенту Великобританії (Верховна Рада України/ Київ, 17 грудня 1998), Науково-практична конференція "Економіка України в 1998–2000 роках" (Київ, 2 квітня 1998), І Міжнародна науково-практична конференція з програмування УкрПРОГ'98 (Київ, 2–4 вересня 1998), І та ІІ Всеукраїнські конференції "Сучасні економіко-математичні методи у ринковій економіці" (Київ, 5–6 листопада 1998 та 27–28 квітня 2000), Міжнародний симпозіум "Питання оптимізації обчислень ПОО-XXVIII" (Київ, 29–30 вересня 1999), Всеукраїнська науково-практична конференція "Інформація, аналіз, прогноз – стратегічні важелі ефективного державного управління" (Київ, 23–24 травня 2000), VI Міжнародна конференція "Досвід проектування та застосування САПР в мікроелектроніці: CADSM 2001" (Львів-Славське, 12–17 лютого 2001), ІІ Міжнародна науково-практична конференція "Проблеми впровадження інформаційних технологій в економіці" (Ірпінь, 16–17 травня 2001), Міжнародна конференція з індуктивного моделювання (Львів 20–25 травня 2002), Міжнародна школа-семінар "Теорія прийняття рішень" (Ужгород, 7–12 жовтня 2002), VIIth International Conference "The Experience of Designing and Application of CAD Systems in Microelectronics CADMS 2003" (Lviv-Slavske, 18–22 February 2003), ІІ Міжнародна школа-семінар "Теорія прийняття рішень" (Ужгород, 27 вересня–2 жовтня 2004).

Публікації. Основні результати дисертації опубліковано в 44 наукових роботах, з яких одна монографія, 34 роботи – у наукових фахових виданнях (журналах та збірниках наукових праць), 9 робіт – у матеріалах наукових конференцій.

Структура та обсяг роботи. Дисертаційна робота складається із вступу, семи розділів, висновків, списку використаних джерел (376 найменувань) та додатку. Загальний обсяг роботи становить 321 сторінку, основний текст роботи викладено на 265 сторінках.

ЗМІСТ РОБОТИ

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

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

Другий розділ присвячений питанням розробки та аналізу алгоритмів прискореного ймовірнісного моделювання (G–алгоритмів), які успішно застосовуються як для безпосереднього розв`язання задач КО, так і як базові (вбудовані) процедури в гібридних алгоритмах, а також ефективних на практиці гібридних алгоритмів КО, основаних на використанні G–алгоритмів, генетичних алгоритмів (ГА) та методу деформованих многогранників. Задачі КО розглядаються в такій загальній постановці: знайти

, (1)

де X – комбінаторна чи інша скінченна (рідше – злічена) множина; Dр – її підмножина, що визначається обмежувальними умовами задачі; f: X?R1 – задана цільова функція задачі; ext{min, max}.

Для розв`язання задач вигляду (1) широко застосовуються алгоритми локального пошуку (зокрема, метод вектора спаду (МВС)), які починають обчислення із деякого початкового наближення та покроково намагаються замінити поточний розв`язок кращим варіантом із певного околу N(x). Знайдений варіант розв`язку є локально оптимальним розв`язком задачі (1) і може бути досить віддаленим від глобального оптимуму. З метою уникнення передчасної зупинки в алгоритмах локального пошуку на кожній ітерації можна допускати перехід в околі не лише до покращуючих варіантів розв`язку, але й дати можливість здійснювати інколи переходи до точок, в яких цільова функція має гірше значення, аніж в поточному варіанті (центрі околу) – такі алгоритми отримали назву алгоритми імітаційного відпалу (АІВ). Ймовірність переходу від поточної точки х до довільної y N(x) в них визначається так: p=exp(- Д / T), де ?=f(x) – f(y), а T, T 0, – спадний параметр алгоритму, який за аналогією із процесом відпалу називається температурою; зміною його значень і управляють ходом обчислень.

Результати застосування АІВ виявили досить суттєві затрати машинного часу на пошук розв`язків, а також значні коливання точності отриманих результатів в залежності від вибору як значень параметрів алгоритмів, що варіюються, так і абсолютних значень цільової функції. З метою зменшення часових затрат та підвищення стабільності результатів було запропоноване сімейство алгоритмів стохастичного локального пошуку, які отримали назву G-алгоритмів. Для побудови обчислювального процесу формується строго зростаюча послідовність дійсних чисел 0 = m0 < m1 < ... = 1, які відіграють роль дещо подібну ролі параметра Т в АІВ. Якщо Lr (xh) – метричний окіл точки xh радіусом ?, xh – поточний варіант на кроці h алгоритму, то варіант yО Lr (xh), для якого f(y)>f(xh), може бути прийнятий як xh+1 за умови, що розрахована ймовірність p(xh,y) перевищить поточне значення m, збільшене на певну випадкову величину.

Нехай параметр г, г>0,– дійсне число. Визначимо для всіх x,y X функцію (x,y)=1 + Д /(f(x)), а на підставі цього – ймовірність переходу від точки x до у:

Значення параметра г визначає інтервал довжиною г f(xh), при попаданні значень f(y) в який точка у ще може бути вибраною як xh+1. Відповідно, за більш значного погіршення (зростання – у випадку пошуку мінімуму) значень f(y) ця точка завжди вилучається з розгляду. Важливо зазначити, що цей інтервал автоматично зменшується при спаданні f(xh), що відбувається при наближенні до більш точних варіантів розв`язку задачі мінімізації, і збільшується у протилежному випадку. Тим самим здійснюється адаптація обчислювального процесу до динаміки зміни значень цільової функції задачі. Крім того, використання відносних величин дозволяє уникнути залежності від абсолютних значень цільової функції.

Розглянуті деякі можливі варіанти реалізації запропонованої схеми та досліджені умови збіжності G-алгоритмів. Нехай {xs} – послідовність варіантів розв`язку задачі КО, побудована згідно з G-алгоритмом. Назвемо варіант розв'язку x* X Lс-оптимальним, якщо для всякого y Lс(x*) виконується нерівність . Позначимо множину Lс-оптимальних розв'язків задачі.

Теорема 1. Нехай {xs} – послідовність, побудована згідно з G-алгоритмом. Тоді за імовірністю.

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

Розглянуті два способи поєднання переваг ГА та G-алгоритмів. У першому із цих гібридних алгоритмів, названому модифікованим ГА (МГА), в схемі еволюційних обчислень як оператор мутації була використана модифікація G-алгоритмів. В частинному випадку цей алгоритм охоплює відомий клас меметичних алгоритмів, які почали розвиватися останнім часом.

Використання G-алгоритмів в еволюційних обчисленнях як процедури підсилення масштабу мутації, яке було здійснене в МГА, дозволило підвищити ефективність пошуку варіантів розв'язку порівняно з автономним застосуванням G-алгоритмів та ГА. При цьому аналіз результатів використання такого підходу для розв`язання багатьох задач КО показав, що застосування в комбінованому методі G-алгоритму у повному обсязі на початкових етапах ГА можна уникнути, якщо основні його параметри, які визначають умови переходу до наступного кроку при локальному пошуку на кожній ітерації, змінювати узгоджено з динамікою змін параметрів ГА та поведінкою цільової функції.

В іншому алгоритмі, названому G-ГА, на відміну від поширених способів гібридизації комбінаторних алгоритмів, ГА виступає не як загальна схема (метаевристика), а як вбудований алгоритм. Алгоритм G-ГА дозволяє здійснювати автоматичну адаптацію своїх параметрів в ході обчислювального процесу: за рахунок послаблення на початковій стадії пошуку умов прийняття до розгляду варіантів розв`язку збільшується кількість точок простору Х, що можуть проглядатися за певний проміжок часу, та підвищується ймовірність потрапляння до "зони притягання" більш точного варіанту розв`язку.

Використовуючи певні аналогії з методом пошуку по деформованих многогранниках (методом Нелдера–Міда) для задач недиференційованої нелінійної оптимізації, в роботі запропоновано оригінальний алгоритм дискретної оптимізації, призначений для використання як на традиційних ЕОМ, так і багатопроцесорних обчислювальних комплексах (БОК), який названий методом деформованих многогранників (МДМ).

На основі поєднання ідей МДМ та G-алгоритмів запропонована схема нового гібридного алгоритму на основі алгоритму МДМ (ГМДМ). Як і повторюваний локальний пошук чи меметичні алгоритми, цей алгоритм оперує лише із локальними екстремумами. На відміну від більшості відомих операторів схрещування чи інших неструктурованих операторів рекомбінації, застосований в ньому спосіб породження нових точок, пов`язаний з оптимізацією вздовж так званих напівінтервалів, не дозволяє "злипатися" вершинам поточного многогранника, тому немає необхідності в диверсифікації результатів, яка пропонується в меметичних алгоритмах. Використання наведеної схеми може породжувати сімейство алгоритмів КО, зокрема, повторюваного локального пошуку чи звичайного МДМ.

У третьому розділі розглянуті питання формалізації ряду прикладних проблем у вигляді задач КО та розробки і дослідження наближених алгоритмів їх розв`язання. Згідно з усталеною практикою, для порівняльного аналізу різних алгоритмів КО використовуються типові моделі задач КО – задачі комівояжера (ЗК) та квадратичні задачі про призначення (КЗП), тому розділ починається з стислого огляду цих моделей. Вони використовуються тут для дослідження ефективності запропонованих G-алгоритмів в залежності від альтернативних варіантів реалізації ряду вузлових аспектів їх обчислювальних схем та порівняння з "класичними" АІВ. Подані результати розв`язання серії відомих та тестових ЗК та КЗП продемонстрували ефективність G-алгоритмів і дозволили виділити ті їх модифікації, які і були використанні у подальших застосуваннях.

Для автоматизації процесу настройки параметрів сформульована задача цілеспрямованого вибору значень змінюваних параметрів алгоритмів КО. На вхід подається множина {M1,…, Mk} задач оптимізації з даного класу B. Ці навчальні задачі можуть братися з бібліотек чи генеруватися випадковим чином, але структура їх даних повинна бути подібною до розв`язуваних задач. Припускається, що кожний алгоритм їх розв’язання має певні параметри, так що позначимо його А(z), де z=(z1,…, zm) – вектор параметрів алгоритму, m – кількість параметрів; позначимо W область допустимих значень параметрів. Нехай µ(M,A(z)) – показник ефективності розв’язання задачі М класу B за допомогою алгоритму А(z). Тоді задача полягає в пошуку такого вектора z*W, який мінімізує на виділеному наборі задач (навчальна вибірка) наступний функціонал:

, zW.

Для аналізу застосування гібридних алгоритмів використовувалися як випадково згенеровані задачі, так і задачі із відомих Інтернет-бібліотек. При розв`язанні відомих ЗК розмірністю від 17 до 101 порівнювались результати застосування стандартного і одного відомого комбінованого ГА та запропонованих алгоритмів G-ГА і МГА. Стандартний ГА жодного разу не показав найкращого результату, за винятком задачі найменшої розмірності (n=17), де результати всіх алгоритмів за точністю збіглися, і однієї задачі середньої розмірності (n = 45), в якій його результат був таким же, як і у G-ГА. У 82% найкращу точність мав алгоритм G-ГА, в 18% – МГА і лише одного разу – комбінований ГА. Для розв`язання більш трудомістких КЗП розмірністю від 19 до 50 був відібраний комбінований ГА і лідер попереднього експерименту – G-ГА та доданий алгоритм ГМДМ. Для задач невеликої розмірності (19–20) кращі результати продемонстрували генетичні алгоритми, але вже для n > 20 проявилася перевага ГМДМ, який частіше знаходив точний розв`язок. Із алгоритмів на базі генетичних більш точним був G-ГА, причому отримувана ним точність була вищою щодо результатів ГА більше, ніж в два рази. Використання процедури настройки параметрів дозволило ГМДМ досягти оптимальних значень практично в усіх задачах (за винятком однієї).

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

Досліджувався наступний клас задач розміщення. Нехай є напівнескінченна стрічка, що складається зі скінченного числа смуг однакової ширини (рівнів). Ширина стрічки дорівнює K h, де 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. Нехай , . Тоді математична модель задачі буде мати вигляд

xkj 0, bkj 0 , k=1,…, K , j=1,…, M; i=1,…, n; (2)

i > 0, zi 0 , yi {1,…,K}; (3)

для кожного i та всіх S{1,…, n}, таких, що yi=ys , zi < zs ,

zi + i zs ; (4)

для кожного i, i=1,…, n, існує одне і тільки одне l {0,1,…, M}, таке, що

Розв’язок цієї задачі можна однозначно описати векторами Z=(zi) і Y=(yi), i=1,…, n. Нехай R(Z,Y) – довільне розміщення. Задача полягає в пошуку варіанта розміщення R*(Z,Y), за якого довжина зайнятої частини стрічки була б мінімальною:

. (6)

Через специфіку обмежень (4), (5) застосування традиційних методів нелінійного програмування для розв’язання задачі (2) – (6) найчастіше неможливе або нераціональне. Тому задача зводиться до спеціальної задачі КО вигляду (1) на просторі перестановок Pn ={ p=(p1,…, pn): ps {1,…,n}, ps pt, s t, s,t=1,...,n}, де елементи перестановки p визначаються згідно з рівністю ps=i, i – номер прямокутника, а s – місце i-го прямокутника у перестановці p, i,s=1,…,n.

Для обґрунтування коректності переходу від задачі з неперервними змінними (1) – (4) до задачі КО були доведені такі твердження.

Теорема 2. Нехай задано довільне розміщення R*(Z,Y){R(Z,Y)}. Тоді знайдеться розміщення , таке, що .

Наслідок. При переході від нескінченної множини допустимих розв`язків {R(Z,Y)} до скінченної множини {R'(Z',Y')} оптимальний розв`язок задачі (2) – (6) не втрачається.

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

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

Використовуючи значення нижньої межі, критерії завершення ітераційних алгоритмів (таких, наприклад, як МВС, АІВ, G-алгоритми) при розв`язанні задачі було доповнене такою перевіркою: якщо на кроці h визначено варіант розв`язку ph, то обчислення припиняються в разі виконання умови , де ? > 0 – задане значення, а С – розраховане значення нижньої межі. Доповнюючи цією умовою той критерій завершення обчислень, який використовується в алгоритмах МВС, АІВ чи G-алгоритмах, перетворюємо їх в наближені алгоритми з оцінкою точності – саме в такій модифікації ці алгоритми були використані в обчислювальному експерименті, в якому реалізовані: МВС – з повним перебором точок в околі; МВС – з вибором до першого покращання з лінійним генератором; МВС з вибором до першого покращання і кільцевим генератором; АІВ; G-алгоритм. Було розв`язано 750 модельних задач розміщення із значеннями n від 50 до 150 (для розмірностей до 100 розв`язувалось по 100 задач, для більших – по 50), а також розраховані довірчі інтервали та інші статистичні характеристики.

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

Однією з важливих задач проектування та оптимізації телекомунікаційних мереж з технологією АТМ є задача оптимального вибору пропускних спроможностей каналів зв’язку. Задано структуру мережі, що складається з комутаторів, з’єднаних каналами зв’язку. Для кожного каналу зв’язку визначена його довжина. Задані також вимоги у передачі трафіка для кожної впорядкованої пари комутаторів. Крім того, для кожного каналу зв’язку задані величини загальних потоків. Пропускна спроможність будь-якого каналу зв’язку пропорційна пропускній спроможності базового каналу. Відомі також питомі вартості каналів зв’язку різної пропускної спроможності на одиницю довжини. Необхідно для всіх каналів зв’язку вибрати таку кількість базових каналів, за якої вартість функціонування мережі буде мінімальною при виконанні обмежень на показники якості обслуговування. В роботі розглянуті два види трафіка: CBR – передача з постійною швидкістю та передача зі змінною швидкістю (VBR і ABR).

Для проведення експериментальних досліджень запропонованих алгоритмів розв’язання задач оптимального вибору пропускних спроможностей каналів зв’язку був розроблений програмний комплекс, що дозволяє формувати тестові задачі з випадковими даними та реалізує алгоритми локального пошуку (МВС), повторюваного локального пошуку, АІВ, G-алгоритми і ГА. Сформований також контрольний набір з 80 задач різної розмірності, при цьому кожної розмірності було по 5 задач. Аналіз результатів експериментів показує, що для задач з трафіком CBR найменше покращання дає алгоритм локального пошуку, інші знаходять приблизно однакові розв’язки, при цьому кращим є G-алгоритм. Для задач з трафіками VBR та ABR найкращі розв’язки знаходять алгоритми повторюваного локального пошуку та G-алгоритм.

Розроблена математична модель оптимального завантаження складських приміщень обмеженої місткості різнотипною продукцією (товарами) за заданих характеристик вірогідності потреб в цій продукції. Нехай на складі, що має місткість V, необхідно розмістити n видів продукції. Відомі: ai – ємність (об’єм) одиниці продукції і-го виду; Иі – потреба в продукції і-го виду з відомим дискретним розподілом; сі – вартість розміщення на складі одиниці продукції і-го виду; di – збиток від того, що потреба в продукції і-го виду буде не задоволена на одиницю, i=1,…, n. Варіант завантаження складу опишемо вектором х=(х1,..., хn), де хі – обсяг продукції і-го виду. Необхідно мінімізувати витрати на зберігання продукції та потреби в середньому, які, припускаючи розподіл величин Иі заданим у вигляді l пар значень Иіk та відповідних імовірностей pik, можна оцінити так:

. (7)

Для розв`язання задач оптимального заповнення складу продукції з цільовою функцією (7) були реалізовані п`ять алгоритмів: алгоритми МВС з різними стратегіями – з повним перебором околу, до першого покращання з лінійним генератором та до першого покращання з кільцевим генератором; АІВ та G-алгоритми. В експерименті за допомогою датчика випадкових чисел генерувалось по 50 тестових задач із значенням розмірності, яке вибиралось в діапазоні від 10 до 100, так що всього було розв`язано 500 задач. Всі алгоритми використовувалися при двох значеннях радіусів околів (1 та 2). Для задач малої розмірності (n<30) найкращі за точністю результати отримані АІВ, тоді як для задач більшої розмірності як за точністю, так і за часом роботи суттєво кращими були результати G-алгоритму. Застосування процедури автоматичного вибору значень параметрів призвело до істотного покращення результатів (у середньому, близько 5%), отримуваних G-алгоритмом, при цьому час розв`язання суттєво зменшився.

Розроблена математична модель проблеми реального інвестування коштів в декілька проектів, в якій при максимізації отриманого прибутку слід враховувати ряд факторів, таких як віддача від вже реалізованих проектів, наявність директивного терміну та джерело інвестованих коштів. Задача полягає у пошуку такого впорядкування заданих n проектів, яке б максимізувало сукупний прибуток на момент завершення реалізації всієї послідовності проектів. Цю послідовність виконання проектів можна подати перестановкою p=(p1,…, pn) Pn , де pi – номер проекту, що реалізується на і-му етапі. Тоді задача полягає в пошуку такої перестановки p Pn , для якої

? max,

де на і-му етапі (i=1,…,n–1) Ui(p) – кошти наявні на початок реалізації етапу (проекту); Zi – прибутки від реалізації завершених проектів за попередній період; Wi-1 – обсяг залучених коштів на початок реалізації i-го проекту; Ei – виплати залучених коштів; Fi – обсяг штрафу за порушення директивного терміну останнім із завершених проектів. Отримані вирази для розрахунку кожного із зазначених факторів, більшість із яких мають рекурсивний характер.

Для розв`язання сформульованої задачі були програмно реалізовані два алгоритми: ГА та G-алгоритм. Дослідження поведінки цих алгоритмів здійснювалось при розв`язанні 30 задач розмірності від 5 до 30. Було виявлено, що за невеликої розмірності задач ГА часто знаходить кращі розв’язки, ніж G-алгоритм. При збільшенні розмірності задачі G-алгоритм починав давати кращі як за точністю, так і за часовими затратами результати (на максимальній розмірності – майже в 1.5 рази швидше), причому його переваги зростали з ростом розмірності задач.

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

Розглянуто моделі ієрархічних БОК, в яких передбачається: всі процесори розбиті на l рівнів, причому процесори 1-го рівня назвемо центральними процесорами (ЦП); комутаційна мережа забезпечує швидкі зв'язки між певною групою (кущем) процесорів (i+1)-го рівня, на які розбита множина всіх процесорів цього рівня, та одним із процесорів i-го рівня (i=1,..., l–1), який назвемо управляючим процесором (УП) даної групи (куща); всі процесори мають достатньо містку власну пам'ять і швидкий доступ до певних сегментів пам'яті свого УП.

Моделі ієрархічних БОК позначаються у вигляді впорядкованих l чисел (р1,..., рl ), де рi – число процесорів на рівні i, i = 1,..., l, а р1 =1. У разі, коли процесори кожного з рівнів i розбиті на групи (кущі) із рівним числом фi процесорів, модель такого регулярного БОК подаватиметься записом (1, р2 /ф2,..., рl /фl), причому вираз рk / рk, буде еквівалентний запису рk .

Найпоширенішими критеріями продуктивності БОК при розпаралелюванні методів розв'язання задач є запропоновані Куком коефіцієнт прискорення Kп і коефіцієнт ефективності Kе. Нехай Тp – час, необхідний для виконання алгоритму на БОК з р процесорами, Т1 – час роботи методу на однопроцесорній ЕОМ при розв'язанні деякого класу задач. Тоді

Kп =