Магистр ДонНТУ:    Джура Валерий Петрович
Факультет:    Компьютерные Информационные Технологии и Автоматика
Специальность:    Компьютерная инженерия
Тема:    «Аппаратная реализация компактных генетических алгоритмов на ЯOА VHDL»
Руководитель:    Скобцов В. Ю.

ВВЕДЕНИЕ

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

Использование генетических алгоритмов (ГА) как механизма для автоматического проектирования схем на реконфигурируемых платформах, получило название эволюционные аппаратные средства (Evolvable Hardware) которое также используется синонимом для несколько общего направления, известного как эволюционная электроника (Evolutionary Electronics).

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

Актуальность и научная новизна темы.

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

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

Цель работы

Цель работы спроектировать аппаратную реализацию компакных генетических алгоритмов. Оценить все плюсы и минусы аппаратной реализации компактных генетических алгоритмов.

1. ОБЩИЕ СВЕДЕНИЯ

      1.1. Эволюционная теория

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

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

Чтобы сделать понятными принципы работы генетических алгоритмов, поясним также, как устроены механизмы генетического наследования в природе. В каждой клетке любого животного содержится вся генетическая информация этой особи. Эта информация записана в виде набора очень длинных молекул ДНК (ДезоксирибоНуклеиновая Кислота). Каждая молекула ДНК - это цепочка, состоящая из молекул нуклеотидов четырех типов, обозначаемых А, T, C и G. Собственно, информацию несет порядок следования нуклеотидов в ДНК. Таким образом, генетический код индивидуума - это просто очень длинная строка символов, где используются всего 4 буквы. В животной клетке каждая молекула ДНК окружена оболочкой - такое образование называется хромосомой.

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

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

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

      1.2. Естественный отбор и генетическое наследование

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

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

Почти в каждой клетке любого животного имеется набор хромосом, несущих информацию об этом животном. Основная часть хромосомы — нить ДНК (молекула дезоксирибонуклеиновой кислоты), которая состоит из четырех видов специальных соединений — нуклеотидов, идущих в определенной последовательности. Нуклеотиды обозначаются буквами A, T, C и G, и именно порядок их следования кодирует все генетические свойства данного организма. Говоря более точно, ДНК определяет, какие химические реакции будут происходить в данной клетке, как она будет развиваться и какие функции выполнять.

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

Различают два вида клеток: половые (такие, как сперматозоид и яйцеклетка) и соматические. В каждой соматической клетке человека содержится 46 хромосом. Эти 46 хромосом — на самом деле 23 пары, причем в каждой паре одна из хромосом получена от отца, а вторая — от матери. Парные хромосомы отвечют за одни и те же признаки — например, отцовская хромосома может содержать ген черного цвета глаз, а парная ей материнская — ген голубоглазости. Существуют определенные законы, управляющие участием тех или иных генов в развитии особи. В частности, в нашем примере потомок будет черноглазым, так как ген голубых глаз является “слабым” (рецессивным) и подавляется геном любого другого цвета.

В половых клетках хромосом только 23, и они непарные. При оплодотворении происходит слияние мужской и женской половых клеток и образуется клетка зародыша, содержащая как раз 46 хромосом. Какие свойства потомок получит от отца, а какие — от матери? Это зависит от того, какие именно половые клетки участвовали в оплодотворении. Дело в том, что процесс выработки половых клеток (так называемый мейоз) в организме подвержен случайностям, благодаря которым потомки все же во многом отличаются от своих родителей. При мейозе, в частности, происходит следующее: парные хромосомы соматической клетки сближаются вплотную, затем их нити ДНК разрываются в нескольких случайных местах и хромосомы обмениваются своими частями (рис. 1.2.1).

Рисунок 1.2.1. Условная схема кроссинговера. (Кол-во кадров 6, задерка 50 мс, размер файла 10 кб)

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

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

      1.3. Задачи оптимизации

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

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

Введем обозначения и приведем несколько классических примеров. Как правило, в задаче оптимизации мы можем управлять несколькими параметрами (обозначим их значения через x1, x2, ..., xn, а нашей целью является максимизация (или минимизация) некоторой функции, f(x1, x2, ..., xn), зависящей от этих параметров. Функция f называется целевой функцией. Например, если требуется максимизировать целевую функцию “доход компании”, то управляемыми параметрами будут число сотрудников компании, объем производства, затраты на рекламу, цены на конечные продукты и т. д. Важно отметить, что эти параметры связаны между собой — в частности, при уменьшении числа сотрудников скорее всего упадет и объем производства.

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

Классический пример такой задачи, известный как “задача коммивояжера” (Traveling Salesman Problem, TSP), формулируется так: коммивояжеру требуется объехать несколько городов, побывав в каждом один раз, и вернуться в исходную точку. Нужно найти кратчайший маршрут.

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

      1.4. Работа генетического алгоритма

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

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

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

(1.4.1)

Потом происходит отбор (с замещением) всех n особей для дальнейшей генетической обработки, соответственно величине Ps(і).

При таком отборе члены популяции с высокой приспособленностью с большей вероятностью будут выбираться чаще, чем особи с низкой приспособленностью. После отбора, n избранных особей случайным образом разбиваются на n/2 пары. Для каждой пары с вероятностью Ps может применяться кроссинговер. Соответственно, с вероятностью 1-Ps кроссинговер не происходит и неизмененные особи переходят на стадию мутации. Если кроссинговер происходит, полученные потомки заменяют родителей и переходят к мутации.

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

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

Кроссинговер (в литературе по генетическим алгоритмам также употребляется название кроссовер или скрещивание) - это операция, при которой из двух хромосом порождается одна или несколько новых хромосом. Одноточечный кросинговер работает следующим образом. Сначала, случайным образом выбирается одна из l-1 точек разрыва. (Точка разрыва - участок между соседними битами в строке.) Обе родительские структуры в этой точке разрываются на два сегмента. Потом, соответствующие сегменты разных родителей склеиваются и выходят два генотипа потомков.

Например, предположим, один родитель состоит из 10 нулей, а другой - с 10 единиц. Пусть из 9 возможных точек разрыва избрана точка 3. Родители и их потомки показаны ниже.

Родитель 1 0000000000 000~0000000 --> 111~0000000 1110000000 Потомок 1

Родитель 2 1111111111 111~1111111 --> 000~1111111 0001111111 Потомок 2

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

В настоящее время исследователи генов предлагают другие операторы отбора, кроссинговера и мутации. Ниже приведены наиболее распространенные.

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

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

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

Рисунок 1.4.1. Блок-схема генетического алгоритма.

      1.5. Применение генетических алгоритмов

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

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

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

      1.6. Преимущества и недостатки генетических алгоритмов

Преимущества генетических алгоритмов:

    •     Они не требуют никакой информации о поверхности ответа;

    •     Разрывы, существующие на поверхности ответа имеют незначительный эффект на полную эффективность оптимизации;

    •     Они стойки к попаданию в локальные оптимумы;

    •     Они хорошо работают при решении крупномасштабных проблем оптимизации;

    •     Могут быть использованы для широкого класса задач;

    •     Просты и прозрачны в реализации;

    •     Могут быть использованы в задачах с изменяющейся средой.

Не желательно и проблематично использовать ГА:

    •     В случае, когда необходимо найти точный глобальный оптимум;

    •     Время исполнения функции оценки велико;

    •     Необходимо найти все решения задачи, а не одно из них;

    •     Конфигурация является не простой (кодирование решения).

2. МЕТОДЫ МАТЕМАТИЧЕСКОГО МОДЕЛИРОВАНИЯ

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

Воспроизводство представляет собой процесс выбора K*N N строк популяции G(t) для дальнейших генетических операций. Выбор производится случайным образом, причём вероятность выбора строки S_i^t пропорциональна её ценности:

Процесс выбора повторяется K*N N раз. Предполагаемое количество экземпляров строки S_i^t в популяции G(t+1) равно

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

Пусть в популяции G(t) содержится n(H, t) строк, удовлетворяющих схеме H. Тогда в результате воспроизводства количество строк, удовлетворяющих схеме H в популяции G(t+1) будет равно n(H, t+1):

. (1)

Используя выражения для средней ценности популяции F_ср(G(t)) и подпопуляции F_ср(G_H(t)), можно записать формулу (1) в виде:

. (2)

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

.

Предположим, что величина c при изменении t не изменяется; тогда, начиная с t=0, получим: , т.е. в этом случае число представителей схемы (строк популяции G(t), соответствующих схеме) изменяется в геометрической прогрессии. В общем случае можно сказать, что процесс изменения представителей схемы так же аппроксимируется геометрической прогрессией.

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

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

Скрещивание представляет собой процесс случайного обмена значениями соответствующих элементов для произвольно сформированных пар строк. Для этого выбранные на этапе воспроизводства строки случайным образом группируются в пары. Далее каждая пара с заданной вероятностью p_скр подвергается скрещиванию. При скрещивании происходит случайный выбор позиции разделителя d (d=1, 2, ..., l-1, где l - длина строки). Затем значения первых d элементов первой строки записываются в соответствующие элементы второй, а значения первых d элементов второй строки - в соответствующие элементы первой. В результате получаем две новых строки, каждая из которых является комбинацией частей двух родительских строк.

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

Рассмотрим некоторую схему H, для которой определим порядок o(H) - число фиксированных позиций схемы и определяющую длину d (H) - расстояние (число позиций) между первой и последней фиксированными позициями. Допустим, что до операции скрещивания строка S была представителем схемы H, т.е. . Допустим, что строка S¹ получена из строки S в результате скрещивания. Строка S¹ будет представителем схемы H в том случае, если позиция разделителя при скрещивании не располагалась между фиксированными позициями схемы. Вероятность того, что позиция разделителя окажется между фиксированными позициями схемы, равна: .

Учтём, что скрещивание происходит с вероятностью p_c, а также то, что даже если позиция разделителя окажется между фиксированными позициями схемы, строка S¹ может являться представителем схемы H, если данная строка была получена скрещиванием двух представителей схемы H. Тогда вероятность p_s,1 того, что строка S¹ является представителем схемы H, определяется выражением: .

Полагая независимость операций воспроизводства и скрещивания, оценим совокупный эффект от этих операций, т.е. число представителей схемы H в популяции G(t+1):

.

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

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

Допустим, что до мутации строка S¹ была представителем схемы H, т.е. . Допустим, что строка S² получена из строки S¹ в результате мутации. Строка S² будет представителем схемы H в том случае, если ни один из элементов строки, соответствующий фиксированным позициям схемы, не был изменён.

Учитывая, что мутация происходит с вероятностью p_мут, вероятность p_s2 того, что строка S² является представителем схемы H, определяется выражением: , где o(H) - число фиксированных позиций схемы H.

Полагая независимость операций воспроизводства, скрещивания и мутации оценим совокупный эффект от этих операций, т.е. число представителей схемы H в популяции G(t+1):

. (3)

Так как, при малых значениях p_m приближенно можно считать , то выражение (3) можно записать в виде:

или

.

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

Очевидно, что эффективность описанной операции скрещивания значительно зависит от способа кодировки строк. Это свойство оказывается полезным для задач оптимизации функций, заданных на числовых множествах. Однако, если функция задана на произвольном множестве, например, на множестве комбинаций значений признаков объекта, где все признаки одинаковы по предпочтительности, то описанный выше способ скрещивания оказывается не вполне корректным, так как вероятность сохранения значений для групп признаков зависит от расстояния между элементами группы в кодовой строке, а это нарушает принцип равной предпочтительности признаков. Поэтому для таких задач операцию скрещивания предполагается производить путём обмена не частями строк, а отдельными элементами. При этом задаётся некоторое число позиций n_П (n_ПО {1, 2, …, l}), которое определяет количество элементов строк, для которых производится обмен значениями. Число позиций n_П может быть задано непосредственно или определяться случайно для каждой пары строк. Далее для каждой пары строк (S¹, S²)_i, где i - номер пары, случайно выбираются n_П номеров n_i,j (n_i,j О {1, 2, …, l}; jО {1, 2, …, n_П}). Затем для строк пары (S¹, S²)_i производится обмен значениями элементов с номерами n_i,j, т.е. каждому элементу с номером n_i,j строки S¹ присваивается значение элемента с номером n_i,j строки S² , а элементу с номером n_i,j строки S² присваивается значение элемента с номером n_i,j строки S¹.

Допустим, что до операции скрещивания строка S была представителем схемы H, т.е. , а строка S¹ получена из строки S в результате поэлементного скрещивания. Вероятность p^’_s,1 того, что строка S¹ будет представителем схемы H, равна:

,

где o(H) - число фиксированных позиций схемы H.

Совокупный эффект от операций воспроизводства и поэлементного скрещивания, и мутации, т.е. число представителей схемы H в популяции G(t+1) определяется выражением:

.

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

Итак, в результате описанных выше операций получаем K*N N новых строк, которые либо полностью формируют новую популяцию G(t+1) (при K=1), заменяя при этом все строки популяции G(t), либо составляют часть популяции G(t+1), заменяя собой K*N N наименее ценных строк предыдущей популяции.

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

3. АППАРАТНАЯ РЕАЛИЗАЦИЯ ГЕННЫХ АЛГОРИТМОВ

3.1. Требования к проектированию генетических алгоритмов

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

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

3.2. Аппаратные решения на примере компактного генетического алгоритма

Работа по аппаратной реализации компактного генетического алгоритма рассматривает переход от программной реализации компактного ГА к аппаратному исполнению на примере реализации алгоритма на FPGA фирмы Xilinx. В результате, аппаратно реализованный компактный ГА выполняет одну генерацию за три тактовых цикла для задачи one-max. Количество тактов на генерацию зависит от задачи оптимизации. Более сложным задачам требуется 3+e циклов, где е количество циклов, используемое при оценке значения функции фитнесса индивидуума. При реализации размер популяции n и длина хромосомы установлены как 256 и 32 соответственно и не могут изменяться в процессе функционирования. По результатам синтеза для задачи one-max, проект использует 15210 эквивалентных вентилей, максимальная частота функционирования 23,57 MГц, было достигнуто повышение быстродействия по сравнению с программной версией в 1000 раз.

Данный алгоритм был также рассмотрен Джоном Галлагхером и доработан для применения в эволюционных аппаратных средствах, на примере использования алгоритма в схеме управления, в котором реконфигурируемая аналоговая нейронная сеть изменяется в интерактивном режиме, для управления физическими процессами. В структуру компактного ГА были добавлены некоторые генетические операторы, например стратегия элитизма, оператор мутации и схема перевыборки лучшего решения (champion resampling), а также были внесены изменения в структуру алгоритма, что позволило добиться получения качественно новых результатов при тестировании алгоритмами ДеДжонга. Основной уклон при аппаратной реализации в данной работе делался в области уменьшения потребляемой мощности и требуемого пространства кристалла для размещения алгоритма. Алгоритм был реализован с применением языка описания аппаратуры VHDL и протестирован на отладочных платах с FPGA фирмы Xilinx семейства VirtexII (xc2v 1000) и XC4000 BORG. Для разрядности хромосомы в 32 бита и размере популяции в 255 особей, при решении задачи one-max, по техническим параметрам были достигнуты результаты, сопоставимые с результатами аппаратной реализации компактного ГА. При этом, данный алгоритм превосходил компактный ГА по эффективности и области применения.

3.3. Аппаратная реализация компактного генетического алгоритма

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

.

Рис 3.3.1 Структурная схема компактного генного алгоритма

Принципиальные схемы кроссовера и мутации представлены на рисунках 3.3.2, 3.3.3.

.

Рис 3.3.2. Принципиальная схема кроссовера

.

Рис 3.3.3. Принципиальная схема мутации

ЗАКЛЮЧЕНИЕ

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

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

СПИСОК ЛИТЕРАТУРЫ

1. [Louis et al., 1991] Louis, S. J. and Rawlins, J. E., Designer genetic algorithms: genetic algorithms in structure design // ICGA-91, in Proceedings of the Fourth International Conference on Genetic Algorithms, Belew, K..K. and Booker, L.B., Eds., Booker, Morgan Kaufman, San Manteo, CA, 1991, 53.

2. [Rawlins et al., 1993] J.E. Rawlins and S.J. Louis. Syntactic Analysis of Convergence in Genetic Algorithms, Foundations of Genetic Algorithms // 2 ed. by L.D. Whitley, San Mateo, CA: Morgan Kaufmann, pp. 141, 1993.

3. [Sidhu et al., 2000] R. Sidhu, S. Wadhwa, A. Mei and V. K. Prasanna. A Self-Reconfigurable Gate Array Archtecture// Field-Programmable Logic and Applications. The Roadmap to Reconfigurable Computing. 10th International Conference, FPL 2000, Villach, Austria, August 27-30, 2000 Proceedings.

4. [Smit et al., 2002] Gerard J.M. Smit, Paul J.M. Havinga, Lodewijk T. Smit, Paul M. Heysters, Michel A.J. Rosien. Dynamic Reconfiguration in Mobile Systems //Field-Programmable Logic and Applications. 12th International Conference, FPL 2002 Lisbon, Portugal 2002 Proceedings, pp 171-181.

5. [Kajitani et al., 1998] I. Kajitani, T. Hoshino, D. Nishikawa, H. Yokoi, S. Nakaya, T. Yamauchi, T. Inuo, N. Kajihara, M. Iwata, D. Keymeulen, T. Higuchi. A gate-level EHW chip: Implementing GA operations and reconfigurable hardware on a single LSI// Evolvable Systems: From Biology to Hardware, Lecture Notes in Computer Science 1478 (Proc. of ICES1998), pp. 1-12, Springer Verlag, 1998.

6. [Chatchawit et al., 2001] A. Chatchawit and C. Prabhas, A Hardware Implementation of the Compact Genetic Algorithm, in Proceedings of the 2001 IEEE Congress on Evolutionary Computation// Seoul, Korea, May 27-30, 2001, pp.624-629.

7. [Курейчик 2004 и др.] В.М. Курейчик, В.В. Курейчик, Л.А. Гладков. Генетические алгоритмы // Ростов-на-Дону, Ростиздат 2004 г. 400 стр.

8. [Blondet et al., 2003] B. Blondet, P. James-Roxby, E. Keller, S. McMillan, P. Sundararajan. A Self-reconfiguring Platform // Field-Programmable Logic and Applications. 13th International Conference, FPL 2003 Proceedings, pp. 565-574.

9. [Higuchi et al., 1993] T. Higuchi et al. Evolvable hardware: A first step towards building a Darwin machine. In Proc. of the 2nd Int. Conference on Simulated Behaviour, pages 417-424. MIT Press, 1993.

10. [Sakanashi et al., 1999] H. Sakanashi, M. Tanaka, M. Iwata, D. Keymeulen, M. Murakawa, I. Kajitani and T. Higuchi. Evolvable Hardware Chips and their Applications// Proc. of the 1999 IEEE Systems, Man, and Cybernetics Conference (SMC'99), pp. V559-V564, 1999.

11. [Scott et al., 2001] Stephen D. Scott, Ashok Samal, Sharad Seth. HGA: A Hardware-Based Genetic Algorithm // Dept. of Computer Science Washington University St. Louis, MO 63130-4899, 7 p. 2001.

12. [Chatchawit et al., 2001] A. Chatchawit and C. Prabhas, A Hardware Implementation of the Compact Genetic Algorithm, in Proceedings of the 2001 IEEE Congress on Evolutionary Computation// Seoul, Korea, May 27-30, 2001, pp.624-629.

13. [Gallagher et al., 2004] John C. Gallagher, Saranyan Vigraham and Gregory Kramer. A Family of Compact Genetic Algorithms for Intrinsic Evolvable Hardware // IEEE Transactions on Evolutionary Computation, vol. 8, No. 2, April, 2004

14. [Zebulum et al., 2002] R.S. Zebulum, M.A. Pacheco, M.M. Vellasco. Evolutionary Electronics: Automatic Design of Electronic Circuits and Systems by Genetic Algorithms// USA, CRC Press LLC, 2002

15. [Harik et al., 1999] G. Harik, F. Lobo and D. Goldberg. The Compact genetic Algorithm // IEEE Transactions on Evolutionary Computation, vol. 3, Nov, 1999, pp. 287-309

16. [Brown et al., 1992] Stephen D. Brown, Robert J. Francis, Jonathat Rose, Zvonko G. Vranesic. Field-Programmable Gate Arrays // Kluwer Academic Publishers, USA 1992. 206 s.

17. [DeJong 1975] K.A. DeJong. An analysis of the behavior of a class of genetic adaptive systems // Ph.D. dissertation, Univ. Michigan, Ann Arbor, MI, 1775

18. [Muhlenbein 1998] H. Muhlenbein. The Equation for Response to Selection and its Use for Prediction// Evolutionary Computation, May 1998, pp.303-346.

19. [Takashi et al., 1999] Iwamoto Takashi, Yasuda Mitsuhiro, Shackleford J Barry, Okushi Etsuko. Genetic algorithm machine and its production method, and method for executing a genetic algorithm Patent number: US5970487, Application number: US19970910103 19970813, 1999.

20. [Лекции по ЭВ 2007] Лекционные материалы по курсу ЭВ

21. [g-u-t.chat.ru] http://g-u-t.chat.ru/ga/oper.htm - Генетический алгоритм: основные операции

22. [Струнков, PC Week RE 1999] http://www.neuroproject.ru/gene.htm - Что такое генетические алгоритмы Тимофей Струнков, PC Week RE, 19/99

23. [www.victoria.lviv] http://www.victoria.lviv.ua/html/oio - Тема 10. Популярно про генетические алгоритмы

Примечание

В настоящий момент времени, магистерская работа находится в стадии разработки. Завершение планируется в декабре 2008 года.