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

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

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

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

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

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

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

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

Реферат

2007

Анотація

В даному документі описана програма, призначена для створення та оптимізації розкладу занять для факультетів вищих навчальних закладів, розроблена в середовищі Borland Delphi 7. Розглянуто алгоритми роботи програми в цілому, а також алгоритми роботи її окремих модулів. Представлено графічний вигляд екранних форм програмних модулів.

Програмний документ містить: розділів - 3, сторінок - 27.

Зміст

Анотація

Загальні відомості

Функціональне призначення

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

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

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

Вхідні дані

Вихідні дані

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

Алгоритм програми

За своєю структурою алгоритм програми поділяється на дві великі частини, а саме: алгоритм генерації розкладу та алгоритм оптимізації розкладу. Алгоритм генерації розкладу на основі вхідних даних генерує певний розклад з дотриманням усіх необхідних умов коректності, але який при цьому не є оптимальним. Алгоритм оптимізації на основі неоптимальних генерованих варіантів розкладу оптимізує останній шляхом використання генетичних алгоритмів.

Блок-схему алгоритму програми наведено на рис.3.1

Рис. 3. 1. Блок-схема алгоритму програми

Алгоритм оптимізації розкладу

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

Рис. 3.4. Вигляд форми, що відображає процес оптимізації розкладуВикористовувані методи

Під час створення програми були використані наступні основні методи. Оскільки задача складання оптимального розкладу є представником класу 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). Після коректного інсталювання програми ярлик для її виклику додається в меню "Пуск". Також існує можливість виклику програми з одним параметром з командного рядка. В ролі параметру необхідно вказати ім’я

Внимание, отключите Adblock

Вы посетили наш сайт со включенным блокировщиком рекламы!
Ссылка для скачивания станет доступной сразу после отключения Adblock!

Скачать