Математичне моделювання процесу складання розкладу в університеті

Поділитися Share on Facebook2Tweet about this on TwitterShare on Google+0Share on LinkedIn0Share on Reddit0Pin on Pinterest0Print this page

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

КЛЮЧОВІ СЛОВА: математичне моделювання, розклад, складання розкладу, університет, еволюційні методи, генетичний алгоритм, фітнес-функція,схрещування, мутація

АКТУАЛЬНІСТЬ. Складання розкладу являє собою надзвичайно трудомісткий та складний процес, який полягає у встановленні послідовності зустрічей викладачів і студентів у заздалегідь заданий проміжок часу (як правило, протягом тижня), з урахуванням задоволення низки обмежень різного характеру. Беручи до уваги  той факт, що в більшості українських ВНЗ складання розкладу відбувається вручну, при цьому, в зв’язку з надзвичайною складністю урахування всіх обмежень, велику увагу приділяють автоматизації складання розкладу. Проте процесу автоматизації передує розробка правильного математичного алгоритму, на основі якого створюватиметься система. Він являється ядром всієї системи, тому перш ніж сідати за проектування та розробку програмного продукту, потрібно скласти правильну математичну модель та метод (алгоритм) для системи. Це є надзвичайно складним процесом, оскільки потрібно враховувати безліч чинників та факторів, таких як навантаження студентів, навантаження викладачів, аудиторний фонд ВНЗ, поділ груп на підгрупи, необхідність спеціалізованих приміщень для проведення лабораторних занять та  багато інших. Актуальність цієї теми полягає в тому, що не зважаючи на те, що є велика кількість методів та алгоритмів для задачі складання розкладів, ще не існує універсального алгоритму, який би здійснював складання розкладу для вищих навчальних закладів без втручання людини. 

АНАЛІЗ ДОСЛІДЖЕНЬ І ПУБЛІКАЦІЙ. Дослідженням даної теми займалися і продовжують займатись науковці із всього світу, втому числи із України.

Бойко О.М. з черкаського державного технологічного університету обґрунтував необхідність створення автоматизованої системи складання розкладу занять. Для цього автор пропонує використовувати генетичний алгоритм. Най його основі формує цільову функцію, необхідні обмеження, формує початкову популяцію та показує приклади, як проводяться такі операція як кросове та мутація. Використовуючи ці знання, автором була побудова система на базі об’єктно-орієнтовних принципів, яка перевіряла залежність час виконання генетичного алгоритму від розміру задачі. Бойко О.М. дійшов висновку, із збільшенням розмірності, збільшується час розв’язання задачі. Також було зазначено, що розв’язок отриманий за допомогою такого алгоритму близький до оптимальності але не оптимальний [2].

С. В. Бевз, В. В. Войтко, С. М. Бурбело, А. М. Шоботенко займались розробкою автоматизованої системи формування розкладу магістратури Вінницького національного технічного університету. Автори створили математичний алгоритм на основі якого повинна працювати система. Сама ж безпосередньо здійснена засобами об’єктно-орієнтовної мови програмування PHP [1].

Цзянь Ні (Jian Ni) з Хебейського університету інженерії (Китай) у своїй праці обґрунтував необхідність створення автоматичної системи створення розкладу. Так наприклад, з 1999 року в Китаї була введена нова політика, щодо зарахування в університет. Внаслідок цього значно зросла кількість студентів, а через це в свою чергу значно ускладнилась робота навчально-методичних відділів. Для вирішення проблеми автор пропонує використовувати генетичний алгоритм, як ефективний метод для розв’язку[10].

Кулдіп Кумар (Kuldeep Kumar), Рамеш Шарма (Ramesh Sharma), Каушал Мехта (Kaushal Mehta) із університету імені Чаудхари Деві Лал (Сирса, Індія) у своїй роботі використовували генетичний алгоритм. Авторами було визначені жорсткі та м’які обмеження, було наведено схему генетичного алгоритму, показані приклади схрещування та мутації, сформована фітнес-функція та початкова популяція. Для практичної реалізації свого алгоритму, використовувалась бібліотека мови програмування C++ для генетичних алгоритмів GALIB 247. В результаті  практичної верифікації було виявлю, що із збільшенням популяції, порушення м’яких та жорстких обмежень зменшуються[11].

ОСНОВНА ЧАСТИНА

1. Генетичний алгоритм

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

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

Генетичний алгоритм (англ. genetic algorithm) — це еволюційний алгоритм пошуку, що використовується для вирішення задач оптимізації і моделювання, шляхом послідовного підбору, комбінування і варіації шуканих параметрів з використанням механізмів, що нагадують біологічну еволюцію.

Цей метод заснований на аналогії з природними еволюційними процесами. Його перевагою є те, що не висуваються додаткові вимог до виду цільової функції, на кожній ітерації працює з множиною рішень, що дозволяє в багатьох випадках більш детально в порівнянні з градієнтними методами багатовимірної нелінійної безумовної оптимізації аналізувати простір пошуку [7].

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

«Батьком-засновником» генетичних алгоритмів вважається Джон Голланд (англ. John Holland), книга якого “Адаптація в природних і штучних системах” (англ. Adaptation in Natural and Artificial Systems) є фундаментальною в цій сфері досліджень.

Згідно з еволюційною теорією Чарльза Дарвіна біологічні світи, для того щоб вижити, повинні пристосовуватися до навколишнього середовища і разом з тим відбувається біологічна спадкоємність нащадками життєво важливих властивостей від батьків. Відповідно до експерименту Освальда Евері, Коліна Маклауда  і Макліна Маккарті зробленого в 1944 році, та на основі сучасних досліджень із цитології та генетики, матеріальною основою спадковості і мінливості організмів  є хромосомна ДНК – основний генетичний матеріал.

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

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

– хромосома – структурний елемент клітинного ядра біологічних організмів, є носієм генів у клітинному ядрі особини. У генетичних методах терміни «хромосома» та «особина» використовуються як синоніми;

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

Генетичний алгоритм має такі переваги:

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

– концептуальна простота та прозорість реалізації;

– можливість розпаралелювання;

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

– можливість застосування до великого кола задач без внесення серйозних змін у внутрішню структуру методу;

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

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

– можливість застосування в методі інших пошукових процедур [7].

Генетичний алгоритм реалізується у декілька етапів (рис. 1) :

genetic_algo

Рис. 1. Схема роботи генетичного алгоритму

2. Обмеження

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

Жорсткі – це обмеження, які повинні неодмінно задовольнятися; такі які фізично не можуть бути порушені (наприклад один і той самий викладач не може бути присутній в один і той самий час у двох місцях одночасно).

М’які – це обмеження, які можна порушувати, але це порушення повинно бути зведене до мінімуму. Їхнє виконання не є таким же обов’язковим, як жорстких. У таблиці 1 наведені жорсткі та м’які обмеження які необхідні для процесу складання розкладу:

Таблиця 1

Обмеження для процесу складання розкладу

Жорсткі

М’які

  • викладач   не може бути присутнім на двох заняттях одночасно;
  •   в одній аудиторії не можуть проводитися різні   заняття одночасно;
  •   місткість аудиторії не може бути меншою, ніж   кількість присутніх у ній студентів;
  •   деякі заняття вимагають особливих аудиторій   (наприклад комп’ютерних класів, лабораторій, спортзалів та інше );
  • одна група не може вивчати декілька   дисциплін на одному занятті одночасно;
  • тижневе навантаження для студентів   бакалаврату становить 30 годин;
  • тижневе навантаження для   студентів-спеціалістів 24 годин;
  • тижневе навантаження для   студентів-магістрів становить 18 годин;
  •  кількість   занять на день не більше 4
  •  викладачі можуть віддавати перевагу конкретним   часовим інтервалам;
  •   викладачі можуть віддавати перевагу певним   аудиторіям;
  •   деякі види предметів не повинно бути в суміжні   в часові;
  •   уникнення проміжних періодів в розкладі (вікна);
  •   рівномірний розподіл занять протягом тижня;
  •   місткість аудиторій не повинна бути набагато   більшою ніж кількість присутніх студентів;
  • більш складні заняття потрібно проводити   на 1-2 парі;
  • фізичне виховання рекомендується проводити   3-4 парою;

3. Вхідна інформація

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

1) T = {tw, td, tp} – множина часу проведення робочих занять (пар), де t_w^k = {1…Nw}- номер тижня, t_d^k = {1…Nd}- номер дня тижня, t_p^k = Np}- номер пари протягом дня;

2) G = { g1, g2…gNg } – множина груп в університеті, де gi – номер навчальної групи, Ng – загальна кількість навчальних груп;

3) L = { l1, l2…lNl } – множина викладачів університету, де li– номер викладача, Nlзагальна кількість викладачів в ;

4) D = { d1, d2…dNd } – множина дисциплін, де Di– номер навчальної дисципліни, Nd– загальна кількість дисциплін в університеті;

5) A = { a1, a2…aNa} – множина аудиторій університету, де ai– номер аудиторії, Na– загальна кількість аудиторій в університеті [3;7].

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

3.1 Аудиторії

Проведемо поділ аудиторій на три типи:

1)      аудиторії для проведення лекційних занять (потокові) – Ab;

2)      аудиторії для практичних занять (для однієї групи/підгрупи) – As;

3)      лабораторні аудиторії (комп’ютерні класи, спец аудиторії та інше) – Al.

Таким чином : A=Ab U As U Al ,  A = (a_j^t), тип аудиторії і приймає значення b, s, l.

3.2 Взаємозв’язок множин дисципліна, викладач та група

Між такими множинами як дисципліна, викладач та група існує тісний зв’язок, оскільки групи вивчають певні дисципліни, які проводяться конкретними викладачами (рис.2).

rel

Рис. 2. Взаємозв’язок множин «Групи», «Дисципліни» та «Викладачі»

Як наслідок утворюється нова множина, яку назвемо «Знання» і можемо представити наступним чином:

Z = {zi} = (z_i^l,z_i^t,z_i^d,z_i^g,z_i^a), де z_i^l- викладач; z_i^d - дисципліна; z_i^g- група; z_i^t- тип занять; z_i^a- необхідна аудиторія.

3.3 Кодування інформації

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

1)      бінарне кодування – гени у хромосомах можуть приймати значення 0 або 1;

2)      числове – гени можуть приймати значення в заданому інтервалі;

3)      векторне – гени є вектором цілих чисел [7].

На нашу думку найкращим методом для кодування такого роду інформації є числовий. Хоч і в класичному генетичному алгоритмі зазвичай кодування відбувається бінарним способом, але для цієї задачі такий метод має ряд недоліків, які впливають на швидкість та збіжність алгоритму. До прикладу, числа 7 та 8 у десятковому представленні відрізняються однією позицією, а от у бітовому (0111 та 1000) – чотирма [2]. Недоліком векторного кодування є те, що вектор не може містити однакових чисел.

Розгляньмо приклад, де початковими даними для складання розкладу є 2 тижні, 5днів тижня, 5 пар на день; 30 викладачів, 70 дисциплін, 20 навчальних груп, 100 аудиторій.

Отже, кодування хромосоми буде наступним: на кодування множини робочих занять відводиться 3 знаки (тижні, дні тижня, пар в день [1,2; 1…5; 1…5] ), на кодування множини знання 10 знаків (викладачі, тип заняття, дисципліни, навчальні групи, аудиторія – [1…30; 1…3; 1…70; 1…20; 1…100] ). Таким чином хромосома містить у собі 13 знаків, а популяція міститиме 1000 особин ( 2тижні*5днів*5пар*20груп). Наприклад одна з особин буде виглядати так:

1 2 3 27 2 54 14 098

і означатиме, що на першому тижні (1), у вівторок (2) на третій парі (3), викладач під номером 27 вестиме практичне (2) заняття з дисципліни під номером 54 в 14 групі у 98 аудиторії.

4. Цільова функція (фітнес-функція)

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

F(H_j )=w_p^{td}*Q*v_g/k_t\rightarrow max,

де Hj – оцінювана хромосома;

w_p^t – ваговий коефіцієнт викладача p, щодо проведення занять у td  день тижня;

td  = {1…Nd}- номер дня тижня, Nd – кількість робочих днів у тижні;

vg – ваговий коефіцієнт, щодо наявності у td  день тижня проміжних періодів у розкладі («вікон») для g групи;

k_{td} – кількість вікон у день td  (якщо вікон немає то k_{td} = 1);

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

Q=y(t,g)*x(t,p),

34

t=(t_w,t_d,t_p ),

де t_w = {1…Nw}- номер тижня;

t_d = {1…Nd}- номер дня тижня;

t_p = {1…Np}- номер пари протягом дня.

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

Цільова функція застосовується щодо кожної особини (хромосоми) популяції і спрямована на знаходження максимального значення.

5. Генетичні оператори

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

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

5.1 Схрещування

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

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

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

crossover

Рис. 3. процедура проведення одноточкового кроссоверу

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

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

Х: 7 3 1 27 2 54 15 38

У: 9 2 4 68 1 63 3 27

Тепер визначимо точку розриву:

Х: 7 3 1 27 2 . 54 15 38

У: 9 2 4 68 1. 63 3 27

Проведемо обмін частинами та утворимо нащадків:

Х2: 7 3 1 27 2 63 3 27

У2: 9 2 4 68 1 54 15 38

Із проведеної операції бачимо, що із батьківських хромосом X і Y утворилися два нащадки Х2 та У2. Проте слід звернути увагу на те, що в першому випадку хромосома Х означала проведення 27 викладачем 54 предмету у групі  під номером 15. А після схрещування, що 27 викладач проводить заняття з дисципліни 63 у групі 3. Це означає, що викладач повинен викладати зовсім інший предмет для іншої групи. Тобто на практиці це те саме, що заставити викладача правничого факультету викладати економетричний аналіз для групи економічного факультету. Звичайно ж така ситуація в реальних умовах не допускається. Тому для завдань складання розкладу за допомогою генетичного алгоритму ми не рекомендуємо застосовувати операцію схрещування.

5.2 Мутація

Оператор мутації полягає в зміні генів у випадково вибраних позиціях. На відміну від оператора схрещування, які використовуються для поліпшення структури хромосом, метою оператора мутації є диверсифікація, тобто підвищення різноманітності пошуку і введення нових хромосом в популяцію для того, щоб більш повно досліджувати простір пошуку. Мутація ініціює різноманітність в популяції, дозволяючи проглядати більше точок в просторі пошуку і долати таким чином локальні екстремуми в ході пошуку [7].

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

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

Алгоритм здійснення операції складається з таких кроків:

  1. Скопіювати батьківську хромосому в хромосому-нащадка;
  2. Вибираємо випадковим чином ген для мутації;
  3. У заданому інтервалі допустимих значень гена вибрати нове значення, що не дорівнює поточному.

Наприклад маємо хромосому Х: {7 3 1 27 2 63 3 27} і хочемо застосувати до неї операцію мутації. Будемо виконувати процедуру поетапно:

1)      Копіюємо батьківську хромосому в хромосому-нащадка:

Х: {7 3 1 27 2 63 3 27} \rightarrow Х2: {7 3 1 27 2 63 3 27}

1)      Вибираємо випадковим чином ген для мутації:

Х2: {7 3 1 27 2 63 3 27}

2)      У заданому інтервалі допустимих значень гена вибираємо нове значення, що не дорівнює поточному:

Х2: {7 1 1 27 2 63 3 27}

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

Для кращого сприйняття здійснимо операцію мутації на реальному прикладі. Припустимо ми маємо попередній зразок розкладу для групи Ек-43, який виглядає наступним чином:

Таблиця 2

Розклад навчальних занять для групи Ек-43на 1 – 5 вересня 2013 року

tb_1

Також маємо індивідуальний розклад викладача Цапіна А.О. для цього ж тижня:

Таблиця 3

Індивідуальний розклад занять викладача Цапіна А.О. на 1-5 вересня 2013року

tb_3

Проведемо операцію мутації для того, щоб покращити поточні результати. Для цього із популяції потрібно відібрати хромосому. Хромосоми складаються на основі таблиці 2 і виглядають наступним чином:

Таблиця 4

Розклад навчальних занять для групи Ек-43на 1 – 5 вересня 2013 року представлений у вигляді хромосом

tb_4

Нами було вибрано для дослідження хромосому Х1: 1 4 4 6 2 6 43 15.

Тепер потрібно вибрати ген для мутації. Ми вибрали 2-й порядковий ген, який відповідає за день тижня. Відповідно до алгоритму ми будемо міняти його значення на ті, які не дорівнюють його поточному значенню і одночасно будемо оцінювати особину за допомогою цільової функції. Заданий інтервал для цього гена {1, 2, 3, 4, 5}, що відповідає номеру дня тижня.

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

Припустимо, що Цапін А. О. сформував вагові коефіцієнти наступним чином: w_6^t = {Пн.-0,15; Вт.-0,1; Ср.-0,3; Чт.-0,2; Пт.-0,25};

вагові коефіцієнти, щодо наявності проміжних періодів для групи Ек-43:

v43 = {0,3-присутні проміжні періоди; 0,7-відсутні}.

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

Оцінюємо цільову функцію:

F(X_1 )=w_6^4*Q*v_{43}/k_4

 

v_{43}= 0,3;

k_t = 3;

Q=y(1;4;4,43)*x(1;4;4,6) = 1*1= 1.

F(X_1 )=w_6^5*Q*v_{43}*k_5 = 0,15*1*0,3/3 = 0,015.

Отож, проводимо мутацію:

X2:  1 5 4 6 2 6 43 15

F(X_2 )=w_6^5*Q*v_{43}/k_5

w_6^5= 0,25;

v_{43}= 0,3;

k_t = 1;

Q=y(1;5;4,43)*x(1;5;4,6) = 1*0= 0.

F(X_2 )=w_6^5*Q*v_{43}*k_5 = 0,25*0*0,3/1 = 0.

Як бачимо фітнес-функція = 0 і це означає, що хромосома Х1 не придатна для використання, тому вона потребує повторного покращення через операцію мутації. Тому виконує процедуру до тих пір, допоки не отримаємо необхідне значення цільової функції.

X3:  1 1 4 6 2 6 43 15

F(X_3 )=w_6^1*Q*v_{43}*k_1 = 0,15*0*0,7/1 = 0.

X4:  1 2 4 6 2 6 43 15

F(X_4 )=w_6^2*Q*v_{43}*k_2 = 0,1*0*0,3/1 = 0.

X5:  1 3 4 6 2 6 43 15

F(X_5 )=w_6^3*Q*v_{43}*k_3 = 0,3*1*0,3/1 = 0,09.

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

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

Таблиця 5

Розклад навчальних занять для групи Ек-43 на 1 – 5 вересня 2013 року після проведення операції мутації

tb_5

Індивідуальний розклад занять для викладача Цапіна А.О. після операції мутації наведено у таблиці 6.

Таблиця 6

Індивідуальний розклад занять викладача Цапіна А.О. на 1-5 вересня 2013року після проведення операції мутації

tb_6

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

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

ВИСНОВКИ

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

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

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

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

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

ЛІТЕРАТУРА

  1. Бевз С. В., Войтко В. В., Бурбело С. М., Шоботенко А. М. Розробка автоматизованої системи формування розкладу магістратури // Наукові праці ВНТУ. – Вінниця. – 2009. – Вип.1. – С. 1-10.
  2. Бойко О.М. Еволюційна технологія розв’язування задачі складання розкладів навчальних занять // Штучний інтелект. – 2006. – Вип.3. – С. 341-348.
  3. Кабальнов Ю.С., Шехтман Л.И., Низамова Г.Ф., Земченкова Н.А. Композиционный генетический алгоритм составления расписания учебних занятий // Вестник УГАТУ. Научные статьи и доклады: Информационные технологии – Уфа. – 2006. – №2(15). – С. 99-107
  4. Ризун Н.О. Применение методов декомпозиции при решении многокритериальной задачи автоматизации составления расписания учебных занятий в ВУЗе // Восточно-Европейский журнал передовых технологий: Математика и кибернетика – фундаментальные и прикладные аспекты. – 2010. – №2/4(44). – С. 59-69.
  5. Рутковская Д., Пилиньский М., Рутковская Л. Нейронные сети, генетические алгоритмы и нечеткие системы: Пер. с польск. И.Д. Рудинского. – М.: Горячая линия-Телеком, 2006. – 452 с.
  6. Сидорин А.Б., Ликучева Л.В., Дворянкин Методы автоматизации составления расписания занятий Часть 2. Эвристические методы оптимизации // Известия ВолгГТУ. – Волгоград. – 2009. – №12(60). – С. 120-123.
  7. Субботін С.О., Олійник А.О., Олійник О.О. Неітеративні, еволюційні та мультиагентні методи синтезу нечіткологічних і нейромережних моделей: Монографія // Під заг. ред. С. О. Субботіна. – Запоріжжя: ЗНТУ, 2009. – 375 с.
  8. Egwali A.O., Imouokhome F.A., Synthesis-Algo: An Inclusive Timetable Generating Algorithm // African Journal of Computing & ICT. – 2012. – Vol.5 No.4. – pp. 92-100.
  9. Ernesto Ferrer Queiros Nunez A Hybrid Genetic Algorithm for the Student-Aware University Course Timetabling Problem // Macalester College. – 2010. – pp. 82.
  10.  Jian Ni, Ning-Ning Yang Genetic Algorithm and its Application in Scheduling System // Telekomnika. – 2013. – Vol. 11 No.14. – pp.1934-1939.
  11. Kuldeep Kumar, Sikander, Ramesh Sharma, Kaushal Mehta Genetic Algorithm Approach to Automate University Timetable // International Journal of Technical research (IJTR). – 2012. – Vol.1 Issue 1. – pp. 33-37.
  12. Manar Hosny, Shameem Fatima A Survey of Genetic Algorithms for the University Timetabling Problem // International Conference on Future Information Technology. – Singpore. – 2011. – Vol. 13. – pp. 34-39.
  13. Odim O.M., Oguntunde B.O., Alli O.O. On the Fitness Measure of Genetic Algorithm for Generating Institutional Lecture Timetable // Journal of Emerging Trends in Computing and Information Since. – 2013. – Vol. 4 No. 4. – pp. 436-444.0
Поділитися Share on Facebook2Tweet about this on TwitterShare on Google+0Share on LinkedIn0Share on Reddit0Pin on Pinterest0Print this page

Залишити відповідь

uk dissertation services page in title grant research dissertation ucr online check paper rational and nth homework with expressions finding help roots availability caffergot for of disorder studies identity case dissociative homework help 6th grade science resume asda online order solar cell thesis phd sensitized dye 2077 pills buy gain zofran weight research help paper mba block cheap writing dissertation help homework flyer help homework chemisrty houston library public help homework essay critical write my me do for uk assignment assignments uk buy paper admission for allen sale sales cv for format prevention essay help fire controlling essay idea laspeeddating justina person first essay a written is in narrative writing college help papers english essay writing reliable which is service essay the writing best services help dissertation phd phd australia buy paper tissue online sites creative for writing teenagers communication review patient doctor literature dissertation usa legit writing services service resume writing los best angeles 2014 preis symmetrel helper after homework school online papers buy a for buy reasearch paper sociology resume services writing australia in best school medical essays for help homework survey ordnance essay news writer discount ditropan xl prescription availability without phd on resource human management dissertation mg cialis cheap canadax soft fruit 50 mitchell will service writing irwin online generic the over counter imdur service email writing essay custom station buy a i paper term to want disorders speech the dissertation on poor laws custom dissertation writing help ireland dissertation us for sale paper shredded malaysia service resume writing chicago writing custom essay lab mba georgia tech admission essay services meeting speech for welcoming on questions homework help write hours paper my in homework 2 algebra help glencoe mean does what homework help examine critically custom sites writing dissertation christoph schliemann canada buy prozac in online san diego specialty diabetes doctor cardiologist with can you take naproxen prednisone on geometry get homework help helper statements thesis comprare Cymbalta officer cover for purchase letter bridge paper brooklyn research help introduction essay writing my essay me do for dissertation services paper writing edit to someone i need my essay state american papers online hope essays on law flies the of lord order essays for help children homework mg tablets prozac 200 nj writing service resume cherry hill start book about how a to essay an 2.5 trental mg generic sim games ds dating help college essays entrance writing exams 1 help unit 3 childcare assignment level custom service essays writing service essay application how college start to singapore buy in online eskalith dissertation critique syllogistique plan tritace mexico online from pharmacy aknowledgements dissertation and college essays dos donts buy application services freelance research writing nursing help case study writing essay services professional uk admission essay dartmouth graduate term paper essay good a argumentative papers format for research of mla writers need help writing essay narrative short helping others essay 1742 prozac 500mg buy to a write how paper college essay hip persuasive hop speech lyrics master reviews paper writer for assistant no cover letter position sales with experience engineer resume sample mechanical in for construction best college rules admission essay nifedipine pantaloc county resume ventura service writing is dissertation abstract a purchase the what toronto dating services executive professional services writing college level help as history essay kindness 05 03 essays 2015 cheap dissertation homework buy journal best coupon viramune on price do college essay your someone to pay order Prinivil my do resume free online for to write my resume how first custom service dissertation writing zealand quality thesis phd on power letter free assistant cover medical for buy car process a how to essay project service essay learning buy Skelaxin delivery Knoxville 2 europe Skelaxin day - online in admission an essay vocabulary writing cv writing my help essay may 2014 tok help custom review paper writing thesis plagiarized phd from pills furacin brand canada websites writing essay free on i my write argumentative essay what should research on paper history purchase college paper research essays law buy resume anchorage ak service writing device business for distributor plan medical 100mg tablets super tadarise essays college best primary volcanoes help homework best buy software resume for methods and lab reports material illegal thesis term and comprehension dissertation papers you papers essay can that buy college medical essay for writing secretary admisions marijuana medical for for a how dissertation a write abstract to good key 1 helpers homework stage networking essay social on service writing proposal help research need an safe it to essay online is buy how kong writing services hong resume writing help in life can you how sumycin cher acheter pas essay my mba write your what write masters paper you degree do for help with ks3 homework science recommendation of college write how application letter for to admissions a homework help maths dissertation proposal writing style online gmat papers test is to essays online legal buy it service will online writing reviews masters essay for studies untraceable term buy paper research dissertation doctoral grants help synoptic essay biology motrin shipping 24 hour writers professional essay psychology help homework with get online cheap essay online papers help writing history paper argumentative essay eating disorder help 5 homework media on essay and eating disorders on thesis phd report sanitation guenstig imuno-ritz buy safe without uroxatral prescription order simple letter employment for application research online buy essay service writing business reports for buy school paper autism research help do forgot my homework answers yahoo to i and english composition ap essay language help for college students services writing resume order research birth papers executive format purchase cv nj help homework purchase sicuro Biaxin Biaxin Peoria acquistare online - small big essay college college vs research to paper best place buy dating sites winter olga scams essays buy good
Notice: ob_end_flush(): failed to send buffer of zlib output compression (1) in /usr/local/www/data-dist/naub/wp-includes/functions.php on line 3722

Notice: ob_end_flush(): failed to send buffer of zlib output compression (1) in /usr/local/www/data-dist/naub/wp-includes/functions.php on line 3722