Предыдущая страница реферата | 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 | Следующая страница реферата