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

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

МІНІСТЕРСТВО ОСВІТИ І НАУКИ УКРАЇНИ

ДНІПРОПЕТРОВСЬКИЙ НАЦІОНАЛЬНИЙ УНІВЕРСИТЕТ

СТЕПАНЧУК ТЕТЯНА ФЕДОРІВНА

УДК 519.8

АЛГОРИТМИ РОЗВ'ЯЗАННЯ ДЕЯКИХ КЛАСІВ

ОПТИМІЗАЦІЙНИХ ЗАДАЧ, ЯКІ ЗВОДЯТЬСЯ

ДО ЗАДАЧ ОПТИМАЛЬНОГО РОЗБИТТЯ

01.05.01 ? теоретичні основи інформатики та кібернетики

АВТОРЕФЕРАТ

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

кандидата фізико ? математичних наук

Дніпропетровськ - 2002р.

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

Робота виконана на кафедрі обчислювальної математики та математичної кібернетики Дніпропетровського національного університету Міністерства освіти і науки України

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

Кісельова Олена Михайлівна, Дніпропетровський національний університет Міністерства освіти і науки України, завідувач кафедри обчислювальної математики та математичної кібернетики.

Офіційні опоненти:доктор фізико - математичних наук, професор

Яковлев Сергій Всеволодович, Національний університет внутрішніх справ, начальник кафедри прикладної математики, заслужений діяч науки і техніки України (м. Харків);

кандидат фізико - математичних наук, доцент

Ус Світлана Альбертівна, Національний гірничий університет Міністерства освіти і науки України, кафедра системного аналізу і управління (м. Дніпропетровськ).

Провідна установа:

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

Захист відбудеться “30” вересня 2002 р. о 14 годині на засіданні спеціалізованої вченої ради К 08.051.09 при Дніпропетровському національному університеті за адресою: пр. Карла Маркса, 35, корп. 3, ауд. 25, м. Дніпропетровськ, 49044.

З дисертацією можна ознайомитись у науковій бібліотеці Дніпропетровського національного університету за адресою: вул. Козакова, 8, м. Дніпропетровськ, 49050.

Автореферат розісланий “30” серпня 2002 р.

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

спеціалізованої вченої ради К 08.051.09 В.А. Турчина

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

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

Великий клас практично важливих задач оптимізації та задач з інших розділів прикладних наук, що виникають у реальному житті, зводиться у математичній постановці до задачі оптимального розбиття. Розробці методів для розв'язання задач оптимального розбиття, що належать мало вивченому класу задач нескінченновимірного математичного програмування з булевими значеннями змінних, їх модифікаціям та узагальненням присвячені публікації Бейко І.В., Капустяна В.О., Кісельової О.М., Крохи Л.С., Кузнєцова К. А., Ус С.А., Шора Н.З. та інших, в яких показано можливість застосування методів оптимального розбиття множин до розв'язання нескінченновимірних однопродуктових і багатопродукто-вих транспортних задач і задач розміщення, задач зрошення, узагальненої задачі Неймана - Пірсона перевірки статистичних гіпотез, задач одержання діаграм Діріхле Вороного, задач територіального планування сфер обслуговування, задач стартового керування параболічними системами, задач розпізнавання образів, нечіткої класифікації і ін. Ця дисертаційна робота є продовженням досліджень щодо можливостей застосування методів оптимального розбиття множин до розв'язання задач глобальної оптимізації, побудови оптимальних квадратур та задач групового вибору, які досліджувалися у роботах Бабенко В.Ф., Батіщева Д.І., Гайсаряна С.С., Глінкіна І.А., Жілінскаса А.Г., Жиглявського А.А., Корнійчука Н.П., Курочки М.А., Міркіна Б.Г., Мулена Е., Нікольського С.М., Новікової Н.Г., Стронгіна Р.Г., Сухарева О.Г., Яковлева С.В. та інших.

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

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

Зв'язок роботи з науковими програмами, планами, темами. Дисертацію виконано на кафедрі ОМ та МК Дніпропетровського національного університету у рамках науково-дослідної роботи кафедри, індивідуального плану підготовки аспіранта та плану науково-дослідної роботи за держбюджетними темами № 07-57-97 “Математичне моделювання, розробка теоретичного апарату, обґрунтування і чисельна реалізація методів оптимізації складних систем” (номер держреєстрації 0197V000684) і № 07-174-00 “Розробка нових необхідних і достатніх умов оптимальності та елементів теорії двоїстості у банаховому просторі для розв'язання нескінченновимірних задач оптимального розбиття” (номер держреєстрації 0100V005244).

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

Поставлена мета визначає наступні задачі:

§ для задач глобальної оптимізації

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

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

- дослідження ефективності та виявлення властивостей розроблених алгоритмів;

- надання рекомендацій щодо вибору основних параметрів алгоритмів;

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

§ для задач побудови оптимальних квадратур

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

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

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

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

- аналіз отриманих результатів і надання рекомендацій щодо вибору параметрів алгоритмів;

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

§ для задач групового вибору

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

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

- розв'язання модельних задач і аналіз отриманих результатів.

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

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

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

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

Для задач глобальної оптимізації

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

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

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

Для задач побудови оптимальних квадратур

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

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

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

Для задач групового вибору

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

- розроблено метод розв'язання поставленої задачі.

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

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

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

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

Особистий внесок здобувача. Всі результати, які становлять суть дисертаційної роботи, отримані автором особисто. У працях, що написані у співавторстві з Кісельовою О.М., дисертанту належать зведення задач глобальної оптимізації та побудови оптимальних квадратур до задачі оптимального розбиття, розробка алгоритмів глобальної оптимізації функцій одно, двох, трьох змінних, дослідження ефективності та виявлення властивостей розроблених алгоритмів, надання рекомендацій щодо вибору основних параметрів алгоритмів; розробка алгоритмів наближеного пошуку оптимальних вузлів та оптимальних коефіцієнтів квадратурної формули; дослідження ефективності розроблених алгоритмів для побудови оптимальних квадратур. У роботі [5], що опублікована у співавторстві з Кісельовою О.М., Бойко Н.І., дисертанту належить постановка задачі групового вибору у термінах задачі оптимального розбиття, розробка алгоритму розв'язання поставленої задачі; [7] опублікована у співавторстві з Кісельовою О.М., Васильєвою Н.К. дисертанту належить дослідження ефективності запропонованого підходу.

Апробація результатів дисертації. Включені до дисертації результати досліджень доповідались та обговорювались на: The US-Ukrainian Workshop “Recent Advances in Non-Differentiable Optimization” (Kyiv, 2000), The 17^th International Symposium on Mathematical Programming (Atlanta, USA, 2000), Міждержавній науково-методичній конференції “Комп'ютерне моделювання” (Дніпродзержинськ, 2001), The European Operational Research Conference (Rotterdam, The Netherlands, 2001), The International Conference “Prediction and Decision Making under Uncertainties (Kyiv, 2001), The Second International Workshop “Recent Advances in Non-Differentiable Optimization” (Kyiv, 2001), The International Conference “Prediction and Decision Making under Uncertainties“ (Kyiv, 2002).

Публікації. Основні результати дисертації опубліковано в 11 наукових працях, з них 3 статті у виданнях, затверджених ВАК України, 6 - тез доповідей на наукових конференціях.

Обсяг та структура роботи. Дисертаційна робота складається із вступу, чотирьох розділів, висновків, списку використаних джерел, п'яти додатків. Повний обсяг дисертації становить 153 сторінки, серед яких 41 рисунок, 19 таблиць, список використаних джерел з 180 найменувань.

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

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

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

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

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

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

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

У підрозділі 2.1 обґрунтовано зведення задачі глобальної оптимізації до задачі оптимального розбиття множин.

У підрозділі 2.2 викладається метод оптимального розбиття множини з -вимірного евклідова простору на підмножини з пошуком координат центрів цих підмножин. Метод розв'язання задачі А засновано на зведенні вихід-ної задачі нескінченновимірної оптимізації до двоїстої скінченновимірної задачі з негладкою цільовою функцією, для розв'язання якої застосовується алгоритм узагальненого градієнтного спуску з розтяганням простору у напрямку різниці двох послідовних узагальнених градієнтів, - алгоритм Н.З. Шора.

Далі в підрозділі 2.3 пропонуються та обґрунтовуються алгоритми розв'язання задачі глобальної оптимізації (1), яка зведена до задачі А оптимального розбиття. Наведемо тут алгоритм для випадку .

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

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

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

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

де обмежена множина скінченої лебегової міри у - вимірному евклідовому просторі .

Функції належать класу вимірних на функцій, що задовольняють нерівност

де функції обмежені, визначені на , вимірні за аргументом при кожному фіксованому з та мають наступні властивості квазиметрики (є квазиметрикою)

Традиційно, будь-яка квадратурна формула виду

задається вектором коефіцієнтів та вузлів

де довільні дійсні числа, а точки з множини .

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

У підрозділі 3.2 обґрунтовано зведення задачі побудови оптимальних квадратур до задачі оптимального розбиття множини .

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

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

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

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

У підрозділі 4.2 побудовано алгоритм розв'язання поставленої задачі.

У підрозділі 4.3 наводиться розв'язання модельних задач та аналіз отриманих результатів при використанні запропонованого алгоритму.

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

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

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

алгоритм клас оптимізаційний розбиття підгрупа

ВИСНОВКИ

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

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

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

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

- для реалізації алгоритмів не обов'язково заздалегідь знати фактичну кількість локальних мінімумів (). Досить вибрати очікувану кількість локальних мінімумів , тому що в цьому випадку алгоритми все рівно знайдуть всі локальних мінімумів. Якщо усе-таки виявилося, що , то деякі локальні мінімуми можуть бути пропущені, Размещено на http://www.allbest.ru/

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

- алгоритми добре проявили себе на функціях з ефектом “плато”;

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

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

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

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

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

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

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

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

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

1. Степанчук Т.Ф. О виде штрафной функции в методе глобальной оптимизации, основанном на оптимальном разбиении множеств // Динамические системы. Симферополь: ТНУ. 2001. Вып. 17. С. 215 222.

2. Киселева Е.М., Степанчук Т.Ф. Поиск глобального минимума недифференцируемой функции с помощью метода оптимального разбиения множеств // Проблемы управления и информатики. 2002. №2. С. 45 60.

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

3. Киселева Е.М., Степанчук Т.Ф. О выборе оптимальных коэффициентов и оптимальных узлов квадратурных формул для функциональных классов, заданных квазиметриками // Проблемы управления и информатики. 2002. №3. С. 138 153.

4. Степанчук Т.Ф. Сведение задачи построения оптимальных квадратур к задаче оптимального разбиения множеств // Питання прикладної математики і математичного моделювання. - Дніпропетровськ: ДНУ. 2002. С. 166170.

5. Киселева Е.М., Бойко Н.И., Степанчук Т.Ф. Применение методов оптимального разбиения множеств к решению одного класса задач группового выбора // Питання прикладної математики і математичного моделювання. - Дніпропетровськ: ДНУ. 2001. С. 40 47.

6. Kiseleva E.M, Stepanchuk T.F. On construction of the optimal quadrature formulae by optimal set partitioning methods // Proc. Second International Workshop “Recent Advances in Non-Differentiable Optimization”. Kyiv (Ukraine). 2001. P. 21.

7. Киселева Е.М., Васильева Н.К., Степанчук Т.Ф. О принятии решений по размещению чебышевских центров, задающих оптимальное покрытие множества // Proc. International Conf. “Prediction and Decision Making under Uncertainties”. Kyiv (Ukraine). 2001. P. 8889.

8. Kiseleva E., Stepanchuk T. Application the optimal set partitioning method the global optimization problem of three variable function // Proc. the European Operational Research Conference. - Rotterdam (The Netherlands). 2001. - P. 143.

9. Степанчук Т.Ф. Об одном методе решения трехмерных задач глобальной оптимизации Праці Міждерж. науково-метод. конф. “Комп'ютерне моделювання”. Дніпродзержинськ: Дніпродзержинський державний технічний університет. 2001. С. 3233.

10. Kiseleva E., Stepanchuk T. The algorithm of global optimization based on partitioning the admissible domain at the local minima attraction spheres // Proc. 17^th International Symposium on Mathematical Programming. Atlanta (USA). 2000. P. 132.

11. Kiseleva E.M., Stepanchuk T.F. On efficiency of global nondifferentiable optimization algorithm based on the method of optimal set partitioning // Proc. US-Ukrainian Workshop “Recent Advances in Non-Differentiable Optimization”. Kyiv (Ukraine). 2000. P. 21.

АНОТАЦІЯ

Степанчук Т.Ф. Алгоритми розв'язання деяких класів оптимізаційних задач, які зводяться до задач оптимального розбиття. - Рукопис.

Дисертація на здобуття наукового ступеня кандидата фізико - математичних наук за спеціальністю 01.05.01 - теоретичні основи інформатики та кібернетики. - Дніпропетровський національний університет Міністерства освіти і науки України, Дніпропетровськ, 2002.

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

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

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

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

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

ANNOTATION

Stepanchuk T.F. The algorithms for solving the some classes of the optimization problems that reduced to the optimal set partitioning problems. Manuscript.

The dissertation for candidate degree in Physics and Mathematics by specialty 01.05.01 theoretical bases of computer science and cybernetics. Dniepropertrovsk national university of Ministry of Education of Ukraine, Dniepropetrovsk, 2002.

The dissertation is devoted to the solution the some classes of the optimization problems such as the global optimization problems, the problems of construction the optimal quadrature formulae, the problems of the group choice using the optimal set partitioning methods.

The reduction of the global optimization problem into the problem of optimal set partitioning is proved. The algorithms for solving the examined problem of the one-dimensional, two-dimensional, three-dimensional Euclidean space are worked out. To estimate the efficiency of the developed algorithms and to show its capabilities, the algorithms are evaluated on a set of well-known test functions. The recommendations for choosing the parameters of the algorithms are given. The application package for solving the global optimization problems is developed.

The opportunity of reduction the problem of construction the optimal quadrature formulae into the optimal set partitioning problem is grounded. The approximate algorithms for numerical search for the nodes and coefficients of the optimal quadrature formulae for different functional classes given by quasimetrics are proposed and proved. The efficiency of the proposed algorithm is explored. The application package for solving the posed problem is developed.

The new statement of the group choice problem in the optimal set partitioning terms is formulated. The algorithm for solving the examined problem is proposed. The efficiency of the proposed algorithm is investigated.

Keywords: global minimum, optimal set partitioning, non-differentiable optimiza-tion, the optimal quadrature formula, the group choice.

АННОТАЦИЯ

Степанчук Т.Ф. Алгоритмы решения некоторых классов оптимизационных задач, сводящихся к задачам оптимального разбиения. - Рукопись.

Диссертация на соискание ученой степени кандидата физико математических наук по специальности 01.05.01 - теоретические основы информатики и кибернетики. - Днепропетровский национальный университет Министерства образования и науки Украины, Днепропетровск, 2002.

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

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

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

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

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

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

Підписано до друку 24.07.02. Формат 60х90/16. Папір друкарський. Друк плоский. Гарнітура Times New Roman Cyr. Умов. друк. арк. 1. Тираж 100 прим. Замовлення № 1718. Друкарня ДНУ, 49050, м. Дніпропетровськ-50, вул. Козакова, 46.

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