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

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

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

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

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

На підставі отриманих результатів створено пакет прикладних програм побудови навчального розкладу.

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

Основні результати роботи такі.

Проведено аналіз існуючих методів розв’язання задач теорії розкладів, заданих на перестановках, і обґрунтовано вибір математичного апарата для підвищення точності наближених розв’язків.

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

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

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

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

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

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

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

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

Розроблено пакет прикладних програм для складання навчальних розкладів на СКБД VisualFoxPro 8.0 під ОС Windows, пакет впроваджено в ЖДТУ.

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

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

1. Арєшкова В.В., Данильченко О.М., Ібрагім С.А. Застосування генетичних алгоритмів для розв’язання задач складання розкладів для мультипроцессорної послідовно-параллельної системи // Вісник Житомирського інженерно-технологічного інституту. – 2002. – № 2. – С. 76–80.

2. Данильченко О.М., Данильченко А.О., Ібрагім С.А. Застосування генетичних алгоритмів для побудови навчальних розкладів на кластерних системах // Вісник Житомирського інженерно-технологічного інституту. – 2003. – № 3. – С. 130–134.

3. Ібрагім С.А. Розв'язання задач теорії розкладів генетичними алгоритмами // Вісник Житомирського державного технологічного університету. – 2004. – № 2. – С. 180–185.

4. Данильченко О.М., Данильченко А.О., Ібрагім С.А. Розв'язання одного класу задач складання розкладів генетичними алгоритмами на кластерних системах // Вісник Житомирського державного технологічного університету. – 2004. – № 4. – С. 130–135.

5. Данильченко А.О., Ібрагім С.А. Організація обчислювального кластера ЖДТУ // Зб. наук. пр. за матеріалами ІІІ Всеукраїнської конф. молодих учених “Інформаційні технології в науці й техніці” (квітень 2002). – Черкаси: ЧДТУ, 2002. – С. 272–275.

6. Данильченко А.М., Данильченко А.А., Ибрагим С.А. Решение задач составления расписаний на кластерных системах // Тр. пятой междунар. науч.-практ. конф. “Современные информационные и электронные технологии” (май 2003). – Одесса: ДП «Нептун-Технология», 2003. – С. 147–149.

7. Данильченко А.М., Ибрагим С.А., Панишев А.В. Генетические алгоритмы в комбинации с методом ветвей и границ для решения задач о перестановках // Материалы междунар. научной конф. „Интеллектуальные системы принятия решений и прикладные аспекты информационных технологий”. – Евпатория, 2006. – Т.2. – С. 34–37.

8. Данильченко А.М., Данильченко А.А., Саад Алла Ибрагим -оптимальний алгоритм рішення задач, заданих на перестановках // Тр. седьмой междунар. науч.-практ. конф. “Современные информационные и электронные технологии” (май 2006). – Одесса: ДП «Нептун-Технология», 2006. – Т.1.– С. 31.