Генетический алгоритм глобальной трассировки
Категория реферата: Рефераты по информатике, программированию
Теги реферата: рефераты на казахском языке, реферат на тему техника
Добавил(а) на сайт: Рейслер.
Предыдущая страница реферата | 1 2 3 4 5 | Следующая страница реферата
3.2 Формирование исходной популяции
Для организации генетического поиска формируется исходная популяция особей P=Hi, где М размер популяции. Популяция Р- представляет собой репродукционную группу – совокупность индивидуальностей, любые две из которых HiÎP и HjÎP, i ¹ j могут размножаться выступая в роли «родителей». Предварительно с помощью процедуры FORM осуществляется разбиение КП на области и формирование модели КП в виде графа W=(X,U). Далее для каждой цепи ti Î Т строится алгоритмом Прима один из вариантов минимального связывающего дерева Di={ri, li=1, … ni}
Затем для каждого rij синтезируется набор Vij вариантов маршрутов в ортогональном графе G, реализующих ребро rij. Пусть nij=| Vij | - число вариантов реализации ребра rij.
Определяется длина L хромосомы, являющейся носителем информации о конкретном решении:
Параметр L определяет число генов в хромосоме. С помощью графика соответствия Q устанавливается соответствие Г(G, Q, R) между генами хромосомы и ребрами минимальных связывающих деревьев для всех цепей.
G=; R=rij
Образом Г(rij) является ген gn. Прообразом Г-1(gn) является ребро rij Значением гена gn, будет номер варианта реализации ребра rij=Г-1(gn) .
Ген gn может принимать любое значение от 1 до nij.
В работе используется принцип случайного формирования исходной популяции.
Для этого в пределах каждой хромосомы Нк каждый ген gn принимает случайное значение в пределах от 1 до nij , где nij число вариантов реализации ребра rij=Г-1(gn).
Управляемыми параметрами при формировании популяции является М - размер популяции, nmax - максимальное число вариантов реализации ребер, т.е. ("ij) [nijnmax]. Если возможное число вариантов nij больше nmax то возникает возможность формирования альтернативных наборов вариантов Vij для rij. Кроме того существует возможность построения альтернативных МСД Di для одной и той же цепи ti.
Все это дает возможность для комбинирования при синтезе исходной популяции. Известно, что для выхода из локальных оптимумов используется механизм смены исходных популяций.
В простейшем случае это можно реализовать с помощью повторной, случайной генерации.
3.3 Генетические операторы
Для получения нового решения (индивидуальности) используются генетические операторы: кроссинговер и мутация.
Кроссинговер заключается во взаимном обмене генами между «родителями» - хромосомами предварительно выбранной пары.
В нашем случае все хромосомы гомологичны, т.к. имеют одну и ту же структуру, одну и ту же длину и несут информацию об одном и том же наборе МСД. Гены, расположенные в одном и том же локусе хромосом, гомологичны, т.к. несут информацию об одном и том же ребре хромосомы.
Предварительно задается величина PK – вероятность кроссинговера и вводится флажок FG с двумя состояниями «выполнять», «не выполнять». Исходное состояние FG «не выполнять». При выполнении кроссинговера последовательно просматриваются локусы выбранной пары хромосом. С вероятностью Pk «флажок» FG переходит в состояние «выполнять». Если FG перешел в состояние «выполнять», то производится обмен генами между парой хромосом в текущем локусе, далее «флажок» переходит в состояние «не выполнять», а затем осуществляется переход к следующему локусу.
Такой алгоритм кроссинговера обеспечивает мультиобмен. Число пар обменивающихся генов определяется параметром Pk.
Операция мутации заключается в изменении значения гена. Алгоритм мутации реализуется следующим образом.
Предварительно, для каждого гена gn, определяется диапазон его возможных значений от 1 до yn, где yn – число сформированных вариантов реализации ребра .
Задается параметр PM – вероятность мутации и «флажок» FG с двумя состояниями «выполнять» и «не выполнять». Исходное состояние FG – «не выполнять».
Последовательно выбираются хромосомы из текущей популяции. В пределах выбранной хромосомы последовательно просматриваются гены. После перехода к очередному гену, FG с вероятностью PM переходит в состояние «выполнять». Если FG перешел в состояние «выполнять», то случайным образом ген gn принимает одно из значений в заданном диапазоне, за исключением значения, которое ген имеет перед мутацией. Далее FG переходит в состояние «не выполнять» и выбирается следующий ген хромосомы, или следующая хромосома.
Для улучшения процесса поиска лучшего решения введем дифференцируемое значение показателя , принимающего различные значения в зависимости от значения гена.
Рекомендуем скачать другие рефераты по теме: тема здоровый образ жизни реферат, банк рефератов бесплатно.
Предыдущая страница реферата | 1 2 3 4 5 | Следующая страница реферата