Операция - скрещивание
Cтраница 1
 |
Древовидное представление компьютерных моделей, отобранных для скрещивания. а - родитель 1. б - родитель 2.| Модели-потомки, полученные в результате скрещивания. [1] |
Операция скрещивания начинается со случайного и независимого выбора точки кроссинговера в каждой из двух моделей-родителей. [2]
Операция скрещивания заключается в обмене фрагментами цепочек между двумя родительскими хромосомами. Пары родителей для скрещивания выбираются из родительского пула случайным образом так, чтобы вероятность выбора конкретной хромосомы для скрещивания была равна вероятности рс. Например, если в качестве родителей случайным образом выбираются две хромосомы из родительской популяции численностью А /, то рс - 2 / N. Аналогично, если из родительской популяции численностью А / выбирается 2z хромосом ( z N12), которые образуют z пар родителей, то рс 2z / N. После операции скрещивания родители в родительской популяции замещаются их потомками. [3]
 |
Динамика генетического алгоритма. [4] |
Введенные генетические операции нормально-линейного вещественного скрещивания и нормальной вещественной мутации, позволяют разрабатывать ГА, обеспечивающий адекватный поиск в пространстве вещественных чисел. [5]
В классическом генетическом алгоритме операция скрещивания представляет собой так называемое точечное скрещивание, рассмотренное в разд. [6]
В ходе анализа влияния операции скрещивания на родительский пул M ( k) рассмотрим некоторую хромосому из множества M ( k) n S, т.е. хромосому из родительского пула, соответствующую схеме S. Вероятность того, что эта хромосома будет отобрана для скрещивания, равна рс. [7]
Другой вариант селекции - отбор после каждой операции скрещивания двух лучших экземпляров среди двух потомков и двух родителей. [8]
В связи с этим для вещественного кодирования хромосом вводится операция линейного скрещивания, при которой потомки находятся на линии, соединяющей точки, соответствующие родителям. [9]
 |
Оператор рекомбинации. [10] |
Оператор рекомбинации имеет естественный аналог [1], при этом в операции скрещивания участвуют две пары хромосом. В соответствии с этим правилом из популяции выбираются две пары хромосом Я1Ь Ян и 21, 22, каждая пара соответствует своему классу. Между двумя хромосомами первой пары и двумя хромосомами второй пары выполняется оператор скрещивания. В результате получается четыре новых решения 3, Н4, 5, е - Применение предлагаемых операторов скрещивания позволяет во многих случаях переходить из одной локальной области пространства решений в другую, а в пределах одной области осуществлять поиск лучших решений. [11]
 |
Пример двухточечного скрещивания.| Пример трехточечного скрещивания.| Двухточечное скрещивание с точками скрещивания 4 и 6. [12] |
Это уже известные нам операции скрещивания и мутации, а также операция инверсии. Инверсия выполняется на одиночной хромосоме; при ее осуществлении изменяется последовательность аллелей между двумя случайно выбираемыми позициями ( locus) в хромосоме. Несмотря на то, что этот оператор был определен по аналогии с биологическим процессом хромосомной инверсии, он не слишком часто применяется в генетических алгоритмах. [13]
Генетический алгоритм с частичной заменой популяции, иначе называемый генетическим алгоритмом с зафиксированным состоянием ( steady-state), характеризуется тем, что часть популяции переходит в следующее поколение без каких-либо изменений. Это означает, что входящие в эту часть хромосомы не подвергаются операциям скрещивания и мутации. Часто в конкретных реализациях алгоритма данного типа на каждой итерации заменяются только одна или две особи вместо скрещивания и мутации в масштабе всей популяции. [14]
Имеется хромосома, представляющая начальное базовое решение. Теперь необходимо сформировать множество промежуточных решений, из числа которых будет выбран второй родитель для участия в операции скрещивания. Множество промежуточных решений формируется путем попарного объединения циклов, причем объединение производится таким образом, чтобы образующиеся в результате парные ребра были идентичны ребрам, присутствующим в разрядах р 1, р 2 начального базового решения. Кроме того, номера циклов множества промежуточных решений не должны совпадать с номерами циклов, участвующих в базовом решении. [15]
Страницы: 1 2