Процесс работы ГА. Часть 1

Процесс работы ГА – совокупность характеристик оптимизационной задачи, кодирование которой выполняется в последовательность, имеющую определенную длину. Работа алгоритма прекращается в случае выполнения заранее известного количества его итераций; алгоритм может быть остановлен, если поставленная задача решена и получен удовлетворяющий исходным данным ответ. Еще одним случаем завершения выполнения процесса является нахождения локального оптимума при исполнении одной из итераций, когда нет возможности найти выход из сложившейся ситуации преждевременной сходимости. Процессы ГА отличаются от других способов оптимизации своей возможности проводить анализ сразу несколько областей пространства решений задачи. Это позволяет определять большее количество новых областей, где параметры ЦФ лучше.

 

Рассмотрим главные термины генетического алгоритма. Начальной информацией для процессов ГА является популяция альтернативных решений P. Число элементов P_i рассчитывается по следующей формуле:

 

Р^t = {P₁ P₂…..P_i._, P_NP)

 

Здесь последовательность t – это номер итерации генетического алгоритма, N – размер популяции. Все элементы P имеют одинаковую структуру; они включают в себя некоторый набор хромосом или особей. Хромосомы – набор генов:

 

Р_i ={g₁,g₂,…,g_v}

 

Локус – схематическое местоположение генов в хромосоме.

 

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

 

Запись кодированной хромосомы длиной 9 в двоичной системе исчисления выглядит следующим образом:

 

Р_i = (001001101).

 

Зачастую некоторые элементы процесса ГА имеют термин «родительский». Родители обладают свойства, заданные заранее. Родителей с заданными характеристиками скрещивают для выведения нового «потомства». Один цикл эволюции «родителей» и «детей» позволят получить новую популяцию. Исполнение единичной итерации именуется поколением.

 

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

 

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

 

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

 

Алгоритм ГА начинают свою работу с создания множества возможных решений для выполнения оптимизации поставленной задачи. Этим он схож с природным процессом создания первой популяции. Далее «родители» создают «детей» за счет появления в них изменений. После проверки изменений на эффективность, продолжаются процессы селекции. Как и в природе при выполнении процессов оптимизации ГА, здесь на первый план выходит «закон выживания»: слабые элементы погибают, и процесс начинается вновь.

 

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

 

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

 

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

 

Алгоритм ГА включает в себя несколько предварительных этапов:

 

1. Подбор вида для представления найденного решения;
2. Выбор операторов для возможных изменений;
3. Разработка перечня условия для «выживания»;
4. Создание первой популяции из будущего множества решений.

 

Рассмотрим каждый этап подробнее.

 

Подбор вида для представления найденного этапа.

 

В ходе работы над этапом №1 необходимо разработать тот вид отображения решения, который даст возможность во время выполнения процесса алгоритма ГА даст возможность кодировать любое решения и анализировать его. Уже давно установлено, что идеального отображения нет. Поэтому чтобы создать наиболее оптимальное представление, придется произвести глубокий анализ, перебор и воспользоваться эвристическим подходом. Такое отображение должно дать возможность перестанавливать различные составляющие в различных видах решений. Что делать правильную оценку, надо разработать метод для исчислений значений ЦФ.

 

Подбор операторов для возможных решений

 

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

 

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

 

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

 

Разработка перечня условия для «выживания».

 

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

 

Создание первой популяции из будущего множества решений.

 

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

 

Эффективность ГА зависит от качества выполнения запланированных действий и от результатов его выполнения. Успех нахождения решения зависит от параметров и состава первоначальной популяции.

 

Операторы

 

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

 

Алгоритм – совокупность операторов. Оператор отображает одно множество алгоритма на другое.

 

Основные операторы могут разделяться на несколько видов:

 

Селекционный оператор – процесс, где решения с более качественным ЦФ получают лучшие условия для воспроизводства потомства. К данным операторам относят:

 

1. Селекционные операторы, выбранные методом «рулетки». Данный метод является наиболее простым из всех возможных. Его реализация выглядит в виде колеса рулетки, поделенного на зоны. Каждой зоне соответствует элемент популяции. Причем размер зоны зависит от величины ЦФ, поэтому большую возможность породить потомство имеют элементы с большим ЦФ.
2. Операторы, которые избираются методом «заданной шкалы». Использование данного метода создает необходимость создания шкалы, значениями которой является один выбранный параметр. Элемент популяции получает свое число и устанавливается на данной шкале. Чем выше располагается элемент, тем больше у него шансов на воспроизведение потомства.

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

 

1. Операторы, полученные методом турнирной селекции. Из количества элементов, основываясь на размере «турнира», выбирается часть. Выбор происходит случайным образом или направлено. Далее из выбранных элементов выбирают те, которые станут «родителями» для дальнейшего потомства.

 

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

 

Существует два типа для реализации репродуктивного оператора:

 

• Выбор хромосом случайным образом.
• Выбор, основанный на анализе значений ЦФ.

 

Первый вариант означает независимость частоты R при образовании пар первостепенных элементов от целевых функций Р_к^t. Данная частота напрямую зависит от множества популяций:

 

 

Здесь   означает селекционный коэффициент. Он может принимать значения от 1 до 4 и зависит от условий окружающей среды.

 

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

 

Если во время выполнения первого направления максимизация ЦФ происходит с вероятностью, рассчитанной по формуле

 

P_r(OP)= , k от 1 до n,

 

 

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

 

Для реализации второго направления все хромосомы делятся на две части. В первую попадают хромосомы, отобранные случайным методом, во вторую – посредством выражения 3.2.

 

В случае, когда ЦФ(Р_к^t) < ЦФ_ср,, где ЦФ_ср  — усредненное величина ЦФ популяции, то отбор происходит естественным образом. Случайный набор хромосом в популяции повышает ее разнообразие. От этого напрямую зависит скорость схождения в первом этапе ГА.

 

Но описанные выше методы селекции не единственные. Их существует огромное множество, и все они разделяются на три основных группы:

 

• Вероятностные методы
• Детерминированные методы
• Комбинации первых и вторых методов

 

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

 

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

 

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

 

Рассмотрим пример, где популяция P состоит из «родителей» P₁ и P₂. Первая родительская хромосома имеет вид P₁:(11111), вторая – P₂:(00000). Разрез будем производить между вторым и последующим генами. Проведя «рассечение», мы можем поменять элементы между P₁ и P₂ и получить новые элементы. Простой ОК исполняется в три шага. В нашем примере:

 

P1: 1 1 | 1 1 1 P’1: 0 0| 0 0 0

P2: 1 1 | 0 0 0 P’2: 0 0 | 1 1 1

 

1. Две хромосомы обираются случайным методом:

 

А = а₁, а₂,.., a _L и В = а’₁, а’₂,.., a’_L

 

2. Как и хромосомы, значение К имеет также случайный характер из множества {1,2,…,L-1). Под L понимают длину хромосомы, К – точка «разреза».
3. Новые хромосомы образуются из А и B путем смены элементов, подчиняющихся законам:

 

A’ = а₁, а₂,…, а’_k, а’_k+1, ,…, a’_L ,

В’=а’₁,а’₂,…,a’_k,а’_k+1,…,a’_L.

 

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

 

В итоге простой ОК частично изменяет хромосомы и производит обмен элементов между ними.

 

Двухточечный оператор. Этот оператор отличается от простого созданием двух точек «разреза» и обменом не элементами, а группами элементов.

 

P1: 1 1 1 | 0 1 | 0 0

P2: 0 0 0 | 1 1 | 1 0

P’1: 1 1 1 | 1 1 | 0 0

P’2: 0 0 0 | 0 1 | 1 0

 

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

 

P1: 1 | 1 1 | 0 1 | 0 0

P2: 0 | 0 0 | 1 0 | 1 1

P’1: 1 | 0 0 | 0 1 | 1 1

P’2: 0 | 1 1  1 0 | 0 0

 

В трехточечном ОК при разрезе получаются строительные блоки. В нашем случае таких блоков четыре. Потомственный элемент Р’₁ создается путем скрещивания нечетных блоков родительского элемента P₁ и четных P₂. Соответственно, элемент Р’₂  — скрещивание четного ряда P₁ и нечетного P₂. Обмен элементами в многоточечном операторе кроссинговера происходит по той же схеме.