A Parallel Genetic Algorithm to Solve Scheduling the University Class Problem

This paper describes the development and implementation of a parallel genetic algorithm (GA) to solve scheduling the university class problem. The proposed GA is based on the "farmer-workers" model and uses a number of heuristics, e. g. classroom and time selection during populatio...

Повний опис

Збережено в:

Бібліографічні деталі
Дата:	2017
Автори:	Glybovets, M.M., Gulayeva, N.M., Pasichnyk, M.M.
Формат:	Стаття
Мова:	Українська
Опубліковано:	PROBLEMS IN PROGRAMMING 2017
Теми:	UDC 004.8
Онлайн доступ:	https://pp.isofts.kiev.ua/index.php/ojs1/article/view/140
Теги:	Додати тег Немає тегів, Будьте першим, хто поставить тег для цього запису!
Назва журналу:	Problems in programming
Завантажити файл:

Репозитарії

Problems in programming

_version_	1859501673035071488
author	Glybovets, M.M. Gulayeva, N.M. Pasichnyk, M.M.
author_facet	Glybovets, M.M. Gulayeva, N.M. Pasichnyk, M.M.
author_sort	Glybovets, M.M.
baseUrl_str	https://pp.isofts.kiev.ua/index.php/ojs1/oai
collection	OJS
datestamp_date	2018-07-18T20:55:57Z
description	This paper describes the development and implementation of a parallel genetic algorithm (GA) to solve scheduling the university class problem. The proposed GA is based on the "farmer-workers" model and uses a number of heuristics, e. g. classroom and time selection during population initialization, adding useful subsolutions into the initial population, using special (new) mutation operator. In the algorithm a specific chromosome coding and fitness function that takes into account a number of restrictions on the resulting schedule are proposed. Problem-specific crossover and mutation operators are developed. Based on a number of computational experiments optimal parameters of GA are proposed for further use.
first_indexed	2026-03-12T23:13:31Z
format	Article
fulltext	Прикладні засоби програмування та програмне забезпечення © М.М. Глибовець, Н.М. Гулаєва, М.М. Пасічник, 2015 76 ISSN 1727-4907. Проблеми програмування. 2015. № 2 УДК 004.8 М.М. Глибовець, Н.М. Гулаєва, М.М. Пасічник ПАРАЛЕЛЬНИЙ ГЕНЕТИЧНИЙ АЛГОРИТМ ПОБУДОВИ РОЗКЛАДУ ЗАНЯТЬ У роботі описана розробка та реалізація паралельного генетичного алгоритму (ГА) побудови розкладу ВНЗ на основі моделі «фермер-робітники» з елементами евристики для вибору аудиторій та пар під час ініціалізації, застосування нового (додаткового) оператора мутації, додання вдалих підрозв’язків в по- пуляцію під час інціалізації початкової популяції. У алгоритмі введено специфічний спосіб кодування хромосоми, запропоновано функцію оцінки хромосоми з урахуванням низки обмежень, що наклада- ються на результуючий розклад-хромосому, а також розроблено спеціальні оператори кросинговеру та мутації. На основі експериментів запропоновано оптимальні значення параметрів ГА. Вступ Розв’язання задачі побудови розк- ладу у загальній постановці є процесом виконання деякої фіксованої системи за- вдань за допомогою певної множини ресу- рсів чи обслуговуючих пристроїв [1]. За- дача складання розкладу занять формулю- ється так: «Для заданого набору навчаль- них аудиторій і заданого набору часових інтервалів (навчальних пар) побудувати такий розподіл навчальних занять для всіх об’єктів (вчителів і навчальних груп, ауди- торій тощо), для якого обраний критерій оптимальності є якнайкращим» [2]. Серед обмежень, які впливають на ефективність розкладу, виділимо необхідність переду- вання лекцій над практичними, лаборатор- ними та побажання викладачів щодо часу проведення занять. Зауважимо, що це ли- ше деякі з можливих вимог до вдалого ро- зкладу навчального закладу. Для розв’язання задачі побудови розкладу (ЗПР) виділяють [3] використан- ня методів: повного перебору, гілок та границь, імітації відпалу, логічного про- грамування з обмеженнями, розфарбуван- ня графу та інші. Враховуючи належність ЗПР до класу NP, прийнятною альтернати- вою її розв’язання є використання еволю- ційного підходу – генетичних алгоритмів (ГА) з акцентом на дослідження впливу різноманітних параметрів алгоритму на ефективність його роботи. Класична схема розробки ГА [4] в контексті ЗПР включає наступні етапи [5, 6]. На першому – розробляється струк- тура та представлення хромосоми, в якій буде зберігатися розв’язок. Обрана струк- тура має враховувати всі особливості, які висуваються до шуканого розкладу, а та- кож те, що від її вибору напряму залежить реалізація алгоритмів кросинговеру та му- тації. Потім створюється початкова попу- ляція, розмір якої залежить від розмірності задачі. Для організації оптимізаційного процесу необхідно створити напрямок ро- звитку популяції. Цим напрямком може виступати мінімізація цільової функції (функції пристосованості чи здоров’я). Ця функція має адекватно відрізняти два варі- анти розкладу. На основі значення оцінки хромосоми відбувається відбір хромосом у батьківський пул, подальше застосування операторів кросинговеру та мутації. Помі- стивши початкову популяцію у створене штучне середовище і реалізувавши проце- си селекції, кросинговеру і мутації, прихо- димо до ітераційного алгоритму пошуку оптимального розв’язку. Ми прагнутимемо побудувати та- кий розклад занять, за якого порушувати- меться якнайменша кількість заданих об- межень. У розпаралелюванні програмної реалізації запропонованого алгоритму використовувався потоковий підхід. Ана- ліз ефективності алгоритму проведено на основі низки експерементів з урахуванням загальноприйнятих критеріїв оцінювання ГА. Наукова новизна отриманих ре- зультатів полягає у запропонованій спе- Прикладні засоби програмування та програмне забезпечення 77 цифіці кодування та введених генетичних операторах і сформульована рекоменда- ціями щодо використання певних конфі- гурацій параметрів ГА. Задача побудови розкладу занять в НаУКМА Для уточнення постановки і розв’язання ЗПР занять оберемо навчаль- ний план факультету інформатики Наці- онального університету «Києво-Моги- лянська академія» (НаУКМА) з урахуван- ням специфіки навчального процесу уні- верситету. Тобто, необхідно побудувати оптимальний розклад занять для всіх кур- сів факультету інформатики (двох бакала- врських та чотирьох магістерських про- грам) з невеликою кількістю вільних ау- диторій (17 навчальних аудиторій) та п’ятиденним робочим тижнем з обмежен- ням у шість пар щодня. Особливістю уні- верситету є велика кількість вибіркових курсів вільного запису. Склад груп певно- го курсу буде залежати від кількості сту- дентів, які записалися на нього, тобто склад і розмір груп є змінним. До інших обмежень віднесемо забезпечення поба- жань викладачів, мінімізацію «вікон» у розкладі, врахування потреби спеціалізо- ваних аудиторій (комп’ютерних класів). Також доцільно, щоб лекції та практичні з одного предмету стояли поруч, і бажано, щоб лекційні заняття проводилися зранку. Перелічені специфіки обмежень ви- значають природність застосування ГА для розв’язання нашої задачі. Наприклад, на основі генетичного оператора мутації можна просто і адекватно реалізувати му- тацію складу груп. Кодування розв’язків. Для ГА пе- ршим важливим кроком є вибір способу кодування розв’язків, тобто представлен- ня хромосоми. Ми обрали представлення хромосом за допомогою цілочисельних значень генів з мультихромосомним ти- пом кодування – кодування трьома хро- мосомами. Першою виступає хромосома послідовності кодів груп, другою – хро- мосома послідовності кодів аудиторій, третьою – послідовності кодів пар (рис. 1). Один набір відповідних значень еле- ментів у всіх трьох списках відображати- ме один мультиген кінцевого розкладу певного курсу. Відповідно, елемент такої мультихромосоми можна представити трійкою «група», «аудиторія», «пара». Довжина мультихромосоми дорівнює кі- лькості груп, для яких будується розклад. За допомогою структурного елеме- нта «група» кодується наступна інформа- ція: «код групи» та «номер групи». Такій парі елементів ставиться у відповідність одне цілочислове значення. Сам код гру- пи інкапсулює у собі структурні одиниці «курс», «предмет», «тип заняття», «№ тижнів», «викладач», «тип групи», «роз- мір групи» та «склад групи». Елемент «курс» представляє навча- льний курс (рік навчання), для якого буду- ється розклад, а «предмет» – відповідний предмет, який вивчається цим курсом. Па- раметр «тип заняття» відповідає лекцій- ним чи практичним заняттям з предмету. Група Аудиторія Пара № пари Курс Предмет Тип заняття № тижнів Викладач Тип групи Розмір групи Склад групи День тижня № аудиторії ТипРозмір № групиКод групи Рис.1. Представлення мультигену мультихромосоми Прикладні засоби програмування та програмне забезпечення 78 В залежності від кількості годин, виділе- них предмету в навчальному плані, він проводиться в певні тижні семестру, за це відповідає структурний елемент «№ ти- жнів». Сам структурний елемент «викла- дач» поділяється на «ПІБ викладача» та «матрицю недоступності викладача», що відображатиме дні та пари, коли викладач не може проводити заняття. Елемент «тип групи» відповідає за те, проста це група чи зведена. Дане поле приймає зна- чення «тип 1», якщо група не належить до зведених груп, або «тип 2», якщо гру- па належить до зведених груп. Для остан- ніх відповідне заняття має проводитися в аудиторії, яка за розміром вміщає всі зве- дені групи. Параметр «розмір групи» є допо- міжним для реалізації обмеження макси- мальної кількості студентів в аудиторії та відповідіності розміру аудиторії розміру групи. Параметр «склад групи» потрібний для унеможливлення накладок розкладу для студента. У випадку лекційного за- няття з невибіркового предмету склад групи міститиме всіх студентів певного курсу, оскільки невибіркові курси мають вивчати всі студенти. На рис. 2 показано приклад представлення групи. Елемент «аудиторія» складається з елементів «номер аудиторії», «розмір аудиторії» та «тип аудиторії». «Номер аудиторії» представляє аудиторію з мно- жини можливих аудиторій, поле «розмір аудиторії» відображає розмір аудиторії, в якій будуть проводитися заняття. Поле «тип аудиторії» визначає тип даної ауди- торії, тобто чи вона лекційна, комп’ютерна, чи може використовуватися і для лекційних, і для практичних занять. Представлення аудиторії можна побачити на рис. 3. Відповідно об’єкт аудиторії ін- капсулює у собі зазначені структурні еле- менти. Структурний елемент «пара» міс- тить у собі наступні параметри: «номер пари» та «день тижня». Відповідно «но- мер пари» відображає номер пари в розк- ладі. Структурний елемент «день тижня» показує день проведення пари. На рис. 4 показано представлення пари. Особина кодується трьома хромо- сомами, де в першій хромосомі зберіга- ються гени всіх груп у певному порядку, в другій хромосомі зберігається список аудиторій, відповідних цим групам, а в третій хромосомі закодовані пари, які відповідають певним групам. Така струк- тура кодування була обрана для легкос- ті застосування операторів кросинговеру та мутацій над кожним списком (груп, аудиторій, пар) окремо. Адже викорис- тання класичних операторів кросинговеру комбінаторної опитимізації через перес- тановки генів одного спільного списку могло б суттєво порушити структуру хромосоми, тобто відповідність «група, аудиторія, пара». На рис. 5 показано цю структуру. ОКА 1 код групи № групи ПІ-1, ОКА, практ., 1-15 т., Петренко П., тип1, 10, Студент 1 Студент 2 ... Студент 10 Рис. 2. Представлення групи 1-223 80 лекційна Рис. 3. Представлення аудиторії ПН 1 пара Рис. 4. Представлення пари (заняття) Прикладні засоби програмування та програмне забезпечення 79 Група Аудиторія Пара Ген 1,1 Ген 3,1 Ген 2,1 Ген 1,2 Ген 3,2 Ген 2,2 Ген 1,n Ген 3,n Ген 2,n ... ... ... Рис. 5. Представлення мультихромосоми Визначення обмежень, що накла- даються на розв’язок. Алгоритм потре- бує встановлення обмежень при побудові та оцінці хромосоми. Такі обмеження до- зволять відсіяти завідомо неправильні та неоптимальні можливі розв’язки постав- леної задачі. Обмеження можуть бути жо- рсткими та нежорсткими. Жорсткі обме- ження показують недопустимість, а не- жорсткі – небажаність розв’язку. До жорстких обмежень віднесемо наступні: y варіанті розв’язку мають бути представлені всі групи, для яких відбува- лася побудова розкладу; викладач не може проводити практичне заняття на одній парі більш ніж в одній групі, допускається про- ведення лекційних занять з предмету, для якого сформовані зведені групи; аудиторія не може бути зайнята для проведення за- нять двома різними групами одночасно, окрім випадку проведення лекцій з пред- мету, для якого сформовані зведені групи; розмір аудиторії має бути більшим чи рів- ним розміру групи; забезпечення відповід- ності аудиторії типу заняття; забезпечення уникнення накладок у розкладі для груп з не попарно незалежними списками студе- нтів на певній парі одночасно (визначимо попарно незалежні групи як групи, поряд- ковий номер яких різний і склад студентів яких не перетинається). Розв’язок-індивід вважається недопустимим, якщо в закодо- ваному ним розкладі порушуються жорст- кі обмеження. До нежорстких обмежень належать наступні: забезпечення побажань виклада- чів; якнайменше вікон у робочих планах викладачів; мінімізація вікон в індивідуа- льних планах студентів (зрозуміло, що це обмеження матиме невелику вартість, адже більше переваг надається виклада- чам); проведення лекційних занять зранку (бажано до третьої пари включно); забез- печення порядку проведення пар для пев- ного предмету: лекція-практика; лекційні та практичні заняття з одного предмету стоять у розкладі поруч та бажано у тих же аудиторіях. Беручи до уваги згадані вище об- меження можна побудувати хромосому адекватну вимогам нашої задачі. Функція здоров’я має враховувати визначені обмеження, і її значення має покращуватися у випадку знаходження кращого варіанта розкладу. Ми обрали наступну функцію здоров’я: n i iicwxf 1 )( , де iicw – добуток кількості порушень і-того обмеження iw на вартість і-того об- меження ic . Покращення у цьому випадку визначатиметься шляхом мінімізації зна- чення коефіцієнта здоров’я, а найкращим розв’язком буде особина зі значенням фу- нкції здоров’я, рівним нулю. Для жорстких обмежень встановлюється вища вартість обмеження у порівнянні з нежорсткими, що дає нам можливість отримувати кращі варіанти розв’язків, коригуючи значення вартостей обмежень. Оператори відбору особин у бать- ківський пул. Ми використовували про- порційний відбір (а саме відбір за методом рулетки), турнірний відбір та елітарний відбір. Прикладні засоби програмування та програмне забезпечення 80 Оператори схрещування. Опера- тор кросинговеру або схрещування (crossover operator) – це оператор, за допо- могою якого реалізується обмін генетич- ною інформацією між особинами популя- ції шляхом рекомбінації частин хромосом- батьків для утворення нащадків. Закодована хромосома груп побу- дована так, що вона містить коди груп, які не повторюються (у випадку, якщо в роз- кладі є предмет, пари з якого мають про- водитися двічі на тиждень, то для нього формуватимуться дві різні групи, відпові- дно для кожного заняття з даного предме- ту). Тому застосування класичних опера- торів кросинговеру може порушити стру- ктуру хромосоми, адже вони не забезпе- чують виконання обмеження, щоб жодне значення з заданої множини кодованих груп не повторювалося більше одного разу, та не забезпечують присутність всіх значень множини кодованих груп в хро- мосомі. Тому для кросинговеру хромосом груп застосовувалися наступні оператори схрещування: кросинговер часткового відображення (PMX-кросинговер) та упо- рядкований кросинговер з однією точкою схрещування (OX-кросинговер). Зако- довані хромосоми аудиторії та пар мо- жуть містити повтори значень, так як множина можливих аудиторій та пар є обмеженою. Відповідно до цього обме- ження у роботі для реалізації схрещуван- ня хромосом аудиторій та пар були засто- совані двоточковий та однорідний кро- синговери. Розглянемо алгоритми виконання цих операторів. За двоточкового кросинговеру (two- point crossover) випадковим чином генеру- ється дві точки перехрещування, та індиві- ди обмінюються ділянками між ними. На- ступний приклад (рис. 6) демонструє цю роботу. Нехай у нас є дві хромосоми ауди- торій довжини 10, що кодуються двознач- ними цілими числами (відповідно, ціле число буде представляти код закодованого об’єкта аудиторії, сам об’єкт, як уже за- значалося, в кодуванні складається з номе- ру, типу та розміру аудиторії), що можуть повторюватися. Відповідне ціле число ко- дує одну аудиторію. Для схрещування обираються точки 2 та 5. У випадку однорідного кросинго- веру (uniform crossover) кожен з генів хро- мосоми першого батька має 50 % шансів обмінятись місцями з відповідним йому геном хромосоми другого батька (рис. 7). Батьки: Нащадки: Рис. 6. Двоточковий кросинговер Батьки: Нащадки: Рис. 7. Однорідний кросинговер 11 15 16 13 17 12 11 18 16 15 17 13 18 12 11 18 15 16 17 13 11 15 18 12 11 12 11 18 16 15 17 13 16 13 17 18 15 16 17 13 11 15 16 13 17 12 11 18 16 15 17 13 18 12 11 18 15 16 17 13 11 13 16 12 11 12 11 16 16 13 17 15 18 13 17 18 15 18 17 15 Прикладні засоби програмування та програмне забезпечення 81 Роботу кросинговеру часткового відображення, або PMX-кросинговеру (Partially-Mapped Crossover), можна опи- сати в два кроки [4]. Спочатку випадко- вим чином обираються дві точки схрещу- вання та відбувається обмін генетичним матеріалом між цими точками. Потім від- бувається усунення дублів. Для цього ви- значається відображення відповідно до значень генів, якими обмінялися хромо- соми. Розглянемо приклад роботи PMX кросинговеру на прикладі 2-х хромосом груп довжини 9, точки схрещування 3 та 7 (рис. 8). Як видно з прикладу, після обміну генетичним матеріалом хромосоми стають некоректними, тому будуються відобра- ження 101 -> 104; 108 ->105 для першого протонащадка та 104 -> 101; 105 ->108 для другого протонащадка. Після усунення дублів отримуємо допустимі хромосоми. Розглянемо роботу упорядкованого OX-кросинговерy (Order Crossover) з од- нією точкою схрещування. На початку його роботи випадковим чином обираєть- ся певна точка схрещування. Далі значен- ня генів першого батька до цієї точки ко- піюються в першого нащадка без змін. А значення генів цього нащадка, що стоять після точки схрещування, заповнюються значеннями генів другого батька, але ти- ми що ще не потрапили в генотип даного нащадка, причому вони записуються в тому порядку, в якому зустрічаються в генотипі другого батька [4]. Відповідно таким же чином формується другий на- щадок. Роботу OX-кросинговеру відобра- жає наступний приклад, в якому теж від- бувається схрещування хромосом груп довжини 9, точка схрещування 4 (рис. 9). Розглядалися два випадки засто- сування цих кросинговерів. У першому випадку кросинговер застосовувався з певною ймовірністю лише до одного спи- ску генів особини (тобто груп, аудиторій чи пар). В другому випадку оператори схрещування застосовувалися до усіх списків, тобто і груп, і аудиторій, і пар. Батьки: Протонащадки: Нащадки: Рис. 8. PMX-кросинговер Батьки: Hащадки: Рис. 9. OX-кросинговер 101 102 103 104 105 106 107 108 109 104 105 102 101 108 107 106 109 103 101 102 103 101 108 107 106 108 109 104 105 102 104 105 106 107 109 103 104 102 103 101 108 107 106 105 109 101 108 102 104 105 106 107 109 103 101 102 103 104 105 106 107 108 109 104 105 102 101 108 107 106 109 103 101 102 103 104 105 108 107 106 109 104 105 102 101 103 106 107 108 109 Прикладні засоби програмування та програмне забезпечення 82 Оператори мутації. Оператор му- тації в генетичних алгоритмах відображає природній процес мутації. Його застосу- вання дозволяє запобігати передчасній збіжності популяції. У роботі розглянуто наступні типи мутацій: мутація обмінами та мутація вставкою. Ці типи мутації мо- жуть бути застосовані і до хромосом груп, і до хромосом аудиторій та пар. У випадку мутації обмінами (Exchange Mutation) дві випадково обрані позиції хромосоми обмінюються значен- нями генів. Кількість обмінів може бути один чи більше і є фіксованою. Розглянемо роботу мутації на прикладі хромосоми довжиною 10, в якому відбувається обмін між 3 і 7 позиціями генів (рис. 10). При мутації вставкою (Insertion Mutation) вибирається певна позиція в хромосомі і значення гену в цій позиції переноситься у випадкову обрану нову позицію. Розглянемо роботу даної мутації на прикладі, в якому відбувається вставка елемента з сьомої в третю позицію хро- мосоми (рис. 11). Оператор мутації, як і оператор кросинговеру, теж розглядався в двох ви- падках: з застосуванням оператора до всіх трьох списків особини (груп, аудиторій, пар) чи з застосуванням оператора мутації лише до одного із списків. Умови завершення роботи гене- тичного алгоритму. Для генетичного ал- горитму розв’язання задачі побудови розк- ладу виділимо три основні умови зупинки: знаходження розв’язку зі значенням коефіцієнта пристосованості, рівним нулю: відповідно цей розв’язок не порушує жод- не обмеження; досягнення максимальної кількості поколінь, заданих для роботи алгоритму; збіжність популяції, тобто середнє значення функції здоров’я не покращуєть- ся більше ніж на задане число певну зада- ну кількість ітерацій. При досяганні однієї з вище на- ведених умов, алгоритм завершуватиметь- ся та виводитиме результат своєї роботи, тобто особину з найкращим рівнем прис- тосованості (найближчим до нуля). Застосування евристик для вибо- ру аудиторій та пар під час ініціалізації. При ініціалізації особин спочатку генеру- ється випадкова послідовність груп, далі аудиторій і в кінці пар. У випадку вибору значень аудиторій, можна запропонувати наступні евристики. По-перше, під час ініціалізації осо- бин використовувати ітеративний метод побудови списку аудиторій. На етапі ініці- алізації індивідів спочатку відбувається ініціалізація списку груп. Коли відбуваєть- ся перехід до ініціалізації списку аудито- рій, то на кожній ітерації будемо викону- вати перевірку, чи не порушує наступна бажана для додання в список аудиторія обмеження того, що в одній аудиторії не може проводитися одночасно заняття в двох групах (окрім зведених груп). Відпо- відно, якщо випадковим чином обрана ау- диторія порушує це обмеження, то необ- хідно ще раз генерувати випадкову ауди- торію зі списку аудиторій, попередньо ви- ключивши з нього дану, завідомо некорек- тну аудиторію для цієї позиції у списку. Батько: Hащадок: Рис. 10. Мутація обмінами Батько: Hащадок: Рис. 11. Мутація вставкою 11 14 13 19 22 10 15 18 21 20 11 14 15 19 22 10 13 18 21 20 11 14 15 19 22 10 13 18 21 20 11 14 13 15 19 22 10 18 21 20 Прикладні засоби програмування та програмне забезпечення 83 По-друге, під час ініціалізації також можна забезпечувати вибір аудиторій для лекцій з аудиторій більшого розміру, а для практичних – з аудиторій меншого розмі- ру. Тому варто проводити переініці- алізацію аудиторії, поки не буде уникнено обмеження розміру. Така генерація ауди- торій на етапі ініціалізації забезпечує ви- конання жорсткого обмеження розміру ау- диторії до розміру групи. Зрозуміло, що схожу схему можна застосовувати і до об- рання комп’ютерних чи некомп’ютерних класів для ініціалізації відповідно до пре- дметів груп. При ініціалізації значень списку пар теж можна застосовувати ітеративну побу- дову, базуючись на частині списку вже обраних варіантів пар для груп певного курсу. Якщо в множині вже обраних пар для певного курсу обрана пара вже зустрі- чається для лекційного заняття (повного складу групи), то потрібно генерувати ін- шу пару для додання до списку, відповідно попередньо виключивши дану зі списку для генерації. У випадку практичних за- нять треба виконувати перевірку на попа- рну незалежність груп. Якщо групи є по- парно незалежними, то вибір пари для проведення заняття дозволяється для двох чи більше попарно незалежних груп, в ін- шому випадку відбувається перегенерація пари для групи. Мутація складу груп. Для НаУК- МА необхідно також врахувати наявність у розкладі курсів вибіркових предметів. Відповідно, це може спричинити накладки в розкладі, бо списки різних груп студентів можуть перетинатися, тобто групи не є попарно незалежними. Щоб покращити значення функції пристосованості хромосоми особини, для якої це обмеження порушується, введемо мутацію складу груп. Ця мутація працюва- тиме наступним чином: якщо дві групи на певній парі мають різні порядкові номери, але їхні списки студентів не є попарно не- залежними, то відбуватиметься обмін спи- сками студентів, що повторюються в обох групах, зі списком студентів інших груп з цього предмету. Ця операція застосовува- тиметься лише до однієї з груп, які пору- шують дане обмеження, з більшою ймові- рністю до тієї групи, для якої зустрічають- ся інші можливі групи з даного предмету. У випадку, коли для обох предметів немає груп для заміни, тоді доведеться проводи- ти обмін самих груп у розкладі. Додавання в початкову популя- цію вдалих підрозв’язків. Ще однією модифікацією, яка може покращити якість знайдених генетичним алгоритмом роз- в’язків, є додавання в популяцію існую- чих розв’язків. У початкову популяцію додаються існуючі розв’язки розкладу, тобто кілька варіантів розкладу, складе- них методистом у минулому навчальному році з заміною попереднього на поточний склад груп. Таке додання в початкову по- пуляцію дозволяє визначити напрям роз- витку популяції та покращити кінцевий результат. Паралельна реалізація алгоритму Розглянемо основні ідеї реалізації запропонованого алгоритму у вигляді про- грамного застосунку. Застосунок розроблено на мові про- грамування Java з використанням програм- ного інструменту maven для управління Java проектами. Графічний інтерфейс за- безпечувала бібліотека Swing. Для збере- ження вхідних даних програми використо- вувалася СКБД MySQL, а програмний зв’язок з базою даних побудований за до- помогою Hibernate. Збереження pdf-файлів з розкладом на диску проводилося на базі бібліотеки itext. З метою пришвидшення роботи ал- горимту було вирішено розробити пара- лельну версію ГА, що базується на моде- лі «фермер-робітники» [7]. Застосування створює декілька робочих потоків, кіль- кість яких дорівнює кількості процесорів, встановлених на комп’ютері, на якому виконується програма. Серед процесорів віділяють «фермера» та «робітників». По- токи «робітники» відповідають за поро- дження нащадків, їxнє оцінювання та му- тацію. Після оцінювання опрацьовані особини передаються «фермеру» для від- бору в нове покоління. На «фермерові» відбувається відбір в нове покоління та застосування оператора кросинговеру. В загальному випадку мутація може вико- Прикладні засоби програмування та програмне забезпечення 84 нуватися теж на «фермері», але в даній програмі вона теж розподіляється на «ро- бітників», які після опрацювання повер- тають особин «фермеру». Коли нове по- коління повністю сформоване, воно знову передається «робітникам» на обробку. Такий поділ особин між фермером і робі- тником обумовлений тим, що функція оцінювання вимагає багато ресурсів для обчислення. Після кодування, створення почат- кової популяції та застосування фітнес- функції та функції-валідації на «робітни- ках» до особин популяції застосовується метод селекції на «фермері», а до обраних селектором індивідів застосовується кро- синговер. Для мутації особини порівну розпаралелюються між «робітниками» і до кожної з них з певною ймовірністю застосовується мутатор. Після того як всі «робітники» завершили свою роботу над особинами, сформоване нове покоління знову подається на вхід наступній ітерації циклу для подальшого оцінювання, селек- ції і т. д., поки дійдемо до останнього по- коління. Коли програма опрацювала останнє покоління – вона знаходить най- кращу особину популяції відповідно до функції оцінювання, яка є найкрашим варіантом розв’язку. Висновки У цій роботі описано розроблений нами паралельний генетичний алгоритм побудови розкладу занять ВНЗ на основі моделі «фермер-робітники». Робота алго- ритму тестувалася програмним застосун- ком із графічним інтерфейсом користувача та збереженням даних в СКБД на основі навчального плану занять факультету ін- форматики НаУКМА на різних конфігура- ціях та значеннях параметрів. Досліджувалися елітарний, пропор- ційний та турнірний методи відбору осо- бин в батьківський пул, PMX-кросинговер та упорядкований OX-кросинговер як ме- тоди кросинговеру груп, двоточковий та однорідний кросинговери для породження нащадків списків аудиторій та пар. Розгля- далося застосування операторів мутації вставкою та обміном. У результаті експериментів можна рекомендувати для розв’язання задачі по- будови розкладу наступну конфігурацію параметрів: застосування турнірного відбору в батьківський пул з невеликим розміром турніру (наприклад, розміром рівним п’яти) для забезпеченя різноманітності особин популяції; застосування кросинговеру PMX для схрещування хромосом груп, резуль- тати застосування якого у всіх тестах є дещо кращими за результати OX- кросинговеру; застосування однорідного кросин- говеру для породження нащадків хромо- сом аудиторій та пар; застосування операторів кросинго- веру одразу до трьох хромосом (груп, ау- диторій і пар) з високою ймовірністю – від 0.9 до 1.0; застосування оператора мутації обмінами з ймовірністю до 0.05 для спрощених задач та з ймовірністю від 0.1 до 0.2 для побудови розкладу усього фа- культету; застосування розроблених модифі- кацій алгоритму (а саме евристик при іні- ціалізації особин, мутації складу груп, до- давання існуючих вдалих підрозв’язків), оскільки їх застосування покращує швид- кість знаходження розв’язків. За вищенаведеною конфігурацією значення найкращого середнього відхи- лення задачі побудови розкладу магістер- ської програми становило 0.115 %. Зна- чення середнього відхилення задачі побу- дови розкладу програми бакалаврату є рів- ним 2.115 %, а для задачі побудови розк- ладу факультету дане значення становить 4.2 %. Проведені експерименти підтверд- жують хороші оцінки практичного засто- сування запропонованого генетичного ал- горитму складання розкладу. 1. Коффман Э.Г. Теория расписаний и вычи- слительные машины. М.: Наука, 1984. – 335 с. 2. Конькова И.С. Генетические алгоритмы в решении задачи составления расписания Прикладні засоби програмування та програмне забезпечення 85 занятий в вузе // Проблемы информатики в образовании, управлении, экономике и технике: Сб. статей XII Междунар. науч- но-техн. конф. – Пенза: ПДЗ, 2012. – С. 26–29. 3. Busetti F. Simulated annealing overview, 2009. – Available at: http://www.cs.ubbcluj.ro/~csatol/mestint/pdfs/ Busetti_AnnealingIntro.pdf. 4. Глибовець М.М., Гулаєва Н.М. Еволюційні алгоритми. – К.: НаУКМА, 2013. – 828 с. 5. Глибовец H.Н., Медвідь С.А. Генетичиские агоритмы и их использование для решения задачи составления расписания // Киберне- тика и системный анализ. – 2003. – № 1. – С. 95–108. 6. тко В.В., Бурбело С.М. та інші. Розробка автоматизованої системи формування розкладу магістратури // Нау- кові праці ВНТУ. – 2009. – №4. – С. 91–94. 7. Бидюк П.И., Литвиненко В.И., Токарь А.А. Параллельные генетические алгоритмы // Системні дослідження та інформаційні те- хнології. – 2002. – № 4. – С. 7–16. Одержано 18.12.2014 Про авторів: Глибовець Микола Миколайович, доктор фізико-математичних наук, професор, декан факультету інформатики НаУКМА, Гулаєва Наталія Михайлівна, кандидат фізико-математичних наук, доцент кафедри інформатики НаУКМА, Пасічник Мар’яна Михайлівна, магістр факультету інформатики НаУКМА. Місце роботи авторів: Національний університет «Києво-Могилянська Академія», 04655, м. Київ, вул.Сковороди, 2. Тел.: (044) 463 6985. Факс: (044) 416 4515. E-mail: glib@ukma.kiev.ua E-mail: ngulayeva@yahoo.com E-mail: mariana.pasichnyk@gmail.com http://www.cs.ubbcluj.ro/~csatol/mestint/pdfs/Busetti_AnnealingIntro.pdf http://www.cs.ubbcluj.ro/~csatol/mestint/pdfs/Busetti_AnnealingIntro.pdf
id	pp_isofts_kiev_ua-article-140
institution	Problems in programming
keywords_txt_mv	keywords
language	Ukrainian
last_indexed	2026-03-12T23:13:31Z
publishDate	2017
publisher	PROBLEMS IN PROGRAMMING
record_format	ojs
resource_txt_mv	ppisoftskievua/df/5e675bdfc9cc077d4b70827e097c38df.pdf
spelling	pp_isofts_kiev_ua-article-1402018-07-18T20:55:57Z A Parallel Genetic Algorithm to Solve Scheduling the University Class Problem Параллельный генетический алгоритм построения расписания занятий Паралельний генетичний алгоритм побудови розкладу занять Glybovets, M.M. Gulayeva, N.M. Pasichnyk, M.M. UDC 004.8 УДК 004.8 УДК 004.8 This paper describes the development and implementation of a parallel genetic algorithm (GA) to solve scheduling the university class problem. The proposed GA is based on the "farmer-workers" model and uses a number of heuristics, e. g. classroom and time selection during population initialization, adding useful subsolutions into the initial population, using special (new) mutation operator. In the algorithm a specific chromosome coding and fitness function that takes into account a number of restrictions on the resulting schedule are proposed. Problem-specific crossover and mutation operators are developed. Based on a number of computational experiments optimal parameters of GA are proposed for further use. В работе описана разработка и реализация параллельного генетического алгоритма (ГА) построения расписания ВУЗа на основе модели «фермер-работники» с элементами эвристики (выбор аудиторий и пар в процессе инициализации, применение нового (дополнительного) оператора мутации, добавление удачных частей решений в популяцию при инициализации начальной популяции). В алгоритме разработан специальный способ кодирования хромосомы, предложена функция оценки хромосомы с учетом ряда ограничений, налагаемых на результирующее расписание-хромосому, а также разработаны специальные операторы кроссинговера и мутации. На основе проведенных экспериментов предложены оптимальные значе-ния параметров ГА. У роботі описана розробка та реалізація паралельного генетичного алгоритму (ГА) побудови розкладу ВНЗ на основі моделі «фермер-робітники» з елементами евристики для вибору аудиторій та пар під час ініціалізації, застосування нового (додаткового) оператора мутації, додання вдалих підрозв’язків в популяцію під час інціалізації початкової популяції. У алгоритмі введено специфічний спосіб кодування хромосоми, запропоновано функцію оцінки хромосоми з урахуванням низки обмежень, що накладаються на результуючий розклад-хромосому, а також розроблено спеціальні оператори кросинговеру та мутації. На основі експериментів запропоновано оптимальні значення параметрів ГА. PROBLEMS IN PROGRAMMING ПРОБЛЕМЫ ПРОГРАММИРОВАНИЯ ПРОБЛЕМИ ПРОГРАМУВАННЯ 2017-06-14 Article Article application/pdf https://pp.isofts.kiev.ua/index.php/ojs1/article/view/140 PROBLEMS IN PROGRAMMING; No 2 (2015) ПРОБЛЕМЫ ПРОГРАММИРОВАНИЯ; No 2 (2015) ПРОБЛЕМИ ПРОГРАМУВАННЯ; No 2 (2015) 1727-4907 uk https://pp.isofts.kiev.ua/index.php/ojs1/article/view/140/133 Copyright (c) 2017 ПРОБЛЕМИ ПРОГРАМУВАННЯ
spellingShingle	UDC 004.8 Glybovets, M.M. Gulayeva, N.M. Pasichnyk, M.M. A Parallel Genetic Algorithm to Solve Scheduling the University Class Problem
title	A Parallel Genetic Algorithm to Solve Scheduling the University Class Problem
title_alt	Параллельный генетический алгоритм построения расписания занятий Паралельний генетичний алгоритм побудови розкладу занять
title_full	A Parallel Genetic Algorithm to Solve Scheduling the University Class Problem
title_fullStr	A Parallel Genetic Algorithm to Solve Scheduling the University Class Problem
title_full_unstemmed	A Parallel Genetic Algorithm to Solve Scheduling the University Class Problem
title_short	A Parallel Genetic Algorithm to Solve Scheduling the University Class Problem
title_sort	parallel genetic algorithm to solve scheduling the university class problem
topic	UDC 004.8
topic_facet	UDC 004.8 УДК 004.8 УДК 004.8
url	https://pp.isofts.kiev.ua/index.php/ojs1/article/view/140
work_keys_str_mv	AT glybovetsmm aparallelgeneticalgorithmtosolveschedulingtheuniversityclassproblem AT gulayevanm aparallelgeneticalgorithmtosolveschedulingtheuniversityclassproblem AT pasichnykmm aparallelgeneticalgorithmtosolveschedulingtheuniversityclassproblem AT glybovetsmm parallelʹnyjgenetičeskijalgoritmpostroeniâraspisaniâzanâtij AT gulayevanm parallelʹnyjgenetičeskijalgoritmpostroeniâraspisaniâzanâtij AT pasichnykmm parallelʹnyjgenetičeskijalgoritmpostroeniâraspisaniâzanâtij AT glybovetsmm paralelʹnijgenetičnijalgoritmpobudovirozkladuzanâtʹ AT gulayevanm paralelʹnijgenetičnijalgoritmpobudovirozkladuzanâtʹ AT pasichnykmm paralelʹnijgenetičnijalgoritmpobudovirozkladuzanâtʹ AT glybovetsmm parallelgeneticalgorithmtosolveschedulingtheuniversityclassproblem AT gulayevanm parallelgeneticalgorithmtosolveschedulingtheuniversityclassproblem AT pasichnykmm parallelgeneticalgorithmtosolveschedulingtheuniversityclassproblem

A Parallel Genetic Algorithm to Solve Scheduling the University Class Problem

Репозитарії

Схожі ресурси