Генетические алгоритмы 2 (стр. 2 из 5)
В наиболее часто встречающейся разновидности генетического алгоритма для представления генотипа объекта применяются битовые строки. При этом каждому атрибуту объекта в фенотипе соответствует один ген в генотипе объекта. Ген представляет собой битовую строку, чаще всего фиксированной длины, которая представляет собой значение этого признака.
Для кодирования таких признаков можно использовать самый простой вариант – битовое значение этого признака. Тогда будет весьма просто использовать ген определенной длины, достаточной для представления всех возможных значений такого признака.
Таким образом, для того, чтобы определить фенотип объекта (то есть значения признаков, описывающих объект) нам необходимо только знать значения генов, соответствующим этим признакам, то есть генотип объекта. При этом совокупность генов, описывающих генотип объекта, представляет собой хромосому. В некоторых реализациях ее также называют особью. В реализации генетического алгоритма хромосома представляет собой битовую строку фиксированной длины. При этом каждому участку строки соответствует ген. Длина генов внутри хромосомы может быть одинаковой или различной. Чаще всего применяют гены одинаковой длины. [9]
Генетические алгоритмы работают с совокупностью "особей" – популяцией, каждая из которых представляет возможное решение данной проблемы. Каждая особь оценивается мерой ее "приспособленности" согласно тому, насколько "хорошо" соответствующее ей решение задачи. В природе это эквивалентно оценке того, насколько эффективен организм при конкуренции за ресурсы. Наиболее приспособленные особи получают возможность "воспроизводить" потомство с помощью "перекрестного скрещивания" с другими особями популяции. Это приводит к появлению новых особей, которые сочетают в себе некоторые характеристики, наследуемые ими от родителей. Наименее приспособленные особи с меньшей вероятностью смогут воспроизвести потомков, так что те свойства, которыми они обладали, будут постепенно исчезать из популяции в процессе эволюции. Иногда происходят мутации, или спонтанные изменения в генах.[13]
Таким образом, из поколения в поколение, хорошие характеристики распространяются по всей популяции. Скрещивание наиболее приспособленных особей приводит к тому, что исследуются наиболее перспективные участки пространства поиска. В конечном итоге популяция будет сходиться к оптимальному решению задачи. Преимущество генетических алгоритмов состоит в том, что он находит приблизительные оптимальные решения за относительно короткое время.
Генетический алгоритм состоит из следующих компонент:
· Хромосома. Решение рассматриваемой проблемы. Состоит из генов.
· Начальная популяция хромосом.
· Набор операторов для генерации новых решений из предыдущей
популяции.
· Целевая функция для оценки приспособленности решений. [11]
1.2 Основные генетические операторы
Стандартные операторы для всех типов генетических алгоритмов это:скрещивание, мутация и селекция.
Как известно в теории эволюции важную роль играет то, каким образом признаки родителей передаются потомкам. В генетических алгоритмах за передачу признаков родителей потомкам отвечает оператор, который называется скрещивание (его также называют кроссовер или кроссинговер). Этот оператор определяет передачу признаков родителей потомкам.
Действует он следующим образом:
1. Из популяции выбираются две особи, которые будут родителями;
2. Определяется (обычно случайным образом) точка разрыва;
3. Потомок определяется как конкатенация части первого и второго родителя.
Таким образом, оператор скрещивание осуществляет обмен частями хромосом между двумя хромосомами в популяции, т. е. создает структуру, основанную на двух структурах – заменой одной части первой структуры на туже область во второй. Затем с вероятностью 0.5 определяется одна из результирующих хромосом в качестве потомка.
Следующий генетический оператор предназначен для того, чтобы поддерживать разнообразие особей в популяции. Он называется мутацией.
При использовании данного оператора каждый бит в хромосоме с определенной вероятностью инвертируется.Кроме того, используется еще и так называемый оператор инверсии, который заключается в том, что хромосома делится на две части, и затем они меняются местами.
Можно сказать, что инверсия - перестановка в структуре некоторой ее части наоборот, а мутация - стохастическое изменение части хромосом, когда каждый ген строки, которая подвергается мутации, с вероятностью Pmut (обычно очень маленькой) меняется на другой ген.
Для функционирования генетического алгоритма достаточно этих двух генетических операторов, но на практике применяют еще и некоторые дополнительные операторы или модификации этих двух операторов. Например, кроссовер может быть не одноточечный (с одной точкой разрыва), а многоточечный, когда формируется несколько точек разрыва (чаще всего две). Кроме того, в некоторых реализациях алгоритма оператор мутации представляет собой инверсию только одного случайно выбранного бита хромосомы.
Оператор селекции осуществляет отбор хромосом в соответствии со значениями их функции приспособленности.
Наиболее эффективные два механизма отбора – элитный отбор и отбор с вытеснением.
Идея элитного отбора основана на построении новой популяции только из лучших особей репродукционной группы, объединяющей в себе родителей, их потомков и мутантов. В основном это объясняют потенциальной опасностью преждевременной сходимости, отдавая предпочтение пропорциональному отбору. Быстрая сходимость, обеспечиваемая элитным отбором, может быть, когда это необходимо, с успехом компенсирована подходящим методом выбора родительских пар, например аутбридингом. Именно такая комбинация "аутбридинг - элитный отбор" является одной из наиболее эффективных. [3]
Второй метод – это отбор вытеснением. Будет ли особь из репродукционной группы заноситься в популяцию нового поколения, определяется не только величиной ее приспособленности, но и тем, есть ли уже в формируемой популяции следующего поколения особь с аналогичным хромосомным набором. Из всех особей с одинаковыми генотипами предпочтение сначала, конечно же, отдается тем, чья приспособленность выше.
Таким образом, достигаются две цели: во-первых, не теряются лучшие найденные решения, обладающие различными хромосомными наборами, а во-вторых, в популяции постоянно поддерживается достаточное генетическое разнообразие. [8]
1.3 Работа генетического алгоритма
Работа генетического алгоритма представляет собой итерационный процесс, который продолжается до тех пор, пока не выполнятся заданное число поколений или какой-либо иной критерий останова. На каждом поколении генетическим алгоритмом реализуется отбор пропорционально приспособленности, кроссовер и мутация.
Схематичное описание функционирования генетического алгоритма (Рисунок 1):
Рисунок 1 Алгоритм работы классического генетического алгоритма
Функционирование генетического алгоритма можно описать следующими шагами:
Инициировать начальный момент времени t=0. Случайным образом сформировать начальную популяцию, состоящую из k-особей.
Вычислить приспособленность каждой особи и популяции в целом. Значение этой функции определяет насколько хорошо подходит особь, описанная данной хромосомой, для решения задачи.
1. Выбрать особь из популяции;
2. С определенной вероятностью (вероятностью кроссовера) выбрать вторую особь из популяции и произвести оператор кроссовера;
3. С определенной вероятностью (вероятностью мутации) выполнить оператор мутации;
4. С определенной вероятностью (вероятностью инверсии) выполнить оператор инверсии;
5. Поместить полученную хромосому в новую популяцию;
6. Выполнить операции, начиная с пункта 3, k-раз;
7. Увеличить номер текущей эпохи t=t+1;
8. Если выполнилось условие остановки, то завершить работу, иначе переход на шаг 2;
Распишем более подробно следующие этапы:
1. Выбор родительской пары:
Первый подход самый простой – это случайный выбор родительской пары, когда обе особи, которые составят родительскую пару, случайным образом выбираются из всей популяции, причем любая особь может стать членом нескольких пар. Несмотря на простоту, такой подход универсален для решения различных классов задач. Однако он достаточно критичен к численности популяции, поскольку эффективность алгоритма, реализующего такой подход, снижается с ростом численности популяции.
Второй способ выбора особей в родительскую пару - так называемый селективный. Его суть состоит в том, что "родителями" могут стать только те особи, значение приспособленности которых не меньше среднего значения приспособленности по популяции, при равной вероятности таких кандидатов составить брачную пару. Такой подход обеспечивает более быструю сходимость алгоритма. Однако из-за быстрой сходимости селективный выбор родительской пары не подходит тогда, когда ставиться задача определения
нескольких экстремумов, поскольку для таких задач алгоритм, как правило, быстро сходится к одному из решений.