Генетические алгоритмы в изобретательских задачах
Курсовой проект - Менеджмент
Другие курсовые по предмету Менеджмент
?овая хромосома. ОМ - А = (a1, a2, a3,..., aL-2, aL-1, aL).
Заметим, что в ПГА ОК - бинарная операция, а ОМ - унарная операция. Кроме того, ОК и ОМ соответствуют перестановкам элементов внутри заданного множества. Важным понятием в ОМ является шкала мутации, которая определяет, какой процент общего числа генов в популяции видоизменяется в каждой генерации. Для оптимизационных задач вероятность ОК обычно принимают равной 0,60,99. а вероятность ОМ от 0,6 и меньше.
Кроме мутации, популярным и используемым в ЕС и ИС является оператор инверсии. В операторе инверсии случайным образом определяется одна или несколько точек инверсии, внутри которых элементы инвертируются.
Генетический оператор инверсии в ГА Д. Холланда состоит из следующих шагов:
.Хромосома В = (b1, b2, ..., bL) выбирается случайным образом из текущей популяции.
.Два числа у1 и у2 выбираются случайным образом из множества {0, 1, 2, ..., L+1}, далее определяем у1 = min{ у1, у2} и у2 = max{ у1, у2}.
.Новая хромосома формируется из В путем инверсии сегмента, который лежит справа от позиции у1 и слева от позиции у2 в хромосоме В.
Тогда, после применения оператора инверсии, получаем B1 :B1=(b1,…, by1, by2-1, by2-2,…, by1+1, by2,…, bL)
Например, для двухточечного оператора инверсии получим:
Рисунок 12 - Двухточечный ОИ
Для одноточечного оператора инверсии запишем:
Рисунок 13 - Одноточечный ОИ
Кроме простого оператора инверсии, вописан специальный оператор инверсии. В нем точки инверсии определяются с заданной вероятностью для каждой новой создаваемой хромосомы в популяции. Оператор инверсии до последнего времени не получил широкого использования при решении оптимизационных задач.
Рассмотрим оператор транслокации. Он представляет собой комбинацию ОК и оператора инверсии. В процессе транслокации случайным образом производится один разрыв в каждой хромосоме. При формировании потомка p1 берется левая часть до разрыва из родителя p1 и инверсия правой части до разрыва из р2. При создании p2 берется левая часть р2 и инверсия правой части р1. Приведем пример оператора транслокации:
Рисунок 14 - Оператор транслокации
Существует большое число других видов оператора транслокации. Отметим, что до последнего времени оператор транс локации не применялся в ГА, а также при разработке интеллектуальных ИС и решении оптимизационных задач.
Кроме описанных операторов, по мнению авторов, интерес может представлять оператор сегрегации и различные его модификации. Приведем один из примеров реализации оператора сегрегации. Отметим, что оператор сегрегации, как правило, реализуется на некотором наборе хромосом. Пусть имеется популяция Р, состоящая из четырех родительских хромосомР = {р1, р2, р3, р4}: р1: (1234); р2: (2431); р3: (3142); р4: (4321). Тогда потомок p1 можно сформировать случайным образом, взяв первый элемент (один или несколько генов) из p1, второй из р2, третий из р3 и четвертый из р4. При этом должны быть отброшены повторяющиеся решения, или решения, содержащие одинаковые элементы. Так, вариант p1: (1412) должен быть отброшен как содержащий две единицы, а вариант p2: (2143) является легальным (допустимым или реальным). Очевидно, что оператор сегрегации можно реализовать различными способами в зависимости от способа выбора генов из хромосом.
Опишем оператор удаления. При реализации оператора удаления направленным или случайным образом определяется точка или точки оператора удаления. Далее производится пробное удаление генов или их ансамблей с вычислением изменения ЦФ. При достижении экстремума ЦФ оператор удаления реализуется. Элементы, расположенные справа от точки оператора удаления или между двумя точками оператора удаления, удаляются из хромосомы.
Опишем оператор вставки. При реализации оператора вставки направленным или случайным образом определяется точка или точки оператора вставки. Затем анализируются другие гены хромосом в популяции для определения альтернативных вставок. Далее производится пробная вставка генов или их.ансамблей с вычислением изменения ЦФ. При достижении экстремума ЦФ оператор вставки реализуется. Новые гены или их ансамбли вставляются, в хромосому справа от точки оператора вставки или между его двумя, точками. Отметим, что оператор удаления и оператор вставки меняют размер хромосом. Для сохранения размера хромосом постоянным эти операторы необходимо применять совместно.
Рассмотрим теперь понятие рекомбинации. Функция рекомбинации определяет, как новая, генерация хромосом будет построена из родителей и потомков. Другими словами, функция рекомбинации - это анализ и преобразование популяции при переходе из одной генерации в другую. Существует много путей выполнения рекомбинации. Один из них состоит из перемещения родителей в потомки после каждого генетического оператора (ГО). Другой путь заключается в перемещении некоторого процента популяции, используя потомков в течение каждой генерации. Обычно в ГА задается параметр W(P), который управляет этим процессом. Так, NP(1 - W(P)) элементов в популяции Р, выбранных случайно, могут выжить в следующей генерации. Здесь NP - размер популяции. Величина W (Р) = 1 означает, что целая предыдущая популяция перемещается в новую в каждой генерации. При дальнейшей реализации алгоритма лучшие элементы из родителей и потомков будут выбираться, для формирования новой популяции[5,6].
.2 Простые генетическ