ChSTU repository
ChSTU repository preserves and enables easy and open access to all types of digital content including text, images, moving images, mpegs and data sets
Learn More
Please use this identifier to cite or link to this item:
https://er.chdtu.edu.ua/handle/ChSTU/6187| Title: | Веб-орієнтований сервіс для розв’язування задач оптимізації чисельними методами |
| Authors: | Триус, Юрій Васильович Заєць, Володимир Михайлович |
| Keywords: | ЗАДАЧІ ОПТИМІЗАЦІЇ;ЧИСЕЛЬНІ МЕТОДИ ОПТИМІЗАЦІЇ;АЛГОРИТМИ ОПТИМІЗАЦІЇ;ВЕБ-ОРІЄНТОВАНИЙ СЕРВІС;КЛІЄНТ;СЕРВЕР;ANGULAR;REST API. |
| Issue Date: | 11-Jun-2024 |
| Abstract: | У сучасному світі швидкість та точність вирішення оптимізаційних задач визначають успіх багатьох проєктів та діяльність підприємств. Розвиток технологій та постійне поглиблення наукових досліджень у цій галузі створюють потребу у впровадженні ефективних інструментів для розв’язування оптимізаційних задач чисельними методами. Веб-орієнтований сервіс з розв’язування задач оптимізації чисельними методами стає невід’ємною частиною сучасного технологічного ландшафту, що сприяє підвищенню ефективності роботи та забезпечує зручний доступ до інструментів оптимізації для широкого кола користувачів. Метою роботи є створення веб-орієнтованого сервісу, який надасть можливість користувачам швидко та ефективно розв’язувати різні класи задач оптимізації чисельними методами та забезпечить доступ до потужних оптимізаційних інструментів через мережу Інтернет. Роботу було апробовано на: 1) Дев’ятій міжнародній конференції «Адаптивні технології управління навчанням». Одеса-Київ, 25–27 жовтня 2023 р.; 2) ІІ Міжнародній науково-практичній конференції «Інновації та перспективні шляхи розвитку інформаційних технологій» (06 груд. 2023 р., м. Черкаси); 3) Днях студентської науки ЧДТУ-2024, м. Черкаси, 23-24 квітня 2024 р., за результатами якої було отримано грамоту за ІІ місце по секції «Комп’ютерні науки та системний аналіз»; 4) VІІ Міжнародній науково-практичній конференції «Інформаційні технології в освіті, науці і техніці» (ІТОНТ-2024), (Черкаси, 23-24 травня 2024 р.). |
| URI: | https://er.chdtu.edu.ua/handle/ChSTU/6187 |
| Appears in Collections: | 122 Комп’ютерні науки (Комп’ютерні науки та прикладне програмування) |
Files in This Item:
| File | Description | Size | Format | |
|---|---|---|---|---|
| Пояснювальна записка_Заєць Володимир_КН-2001_2023-2024.pdf Restricted Access | 2.35 MB | Adobe PDF | View/Open Request a copy |
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.
Extracted text
МІНІСТЕРСТВО ОСВІТИ І НАУКИ УКРАЇНИ
ЧЕРКАСЬКИЙ ДЕРЖАВНИЙ ТЕХНОЛОГІЧНИЙ УНІВЕРСИТЕТ
Факультет інформаційних технологій і систем
Кафедра комп’ютерних наук та системного аналізу
Пояснювальна записка
до кваліфікаційної роботи
бакалавра
(освітньо-кваліфікаційний рівень)
на тему: «Веб-орієнтований сервіс для розв’язування задач оптимізації
чисельними методами»
Виконав: студент 4 курсу, групи КН-2001
спеціальності 122 «Комп’ютерні науки»
(шифр і назва спеціальності)
Освітня програма «Комп’ютерні науки та
(назва освітньої програми)
прикладне програмування»
Заєць Володимир Михайлович
Керівник Триус Ю.В.
(прізвище та ініціали)
Рецензент Красношлик Н.О.
(прізвище та ініціали)
Черкаси 2024 року
Черкаський державний технологічний університет
Факультет Інформаційних технологій і систем
Кафедра Комп’ютерних наук та системного аналізу
Освітньо-кваліфікаційний рівень Бакалавр
Спеціальність 122 – комп’ютерні науки
Освітня програма Комп’ютерні науки та прикладне програмування
ЗАТВЕРДЖУЮ
Завідувач кафедри КНСА
_______________ Юрій ТРИУС
«____» _____________ 20__ р.
ЗАВДАННЯ
на кваліфікаційну роботу бакалавра студенту
Зайцю Володимиру Михайловичу
(прізвище, ім‘я, по батькові)
1. Тема роботи Веб-орієнтований сервіс для розв’язування задач оптимізації
чисельними методами
Керівник роботи
(прізвище, ім’я, по батькові, науковий ступінь, вчене звання)
затверджені наказом університету від «26» лютого 2024 р. №60/04.
2. Строк подання студентом роботи «10» червня 2024 року
3. Вихідні дані до роботи:
3.1. Звіти з лабораторних робіт з дисципліни «Методи оптимізації та дослідження операцій».
3.2. Розрахунково-графічна робота з дисципліни «Методи оптимізації та дослідження операцій».
4. Зміст пояснювальної записки (перелік питань, що їх належить розробити):
Вступ
4.1. ОГЛЯД ДОСЛІДЖЕНЬ У ГАЛУЗІ МЕТОДІВ ОПТИМІЗАЦІЇ
4.2. ХАРАКТЕРИСТИКА ЧИСЕЛЬНИХ МЕТОДІВ ОПТИМІЗАЦІЇ
4.3. ПРОЄКТУВАННЯ ВЕБ-ОРІЄНТОВАНОГО СЕРВІСУ
4.4. РОЗРОБКА ВЕБ-ОРІЄНТОВАНОГО СЕРВІСУ ДЛЯ РОЗВ’ЯЗУВАННЯ ЗАДАЧ
ОПТИМІЗАЦІЇ
Висновки.
5. Перелік додатків (з точним зазначенням назв додатків):
5.1. Додаток А. Специфікація
1 . Інструкція користувача
5.2. Додаток Б. Тестові функції для методів оптимізації
5.3. Додаток В. Текст програми
5.4. Додаток Г. Інструкція користувача
5.5. Додаток Д. Публікації з теми кваліфікаційної роботи бакалавра
6. Консультанти розділів роботи
Прізвище, ініціали та Підпис, дата
Розділ посада
завдання видав завдання прийняв
консультанта
7. Дата видачі завдання 15.01.2024 р.
КАЛЕНДАРНИЙ ПЛАН
Строк виконання
№ з/п Назва етапів кваліфікаційної роботи бакалавра Примітка
етапів роботи
1 Видача завдання на кваліфікаційну роботу
до 15.01.2024
бакалавра.
2 Аналіз літературних джерел, об’єкту та предмету
до 31.01.2024
дослідження.
3 Написання теоретичного розділу кваліфікаційної
до 28.02.2024
роботи бакалавра.
4 Написання аналітичного розділу (аналіз об’єкту
до 31.03. 2024
й предмету дослідження).
5 Написання практичних розділів й висновків по
до 20.05.2024
роботі.
6 Передзахист кваліфікаційної роботи бакалавра
до 21.05.2024
на засіданні випускової кафедри.
7 Подання роботи завідувачу кафедри. до 10.06. 2024
8 Захист кваліфікаційної роботи бакалавра. 11.06.2024
Студент _____________________________ /____Заєць В.М.____/
(підпис) ПІБ
Керівник роботи ____________________________ /____Триус Ю.В.____/
(підпис) ПІБ
РЕФЕРАТ
Кваліфікаційна робота бакалавра містить: 82 с. основного тексту, 18 рис., 38
використаних джерел, 5 додатків.
Актуальність теми. У сучасному світі швидкість та точність вирішення
оптимізаційних задач визначають успіх багатьох проєктів та діяльність підприємств.
Розвиток технологій та постійне поглиблення наукових досліджень у цій галузі
створюють потребу у впровадженні ефективних інструментів для розв’язування
оптимізаційних задач чисельними методами. Веб-орієнтований сервіс з розв’язування
задач оптимізації чисельними методами стає невід’ємною частиною сучасного
технологічного ландшафту, що сприяє підвищенню ефективності роботи та забезпечує
зручний доступ до інструментів оптимізації для широкого кола користувачів.
Метою роботи є створення веб-орієнтованого сервісу, який надасть можливість
користувачам швидко та ефективно розв’язувати різні класи задач оптимізації
чисельними методами та забезпечить доступ до потужних оптимізаційних
інструментів через мережу Інтернет.
Завдання кваліфікаційної роботи бакалавра:
проаналізувати існуючі веб-орієнтовані сервіси для розв'язання задач
оптимізації;
розглянути теоретичні основи чисельних методів, що використовуються для
розв'язання задач оптимізації;
визначити вимоги до веб-орієнтованого сервісу та розробити його
архітектуру;
спроєктувати та реалізувати веб-орієнтований сервіс для розв'язання задач
оптимізації чисельними методами;
провести тестування та оцінку ефективності розробленого сервісу на
прикладі реальних задач.
Об’єкт дослідження: процес розв’язування задач оптимізації чисельними
методами за допомогою веб-орієнтованого сервісу.
Предмет дослідження: веб-орієнтований сервіс для розв’язування задач
оптимізації чисельними методами.
Методи дослідження: аналіз науково-технічної літератури з питань розробки та
впровадження веб-орієнтованих сервісів та чисельних методів оптимізації; відомі
чисельні методи розв'язання задач оптимізації; методологія проєктування веб-додатків,
включаючи архітектурні підходи та технології реалізації; методи тестування та оцінки
ефективності програмного забезпечення.
Апробація результатів роботи. Роботу було апробовано на:
1) Дев’ятій міжнародній конференції «Адаптивні технології управління
навчанням». Одеса-Київ, 25–27 жовтня 2023 р.;
2) ІІ Міжнародній науково-практичній конференції «Інновації та перспективні
шляхи розвитку інформаційних технологій» (06 груд. 2023 р., м. Черкаси);
3) Днях студентської науки ЧДТУ-2024, м. Черкаси, 23-24 квітня 2024 р., за
результатами якої було отримано грамоту за ІІ місце по секції «Комп’ютерні науки та
системний аналіз»;
4) VІІ Міжнародній науково-практичній конференції «Інформаційні технології
в освіті, науці і техніці» (ІТОНТ-2024), (Черкаси, 23-24 травня 2024 р.).
Публікації. Результати кваліфікаційної роботи бакалавра опубліковано у:
1) збірнику матеріалів дев’ятої міжнародної конференції «Адаптивні технології
управління навчанням»: Триус Ю.В., Заєць В.М., Шабельник Я.А. «Адаптивні
процедури у методах колективного інтелекту розв’язування задач глобальної
оптимізації»: Збірник матеріалів дев’ятої міжнародної конференції «Адаптивні
технології управління навчанням». Одеса-Київ, 25–27 жовтня 2023 р. Київ: ІЦО
НАПН України, 2023. 92 с. С. 8-10;
2) збірнику тез доповідей ІІ Міжнародної науково-практичної конференції
«Інновації та перспективні шляхи розвитку інформаційних технологій»: Заєць В.М.,
Триус Ю.В. Веб-орієнтований сервіс для розв’язування задач оптимізації чисельними
методами. Збірник тез доповідей ІІ Міжнародної науково-практичної конференції
«Інновації та перспективні шляхи розвитку інформаційних технологій»: (06 груд.
2023 р., м. Черкаси) [Електронний ресурс] / упоряд. : Т. О. Прокопенко, Я. В.
Тарасенко ; М-во освіти і науки України, Черкас. держ. технол. ун-т. Черкаси : ЧДТУ,
2023. 277 с. С. 113-114;
3) збірнику тез доповідей студентської науково-практичної конференції ЧДТУ:
Заєць В.М., Триус Ю.В. Розробка веб-орієнтованого ресурсу для розв’язання
оптимізаційних задач. [Електронний ресурс]: Збірник тез доповідей студентської
науково-практичної конференції ЧДТУ: 23–24 квітня 2024 / [упорядник Мельник
І.В.]; Міністерство освіти і науки України, Черкаський державний технологічний ун-
т. Черкаси: ЧДТУ, 2024. С. 87;
4) збірнику тез доповідей VІІ Міжнародної науково-практичної конференції
«Інформаційні технології в освіті, науці і техніці» (ІТОНТ-2024): Федоренко В.С.,
Триус Ю.В., Заєць В.М. Адаптивні процедури методу PSO та їх програмна реалізація.
Тези доповідей VІІ Міжнародної науково-практичної конференції «Інформаційні
технології в освіті, науці і техніці» (ІТОНТ-2024), (Черкаси, 23-24 травня 2024 р.)
[Електронний ресурс]. Черкаси : ЧДТУ, 2024. 350 с. С. 151-154.
Ключові слова: ЗАДАЧІ ОПТИМІЗАЦІЇ, ЧИСЕЛЬНІ МЕТОДИ ОПТИМІЗАЦІЇ,
АЛГОРИТМИ ОПТИМІЗАЦІЇ, ВЕБ-ОРІЄНТОВАНИЙ СЕРВІС, КЛІЄНТ, СЕРВЕР,
PYTHON, FASTAPI, JAVA, SPRING, SQL, POSTGRESQL, TYPESCRIPT, HTML, CSS,
ANGULAR, NGRX, REST API.
ABSTRACT
The qualification work of bachelor contains: 82 pages of the main text, 18 figures,
38 sources used, 5 attachments.
Actuality of theme. In the modern world, the speed and accuracy of solving
optimization tasks determine the success of many projects and business activities. The
continuous development of technologies and deepening scientific research in this field create a
need for the implementation of effective tools for solving optimization problems using
numerical methods. A web-oriented service for solving optimization problems using numerical
methods has become an integral part of the modern technological landscape, contributing to
increased work efficiency and providing convenient access to optimization tools for a wide
range of users.
The purpose of the work is to create a web-oriented service that will allow users to
quickly and efficiently solve various classes of optimization problems using numerical
methods and provide access to powerful optimization tools over the internet.
Objectives of qualifying work:
analyse existing web-oriented services for solving optimization problems;
examine the theoretical foundations of numerical methods used for solving
optimization problems;
determine the requirements for the web-oriented service and develop its
architecture;
design and implement a web-oriented service for solving optimization problems
using numerical methods;
conduct testing and evaluate the effectiveness of the developed service using real-
world examples.
The object of research: the process of solving optimization problems using
numerical methods through a web-oriented service.
The subject of research: the web-oriented service for solving optimization problems
using numerical methods.
Research methods: analysis of scientific and technical literature on the development
and implementation of web-oriented services and numerical optimization methods; known
numerical methods for solving optimization problems; methodology of designing web
applications, including architectural approaches and implementation technologies; methods of
testing and evaluating the effectiveness of software.
Approval of the results of work. The work was approved on:
1) The Ninth International Conference "Adaptive Learning Management
Technologies." Odessa-Kyiv, October 25-27, 2023;
2) The Second International Scientific and Practical Conference "Innovations and
Prospects for the Development of Information Technologies" (December 6, 2023,
Cherkasy);
3) The Days of Student Science at ChSTU-2024, Cherkasy, April 23-24, 2024, where
it received a certificate for 2nd place in the section "Computer Science and Systems
Analysis";
4) The Seventh International Scientific and Practical Conference "Information
Technology for Education, Science, and Technics" (ITEST-2024), (Cherkasy, May 23-24,
2024).
Publications. The results of the qualification work of the bachelor are published in:
1) collection of materials of the Ninth International Conference "Adaptive Learning
Management Technologies": Tryus Yu.V., Zaiets V.M., Shabelnyk Ya.A. "Adaptive
Procedures in Collective Intelligence Methods for Solving Global Optimization Problems":
Collection of materials of the Ninth International Conference "Adaptive Learning
Management Technologies." Odessa-Kyiv, October 25-27, 2023. Kyiv: ICT of the NAPS
of Ukraine, 2023. 92 p. P. 8-10;
2) collection of abstracts of the Second International Scientific and Practical
Conference "Innovations and Prospects for the Development of Information Technologies":
Zaiets V.M., Tryus Yu.V. Web-oriented service for solving optimization problems using
numerical methods. Collection of abstracts of the Second International Scientific and
Practical Conference "Innovations and Prospects for the Development of Information
Technologies" (December 6, 2023, Cherkasy) [Electronic resource] / compiled by T.O.
Prokopenko, Ya.V. Tarasenko; Ministry of Education and Science of Ukraine, Cherkasy
State Technological University. Cherkasy: ChSTU, 2023. 277 p. P. 113-114;
3) collection of abstracts of the student scientific and practical conference of ChSTU:
Zaiets V.M., Tryus Yu.V. Development of a web-oriented resource for solving optimization
problems. [Electronic resource]: Collection of abstracts of the student scientific and
practical conference of ChSTU: April 23-24, 2024 / [compiled by Melnyk I.V.]; Ministry of
Education and Science of Ukraine, Cherkasy State Technological University. Cherkasy:
ChSTU, 2024. P. 87;
4) collection of abstracts of the Seventh International Scientific and Practical
Conference "Information Technologies in Education, Science, and Technology" (ITONT-
2024): Fedorenko V.S., Tryus Yu.V., Zaiets V.M. Adaptive Procedures of the PSO Method
and Their Software Implementation. Abstracts of the Seventh International Scientific and
Practical Conference "Information Technology for Education, Science, and Technics"
(ITEST-2024), (Cherkasy, May 23-24, 2024) [Electronic resource]. Cherkasy: ChSTU,
2024. 350 p. P. 151-154.
Keywords: OPTIMIZATION TASKS, NUMERICAL OPTIMIZATION METHODS,
OPTIMIZATION ALGORITHMS, WEB-ORIENTED SERVICE, CLIENT, SERVER,
PYTHON, FASTAPI, JAVA, SPRING, SQL, POSTGRESQL, TYPESCRIPT, HTML, CSS,
ANGULAR, NGRX, REST API.
9
ЗМІСТ
ВСТУП ······························································································· 12
1 ОГЛЯД ДОСЛІДЖЕНЬ У ГАЛУЗІ МЕТОДІВ ОПТИМІЗАЦІЇ ······················· 15
1.1 Характеристика обраного напряму дослідження ··································· 15
1.2 Постановка проблеми ···································································· 18
1.3 Аналіз деяких сервісів розв’язання задач оптимізації ····························· 20
1.3.1 MATLAB Optimization Toolbox ·················································· 20
1.3.2 GNU Octave ··········································································· 22
1.3.3 Google OR-Tools ····································································· 23
1.3.4 Microsoft Azure Machine Learning ················································ 25
1.3.5 Wolfram Alpha ······································································· 27
1.3.6 Спеціалізовані бібліотеки та пакети програмного забезпечення ·········· 28
1.4 Результати аналізу обраного напряму дослідження ······························· 30
Висновки до розділу 1 ·········································································· 31
2 ХАРАКТЕРИСТИКА ЧИСЕЛЬНИХ МЕТОДІВ ОПТИМІЗАЦІЇ ····················· 32
2.1 Загальна характеристика ітераційних методів оптимізації ······················· 32
2.1.1 Основні принципи та підходи до ітераційних методів оптимізації ······· 33
2.1.2 Переваги та недоліки використання ітераційних методів ·················· 34
2.1.3 Класифікація ітераційних методів оптимізації ································ 35
2.2 Методи одновимірної оптимізації ····················································· 37
2.2.1 Метод дихотомії ····································································· 37
2.2.2 Метод золотого перерізу ·························································· 38
2.2.3 Метод Фібоначчі ···································································· 38
2.2.4 Метод парабол ······································································· 39
2.3 Методи безумовної оптимізації ························································ 39
2.3.1 Метод найшвидшого спуску ······················································ 40
2.3.2 Яристий метод ······································································· 42
2.3.3 Метод спряжених градієнтів ······················································ 42
2.3.4 Узагальнений метод Ньютона ···················································· 42
2.3.5 Квазіньютонівські методи ························································· 43
10
2.3.6 Симплексний метод Нелдера-Міда ·············································· 43
2.4 Методи умовної оптимізації ···························································· 44
2.4.1 Метод проекції градієнта ·························································· 44
2.4.2 Метод умовного градієнта ························································ 45
2.4.3 Метод штрафних функцій ························································· 45
2.5 Методи глобальної оптимізації ························································· 46
2.5.1 Метод рою частинок ································································ 46
2.5.2 Метод кажанів ······································································· 47
2.5.3 Метод гравітаційного пошуку ···················································· 47
2.5.4 Метод зграї сірих вовків ··························································· 48
2.6 Тестові функції для методів оптимізації ············································· 48
Висновки до розділу 2 ·········································································· 49
3 ПРОЄКТУВАННЯ ВЕБ-ОРІЄНТОВАНОГО СЕРВІСУ ································ 51
3.1 Вимоги до веб-орієнтованого сервісу ················································· 51
3.1.1 Функціональні вимог до веб-орієнтованого сервісу ························· 51
3.1.2 Вимоги до ефективності та швидкодії ·········································· 52
3.2 Структура веб-орієнтованого сервісу ················································· 53
3.2.1 Моделі даних та їх взаємозв'язки ················································ 53
3.2.2 Реалізація системи безпеки ······················································· 55
3.2.3 Робота з даними ····································································· 55
3.3 Засоби розробки ··········································································· 56
3.3.1 Вибір мов програмування та фреймворків ····································· 56
3.3.2 Використання сторонніх бібліотек та інструментів ·························· 58
3.3.3 Засоби для тестування та валідації ·············································· 59
3.4 Синтаксичний аналізатор формул ····················································· 60
3.4.1 Функціональні можливості аналізатора ········································ 60
3.4.2 Алгоритм обробки та інтерпретації формул ··································· 61
3.4.3 Методи валідації та перевірки формул ········································· 62
Висновки до розділу 3 ·········································································· 62
11
4 РОЗРОБКА ВЕБ-ОРІЄНТОВАНОГО СЕРВІСУ ДЛЯ РОЗВ’ЯЗУВАННЯ ЗАДАЧ
ОПТИМІЗАЦІЇ ··················································································· 64
4.1 Серверна частина веб-орієнтованого сервісу для розв’язування задач
оптимізації ·················································································· 64
4.1.1 Система безпеки та обробки запитів ············································ 65
4.1.2 Обчислювач ·········································································· 68
4.2 Клієнтська частина веб-орієнтованого сервісу для розв’язування задач
оптимізації ·················································································· 71
Висновки до розділу 4 ·········································································· 77
ВИСНОВКИ ························································································· 79
СПИСОК ВИКОРИСТАНИХ ДЖЕРЕЛ ······················································· 80
Додаток А Специфікація ·········································································· 83
Додаток Б Тестові функції для методів оптимізації ········································· 85
Додаток В Текст програми ······································································· 89
Додаток Г Інструкція користувача ······························································ 99
Додаток Д Публікації з теми кваліфікаційної роботи бакалавра ······················· 102
12
ВСТУП
Актуальність теми. У сучасному світі, де швидкість і ефективність процесів є
критичними факторами успіху, чисельні методи оптимізації набувають особливого
значення. Умови жорсткої конкуренції вимагають від компаній та організацій
постійного вдосконалення своїх операцій і зменшення витрат. Чисельні методи
оптимізації дозволяють знаходити оптимальні рішення для широкого спектра задач,
що допомагає досягати високих результатів у короткі терміни.
Використання чисельних методів оптимізації є критично важливим у багатьох
галузях, включаючи логістику, економіку, машинобудування, енергетику, управління
ресурсами та інші. Наприклад, у логістиці оптимізація маршрутів доставки може
значно знизити витрати на транспорт і підвищити ефективність використання
транспортних засобів, а в енергетиці оптимізація розподілу ресурсів дозволяє
зменшити витрати на виробництво і передачу енергії.
Одним з важливих аспектів є інтеграція чисельних методів оптимізації у веб-
орієнтовані сервіси. Такі сервіси забезпечують доступність потужних інструментів
оптимізації для широкого кола користувачів через мережу Інтернет. Це дозволяє
користувачам з різних куточків світу мати доступ до найсучасніших методів
вирішення задач, що сприяє глобалізації та демократизації технологій. Також, це
дозволяє мінімізувати потребу у власних високопродуктивних обчислювальних
системах, що, у свою чергу, зменшує капітальні та експлуатаційні витрати. Навіть
малі та середні підприємства, які не мають значних ресурсів для інвестування у
високопродуктивні обчислювальні системи, можуть скористатися перевагами
чисельних методів оптимізації.
Крім того, сучасні чисельні методи оптимізації активно розвиваються завдяки
поєднанню класичних алгоритмів з інноваційними підходами, такими як машинне
навчання і штучний інтелект. Це дозволяє створювати більш ефективні та точні
методи розв’язання складних задач оптимізації. Використання хмарних обчислень
також є важливою тенденцією, яка відкриває нові можливості для масштабування і
розподілу обчислювальних ресурсів.
13
Отже, розробка веб-орієнтованого сервісу для розв’язування задач оптимізації
чисельними методами є надзвичайно актуальною. Такий сервіс не тільки підвищить
ефективність і швидкість вирішення складних задач, але й зробить передові
оптимізаційні технології доступними для широкого кола користувачів, сприяючи тим
самим технологічному прогресу.
Метою роботи є створення веб-орієнтованого сервісу, який надасть можливість
користувачам швидко та ефективно розв’язувати різні класи задач оптимізації
чисельними методами, забезпечуючи доступ до потужних оптимізаційних
інструментів через мережу Інтернет. Такий сервіс має стати інструментом, який
значно полегшить процес розв’язання задач оптимізації, зробить його доступним для
широкого кола користувачів і підвищить ефективність прийняття рішень.
Завдання кваліфікаційної роботи бакалавра, які необхідно вирішити для
досягнення поставленої мети:
– проаналізувати існуючі веб-орієнтовані сервіси для розв'язання задач
оптимізації;
– розглянути теоретичні основи чисельних методів, що використовуються для
розв'язання задач оптимізації;
– визначити вимоги до веб-орієнтованого сервісу та розробити його
архітектуру;
– спроєктувати та реалізувати веб-орієнтований сервіс для розв'язання задач
оптимізації чисельними методами;
– провести тестування та оцінку ефективності розробленого сервісу на
прикладі реальних задач.
Об’єктом дослідження є процес розв’язування задач оптимізації чисельними
методами за допомогою веб-орієнтованого сервісу.
Предметом дослідження є веб-орієнтований сервіс для розв’язування задач
оптимізації чисельними методами.
Методи дослідження включають аналіз науково-технічної літератури з питань
розробки та впровадження веб-орієнтованих сервісів та чисельних методів
оптимізації; вивчення відомих чисельних методів розв'язання задач оптимізації;
14
застосування методології проєктування веб-додатків, включаючи архітектурні
підходи та технології реалізації; методи тестування та оцінки ефективності
програмного забезпечення.
Отже, впровадження веб-орієнтованого сервісу для розв’язування задач
оптимізації чисельними методами є стратегічно важливим кроком, який буде сприяє
зниженню витрат, підвищенню ефективності виробничих процесів, доступності
передових технологій та загальному технологічному прогресу. Це дозволяє
компаніям та організаціям оперативно вирішувати складні задачі оптимізації,
підтримуючи високий рівень конкурентоспроможності та інноваційної активності.
15
1 ОГЛЯД ДОСЛІДЖЕНЬ У ГАЛУЗІ МЕТОДІВ ОПТИМІЗАЦІЇ
1.1 Характеристика обраного напряму дослідження
Сучасні задачі оптимізації є одними з найбільш складних та важливих для
вирішення проблем у багатьох наукоємних галузях. Сучасні методи оптимізації часто
вимагають значних обчислювальних ресурсів і глибоких знань у сфері математичного
моделювання. Однією з актуальних проблем є створення таких чисельних методів і
алгоритмів, які б дозволяли ефективно вирішувати великі та складні задачі в
реальному часі.
У науковій спільноті важливий внесок у розвиток теорії та практики оптимізації
зробили такі вчені, як Джорж Данціг, який є автором симплекс-методу розв’язання
задач лінійного програмування, Річард Беллман, відомий завдяки роботам у сфері
динамічного програмування, Джон фон Нейман, який зробив вагомий внесок у теорію
ігор та лінійного програмування.
Останнім часом математичне програмування розвивається у напрямі
дослідження все більш спеціальних класів екстремальних задач (у відповідності до
потреб різноманітних застосувань), розробки чисельних методів, які долають
негладкiсть, неопуклiсть, яристiсть, розривність цільових функцій, а також
враховують багатоекстремальнiсть, багатокритеріальність, можливу нечітку і
стохастичну природу оптимізаційних задач.
Значний внесок у розвиток зазначених напрямів теорії і методів оптимізації
зробили українські вчені: В.М. Глушков, В.С. Мiхалевич, Ю.М. Єрмольєв,
Б.М. Пшеничний, Н.З. Шор та інші.
Однією з ключових тенденцій у вирішенні задач оптимізації є розвиток
гібридних методів, що поєднують класичні алгоритми з методами машинного
навчання. Це дозволяє підвищити ефективність і точність розв’язування складних
задач. Водночас активний розвиток отримали хмарні обчислення, що дозволяють
використовувати значні обчислювальні потужності для вирішення задач оптимізації
на веб-орієнтованих платформах. Це відкриває нові можливості для швидкого та
ефективного розв’язання задач у реальному часі, забезпечуючи доступ до потужних
оптимізаційних інструментів через Інтернет.
16
Сучасні дослідження в галузі оптимізації націлені на пошук нових інноваційних
підходів та методів, які дозволять ефективно розв'язувати складні оптимізаційні
задачі. Розглянемо основні напрями розвитку та інноваційні підходи, що
використовуються в сучасних дослідженнях в галузі оптимізації.
1. Метаевристичні методи. Метаевристичні методи представляють собою клас
алгоритмів, які моделюють процеси живої та неживої природи, а також соціальні
явища у людських спільнотах для розв'язання оптимізаційних задач. Ці методи
включають в себе генетичні алгоритми, еволюційні стратегії, поведінкові методи та
інші. Вони відрізняються високою здатністю дослідження простору рішень та
здатністю знаходити глобальні оптимальні розв’язки в складних задачах. Приклади
досліджень з цього напрямку розвитку наведено в роботах [1]-[4].
2. Методи машинного навчання. Використання алгоритмів машинного
навчання для розв'язання оптимізаційних задач стало дуже популярним напрямом
досліджень. Ці методи, такі як нейронні мережі, випадковий ліс, методи підтримки
векторів, глибоке навчання тощо, можуть створювати моделі, які навчаються з даних
та знаходять оптимальні рішення в різних областях застосування [5]-[6].
3. Еволюційні стратегії. Еволюційні стратегії моделюють процес еволюції в
природі для пошуку оптимальних рішень [7]. Вони використовують механізми
мутації, схрещування та відбору для поступового покращення рішення в кожній
ітерації. Ці стратегії дозволяють ефективно досліджувати простори рішень та
знаходити найкращі рішення в складних задачах.
4. Гібридні методи. Гібридні методи є комбінацією різних чисельних методів
для досягнення більшої ефективності та швидкості знаходження оптимальних
рішень. Наприклад, поєднання методів метаевристик з алгоритмами машинного
навчання або з еволюційними стратегіями [8]-[10]. Ці гібридні підходи можуть
забезпечувати значні переваги в розв'язанні складних оптимізаційних завдань.
5. Подальший розвиток і удосконалення існуючих методів. Дослідниками
ведеться постійна робота над вдосконаленням існуючих чисельних методів
оптимізації для забезпечення більшої швидкості, точності та ефективності [11]-[13].
Цей напрям досліджень включає в себе пошук нових алгоритмічних підходів,
17
оптимізацію параметрів методів шляхом використання адаптаційних процедур та
впровадження нових технологій для покращення результатів.
Як можна побачити з сучасних досліджень у галузі чисельних методів
оптимізації [1]-[13] ці напрями відображають неперервний розвиток інтелектуальних
зусиль, що приводить до появи нових ідей, концепцій та підходів до вирішення
складних завдань. Цей постійний пошук інновацій зумовлений потребами розвитку
сучасного суспільства та високою конкуренцією в різних галузях, що вимагають
ефективних і надійних методів оптимізації. Такий розвиток дозволяє пристосовувати
та удосконалювати існуючі методи, а також створювати нові підходи, які
відповідають сучасним вимогам та викликам. У результаті, оптимізаційні методи
стають все більш потужними та універсальними і можуть успішно застосовуватися у
широкому спектрі сфер, включаючи ті, що потребують вирішення надскладних
проблем аналізу, планування та управління.
На сьогоднішній день існує низка викликів, пов'язаних з розробкою та
впровадженням веб-орієнтованих сервісів, що можуть ефективно використовувати
чисельні методи оптимізації для вирішення широкого спектру задач.
Провідними компаніями, що активно розвивають веб-орієнтовані технології
оптимізації, є:
1. Wolfram Research. Компанія Wolfram Research, відома своїми продуктами
Mathematica та Wolfram Alpha, що використовують методи оптимізації для
розв'язання складних математичних задач, моделювання і аналізу даних.
2. Google. Google активно впроваджує оптимізаційні алгоритми для
покращення пошукових результатів, управління рекламними кампаніями та
оптимізації продуктивності своїх дата-центрів.
3. IBM. IBM зі своїм продуктом Watson використовує методи оптимізації для
аналізу великих даних, штучного інтелекту та прийняття рішень, забезпечуючи
передові рішення для бізнесу.
4. Microsoft. Microsoft впроваджує оптимізаційні алгоритми в своїх продуктах,
таких як Azure та Office 365, для підвищення ефективності та продуктивності роботи
користувачів з різноманітними даними.
18
5. Maplesoft. Maplesoft – розробник системи комп’ютерної математики Maple,
пропонує інструменти для символьних і чисельних розрахунків, що
використовуються в оптимізації та моделюванні різних систем.
6. PTC. Компанія PTC, яка розвиває відому систему комп’ютерної математики
Mathcad, забезпечує середовище для інженерних розрахунків і аналізу, допомагаючи
інженерам оптимізувати конструкції та процеси.
7. Aptech Systems. Aptech Systems, відома своїм продуктом GAUSS, надає
інструменти для економетричного аналізу і чисельного моделювання, що часто
застосовуються в фінансовій і економічній оптимізації.
8. MathWorks. MathWorks, розробник системи комп’ютерної математики
MATLAB, широко використовується в інженерії, науці та фінансах для
математичного моделювання, обробки даних та алгоритмів оптимізації.
1.2 Постановка проблеми
Тема дослідження – розробка веб-орієнтованого сервісу для розв’язування
задач оптимізації чисельними методами.
Створення веб-орієнтованого сервісу для розв’язання задач оптимізації надасть
можливість дослідникам і фахівцям у різних сферах діяльності людини
використовувати сучасні інформаційні технології як для проведення наукових
розвідок, так і для вирішення практичних екстремальних задач. Цей сервіс
представляє собою інноваційний інструмент, доступний для широкого кола
користувачів, який забезпечить зручний та швидкий доступ до потужних
інструментів оптимізації через веб-інтерфейс.
Основними перевагами сервісу мають бути:
– широкий спектр застосування: веб-орієнтований сервіс дозволяє
розв’язувати задачі оптимізації в різних галузях діяльності людини, включаючи
фінанси, технології, медицину, транспорт, енергетику, логістику та багато інших, що
робить його досить універсальним і корисним інструментом для широкого кола
професіоналів та науковців;
19
– доступність та мобільність: веб-орієнтований сервіс доступний з будь-
якого пристрою з підключенням до мережі Інтернет, що робить його надзвичайно
зручним для користувачів у будь-якому місці та часі. Це дозволяє користувачам
працювати з даними та розв’язувати задачі оптимізації, не обмежуючи себе жодними
географічними або технічними обмеженнями;
– швидкість та ефективність: використання потужних обчислювальних
ресурсів та передових алгоритмів оптимізації дозволяє швидко та ефективно
розв’язувати складні оптимізаційні задачі, що допомагає користувачам зберігати час
та зусилля при вирішенні важливих проблем;
– гнучкість та масштабованість: сервіс має гнучкі засоби введення вхідних
параметрів, забезпечує можливість налаштування та розширення функціоналу з
урахуванням специфічних потреб користувачів та сучасних технологічних тенденцій.
Веб-орієнтований сервіс розв’язування задач оптимізації чисельними методами
можна буде використовувати не лише в наукових дослідженнях, а й надає значні
можливості для навчання студентів математичних та комп’ютерних спеціальностей
методам оптимізації та пов'язаних з ними дисциплін.
Студенти зможуть використовувати сервіс для вивчення та практичного
застосування різних чисельних методів оптимізації. Вони зможуть експериментувати
з різними алгоритмами та параметрами, аналізувати результати та отримувати
практичний досвід у вирішенні реальних оптимізаційних задач. Це дозволить їм
краще зрозуміти та вивчити основні принципи та концепції оптимізації, а також
навчитися ефективно використовувати веб-сервіси для розв'язання складних завдань.
Крім того, за допомогою даного сервісу викладачі математичних та
комп'ютерних дисциплін зможуть створювати навчальні курси, лабораторні роботи
та практичні завдання, спрямовані на вивчення методів оптимізації. Вони зможуть
створювати реалістичні сценарії та завдання, що відповідають сучасним вимогам та
тенденціям у галузі, тим самим підвищуючи якість освітнього процесу.
Такий сервіс може стати важливим кроком у модернізації навчання, сприяючи
розвитку компетентностей студентів у сфері аналізу даних, програмування та
20
оптимізації, а також забезпечуючи їх підготовку до викликів сучасного
технологічного світу.
1.3 Аналіз деяких сервісів розв’язання задач оптимізації
На сьогодні провідні ІТ-компанії світу розробляють програмні засоби для
розв’язання задач оптимізації, зокрема й веб-орієнтовані сервіси. Розглянемо деякі з
них.
1.3.1 MATLAB Optimization Toolbox
MATLAB Optimization Toolbox [14] є одним із ключових інструментів в
екосистемі системи комп’ютерної математики MATLAB, призначеним для
розв'язання різноманітних задач оптимізації. Цей пакет надає багато функцій і
методів для вирішення завдань мінімізації та максимізації функцій з урахуванням
обмежень (Рис. 1.1).
Рисунок 1.1 – Приклад використання MATLAB Optimization Toolbox для
розв’язання задач оптимізації
Optimization Toolbox включає засоби розв’язання таких задач:
21
– задач одновимірної умовної оптимізації: розв'язання задач мінімізації
цільової функції від однієї змінної на заданому проміжку (функція fminbnd);
– задач безумовної оптимізації: розв'язання задач мінімізації цільової функції
без обмежень (функції fminsearch, fminunc);
– задач умовної оптимізації: розв'язання задач мінімізації цільової функції за
наявності лінійних та нелінійних обмежень (функція fmincon);
– задач лінійного програмування (Linear Programming): розв'язання задач
математичного програмування, де цільова функція та функції обмежень є
лінійними (функція linprog);
– задач нелінійного програмування (Nonlinear Programming): розв'язання
задач нелінійної оптимізації, де цільова функція та функції обмежень
можуть бути нелінійними (функція: fmincon);
– задач квадратичного програмування (Quadratic Programming): розв'язання
задач квадратичного програмування, які часто виникають у вирішенні
різних оптимізаційних проблем (функція quadprog);
– задач цілочислового лінійного програмування (Integer Linear Programming):
розв'язання задач, в яких деякі змінні повинні бути цілими числами (функція
intlinprog);
– задачі глобальної оптимізації: розв'язання задач, в яких здійснюється пошук
глобальних мінімумів та максимумів цільової функції у заданій області за
допомогою генетичного алгоритму (функція ga) та поведінкового алгоритму
PSO (функція particleswarm);
– задачі багатокритеріальної оптимізації: можливість розв'язання задач, в
яких існують кілька цільових функцій і вимагається знаходження
компромісного рішення (функції fminimax, fgoalattain).
Математична потужність та зручність MATLAB Optimization Toolbox роблять
його популярним серед інженерів, науковців та професіоналів у багатьох галузях, де
важливо знаходити оптимальні рішення. Окрім Optimization Toolbox, MATLAB
пропонує ще декілька інших інструментів, що сприяють оптимізації в широкому
спектрі застосувань. Global Optimization Toolbox надає методи для пошуку
22
глобальних мінімумів та максимумів цільових функцій, допомагаючи уникнути
попадань в локальні мінімуми. Curve Fitting Toolbox дозволяє наближати
експериментальні дані математичними моделями, що може бути корисним у випадках
оптимізації параметрів моделей. Simulink Design Optimization дозволяє
використовувати оптимізаційні методи для налаштування параметрів і моделей
Simulink, що значно полегшує процес проєктування та аналізу систем керування та
симуляцій. Ці інструменти, доповнюючи Optimization Toolbox, роблять MATLAB і
його веб-аналог MATLAB ONLINE потужним середовищем для розв'язання
різноманітних завдань оптимізації у багатьох галузях, включаючи інженерію, науку,
фінанси та бізнес.
1.3.2 GNU Octave
GNU Octave [15] – безкоштовний альтернативний програмний пакет до Matlab,
який також має власну бібліотеку чисельних методів оптимізації. Вона містить
реалізації різних алгоритмів оптимізації, доступних для безкоштовного
використання. Однак інтерфейс користувача Octave (Рис 1.2) може бути менш
зручний порівняно з інтерфейсом системи MATLAB.
Рисунок 1.2 – Приклад використання GNU Octave
23
Основними перевагами GNU Octave є:
– безкоштовність: GNU Octave є вільним програмним забезпеченням, який
можна використовувати безкоштовно без обмежень та ліцензійних вимог;
– крос-платформенність: Octave доступний для різних операційних систем,
включаючи Windows, macOS та різні дистрибутиви Linux, що робить його
доступним для широкого кола користувачів;
– сумісність з MATLAB: Octave забезпечує високий рівень сумісності з
MATLAB, що дозволяє використовувати код, написаний для MATLAB, без
змін. Це дозволяє користувачам легко переходити від одного середовища до
іншого;
– широкий функціонал: GNU Octave містить широкий набір функцій для
різних обчислень, включаючи аналіз даних, обробку сигналів, обчислення
та інші. Він також має багато вбудованих функцій, що реалізують чисельні
методи оптимізації, що робить його корисним інструментом для розв’язання
оптимізаційних задач;
– активна спільнота: Octave має велику та активну спільноту користувачів та
розробників, яка надає підтримку, допомогу та розвиток програмного
забезпечення. Це дозволяє швидко вирішувати проблеми та отримувати нові
функції та покращення.
Загалом, GNU Octave є потужним та безкоштовним інструментом для наукових
обчислень, який може бути використаний для розв’язання різних задач, включаючи
задачі оптимізації.
1.3.3 Google OR-Tools
Google OR-Tools [16] - це набір безкоштовних відкритих інструментів для
розв'язання різноманітних оптимізаційних задач. Однією з основних особливостей
цього пакету є те, що він розроблений компанією Google (Рис 1.3) і має високу
швидкість та ефективність завдяки використанню передових алгоритмів та
технологій.
24
Рисунок 1.3 – Головна сторінка Google OR-Tools
Основні компоненти Google OR-Tools включають:
– OR-Tools Linear Solver. Цей компонент надає можливості для розв'язання
лінійних оптимізаційних задач, таких як задач лінійного програмування. Він
дозволяє здійснювати максимізацію або мінімізацію лінійних функцій
об'єкта за наявності обмежень;
– OR-Tools Integer Solver. Цей компонент призначений для розв'язання
цілочисельних оптимізаційних задач, де змінні обмежені цілими числами.
Він надає можливість розв’язувати комбінаторні проблеми, такі як задачі
комівояжера, розкладання, покриття і т.д;
– OR-Tools Constraint Solver. Цей компонент надає можливості моделювати та
розв'язувати різноманітні оптимізаційні задачі за наявності обмежень. Він
дозволяє розв’язувати складні задачі зі змінними обмеженнями та умовами;
– OR-Tools Routing. Цей компонент призначений для розв'язання задач
маршрутизації, таких як задача комівояжера, задача розкладання маршрутів
25
та інші. Він дозволяє ефективно оптимізувати маршрути для різноманітних
задач;
– OR-Tools Graph Algorithms. Цей компонент призначений для реалізації
різних алгоритмів оптимізації на графах, включаючи пошук найкоротшого
шляху, мінімального остовного дерева, потоку максимального розрізу та
інші.
Google OR-Tools має декілька переваг, включаючи високу швидкість та
ефективність, розширені можливості для різних типів оптимізаційних задач та
безкоштовну ліцензію. Цей набір інструментів може бути корисним для розробки
різноманітних оптимізаційних додатків та програмних рішень.
1.3.4 Microsoft Azure Machine Learning
Microsoft Azure Machine Learning [17] - це хмарна платформа для розробки,
навчання, валідації та розгортання моделей машинного навчання та штучного
інтелекту, яка також має функціонал для розв'язання оптимізаційних завдань. Вона
надає користувачам доступ до широкого спектру алгоритмів оптимізації та
машинного навчання через веб-інтерфейс (Рис. 1.4) або API.
Рисунок 1.4 – Домашня сторінка Microsoft Azure Machine Learning Studio
26
Основні характеристики та компоненти платформи включають:
– інтегроване середовище розробки: Azure Machine Learning Studio надає
візуальний інтерфейс для створення, навчання та валідації моделей
машинного навчання. Це інтуїтивно зрозуміле середовище, яке дозволяє
користувачам проводити експерименти з різними алгоритмами та
параметрами моделей;
– інтеграція з іншими сервісами Azure: Azure Machine Learning легко
інтегрується з іншими сервісами Azure, такими як Azure Data Lake, Azure
Blob Storage, Azure SQL Database тощо. Це дозволяє легко і безпечно
взаємодіяти з даними та іншими ресурсами в хмарному середовищі;
– автоматизація процесу навчання моделей: Azure Machine Learning надає
можливості для автоматизації процесу навчання моделей, включаючи
автоматичний підбір гіперпараметрів, оптимізацію моделей та вибір
найкращих моделей за критеріями ефективності;
– масштабованість: платформа Azure забезпечує масштабованість
обчислювальних ресурсів для навчання та валідації моделей, що дозволяє
ефективно обробляти великі обсяги даних та виконувати складні
обчислення;
– безпека та конфіденційність даних: Azure Machine Learning відповідає
вимогам щодо безпеки та конфіденційності даних, забезпечуючи захист
даних користувачів під час їх обробки та аналізу;
– розгортання моделей: після навчання моделей в Azure Machine Learning їх
легко розгорнути у виробничому середовищі для використання у реальних
додатках та процесах бізнесу.
Загалом, Microsoft Azure Machine Learning надає широкий спектр можливостей
для розробки та використання моделей машинного навчання в хмарному середовищі.
Це робить платформу популярним інструментом серед розробників та дослідників у
галузі штучного інтелекту та аналітики даних.
27
1.3.5 Wolfram Alpha
Wolfram Alpha [18] – це база знань і набір обчислювальних алгоритмів (англ.
computational knowledge engine), яка функціонує як онлайн-сервіс типу «питання-
відповідь» і розроблена компанією Wolfram Research. Цей сервіс має засоби для
розв'язання різноманітних оптимізаційних задач та може вирішувати прості та
складні математичні задачі, включаючи задачі мінімізації та максимізації функцій з
обмеженнями (Рис. 1.5).
Рисунок 1.5 – Сторінка розв’язку задачі глобальної оптимізації в Wolfram Alpha
Основні кроки використання Wolfram Alpha для розв’язання задач оптимізації
можна узагальнити наступним чином:
– введення умови задачі оптимізації: спочатку, користувач вводить у
відповідне поле запиту Wolfram Alpha математичні формули, що описують
цільову функцію та обмеження, які повинні бути враховані в задачі
оптимізації (мінімізації або максимізації функції за наявності певних умов);
28
– активізація розв’язувача Wolfram Alpha: після введення задачі, користувач
натискає кнопку «=» Wolfram Alpha, що активує блок розв’язування
поставленої задачі;
– аналіз та відповідь: Wolfram Alpha аналізує введену задачу та використовує
чисельні методи для знаходження оптимального розв'язку. Результат
включає значення змінних, при яких досягається екстремум, а також
значення самої функції;
– візуалізація результатів: Wolfram Alpha може надати графіки, таблиці та
інші візуальні елементи, щоб допомогти користувачеві зрозуміти
оптимальний результат та вплив різних змінних;
– додаткові опції та аналіз: користувач може використовувати додаткові
параметри та опції, щоб налаштувати процес оптимізації або отримати
додаткову інформацію про розв'язок.
Wolfram Alpha може обробляти більш складні задачі оптимізації, враховуючи
різноманітні умови та обмеження. Використання чисельних методів дозволяє
отримувати швидкі та точні результати в різноманітних оптимізаційних сценаріях.
1.3.6 Спеціалізовані бібліотеки та пакети програмного забезпечення
Також для розв'язання задач оптимізації існує ряд спеціалізованих бібліотек та
пакетів програмного забезпечення, які дозволяють використовувати різні чисельні
методи та оптимізаційні алгоритми:
– SciPy [19] – бібліотека для мови програмування Python, яка містить модуль
scipy.optimize для чисельного розв'язання задач оптимізації. Вона включає в
себе різні методи, такі як методи мінімізації та глобальної оптимізації;
– CVXPY [20] – бібліотека для оптимізації, яка дозволяє формулювати задачі
оптимізації у формульному вигляді в Python та використовувати різні засоби
для їх розв'язання;
– Gurobi [21] – комерційний пакет для розв'язання задач оптимізації, який
надає швидкі та ефективні розв'язки для широкого спектру оптимізаційних
завдань;
29
– Optim.jl [22] – бібліотека для мови програмування Julia, яка містить
різноманітні чисельні методи для оптимізації, включаючи методи
мінімізації та глобальної оптимізації;
– AMPL [23] – мова та середовище для моделювання та розв'язання задач
оптимізації. Вона дозволяє виразно визначати математичні моделі та
використовувати різні солвери для їх розв'язання;
– MOSEK [24] – комерційний розв’язувач задач оптимізації, який підтримує
різноманітні види оптимізаційних задач, включаючи лінійне
програмування, квадратичне програмування та цілочислове програмування.
Платформи, розглянуті вище, мають як свої переваги, так і недоліки, особливо
при використанні у навчанні. Один із недоліків полягає у тому, що вони, зазвичай,
повертають лише кінцевий результат оптимізації, не надаючи відомостей про
ітераційний процес пошуку оптимального розв'язку. Це може бути обмеженням для
студентів та інших користувачів, які хочуть отримати більше інсайтів про роботу
чисельних методів оптимізації.
Окрім того, інтерфейси деяких інструментів можуть бути складними для
розуміння, особливо для початківців. Зрозумілий та інтуїтивний інтерфейс грає
важливу роль у сприйнятті та вивченні матеріалу, що розглядається.
Одним із головних пріоритетів при розробці нового сервісу є надання
користувачам повного розуміння процесу оптимізації. Таким чином, новий сервіс
буде спроєктований так, щоб відображати ітераційний процес пошуку результату,
щоб користувачі мали можливість докладно вивчати та розуміти етапи оптимізації.
Крім того, для полегшення вивчення та розуміння методів оптимізації,
розроблений сервіс буде містити відкриту Python бібліотеку. Це надасть
користувачам можливість ознайомитися з реалізацією чисельних методів оптимізації,
експериментувати з ними та вдосконалювати їх у власних проєктах. Такий підхід
дозволить розширити знання користувачів і зробить процес навчання більш
доступним та ефективним.
30
1.4 Результати аналізу обраного напряму дослідження
У даному розділі було проведено аналіз сучасного стану проблем у галузі
методів оптимізації, що здійснюються вітчизняними та зарубіжними науковцями.
Основним завданням було виявлення основних напрямів розвитку та інноваційних
підходів, які застосовуються для розв’язання складних оптимізаційних задач.
Зазначений аналіз охопив як вітчизняні, так і зарубіжні наукові джерела, що
дозволило отримати широкий огляд ключових напрямів розвитку та інноваційних
підходів.
Метаевристичні алгоритми, такі як генетичні алгоритми та ройові алгоритми,
здобули широке визнання як ефективні інструменти для розв'язання складних
оптимізаційних задач. Їхній успіх полягає в здатності працювати з великими обсягами
даних та знаходити оптимальні рішення в умовах невизначеності та неоднорідності.
Методи машинного навчання, зокрема нейронні мережі та глибоке навчання,
змінили спосіб сприйняття оптимізації. Вони дозволяють розробляти інтелектуальні
системи, які можуть самостійно навчатися та адаптуватися до нових умов, що
відкриває нові можливості для пошуку оптимальних рішень у різних галузях
застосування.
Гібридні підходи, які комбінують різні методи оптимізації, стають все більш
популярними. Їхній успіх полягає в здатності комбінувати переваги різних методів та
знаходити найкращі рішення в різних умовах.
Оптимізація з обмеженнями викликає особливий інтерес, оскільки це важлива
складова реальних задач, де потрібно враховувати різноманітні умови та обмеження.
Врахування нечітких та невизначених даних стає все більш важливим аспектом
у галузі оптимізації. Розробка адаптивних та гнучких моделей, які можуть працювати
з різними типами даних та умовами, відкриває нові можливості для пошуку
оптимальних рішень.
Загальний аналіз сучасних досліджень у галузі оптимізації чисельними
методами підкреслює важливість подальшого дослідження та розвитку методів для
вирішення складних завдань у різних галузях.
31
Висновки до розділу 1
У даному розділі було проведено аналіз обраного напряму дослідження, який
охоплює сучасні методи та інструменти для розв’язання задач оптимізації. У ході
цього аналізу було розглянуто основні характеристики напрямів розвитку чисельних
методів оптимізації, що включає вивчення теоретичних аспектів та практичних
застосувань цих методів.
У результаті аналізу було також виявлено проблемні аспекти, які можуть
вплинути на подальше дослідження та розробку нових рішень. Серед таких аспектів
– необхідність у забезпеченні масштабованості сервісів, адаптації методів
оптимізації до різних типів задач, а також інтеграції з сучасними технологіями
машинного навчання та опрацювання великих даних.
Отримана інформація надає чітке уявлення про стан сучасних засобів реалізації
чисельних методів оптимізації та окреслює напрями для подальшого вдосконалення.
Зокрема, вона допоможе у розробці нового веб-орієнтованого сервісу, який
поєднуватиме в собі найкращі риси існуючих рішень та враховуватиме виявлені
недоліки і проблеми. Це сприятиме створенню більш ефективного, надійного та
зручного інструменту для розв’язання задач оптимізації, що відповідатиме сучасним
вимогам та потребам користувачів.
32
2 ХАРАКТЕРИСТИКА ЧИСЕЛЬНИХ МЕТОДІВ ОПТИМІЗАЦІЇ
2.1 Загальна характеристика ітераційних методів оптимізації
Всюди, де є можливість активної участі людини, виникає проблема відшукання
найкращого, тобто оптимального, рішення. Слово "оптимальний" походить від
латинського optimus, що значить - найкращий, досконалий. Щоб знайти оптимальний
серед множини різних варіантів, доводиться розв'язувати задачі на знаходження
максимуму, чи мінімуму певних показників, тобто найбільших чи найменших значень
деяких величин. Обидва ці поняття - максимум (maximum), чи мінімум (minimum)
об'єднуються єдиним терміном "екстремум" (від латинського extremum - крайнє).
Задачі на відшукання максимуму, чи мінімуму певних величин називаються
екстремальними задачами. Методи дослідження різних типів екстремальних задач та
їх розв'язування складають основу теорії оптимізації.
Конкретні цілі, поставлені в задачі, об’єднуються, з математичної точки зору, в
цільову функцію, максимум чи мінімум якої треба знайти, а обмеження задачі
визначають деяку множину значень величин, від яких залежить цільова функція, що
задовольняють всім умовам задачі. Ця множина значень утворює допустиму множину
задачі. Якщо цілі поставленої задачі описуються однією функцією, то задача
називається однокритеріальною, в протилежному випадку – багатокритеріальною.
Формальна модель задачі оптимізації має вигляд:
��(����, ����, … , ����) → ������ (������), �� ∈ ��, (2.1)
де ��(��) – цільова функція, �� – допустима множина.
Зазначимо, що в загальному випадку, за допомогою випадкового, інтуїтивного,
або евристичного вибору значень відповідних величин, реальну задачу розв’язати
практично неможливо, оскільки помилка може занадто дорого коштувати. Тому в цій
ситуації на допомогу приходять потужні математичні методи та засоби сучасних
комп’ютерних технологій, які досить точно і ефективно розв’язують поставлену
задачу.
Якщо одержана математична модель (задача) відноситься до певного класу
оптимізаційних задач, то метод її розв’язування обирається, як правило, з вже
існуючих методів. У протилежному випадку необхідно:
33
– дослідити властивості цільової функції, зокрема на неперервність i
диференційованість;
– визначити умови існування розв'язку задачі при заданих обмеженнях;
– встановити необхідні, а по можливості i достатні, умови глобального або
локального екстремуму;
– розробити аналітичні та/або чисельні методи відшукання розв'язку задачі.
Надалі будемо розглядати скiнченновимiрнi задачі оптимізації, тобто задачі,
допустима множина яких належить евклідовому простору ����. Якщо �� ≠ ∅, то задача
(2.1) називається сумісною, в протилежному випадку – несумісною. Якщо �� = ����, то
задача (2.1) називається задачею без обмежень на змінні, у протилежному випадку –
задачею з обмеженнями. Формалізація екстремальної задачі полягає в точному
визначенні її основних елементів: цільової функції ��(��) i допустимої множини ��.
Для розв’язанні оптимізаційних задач найбільш розповсюдженими є так звані
методи послідовних наближень, або ітераційні методи, в яких будується
послідовних точок
��(0), ��(1), … , ��(��), ��(��+1), …, (2.2)
пов’язаних між собою рекурентним співвідношенням
��(��+1) = ��(��(��)), �� = 0,1, …, (2.3)
де �� – деяке правило, за допомогою якого точці ��(��) ставиться у відповідність
нова точка ��(��+1).
2.1.1 Основні принципи та підходи до ітераційних методів оптимізації
Ітераційні методи оптимізації є ключовою складовою сучасних алгоритмів
розв'язання складних математичних задач. Ці методи використовуються для
ефективного пошуку оптимальних рішень у широкому спектрі областей, від науки та
інженерії до фінансів та штучного інтелекту.
Основний принцип ітераційних методів полягає в систематичному
вдосконаленні кандидатів у рішення на кожній ітерації з метою збільшення якості та
34
точності результату. Це досягається шляхом послідовного оновлення параметрів
алгоритму на основі аналізу властивостей функції та її похідних.
В ітераційних методах використовуються різноманітні підходи та стратегії для
вибору напрямку руху та розміру кроку. Вони включають в себе методи на основі
градієнта, які використовують інформацію про перші частинні похідні функції для
визначення найкращого напрямку у просторі параметрів. Крім того, існують методи
на основі спряжених напрямків, які використовують ідею комбінування між різними
напрямками для забезпечення ефективного пошуку рішення.
Найпродуктивніші підходи до оптимізації зазвичай поєднують у собі різні
методи та стратегії. Наприклад, метод Ньютона використовує інформацію про другі
частинні похідні функції для побудови апроксимації цільової функції у формі
квадратичного наближення, що дозволяє здійснювати швидкий та точний пошук
оптимального рішення.
2.1.2 Переваги та недоліки використання ітераційних методів
Хоча ітераційні методи оптимізації є невід'ємною складовою багатьох
алгоритмів оптимізації та штучного інтелекту проте, їх використання не є
універсальним рішенням для всіх видів оптимізаційних задач. Вони мають свої
обмеження та недоліки, які варто враховувати при їх виборі.
Щоб розібратись з недоліками ітераційних методи оптимізації, варто спочатку
звернути увагу на їх переваги:
– ефективність: ітераційні методи здатні до ефективного знаходження
локальних екстремумів у великих просторах параметрів, що робить їх
відмінними для застосування у складних оптимізаційних задачах;
– гнучкість: ітераційні методи можуть бути адаптовані до різних типів
функцій, обмежень та умов задачі, що робить їх, у певному розумінні,
універсальними інструментами для вирішення різних проблем;
– збіжність: правильно налаштовані ітераційні методи можуть швидко
збігатися до оптимального розв'язку для деяких класів функцій, зменшуючи
кількість ітерацій, необхідних для досягнення заданої точності.
35
Тепер звернемо увагу на недоліки таких методів:
– залежність від початкового наближення: ефективність ітераційних методів
може значно залежати від початкового наближення, що може призвести до
потрапляння у локальні екстремуми та зниження точності та якості
результату;
– чутливість до обмежень: деякі ітераційні методи можуть бути
неефективними за наявності обмежень, або умов задачі, що може
обмежувати їх застосування в певних сценаріях або вимагати додаткової
уваги до їх обробки;
– обчислювальні витрати: використання ітераційних методів може вимагати
значних обчислювальних ресурсів, особливо при пошуку в просторі великої
розмірності або при оптимізації цільових функцій зі складною топологією
ліній рівня, що може бути обмеженням в деяких ситуаціях.
Отже, ефективність ітераційних методів залежить від конкретного випадку
використання, включаючи властивості цільової функції, обмеження задачі та
наявність обчислювальних ресурсів. Правильний вибір методу та належне
налаштування параметрів може забезпечити успішне розв’язання оптимізаційних
задач з високою точністю та ефективністю.
2.1.3 Класифікація ітераційних методів оптимізації
Ітераційні методи оптимізації, розглянуті у контексті їх широкого спектру
застосування та особливостей, можна класифікувати за різними критеріями, що
дозволяє краще розуміти їхні характеристики та обирати серед них найбільш
відповідні для конкретних завдань.
Можна розглянути наступні критерії, які можуть бути використані для
класифікації:
– за правилом вибору напрямку руху: цей критерій відображає підходи до
визначення напрямку оптимізації. Методи з напрямком використовують
градієнт функції для визначення напрямку, тоді як методи без напрямку
36
можуть працювати без цих даних або використовувати інші методи
визначення напрямку;
– за типами задач оптимізації, до розв’язування яких вони застосовуються:
ітераційні методи можна класифікувати за типами задач оптимізації, до
розв’язування яких вони застосовуються, зокрема, методи одновимірної
оптимізації, методи безумовної та умовної оптимізації, а також методи
глобальної оптимізації;
– за складністю та швидкістю: цей критерій класифікації відображає
складність методів та їхню швидкість збіжності. Деякі методи можуть бути
більш ефективними з точки зору обчислювальних ресурсів, а інші - швидше
збігатися до оптимального розв'язку;
– за придатністю для паралельних обчислень: оскільки паралельні
обчислення стають все більш поширеними, ітераційні методи можна
класифікувати за їхньою придатністю для паралельного виконання. Деякі
методи можуть бути легко розпаралеленими, тоді як інші можуть бути менш
придатними для паралельного виконання через свою структуру, чи
особливості алгоритму.
Детальна класифікація методів за типами задач оптимізації, до розв’язування
яких вони застосовуються, має важливе значення, оскільки вона дозволяє розуміти, в
яких конкретних ситуаціях можна застосувати кожен з них. Це розкриває потенційні
можливості кожного методу та допомагає обрати той, який найбільш придатний до
розв’язання конкретної задачі оптимізації.
У подальших розділах даної роботи методи будемо класифікувати за типами
задач оптимізації, до розв’язування яких вони застосовуються. Це включатиме аналіз
їхньої ефективності та придатності для вирішення різноманітних типів
оптимізаційних задач, таких як одновимірна оптимізація, безумовна та умовна
оптимізація, а також глобальна оптимізація (Рис. 2.1).
37
Рисунок 2.1 – Класифікація методів оптимізації
2.2 Методи одновимірної оптимізації
Основна особливість методів одновимірної оптимізації полягає в їхній
здатності працювати з одновимірними функціями, тобто такими, які залежать лише
від однієї змінної. Це дозволяє ефективно аналізувати та оптимізувати параметри
моделей, фінансові стратегії, медичні та технічні процеси, серед інших застосувань.
Кожен метод одновимірної оптимізації має свої особливості. Наприклад, метод
дихотомії характеризується простотою та надійністю, в той час як метод золотого
перетину відзначається швидкою збіжністю. Метод Фібоначчі має оптимальну
збіжність, в той час як метод парабол використовує квадратичні інтерполяції для
ефективного зближення до точки мінімуму, або максимуму.
Ці методи є ключовими інструментами в чисельних методах оптимізації,
дозволяючи вирішувати складні завдання швидко та ефективно.
2.2.1 Метод дихотомії
В основі методу дихотомії (див., наприклад, [25]) лежить ідея пошуку мінімуму,
або максимуму функції на заданому відрізку, шляхом послідовного поділу цього
відрізка на дві рівні частини та оцінки значення функції в обох точках.
38
Особливість методу дихотомії полягає у його простоті та надійності. Він добре
працює з неперервними та гладкими функціями, і не вимагає диференціювання
функції для знаходження точки екстремуму
Проте метод дихотомії може бути повільним, особливо при роботі з великими
відрізками. Також він може бути менш ефективним у випадку, коли функція має
вузький пік або яму.
2.2.2 Метод золотого перерізу
Метод золотого перерізу (див., наприклад, [25]) базується на поділі інтервалу
відносно золотого відношення. Він використовує властивість золотого відношення,
де відношення двох послідовних відрізків дорівнює відношенню більшого відрізка до
меншого, яке дорівнює приблизно 1.618.
Особливість методу золотого перерізу полягає в його швидкій збіжності. Ще
однією важливою перевагою цього методу є мінімальна кількість обчислень функції,
що потрібна для знаходження оптимального розв'язку.
Проте метод золотого перерізу має свої обмеження. Він вимагає визначення
постійного кроку, що може бути складним у деяких випадках. Також, використання
золотого відношення може бути менш ефективним у випадках, коли функція має
нерегулярні або нестандартні форми.
2.2.3 Метод Фібоначчі
Цей метод (див., наприклад, [25]) використовує властивість послідовності
Фібоначчі, де кожне наступне число є сумою двох попередніх. В основі його роботи
лежить ідея пошуку мінімуму, або максимуму функції на заданому відрізку шляхом
зменшення його довжини на кожній ітерації.
Особливість методу Фібоначчі полягає в його оптимальній збіжності. Він
дозволяє швидко наближатися до точки мінімуму, або максимуму за рахунок
раціонального зменшення величини відрізка пошуку. Цей метод використовує
обмежену кількість обчислень функції, що робить його ефективним для розв'язання
чисельних задач оптимізації.
39
Проте метод Фібоначчі може бути менш ефективним у випадках, коли
необхідно проводити багато ітерацій для досягнення потрібної точності, особливо на
великих відрізках. Також, він вимагає встановлення початкових границь інтервалу
пошуку, що може бути складним у деяких сценаріях.
2.2.4 Метод парабол
Основна особливість методу парабол (див., наприклад, [25]) полягає у
використанні квадратичних апроксимацій функції на кожній ітерації. Це дозволяє
методу адаптуватися до форми функції та швидко зближатися до точки екстремуму.
При цьому метод парабол є менш чутливим до обмежень, що вимагаються для інших
методів.
Проте метод парабол може бути менш ефективним у випадках, коли функція
має складну, або нерегулярну форму, оскільки квадратична апроксимація може бути
недостатньою для відтворення таких форм. Також, використання методу парабол
вимагає визначення початкових точок для кожної квадратичної інтерполяції, що може
бути не простою задачею.
2.3 Методи безумовної оптимізації
Методи безумовної оптимізації використовуються для пошуку мінімуму або
максимуму функції без обмежень на значення змінних.
В n-вимірному евклідовому просторі ���� розглядається задача відшукання
мінімуму функції ��(��) на множині �� = ����:
��(��) → ������, �� ∈ ����, (2.4)
тобто задача безумовної оптимізації. Як вже відмічалось, найбільш
розповсюдженими наближеними методами розв’язування задачі виду (2.4) є
ітераційні методи. Одним з відомих рекурентних співвідношень виду (2.3) є
співвідношення виду:
��(��+1) = ��(��) + ℎ ��(��)
�� , (2.5)
40
де �� = 0,1,2, …, ��(��) ∈ ���� – вектор, який визначає напрям руху з точки ��(��) ,
ℎ 1
�� ∈ �� – параметр, величина якого визначає довжину кроку в напрямку ��(��). При
цьому, якщо ��(��) є напрямком спадання функції ��(��) в точці ��(��) для будь-яких �� =
0,1,2, …, то метод називається методом спуску.
Методи безумовної оптимізації можна класифікувати за різними критеріями.
Наприклад, за типом використаної інформації про похідні. Методи першого порядку,
такі як градієнтний спуск, використовують перші частинні похідні функції для оцінки
напрямку найшвидшого зростання чи спадання функції. Методи другого порядку,
наприклад, метод Ньютона, використовують додаткову інформацію про другі
частинні похідні для покращення точності та швидкості знаходження розв'язку.
Крім того, методи безумовної оптимізації можна класифікувати за розмірністю
задачі. Деякі методи спеціалізуються на оптимізації одновимірних функцій, тобто
функцій, які залежать лише від однієї змінної, тоді як інші придатні для
багатовимірних функцій, де кількість змінних може бути будь-якою.
Нехай в задачі (2.4) функція ��(��) диференційована на ����. Вибираючи в (2.5) за
напрямок спуску антиградієнт функцiї в точцi ��(��) , тобто вектор −��′(��(��)) ,
приходимо до iтерацiйного процесу виду
��(��+1) = ��(��) − ℎ����′(��(��)), ℎ�� > 0, �� = 0,1,2, … . (2.6)
Ітерацiйнi процеси, в яких напрямок руху на кожному кроцi спiвпадає з
антиградiєнтом (градiєнтом) функцiї, називаються градiєнтними методами. Цi
методи вiдрiзняються один вiд одного способами вибору кроку ℎ��. Розглянемо деякі
з них.
2.3.1 Метод найшвидшого спуску
Метод найшвидшого спуску (див., наприклад, [25]) – це один з основних
методів безумовної оптимізації першого порядку. Основна ідея цього методу полягає
у тому, щоб крок за кроком пересуватися вздовж антиградієнта функції для
зменшення значення функції.
41
На кожному кроці метод найшвидшого спуску обчислює градієнт (вектор
перших похідних) у поточній точці, який показує напрямок найшвидшого зростання
функції. Потім обчислюється оптимальна довжина кроку вздовж цього напрямку,
щоб забезпечити найбільше зменшення значення функції. Цей крок може бути
обчислений аналітично або чисельно, наприклад, за допомогою методу золотого
перерізу.
Метод найшвидшого спуску може мати обмеження, зокрема, він може зійти з
шляху або зупинитися в локальному мінімумі. Це особливо стосується функцій, що
мають вузькі долини. Також метод може бути повільним у збіжності, особливо в
областях, де лінія рівня цільової функції має «яристу» структуру. В таких випадках
траєкторія градієнтного методу характеризується досить швидким спуском на "дно
яру" і потім повільним зигзагоподібним рухом вздовж "яру" до точки мінімуму x*
(Рис. 2.2).
x (k)
x*
x(k+1)
Рисунок 2.2 – Зигзагоподібний рух градієнтного методу вздовж "яру"
Достоїнством градієнтних методів є простота і можливість використання для
мінімізації досить різних за характером функцій. Але в силу своєї повільної збіжності
вони, як правило, не застосовуються для розв’язання складних задач мінімізації,
зокрема з складною топографічною структурою ліній рівня цільових функцій. Тому
були розроблені і далі розробляються методи з більш високою швидкістю збіжності.
Градієнтні ж методи часто використовуються в комбінації з іншими більш
ефективними методами на початковому етапі розв’язування задачі мінімізації. Це
доцільно робити коли початкове наближення знаходиться досить далеко від точки
мінімуму і кроки вздовж антиградієнта дозволяють значно зменшити значення
цільової функції.
42
2.3.2 Яристий метод
Одним з ефективних засобів прискорення збіжності градієнтних методів є
метод, ідея якого була запропонована І. М. Гельфандом на початку 60-х років ХХ
століття, і який в літературі називається яристим методом (див., наприклад, [25]).
“Яристий крок” в (2.5), від правильності вибору якого істотно залежить
швидкість збіжності методу, може бути як сталою величиною для будь-яких k, так і
змінюватися, реагуючи на повороти “яру”. В першому випадку підбір треба робити
емпірично з врахуванням інформації про цільову функцію, яка одержується в процесі
роботи алгоритму. В другому – треба намагатися регулювати цим параметром, так,
щоб по можливості швидше проходити прямолінійні ділянки на “дні яру”, а на крутих
поворотах “яру” запобігати відхиленню від його “дна”.
2.3.3 Метод спряжених градієнтів
Основна ідея методу спряжених градієнтів (див., наприклад, [26]) полягає у
використанні градієнтів функції для керування пошуковими напрямками.
На кожній ітерації метод обчислює напрямок спуску, використовуючи
інформацію про градієнти функції та попередні напрямки спуску. Цей напрямок
спуску спряжений з попередніми, що дозволяє методу ефективно пересуватися в
просторі пошуку.
Метод спряжених градієнтів є потужним і універсальним інструментом для
оптимізації різноманітних функцій. Він ефективно працює як на простих, так і на
складних функціях, забезпечуючи швидку збіжність і точність результатів. Однак для
його успішного застосування потрібно мати можливість обчислення градієнтів
функції, що може бути складною задачею у деяких випадках.
2.3.4 Узагальнений метод Ньютона
Узагальнений метод Ньютона (див., наприклад, [25]) – це ітераційний метод
безумовної оптимізації, що використовує інформацію про другі частинні похідні
цільової функції для ефективного пошуку екстремумів.
43
На кожній ітерації метод обчислює напрямок спуску, використовуючи градієнт
функції у поточній точці та обернену матрицю Гессе (матрицю других частинних
похідних – Гессіана), що характеризує кривизну функції в поточній точці. Цей
напрямок спуску дозволяє ефективно пересуватися в просторі пошуку, мінімізуючи
значення функції.
Використання узагальненого методу Ньютона допомагає забезпечити точність
та швидкість пошуку екстремуму функції, що робить його популярним інструментом
для оптимізації в різних сферах, включаючи машинне навчання, обробку сигналів та
фінансову аналітику.
2.3.5 Квазіньютонівські методи
Квазіньютонівський методи (див., наприклад, [27]) – це сімейство ітераційних
методів безумовної оптимізації, які створені для розв'язання задач оптимізації, не
вимагаючи обчислення матриці других частинних похідних функції. Вони поєднують
в собі швидкість та ефективність методів Ньютона з відсутністю обчислення матриці
других частинних похідних та оберненої до неї матриці на кожній ітерації, що робить
їх привабливими для використання в різних областях.
Основною ідеєю квазіньютонівських методів є побудова наближеного
оберненого Гессіана функції, який оновлюється на кожній ітерації за допомогою
інформації про градієнт функції. Це дозволяє ефективно вирішувати оптимізаційні
задачі, навіть коли обчислення похідних є складним або неможливим.
2.3.6 Симплексний метод Нелдера-Міда
Симплексний метод Нелдера-Міда (див., наприклад, [25]) – це ітераційний
метод безумовної оптимізації нульового порядку, який використовує геометричний
об'єкт, відомий як симплекс.
Основна ідея полягає в тому, щоб у кожній ітерації методу визначити нові точки
симплексу, оцінити значення цільової функції в цих точках і пересунути симплекс у
напрямку зменшення значення функції.
44
Однією з особливостей симплексного методу Нелдера-Міда є його здатність
працювати у випадках, коли функція має нелінійну, негладку структуру, або коли
функція не має аналітичної форми. Він також ефективно працює у просторах великої
розмірності та може знаходити, як локальні, так і глобальні мінімуми функції.
2.4 Методи умовної оптимізації
Методи умовної оптимізації відрізняються від методів безумовної оптимізації
тим, що вони враховують наявність обмежень на значення змінних. Це означає, що
розв'язок повинен знаходитися в певній області, визначеній обмеженнями. У таких
умовах задача стає складнішою, оскільки розв'язок повинен задовольняти не лише
умовам оптимізації функції, а й умовам обмежень.
Одним із підходів до вирішення таких задач є використання методів штрафних
функцій, де обмеження перетворюються на частину функції, яку оптимізують. Ці
методи дозволяють знаходити розв'язки в області обмежень, проте можуть вимагати
великої кількості обчислень.
Інший підхід полягає в використанні методів проекції, де на кожній ітерації
здійснюється корекція розв'язку таким чином, щоб він задовольняв усім обмеженням.
Ці методи дозволяють ефективно працювати з допустимими множинами, що являють
собою опуклі тіла, але їх використання ускладнене для інших типів обмежень.
2.4.1 Метод проекції градієнта
Метод проекції градієнта (див., наприклад, [25]) є одним із методів умовної
оптимізації, який базується на використанні градієнта функції та проекції точок на
допустиму область. У цьому методі на кожній ітерації використовується інформація
про градієнт функції для знаходження напрямку найшвидшого зростання чи
спадання.
Особливістю методу проекції градієнта є те, що на кожній ітерації здійснюється
корекція розв'язку таким чином, щоб він залишався в допустимій області. Це дозволяє
ефективно працювати з обмеженнями, оскільки розв'язок завжди знаходиться в
області, що задовольняє всі умови.
45
Проте метод проекції градієнта може бути недостатньо ефективним у випадку
складних областей обмежень, або нелінійних умов. Також, в деяких випадках, для
досягнення оптимального розв'язку може бути необхідною занадто велика кількість
ітерацій.
2.4.2 Метод умовного градієнта
У методі умовного градієнта (див., наприклад, [25]) на кожній ітерації
використовується інформація про градієнт функції для знаходження напрямку
найшвидшого зростання, чи спадання. Особливістю цього методу є те, що розв'язок
завжди знаходиться в допустимій області, оскільки на кожній ітерації здійснюється
корекція таким чином, щоб він задовольняв усім обмеженням.
Метод умовного градієнта виявляється ефективним у вирішенні задач зі
складними областями обмежень, де інші методи можуть бути недостатньо
ефективними. Однак він може вимагати значної кількості ітерацій для досягнення
оптимального розв'язку в деяких випадках.
На відміну від методу проекції градієнта, метод умовного градієнта може бути
ефективним і у випадку складних умов обмежень та забезпечує швидку збіжність до
оптимального розв'язку. Однак слід враховувати, що в деяких сценаріях може
знадобитися більша кількість обчислень для досягнення прийнятного результату.
2.4.3 Метод штрафних функцій
Метод штрафних функцій (див., наприклад, [25]) дозволяє розв'язувати задачі
оптимізації з обмеженнями, перетворюючи їх на послідовність безумовних задач.
Основна ідея полягає у введенні штрафу за порушення обмежень у функцію цілі.
Однією з переваг методу штрафних функцій є його універсальність і
можливість застосування до різноманітних видів обмежень. Крім того, він дозволяє
знайти розв'язок навіть у випадках, коли інші методи можуть виявитися
неефективними, або непридатними.
46
Проте метод штрафних функцій може мати деякі обмеження у випадку
складних областей обмежень, або коли обмеження важко формалізувати у вигляді
функцій штрафу та не завжди гарантує збіжність до глобального екстремуму.
2.5 Методи глобальної оптимізації
Методи глобальної оптимізації відрізняються від інших тим, що вони
спрямовані на знаходження глобального мінімуму (або максимуму) функції на
заданій області, яка може бути дуже складною та має багато локальних екстремумів.
Методи глобальної оптимізації використовують різні стратегії для пошуку
оптимального розв'язку. Вони можуть включати в себе методи перебору, еволюційні
алгоритми, методи з випадковим пошуком та інші підходи, які орієнтовані на
виявлення глобальних екстремумів у складних функціях.
Однією з важливих переваг методів глобальної оптимізації є їхній потенціал для
виявлення глобальних максимумів або мінімумів, незважаючи на складність функції
та наявність локальних екстремумів. Вони часто застосовуються в задачах, де
важливо знайти найкращий розв'язок, що може бути поза межами традиційних
методів локальної оптимізації.
2.5.1 Метод рою частинок
Метод рою частинок (Particle Swarm Optimization) (див., наприклад, [28]) – це
метаевристичний алгоритм глобальної оптимізації, заснований на поведінці рою
птахів, чи інших живих організмів. У цьому методі кожна частинка представляє
потенційний розв'язок задачі оптимізації. Вона рухається у просторі пошуку згідно з
певними правилами, орієнтованими на знаходження найкращого розв'язку.
Основна ідея методу рою частинок полягає в тому, що кожна частинка оцінює
якість свого поточного положення, орієнтуючись на положення найкращої частинки
в рої та на свої попередні рухи. Метод рою частинок зазвичай використовується для
задач оптимізації, де немає можливості аналітичного обчислення похідних, або коли
функція має багато локальних мінімумів.
47
Метод рою частинок може бути ефективним при пошуку глобальних розв'язків
в складних просторах. Разом з тим, він може повільно збігатися до глобального
розв’язку або потрапляти до локальних екстремумів, що зменшує його здатність до
ефективного знаходження глобального розв'язку.
2.5.2 Метод кажанів
Метод кажанів (Bat Algorithm) (див., наприклад, [29]) – це інша метаевристична
техніка, яка моделює поведінку кажанів у природі для розв'язання задач оптимізації.
Основна ідея методу кажанів полягає в тому, що кажани рухаються від позиції
до позиції, притягуючись один до одного та до найкращого розв'язку, який був
знайдений до цього моменту. Вони також здатні випадково змінювати свої шляхи
руху для збільшення випадковості.
Метод кажанів може бути ефективним у розв'язанні задач оптимізації, особливо
тих, де просторий пошуку складний, або має багато локальних екстремумів. Він
також має здатність адаптуватися до змін у середовищі пошуку та виявляти глобальні
оптимальні розв'язки. Однак, як й інші метаевристичні методи, він може страждати
від недоліків, таких як збіжність до локальних екстремумах, або повільна збіжність.
2.5.3 Метод гравітаційного пошуку
Метод гравітаційного пошуку (Gravitational Search Algorithm) (див., наприклад,
[30]) – це метаевристичний алгоритм, який імітує рух об'єктів у гравітаційному полі
для пошуку глобального екстремуму в просторі пошуку.
Основна ідея полягає в тому, що кожен кандидат представляється як тіло з
певною масою, яке притягується до інших тіл в просторі пошуку згідно з їхніми
масами та відстанями. Також існує компонента руху, яка дозволяє кандидатам
рухатися у просторі залежно від їхньої швидкості та напрямку.
Однак, метод гравітаційного пошуку може мати обмеження у швидкості
збіжності та може бути чутливим до налаштувань параметрів, таких як коефіцієнт
прискорення та радіус впливу.
48
2.5.4 Метод зграї сірих вовків
Метод зграї сірих вовків (Grey Wolf Optimizer) (див., наприклад, [31]) – це
метаевристичний алгоритм оптимізації, який інспірований поведінкою зграї сірих
вовків під час полювання на здобич. У цьому методі кожен вовк представляє
кандидата на розв'язок, а зграя володіє властивістю кооперативної поведінки для
досягнення глобального екстремуму.
Основна ідея полягає в тому, що вовки в зграї намагаються зблизитися до
потенційної здобичі, яка може бути кращим розв'язком, з кожною новою ітерацією.
Вони використовують різні стратегії, такі як пошук, кругове обертання та зближення
до здобичі, для покращення якості розв'язків.
Метод зграї вовків може бути ефективним у розв'язанні різних видів
оптимізаційних задач, проте він може вимагати точних налаштувань параметрів,
таких як розмір зграї, коефіцієнти швидкості та керованої деструкції.
Усі вищенаведені методи оптимізації можуть бути потужними інструментами
для пошуку глобальних мінімумів, або максимумів у складних функціях. Однак
важливо враховувати, що багато з цих методів можуть вимагати значних
обчислювальних ресурсів, особливо при роботі зі складними функціями.
Крім того, існує ризик збіжності до локальних мінімумах, що може знизити
ефективність цих методів у пошуку глобальних екстремумів. Тому перед
використанням будь-якого методу оптимізації важливо ретельно вивчити його
характеристики, особливості та обмеження, а також врахувати специфіку задачі, яку
потрібно вирішити.
Додатковою стратегією може бути комбінація різних методів, або використання
додаткових технік, зокрема адаптаційних процедур, для забезпечення більш точного
та ефективного пошуку оптимальних розв'язків.
2.6 Тестові функції для методів оптимізації
Для об'єктивної оцінки та порівняння ефективності різних методів оптимізації
зазвичай використовують спеціально розроблені тестові функції (див., наприклад,
[32], [33]). Ці функції створюються з метою випробування алгоритмів оптимізації та
49
мають відомий глобальний мінімум, або максимум, що дозволяє об'єктивно оцінити
розв'язок, який повинен бути знайдений. Тестові функції можуть мати різні форми,
складності та характеристики, що дозволяє проводити широкий спектр тестувань та
порівнянь.
Важливим аспектом тестових функцій є їхня репрезентативність: вони повинні
відображати реальні обмеження та властивості оптимізаційних задач. Вони можуть
бути налаштовані для відтворення конкретних умов, таких як наявність локальних
екстремумів, аномалій, шумів, та інших випадків, що можуть виникати у реальних
задачах оптимізації.
Тестові функції, використані у веб-орієнтованому сервісі (див. табл. Б.1), є
важливим інструментом для оцінювання та порівняння різних методів оптимізації.
Кожна з цих функцій має свою унікальну форму та характеристики, що робить їх
корисними для випробування алгоритмів у різних умовах. Вони дозволяють
проводити об'єктивні порівняння методів оптимізації та визначати їхню ефективність
у пошуку глобальних мінімумів або максимумів. Ретельне тестування на цих
функціях допомагає розкрити сильні та слабкі сторони кожного методу, а також
сприяє розробці нових, більш ефективних алгоритмів оптимізації. Таким чином,
тестові функції є важливою складовою процесу вдосконалення методів оптимізації та
їх розвитку.
Висновки до розділу 2
У даному розділі було розглянуто найбільш популярні методи умовної і
безумовної оптимізації, що дозволило виявити основні принципи та підходи до їх
використання, а також переваги та недоліки цих методів.
Класифікація ітераційних методів допомогла розкрити різноманітність підходів
до оптимізації та їх застосування у різних ситуаціях. Були проаналізовані принципи
роботи, основні переваги та недоліки деяких методів одновимірної, безумовної,
умовної та глобальної оптимізації.
Крім того, були представлені тестові функції, які можуть бути використані для
перевірки ефективності різних методів оптимізації.
50
В цілому, отримана інформація надає комплексне уявлення про різноманітні
методи оптимізації, що є важливим кроком у подальшому розробленні та
вдосконаленні програмних рішень в області чисельних методів оптимізації.
51
3 ПРОЄКТУВАННЯ ВЕБ-ОРІЄНТОВАНОГО СЕРВІСУ
3.1 Вимоги до веб-орієнтованого сервісу
Перед тим як розпочати проєктування та розробку веб-орієнтованого сервісу
для розв'язування задач оптимізації, важливо чітко визначити вимоги до цього
сервісу. Ці вимоги включають не лише функціональні аспекти, а й нефункціональні
характеристики, такі як продуктивність, надійність та безпека.
Потрібно провести ретельний аналіз потреб користувачів та їх очікувань від
сервісу. Цей процес включатиме в себе обговорення з зацікавленими сторонами,
дослідження ринкових тенденцій та аналіз конкурентів. У результаті цього етапу буде
отримано уявлення про те, які функціональні можливості повинен надавати сервіс для
задоволення потреб користувачів та досягнення мети проєкту.
3.1.1 Функціональні вимог до веб-орієнтованого сервісу
Для початку важливо чітко визначити функціональні вимоги до веб-
орієнтованого сервісу для розв'язування задач оптимізації. Опис функціональних
вимог грає ключову роль у формулюванні потреб користувачів та уточненні їх
очікувань від сервісу.
Після проведення аналізу було сформовано перелік функціональних вимог до
веб-орієнтованого сервісу для розв'язування задач оптимізації, які повинні бути
враховані для забезпечення ефективного та зручного використання:
– реєстрація та аутентифікація користувачів: надання можливості
користувачам створювати облікові записи та виконувати вхід в систему для
забезпечення конфіденційності та безпеки даних;
– вибір методів оптимізації: можливість користувачів вибирати один або
кілька методів оптимізації залежно від специфіки їхніх завдань;
– введення параметрів задачі оптимізації: розробка інтуїтивного інтерфейсу
для введення параметрів задачі оптимізації, включаючи обмеження,
початкові значення змінних та функції;
– відображення результатів: представлення результатів у зручному форматі,
включаючи числові значення, графіки, діаграми та таблиці;
52
– збереження даних: забезпечення можливості зберігання та завантаження
даних користувачів для подальшого використання та аналізу;
– взаємодія з користувачем: розробка інтерфейсу, який забезпечує зручну
взаємодію з користувачами, включаючи надання підказок та інструкцій для
кращого розуміння процесу роботи з системою.
У першу чергу, виявлено, що широкий набір опцій оптимізації є критично
важливим для задоволення різноманітних потреб користувачів. Різноманіття
алгоритмів та стратегій оптимізації дозволяє користувачам налаштовувати сервіс з
урахуванням їхніх конкретних вимог та унікальних характеристик задач.
Другим важливим аспектом є необхідність зручного та інтуїтивно зрозумілого
інтерфейсу користувача, який дозволяв би ефективно взаємодіяти з сервісом та
виконувати різноманітні завдання оптимізації без зайвих ускладнень.
Також важливим аспектом є можливість візуалізації результатів оптимізації для
зручного аналізу та відстеження ітераційного процесу. Інтерактивні графіки, діаграми
та інші візуальні елементи сприяють кращому розумінню отриманих результатів та
допомагають користувачам приймати обґрунтовані рішення.
3.1.2 Вимоги до ефективності та швидкодії
Вимоги до ефективності та швидкодії веб-орієнтованого сервісу для
розв'язування задач оптимізації визначаються кількома ключовими аспектами:
– швидкість обробки даних: сервіс повинен бути здатним швидко обробляти
великі обсяги даних та розрахунків. Швидка реакція на запити користувачів
є критично важливою для забезпечення продуктивної роботи та задоволення
їхніх потреб;
– масштабованість: система повинна бути гнучкою та масштабованою, щоб
забезпечити продуктивну роботу навіть при збільшенні навантаження. Це
включає в себе можливість автоматичного масштабування ресурсів,
оптимізацію роботи алгоритмів та використання розподіленого обчислення,
якщо необхідно;
53
– оптимізація ресурсів: сервіс повинен оптимально використовувати
обчислювальні та мережеві ресурси для мінімізації часу реакції та
максимізації продуктивності. Це може включати кешування результатів,
оптимізацію запитів та використання розподіленого обчислення;
– стійкість та надійність: сервіс повинен бути стійким та надійним, щоб
забезпечити безперебійну роботу в умовах високого навантаження та
можливих помилок. Це може включати належне керування помилками,
резервне копіювання даних та застосування найкращих практик
забезпечення якості програмного забезпечення.
Ці вимоги до ефективності та швидкодії визначають ключові аспекти, які
повинні бути враховані під час розробки та вдосконалення веб-сервісу для
розв'язування задач оптимізації.
3.2 Структура веб-орієнтованого сервісу
3.2.1 Моделі даних та їх взаємозв'язки
У контексті розробки програмного забезпечення модель даних визначає
структуру та взаємозв'язки між різними типами даних, які використовуються в
системі. Ці моделі даних є основою для проєктування баз даних, розробки
програмного забезпечення та взаємодії з даними. Вони відображають сутності,
атрибути цих сутностей та взаємозв'язки між ними, що допомагає зрозуміти, як дані
будуть організовані для ефективного доступу та операцій з ними.
У веб-сервісах моделі даних важливі, оскільки вони визначають структуру та
формат даних, які обмінюються між клієнтом та сервером. Вони допомагають
зберегти консистентність даних та забезпечити правильну обробку інформації.
Під час аналізу вимог до системи і потреб користувачів було визначено ключові
моделі даних, які будуть використовуватись у веб-сервісі:
– модель даних «користувач», що включає основні атрибути та
характеристики користувачів, необхідні для процесів авторизації та автентифікації.
Вона включає інформацію, таку як ім'я користувача, електронну пошту, пароль та
права доступу, які є ключовими для доступу до системи;
54
– модель даних «роль», що визначає рівень доступу користувача до різних
ресурсів системи. Користувачі можуть мати різні ролі, які визначають їх
повноваження та обмеження при використанні функціоналу системи та її ресурсів;
– модель даних «профіль», яка пов'язана з моделлю користувача і містить
дані, що характеризують особистий профіль кожного користувача. Вона може
включати в себе інформацію про особисті налаштування, контакти, зображення
профілю та інші дані, які використовуються для персоналізації користувача в системі.
У даній системі користувачі можуть мати різні повноваження та рівні доступу
до різних частин системи, тому зв'язок між користувачами та ролями визначається як
багато-до-багатьох. Це означає, що один користувач може мати декілька ролей, і
навпаки, одна роль може бути призначена для декількох користувачів. Для
відображення цього зв'язку варто використати проміжну таблицю, яка буде зберігати
записи зв’язків користувачів та ролей.
Для кращого уявлення структури цих моделей та їх взаємозв'язків можна
скористатись ER-діаграмою (реляційною діаграмою сутностей-відносин). Ця
діаграма (Рис. 3.1) є графічним представленням структури даних та зв'язків між ними,
що полегшить подальше проєктування та реалізацію системи.
Рисунок 3.1 – ER-діаграма структури даних та зв'язків між ними
55
3.2.2 Реалізація системи безпеки
У контексті веб-сервісів забезпечення безпеки є однією з найважливіших задач.
Реалізація системи безпеки включає в себе заходи для захисту конфіденційності,
цілісності та доступності даних, а також автентифікацію та авторизацію користувачів.
Однією з найефективніших та найпопулярніших практик є використання
технологій JWT (JSON Web Token).
Дана система безпеки включає такі аспекти:
– автентифікація користувача: після того, як користувач надає свої облікові
дані для входу на сайт, сервер має перевірити ці дані на правильність та
актуальність;
– генерація токенів: при кожній авторизації новий JWT-токен повинен
згенеруватися та повернутися на клієнт;
– перевірка токенів: при кожному запиті, клієнт має додавати отриманий при
авторизації токен, щоб підтвердити серверу право на отримання доступу до
певного ресурсу.
– оновлення токенів: для підвищення безпеки та запобігання зловживанням,
встановлюється час життя для кожного JWT-токена. Після закінчення цього
терміну, користувачеві потрібно знову пройти процес аутентифікації та
отримати новий токен.
Реалізація системи безпеки з використанням JWT-токенів забезпечує високий
рівень захисту даних, зручність в управлінні авторизацією та автентифікацією
користувачів та дозволяє зберігати безпеку системи на високому рівні.
3.2.3 Робота з даними
Після визначення моделей даних та розробки системи безпеки, наступним
кроком є розробка механізму обробки запитів та передачі даних між клієнтом та
сервером.
Для цього визначимо елементи з яких буде складатись сервіс:
56
– клієнт: клієнтська частина програми, з якої користувачі взаємодіють з
системою. Клієнт відправляє запити на сервер та отримує відповіді,
відображаючи їх для користувача у зрозумілому форматі;
– сервер: серверна частина програми, яка обробляє запити від клієнта та
відповідає на них.
Серверну частину, в свою чергу, теж можна розділити на дві частини:
– система безпеки та обробки запитів: система, що відповідає за авторизацію
та автентифікацію користувачів, а також за обробку та маршрутизацію
запитів, що надходять від клієнта;
– обчислювач: частина, що відповідає за виконання обрахунків. Обчислювач
отримує дані від системи обробки запитів, виконує всі необхідні обрахунки
та повертає оформлені результати назад до системи обробки запитів для
подальшої передачі клієнту та відображення користувачу.
Ця архітектура дозволяє ефективно обробляти запити користувачів,
забезпечуючи високу продуктивність та безпеку даних. Розділення на клієнтську та
серверну частини дозволяє забезпечити чітку структуру та підтримувати
розширюваність системи, а розділення серверної частини на систему безпеки та
обробки запитів і обчислювач покращить модульність та масштабованість сервісу, а
також забезпечить можливість покращення та оптимізації роботи кожного
компонента окремо.
3.3 Засоби розробки
3.3.1 Вибір мов програмування та фреймворків
При виборі мов програмування та фреймворків для розробки веб-сервісу для
розв'язування оптимізаційних задач варто врахувати кілька ключових критеріїв.
Оскільки проєкт передбачає створення веб-орієнтованого ресурсу зі складним
функціоналом та великою кількістю взаємодій, обрані мови програмування та
фреймворки повинні забезпечити високу продуктивність, ефективність та
масштабованість системи.
57
У зв'язку з цим, для розробки серверної частини, яка відповідає за систему
безпеки та обробку запитів, було обрано мову програмування Java разом з
фреймворком Spring. Java є потужною мовою програмування з великою кількістю
готових бібліотек та рішень для різних завдань. Фреймворк Spring, у свою чергу,
забезпечує швидку розробку, інтеграцію з іншими технологіями, а також підтримку
високого рівня безпеки та стабільності системи.
Однак, для виконання обчислень та обробки складних оптимізаційних задач був
створений окремий обчислювач на мові програмування Python з використанням
фреймворку FastApi. Python є потужною та динамічною мовою, яка має велику
кількість бібліотек для наукових обчислень та обробки даних. FastApi, з свого боку,
надає швидкий та ефективний спосіб створення веб-сервісів на Python, забезпечуючи
високу продуктивність та зручний API для взаємодії з іншими компонентами
системи.
Оскільки для ефективної роботи сервісу необхідно зберігати та оперативно
обробляти великий обсяг даних, в якості бази даних використана база даних
PostgreSQL. PostgreSQL є потужною та надійною реляційною базою даних, яка
забезпечить ефективне зберігання та операції з даними.
Для розробки інтерфейсу та клієнтської частини було обрано фреймворк
Angular, написаний на мові програмування TypeScript. TypeScript надає можливість
розробляти масштабовані та підтримувані застосунки з мінімальними помилками,
завдяки типізації та іншим сучасним функціям. Angular, у свою чергу, забезпечує
швидку розробку інтерфейсу користувача, масштабованість та ефективне управління
станами сервісу.
Засоби розробки сервісу та зв’язки між ними зображено на рисунку 3.2.
58
Рисунок 3.2 – Засоби розробки та зв’язки між ними
3.3.2 Використання сторонніх бібліотек та інструментів
Під час розробки веб-сервісу для розв'язування оптимізаційних задач
використані різноманітні сторонні бібліотеки та інструменти для полегшення процесу
розробки та забезпечення високої якості коду та функціональності продукту.
Для серверної частини на Java з фреймворком Spring використані наступні
бібліотеки та інструменти:
– OpenAPI – використовується для автоматичної генерації документації API
та забезпечення відповідності стандартам OpenAPI Specification;
– Flyway – використовується для керування версіями бази даних та
автоматизації процесу міграцій;
– Lombok – дозволяє скоротити кількість шаблонного коду та автоматизувати
його генерацію;
– Jakarta Validation – використовується для валідації вхідних даних та
форматування помилок.
В частині обчислювача, що написаний на Python, використані наступні
бібліотеки:
59
– NumPy – бібліотека для роботи з масивами даних та виконання складних
математичних обчислень;
– Matplotlib – бібліотека для візуалізації результатів оптимізаційних
алгоритмів та аналізу даних.
На клієнтській стороні, розробленій з використанням фреймворку Angular,
використані наступні сторонні бібліотеки та інструменти:
– Angular Material – бібліотека готових компонентів та стилів для швидкого
створення стильних та функціональних інтерфейсів;
– NgRx – бібліотека для полегшення управління станом сервісу та
впровадження принципів реактивного програмування.
Використання цих бібліотек та інструментів значно полегшило процес
розробки, забезпечило високу якість та продуктивність програмного забезпечення та
дозволяє ефективно виконувати поставлені завдання.
3.3.3 Засоби для тестування та валідації
Під час розробки веб-сервісу використані різноманітні засоби для тестування та
валідації як серверної, так і клієнтської частин програмного забезпечення.
У серверній частині, використані наступні засоби для тестування та валідації:
– Postman [34] – засіб для автоматизованого тестування та валідації API
шляхом відправлення запитів і отримання відповідей на них;
– Testcontainers [35] – фреймворк для запуску Docker-контейнерів для тестів,
що дозволяє виконувати тестування бази даних навіть без її встановлення
на комп’ютер;
– REST Assured [36] – бібліотека для написання та виконання автоматизованих
тестів REST API;
– Mockito [37] – фреймворк для створення штучних програмних об'єктів та
управління їхньою поведінкою під час тестування.
У клієнтській частині, розробленій з використанням Angular, використано
Karma для виконання автоматизованих тестів JavaScript коду в середовищі браузера.
60
Використання цих засобів для тестування та валідації допоможе забезпечити
високу якість програмного забезпечення, виявити та усунути помилки та недоліки ще
на стадії розробки, а також підтримувати стабільну та надійну роботу системи у
продуктивному середовищі.
Паралельно з автоматизованим тестуванням бібліотеку Python для чисельних
методів оптимізації також буде протестовано на реальних оптимізаційних задачах
шляхом ручного тестування. Цей процес включатиме запуск бібліотеки на
конкретних прикладах оптимізаційних задач і перевірку результатів в порівнянні з
очікуваними значеннями. Ручне тестування дозволить виявити недоліки та помилки
реалізації методів оптимізації, а також забезпечить перевірку роботи бібліотеки в
реальних умовах експлуатації.
3.4 Синтаксичний аналізатор формул
Для забезпечення правильної обробки математичних виразів та можливості
введення власних формул у сервісі розроблено власний синтаксичний аналізатор. Цей
інструмент відповідає за розбиття введених математичних функцій на окремі операції
та послідовне їх виконання.
3.4.1 Функціональні можливості аналізатора
Синтаксичний аналізатор формул, реалізований на мові програмування Python,
надає ряд наступних функціональних можливостей для зручного та ефективного
оброблення математичних виразів:
– розбиття формул на складові частини: аналізатор розбиває вхідні
математичні формули на окремі складові, що полегшує подальший їх аналіз
та обробку;
– визначення використовуваних змінних: аналізатор автоматично визначає всі
використані змінні в формулі, що дозволяє користувачам працювати з
довільною кількістю змінних у вхідних виразах;
61
– підтримка функцій суми та добутку для багатовимірних задач: аналізатор
обробляє вирази, які містять функції суми та добутку для багатовимірних
задач, що розширює можливості введення складних математичних формул;
– коректне обчислення виразів з урахуванням змінних та функцій: аналізатор
забезпечує коректне виконання обчислень з урахуванням всіх вказаних
змінних, використаних функцій та послідовності їх виконання.
Ці функціональні можливості дозволяють користувачам вводити власні складні
математичні формули та виконувати їх обчислення з високою точністю та
ефективністю.
3.4.2 Алгоритм обробки та інтерпретації формул
Розглянемо основний алгоритм, який використаний для обробки та
інтерпретації формул в синтаксичному аналізаторі:
– аналіз формули: першим кроком є аналіз формули, який полягає у виявленні
та інтерпретації математичних виразів та змінних. Для цього використано
вбудований в Python модуль ast, який дозволяє розбирати вирази у вигляді
дерева синтаксичного аналізу, що дозволяє отримати деталізовану
інформацію про структуру та компоненти формули;
– підготовка до обчислень: після аналізу формули, потрібно підготувати її до
обчислень. Для цього потрібно звести формулу до вигляду, який буде
відповідати формату вбудованих функцій мови програмування Python;
– розбиття формул на складові: формули розбиваються на складові частини,
такі як окремі вирази, оператори, змінні та функції. Це дозволяє проводити
подальший аналіз та обробку кожної частини окремо;
– виконання формули: після розбиття формули на складові частини, вони
виконуються в правильній послідовності, шляхом підстановки замість
математичних виразів та змінних вже визначені числові значення;
– повернення результату обчислень: після виконання обчислень, результат
повертається для подальшого використання.
62
Цей алгоритм дозволяє аналізувати та обробляти складні формули, включаючи
функції, змінні та оператори, інтерпретуючи їх у формат, зрозумілому мові
програмування Python. Такий підхід дозволяє ефективно виконувати обчислення та
аналізувати дані у великих обсягах.
3.4.3 Методи валідації та перевірки формул
У зв'язку з тим, що формула, введена користувачем, виконується як Python-код,
важливо забезпечити безпеку та надійність системи шляхом валідації та перевірки
введених формул. Для цього використовуються наступні засоби:
– обмеження доступу до системних ресурсів: забезпечення обмеженого
доступу середовища виконання обрахунків до системних ресурсів
допомагає зменшити ризик критичних вразливостей;
– очищення введених даних: фільтрація та очищення введених користувачем
даних від потенційно небезпечних конструкцій та символів, які можуть
вплинути на безпеку системи;
– використання безпечних обчислень: застосування методів обчислень та
перевірка результатів на відповідність очікуваним значенням для
запобігання непередбаченим поведінкам системи;
– тестування на наборі тестових даних: проведення тестування та перевірки
роботи системи на різних наборах тестових даних для виявлення та
виправлення можливих проблем та вразливостей.
Таки підхід допомагає забезпечити безпеку та надійність системи, уникнувши
можливих загроз та забезпечивши стабільну роботу системи у всіх сценаріях
використання.
Висновки до розділу 3
У даному розділі ретельно проаналізовані вимоги до веб-орієнтованого сервісу,
включаючи функціональні вимоги та вимоги до ефективності та швидкодії. Це надало
змогу зрозуміти потреби користувачів та визначити основні критерії успішної
реалізації сервісу.
63
Структура веб-орієнтованого сервісу розроблена з урахуванням моделей даних
та їх взаємозв'язків, реалізації системи безпеки та обробки даних. Це забезпечує чітку
організацію та ефективне управління інформацією у сервісі.
Визначено засоби розробки, включаючи мови програмування, фреймворки,
сторонні бібліотеки, інструменти, а також засоби для тестування та валідації, які були
обрані з урахуванням потреб проєкту.
У розділі представлено синтаксичний аналізатор формул та його функціональні
можливості, алгоритм обробки та інтерпретації формул, а також методи валідації та
перевірки, що допоможуть в створенні потужного інструменту для розв’язання задач
оптимізації чисельними методами.
64
4 РОЗРОБКА ВЕБ-ОРІЄНТОВАНОГО СЕРВІСУ ДЛЯ РОЗВ’ЯЗУВАННЯ
ЗАДАЧ ОПТИМІЗАЦІЇ
Сучасні задачі оптимізації вимагають ефективних та зручних інструментів для
їх розв'язання. Розроблений веб-орієнтований сервіс для розв’язування задач
оптимізації чисельними методами поєднує в собі передові технології та методи, що
дозволяють користувачам швидко та ефективно вирішувати складні задачі
оптимізації та зручний інтерфейс для збільшення доступності даних задач для
широкого кола користувачів.
Серверна частина сервісу відповідає за обробку запитів, забезпечення безпеки
та виконання обчислень. Використання мови програмування Java з фреймворком
Spring та базою даних PostgreSQL дозволяє створити надійну та масштабовану
систему, а обчислювач, реалізований на Python з використанням FastAPI, забезпечує
швидке та ефективне виконання обчислень.
Клієнтська частина сервісу, реалізована на фреймворку Angular, забезпечує
зручний та інтуїтивно зрозумілий інтерфейс для користувачів. Вона включає форми
для введення даних, візуалізацію результатів та інтерактивні елементи для взаємодії
з користувачем. Важливою складовою є також валідація введених даних та
забезпечення безперебійної взаємодії з серверною частиною через REST API.
В сукупності ці компоненти забезпечують комплексний підхід до розв’язання
задач оптимізації, надаючи користувачам інтуїтивно зрозумілий інтерфейс та потужні
інструменти для обробки й аналізу даних.
4.1 Серверна частина веб-орієнтованого сервісу для розв’язування задач
оптимізації
Як було визначено при побудові структури сервісу, серверна частина веб-
орієнтованого сервісу для розв’язування задач оптимізації складається з кількох
основних компонентів, кожен з яких виконує певну роль в загальній архітектурі
системи:
– система обробки запитів: цей компонент відповідає за правильну обробку
вхідних запитів та передачу їх в необхідному напрямку;
65
– система безпеки: цей компонент відповідає за автентифікацію і
авторизацію, а також безпеку даних користувачів;
– обчислювач: цей компонент відповідає за розв’язання задач оптимізації, а
також структурування та оформлення результату;
– база даних: цей компонент відповідає за зберігання та управління даними,
необхідними для функціонування системи.
REST API виступає як точка входу для вхідних запитів і направляє їх до системи
обробки запитів, яка передає їх до системи безпеки. Система безпеки перевіряє
аутентифікацію та авторизацію, звіряючи дані отримані від клієнта та з даними, що
зберігаються в базі даних, після чого до системи обробки запитів повертається
відповідь з відмовою в доступі, або дозвіл на доступ до ресурсу. В випадку отримання
дозволу на виконання обрахунків, система обробки запитів пересилає дані на
обчислювач, який виконує всі необхідні обрахунки та повертає оформлені результати
назад для подальшої передачі клієнту та відображення користувачу (Рис. 4.1).
Рисунок 4.1 – Взаємодія компонентів серверної частини
Розглянемо роботу кожного компоненту серверної частини більш детально.
4.1.1 Система безпеки та обробки запитів
Для забезпечення безпеки, на мові Java з використанням фреймворку Spring,
було розроблено систему безпеку на основі технології JWT (JSON Web Token). Вона
базується на використанні підписаних токенів, які містять інформацію про
користувача та його права доступу.
Реалізація такої системи безпеки включає наступні кроки:
66
– реєстрація користувача: при першому вході користувач надає свої облікові
дані, які будуть використані в майбутньому для входу на сайт. Ці дані
перевіряються на правильність та у випадку успішної перевірки
зберігаються в базі даних;
– автентифікація користувача: якщо користувач зареєстрований, то він в
будь-який момент може виконати авторизацію. Для цього йому потрібно
знову надати свої облікові дані для входу, які сервер перевіряє на
відповідність даним збереженим в базі. Якщо вони правильні, сервер
генерує Access-токен, який містить у собі інформацію про користувача та
його ролі в системі. Після цього даний токен надсилається клієнту, який
зберігає його в локальному сховищі користувача;
– оновлення токенів: для підвищення безпеки та запобігання зловживанням,
для кожного токена встановлюється час життя. Після закінчення цього
терміну, користувачеві потрібно знову пройти процес аутентифікації. Однак,
для зручності користувачів, також було додано Refresh-токен, що має
набагато довший термін дії та дозволяє непомітно для користувача
згенерувати новий Access-токен без повторного проходження
аутентифікації. На відміну від Access-токену, Refresh-токен зберігається в
базі даних, що дозволяє за необхідності видалити його, заборонивши
користувачу отримання нових Access-токенів;
– перевірка токенів: при кожному запиті, клієнт додає до запиту збережений
Access-токен, щоб підтвердити серверу право на отримання доступу до
певного ресурсу. В випадку якщо токен відсутній, не відповідає даним про
користувача, чи має закінчений термін дії, сервер поверне помилку
автентифікації та заборонить доступ до ресурсу. В випадку заборони з
причини закінчення терміну дії Access-токену, чи його відсутності, клієнт
спробує отримати новий, відправивши запит з Refresh-токеном, який буде
звірений з наявним у базі даних та у випадку успіху поверне необхідні дані
для оновлення права доступу до ресурсу (Рис. 4.2).
67
Рисунок 4.2 – Візуалізація роботи системи безпеки на основі JWT-токенів [38]
Для забезпечення роботи такої системи безпеки в базі даних створено окрему
таблицю для збереження Refresh-токенів, пов’язану з користувачем (Рис. 4.3), що
дозволяє легко та ефективно перевіряти їх валідність та видаляти їх коли користувач
виходить з системи, чи не зміг пройти автентифікацію. Основний текст програми
системи безпеки можна переглянути в додатку В.1.1.1.
Рисунок 4.3 – Зв’язок сутності Refresh-токену та користувача
68
Реалізація системи безпеки з використанням пари Access- та Refresh-токену
забезпечує безпеку даних користувачів навіть у випадку викрадення даних для
авторизації та автентифікації і зручне керування їх правами доступу.
4.1.2 Обчислювач
Окремо від основного компоненту на Java було додатково розроблено
обчислювач з власним обробником запитів з використанням мови програмування
Python та фреймворку FastAPI.
Завдяки своїй простоті та швидкодії фреймворк FastAPI не створює
додаткового навантаження на сервер. У ньому не було розроблено жодних систем
безпеки, авторизації та автентифікації, тому що він може бути викликаний тільки з
компоненту, який вже має систему безпеки і розробка додаткового рівня безпеки була
б непотрібним збільшенням навантаження на сервер, що могло відобразитись на
швидкодії виконання обчислень.
Такий підхід дозволяє легко масштабувати серверну частину та навіть винести
обчислювач на окремий сервер з власними ресурсами для виконання обчислень.
У свою чергу обчислювач складається з наступних компонентів:
– бібліотека методів оптимізації: алгоритми всіх методів оптимізації
реалізовані в вигляді окремих файлів бібліотеки з власним інтерфейсом
виклику, в якому задано які вхідні параметри приймає метод та в якому
вигляді будуть повернені результати;
– інструменти бібліотеки методів оптимізації: окрім файлів з алгоритмами
виконання методів, до бібліотеки входять інструменти валідації вхідних
даних та виконання обчислень. Для виконання обрахунку значень функції,
методи оптимізації викликають спеціальний аналізатор, передаючи в нього
функцію у вигляді рядка, розмірність задачі та масив значень координат
точки, для якої виконується обрахунок значення функції. Цей аналізатор
розбиває функцію на складові, після чого виконує обрахунки кожної
складової та об’єднує їх в один результат, який повертається в вигляді
числового значення. Оскільки цільова функція передається у вигляді рядка
69
та виконується як Python-код, до аналізатору також входить валідатор
цільової функції, який перевіряє функцію на наявність небезпечних
викликів та ключових слів, які можуть бути використані для отримання
доступу до внутрішніх ресурсів серверу обчислень, чи призвести до його
поломки, а також на наявність синтаксичних помилок, які можуть зламати
хід виконання обрахунків. Валідація викликається при завантаженні методу
оптимізації до виконання будь-яких обчислень і тільки після успішної
перевірки функції, аналізатор надає доступ до виконання обрахунків. Текст
програми обчислювача можна переглянути в додатку В.1.2.1;
– обробник запитів: при отриманні вхідного запиту через REST API, цей
компонент знаходить в бібліотеці методів оптимізації потрібний метод та
перенаправляє в нього отримані дані для виконання обчислень. На
виконання обчислень накладається обмеження по часу та використання
ресурсів, що не дозволяє завантажити сервер занадто складною задачею,
заблокувавши виконання обрахунків для інших користувачів. У випадку
перевищення цих обмежень сервер зупинить виконання обрахунків та
поверне помилку з описом причин. Основний текст програми обробника
запитів можна переглянути в додатку В.1.2.2.
Модульна система побудови обчислювача дозволяє додавати нові методи
оптимізації лише створивши файл з основним алгоритмом його роботи та
підключивши до нього інструменти валідації та обрахунку значень цільової функції,
що спрощує подальшу підтримку та розширення сервісу та гарантує його
масштабованість.
Загалом, така структура (Рис. 4.4) дозволяє забезпечити високу продуктивність
та масштабованість обчислень, а також гарантує безпеку та цілісність виконання
задач оптимізації.
Рисунок 4.4 – Взаємодія компонентів обчислювача
70
Також, для кожного методу оптимізації існує файл автономного варіанту, що
надає можливість виконувати обчислення в середовищі Python у режимі діалогу,
незалежно від веб-орієнтованого сервісу (Рис. 4.5).
Рисунок 4.5 – Приклад використання автономних файлів методів оптимізації
Ці автономні файли використовують бібліотеку Matplotlib для створення
інтерактивної графіки, що сприяє зручному аналізу алгоритмів роботи методів
оптимізації (Рис 4.6).
Такий підхід відкриває користувачам широкі можливості для вивчення та
розуміння роботи різноманітних методів оптимізації. Користувачі можуть
аналізувати алгоритми, експериментувати з ними та створювати власні адаптації з
метою оптимізації їхнього функціонування під конкретні вимоги та умови. Це сприяє
глибшому розумінню та вдосконаленню методів оптимізації, а також стимулює
інноваційний процес у галузі чисельних методів оптимізації.
71
Рисунок 4.6 – Приклад графіки автономних файлів методів оптимізації
Більш того, такий доступ до автономних файлів дозволяє користувачам
експериментувати з алгоритмами і здійснювати їхнє налаштування під індивідуальні
потреби. Це створює сприятливе середовище для колаборативного дослідження та
спільного вдосконалення методів оптимізації, що може в результаті призвести до
нових відкриттів та покращень у цій сфері.
4.2 Клієнтська частина веб-орієнтованого сервісу для розв’язування
задач оптимізації
Клієнтська частина веб-орієнтованого сервісу для розв’язування задач
оптимізації розроблена за допомогою фреймворку Angular, що забезпечує високу
продуктивність, модульність та масштабованість сервісу. Використання NgRx для
управління станом сервісу дозволяє зручно керувати складними станами,
забезпечуючи чистоту коду та легкість тестування.
Основна архітектура клієнтської частини складається з наступних елементів:
– Components – основні будівельні блоки інтерфейсу користувача. Кожен
компонент відповідає за відображення певної частини інтерфейсу та має
свою логіку для управління даними;
– Effects – використовуються для обробки побічних ефектів, таких як
асинхронні запити до серверу, що дозволяє зберегти логіку компонентів
чистою та зручною для тестування;
– Actions – дії, які описують зміни в стані сервісу, що ініціюються
користувачем або системою і передаються в функції для обробки;
72
– Reducers – функції, які приймають поточний стан сервісу та дію (Action), і
повертають новий стан. Це забезпечує передбачуваність змін стану та
полегшує тестування;
– Selectors – використовуються для отримання частин стану з NgRx Store, що
дозволяє компонентам підписуватися на зміни в стані сервісу.
На даний момент клієнтська частина має декілька основних сторінок:
– сторінка реєстрації: сторінка для створення нового облікового запису
користувача (Рис. 4.7);
Рисунок 4.7 – Сторінка реєстрації
– сторінка логіну: сторінка для входу в систему (Рис. 4.8);
Рисунок 4.8 – Сторінка логіну
73
– сторінка обчислювача: сторінка вибору методу оптимізації (Рис. 4.9),
введення даних задачі оптимізації та отримання результатів.
Рисунок 4.9 – Сторінка обчислювача на етапі вибору методу оптимізації
При першому вході в сервіс, користувач має зареєструватись, ввівши свої дані
в спеціальну форму на сторінці реєстрації, після чого вони перевіряться на
правильність введення та будуть відправлені на сервер для створення облікового
запису, який дозволить йому використовувати ресурси серверу для розв’язання задач
оптимізації. В випадку введення даних, які не відповідають потрібним вимогам,
користувач отримає повідомлення з помилкою біля відповідних полів (Рис. 4.10).
Рисунок 4.10 – Відображення помилки введення даних при реєстрації
74
Після успішної реєстрації користувач може ввійти в свій обліковий запис на
сторінці логіну, ввівши в спеціальну форму свої облікові дані, які відправляться на
сервері для перевірки на відповідність збереженим в базі даних. При успішній
автентифікації користувач отримує доступ до сервісу, а якщо автентифікація невдала,
то користувач отримує повідомлення з причиною відмови в доступі (Рис. 4.11);
Рисунок 4.11 – Відображення помилки автентифікації
Оскільки у різних методів можуть бути різні вхідні параметри, дані результатів
обчислень, а також особливі умови використання деяких параметрів, було вирішено
створити генератор сторінки розв’язку, який буде динамічно створювати сторінку
введення даних та виведення результату.
Для цього було створено JSON-документ, який зберігається всередині
бібліотеки методів оптимізації в обчислювачі та має інформацію про кожен наявний
в бібліотеці метод. Цей документ містить інформацію про кожен метод оптимізації та
його поля введення, включаючи таку інформацію, як його назва, тип даних,
обмеження, чи є поле обов'язковим, від якого іншого поля може залежати його
відображення, чи має стандартні значення тощо. Основний текст програми генерації
сторінки введення даних можна переглянути в додатку В.2.1-В.2.3.
Такий підхід дозволяє динамічно формувати інтерфейс введення даних для
кожного методу оптимізації (Рис. 4.12), постійно підтримуючи актуальність даних
відносно бібліотеки методів оптимізації.
75
Рисунок 4.12 – Згенерована сторінка введення даних для класичного методу рою
частинок розв’язання глобальної задачі оптимізації
Після успішного введення даних та натиснення кнопки підтвердження, дані
будуть відправлені на серверну частину, який їх обробить на поверне результат
обчислень. Оскільки кожен метод сам визначає, які дані він повертає, результат теж
генерується динамічно. Для цього в кожному методі оптимізації прописано дані для
генерації сторінки, такі як назви полів, їх значення, правила відображення цих полів,
повідомлення з причиною зупинки методу та покроковий запис всього ітераційного
76
процесу обрахунків. Ці дані виводяться на сторінці після форми введення за власними
правилами (Рис. 4.13), а на основі запису всього ітераційного процесу для деяких
задач будуються графіки для візуального відображення пошуку оптимального
рішення (Рис. 4.14).
Рисунок 4.13 – Виведення результату обрахунків
77
Рисунок 4.14 – Виведення графіків результату обрахунків
Висновки до розділу 4
У даному розділі було описано процес розробки веб-орієнтованого сервісу для
розв’язування задач оптимізації. Було визначено основні компоненти архітектури
78
системи, а також описано компоненти з яких складаються серверна та клієнтська
частини розробленого сервісу. Було описано основні алгоритми роботи кожного
компоненту та продемонстровано роботу всього сервісу в цілому.
Особлива увага була приділена створенню динамічного інтерфейсу для
введення даних та виведення результатів. Було розроблено генератор сторінки
розв’язку, який динамічно створює форму введення даних на основі JSON-документу,
що зберігається всередині бібліотеки методів оптимізації. Це дозволяє підтримувати
актуальність інтерфейсу відносно методів, наявних у бібліотеці, і забезпечує
гнучкість у роботі з різними задачами оптимізації.
У результаті проведеної роботи було створено веб-орієнтований сервіс, що
дозволяє користувачам реєструватися, входити в систему та розв'язувати задачі
оптимізації за допомогою різних чисельних методів. Використання сучасних
технологій та підходів забезпечує зручність, надійність та ефективність роботи
сервісу, що сприяє підвищенню якості та швидкості вирішення задач оптимізації.
79
ВИСНОВКИ
У даній кваліфікаційній роботі було здійснено аналіз актуальності та
значущості веб-орієнтованих сервісів для розв’язання задач оптимізації чисельними
методами. Зазначено, що у сучасному світі, де швидкість та ефективність процесів
мають вирішальне значення для успіху, чисельні методи оптимізації набувають все
більшої актуальності. Використання таких методів стає критично важливим у різних
галузях, від логістики та машинобудування до енергетики та управління ресурсами.
Дослідження також вказує на важливість інтеграції чисельних методів
оптимізації у веб-орієнтовані сервіси, що робить передові технології доступними для
широкого кола користувачів та сприяє технологічному прогресу. Особливу увагу
приділено розвитку гібридних методів, поєднанню класичних алгоритмів з методами
машинного навчання, а також активному розвитку хмарних обчислень.
З метою розв’язання задач оптимізації та полегшення їх вирішення, в цій роботі
було сформульовано завдання та виконано аналіз популярних веб-орієнтованих
сервісів, розглянуто характеристики основних чисельних методів оптимізації,
розроблено архітектуру веб-орієнтованого сервісу, представлено його реалізацію та
тестування. Результатом роботи є створення зручного та потужного інструменту,
який дозволяє ефективно розв’язувати різноманітні задачі оптимізації та буде
сприяти подальшому розвитку в цій області.
Впровадження таких сервісів сприяє розвитку передових технологій та підходів
до розв’язування задач оптимізації. Це може призвести до появи нових стратегій та
підходів у вирішенні екстремальних задач, що дозволить оптимізувати процеси
управління в різних сферах діяльності людини, що, в свою чергу, дозволить
підприємствам отримати конкурентну перевагу на ринку.
Веб-орієнтований сервіс розв’язування задач оптимізації чисельними методами
буде корисним як при вивченні методів оптимізації у межах відповідних дисциплін
для студентів математичних і комп’ютерних спеціальностей, а також для проведення
чисельних експериментів з дослідження ефективності різних чисельних методів
оптимізації, що використовуються, наприклад, у машинному навчання.
80
СПИСОК ВИКОРИСТАНИХ ДЖЕРЕЛ
1. El-sayed. M. El-Kenawy et al., Novel Meta-Heuristic Algorithm for Feature
Selection, Unconstrained Functions and Engineering Problems. IEEE Access, 10, 40536-
40555, 2022.
2. S. Mirjalili, Dragonfly algorithm: a new meta-heuristic optimization technique for
solving single-objective, discrete, and multi-objective problems. Neural Comput. Appl.
27(4), 1053–1073, 2016.
3. F.A. Hashim, E.H. Hussain, K. Houssein, M.S. Mabrouk, W. Al-Atabany,
Archimedes optimization algorithm: a new metaheuristic algorithm for solving optimization
problems. Appl Intell., 2020.
4. El-sayed. M. El-Kenawy et al., Novel Meta-Heuristic Algorithm for Feature
Selection, Unconstrained Functions and Engineering Problems. IEEE Access, 10, 40536-
40555, 2022.
5. He, Y., Li, H., & Ye, D., A hybrid cuckoo search algorithm for model predictive
control of a two-wheeled inverted pendulum robot. Applied Mathematics and Computation,
408, 126732, 2021.
6. Zhang, X., Li, Y., & Zhang, Y., Deep learning-based feature selection with genetic
algorithm for high-dimensional data classification. Neurocomputing, 433, 312-321, 2021.
7. E.H. Houssein, Y. Mina, E. Aboul. (2019). Nature-inspired algorithms: a
comprehensive review in Hybrid Computational Intelligence: Research and Applications.
CRC Press, New York.
8. Kumar, S., & Singh, K., A novel hybrid algorithm for wind turbine design
optimization. Journal of Cleaner Production, 312, 127796, 2021.
9. Li, T., Wang, X., & Chen, Y., A multi-objective optimization approach for distillation
column design based on improved MOEA/D. Journal of Cleaner Production, 288, 125695,
2021.
10. Liu, H., Chu, C., & Zhang, X., A hybrid artificial bee colony algorithm for multi-
objective optimization of a milling process. International Journal of Advanced
Manufacturing Technology, 116(9-10), 2977-2989, 2021.
81
11. Y. T. Juang, S. L. Tung, H. C. Chiu. Adaptive fuzzy particle swarm optimization for
global optimization of multimodal functions. Information Sciences, vol. 181, 4539–4549,
2011.
12. Jixiong Zhang, Yanmei Xiong, Shungeng Min, A new hybrid filter/wrapper algorithm
for feature selection in classification. Analytica Chimica Acta, 1080, 43-54, 2019.
13. El-Sayed. M. El-Kenawy, M. M. Eid, M. Saber, A. Ibrahim, "MbGWO-SFS:
Modified Binary Grey Wolf Optimizer Based on Stochastic Fractal Search for Feature
Selection, IEEE Access, 8, 107635-107649, 2020.
14. Optimization Toolbox - MATLAB. URL:
https://www.mathworks.com/products/optimization.html (дата звернення: 28.05.2024).
15. GNU Octave. URL: https://octave.org (дата звернення: 28.05.2024).
16. OR-Tools. URL: https://developers.google.com/optimization (дата звернення:
28.05.2024).
17. Microsoft Azure: Cloud Computing Services. URL: https://azure.microsoft.com/en-
gb (дата звернення: 28.05.2024).
18. Wolfram|Alpha: Computational Intelligence. URL: https://www.wolframalpha.com
(дата звернення: 28.05.2024).
19. SciPy. URL: https://scipy.org (дата звернення: 28.05.2024).
20. Welcome to CVXPY 1.5 — CVXPY 1.5 documentation. URL:
https://www.cvxpy.org (дата звернення: 28.05.2024).
21. The Leader in Decision Intelligence Technology – Gurobi Optimization. URL:
https://www.gurobi.com (дата звернення: 28.05.2024).
22. Home · Optim. URL: https://julianlsolvers.github.io/Optim.jl/stable/ (дата
звернення: 28.05.2024).
23. AMPL Optimization: Empowering Businesses and Institutions. URL:
https://ampl.com (дата звернення: 28.05.2024).
24. Mosek ApS. URL: https://www.mosek.com (дата звернення: 28.05.2024).
25. Жалдак М. І., Триус Ю. В. Основи теорії і методів оптимізації : навчальний
посібник. – Черкаси : Брама-Україна, 2005. 608 c.
82
26. Fletcher R., Reeves C.M. Function minimization by conjugate gradients // Comp. J.,
7, 1964. P. 149-154.
27. Fletcher R., Powell M. J. D. A rapidly convergent descent method for minimization
// Comp. J., 6, 1963. P. 163-168.
28. J. Kennedy and R. C. Eberhart, “Particle swarm optimization,” in Proc. IEEE Int.
Conf. Neural Netw., Perth, Australia, 1995, vol. 4, pp. 1942–1948.
29. Yang, X. S. A New Metaheuristic Bat-Inspired Algorithm, in: Nature Inspired
Cooperative Strategies for Optimization (NISCO 2010), 2010, 65–74.
30. S. Yazdani, H. Nezamabadi-pour, and S. Kamyab, A Gravitational Search Algorithm
for Multimodal Optimization, Swarm and Evolutionary Computation, 2013, pp. 1–14.
31. S. Mirjalili, S.M. Mirjalili, A. Lewis, Grey Wolf Optimizer, Advances in Engineering
Softwhas, 2014, Vol. 69, pp. 46-61.
32. J. J. Liang, A. K. Qin, P. N. Suganthan, and S. Baskar, “Comprehensive learning
particle swarm optimizer for global optimization of multimodal functions,” IEEE Trans.
Evol. Comput., vol. 10, no. 3, pp. 281–295, Jun. 2006.
33. X. Yao, Y. Liu, and G. M. Lin, “Evolutionary programming made faster,” IEEE
Trans. Evol. Comput., vol. 3, no. 2, pp. 82–102, Jul. 1999.
34. Postman API Platform. URL: https://www.postman.com (дата звернення:
20.05.2024).
35. Testcontainers. URL: https://testcontainers.com (дата звернення: 20.05.2024).
36. REST Assured. URL: https://rest-assured.io (дата звернення: 20.05.2024).
37. Mockito framework site. URL: https://site.mockito.org (дата звернення:
20.05.2024).
38. Spring Boot Token based Authentication with Spring Security & JWT. URL:
https://www.bezkoder.com/spring-boot-jwt-authentication/ (дата звернення: 20.05.2024).