Генетические алгоритмы.

ВВЕДЕНИЕ

Генетическими алгоритмами называют оптимизационные методы, основанные на идее эволюции с помощью естественного отбора, выдвинутой Дарвином.
Генетические алгоритмы работают с совокупностью "особей"  популяцией, каждая из которых представляет возможное решение данной проблемы. Каждая особь оценивается мерой ее "приспособленности" согласно тому, насколько "хорошо" соответствующее ей решение задачи. В природе это эквивалентно оценке того, насколько эффективен организм при конкуренции за ресурсы. Наиболее приспособленные особи получают возможность "воспроизводить" потомство с помощью "перекрестного скрещивания" с другими особями популяции. Это приводит к появлению новых особей, которые сочетают в себе некоторые характеристики, наследуемые ими от родителей. Наименее приспособленные особи с меньшей вероятностью смогут воспроизвести потомков, так что те свойства, которыми они обладали, будут постепенно исчезать из популяции в процессе эволюции. Иногда происходят мутации, или спонтанные изменения в генах.
Таким образом, из поколения в поколение хорошие характеристики распространяются по всей популяции. Скрещивание наиболее приспособленных особей приводит к тому, что исследуются наиболее перспективные участки пространства поиска. В конечном итоге популяция будет сходиться к оптимальном решению задачи. Преимущество генетических алгоритмов состоит в том, что они находят приблизительные оптимальные решения за относительно короткое время.



Общая схема построения генетических алгоритмов

Генетические алгоритмы [1-4] работают по аналогии с алгоритмом эволюции видов (популяций) живых организмов. В генетическом алгоритме каждый индивид кодируется сходным с ДНК методом  в виде строки из символов одного типа. Длина строки (ДНК) постоянна. В дальнейшем в качестве кодовой строки будет использоваться битовая (двоичная) строка. Популяция из индивидов подвергается процессу эволюции с интенсивным использованием скрещивания и мутаций.
Кодовую строку каждого индивида назовем геномом. Для каждого индивида в популяции задается целевая функция. Значение целевой функции назовем целевым значением. Вектор, состоящий из целевых значений всех индивидов в популяции, назовем вектором целевых значений. Тогда если вычислен вектор целевых значений, то можно определить приспособленность (fitness) индивида в популяции.

СОДЕРЖАНИЕ
Задание. Вариант № 13 1
СОДЕРЖАНИЕ 1
ВВЕДЕНИЕ 1
Общая схема построения генетических алгоритмов 2
Построение генетического алгоритма по предложенному заданию. 3
Выводы: 6
ЛИТЕРАТУРА 7
ПРИЛОЖЕНИЕ: ПРОГРАММА 8

ЛИТЕРАТУРА

1. Емельянов В.В., Курейчик В.В., Курейчик В.М. Теория и практика эволюционного моделирования.  М.:ФИЗМАТЛИТ, 2003.  432 с.
2. Батищев Д.А. Генетические алгоритмы решения экстремальных задач.  Воронеж: Изд.-во ВГТУ, 1995.
3. Дюк В., Самойленко А. Data Mining: учебный курс . - СПб: Питер, 2001. - 386 с.: ил.
4. Божич В.И., Кононенко Р.Н., Абияка А.А. Нейросетевое управление в мультиагентной системе с самоорганизующейся коммуникацией // Материалы Всеросс. конф. "Нейроинформатика-99", М.: МИФИ, 1999. Часть 3. - С.239-246.
5. Исаев Сергей. Популярно о генетических алгоритмах www.algolist.manual.ru