Харківський національний університет радіоелектроніки

Саад Алла Ібрагім

УДК 519.12.176

ПАРАЛЕЛЬНА РЕАЛІЗАЦІЯ ГЕНЕТИЧНИХ АЛГОРИТМІВ ДЛЯ ЗАДАЧ ТЕОРІЇ РОЗКЛАДІВ, ЗАДАНИХ НА ПЕРЕСТАНОВКАХ

01.05.02 – математичне моделювання та обчислювальні методи

Автореферат

дисертації на здобуття наукового ступеня

кандидата технічних наук

Харків – 2007

Дисертацією є рукопис.

Робота виконана в Житомирському державному технологічному університеті, Міністерства освіти і науки України.

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

Офіційні опоненти: доктор технічних наук, професор Ходаков Віктор Єгорович, Херсонський національний технічний університет, завідувач кафедри інформаційних технологій;

кандидат технічних наук, доцент Ребезюк Леонід Миколайович, Харківський національний університет радіоелектроніки, доцент кафедри системотехніки.

Провідна установа – Харківський національний університет ім. В.Н.Каразіна України (кафедра математичного моделювання та забезпечення ЕОМ) Міністерства освіти і науки.

Захист відбудеться „_26_” червня 2007 р. о _13-00_ годині на засіданні спеціалізованої вченої ради Д 64.052.02 Харківського національного університету радіоелектроніки за адресою: 61166, м. Харків, просп. Леніна, 14.

З дисертацією можна ознайомитись у бібліотеці Харківського національного університету радіоелектроніки, м. Харків, просп. Леніна, 14.

Автореферат розісланий „__24___” травня 2007 р.

Вчений секретар

спеціалізованої вченої ради Безкоровайний В.В.

ЗАГАЛЬНА ХАРАКТЕРИСТИКА РОБОТИ

Актуальність теми. Розв’язки багатьох задач теорії розкладів можливо надати у вигляді перестановок чисел від 1 до . Галузь їх практичного використання досить широка: календарне планування виробничих процесів, транспортні системи, побудова розкладів навчального процесу вищих навчальних закладів (ВНЗ).

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

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

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

Зв’язок роботи з науковими програмами, планами, темами. Дослідження виконувались у відповідності з координаційним планом Міністерства освіти і науки України за науковим напрямком „Технічна кібернетика” і в рамках держбюджетних тем: №0197U015183 „Розвиток математичних методів і алгоритмів скорочення перебору рішень в задачах створення інтелектуальних систем обробки інформації”, №0199U002692 „Моделювання послідовно-паралельних процесів функціонування технічних і виробничих систем на основі методів комбінаторної оптимізації і перспективних інформаційних технологій” на період з 2002 по 2004 роки. Здобувач брав участь у виконанні робіт за вище вказаними темами як виконавець.

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

Для досягнення поставленої мети потрібно вирішити такі завдання:–

систематизувати та проаналізувати теоретичні та практичні досягнення в дослідженні задач теорії розкладів, заданих на перестановках;

побудувати загальну математичну модель задач дослідження;

розробити методи розв’язання поставлених задач, що дозволяють отримувати розв’язки із заданою точністю;

на основі розроблених методів побудувати алгоритми складання розкладів та їх паралельні версії для реалізації на кластерних системах для збільшення швидкодії;–

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

Об'єкт дослідження – процеси упорядкування об’єктів в задачах складання розкладів, заданих на перестановках.

Предмет дослідження – точність та швидкодія методів складання розкладів із застосуванням кластерних систем.

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

Наукова новизна отриманих результатів.

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

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

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

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

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

На підставі запропонованих алгоритмів розроблені програми складання навчального розкладу на VisualFoxPro 8.0 під OS Windows та їхня паралельна реалізація під OS Linux. Проведено впровадження створеного програмного забезпечення в Житомирському державному технологічному університеті (ЖДТУ).

Результати досліджень і розробок використовуються в навчальному процесі у дисциплінах “Теорія розкладів і масового обслуговування” і “Теорія складності екстремальних задач”.

Особистий внесок здобувача. Усі наукові результати, що виносяться, на захист, одержані автором особисто. У роботах, що виконані у співавторстві, здобувачеві належать такі результати: у роботі [1] – генетичний алгоритм побудови розкладу виконання завдань для мультипроцесорних обчислювальних систем, у [2] – математична модель і генетичний алгоритм розв’язку задачі складання навчального розкладу, у роботі [3] – алгоритми побудови розкладів для конвеєрної і загальної задач, у [4] – паралельні версії алгоритмів та описано обчислювальний експеримент, що підтверджує ефективність розглянутих методів, у роботі [7] – загальна математична модель задач теорії розкладів, заданих на перестановках, та запропоновано метод отримання розв’язків із заданою точністю.

Апробація результатів дисертації. Основні результати дисертаційної роботи доповідалися та обговорювалися на конференціях і семінарах: Ш всеукраїнська конференція молодих вчених “Інформаційні технології в науці, освіті і техніці” (Черкаси, 2002 р.), ІV міжнародна науково-практична конференція “Современные информационные и электронные технологии” (Одеса, 2003 р.), II міжнародна науково-технічна конференція “Інформаційно-комп'ютерні технології 2004” (Житомир, 2004 р.), міжнародна наукова конференція „Інтелектуальні системи прийняття рішень і прикладні аспекти інформаційних технологій” (Євпаторія 2006 р.), VII міжнародна науково-практична конференція „Современные информационные и электронные технологии” (Одеса, 2006 р.).

Публікації. Результати досліджень опубліковані в 8 друкованих працях, з них 4 статті в наукових виданнях і збірниках наукових праць, що входить до переліків, затверджених ВАК України, 4 – у матеріалах і тезах конференцій.

Структура й обсяг роботи. Дисертація складається із вступу, чотирьох розділів, висновків, списку використаних джерел, що містить 112 найменувань на 11 сторінках, 4 додатки на 41 сторінці. Робота містить 111 сторінок основного тексту, 24 рисунки на 8 сторінках і 4 таблиці на 2 сторінках.

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

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

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

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

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

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

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

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

Нехай задана скінченна множина об’єктів довільного виду: пункти в системі транспортних сполучень, послідовності операцій технологічного процесу, перелік занять, які треба проводити у зазначений час, і т. п. Всі об’єкти пронумеровані числами від 1 до , . Розв’язком задачі на перестановках у просторі розв’язків є певна послідовність із об'єктів. Їй відповідає перестановка номерів об’єктів, у якій об’єкт з номером займає позицію . Множина характеризується набором параметрів , що містить припустимі набори даних , а також сукупністю умов у системі обмежень .

Для оцінки розвязку існує функціонал вартості , де – вартість розв’язку при заданому значенні параметра і системі обмежень .

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

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

Наприклад, для конвеєрної задачі теорії розкладів з кількістю машин розклад можливо подати однією перестановкою. Тоді функціонал цілі має вигляд:

, (1)

де порядковий номер обробки -ї деталі по перестановці на будь якій машині; час обробки -ї деталі на машині .

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

. (2)

Для опису конвеєрної задачі в загальному випадку однієї перестановки недостатньо. Розглянемо множину , елементами якої є – набори перестановок номерів деталей в порядку їх обробки на -й машині. Причому и . Тоді

. (3)

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

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

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

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

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

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

Для всіх задач побудови розкладів, заданих на перестановках, основні етапи методу, який пропонується, реалізовані у такий спосіб:

хромосоми в початковій популяції заповнюються випадковими перестановками чисел від 1 до ;

вибір хромосом для схрещування проводиться за методом “турнірного відбору”;

застосовується одномістне схрещування;

операція мутації є перестановкою двох випадково обраних елементів у хромосомі;

реалізується регенераційний тип репродукції поколінь із переносом кращої хромосоми з попереднього покоління до наступного;

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

У процесі роботи генетичного алгоритму найважливішою є постійна підтримка припустимості розв’язків, тобто підтримка хромосом такими, які не порушували б обов’язкових обмежень. На припустимість хромосоми може вплинути оператор схрещування. Тому після виконання цього оператора потрібно перевіряти новостворену хромосому на наявність порушень обов’язкових обмежень і з появою таких виконати процедуру виправлення хромосоми. У даній реалізації алгоритму пропонується така процедура з обчислювальною складністю не більш ніж . У роботі також пропонується інший підхід до підтримки припустимості розв’язків – непряме кодування хромосом. Кожен ген у хромосомах з непрямим кодуванням є відносним порядковим номером ще не встановленого об’єкта. Прямому поданню хромосоми (1,3,2,5,4) буде відповідати непряме (1,2,1,2,1) у фіксованому порядку (1,2,3,4,5). Застосування непрямих подань хромосом дозволяє уникнути неприпустимих розв’язків, але збільшує час на розрахунок функції придатності.

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

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

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

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

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

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

(4)

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

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

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

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

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

= ,

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

де

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

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

(5)

де значення глобального мінімуму; – наперед задане число.

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

Метод складається з такої послідовності кроків.

1. Формування початкових даних, 0 (номер рівня), завдання .

2. ; проведення розгалуження на -му рівні, формування нащадків.

3. Обчислення нижніх меж для кожного нащадка.

4. Обчислення верхніх меж для кожного нащадка генетичним алгоритмом, 0.

4.1., якщо , то перехід до п. 5.

4.2. Формування початкової популяції 0. Обчислення функції придатності.

4.2.1. , якщо то перехід до п. 4.3.

4.2.2. Турнірний відбір.

4.2.3. Схрещування.

4.2.4. Мутація.

4.2.5. Формування нової популяції, обчислення функцій придатності, перехід до пункту 4.2.1.

4.3. Визначення верхньої межі, перехід до п.4.1.

5. Обчислення =

6. Відсікання гілок. Якщо то вершина відкидається.

7. Перевірка умов завершення алгоритму. Якщо всі вершини розглянуті, то перехід до п. 8, інакше – вибір вершини для розгалуження з мінімальною верхньою оцінкою, перехід до п. 2.

8. Завершення алгоритму.

Генетичний алгоритм працює для кожної вершини в методі гілок та меж. Як верхня межа для кожної вершини вибирається найкращий розв’язок, отриманий генетичним алгоритмом. Для кожної вершини фіксуємо компонентів, і генетичний алгоритм фактично працює з компонентами (). Після закінчення роботи генетичного алгоритму зберігається тільки хромосома з найкращим значенням функціоналу цілі. Ця хромосома обов’язково передається в початкові популяції для одержання верхніх меж при подальшому розгалуженні. Таким чином, через те, що при переході від покоління до покоління точність розв’язку не збільшується, верхня оцінка для кожної наступної вершини може тільки покращитися (зменшитися). Генетичний алгоритм варто застосовувати тільки до розмірності 4 (2*3*4=24). Для такої розмірності досить згенерувати 23 хромосоми (перестановки ) без повторень, що дозволяє одержувати верхню оцінку, яка дорівнює оптимальному, для даної множини, значенню функції цілі.

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

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

варіант розподілення між процесорами оцінок для кожної хромосоми при роботі генетичного алгоритму на кожному кроці розгалуження;–

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

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

У роботі оцінено час розрахунку за кожним з варіантів. Порівняння часу обчислень зведено до аналізу наступного виразу:

,

де – кількість вершин -го рівня; – кількість хромосом в популяції;

– задана кількість процесорів для реалізації паралельної версії методу.

Якщо значення и кратні , то цей вираз дорівнює 0. Значення можливо призначити вільно. Виберемо кратним кількості процесорів. Значення змінюється в процесі роботи алгоритму. причому деякі рівні можуть бути вибрані для розгалуження декілька разів. Тому існують етапи розгалуження, для яких значення виразу

,

і час розрахунку за другім варіантом набагато перевищує час розрахунку за першим.

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

У результаті обчислювального експерименту були отримані такі найбільш прийнятні параметри генетичного алгоритму для методу гілок та меж: обсяг популяції – 10–20 хромосом, турнірний відбір – 3–5 хромосом, кількість поколінь – 10–20, ймовірність проведення схрещування – 0,9.

Мутація проводиться тільки для ( ). Ймовірність мутації варто збільшити до 0,1, тому що необхідно знайти - оптимальний розв’язок та необхідно досліджувати різні області.

Для розрахунку розкладу ВНЗ і проведення обчислювальних експериментів створено комплекс програм. Програми під ОС Windows написані на VisualFoxPro 8.0, а під Linux – мовою С.

Максимальний коефіцієнт прискорення досягається для задач великої розмірності. Для задач з довжиною хромосоми менш, ніж 20 ген, прискорення практично відсутнє.

Рис. 1. Залежність коефіцієнта прискорення від кількості процесорів для конвеєрної системи

Для конвеєрних систем максимальний коефіцієнт прискорення процесу на кластерній системі в порівнянні з однопроцесорним варіантом складає 2,6 на кластері з 6 процесорів (при використанні 5 дочірніх процесів). Подальше збільшення кількості процесорів приведе до збільшення коефіцієнта прискорення тільки для задач дуже великої розмірності. Для загальної задачі теорії розкладів на кластерній системі не вдалося одержати коефіцієнт прискорення більше одиниці. Її розв’язання запропонованим алгоритмом доцільно тільки для задач дуже великих розмірностей тому, що витрати на обмін даними між вузлами кластера настільки великі, що нівелюють виграш від паралельного обчислення функції цілі. Для розв’язання задач із довжиною хромосоми до 40 досить добре працює однопроцесорний варіант.

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

а). б).

Рис. 2 Залежність коефіцієнта прискорення від кількості процесів для а) конвеєрної системи з прямим кодуванням, б) конвеєрної системи з непрямим кодуванням

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

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

Рис.3. Залежність коефіцієнта прискорення від кількості процесорів для задачі складання навчального розкладу

Як контрольні приклади були обрані завдання з довжиною хромосом 1000, 2000, 4000 й 6000 ген.

а) б)

Рис.4. Залежність коефіцієнта прискорення від кількості процесів для задачі СРВНЗ а) з прямим кодуванням, б) з непрямим кодуванням

Оскільки у загальному випадку генетичні алгоритми дають наближені розв’язки, то зроблена спроба підібрати оптимальний набір параметрів алгоритму для одержання кращих результатів. Обчислювальний експеримент поставлено для всіх розглянутих задач. Для конвеєрної задачі розглядалися тестові завдання розмірами від 10*10 до 100*100, для загальної задачі теорії розкладів – завдання від 10*10 до 30*30 і для задачі складання навчального розкладу – завдання з кількістю трійок (предмет, група, викладач) від 1000 до 6000.

У процесі дослідження виявилося, що значення параметрів алгоритму практично не залежать від типу задачі. Були отримані такі значення оптимальних параметрів:–

кількість хромосом у популяції: 500;–

кількість кандидатів на турнірний відбір: від 2 до 5;–

ймовірність схрещування: близька до 1;–

ймовірність мутації хромосоми: від 0,001 до 0,05–

ймовірність мутації кожного гена: 0,05;–

кількість отриманих популяцій: 100.

Загальна кількість розглянутих рішень для кожного експерименту – 50000.

Четвертий розділ дисертації присвячений опису пакета програм побудови розкладу занять ВНЗ.

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

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

проведення не більше одного заняття одним викладачем одночасно;

неможливість проведення в одному приміщенні більше одного заняття одночасно;

неможливість проведення занять для викладача в заборонені часові інтервали;

проведення занять у спеціалізованих аудиторіях;

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

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

До числа неосновних вимог варто віднести небажаність „вікон” у груп студентів, проміжки часу між проведенням занять одним викладачем, проведення лекцій на початку і в середині навчального дня та інше. Звичайно, перелік цих вимог не претендує на повноту і може змінюватися з урахуванням специфіки ВНЗ.

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

За розробленою програмою було розраховано семестровий розклад Житомирського технологічного університету. Типовий приклад складався з наступного набору вихідних даних: кількість викладачів – 78, кількість предметів – 160, кількість груп – 102, кількість аудиторій – 74.

У результаті розподілу навантаження з урахуванням того, що лекційні заняття проводяться для декількох груп, отримано 6950 трійок (предмет, група, викладач).

Параметри генетичного алгоритму обрані такими: кількість хромосом у популяції – 200, кількість популяцій – 1000, коефіцієнт турнірного відбору – 3, штрафний коефіцієнт вікон для груп – 5, штрафний коефіцієнт вікон для викладачів – 1, штрафні коефіцієнти небажаності проведення занять (наприклад, лекцій) у певний час – від 1 до 5.

Початкова популяція формувалася випадковим способом. Для уточнення коефіцієнтів схрещування і мутації попередньо було розраховано близько 100 прикладів з невеликими наборами вихідних даних. У результаті отримано, що із зростанням коефіцієнта схрещування результати поліпшуються, а коефіцієнт мутації варто зменшувати. Найбільш сприятливими парами варто вважати коефіцієнт схрещування 0,96 – 0,99, а коефіцієнт мутації дорівнює 0,01 – 0,03.

Найменше значення штрафу в отриманому розкладі 277 одиниць. Час рахунку складає близько 6 годин, а в послідовному режимі більше 17. Причому обробка кожної популяції забирає не набагато більше 1 хв. Основний час при формуванні популяції забирає обчислення функцій придатності – близько 0,27 хв. для кожної хромосоми.

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

ВИСНОВКИ

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

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

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

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

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

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

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

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

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

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

АНОТАЦІЯ

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

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

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

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

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

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

АННОТАЦИЯ

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

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

Диссертация посвящена изучению моделей задач теории расписаний, заданных на перестановках, и развитию методов их оптимизации. Большое количество задач теории расписаний, на первый взгляд, не являются задачами, заданными на перестановках. В них для задания допустимого решения либо недостаточно одной перестановки, либо следует учитывать дополнительные ограничения. В этом случае перестановку можно рассматривать как начальный порядок элементов (объектов) решения, который используется для получения полного решения, удовлетворяющего всем ограничениям. Другими словами, нужно построить процедуру, которая по заданному начальному порядку определяла бы допустимое решение задачи. Например, такими задачами являются наиболее трудные задачи составления расписаний – конвейерная и общая задачи теории расписаний, задача составления расписания учебного заведения, задача коммивояжера и другие.

Для более точного решения поставленных задач в диссертационной работе предлагается приближённый метод, позволяющий получать решения с заданной точностью. Он разработан на совместном использовании алгоритма типа ветвей и границ и генетического алгоритма. Генетический алгоритм применяется для нахождения верхних оценок текущих решений и выбора направления в дереве перебора, которое строится по схеме ветвей и границ. В комбинации точного и приближенного методов оптимизации построенное решение предъявляется вместе с доказательством того, что его относительная погрешность не больше предварительно заданного числа .

Для увеличения быстродействия разработанного метода выполнена его реализация на параллельных (кластерных) системах.

В результате вычислительного эксперимента получены наиболее предпочтительные параметры генетического алгоритма для метода ветвей и границ.

Показано, что с уменьшением резко увеличивается количество вершин дерева ветвления: для =0,1 и =0 среднее количество вершин увеличивается примерно в 10 раз. Применение генетического алгоритма для расчёта верхних границ увеличивает время расчёта каждой вершины не более чем в 3 раза. Таким образом, можно сделать вывод о целесообразности применения -оптимальных алгоритмов для решения задач теории расписаний, заданных на перестановках.

Рассмотрено несколько вариантов предложенного метода. Показано,