Запанувала тиша, яку порушив сам Швейк, зітхнувши:
- ... На військовій службі повинна бути дисципліна - без неї ніхто б і пальцем для діла не ворухнув. Наш обер-лейтенант Макіївці завжди говорив: «Дисципліна, бовдури, необхідна. Не будь дисципліни, ви б, як мавпи, по деревах лазили. Військова служба з вас, йолопи, людей зробить! »Ну, хіба це не так? Уявіть собі парк, скажімо, на Карлаку, і на кожному дереві сидить солдат без дисципліни. Це мене страшенно лякає.
Ярослав Гашек Пригоди бравого солдата Швейка
Розклад занять, це поєднання в просторі і часі дисципліни (предмета), викладача (викладачів), аудиторії і групи (підгрупи, потоку) студентів.
Постановка задачі
Висновок. Як видно з постановки, оцінити якість розкладу можливо, тільки після його повного складання. Отже застосування генетичних алгоритмів може дозволити побудувати рішення шуканої завдання і навіть отримати в певному сенсі одне з хороших. При цьому генетичні алгоритми дуже швидко сходяться до оптимального на початку і означає практично не буде обмежень на обсяг вхідних даних.
Картинка взята звідси.
генетичний алгоритм
Чисто риторично, повторю основні етапи генетичного алгоритму:
- Задати цільову функцію (пристосованості) для особин популяції
- Створити початкову популяцію
- (Початок циклу)
- Розмноження (схрещування)
- мутирование
- Обчислити значення цільової функції для всіх особин
- Формування нового покоління (селекція)
- Якщо виконуються умови зупинки, то кінець циклу, інакше (початок циклу).
Найбільш характерна помилка застосування генетичних алгоритмів полягає у виборі генів. Часто в якості генів вибирають просто саме рішення. Вибір генів є нетривіальним і творчим елементом при створенні генетичного алгоритму. Особисто я вважаю, що вибір генів повинен відповідати двом основним вимогам.
- По набору генів рішення шуканої завдання повинно будується швидко і однозначно.
- При схрещуванні нащадок повинен наслідувати характерні риси батьків.
Алгоритм складання розкладів
Я тільки опишу самі гени, алгоритм побудови по ним рішення, схрещування і мутації.
Як становить розклад досвідчений диспетчер. Слово досвідчений означає, що диспетчер вже становив / а розклад вже на раз і знає його вузькі місця. Наприклад брак великих потокових аудиторій або комп'ютерних класів. Перший курс, оскільки у них багато потокових лекцій і одночасно занять в підгрупах по комп'ютерних класів, англійська / англійська з нуля / німецька / французька і т.д. а начальство при цьому вимагає, щоб у першого курсу не в якому разі не було вікон і не більше двох лекцій в день і дні були рівномірно навантажені. Тому досвідчений диспетчер розставляє спочатку «вузькі заняття», заняття начальства на їх вимогу і заняття особливо докучливих викладачів. Потім використовуючи розставлені заняття як скелет, досить швидко добудовує розклад. Спробуємо з імітувати, в деякому сенсі, цей процес.
Частина занять вже у нас стоїть в розкладі, що залишилися послідовно Занумеруем. Масив номерів занять будемо вважати геномом, хоча в принципі тут важливий лише порядок занять. Для побудови розкладу будемо послідовно витягувати номери занять і ставити вибране заняття в розклад задовольняючи необхідним вимогам і максимізуючи цільову функцію для студентів, викладачів і аудиторій (у них теж бувають критерії зайнятості).
Якщо необхідним вимогам не вдається задовольнити, то особина з таким геномом може бути відкинута як нежиттєздатна. Якщо розклад скласти не виходить, то можна замінити необхідні вимоги штрафом в цільової функції.
Схрещування можна організувати декількома способами. Наприклад один з них. Нехай маємо наступні гени
3 1 2 5 6 4 7
2 3 5 7 1 4 6
Тут видно, що заняття 3 зустрічається в обох генах до позиції 2 включно, а, наприклад, з позиції 2 до позиції 5 інтервал для 1 заняття. Зробимо наступну табличку
_ * * * * _ _ Для 1 заняття
* * * _ _ _ _ Для 2 заняття
* * _ _ _ _ _ Для 3 заняття
_ _ _ _ _ * _ Для 4 заняття
_ _ * * _ _ _ Для 5 заняття
_ _ _ _ * * * Для 6 заняття
_ _ _ * * * * Для 7 заняття
тут зірочками позначені можливі позиції для номерів занять нащадка. Можна вибрати з одного або кілька можливих рішень в якості нащадка або нащадків цих батьків. Рішення для вибору генів нащадка завжди є, наприклад обоє батьків самі йому задовольняють. Перепишемо таблицю через безлічі можливих позицій
Для побудови рішень можна використовувати наступний алгоритм. Спочатку будемо ставити ті номери занять, які рідше зустрічаються. Якщо їх впорядкувати за зростанням, то матимемо
1 раз 4
2 рази 3, 5
3 рази 2, 6
4 рази 1, 7
Отже спочатку ставимо 4 заняття на 6-ту позицію, потім 3 або 5 на позиції або відповідно. На кожному кроці можна кидати коробок сірників. В результаті можна отримати наприклад такі кроки для алгоритму схрещування
* * * * * 4 *
3 * * * * 4 *
3 * * 5 * 4 *
3 * * 5 * 4 6
3 * 2 5 * 4 6
3 * 2 5 7 4 6
3 1 2 5 7 4 6
Оскільки можна і не побудувати правильну послідовність, то краще алгоритм організувати у вигляді простої рекурсії для можливості повторення алгоритму, тобто організації деякого перебору.
Мутацію можна організувати досить просто, випадкової перестановкою номерів занять.
висновок
Повторно пропоную наступні рішення (малюнок).
Дякуємо Всім хто відгукнувся, після обговорення цього топіка можна буде зі організуватися.