Міністерство транспорту та зв'язку України
Одеська національна академія зв'язку ім.О.С. Попова
Кафедра інформатизації та управління
Комплексне завдання
на тему:
«ГЕНЕТИЧНИЙ АЛГОРИТМ»
Виконала:
Ст. групи ПС-3.12
Волощук В.С.
Перевірив:
зав.кафедри Андрієм А.І.
Одеса 2010
Зміст
1 Історія
2 Опис алгоритму
2.1 Створення початкової популяції
2.2 Розмноження (Схрещування)
2.3 Мутації
2.4 Відбір
3 Застосування генетичних алгоритмів
4 Приклад тривіальної реалізації на C + +
Примітки
Книги
Посилання
Література
Генетичний алгоритм
Генети чний алгоритми тм (англ. genetic algorithm) - це евристичний алгоритм пошуку, що використовується для вирішення завдань оптимізації та моделювання шляхом випадкового підбору, комбінування і варіації шуканих параметрів з використанням механізмів, що нагадують біологічну еволюцію. Є різновидом еволюційних обчислень. Відмінною особливістю генетичного алгоритму є акцент на використання оператора «схрещування», який виробляє операцію рекомбінації рішень-кандидатів, роль якої аналогічна ролі схрещення в живій природі.
1. Історія
«Батьком-засновником" генетичних алгоритмів вважається Джон Холланд (en: John Henry Holland), книга якого «Адаптація в природних і штучних системах» (1975) [1] є основоположним працею в цій галузі досліджень. Йому ж належить Генетичні алгоритми.
Ідея генетичних алгоритмів запозичена у живої природи і полягає в організації еволюційного процесу, кінцевою метою якого є отримання оптимального рішення в складній комбінаторної задачі. Розробник генетичних алгоритмів виступає в даному випадку як "творець", який повинен правильно встановити закони еволюції, щоб досягти бажаної мети якомога швидше. Вперше ці нестандартні ідеї були застосовані до вирішення оптимізаційних завдань у середині 70-х років. Приблизно через десять років з'явилися перші теоретичні обгрунтування цього підходу. На сьогоднішній день генетичні алгоритми довели свою конкурентноздатність при вирішенні багатьох NP-важких завдань і особливо в практичних додатках, де математичні моделі мають складну структуру і застосування стандартних методів типу гілок і меж, динамічного або лінійного програмування вкрай утруднено.
Щорічно у світі проводиться кілька конференцій з цієї тематики, інформацію про які можна знайти в Інтернет за адресами:
http://www.natural-selection.com/eps/
http://mat.gsia.cmu.edu/Conferences/.
Загальну схему генетичних алгоритмів простіше всього зрозуміти, розглядаючи задачі безумовної оптимізації
max {F (i) | i {0,1} n }.
Прикладами служать задачі розміщення, стандартизації, здійсненності та інші. Стандартний генетичний алгоритм починає свою роботу з формування початкової популяції I 0 = {i 1, i 2, ..., i s} - кінцевого набору допустимих рішень задачі. Ці рішення можуть бути обрані випадковим чином або отримані за допомогою імовірнісних жадібних алгоритмів. Як ми побачимо нижче, вибір початкової популяції не має значення для збіжності процесу в асимптотики, проте формування "хорошою" початкової популяції (наприклад з безлічі локальних оптимумів) може помітно скоротити час досягнення глобального оптимуму.
На кожному кроці еволюції за допомогою імовірнісного оператора селекції вибираються два рішення, батьки i 1, i 2. Оператор схрещування за рішеннями i 1, i 2 будує нове рішення i ', яке потім піддається невеликим випадковим модифікаціям, які прийнято називати мутаціями. Потім рішення додається в популяцію, а рішення з найменшим значенням цільової функції видаляється з популяції.
Доказ теореми схем.
1. Вибрати початкову популяцію I 0 і покласти
f * = max {F (i) | I I 0}, k: = 0.
2. Ще не виконаний критерій зупинки робити наступне.
2.1. Вибрати батьків i 1, i 2 з популяції I k.
2.2. Побудувати i 'по i 1, i 2.
2.3. Модифікувати i '.
2.4. Якщо f * <f (I '), то f *: = f (I ').
2.5. Оновити популяцію і покласти k: = k +1.
Гіпотеза 1.
У середньому локальні оптимуми розташовані набагато ближче до глобального оптимуму, ніж до випадково вибраної точці. Їх розподіл в області допустимих рішень на є рівномірним. Вони концентруються в районі глобального оптимуму, займаючи область невеликого діаметру.
Ця гіпотеза частково пояснює працездатність генетичних алгоритмів. Якщо в популяції збираються локальні оптимуми, які відповідно до гіпотези сконцентровані в одному місці, і чергове рішення i 'вибирається десь між двома довільними локального оптимуму, то такий процес має багато шансів знайти глобальний оптимум. Аналогічні міркування пояснюють працездатність та інших локальних алгоритмів. У зв'язку з цим перевірка і теоретичне обгрунтування даної гіпотези представляє безперечний інтерес.
2. Опис алгоритму
Схема роботи генетичного алгоритму
Завдання формалізується таким чином, щоб її рішення могло бути закодовано у вигляді вектора («генотипу») генів. Де кожен ген може бути бітом, числом або якимсь іншим об'єктом. У класичних реалізаціях ГА передбачається, що генотип має фіксовану довжину. Однак існують варіації ГА, вільні від цього обмеження.
Деяким, звичайно випадковим, чином створюється безліч генотипів початкової популяції. Вони оцінюються з використанням «функції пристосованості», в результаті чого з кожним генотипом асоціюється певне значення («пристосованість»), яке визначає наскільки добре фенотип їм описуваний вирішує поставлене завдання.
З отриманого безлічі рішень («покоління») з урахуванням значення «пристосованості» обираються рішення (зазвичай кращі особини мають велику ймовірність бути вибраними), до яких застосовуються «генетичні оператори» (у більшості випадків «схрещування» - crossover і «мутація» - mutation ), результатом чого є отримання нових рішень. Для них також обчислюється значення пристосованості, і потім проводиться відбір («селекція») кращих рішень у наступне покоління.
Цей набір дій повторюється ітеративне, так моделюється «еволюційний процес», що триває декілька життєвих циклів (поколінь), поки не буде виконано критерій зупинки алгоритму. Таким критерієм може бути:
знаходження глобального, або субоптимального рішення;
вичерпання числа поколінь, відпущених на еволюцію;
вичерпання часу, відпущеного на еволюцію.
Генетичні алгоритми служать, головним чином, для пошуку рішень в багатовимірних просторах пошуку.
Таким чином, можна виділити наступні етапи генетичного алгоритму:
Поставити цільову функцію (пристосованості) для особин популяції
Створити початкову популяцію
(Початок циклу)
Розмноження (схрещування)
Мутирование
Обчислити значення цільової функції для всіх особин
Формування нового покоління (селекція)
Якщо виконуються умови зупинки, то (кінець циклу), інакше (початок циклу).
2.1 Створення початкової популяції
Перед першим кроком потрібно випадковим чином створити початкову популяцію; навіть якщо вона виявиться абсолютно неконкурентоздатною, генетичний алгоритм все одно достатньо швидко переведе її в життєздатну популяцію. Таким чином, на першому кроці можна особливо не старатися зробити надто вже пристосованих особин, достатньо, щоб вони відповідали формату особин популяції, і на них можна було підрахувати функцію пристосованості (Fitness). Підсумком першого кроку є популяція H, що складається з N особин.
2.2 Розмноження (Схрещування)
Розмноження в генетичних алгоритмах зазвичай статеве - щоб зробити нащадка, потрібні кілька батьків, зазвичай два.
Розмноження в різних алгоритмах визначається по-різному - воно, звичайно, залежить від подання даних. Головна вимога до розмноження - щоб нащадок чи нащадки мали можливість успадкувати риси обох батьків, «змішавши» їх будь-яким способом.
Чому особи для розмноження зазвичай вибираються із всієї популяції H, а не з тих, що вижили на першому кроці елементів H0 (хоча останній варіант теж має право на існування)? Справа в тому, що головний бич багатьох генетичних алгоритмів - недостача різноманітності (diversity) в особин. Досить швидко виділяється один-єдиний генотип, який представляє собою локальний максимум, а потім всі елементи популяції програють йому відбір, і вся популяція «забивається» копіями цієї особи. Є різні способи боротьби з таким небажаним ефектом; один з них - вибір для розмноження не самих пристосованих, але взагалі всіх особин.
2.3 Мутації
До мутацій відноситься все те ж саме, що і до розмноження: є деяка доля мутантів m, що є параметром генетичного алгоритму, і на кроці мутацій потрібно вибрати mN особин, а потім змінити їх відповідно до заздалегідь визначеними операціями мутації.
2.4 Відбір
На етапі відбору потрібно з усієї популяції вибрати певну її частку, яка залишиться «в живих» на цьому етапі еволюції. Є різні способи проводити відбір. Імовірність виживання особини h повинна залежати від значення функції пристосованості Fitness (h). Сама частка тих, що вижили s зазвичай є параметром генетичного алгоритму, і її просто задають заздалегідь. За підсумками відбору з N особин популяції H повинні залишитися sN особин, які увійдуть до підсумкової популяцію H '. Решта особини гинуть.
3. Застосування генетичних алгоритмів
Генетичні алгоритми застосовуються для вирішення наступних завдань:
Оптимізація функцій
Оптимізація запитів в базах даних
Різноманітні задачі на графах (задача комівояжера, розфарбування, знаходження паросполучення)
Налагодження та навчання штучної нейронної мережі
Завдання компонування
Складання розкладів
Ігрові стратегії
Теорія наближень
Штучне життя
Біоінформатика (фолдінг білків)
4. Приклад тривіальної реалізації на C + +
Пошук в одномірному просторі, без схрещування.
# Include <iostream>
# Include <algorithm>
# Include <numeric>
int main ()
{
using namespace std;
srand ((unsigned) time (NULL));
const int N = 1000;
int a [N];
/ / Заповнюємо нулями
fill (a, a + N, 0);
for (;;)
{
/ / Мутація в випадкову сторону кожного елемента:
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;
}
}
Книги
Ємельянов В. В., Курейчик В. В., Курейчик В. М. Теорія і практика еволюційного моделювання. - М: Фізматліт, 2003. - С. 432. - ISBN 5-9221-0337-7
Курейчик В. М., Лебедєв Б. К., Лебедєв О. К. Пошукова адаптація: теорія і практика. - М: Фізматліт, 2006. - С. 272. - ISBN 5-9221-0749-6
Гладков Л. А., Курейчик В. В., Курейчик В. М. Генетичні алгоритми: Навчальний посібник. - 2-ге вид .. - М: Фізматліт, 2006. - С. 320. - ISBN 5-9221-0510-8
Гладков Л. А., Курейчик В. В, Курейчик В. М. та ін Біоінспірірованние методи в оптимізації: монографія. - М: Фізматліт, 2009. - С. 384. - ISBN 978-5-9221-1101-0
Рутковська Д., Піліньскій М., Рутковський Л. Нейронні мережі, генетичні алгоритми й нечіткі системи = Sieci neuronowe, algorytmy genetyczne i systemy rozmyte. - 2-ге вид .. - М: Гаряча лінія-Телеком, 2008. - С. 452. - ISBN 5-93517-103-1
Посилання
-Наукові статті з генетичним алгоритмам
-Реалізація генетичного алгоритму для. NET Framework 2.0
-Проект CuberGA - розширювана framework для реалізації генетичних алгоритмів
Еволюційні обчислення
Генетичні алгоритми
Генетичні алгоритми
Рішення діофантових рівнянь
Добірка статей по темі Генетичні алгоритми
Основні операції генетичного алгоритму
Використання генетичних алгоритмів в проблемі автоматичного написання програм
Реалізація генетичних алгоритмів у середовищі MATLAB v6.12
Сергій Ніколенко. Генетичні алгоритми (слайди) - лекція № 4 з курсу «Самонавчальні системи»
geneticprogramming.us
Огляд методів еволюції нейронних мереж
Генерування автоматів станів за допомогою ГА
Субботін С. О., Олійник О. О., Олійник О. О. Неітератівні, еволюційні та мультіагентні методи синтезу нечіткологічніх І нейромережніх моделей: Монографія / Під заг. ред. С. О. Субботіна. - Запоріжжя: ЗНТУ, 2009. - 375 с. (Укр.)
A Field Guide to Genetic Programming. - Lulu.com, freely available from the internet, 2008. - ISBN 978-1-4092-0073-4
Special Interest Group for Genetic and Evolutionary Computation (former ISGEC) (англ.)
JAGA (Java API for Genetic Algorithms) - Extensible and pluggable open source API for implementing genetic algorithms and genetic programming applications in Java (англ.)
IlliGAL (Illinois Genetic Algorithms Laboratory) Home Page (англ.)
Evolutionary Computation Laboratory at George Mason University-(англ.)
GENITOR Research Group (CS, Colorado) (англ.)
Evolutionary and Adaptive Systems (EASy) at Sussex (англ.)
Genetic Algorithms Articles (англ.)
Evolutionary Algorithms Research Group at University of Dortmund (англ.)
Evolutionary Digest Archive (англ.)
GAUL: Genetic Algorithm Utility Library - нетривіальна узагальнена вільна реалізація GA (англ.)
Дуже велика підбірка статей по використанню генетичних алгоритмів у задачах багатокритеріальної оптимізації (англ.)
Genetic Algorithms in Ruby (англ.)
Lakhmi C. Jain; NM Martin Fusion of Neural Networks, Fuzzy Systems and Genetic Algorithms: Industrial Applications. - CRC Press, CRC Press LLC, 1998
Література
Александров Д. А. Алгоритм мурашиної колонії для задачі про мінімальний покритті. XI міжнар. Байкальська школа-семінар Методи оптимізації та їх застосування, Праці, т3 (1998), Іркутськ, с. 17-20.
Береснєв В. Л., Гімаді Е. Х., Дементьєв В. Т. Екстремальні задачі стандартизації. Новосибірськ: Наука, 1978.
Гончаров О. М., Кочетов Ю. А. Поведінка імовірнісних жадібних алгоритмів для багатостадійної задачі розміщення. Дискретний аналіз і дослідження операцій. Сер. 2. Т6 (1999), № 1, с. 12-32.
Горбачовська Л. Є., Кочетов Ю. А. Імовірнісна евристика для дворівневої задачі розміщення. XI міжнар. Байкальська школа-семінар Методи оптимізації та їх застосування, Праці, т1 (1998), Іркутськ, с. 249-252.
Гері В., Джонсон Д. Обчислювальні машини і важко вирішити. М.: Світ, 1982.
Єремєєв А.В. Розробка та аналіз генетичних і гібридних алгоритмів для вирішення задач дискретної оптимізації. Дисс. канд.фіз.-мат.наук. Омськ, 2000.
Растрігін Л.А. Випадковий пошук - специфіка, етапи історії та забобони. Питання кібернетики. Вип. 33 (1978), с. 3-16.
Aggarwal CC, Orlin JB, Tai RP Optimized crossover for maximum independent set. Oper. Res. v45 (1997), pp 225-234.
Balas E., Niehaus W. Finding large cliques in arbitrary graphs by bipartite matching. Cliques, coloring, and satisfiability. DIMACS Ser. Discrete Math. Theoret. Comput. Sci. v26 (1996), pp 29-49.
Balas E., Niehaus W. Optimized crossover-based genetic algorithms for the maximum cardinality and maximum weight clique problems. J. Heuristics. V4 (1998), N4, pp 107-122.
Boese KD, Kahng AB, Muddu S. A new adaptive multi-start technique for combinatorial global optimizations. Oper. Res. Lett. V16 (1994), N2, pp 101-114.
Bremermann HJ, Roghson J., Salaff S. Global properties of evolution processes. Natural automata and useful simulations. London: Macmillan. 1966. pp 3-42.