Генетические алгоритмы в изобретательских задачах
Курсовой проект - Менеджмент
Другие курсовые по предмету Менеджмент
ого родителей с формированием потомков. При этом правый сегмент р2 переносится в р1, левый сегмент р1 переносится в р1 с заменой повторяющихся генов на отсутствующие (гены, находящиеся в частичном соответствие). Например:
Рисунок 4 - Частично-соответствующийОК
Циклический ОК. Циклический OK выполняет рекомбинации согласно циклам, которые существуют при установлении соответствия между генами первого и второго родителей. Например, пусть популяция Р состоит из двух хромосом Р = {р1,р2}. Первый и второй родители и их потомок имеют вид:
Рисунок 5 - Циклический ОК
Универсальный ОК. В настоящее время он популярен для решения различных задач теории расписаний. Вместо использования разрезающей точки (точек) здесь определяют двоичную маску, длина которой равна длине заданных хромосом. Получение потомков выполняется на основе правил сложения булевой алгебры соответствующих генов родителей и маски (0 + 0 = 0, 0 + 1 = 1, 1 + 1=0). Для каждого элемента в p1, р2 гены меняются, как показано на следующем примере:
Рисунок 6 - Универсальный ОК
Маска обычно выбирается случайно с заданной вероятностью или на основе генератора случайных чисел. При этом чередование 0 и 1 в маске происходит с вероятностью 0,5 (т. е. приблизительно в 50% случаев). В некоторых случаях используются параметризированный универсальный ОК, где маска может выбираться с вероятностью для 1 или 0 выше, чем 0,5. Такой вид маски эффективен, когда хромосомы кодируются в двоичном алфавите.
В оптимизационных задачах находят применение различного типа жадные операторы кроссинговера. Они основаны на анализе ЦФ решений после каждого шага жадного ОК. Он может быть реализован на двух и более хромосомах, а в пределе - на всей популяции. Приведем типичный модифицированный алгоритм жадного ОК:
.Для всех хромосом популяции вычисляется ЦФ. Выбирается заданное число родительских хромосом, и случайным образом на одной из хромосом определяется точка жадного ОК.
.В выбранной хромосоме для i-го гена, расположенного слева от точки жадного ОК, определяется частичная ЦФ, т. е. стоимость пути от i-гo гена к рядом находящемуся гену. Аналогичные действия выполняются по определению стоимости пути во всех остальных хромосомах, выбранных для жадного ОК.
.В хромосому потомок выбирают тот ген, у которого значение ЦФ выше (ниже) при максимизации (минимизации) ЦФ.
. Процесс продолжается, пока не будет построена хромосома потомок. Если в процессе реализации жадного О К возникает цикл или тупик, то в потомок выбираются нерассмотренные гены с лучшей ЦФ.
Например, пусть популяция Р состоит из трех родительских хромосом Р = {р1, р2, р3}, где p1:(abcde); p2:(bdeca); p3:(ebadc). Причем стоимость (ЦФ) для каждого гена в хромосоме задана матрицей:
Рисунок 7 - Матрица стоимости ген в хромосоме
Согласно алгоритму выберем точку жадного ОК между генами b и с в хромосоме p1. Теперь выбор (b-c) дает значение ЦФ, равное 4; выбор (b-а) определяет ЦФ со значением 15, а выбор (b-d) определяет ЦФ, равную 3. При решении задачи минимизации ЦФ выберем путь (b-d). Продолжая далее, получим путь реализации жадного ОК. Итак, хромосома потомка р: (b d с а е) имеет суммарную ЦФ, равную 18 (3 +1 + 6 + 8 = 18), а ЦФ родителей для p1 равна 15 + 4 + 1 + 9 = 29, для р2 равна 3 + 9 + 10 + + 6 = 28 и для р3 равна 2 + 15 + 7 + 1 = 25. Стратегию жадного ОК можно выполнять различными способами.
Следует отметить, что исследователи продолжают поиск оптимального ОК.
Рисунок 8 - Поиск оптимального ОК
Рассмотрим кратко основные операторы мутации (ОМ). Мутация необходима потому, что предотвращает потерю важного генетического материала. Обычно ОМ является одноточечным оператором, который случайно выбирает ген в хромосоме и обменивает его на рядом расположенный ген. Например, одноточечный ОМ имеет вид:
Рисунок 9 - Одноточечный ОМ
Двухточечный ОМ заключается в перестановке генов, расположенных справа от точек разрыва. Например:
Рисунок 10 - Двухточечный ОМ
Процесс преобразования в ЕС и ИС обычно происходит толчками. При этом важную роль играют толчковые мутации. Они не изменяют размера и строения хромосом, а изменяют взаимное расположение генов в хромосоме.
В оптимизационных задачах, с нашей точки зрения, интерес может представлять использование ОМ, основанных на знаниях о решаемой задачи.Такие ОМ называются аргументированными знаниями. В них могут переставляться местами любые выбранные гены в хромосоме. Как правило, втаких ОМ точка или точки мутации определяются не случайно, а направленно. Например, в позиционном операторе мутации две точки мутации выбираются случайно, а затем ген, соответствующий второй точке мутации, размещается в позицию перед геном, соответствующим первой точке мутации. Например:
Рисунок 11 - Пример
Согласно Д. Холланду, ОМ выполняется следующим образом:
.В хромосоме А = (a1, a2, a3,..., aL-2, aL-1, aL) определяются случайным образом две позиции (например, а2 и aL-1).
.Гены, соответствующие выбранным позициям, переставляются, и формируется ?/p>