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

Розвязки багатьох задач теорії розкладів можливо надати у вигляді перестановок чисел від 1 до . У цьому випадку перестановку можна розглядати як деякий початковий порядок елементів (обєктів), що використовується для отримання повного розвязку, який задовольняє всім обмеженням. Наприклад, такими задачами є найскладніші задачі теорії розкладів - конвеєрна і загальна задачі, задача побудови розкладу навчального закладу, задача комівояжера та інші. Для досягнення поставленої мети потрібно вирішити такі завдання: - систематизувати та проаналізувати теоретичні та практичні досягнення в дослідженні задач теорії розкладів, заданих на перестановках; У дисертаційній роботі використано: для проектування основних методів розвязання задач дослідження - загальні схеми генетичних алгоритмів та методу гілок та меж, методи комбінаторної оптимізації, для побудови паралельних версій алгоритмів - методи та засоби паралельного програмування, для отримання оцінок швидкодії алгоритмів - елементи теорії складності екстремальних задач.У другому розділі наведено математичну модель задачі складання розкладів на перестановках і методи її розвязання, які основані на використанні класичної схеми генетичних алгоритмів з оригінальними процедурами обчислення функцій придатності та виправлення неприпустимих хромосом. Глобально оптимальним розвязком задачі на перестановках для фіксованого значення параметра за обмежень будемо називати перестановку , таку, що для всіх у випадку мінімізації функціонала та у випадку його максимізації. Наприклад, для конвеєрної задачі теорії розкладів з кількістю машин розклад можливо подати однією перестановкою. Те ж саме можна сказати і для більш складних задач теорії розкладів, заданих на перестановках (наприклад, для загальної задачі теорії розкладів). Такий підхід дозволяє використати для розвязання цієї задачі схему класичного генетичного алгоритму з високою швидкодією і перенести всю складність розвязання на процедуру побудови розкладу та обчислення функції придатності для кожної хромосоми.Усі вимоги до розкладу можна розділити на основні і неосновні. Повне виконання всіх неосновних вимог до розкладу занять при обовязковому виконанні основних найчастіше виявляється практично неможливим. Виходячи з аналізу вимог, видається природним при побудові математичної моделі розкладу записати основні вимоги у вигляді обмежень задачі, а неосновні - звести в цільову функцію. Таким чином, задача побудови розкладу занять полягає в мінімізації дефекту якості, викликаного порушенням ряду неосновних вимог при повному виконанні основних вимог. Як основні вимоги можна виділити такі: - проведення не більше одного заняття одним викладачем одночасно;У дисертації наведені результати досліджень, які є подальшим розвитком розділу теорії розкладів, що присвячений розвязанню найбільш складних задач, заданих на перестановках, шляхом використанням - оптимального методу, який є комбінацією генетичного алгоритму та методу гілок та меж. Проведено аналіз існуючих методів розвязання задач теорії розкладів, заданих на перестановках, і обґрунтовано вибір математичного апарата для підвищення точності наближених розвязків. Побудовано математичну модель загальної задачі теорії розкладів, заданої на перестановках. Розроблено загальну схему генетичного алгоритму для розвязання задач теорії розкладів, заданих на перестановках, з урахуванням двох методів кодування хромосом. Проведено обчислювальний експеримент, в результаті якого встановлені оптимальні параметри генетичних алгоритмів, висока ефективність паралельних версій алгоритмів, прийнятний коефіцієнт прискорення для конвеєрної задачі і задачі побудови навчального розкладу на кластерних системах, недоцільність розвязання на кластерних системах загальної задачі теорії розкладів малої розмірності.

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

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

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

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

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

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

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

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

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

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

Розроблено пакет прикладних програм мовою С під ОС 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.

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