Нейронні мережі нового покоління
Курсовой проект - Компьютеры, программирование
Другие курсовые по предмету Компьютеры, программирование
MS Excel;
4) для зменшення часу складання розкладу та підвищення його якості використати новий метод - генетичні алгоритми.
2.2.2 Теорія розкладів
Теорія розкладів досліджує задачі, в яких необхідно впорядкувати, тобто визначити послідовність виконання сукупності робіт, використання певних засобів та ін. До таких задач відносяться, наприклад, задачі складання розкладу для навчальних закладів [2].
У загальному формулюванні задача складання розкладу полягає у наступному. За допомогою деякої множини ресурсів або обслуговуючих пристроїв повинна бути виконана певна фіксована система завдань. Мета полягає в тому, що при заданих властивостях завдань і ресурсів, а також накладених на них обмежень, знайти ефективний алгоритм впорядкування завдань.
Загальна теорія розкладів передбачає, що всі обслуговуючі пристрої (або процесори) не можуть виконувати в даний момент часу більше одного завдання. Проте для розкладу навчальних занять така умова є достатньою, якщо в якості процесора при розподілі занять прийняти навчальну аудиторію. Так в деяких випадках в одній аудиторії можуть проводитися заняття з більш ніж з однією групою одночасно.
Таким чином формулювання задачі складання розкладу для навчальних закладів можна записати наступним чином: „Для заданого набору навчальних аудиторій (в даному випадку під навчальною аудиторією розуміється широкий круг приміщень, в яких проводяться навчальні заняття: від компютерного класу до спортивного залу) і заданого набору часових інтервалів (навчальних пар) побудувати такий розподіл навчальних занять для всіх обєктів (викладачі і навчальні групи), для якого вибраний критерій оптимальності буде найкращим.
Пошук оптимального або близького до оптимального розкладу виконується за допомогою одного з 4 підходів:
1) математичного програмування;
2) комбінаторного;
3) евристичного;
4) статистичного (ймовірнісного).
При використанні методів математичного програмування для розвязку задач складання розкладу неминуча експоненційна складність часу розвязку задачі. Для скорочення перебору використовуються різноманітні методи, зокрема методів віток і границь.
Комбінаторний метод зводиться до цілеспрямованої перестановки пар робіт в деякій послідовності, поки не буде отримано оптимальне (або близьке до оптимального) рішення.
Евристичні алгоритми засновані на прийомі зниження вимог. Він полягає у пошуку рішення, близького до оптимального, за допустимий час. Широко використовується так званий метод локального пошуку. При цьому наперед вибрана множина перестановок використовується для послідовного покращення початкового розвязку до тих пір, поки таке покращення можливе, в іншому випадку буде отримано локальний оптимум.
Ймовірнісні методи полягають у випадковому виборі послідовності виконання робіт. Вибір повторюється багато разів, в результаті чого вибирається найкращий варіант розкладу.
Згідно з вищесказаним складемо математичну модель розкладу для факультету вузу:
Період розкладу QW = 2 тижні (1 і 2 тиждень, 10 робочих днів), номер тижня w=1. QW.
День тижня d=1. QD; де QD=10.
Номер пари z=1. QZ, де QZ=8.
Номер дисципліни j=1. QJ.
Для оптимізації навчального процесу групи слід обєднувати в потоки, якщо в групах одного курсу читається лекція з однієї дисципліни.
2.2.3 Генетичні алгоритми
Генетичні алгоритми ГА (Genetic Algorithms) є складовою еволюційних методів, оскільки виникли у результаті спроб копіювання еволюції живих організмів. Ідея генетичних алгоритмів вперше висловив Дж. Холланд в кінці 60-х років ХХ століття. Суть методу полягала у створенні компютерної програми, яка б вирішувала складні задачі так, як це робить природа - шляхом еволюції. Відповідно у ГА використовують поняття, запозичені з генетики [3-5].
За допомогою ГА задача вирішується наступним чином. Спочатку створюється математична модель штучного світу, який населений N істотами (особинами), причому генетичний код кожної особини - це деякий розвязок задачі (допустимий варіант розкладу). Генетичний код кожної особини (генотип) записується у вигляді однієї хромосоми Х. Разом всі особини утворюють популяцію Р={X1, Xn,. ., XN}. У свою чергу кожна хромосома є набором з М генів Ge (кожен ген описує одне заняття), тобто X={Ge1, Gem, GeM}. Відповідно до видів занять існує три типи генів: потоки, заняття групи та підгруп. Кожний ген Ge={AL1,..., ALl,..., ALL} є послідовністю з L аллелів AL (цілих чисел), які описують одне заняття: номер групи, пари, дня, тижня, кількість підгруп і номер підгрупи, номери дисципліни, викладача, виду заняття, приміщення. Особина вважається тим більш пристосованою, чим краще рішення задачі вона забезпечує (мінімальне значення цільової функції F).
ГА подібні до еволюційних стратегій, але еволюційні стратегії оперують векторами дійсних чисел, а ГА - двійковими векторами.
Імітуючи еволюцію на компютері часто використовується стратегія елітизму, яка полягає у збереженні життя кращому з індивідуумів поточного покоління.
За сучасними уявленнями еволюція - це процес постійної оптимізації біологічних видів. В класичних задачах оптимізації можна керувати декількома параметрами (позначимо їх значення через g1,… gM), а метою є максимізація (або мінімізація) деякої функції F (g1,… gM). Функція F називається ціл?/p>