Представление преобразования "генотип – фенотип" для генетических вычислений

П. П.Макарычев, Н. В. Слепцов

Размещено на http://www.allbest.ru/

72

ВЕСТНИК ПЕРМСКОГО УНИВЕРСИТЕТА

2011 Математика. Механика. Информатика Вып. 1(5)

62

Пензенский государственный университет

Представление преобразования "генотип - фенотип" для генетических вычислений

П.П. Макарычев, Н.В. Слепцов

Аннотация

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

Ключевые слова: эволюционно-генетический поиск; кодирование; сетевые структуры; преобразования.

Annotation

Transformation representation "a genotype - a phenotype" for Genetic calculations

P. P. Makarychev, N. V. Sleptsov Penza State University

The way of increase of efficiency avolution - genetic search is considered. Concrete mechanisms of coding of modular network structures are offered, procedures of direct and return transformations are described.

Key words: evolutionary and genetic search; encryption; network structure; transform.

1. Введение

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

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

Преимущества эволюционных алгоритмов в свою очередь способствовали разработке способов формального и целенаправленного управления методами эволюционно-генетических вычислений (ЭГВ). Конкретизация применений данных методов предполагает реализацию 2 составляющих: представление исходной проблемы и обеспечение конструктивности получаемых/генерируемых решений. Обе составляющие тесно связаны друг с другом и поэтому методы решения, применяемые в одном случае, востребованы, хотя бы частично, в другом.

Представление исходной проблемы - формирование отображения структуры данных задачи в код ЭГВ [1, 7]. Принципиально здесь речь идет о прямом кодировании задачи в генотипе особи или о кодировании алгоритма получения (точнее - развертывания) решения в фенотипе. Достоинства и недостатки подходов очевидны: в первом случае обеспечивается наглядность, но возникают проблемы с манипулированием строками большой размерности, что ограничивает размерность и модульность итоговых решений, во втором случае обеспечивается и размерность, и модульность решений, но мы отказываемся от прозрачности представления задачи в генетическом коде и дополнительно решаем проблему преобразования генотипа в фенотип. Последняя проблема принципиально не может быть разрешена однозначно [2, 3, 4], требует анализа и учета дополнительных факторов и механизмов, однако ее потенциальная мощность должна интенсивно исследоваться [7].

2. Кодирование модульности

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

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

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

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

Для поиска решений нейронной сетью с применением ГА есть несколько методов, главные из них приведены ниже.

· Применение ГА для поиска весов данной структуры сети, которые дают минимальную ошибку. При этом ГА используется вместо алгоритма обучения, например алгоритма обратного распространения. Гены применяемого ГА имеют взаимно однозначное соответствие весам сети. Незначительные модификации этого метода дают ГА для поиска весов, обеспечивая очень точную настройку алгоритма обучения [6 и 12].

· Использование ГА для поиска структуры сети. Этот метод ГА осуществляет поиск оптимальной структуры сети, а не настройку весов для данной структуры. Гены ГА содержат кодировку для топологии сети, определяя наличие связей. Веса сети должны настраиваться в процессе обычного обучения [10].

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

В большинстве работ, посвященных поиску удачных топологий сети с применением ГА, использован подход, основанный на методе проекта кодирования топологии в генах членов популяции [9]. Но фактически такой подход означает упрощение, поскольку кодировка генами определяет не проект, а способ, рецепт получения окончательного результата. Поэтому представляет особый интерес способ описания развертывания кодировки в результат перехода от генотипа к фенотипу. Задача облегчается тем, что окончательный объект - ИНС - допускает четкое формальное описание.

3. Применение графовых грамматик для перехода к фенотипу

генетический фенотип графовый модульный

Нейронная сеть, рассматриваемая как соединение узлов и дуг, является графом; соответственно метод описания кодирования ИНС должен относиться к методам генерации графов. Недостатком существующих формальных языков описания графов [10] является то, что они не позволяют в явной форме отражать развитие исследуемых форм (конструкций, растений и т.д.). L-системы - модель реального мира, основанная на имитации роста и развития биологических объектов. Математически L-системы - специальный класс фракталов. L-систему можно определить как параллельный строковый перезаписывающий механизм, являющийся одной из разновидностей грамматик.

Рис. 1 Представление системы L1: аксиома F F> F [+F]F[-F]F 5 шагов, д = 26°

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

Каждый символ может интерпретироваться как направление, например, если F будет означать рисование линии, - и + соответственно левый и правый повороты, то действия при разборе элементов строки будут состоять из рисования линии и поворотов. Величину угла для символов - и +, которая может меняться, обозначим д. Левая часть правила вывода (до -->) описывает подстроку, которая будет заменена.

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

[ - запомнить текущую позицию и направление перемещения;

] - восстановить последнюю сохраненную позицию и направление.

Применение этих скобочных символов обеспечивает реалистичное отображение (см. рис. 1 [11]).

Одно из главных преимуществ L-систем по сравнению с обычными графовыми грамматиками - простота включения контекста, что позволяет задать явную аналогию дифференциации узла (фрагмента, ячейки) при росте ИНС.

а б

Рис 2 Правила вывода

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

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

· L-системы,

· искусственные нейронные сети,

для того чтобы спроектировать метод автоматического поиска оптимальных модульных нейросетевых структур.

Применяемый подход основывается на следующей совокупности шагов:

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

2. L-система обеспечивает развитие ИНС, следуя правилам, закодированным в хромосоме. Хромосома декодируется и преобразуется в ряд правил вывода. Они применены к аксиоме для произведения ряда итераций, и получающаяся строка преобразуется в спецификацию структуры для сети.

3. Полученная ИНС обучается для выполнения конкретной задачи. Итоговая ошибка преобразуется в оценку пригодности, это значение возвращается ГА (рис. 3).

Рис. 3 Взаимодействие применяемых методов

4. Кодирование и переход от сетевого представления к строковому

В соответствии с изложенным ГА должен управлять определенной популяцией, состоящей из наборов правил вывода. Каждый член популяции - двоичная строка, содержащая одно или более правил вывода для L-системы. Для определения пригодности строки производится извлечение из нее правила вывода, далее L-система перезаписывает аксиому, используя эти правила. Получающаяся строка интерпретируется как сеть, которая далее обучается, например, методом обратного распространения. Применение метода обратного распространения ограничивает возможную топологию прямонаправленными сетями: все узлы индексируются так, что присутствуют только связи от n_i до n_j для i<j.

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

Примеры сетей. Рассмотрим ряд структур, применяемых для оценки эффективности применяемых строчных нотаций.

Рис. 4 Базовые элементы сети

На рис. 4. показаны четыре основных элемента, применяемых при оценке строк; a и b - простые структуры, c и d комбинируют эти элементы, вводя элементы модульности, что необходимо для представления грамматики.

На рис. 5 представлены две стандартные сети, способные разрешить столь же стандартную проблему исключающего ИЛИ (XOR). Дополнительная связь в b обеспечивает лучшие результаты, хотя кодирование строки в этом случае будет сложнее.

a b Строки с относительным пропуско

Рис. 5 Сети XOR

Строки с относительным пропуском. Строки образованы символами {A-Z, 1-9, [,]} {,}.Узлы сети представляются символами алфавита (A-Z). Два смежных символа по умолчанию определяют прямую связь. Два разделенных запятой символа означают отсутствие связи. Модули указываются группировкой узлов (или других модулей) внутри квадратных скобок.

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

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

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

Цифра x интерпретируется как "пропуск x узлов и/или модули с правой стороны от текущей позиции и образование связи со следующим узлом или модулем".

Для строки A1BC узел A связан с C (1-пропуск B), но также и с B, поскольку между A и B отсутствует запятая). Для строк A1, BC или A,1BC узел A связан только с С. При пропуске модули интерпретируются как одно целое, поэтому для строки A1,[BC]D узел A связан с D, но не с C.

Если указатель пропуска содержится в модуле и выходит за пределы закрывающей скобки, пропуск продолжается после ].

В строке [A2 [B, C] D] E узел A связан с узлами B и C, потому они оба являются входными узлами модуля [B, C] (при отсутствии запятой между B и C A не был бы связан с C). Узел A также связан с узлом E, поскольку указатель пропуска 2 обеспечивает пропуск [B, C] и D и соединяет узел с E (несмотря на то, что E находится вне модуля, содержащего A).

Сеть, закодированная такой строкой, представлена на рис. 6.

Рис 6 Интерпретация строки [A2 [B, C] D] E