Використання генетичних алгоритмів для складання розкладу
Информация - Компьютеры, программирование
Другие материалы по предмету Компьютеры, программирование
о заняття вибирається приміщення з набору придатних саме для цього заняття. Потім так само розміщуються на вільні місця заняття для груп та підгруп. При цьому враховуються наступні дані: а) кількість годин даного заняття за семестр; б) можливість проведення викладачем даної пари; в) придатність вибраного приміщення для даного заняття; г) чи є вибране приміщення вільним для даної пари.
Рис. 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-повних задач, для знаходження близького до оптимуму розвязку було використано один із сучасних методів розвязування подібних задач - метод генетичних алгоритмів. Цей метод показує непогану ефективність, коли звичайні методи перебору малоефективні.
Також були використані методи нечіткої (розмитої) логіки, а саме для опису деяких типів частково невизначених початкових даних. Наприклад, бажаність проведення заняття у певний день тижня для викладача або придатність певного приміщення для даного заняття - ці величини можна описати дійсним числом, яке знаходиться у визначеному діапазоні.
Крім описаних вище були реалізовані стандартні методи мовної локалізації та побудови інтерфейсу програми, зберігання та зчитування параметрів і налаштувань, а також звязку з іншими програмами.
Структура програми.
З точки зору моделі прецедентів структура програми виглядає наступним чином. Користувачеві надається можливість виконувати основні дії, передбачені в програмі, а саме: а) генерувати розклад; б) генерувати та оптимізувати розклад; в) змінити розклад в ручному режимі; г) завантажити розклад з файлу; д) змінити або додати початкові дані. Існують додаткові дії, які залежать від основн