Використання генетичних алгоритмів для складання розкладу

Міністерство освіти і науки України

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

імені Юрія Федьковича

Факультет комп’ютерних наук

Кафедра комп’ютерних систем і мереж

Використання генетичних алгоритмів

для складання розкладу

Реферат

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.

Використовувані методи

.

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

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

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

Структура програми

.

З точки зору моделі прецедентів структура програми виглядає наступним чином. Користувачеві надається можливість виконувати основні дії, передбачені в програмі, а саме: а) генерувати розклад; б) генерувати та оптимізувати розклад; в) змінити розклад в ручному режимі; г) завантажити розклад з файлу; д) змінити або додати початкові дані. Існують додаткові дії, які залежать від основних, а саме: а) зберегти розклад у файл; б) експортувати розклад у Microsoft Excel; в) експортувати часткові розклади у Microsoft Word.

UML-діаграма прецедентів програми зображена на рис.3.6.

Рис. 3.6. Діаграма прецедентів програми

Зв’язки програми з іншими програмами
.

Програма "Schedule" тісно пов’язана з таким програмним продуктом фірми Microsoft, як Microsoft Office. Так, готовий розклад, створений за допомогою програми "Schedule", за допомогою відповідної команди експортується в Microsoft Excel з форматуванням, необхідним для його подальшого друку та використання. Програма "Schedule" також надає користувачеві можливість експортувати в Microsoft Word часткові розклади для будь-якої групи або викладача. Часткові розклади експортуються у вигляді таблиць, оптимізованих для друку або редагування.

Використовувані технічні засоби

Для розробки програмного продукту було використано комп’ютер наступної конфігурації:

Центральний процесор - Pentium IV, 3.0 GHz (1 MB L2-Cache, 800 MHz FSB, PGA-478 Pkg);

Материнська плата - Gigabyte GA-8IPE1000-G;

Оперативна пам’ять - 512 MB;

Жорсткий диск - Seagate Barracuda ST3200822AS SATA 200 GB;

Графічний адаптер - ATI Radeon 9600 Pro (Sapphire).

Виклик і завантаження

Програма "Schedule" може бути викликана стандартними методами, прийнятими в операційній системі Microsoft Windows, а саме: подвійним натисканням лівої кнопки маніпулятора "миша" в момент перебування його вказівника на значкові програми або ярлика до неї; натисканням на клавіатурі клавіші "Enter" або "Return" після активування значка або ярлика (підсвічування синім кольором). Для цієї мети доцільно використовувати можливості багаточисленних файлових менеджерів (напр., Far Manager або Total Commander). Після коректного інсталювання програми ярлик для її виклику додається в меню "Пуск". Також існує можливість виклику програми з одним параметром з командного рядка. В ролі параметру необхідно вказати ім’я файлу з розкладом, який буде негайно відкрито програмою. Під час інсталювання програми "Schedule" виконавчий модуль дистрибутива створює асоціацію програми з файлами типу ". bsc" - від "Binary Schedule" - бінарний файл з розкладом. Тому при спробі завантаження такого файлу також викликається програма "Schedule", за допомогою якої даний файл негайно відкривається для подальшої роботи з ним (по аналогії з документами Microsoft Word).

Вхідні дані

Вхідними даними для програми "Schedule" є дані, що зберігаються в базі даних (Рис.6.16) і параметри розкладу (Рис.6.13), програми (Рис.6.14) та бази даних (Рис.6.15), які зберігаються в системному реєстрі. При наявності файлів із збереженим розкладом вони також можуть виступати в ролі вхідних даних. База даних працює під керуванням СКБД FireBird 1.5, встановленої на серверній машині, що має зв’язок по мережі з клієнтською машиною, на якій знаходиться програма. Остання надає можливість змінювати, додавати та видаляти будь-які з вказаних даних за допомогою відповідної кількості непов’язаних між собою екранних форм, що дозволяє користувачеві порівнювати та оцінювати одночасно декілька блоків даних.

В базі даних міститься наступна інформація:

Викладачі (Рис.6.1).

Прізвище.

Ім’я.

По-батькові.

Посада.

Науковий ступінь.

Коротка інформація.

Зайнятість (відсутність можливості проводити певні пари в певні дні).

Групи (Рис.6.2).

Номер групи.

Курс.

Спеціальність.

Кількість студентів.

Кількість підгруп.

Приміщення (Рис.6.3).

Номер.

Назва.

Вид.

Кількість робочих місць.

Навчальний корпус.

Спеціальності (Рис.6.4).

Назва.

Дисципліни (Рис.6.5).

Назва.

Види занять (Рис.6.6).

Назва.

Навчальне навантаження (Рис.6.7).

Порядковий номер.

Група.

Дисципліна.

Вид заняття.

Кількість підгруп.

Номер підгрупи.

Кількість годин за семестр

Викладач.

Придатність приміщень (Рис.6.8).

Дисципліна.

Вид заняття.

Максимально придатні приміщення.

Придатні приміщення.

Непридатні приміщення.

Види приміщень (Рис.6.9).

Вид приміщення.

Вид заняття, якому відповідає вид приміщення.

Посади (Рис.6.10).

Назва посади.

Скорочена назва посади.

Наукові ступені (Рис.6.11).

Назва.

Навчальні корпуси (Рис.6.12).

Назва.

Номер.

Параметрами розкладу та програми є наступні величини.

Параметри розкладу (Рис.6.13):

Кількість робочих днів у тижні.

Кількість пар у день.

Параметри програми (Рис.6.14):

Параметри початкової генерації.

Кількість спроб вставки потоку.

Кількість спроб вставки групи.

Кількість спроб вставки підгрупи.

Кількість спроб генерування розкладу.

Параметри генетичного алгоритму.

Максимальна кількість поколінь.

Максимальний час процесу оптимізації.

Імовірність мутації.

Процент мутацій в хромосомі.

Кількість спроб кросоверу потоків.

Кількість спроб кросоверу груп.

Кількість спроб кросоверу підгруп.

Рис. 6.1 Форма "Викладачі"

Рис. 6.2. Форма "Групи"

Рис. 6.3. Форма "Приміщення"

Рис. 6.4. Форма "Спеціальності"

Рис. 6.5. Форма "Дисципліни"

Рис. 6.6. Форма "Види занять"

Рис. 6.7. Форма "Навчальне навантаження"

Рис. 6.8. Форма "Придатність приміщень"

Рис. 6.9. Форма "Види приміщень"

Рис. 6.10. Форма "Посади"

Рис. 6.11. Форма "Наукові ступені"

Рис. 6.12. Форма "Навчальні корпуси"

Рис. 6.13. Форма "Параметри розкладу"

Рис. 6.14. Форма "Параметри програми"

Рис. 6.15. Форма "База даних"

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

Оскільки розроблена програма є клієнт-серверною системою, існує можливість одночасного редагування даних декількома клієнтами, тобто, за допомогою декількох копій програми, запущених на різних машинах, що мають зв’язок по мережі з сервером баз даних. В цьому випадку, так само, як і в усіх інших, керувати даними (доступом, зміною, розв’язанням накладок та ін) буде СКБД FireBird, що виключає виникнення колізій, наприклад, при спробі зміни одних даних різними користувачами. Така архітектура забезпечує додаткові можливості програми, такі, як: незалежне внесення даних різними кафедрами; можливість перегляду/експорту розкладу або часткових розкладів на кафедрах; створення певної кількості користувачів та надання їм різних рівнів та привілеїв доступу до даних.

Рис. 6.16. Спрощена структура таблиць бази даних

Вихідні дані

Основними вихідними даними програми "Schedule" є розклад занять для факультету вищого навчального закладу (рис.7.1). Розклад може бути або експортований в Microsoft Excel, або збережений у спеціальний бінарний файл з розширенням ". bsc". Файл складається з блоків розміром по 80 bit, де кожен з них містить вичерпну інформацію щодо однієї комірки розкладу. Блок складається з 5-ти цілих чисел по 16 bit, що означають наступне:

Номер вибраного типу заняття;

Тип заняття;

Приміщення;

Дисципліна;

Викладач.

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

Додатковими вихідними даними програми є часткові розклади для окремих груп і викладачів, що можуть бути експортовані в Microsoft Word (рис.7.2).

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

Рис. 7.1. Фрагмент розкладу, експортованого в Microsoft Excel

Рис. 7.2. Фрагмент часткового розкладу, експортованого в Microsoft Word.

Рис. 7.3. Форма "Звіти"

Для зручності користувача розроблено інсталяційний пакет, який забезпечує коректне встановлення програмного продукту, зокрема із внесенням відповідних змін та початкових параметрів програми у реєстр Windows (рис.7.4).

Рис.7.4. Інсталяція програми.

Список літератури

1. Холл М. Сервлеты и JavaServer Pages. Библиотека програмиста. - СПб.: Питер, 2001. - 496.

2. JavaServer Pages™ Specification version 2.0. - Sun Microsystems, 2003. - 765.

3. Грофф Дж., Вайнберг П. SQL: Полное руководство: Пер. с англ. -К BHV, 2001. - 816.