Генетические операторы и их описание.

 

Стандартные операторы для всех типов генетических алгоритмов это:скрещивание, мутация и селекция.

Как известно в теории эволюции важную роль играет то, каким образом признаки родителей передаются потомкам. В генетических алгоритмах за передачу признаков родителей потомкам отвечает оператор, который называется скрещивание. Этот оператор определяет передачу признаков родителей потомкам.

 

Действует он следующим образом:

1. Из популяции выбираются две особи, которые будут родителями;

2. Определяется (обычно случайным образом) точка разрыва;

3. Потомок определяется как конкатенация части первого и второго родителя.

Таким образом, оператор скрещивание осуществляет обмен частями хромосом между двумя хромосомами в популяции, создает структуру, основанную на двух структурах – заменой одной части первой структуры на туже область во второй. Затем с вероятностью 0.5 определяется одна из результирующих хромосом в качестве потомка.

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

При использовании данного оператора каждый бит в хромосоме с определенной вероятностью инвертируется.Кроме того, используется еще и так называемый оператор инверсии, который заключается в том, что хромосома делится на две части, и затем они меняются местами.

Можно сказать, что инверсия - перестановка в структуре некоторой ее части наоборот, а мутация - стохастическое изменение части хромосом, когда каждый ген строки, которая подвергается мутации, с вероятностью меняется на другой ген.

Для функционирования генетического алгоритма достаточно этих двух генетических операторов, но на практике применяют еще и некоторые дополнительные операторы или модификации этих двух операторов. Например, кроссовер может быть не одноточечный, а многоточечный, когда формируется несколько точек разрыва. Кроме того, в некоторых реализациях алгоритма оператор мутации представляет собой инверсию только одного случайно выбранного бита хромосомы.

Оператор селекции осуществляет отбор хромосом в соответствии со значениями их функции приспособленности.

Наиболее эффективные два механизма отбора – элитный отбор и отбор с вытеснением.

Идея элитного отбора основана на построении новой популяции только из лучших особей репродукционной группы, объединяющей в себе родителей, их потомков и мутантов. В основном это объясняют потенциальной опасностью преждевременной сходимости, отдавая предпочтение пропорциональному отбору. Быстрая сходимость, обеспечиваемая элитным отбором, может быть, когда это необходимо, с успехом компенсирована подходящим методом выбора родительских пар, например аутбридингом. Именно такая комбинация "аутбридинг - элитный отбор" является одной из наиболее эффективных.

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

Таким образом, достигаются две цели: во-первых, не теряются лучшие найденные решения, обладающие различными хромосомными наборами, а во-вторых, в популяции постоянно поддерживается достаточное генетическое разнообразие.