Міністерство освіти і науки Російської Федерації
Федеральне державне бюджетне освітня установа
вищої професійної освіти
«МІНІСТЕРСТВО ОСВІТИ УНІВЕРСИТЕТ
СИСТЕМ УПРАВЛІННЯ ТА РАДІОЕЛЕКТРОНІКИ »(ТУСУР)
Кафедра радіоелектроніки та захисту інформації (РЗІ)
Курсовий проект
З дисципліни «Інформатика - КП»
Виконав студент
спеціальності 210400.62
Група з - 142-а
Хусаєнов Руслан Альфатовіч
2 015
Введення
Генетичні елементи (ГА) працюють з сукупністю особин - популяцією, кожна з яких представляє можливе рішення даної проблеми. Кожна особина оцінюється мірою її пристосованості згідно з тим, наскільки добре відповідне їй рішення задачі. У природі це еквівалентно оцінці того, наскільки ефективний організм при конкуренції за ресурси. Найбільш пристосовані особини отримують можливість відтворювати потомство за допомогою перехресного схрещування з іншими особинами популяції. Це призводить до появи нових особин, які поєднують в собі деякі характеристики, успадковані ними від батьків. Найменш пристосовані особини з меншою ймовірністю зможуть відтворити нащадків, так що ті властивості, якими вони володіли, будуть поступово зникати з популяції в процесі еволюції. Іноді відбуваються мутації, або спонтанні зміни в генах.
Таким чином, з покоління в покоління хороші характеристики поширюються по всій популяції. Схрещування найбільш пристосованих особин призводить до того, що досліджуються найбільш перспективні ділянки простору пошуку. Зрештою популяція буде сходитися до оптимального рішення задачі. Перевага ГА полягає в тому, що він знаходить приблизні оптимальні рішення за відносно короткий час.
У процесі виконання даного проекту створена програма для пошуку мінімуму функції двох дійсних змінних в заданій області за допомогою генетичного алгоритму.
Постановка завдання
програма генетичний алгоритм популяція
Необхідно знайти мінімум функції в заданій області.
При виконанні даного проекту необхідно враховувати, що рішення задачі є схильним до впливу випадкових величин. Тому кожен запуск програми необхідно повторювати, принаймні, 20 - 30 разів. Після цього з набору отриманих рішень треба відібрати краще. Зрозуміло, це треба зробити, помістивши зміст головної програми у відповідний цикл, в якому буде одночасно вибиратися найкраще рішення. Одночасно треба обчислити і середнє значення мінімуму за ці 20-30 прогонів.
.
.
.
Розглянути рівномірне схрещування і двоточкову мутацію.
Кожна змінна кодується 20 бітами.
Провести розрахунки для 40 і 80 поколінь.
Порівняти отримувані рішення при розмірах популяції 8, 12, 20 особин.
Генетичні алгоритми
Нехай у нас є деякий певний тип або клас об'єктів (тобто безліч об'єктів, що задовольняють деякому набору умов). І нехай нам необхідно знайти в цьому класі деякий об'єкт, що задовольняє іншому деякому умові. Такий процес можна узагальнено назвати пошуком або рішенням. Клас, серед об'єктів якого проводиться пошук, назвемо областю пошуку або простором пошуку. Шуканий об'єкт можна назвати метою або цільовим об'єктом пошуку, а умова, якому він повинен задовольняти - цільовим умовою. Для визначення умови зазвичай задається деяка функція на просторі пошуку. Досягнення функцією певного значення і є цільовим умовою. Така функція називається цільовою функцією. Таким чином, пошук полягає в перегляді за певними правилами простору пошуку всіх об'єктів, поки не буде виявлений цільовий. Функції вибору нового кандидата для перевірки називаються операторами пошуку.
Для комп'ютерних алгоритмів рішення (пошуку), що використовують обчислювальні моделі механізмів еволюції в якості ключових структурних елементів, використовується узагальнена назва - еволюційні алгоритми.
У генетичному алгоритмі (ГА) кожен індивід кодується подібним з ДНК методом - у вигляді рядка з символів одного типу. Довжина рядка (ДНК) постійна. Популяція з індивідів піддається процесу еволюції з інтенсивним використанням схрещування і мутацій.
