новая папка 1 / 294549

МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РФ ФЕДЕРАЛЬНОЕ ГОСУДАРСТВЕННОЕ БЮДЖЕТНОЕ ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ ВЫСШЕГО ПРОФЕССИОНАЛЬНОГО ОБРАЗОВАНИЯ «ВОРОНЕЖСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ»

ГЕНЕТИЧЕСКИЕ АЛГОРИТМЫ: БАЗОВЫЕ ПОНЯТИЯ

Учебно-методическое пособие для вузов

Составители: М.А. Артемов, И.Ю. Стародубцев, Н.А. Стародубцева

Воронеж Издательский дом ВГУ

2014

1

Утверждено научно-методическим советом факультета прикладной математики, информатики и механики 20 февраля 2014 г., протокол № 6

Рецензент д-р физ.-мат. наук, проф. А.И. Шашкин

Учебно-методическое пособие подготовлено на кафедре программного обеспечения и администрирования информационных систем факультета ПММ Воронежского государственного университета.

Рекомендуется для студентов 4-го курса очной и очно-заочной форм обучения факультета ПММ.

Для направления 010500 – Математическое обеспечение и администрирование информационных систем

2

3

Введение

Генетические алгоритмы – это новая область исследований, которая появилась в результате работ Д. Холланда [1] и его коллег в конце шестидесятых – начале семидесятых годов ХХ века. Основой для возникновения генетических алгоритмов послужили модель биологической эволюции и методы случайного поиска. Л. Растригин [2] отмечал, что случайный поиск возник как реализация простейшей модели эволюции, когда случайные мутации моделировались случайными шагами оптимального решения, а отбор – «устранением» неудачных вариантов.

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

Цель генетических алгоритмов состоит в том, чтобы:

−абстрактно и формально объяснять адаптацию процессов в естественной системе и интеллектуальной исследовательской системе;

−моделировать естественные эволюционные процессы для эффективного решения оптимизационных задач науки и техники.

1. Базовые понятия генетических алгоритмов

Генетические алгоритмы, описанные Д. Холландом, заимствуют в своей терминологии многое из естественной генетики [4]. Например, речь идет о популяции особей, а в качестве базовых понятий применяются ген,

хромосома, генотип, фенотип, аллель. Также используются соответствую-

щие этим терминам определения из технического лексикона, в частности

цепь, двоичная последовательность, структура.

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

Хромосомы (другие названия – цепочки или кодовые последова-

тельности) – это упорядоченные последовательности генов.

Генотип, или структура, – это набор хромосом данной особи. Следовательно, особями популяции могут быть генотипы либо единичные хромосомы (в довольно распространенном случае, когда генотип состоит из одной хромосомы).

4

Фенотип – это набор значений, соответствующих данному генотипу, т.е. декодированная структура или множество параметров задачи (решение, точка пространства поиска).

Аллель – это значение конкретного гена, также определяемое как значение свойства или вариант свойства.

Локус, или позиция, указывает место размещения данного гена в хромосоме (цепочке). Множество позиций генов – это локи.

Очень важным понятием в генетических алгоритмах считается функция приспособленности (fitness function), иначе называемая функцией оценки.

Она представляет собой меру приспособленности данной особи в популяции. Эта функция играет важнейшую роль, поскольку позволяет оценить степень приспособленности конкретных особей в популяции и выбрать из них наиболее приспособленные (т.е. имеющие наибольшие значения функции приспособленности) в соответствии с эволюционным принципом выживания «сильнейших» (лучше всего приспособившихся).

2. Простой генетический алгоритм

Этот алгоритм был впервые описан Д. Гольдбергом [3] на основе работ Д. Холланда. Его механизм несложен. Предварительно простой генетический алгоритм случайно генерирует популяцию последовательностей – хромосом (альтернативных упорядоченных и неупорядоченных решений). Затем производится копирование последовательности хромосом и перестановка их частей. Далее простой генетический алгоритм реализует множество простых операций к начальной популяции и генерирует новые решения.

Простой генетический алгоритм состоит из трех операторов:

•репродукции;

•кроссинговера;

•мутации.

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

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

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

Генетический алгоритм состоит из набора генетических операторов. Генетический оператор по аналогии с оператором алгоритма –

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

5

Рассмотрим основные операторы генетических алгоритмов. Оператор репродукции (селекция) – это процесс, посредством которого

хромосомы (альтернативные решения), имеющие более высокое значение целевой функции (с «лучшими» признаками), получают большую возможность для воспроизводства (репродукции) потомков, чем «худшие» хромосомы. Элементы, выбранные для репродукции, обмениваются генетическим материалом, создавая аналогичных или различных потомков.

Существуют многие виды операторов репродукции. К ним относятся следующие:

1.Селекция на основе рулетки – это простой и широко используемый в простом генетическом алгоритме метод. При его реализации каждому элементу в популяции соответствует зона на колесе рулетки, пропорционально соразмерная с величиной целевой функции. Тогда при повороте колеса рулетки каждый элемент имеет некоторую вероятность выбора для селекции. Причем элемент с бóльшим значением целевой функции имеет бóльшую вероятность для выбора.

2.Селекция на основе заданной шкалы. Здесь популяция предваритель-

но сортируется от «лучшей» к «худшей» на основе заданного критерия. Каждому элементу назначается определенное число, и тогда селекция выполняется согласно этому числу.

3.Элитная селекция. В этом случае выбираются лучшие (элитные) элементы на основе сравнения значений целевой функции. Далее они вступают в различные преобразования, после которых снова выбираются элитные элементы. Процесс продолжается аналогично до тех пор, пока продолжают появляться элитные элементы.

4.Турнирная селекция. При этом некоторое число элементов (согласно размеру «турнира») выбирается – случайно или направленно – из популяции, и лучшие элементы в этой группе на основе заданного турнира определяются для дальнейшего эволюционного поиска.

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

– случайный выбор хромосом;

– выбор хромосом на основе значений целевой функции.

При случайном выборе хромосом частота R образования родительских пар не зависит от значения целевой функции хромосом и полностью определяется численностью популяции N:

6

где β – коэффициент селекции, в зависимости от условий внешней среды принимающий значение 1÷4.

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

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

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

Опишем теперь оператор кроссинговера (скрещивания). Оператор кроссинговера – это языковая конструкция, позволяющая на основе преобразования (скрещивания) хромосом родителей (или их частей) создавать хромосомы потомков. Существует огромное число операторов кроссинговера, так как их структура в основном и определяет эффективность генетических алгоритмов. Кратко рассмотрим основные операторы кроссинговера, известные в литературе, и их модификации.

Простой (одноточечный) оператор кроссинговера. Перед началом работы одноточечного оператора кроссинговера определяется так называемая точка оператора кроссинговера, или разрезающая точка оператора кроссинговера, которая обычно определяется случайно. Эта точка определяет место в двух хромосомах, где они должны быть «разрезаны». Например, пусть популяция P состоит из хромосом P1 и P2, которые выступают в качестве родителей P = {P1, P2}. Пусть первый и второй родители имеют вид P1 : 11111, P2 : 00000. Выберем точку оператора

7

кроссинговера между вторым и третьим генами в P1, P2. Тогда, меняя элементы после точки оператора кроссинговера между двумя родителями, можно создать два новых потомка (табл. 1).

Таблица 1

Результат применения оператора кроссинговера

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

Двухточечный оператор кроссинговера. В каждой хромосоме определяются две точки оператора кроссинговера, и хромосомы обмениваются участками, расположенными между двумя точками оператора кроссинговера (табл. 2).

Таблица 2

Применение двухточечного оператора кроссинговера

Отметим, что точки оператора кроссинговера в двухточечном операторе кроссинговера также определяются случайно. Существует большое количество модификаций двухточечного оператора кроссинговера. Развитием двухточечного оператора кроссинговера является многоточечный, или N-точечный, оператор кроссинговера. Многоточечный оператор кроссинговера выполняется аналогично двухточечному, хотя большое число «разрезающих» точек может привести к потере «хороших» родительских свойств.

Упорядоченный оператор кроссинговера. Здесь «разрезающая» точка также выбирается случайно. Далее происходит копирование левого сегмента P1 в P1(нов.). Остальные позиции в P1(нов.) берутся из P2 в упорядоченном виде слева направо, исключая элементы, уже попавшие в P1 (нов.) (таблица 3).

8

Таблица 3

Применение упорядоченного оператора кроссинговера

Также хорошо известны другие модификации оператора кроссинго-

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

Оператор мутации – языковая конструкция, позволяющая на основе преобразования родительской хромосомы (или ее части) создавать хромосому потомка. Оператор мутации обычно состоит из двух этапов:

1.В хромосоме A = (a1 , a2 , ..., aL−1 , aL ) определяются случайным образом две позиции (например, a2 и aL ).

2.Гены, соответствующие выбранным позициям, переставляются, и формируется новая хромосома Aнов = (a1 , aL , ..., aL−1 , a2 ) .

Рассмотрим кратко основные операторы мутации. Простейшим оператором мутации является одноточечный. При таком операторе случайно выбирают ген в родительской хромосоме и обменивают на рядом расположенный ген. В результате получают хромосому потомка (табл. 4).

Таблица 4

Применение одноточечного оператора мутации

Здесь P1 – родительская хромосома, а P1(нов.) – хромосома-потомок после применения одноточечного оператора мутации.

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

(табл. 5).

Таблица 5

Двухточечный оператор мутации

Здесь P1 – родительская хромосома, а P1(нов.) – хромосома-потомок после применения двухточечного оператора мутации.

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

9

4.Теоретико-множественные операции над популяциями

ихромосомами

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

Объединением популяций (хромосом) А и B будем считать популяцию (хромосому) С, которая состоит из элементов, принадлежащих или популяции (хромосоме) А, или популяции (хромосоме) В, или обеим популяциям (хромосомам) одновременно.

C = A B, где – знак объединения.

Можно объединить не только две, но и любое количество популяций (хромосом):

n

A1 A2 A3 ... An = U Ai .

i=1

Популяция C считается пересечением популяций А и В, если популяция С состоит из элементов, которые принадлежат одновременно и популяции А, и популяции В:

C = A ∩ B, где ∩ – знак пересечения.

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

Популяция C, равная A \ B, называется разностью популяций A и B, если C состоит из элементов, которые принадлежат A и не принадлежат B:

С = А \ В,

где \ – знак разности.

В отличие от объединения и пересечения операция разности применяется только для двух популяций или их элементов.

Кортеж – конечное упорядоченное множество.

Прямым, или декартовым, произведением популяций A и B называет-

ся популяция, состоящая из всех тех и только тех пар, т.е. кортежей длины 2, первая компонента которых принадлежит популяции А, а вторая – популяции В:

A B – прямое (декартово) произведение популяций A и B.

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

10