Нейронні мережі нового покоління
Курсовой проект - Компьютеры, программирование
Другие курсовые по предмету Компьютеры, программирование
?овою функцією. Наприклад, якщо вимагається максимізувати цільову функцію "дохід компанії", то керованими параметрами будуть число співробітників компанії, обєм виробництва, ціни товари і т.д. Цільова функція також називається функцією пристосованості (fitness function) або функція оцінки, яка дозволяє серед популяції особин виділити найкращих.
У випадку розкладу цільова функція F забезпечує: мінімізацію кількості вікон для навчальних груп та викладачів, мінімізацію переходів між приміщеннями і корпусами, рівномірний розподіл занять з кожної дисципліни за днями тижня; враховує пристосованість приміщень для проведення занять; вимоги викладачів до вільних пар.
Існує багато методів рішення оптимізацій них задач. У випадку, якщо цільова функція достатньо гладка і має тільки один локальний максимум (унімодальна), те оптимальне рішення можна одержати методом градієнтного спуску. Ідея цього методу полягає у тому, що оптимальне рішення знаходиться методом ітерацій. Тобто береться випадкова початкова точка, а потім в циклі відбувається зміщення цієї точки на малий крок в тому напрямі найшвидшого зростання цільової функції. Недоліком градієнтного алгоритму є дуже високі вимоги до функції - на практиці унімодальность зустрічається украй рідко, а для інших функцій градієнтний метод часто приводить до неоптимальної відповіді. Аналогічні проблеми виникають із застосуванням інших математичних методів.
Генетичний алгоритм являє собою метод, який відображає природну еволюцію методів вирішення проблем, у першу чергу задач оптимізації. Генетичні алгоритми - це процедури пошуку, засновані на механізмах природного відбору і спадкування. У них використовується еволюційний принцип виживання найбільш пристосованих особин. Га відрізняються від традиційних задач оптимізації кількома моментами:
ГА оброблюють не значення параметрів самої задачі, а їх закодовану форму;
виконують пошук рішення виходячи не з однієї точки, а з деякої популяції;
використовують тільки цільову функцію, а не її похідні або іншу додаткову інформацію;
використовують ймовірнісні, а не детерміновані правила відбору.
Основний (класичний) генетичний алгоритм складається з наступних кроків (рис.2.1):
1. Ініціалізація, або вибір початкової популяції хромосом.
2. Оцінювання пристосованості хромосом в популяції
3. Перевірка умови закінчення алгоритму.
4. Селекція хромосом
5. Використання генетичних операторів
6. Формування нової популяції
7. Вибір найкращої хромосоми
Розглянемо ГА більш детально:
1. Ініціалізація, або вибір початкової популяції хромосом. Полягає у випадковому виборі заданої кількості N хромосом (особин).
2. Оцінювання пристосованості хромосом в популяції полягає у розрахунку функції пристосованості для кожної хромосоми pS (Xi). Приймається, що функція пристосованості завжди приймає невідємні значення. Звичайно знаходиться максимум цієї функції.
Рис.2.1 Алгоритм класичного ГА.
3. Перевірка умови закінчення алгоритму. Алгоритм може бути закінчений, якщо його виконання не приводить до покращення отриманого результату або через певний проміжок часу. .
4. Селекція хромосом полягає у виборі на основі функції пристосованості тих хромосом, які будуть приймати участь у створення нащадків, тобто нового покоління. Такий вибір виконується згідно принципу природного відбору, за яким найбільші шанси на створення потомства мають хромосоми з найвищими значеннями функції пристосованості. Існують різні методи селекції. Найбільш популярним вважається метод рулетки. Кожній хромосомі ставиться у відповідність сектор колеса рулетки, величина якого пропорційна до функції пристосованості даної хромосоми. Ймовірність селекції хромосоми Xi, i=1. N (для випадку, що функція F максимізується):
.
Таким чином, ймовірність селекції найбільша для хромосом з великим значенням функції пристосованості. У результаті селекції формується батьківська популяція з чисельністю N у яку особини з великим значенням pS (Xi) можуть увійти кілька разів, а з малим значенням pS (Xi) - жодного.
5. Використання генетичних операторів до відібраних у результаті селекції батьківських хромосом приводить до створення популяції нащадків. В класичному ГА використовують два основних генетичних оператора: оператор схрещування (crossover) і оператор мутації (mutation). Як і живих організмах, ймовірність мутації звичайно дуже мала (рм<0,1).
В ГА мутація може виконуватися на популяції батьків перед схрещуванням або на популяції нащадків, утворених у результаті схрещування.
Оператор схрещування. На першому етапі схрещування вибиваються пари хромосом з батьківської популяції. Операції схрещування полягають у обміні фрагментами ланцюжків між двома батьківськими хромосомами (рис.2.2). Далі для кожної пари вибирається позиція гена (локус) в хромосомі, який визначає точку схрещування. Якщо хромосома містить L двійкових чисел, то точка схрещування LK вибирається випадковим чином з інтервалу [1, L]. В результаті схрещування утворюються два нащадки:
1) нащадок, хромосома якого на позиціях від 1 до LK складається з генів першого предка, а позиції від LK+1 до L - з генів другого предка.
2) нащадок, хромосома якого на позиціях від 1 до LK складається з генів другого предка, а позиції від LK+1 до L - з генів першого предка.
Рис.2.2 Умовна сх?/p>