Курсовая работа: Нейронні мережі нового покоління

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 істотами (особинами), причому генетичний код кожної особини - це деякий розв’язок задачі (допустимий варіант розкладу). Генетичний код кожної особини (генотип) записується у вигляді однієї хромосоми Х . Разом всі особини утворюють популяцію Р ={X₁ , X_n ,. ., X_N }. У свою чергу кожна хромосома є набором з М генів G^{e (} кожен ген описує одне заняття), тобто X ={G^e ₁ , G^e _m , G^e _M }. Відповідно до видів занять існує три типи генів: потоки, заняття групи та підгруп. Кожний ген G^e ={A^L ₁ ,..., A^L _l ,..., A^L _L } є послідовністю з L аллелів A^L (цілих чисел), які описують одне заняття: номер групи, пари, дня, тижня, кількість підгруп і номер підгрупи, номери дисципліни, викладача, виду заняття, приміщення. Особина вважається тим більш пристосованою, чим краще рішення задачі вона забезпечує (мінімальне значення цільової функції F ).

ГА подібні до еволюційних стратегій, але еволюційні стратегії оперують векторами дійсних чисел, а ГА - двійковими векторами.

Імітуючи еволюцію на комп'ютері часто використовується стратегія елітизму , яка полягає у збереженні життя кращому з індивідуумів поточного покоління.

За сучасними уявленнями еволюція - це процес постійної оптимізації біологічних видів. В класичних задачах оптимізації можна керувати декількома параметрами (позначимо їх значення через g₁ ,… g_M ), а метою є максимізація (або мінімізація) деякої функції F (g₁ ,… g_M ). Функція F називається цільовою функцією. Наприклад, якщо вимагається максимізувати цільову функцію "дохід компанії", то керованими параметрами будуть число співробітників компанії, об'єм виробництва, ціни товари і т.д. Цільова функція також називається функцією пристосованості (fitness function) або функція оцінки, яка дозволяє серед популяції особин виділити найкращих.

У випадку розкладу цільова функція F забезпечує: мінімізацію кількості вікон для навчальних груп та викладачів, мінімізацію переходів між приміщеннями і корпусами, рівномірний розподіл занять з кожної дисципліни за днями тижня; враховує пристосованість приміщень для проведення занять; вимоги викладачів до вільних пар.

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

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

ГА оброблюють не значення параметрів самої задачі, а їх закодовану форму;

виконують пошук рішення виходячи не з однієї точки, а з деякої популяції;

використовують тільки цільову функцію, а не її похідні або іншу додаткову інформацію;

використовують ймовірнісні, а не детерміновані правила відбору.

Основний (класичний) генетичний алгоритм складається з наступних кроків (рис.2.1):

1. Ініціалізація, або вибір початкової популяції хромосом.

2. Оцінювання пристосованості хромосом в популяції

3. Перевірка умови закінчення алгоритму.

4. Селекція хромосом

5. Використання генетичних операторів