Використання генетичних алгоритмів для складання розкладу
Информация - Компьютеры, программирование
Другие материалы по предмету Компьютеры, программирование
Міністерство освіти і науки України
Чернівецький національний університет
імені Юрія Федьковича
Факультет компютерних наук
Кафедра компютерних систем і мереж
Використання генетичних алгоритмів
для складання розкладу
Реферат
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. Основна форма програми
Принцип генерації наступний. Спочатку програма з навчального навантаження виділяє заняття для потоків, груп і підгруп. Далі випадковим чином, рівномірно по днях, але якомога ближче до першої пари, розміщуються заняття для потоків, для кожног