Оператор - скрещивание
Cтраница 2
Наиболее распространенными при этом являются одноточечный, двухточечный и равномерный операторы скрещивания. [16]
Рассмотрим процедуру соединения N элементов с разными описаниями, соответствующую оператору скрещивания в генетических методах поиска оптимальных решений. Заметим, что в данном случае потомок происходит от N родителей. Отбор кандидатов для скрещивания основан на вычислении степени удовлетворения взаимных требований соединяемых ФПС. [17]
Однако следует отметить, что оператор мутации играет явно второстепенную роль по сравнению с оператором скрещивания. Это означает, что скрещивание в классическом генетическом алгоритме производится практически всегда, тогда как мутация - достаточно редко. Это следует из аналогии с миром живых организмов, где мутации происходят чрезвычайно редко. [18]
Это временная популяция, состоящая из хромосом, отобранных в результате селекции и предназначенных для дальнейших преобразований операторами скрещивания и мутации с целью формирования новой популяции потомков. На данном этапе хромосомы из родительской популяции объединяются в пары. Это производится случайным способом в соответствии с вероятностью скрещивания рс. Далее для каждой пары отобранных таким образом родителей разыгрывается позиция гена ( локус) в хромосоме, определяющая так называемую точку скрещивания. [19]
В качестве операторов скрещивания, отбора и редукции выберем традиционные операторы, рассмотренные выше при решении задачи нахождения максимума одномерной функции. Дополнительно для оператора скрещивания можно установить вероятность применения 0 95 и использовать элитизм. [20]
 |
Процесс скрещивания хромосом в примере. [21] |
При этом процесс скрещивания протекает так. В результате выполнения оператора скрещивания получаются 4 пары потомков. [22]
 |
Зависимость максималь. [23] |
Для решения этой проблемы была предложена эвристика, которая заключается в модификации генетического алгоритма. Данная модификация оптимизационного алгоритма заключается в изменении операторов скрещивания и мутации. Поскольку в старом алгоритме в качестве оптимизационного алгоритма использовался ПГА, то механизм оператора скрещивания представлял собой скрещивание двух особей предков с разрывом в одной точке ( точка разрыва выбирается случайно) и последующим обменом концов строк-хромосом особей предков для получения двух особей потомков. Механизм мутации представлял собой однобитную мутацию, при которой для случайно выбранной особи случайным образом определялся ген и бит в строке-хромосоме; затем данный бит инвертировался. Исследования работы алгоритма для больших портфелей заказов показали, что такая схема работы оказывает малое влияние на развитие популяции, что приводит к плохим результатам. Для решения было предложено использовать механизм многоточечного скрещивания и многобитной мутации. [24]
Классический генетический алгоритм выполняется при фиксированной длине двоичных последовательностей и в нем применяются операторы скрещивания и мутации. Эволюционные программы обрабатывают более сложные структуры ( не только двоичные коды) и могут выполнять иные генетические операции. Например, эволюционные стратегии могут трактоваться в качестве эволюционных программ, в которых хромосомы представляются вещественными ( не двоичными) числами, а мутация используется как единственная генетическая операция. [25]
В этой программе применяется алгоритм с частичной заменой популяции ( steady-state), при которой в каждый момент времени заменяется только одна особь. Если говорить о так называемых генетических операторах, то в программе Evolver применяются два различных оператора скрещивания и два различных оператора мутации - отдельно для оптимизационных и для комбинаторных задач. [26]
Реализуются генетические операторы репродукции, скрещивания и мутации. В результате репродукции осуществляется копирование уже созданных программ с хорошими значениями целевой функции. Оператор скрещивания создает новые программы путем комбинирования фрагментов существующих программ. Мутация заключается в замене некоторого фрагмента программы случайно порожденным символьным выражением. [27]
Определим некоторые характеристики генетического алгоритма. Пусть размер популяции будет 4, вероятность мутации 0 001, сам процесс мутации заключается в инверсии одного из битов строки, выбираемого случайно по равномерному закону. Оператор скрещивания и отбора аналогичны описанным выше. Поскольку задача является простейшей, будем считать, что алгоритм не использует элитизм. [28]
Вырожденными формами операторов скрещивания являются, с одной стороны, точное копирование потомками своих родителей, а с другой, порождение потомков, в наибольшей степени отличающихся от них. Преимуществом первого варианта является скорейшее нахождение лучшего решения, а недостатком, в свою очередь, тот факт, что алгоритм не сможет найти решения лучше, чем уже содержится в исходной популяции, поскольку в данном случае алгоритм не порождает принципиально новых особей, а лишь копирует уже имеющиеся. Чтобы все-таки использовать достоинства этой формы операторов скрещивания в реальных генетических алгоритмах, применяют элитизм, речь о котором шла выше. [29]
Определение 2-го и 3-го потомков 1 - й особи. Реализуется в случае выполнения условия скрещивания особей. При этом образуются второй и третий потомки г-й особи посредством оператора скрещивания. Оператор скрещивания представляет собой механизм одноточечного скрещивания двух особей с разрывом хромосом по одной позиции. [30]
Страницы: 1 2 3