Предыдущая страница реферата | 4  5  6  7  8  9  10  11  12  13  14 | Следующая страница реферата

Определим теперь понятия, соответствующие мутации и кроссинговеру в генетическом алгоритме.

Мутация — это преобразование хромосомы, случайно изменяющее одну или несколько ее позиций (генов). Наиболее распространенный вид мутаций — случайное изменение только одного из генов хромосомы.

Кроссинговер (в литературе по генетическим алгоритмам также употребляется название кроссовер или скрещивание) — это операция, при которой из двух хромосом порождается одна или несколько новых хромосом. В простейшем случае кроссинговер в генетическом алгоритме реализуется так же, как и в биологии (см. рис. 1). При этом хромосомы разрезаются в случайной точке и обмениваются частями между собой. Например, если хромосомы (1, 2,
3, 4, 5) и (0, 0, 0, 0, 0) разрезать между третьим и четвертым генами и обменять их части, то получатся потомки (1, 2, 3, 0, 0) и (0, 0, 0, 4, 5).

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

В каждом следующем поколении мы будем наблюдать возникновение совершенно новых решений нашей задачи. Среди них будут как плохие, так и хорошие, но благодаря отбору число хороших решений будет возрастать.
Заметим, что в природе не бывает абсолютных гарантий, и даже самый приспособленный тигр может погибнуть от ружейного выстрела, не оставив потомства. Имитируя эволюцию на компьютере, мы можем избегать подобных нежелательных событий и всегда сохранять жизнь лучшему из индивидуумов текущего поколения — такая методика называется “стратегией элитизма”.

Чтобы использовать генетический алгоритм для решения практических задач, необходимо рассматривать более сложные варианты введенных выше понятий. Поясним это на примере задачи коммивояжера для 20 городов.

В качестве индивидуумов будем рассматривать маршруты обхода.
Информацию о маршруте можно записать в виде одной хромосомы — вектора длины
20, где в первой позиции стоит номер первого города на пути следования, затем — номер второго города и т. д. Первое затруднение возникает, когда мы пытаемся определить мутации для таких хромосом — стандартная операция, изменяющая только одну позицию вектора, недопустима, так как приводит к некорректному маршруту. Но можно определить мутацию как перестановку значений двух случайно выбранных генов. При таком преобразовании путь следования меняется только в двух городах.

Найденный маршрут, вероятно, не является самым оптимальным, но близок к нему по длине — как правило, генетические алгоритмы “ошибаются” не более чем на 5—10%. Этот недостаток компенсируется для комбинаторных задач относительно высокой скоростью работы — в нашем примере ответ был получен за 25 секунд. На практике генетические алгоритмы нередко используют совместно с другими методами, которые позволяют повысить их точность.

Эксперименты показали, что погрешность разработанного алгоритма не зависит от погрешности начального решения и составляет (максимальные значения) для ориентированных графов - 5%, для неориентированных 1%. Причем в 90% случаев алгоритм находил точное решение. Эксперименты проводились для графов с количеством вершин, меньшим 75 (где было возможным нахождение точного решения).

Список литературы

В.М. Бондарев, В.И. Рублинецкий, Е.Г. Качко. Основы программирования, 1998 г.
Н. Кристофидес. Теория графов: алгоритмический подход, Мир, 1978 г.
Ф.А. Новиков. Дискретная математика для программистов, Питер, 2001 г.
В.А. Носов. Комбинаторика и теория графов, МГТУ, 1999 г.
О. Оре. Теория графов, Наука, 1982 г. www.codenet.ru www.algolist.ru
-----------------------

[pic]

[pic]

[pic]

[pic]

[pic]

[pic]

[pic]

[pic]

[pic]

[pic]

[pic]

[pic]

[pic]

[pic]

Рекомендуем скачать другие рефераты по теме: доклад на тему культура, реферат н.





Предыдущая страница реферата | 4  5  6  7  8  9  10  11  12  13  14 | Следующая страница реферата