Реферат за темою магістерської роботи
Вступ .
1. Мета дослідження, плановані результати .
3. Огляд досліджень і розробок .
Висновки .
.
Вступ
.Організація навчального процесу у вищому навчальному закладі є основою підготовки висококваліфікованих фахівців. Базисом навчального процесу навчання є складання "оптимального" розкладу навчальних занять. Розклад навчальних занять має задовольняти вимогам щодо забезпечення все більш зростаючих вимог до майбутніх спеціалістів. Існує достатня кількість програмних комплексів для складання навчальних розкладів. Перші програми автоматизованого складання розкладів навчальних занять з'явилися на початку 90-х років. На жаль, лише невелика їх частина реально використовується в навчальних закладах різного рівня. Головними проблемами залишаються: висока трудомісткість отримання рішень, недосконалість технології проектування розкладу, низька ергономічність процедури і високі тимчасові витрати [1].
1. Мета дослідження, плановані результати
.Завдання автоматизації складання розкладів–одна з тих завдань, які здавна турбували душу математиків і програмістів. Широкі розробки в цьому напрямі велися з початку XX століття.
З розвитком комп'ютерної техніки та комп'ютерних обчислень дуже багато завдань намагалися перевести на автоматизований, а в кращому випадку і повністю автоматичний режим обчислення. Не дивно, що з середини 90-х років починається справжній бум на реалізацію програм автоматичного складання розкладу. Таких програм було безліч, вони реалізовували різні алгоритми, однак зі своїм завданням вони абсолютно не справлялися. Результати робіт цих програм видавали в більшості своїй такі мінуси:.
1) Довгий час роботи. Користувач міг запустити програму на виконання, піти додому, а через тиждень отримати повідомлення, про неможливість суміщення годин, хоча диспетчера цей навчальний план розташовували в сітку розкладу навіть із запасом.
2) Незручний інтерфейс та завантаження бази даних.
3) Абсолютно незручні розклади і для студентів, і для викладачів.
4) Крайнє затрудження розрахунку, якщо предмет припускає розподіл групи на підгрупи і ділення тижнів на парну / непарну.
У результаті всього цього були висунуті деякі теорії, які свідчили, що завдання не має рішення, оскільки лежить в області міжособистісних відносин, а тому не може бути вирішена шляхом алгоритмізації і подальшої автоматизації [1].
При розробці алгоритмів автоматизованого складання розкладу занять гостро стоїть проблема створення універсальних алгоритмів, що враховують специфіку умов кожної конкретної задачі. Такі алгоритми мають бути достатньо "гнучкими", тобто без істотного їх зміни можна було б включати і виключати вимоги з системи вимог до розкладу. Проте спроба вирішувати задачу яким одним єдиним універсальним алгоритмом на даний момент не представляється можливою. Алгоритми, що дозволяють вирішувати широкий клас задач, не дають тієї ефективності, яку забезпечують більш конкретні, адаптовані з урахуванням конкретних умов алгоритми.
Для систем складання розкладу занять характерна сильна залежність від специфіки конкретних навчальних закладів вже на рівні математичних моделей і представлення даних, що ускладнює використання типових систем. Систему, створену в одному вузі, зазвичай без зміни і доопрацювання неможливо ефективно використовувати в іншому. До того ж багато з них створювалися досить давно і з їх допомогою неможливо ефективно вирішувати поставлену задачу [2].
Метою даної роботи є аналіз основних методів автоматизації складання розкладу. Проаналізувавши основні методи автоматизованого складання розкладів ми можемо вибрати те, яке в майбутньому будемо використовувати для побудови автоматичної системи побудови першої версії розкладу в АСК "Деканат" ФКНТ ДонНТУ. Це і буде результатом роботи.
.
2. Постановка завдання
.Формально завдання складання розкладу можна розглядати наступним чином: Задані:.
• Множина викладачів.
• Множина груп.
• Множина аудиторій.
• Множина предметів.
• Навчальний план.
Також можуть бути висунуті два низки вимог до розкладу:.
• Жорсткі або обов'язкові вимоги:.
o Для певних пар потрібні місткі аудиторії (наприклад, потокові лекції).
o Для певних пар потрібні аудиторії зі спеціальним обладнанням (наприклад, аудиторії з аналого-обчислювальними комплексами для практичних занять з предметів, пов'язаними з електронікою).
• М'які вимоги:.
o Відсутність вікон у студентів.
o Відсутність вікон у викоадачів.
o Мінімальна кількість переїздів між групами корпусів, якщо університетське містечко знаходиться не в одному місці (наприклад, Донецький Національний Технічний Університет має 3 групи корпусів досить віддалених один від одного).
o Лекції повинні бути вранці, практичні заняття–на останніх парах.
o Рівномірне навантаження студентів.
o "Бібліотечні" дні для викладачів.
o Інші умови.
Як видно з постановки, оцінити якість розкладу можливо, тільки після його повного складання.
Сама завдання дуже важка, і деякими вченими названа "завданням без рішення". Поглянувши на малюнок № 1 ви можете побачити як багато частин у цій безумовно нелегкій справі.
.
Рис. №1 Основні компоненти моделей складання розкладів [4].
Для вирішення поставлених проблем, потрібна побудова гнучкою і легко адаптується системи на основі нових принципів, з використанням сучасних комп'ютерних технологій. Необхідна система, складова розклад відповідно до обраних критеріїв і заданими вимогами, тобто що бере на себе якомога більше функцій людини, щоб розклад доводилося менше доводити вручну. Дані можливості повинні здійснюватися також, без зміни початкового коду системи, щоб використовуватися користувачами-непрограмістів. Для покриття найбільш типових випадків, необхідний аналіз і застосування кількох типових алгоритмів, що реалізують складання розкладів. Потрібна система підтримки прийняття рішень, що має можливість налаштування, в ідеалі що бере на облік всі можливі обмеження і побажання.
Дана система повинна:.
• мати можливість доповнення і зміни існуючої бази даних.
• мати можливість доповнення і зміни інтерфейсу користувача.
• забезпечувати можливість самостійно підключення додаткових самостійно розроблених алгоритмів, можливо з викликом деяких надаються системою типових алгоритмів.
Все це давало б можливість задавати в кожному вузі вимоги, що відповідають його умовам, і, за допомогою підбору і настройки підходящого алгоритму, отримувати необхідний розклад.
3. Огляд досліджень і розробок
.У теорії розкладів виділяють такі групи методів вирішення завдань.
• Точні методи (методи на основі повного перебору) До них відносяться методи лінійного програмування, алгоритми цілочисельного програмування Гомори, в якому передбачається, що всі коефіцієнти у виразах і цільової функції є цілими числами. Якщо врахувати неподільність окремих видів робіт і ресурсів, комбінаторний характер операцій, з яких складається розклад, то такий метод має певні можливості.
• Наближені методи.
Їх можна розбити на наступні групи:.
o методи локальної оптимізації.
o модифікації точних методів.
o евристичні методи, максимально враховують специфіку розв'язуваних завдань.
o методи випадкового пошуку.
o методи, що поєднують локальну оптимізацію з випадковим пошуком.
Відзначимо, що багато наближені алгоритми дозволяють вирішувати завдання дискретної оптимізації в діалоговому режимі. Це дає можливість в залежності від виділених ресурсів (часу, пам'яті комп'ютера тощо) послідовно покращувати отримане рішення шляхом зміни всіх або деяких вихідних даних. Значна частина наближених алгоритмів дискретної оптимізації базується на використанні обчислювальних схем відомих точних методів, таких як метод гілок і меж, послідовного аналізу варіантів і інших. Одними з найбільш розвинених наближених методів є методи локальної оптимізації, мають на меті відшукання локально оптимальних рішень.
Нерідко в цих методах на певних етапах рішення задачі використовуються методи випадкового пошуку, а також різні способи (евристики), які дають можливість скоротити хід варіантів і максимально враховують специфіку завдання. Слід зазначити, що алгоритми, в яких комбінуються різні ідеї, на практиці часто виявляються найбільш ефективними. За допомогою цих методів були вирішені численні складні завдання класифікації об'єктів, розміщення, планування і проектування. Основна перевага цих методів–простота реалізації, а основний недолік–це те, що вони не можуть адаптуватися до умов розв'язуваної задачі. Значно більш гнучкими є методи, у яких імовірнісний закон залежить від результатів попередніх випробувань і змінюється від ітерації до ітерації. Це методи випадкового пошуку з навчанням.
У своїй роботі я проаналізую 4 базових алгоритму, які використовуються найчастіше в задачах автоматизації складання розкладів, метод перебору, метод кордонів і гілок, генетичний метод, евристичні методи.
3.1. Метод перебору
.Метод перебору або метод рівномірного пошуку-найпростіший з методів пошуку значень. Будь-яку задачу побудови алгоритму можна вирішити за допомогою цього методу, однак складність перебору залежить від кількості умов завдання.
Метод перебору інтуїтивно простий і зрозумілий. Його єдина перевага в порівнянні з іншими методами–він ГАРАНТОВАНО дасть вам ідеальне рішення, якщо воно звичайно існує, навіть з урахуванням всіх обмежень і вимог.
Суть цього методу–спробувати абсолютно всі комбінації і перестановки в сітці розкладів.
Звідси випливають такі характеристики цього методу: він простий, він гарантує результат, при його існування, він ідеально ефективно справляється з малими завданнями, наприклад складання розкладу для початкової школи, де 3 паралелі по 4 класу в кожній.
Єдиний мінус, який перекреслює всі переваги, цього методу випливає з його плюсів: цей метод абсолютно неефективний при збільшенні кількості умов. Якщо для розкладу початкової школи цей метод ефективний, то для розкладу вже всієї школи–результату доведеться чекати вже набагато більшу кількість часу. Для Донецького національного технічного університету з сотнями груп, викладачів, аудиторій та предметів, перебір може тривати століття. Адже кількість варіантів для однієї тільки групи 2 * 25! (2 тижні по 5 занять 5 разів на день). Тому цей метод вважається дуже невдалим для заданої задачі.
3.2 Метод гілок і меж
.Метод гілок і меж (англ. branch and bound)–загальний алгоритмічний метод для знаходження оптимальних рішень різних задач оптимізації, особливо дискретної і комбінаторної оптимізації. По суті, метод є варіацією повного перебору з відсівом підмножин допустимих рішень, свідомо не містять оптимальних рішень.
Метод гілок і меж–один з комбінаторних методів. Його суть полягає в упорядкованому переборі варіантів і розгляді лише тих з них, які виявляються за певними ознаками перспективними, і відкиданні безперспективних варіантів.
Метод гілок і меж полягає в наступному: безліч припустимих рішень (планів) деяким способом розбивається на підмножини, кожне з яких цим же способом знову розбивається на підмножини. Процес продовжується до тих пір, поки не отримано оптимальне цілочисельне рішення вихідної задачі.
В основі методу гілок і меж лежить ідея послідовного розбиття множини допустимих рішень на підмножини (стратегія "розділяй і володарюй"). На кожному кроці методу елементи розбиття піддаються перевірці для порівняння підмножини і з'ясування, оптимальне це рішення чи ні. Перевірка здійснюється за допомогою обчислення оцінки знизу для цільової функції на даному підмножині. Якщо оцінка знизу не менше рекорду–найкращого зі знайдених рішень, то підмножина може бути відкинуто. Проверяемое підмножина може бути відкинуто ще і в тому випадку, коли в ньому вдається знайти найкраще рішення. Якщо значення цільової функції на знайденому вирішенні менше рекорду, то відбувається зміна рекорду. По закінченню роботи алгоритму рекорд є результатом його роботи.
Якщо вдається відкинути всі елементи розбиття, то рекорд–оптимальне рішення задачі. В іншому випадку, з неотброшенних підмножин вибирається найбільш перспективне (наприклад, з найменшим значенням нижньої оцінки), і воно піддається разбиению. Нові підмножини знову піддаються перевірці і т.д.
Аналізуючи цей метод ми можемо зрозуміти, що, хоч він і заснований на переборі, він перебирає набагато менше варіантів, ніж його "батько"–метод повного перебору.
Мінуси методу–він уже не настільки простий, як метод повного перебору, він важко застосовується до теорії розкладу занять, він все ще занадто довгий з виконання.
3.3 Генетичний алгоритм
.Генетичний алгоритм (англ. genetic algorithm)–це алгоритм пошуку, використовуваний для вирішення завдань оптимізації та моделювання шляхом випадкового підбору, комбінування і варіації шуканих параметрів з використанням механізмів, що нагадують біологічну еволюцію. Є різновидом еволюційних обчислень, за допомогою яких вирішуються оптимізаційні задачі з використанням методів природної еволюції, таких як успадкування, мутації, відбір і кросинговер. Відмінною особливістю генетичного алгоритму є акцент на використання оператора "схрещування", який виробляє операцію рекомбінації рішень-кандидатів, роль якої аналогічна ролі схрещування в живій природі.
Інтенсивно розвиваються останнім часом методи вирішення великорозмірних завдань цілочисельного програмування, об'єднаних терміном "генетичні алгоритми". Основні відмінності та переваги генетичних алгоритмів у порівнянні з класичними методами полягають у наступному: .
–генетичний алгоритм (ГА) працює з кодами, в яких представлений набір параметрів, що прямо залежать від аргументів цільової функції; .
–в процесі пошуку ГА використовує кілька точок пошукового простору (процес розпаралелюється), а не переходить від точки до точки, як це відбувається в традиційних методах, тобто ГА оперує з усією сукупністю допустимих рішень; .
–ГА в процесі роботи не використовує додаткової інформації, що підвищує швидкість його роботи; .
–ГА використовує як імовірнісні правила для породження нових точок пошуку, так і детерміновані правила для переходу від одних точок до інших і ін .
Генетичний алгоритм складається з наступних компонент: .
–Хромосома. В якості хромосоми виступає рішення розглянутої задачі. Хромосома складається із сукупності генів–параметрів.
–Початкова популяція хромосом.
–Набір операторів для генерації нового покоління. Генетичними операторами є оператор кросовера (crossover operator) і оператор мутації (mutation operator). За рахунок кросовера проводиться обмін генами між особинами, тобто процес схрещування особин. Хай є дві батьківські особини з хромосомами X = {xi, I = 1, N} і Y = {yi, I = 1, N}.
–Випадковим чином визначається точка розриву (crossover point), всередині хромосоми, в якій обидві хромосоми діляться на дві частини і обмінюються ними.
–Оператор мутації інвертує випадково обраний біт (ген) в хромосомі.
–Цільова функція для оцінки пристосованості (fitness) рішення.
.
Рис.2 схема праці генетичного алгоритма.
.
Рис. №3 схема праці генетичного алгоритма. Анімація (21 кадр, 1 повторення).
Генетичні алгоритми мають недоліки, які можна представити у вигляді трьох груп: .
• Завершення роботи генетичного алгоритму відбувається по досягненню заданого (не завжди обгрунтованого) числа ітерацій, що в ряді випадків перешкоджає пошуку кращого розкладу.
• Слабкий врахування специфіки задачі складання розкладу навчальних занять при організації її вирішення за допомогою генетичних алгоритмів. Так, у відомих генетичних алгоритмах складання розкладу занять не враховується наявність зв'язків між об'єктами розкладу та велике різноманіття описів самих об'єктів розкладу.
До плюсів же цього методу можна віднести те, що він дає оптимальне рішення в 99% випадків і досить швидкий [1].
3.4 Евристичні алгоритми
.Евристичний алгоритм–це алгоритм вирішення задачі, правильність якого для всіх можливих випадків не доведена, але про який відомо, що він дає досить хороше рішення в більшості випадків. Насправді може бути навіть відомо (тобто доведено) те, що евристичний алгоритм формально невірний. Його все одно можна застосовувати, якщо при цьому він дає невірний результат тільки в окремих, досить рідкісних і добре виділяються випадках, або ж дає неточний, але все ж прийнятний результат.
Простіше кажучи, евристика–це не повністю математично обгрунтований (або навіть "некоректний"), але при цьому практично корисний алгоритм.
Вона не гарантує знаходження рішення, навіть якщо воно явно існує (можливий "перепустку мети").
Евристичні алгоритми грунтуються на прийомі, який називається прийомом зниження вимог. Він полягає у відмові від пошуку оптимального рішення за прийнятний час. Евристичні алгоритми використовують різні розумні міркування без строгих обгрунтувань, тому досить складно зробити узагальнення евристичних методів. Стикаючись з конкретним завданням, людина може обдумувати спосіб отримання рішення, що володіє невисокою вартістю, дуже мало піклуючись при цьому про теоретичному обгрунтуванні.
Завдання складання розкладу зводиться до задачі задоволення обмежень. Процес складання розкладу представляється як процес розподілу часу і місця між заняттями таким чином, щоб виконувалося безліч обмежень. Зазвичай для цього задається безліч правил. Даний метод передбачає "жорсткі" (hard) і "м'які" (soft) обмеження. Виконання "жорстких" обмежень обов'язково, а "м'яких" бажано. На кожному кроці розставляються одна група або курс. Якщо на якомусь кроці неможливо призначити час або аудиторію таким чином, щоб не порушилися обмеження, то послаблюється одне з "м'яких" обмежень. І так повторюється до тих пір, поки не стане можливим призначити час або аудиторію без порушень обмежень, що залишилися. Недоліком цього методу є те, що не завжди можна розставити групу або курс і тому це доводиться робити вручну.
Плюси евристичних методів в тому, що при всій своїй довільності і слабкості можуть бути з успіхом застосовані для вирішення завдань високої обчислювальної складності (задачі, що належать класу NP). Наприклад, у методі гілок і меж евристичні алгоритми застосовуються як засіб отримання початкових рішень і верхніх оцінок.
Мінуси ж евристичних методів в тому, що вони не гарантують знаходження кращого рішення і вони не гарантують знаходження рішення, навіть якщо воно явно існує (можливий "перепустку мети").
Висновки
.Проаналізувавши алгоритми автоматизації складання розкладів можна зробити наступні висновки: .
• Існуючі методи складання розкладу можна розбити на дві групи: повний перебір (точні методи) і методи скорочення повного перебору (наближені методи).
• Вибір алгоритму безпосередньо залежить від умов поставленої задачі. Для задачі розкладу–це кількість і вид ресурсів, завдань і обмежень.
Таким чином ми можемо зрозуміти, що для успішної реалізації ідеї автоматичного складання розкладу з впровадженням її в АСК "Деканат" Донецького Національного Технічного Університету перед початком роботи необхідно точно дізнатися: .
• навчальний план.
• кількість аудиторій.
• м'які і жорсткі обмеження.
Список использованной литературы.
Список использованной литературы.
1. Сипко Е.Н. Метод последовательного анализа вариантов решения задачи составления расписания занятий, 2011 г. [Электронный ресурс]. URL:http://archive.nbuv.gov.ua/portal/natural/ii/2011/AI_2011_1/2/00_Sipko.pdf<
2. Бартенев А.С. Обзор основных вопросов автоматизированного составления расписания занятий в высшем учебном заведении. // Современные научные исследования и инновации. – Сентябрь, 2011 [Электронный ресурс]. URL: http://web.snauka.ru/issues/2011/09/2576
3. Каширина И.Л. Генетический алгоритм решения квадратичной задачи о назначениях специального вида. // Вестник ВГУ, Серия физика, математика, 2003, №1. [Электронный ресурс]. URL:http://www.vestnik.vsu.ru/pdf/physmath/2003/01/kashirina.pdf
4. Топорков В.В. Модели распределенных вычислений, М.: ФИЗМАТЛИТ, 2004. 218 стр.
5. Береговых Ю.В., Васильев Б.А., Володин Н.А. Алгоритм составления расписания занятий, Государственный университет информатики и искусственного интеллекта, г. Донецк, Украина. [Электронный ресурс]. URL: http://archive.nbuv.gov.ua/portal/natural/ii/2009_2/2%5C00_Beregovykh_Vasilev_Volodin.pdf
6. Лазарев А.А., Методы и алгоритмы решения задач теории расписаний для одного и нескольких приборов и их применение для задач комбинаторной оптимизации, Научная библиотека диссертаций и авторефератов disserCat http://www.dissercat.com/content/metody-i-algoritmy-resheniya-zadach-teorii-raspisanii-dlya-odnogo-i-neskolkikh-priborov-i-ik#ixzz2OqtZiCN6
7. Коффман Э.Г. Теория расписаний и вычислительные машины, М; Наука, 1984. 87-88 стр.
8. Танаев В.С., Шкуба В.В. Введение в теорию расписаний. – М.: Наука, 1975. 139 стр.