Виконав студент 3-Б курсу Зраєв Дмитро Еволюц ійні та генетичні методи в

алгоритм
Етапи генетичного алгоритму
Робота генетичного алгоритму
Застосування генетичних алгоритмів
План

що обов'язково приводить до розв'язання певного класу задач після скінченного

числа операцій.

Алгоритм

є списком добре визначених інструкцій для розв'язання задачі;
Починаючи з початкового

стану, інструкції алгоритму описують процес обчислення, які відбуваються через послідовність станів, які, зрештою, завершуються кінцевим станом;
Перехід з одного стану до наступного не обов'язково детермінований — деякі алгоритми містять елементи випадковості;
Для візуального зображення алгоритмів часто використовують блок-схеми.

Особливості алгоритмів

роботи призводить до отримання певного результату.
Робота кожного алгоритму

відбувається шляхом виконання послідовності деяких елементарних дій (кроків).
Кожен алгоритм покликаний розв'язувати клас однотипних задач.
Виконання команд алгоритму відбувається у єдиний спосіб та призводить до однакового результату для однакових вхідних даних.

Робота алгоритму

що використовує і моделює біологічну еволюцію.
Еволюційний алгоритм - це

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

Еволюційний алгоритм

1 точки, а з множини - популяції точок;
Будь-яка особина

характеризується рівнем пристосованості;
Оптимізація функції пристосованості;
Пошук особин з високою пристосованістю здійснюється на основі механізмів Дарвіна.

Основні властивості еволюційних алгоритмів:

на рекомбінації геномів
Еволюційне програмування - орієнтоване на оптимізацію неперервних

функцій без використання рекомбінації
Еволюційна стратегія - еволюційне програмування з використанням рекомбінації
Генетичне програмування - використовує еволюційний метод для оптимізації комп'ютерних програм

Напрями еволюційних алгоритмів:

завдань виду функціональної оптимізації і можуть легко бути описані на

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

Класифікація еволюційних алгоритмів

алгоритми з успіхом було застосовано для розв'язання класичних NP-повних

проблем, задача пакування рюкзака, розбиття чисел, максимальна незалежна множина та розфарбовування графів.
До інших не класичних, але важливих, задач, для розв'язання яких застосовано еволюційні алгоритми, належать планування, складання розкладів, обчислення маршрутів, задачі розташування та транспортування.
Також еволюційні алгоритми використовують для оптимізації структур та електронних схем, в медицині та в економіці.

Застосування еволюційних алгоритмів

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

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

Генетичний алгоритм

виконання критерію зупинки алгоритму:
Вибір індивідів із поточної популяції (селекція);
Схрещення або/та

мутація;
Обчислення функції пристосовуваності для всіх осіб;
Формування нового покоління.

Етапи генетичного алгоритму

(набору окремих рішень), домагаючись тим самим отримання нових

наборів рішень (нових популяцій).
При цьому на кожному кроці з популяції вибираються «батьківські особини», тобто рішення, спільна модифікація яких (схрещування) і приводить до формування нової особини в наступному поколінні.
Генетичний алгоритм використовує три види правил, на основі яких формується нове покоління: правила відбору, схрещування і мутації.
Мутація дозволяє шляхом внесення змін до нового покоління уникнути попадання в локальні мінімуми оптимізує функцію.

Робота генетичного алгоритму

комівояжера, розфарбування);
Налаштування і навчання штучної нейронної мережі;
Задачі компоновки;
Створення розкладів;
Ігрові стратегії;
Апромоксація

функцій;
Штучне життя;
Біоінформатика (згортання білків).

Застосування генетичних алгоритмів

за значенням елементи представлені цілими числами найбільш життєздатними.

# include
#

include
# include
using namespace std;
int main()
{
//початковий масив (популяція) з 1000 елементів (осіб).
const int N = 1000;
int a[N];
//заповнимо елементи нулями
fill(a, a+N, 0);
for (;;)

Приклад реалізації на C++

//Випадково збільшуємо або зменшуємо значення елементу на один;

for (int i = 0; i < N; ++i)
if (rand()%2 == 1)
a[i] += 1;
else
a[i] -= 1;
//відсортуванням по зростанню вибираємо більші за значенням...
sort(a, a+N);
//... і тоді більші за значенням виявляться в другій частині масиву.
//скопіюємо більші в першу половину, коли вони залишили нащадків, а перші померли:
copy(a+N/2, a+N, a /*куди*/);
//тепер поглянемо на середнє значення елементу популяції. Як бачимо, середнє значення все більше і більше.
cout << accumulate(a, a+N, 0) / N << endl;
}
}