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