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

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

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

Опис логічної структури

Програма складається з 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-повних задач, для знаходження близького до оптимуму розв’язку було використано один із сучасних методів розв’язування подібних задач - метод генетичних алгоритмів. Цей метод показує непогану ефективність, коли звичайні методи перебору малоефективні.

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