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