Використання генетичних алгоритмів для складання розкладу (стр. 1 из 3)
Міністерство освіти і науки України
Чернівецький національний університет
імені Юрія Федьковича
Факультет комп’ютерних наук
Кафедра комп’ютерних систем і мереж
Використання генетичних алгоритмів
для складання розкладу
Реферат
2007
Анотація
В даному документі описана програма, призначена для створення та оптимізації розкладу занять для факультетів вищих навчальних закладів, розроблена в середовищі Borland Delphi 7. Розглянуто алгоритми роботи програми в цілому, а також алгоритми роботи її окремих модулів. Представлено графічний вигляд екранних форм програмних модулів.
Програмний документ містить: розділів - 3, сторінок - 27.
Зміст
Використовувані технічні засоби
Загальні відомості
Тема розробки: „Використання генетичних алгоритмів для складання розкладу", умовне позначення теми розробки 482.362.80915-71.
Програма для складання розкладу "Schedule" створена в середовищі Delphi 7 і розрахована на роботу в мережі за протоколами TCP, SPX або NamedPipe. Вона призначена для автоматичного створення розкладу занять для стаціонарної форми навчання на один факультет. Програма розроблена для операційних систем сімейства Microsoft Windows від Windows 95 до Windows Vista. Мінімальні апаратні вимоги: Pentium 100, 32 Mb RAM, 10 Mb HDD, Microsoft Office 97, але для комфортної роботи бажано мати машину з тактовою частотою не менше 800 MHz (основна потужність процесора використовується при оптимізації, якщо розклад оптимізується вручну - достатньо мінімальної конфігурації).
Для роботи програми "Schedule" необхідно:
1. Встановлений та налаштований сервер баз даних FireBird 1.5 на серверній машині.
2. База даних.
3. Наявність зв’язку по мережі клієнтської машини з серверною.
4. Встановлена та налаштована програма "Schedule" на клієнтській машині.
Можливий варіант роботи сервера і клієнта на одній машині.
Програма має два режими роботи - ручний та автоматичний. В автоматичному режимі вона дозволяє генерувати розклад занять на факультет та оптимізувати його; в ручному режимі лише генерується коректний, але не оптимальний розклад. Користувачу надається можливість після генерування або автоматичної оптимізації змінювати розклад шляхом переміщення комірок з заняттями на вільні місця. Кінцевий варіант розкладу можна зберегти у файл для подальшої роботи або експортувати в Microsoft Excel. Також існує можливість експортувати в Microsoft Word часткові розклади для окремих груп та викладачів.
Функціональне призначення
Дана програма призначена для створення розкладу для факультету вузу на основі навчального навантаження для груп з врахуванням вимог і побажань викладачів, а також наявності приміщень для проведення занять. Розклад складається на один семестр, при цьому враховується можливість навчання по першому і другому тижнях.
Програма забезпечує введення вхідних даних розкладу користувачем та збереження їх в базі даних, складання розкладу на один семестр для факультету вузу, тобто визначення для кожної навчальної групи або підгрупи часу проведення занять, назви навчальної дисципліни, виду заняття, прізвища викладача та місця проведення заняття (наприклад, аудиторії або лабораторії).
Опис логічної структури
Програма складається з 23 модулів, 22 форм, 137 процедур та 3 функцій. Основна логіка програми зосереджена в головному модулі "MainUnit", решта модулів є допоміжними.
За своєю структурою алгоритм програми поділяється на дві великі частини, а саме: алгоритм генерації розкладу та алгоритм оптимізації розкладу. Алгоритм генерації розкладу на основі вхідних даних генерує певний розклад з дотриманням усіх необхідних умов коректності, але який при цьому не є оптимальним. Алгоритм оптимізації на основі неоптимальних генерованих варіантів розкладу оптимізує останній шляхом використання генетичних алгоритмів.
Блок-схему алгоритму програми наведено на рис.3.1
Рис. 3. 1. Блок-схема алгоритму програми
Алгоритм генерації розкладу.
На етапі генерації розкладу спершу вводяться такі поняття, як: заняття для потоку, заняття для групи та заняття для підгрупи. Заняттям для потоку вважається лекція, яка проводиться одним викладачем з одного предмету на одному курсі, але для декількох груп. Заняттям для групи вважається заняття, яке проводиться для усіх підгруп певної групи одним викладачем з одного предмету. Заняття, яке проводиться для окремої підгрупи вважаються заняттям для підгрупи. На основі саме цих даних і відбувається генерація розкладу. Зовнішній вид основної форми програми наведено на рис.3.2 Виділений пункт "Генерувати" головного меню приводить в дію алгоритм генерації розкладу.
Рис. 3. 2. Основна форма програми
Принцип генерації наступний. Спочатку програма з навчального навантаження виділяє заняття для потоків, груп і підгруп. Далі випадковим чином, рівномірно по днях, але якомога ближче до першої пари, розміщуються заняття для потоків, для кожного заняття вибирається приміщення з набору придатних саме для цього заняття. Потім так само розміщуються на вільні місця заняття для груп та підгруп. При цьому враховуються наступні дані: а) кількість годин даного заняття за семестр; б) можливість проведення викладачем даної пари; в) придатність вибраного приміщення для даного заняття; г) чи є вибране приміщення вільним для даної пари.
Рис. 3.3. Блок-схема алгоритму генерації розкладу.
Під час генерації працює процедура, яка випадковим чином міняє місцями робочі тижні деяких пар у 50% пар розкладу. Це дозволяє ще на стадії генерації мінімізувати кількість можливих вікон для студентів та більш компактно розмістити усі види занять. Блок-схему алгоритму генерації розкладу наведено на рис.3.3 Блоки 2 і 3 аналогічні за будовою до блоку 1. Відмінність полягає у використанні змінних Y і Z замість змінної X, а також кількостей груп і підгруп відповідно замість кількості потоків. Згадані блоки містять алгоритми розміщення занять для потоків, груп і підгруп. Величини X, Y і Z є параметрами програми, що можуть бути змінені користувачем і означають, відповідно, кількості спроб вставки у розклад потоків, груп і підгруп. За замовчуванням ці величини встановлюються рівними 200.
Алгоритм оптимізації розкладу.
Програма дозволяє проводити оптимізацію розкладу в автоматичному режимі, тобто без втручання користувача. Вигляд форми, що відображає процес оптимізації розкладу, наведено на рис.3.4.
Рис. 3.4. Вигляд форми, що відображає процес оптимізації розкладу
В основу оптимізації покладено принцип генетичних алгоритмів. Цей принцип полягає у застосуванні основних принципів природної еволюції до математичної моделі задачі. Основними перевагами таких алгоритмів є: можливість застосування до вирішення широкого кола досить складних задач, де інші типи алгоритмів неефективні; знаходження розв’язку, близького до оптимального, за порівняно невеликий час; простота корекції умов оптимізації; можливість контролю процесу оптимізації.
Згідно з принципами генетичних алгоритмів на початку оптимізації відбувається початкова ініціалізація, тобто генерація певної популяції хромосом, що складається з N особин. Кожна хромосома є допустимим, але не оптимальним розв’язком задачі складання розкладу - тобто кожна хромосома є певним розкладом. Далі для кожної хромосоми популяції розраховується цільова, або фітнес-функція, яка є мірою оптимальності даної хромосоми. Потім до популяції застосовуються такі генетичні оператори, як схрещування (кросовер), мутація та вибір (селекція) хромосом. В результаті формується нове покоління (популяція), яка з великою імовірністю містить більш оптимальних представників, ніж попереднє. Генетичні оператори повторюються до виконання умови закінчення оптимізації, після чого з останнього покоління вибирається найкращий представник, конвертується у розклад і вважається розв’язком поставленої задачі. Цей розв’язок не є оптимальним, але близький до оптимального. Отриманий розклад відображається на головній формі програми у вигляді таблиці. Він може змінюватись користувачем в ручному режимі, також може бути збережений у файл для подальшої роботи або експортований у Microsoft Excel у вигляді, придатному для друку та використання. Програма також дозволяє експортувати в Microsoft Word часткові розклади для навчальних груп та окремих викладачів у вигляді, зручному для друку.
Рис. 3.5. Блок-схема алгоритму оптимізації розкладу
Блок-схему алгоритму оптимізації розкладу наведено на рис.3.5 Блок 1 містить початкову генерацію популяції хромосом; блок 2 - оптимізацію популяції методом генетичного алгоритму. Величина N означає розмір популяції, тобто кількість особин, що її формують. Умовою закінчення оптимізації є або закінчення часового проміжку, виділеного на оптимізацію, або синтез певного числа поколінь. Ці величини є параметрами програми і можуть бути змінені користувачем. За замовчуванням часовий проміжок встановлюється рівним 10 хв., а максимальна кількість поколінь рівною 10000.