🗊Генетические алгоритмы

Генетические алгоритмы

Генетические алгоритмы Понятие генетического алгоритма

Принцип работы ГА Задача кодируется таким образом, чтобы её решение могло быть представлено в виде вектора («хромосома»). Случайным образом создаётся некоторое количество начальных векторов («начальная популяция»). Они оцениваются с использованием «функции приспособленности», в результате чего каждому вектору присваивается определённое значение («приспособленность»), которое определяет вероятность выживания организма, представленного данным вектором. После этого с использованием полученных значений приспособленности выбираются вектора (селекция), допущенные к «скрещиванию». К этим векторам применяются «генетические операторы» (в большинстве случаев «скрещивание» - crossover и «мутация» - mutation), создавая таким образом следующее «поколение». Особи следующего поколения также оцениваются, затем производится селекция, применяются генетические операторы и т. д. Так моделируется «эволюционный процесс», продолжающийся несколько жизненных циклов (поколений), пока не будет выполнен критерий остановки алгоритма. Таким критерием может быть: нахождение глобального, либо субоптимального решения; исчерпание числа поколений, отпущенных на эволюцию; исчерпание времени, отпущенного на эволюцию.

Этапы генетического алгоритма Создание начальной популяции Вычисление функций приспособленности для особей популяции (оценивание) Начало цикла: Выбор индивидов из текущей популяции (селекция) Скрещивание и\или мутация Вычисление функций приспособленности для всех особей Формирование нового поколения Если выполняются поставленные критерии, то Конец цикла иначе Начало цикла.

Модель «эволюционного процесса»

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

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

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

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

Пример ГА: Решение Диофантова уравнения Рассмотрим диофантово (только целочисленные решения) уравнение: a+2b+3c+4d=30, где a, b, c и d – некоторые положительные целые. Применение ГА за очень короткое время находит искомое решение (a, b, c, d). Для начала выберем 5 случайных решений: 1 =< a,b,c,d =< 30

Таблица 3: Вероятность оказаться родителем Таблица 3: Вероятность оказаться родителем

Средняя приспособленность (fitness) потомков оказалась 38.8, в то время как Средняя приспособленность (fitness) потомков оказалась 38.8, в то время как у родителей этот коэффициент равнялся 59.4. Следующее поколение может мутировать. Например, мы можем заменить одно из значений какой-нибудь хромосомы на случайное целое от 1 до 30. Продолжая таким образом, одна хромосома в конце концов достигнет коэффициента выживаемости 0, то есть станет решением.

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

Использование генетических алгоритмов для автоматического формирования программ управления движением автономных реконфигурируемых мехатронно-модульных роботов Использование генетических алгоритмов для автоматического формирования программ управления движением автономных реконфигурируемых мехатронно-модульных роботов Совершено самостоятельный аспект исследований, которые активно проводятся в рамках этой очень широкой тематики, связан с попытками применения генетических алгоритмов для решения задач по автоматическому формированию программ, выполняющих требуемые функции. Подобные задачи приобретают особую актуальность в контексте проблем разработки принципиально нового класса технических систем, обладающих способностями к самоорганизации и самообучению. Одним из примеров систем такого рода являются многозвенные реконфигурируемые мехатронно-модульные роботы, техническая реализуемость которых подтверждается результатами ряда известных проектов. Так, в лабораторных испытаниях конкретных образцов реконфигурируемых мехатронно-модульных роботов различных типов, включая Poly Bot (PARK, USA), Polypod (Stanford University, USA), MTRAN (AIST, Japan) и др., неоднократно демонстрировалась возможность изменения кинематической структуры за счет автоматической перестыковки ее фрагментов.

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

Формирование программы управления мехатронно-модульного робота в Формирование программы управления мехатронно-модульного робота в конфигурации шагающего устройства предполагает необходимость построения целесообразной последовательности циклических изменений состояния конечностей, обеспечивающей тот или иной вид походки. При этом изменение состояния конечностей соответствует выполнению элементарных движений из следующего набора: • поднять конечность; • опустить конечность; • повернуть конечность вперед (+15°); • повернуть конечность в нейтральное положение (0°); • повернуть конечность назад (—15°). Будем считать, что реализация оговоренных движений определяется радом допущений: • прямоугольная система координат робота связана с его узловым модулем; • точки крепления конечностей к узловому модулю совпадают с осями системы координат робота; • движение каждой конечности в вертикальной, плоскости осуществляется поворотами шарниров первого и второго модулей (в порядке следования от узлового) • движение каждой конечности в горизонтальной плоскости осуществляется поворотом шарнира, первого модуля (по отношению к узловому)

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

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

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

Анализ экспериментальных данных показывает, что в смысле полезности Анализ экспериментальных данных показывает, что в смысле полезности полученных хромосом автоматически формируемые с помощью генетического алгоритма решения в ряде отдельных случаев оказываются намного более эффективными, чем синтезируемые экспертом. При этом следует отметить, что если поиск приемлемых решений по формированию программ управления походкой шагающего робота в автоматическом режиме по времени занимает от 10 до 30 минут, то для эксперта решение аналогичной задачи требует от 1,5 до 3 суток.

АППАРАТНАЯ РЕАЛИЗАЦИЯ ГЕНЕТИЧЕСКИХ АЛГОРИТМОВ АППАРАТНАЯ РЕАЛИЗАЦИЯ ГЕНЕТИЧЕСКИХ АЛГОРИТМОВ Идея применения генетических алгоритмов в системах автоматизированного проектирования активно развивается наряду с другими направлениями. Впервые эта идея была предложена С. Луисом [Louis et al., 1991] и Д. Раулинсом [Rawlins et al., 1993] в 1991 году и экспериментально проверена в области цифровых схем. В дальнейшем, предложенные методы были развиты и доработаны, и получили применение во многих автоматизированных системах проектирования аппаратуры. Использование генетических алгоритмов (ГА) [Курейчик 2004 и др.] как механизма для автоматического проектирования схем на реконфигурируемых платформах [Blondet et al., 2003], получило название эволюционные аппаратные средства (Evolvable Hardware) [Higuchi et al., 1993], [Sakanashi et al., 1999], которое также используется синонимом для несколько общего направления, известного как эволюционная электроника (Evolutionary Electronics) [Zebulum et al., 2002]. Для автономных решений и задач, связанных с построением эволюционных аппаратных средств, программная реализация ГА является неприемлемой по целому ряду критериев. Сам факт автономности исключает наличие возможности использования программных решений, выполняемых на ПК или кластерным методом. С другой стороны, автономные системы, как правило, функционируют в режиме реального времени, что накладывает ряд требований на временные характеристики используемых алгоритмов, в связи с чем, вопрос использования программных моделей перестает быть актуальным.