Анотація до роботи:

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Публікації автора:

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

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

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

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

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. 88-89.

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. - С. 32-33.

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.