Частично-соответствующий оператор кроссинговера

Предыдущая 10 11 12 13 14 15 16 17 18 19 20 21 222324 25 Следующая

Здесь также случайно выбирается «разрезающая» точка или точка оператора кроссинговера. Дальше анализируются сегменты (части) в обеих хромосомах и устанавливается частичное соответствие между элементами первого и второго родителей с формированием потомков. При этом правый сегмент Р₂ переносится в Р'₁,левый сегмент Р₁переносится в Р'₁с заменой повторяющихся генов на отсутствующие гены, находящиеся в частичном соответствии. Например:

Аналогично можно получить Р'₂:

3.12. Циклический оператор кроссинговера

Циклический оператор кроссинговера выполняет рекомбинации согласно циклам, которые существуют при установлении соответствия между генами первого и второго родителей. Например, пусть популяция Р состоит из двух хромосом: Р₁ и Р₂, Р = {Р₁, Р₂}. Первый и второй родители и их потомок имеют вид:

При выполнении циклического оператора кроссинговера Р'₁заполняется, начиная с первой позиции, и копирует элемент с первой позиции Р₁. Элементу 1 в Р₁ соответствует элемент 5 в Р₂. Следовательно, имеем первый путь в цикле (1,5). Элементу 5 в Р₁соответствует элемент 4 в Р₂, откуда второй путь в первом цикле (1,5; 5,4). Продолжая далее, получим, что элементу 4 в Р₁ соответствует элемент 1 в Р₂. Следовательно, сформирован первый цикл (1,5; 5,4; 4,1). Согласно этому циклу элемент 5 переходит в пятую позицию Р'₁,а элемент 4 – в четвертую позицию.

Сформируем теперь второй цикл. Элемент 2 в Р₁соответствует элементу 3 в Р₂. Продолжая аналогично, получим второй цикл (2,3; 3,9; 9,6; 6,8; 8,2) и третий (7,10; 10,7) циклы.

Следовательно, в Р'₁элемент 3 расположен во втором локусе, т. е. на второй позиции, элемент 9 – в третьем, элемент 6 – в девятом, элемент 8 – в шестом, элемент 2 – в восьмом, элемент 10 – в седьмом и элемент 7 – в десятом локусах. Циклический оператор кроссинговера и его модификации эффективно применяются для решения комбинаторно-логических задач, задач на графах и гиперграфах и других оптимизационных задач.

3.13.Оператор мутации

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

Оператор мутации обычно состоит из двух этапов:

1. В хромосоме А = (а₁, а₂, … , а_L_-₂, а_L_-₁, а_L) определяются случайным образом две позиции (например, а₂ и а_L_-₁).

2. Гены, соответствующие выбранным позициям, переставляются, и формируется новая хромосома А³ = (а₁, а_L_-₁, а₃, … , а_L_-₂, а₂, а_L).

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

,

где Р₁ – родительская хромосома, а Р'₁ - хромосома-потомок после применения одноточечного оператора мутации.

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

,

где Р₁– родительская хромосома, а Р'₁ – хромосома-потомок после применения двухточечного оператора мутации.

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

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

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

При нечетном числе точек потомок получается после обмена участками хромосом, расположенных между четными точками разреза, например:

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

В позиционном операторе мутации две точки разреза выбираются случайно, а затем ген, соответствующий второй точке мутации, размещается в позицию перед геном, соответствующим первой точке, например:

Р₁: А | ВСD | ЕF

Р'₁: А ЕВС D F.

Оператор инверсии

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

Генетический оператор инверсии состоит из следующих шагов.

1. Хромосома В = b₁, b₂,…, b_L выбирается случайным образом из текущей популяции.

2. Два числа у'₁и у'₂выбираются случайным образом из множества {0,1,2,..., L+1}, причем считается, что y₁ = min { у'₁, у'₂}и y₁ = max { у'₁, у'₂}.

3. Новая хромосома формируется из В путем инверсии сегмента, который лежит справа от позиции у₁и слева от позиции у₂в хромосоме В. Тогда после применения оператора инверсии получаем:

В = (b₁, b_y₁, b_y_2-1, b_y_2-2,…, b_y₁₊₁, b_y₂,…, b_L ).

Для одноточечного оператора инверсии запишем

где Р₂ - родительская хромосома, Р'₂ – хромосома-потомок после применения оператора инверсии.

Например, для двухточечного оператора инверсии получим

где Р₁ – родительская хромосома, Р'₁ – хромосома-потомок после применения двухточечного оператора инверсии.

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

На рис. 3.11 представлена триада генетических операторов.

Рис. 3.11. Триада генетических операторов

3.15. Оператор редукции

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

Численность новой популяции

где N^t⁺¹ – численность новой популяции; N^t – численность популяции на предыдущем шаге (поколении) t; N_ОК, N_ОМ, N_ОИ, N_ОТ, N_ОТР, N_ОС, N_ОУ, N_ОВ–потомки, полученные в результате применения операторов: кроссинговера, мутации, инверсии, транслокации, транспозиции, сегрегации, удаления, вставки.

Транслокация (от транс и лат. locatio — размещение), – тип хромосомной перестройки (мутации), заключающийся в переносе гена или участка хромосомы в новое, необычное положение (локус) в той же или другой хромосоме. В ходе транслокации происходит обмен участками негомологичных хромосом, но общее число генов не изменяется.

Транспозиция (транспони́рование, транспониро́вка; от позднелат. transpositio — перестановка, перемещение) в комбинаторике – перестановка, которая меняет местами только два элемента. Транспозиция в генетике – перемещение определенных генетических элементов из одного места на хромосоме в другое.

Сегрега́ция (позднелат. segregatio — отделение) — политика принудительного отделения какой-либо группы населения. Обычно упоминается как одна из форм религиозной и расовой дискриминации (отделение группы по расовому или этническому признаку).

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

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

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

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

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

· мутации.

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

Гибридные системы

Весь цикл разработки и эксплуатации любой сложной системы носит итеративный характер (рис. 3.12). Выполнение любой итерации, как показано на рис. 3.12, проводится с использованием моделей сложной системы. Наиболее продвинутым и мощным аппаратом построения соответствующих моделей для рассматриваемых систем является имитационное моделирование. оно обеспечивает глубокое представление моделируемого объекта , дает возможность анализа процессов на любом временном интервале, позволяет учитывать случайные и неопределенные факторы, оценивать как технические, так экономические показатели функционирования системы.

Рис. 3.12. Цикл разработки сложной системы

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

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

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

Рис. 3.13. Простейшая гибридная система

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

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

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

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

Рис. 3.14. Простейшая гибридная система с генетическим алгоритмом и имитационной моделью

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

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

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

Рис. 3.15. Структура типовой гибридной схемы

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

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

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

Экспертная система осуществляет направленный выбор таких параметров ПГА, как: размер популяции, вероятности скрещивания и мутации. Кроме того, она применяет некоторые правила для сохранения особей с высоким значением функции пригодности из поколения в поколение в ходе из воспроизводства и т.п.

Экспертная система, таким образом, представляет область комбинаций знаний о генетических алгоритмах, вычислительной математике, искусственном интеллекте и знаний эксперта. Прикладная область для экспертной системы хорошо не определена и пространство поиска плохо структурировано и поэтому экспертная система работает наряду с ПГА на основе текущих данных относительно популяции и текущего состояния имитатора.

Предыдущая 10 11 12 13 14 15 16 17 18 19 20 21 222324 25 Следующая

Не нашли, что искали? Воспользуйтесь поиском по сайту: