Уктуре генетических алгоритмов, рассмотрю один из примеров использования алгоритмов, а также поподробнее остановлюсь на методах отбора в генетических алгоритмах

Вид материала

Доклад

Содержание Что такое генетический алгоритм Вычисление приспособленности. Критерии останова и выживаемости N - максимальное число процессоров (полагается равным числу процессов N в алгоритме), M Схема рулетки Элитный отбор Отбор с вытеснением

Подобный материал:

• Рабочая программа учебной дисциплины (модуля) Программная реализация экспертных систем, 94.38kb.
• Д. С. Осипенко Понятие алгоритма. Примеры алгоритмов. Свойства алгоритмов. Способы, 96.46kb.
• В. Е. Латов Тульский государственный университет mibo@klax tula ru Эволюционное моделирование, 65.56kb.
• Тарасюк А. П., Спасский, 109.74kb.
• Секция “Краевые задачи в физике и химии твердого тела”, 31.36kb.
• «Понятие об алгоритме. Примеры алгоритмов. Свойства алгоритмов. Типы алгоритмов, построение, 84.9kb.
• Методические рекомендации к занятиям темы 7 «Алгоритмы обработки информации», 163.76kb.
• Программные средства реализации адаптивных моделей с нечеткой логикой, 64.25kb.
• Задачи урока: Учебная углубление, обобщение и систематизация знаний по составлению, 53.73kb.
• Определения и понятия генетических алгоритмов, 471.62kb.

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

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

^

Что такое генетический алгоритм

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


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


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


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


Имеются много способов реализации идеи биологической эволюции в рамках ГА. Традиционным считается ГА, представленный на схеме. Традиционная схема называется SGA.

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

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

^ Вычисление приспособленности. Для каждого генома должно быть определено значение, соответствующее “качеству” соответствующего решения. Такое значение называют приспособленностью данного генома (особи). От приспособленности зависит вероятность того, попадет ли данная особь в пару для скрещивания, а также, возможно, вероятность ее элиминирования на каком-то этапе процесса.

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

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

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

Для этой задачи требуется определить

• M - число процессоров в ВС,
  
• SP = {SP_i}_i=(1...M) - привязку процессов, составляющих программу, к процессорам ВС (SP_i - упорядоченный список процессов, выполняемых на i-ом процессоре);
  
• IO_MM - интенсивность межпроцессорного взаимодействия в форме матрицы интенсивности обменов между процессорами или временной диаграммы обменов;
  

при этом должны выполняться условия:

1. время выполнения алгоритма не должно превышать директивный срок T^waT^dir;
   
2. число процессоров M в ВС должно быть минимально необходимым для выполнения условия 1.
   

Кодирование

Для однозначного распределения процессов по процессорам, необходимо для каждого процесса p_i иметь номер процессора, на котором он выполняется (M_i) и его порядковый номер на этом процессоре (N_mi). Кодировка ВС в виде битовой строки и была сделана исходя из этих соображений.

^ Критерии останова и выживаемости

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

1. время выполнения алгоритма не должно превышать директивный срок T^waT^dir,
   
2. число процессоров M в ВС должно быть минимально необходимым для выполнения условия 1.
   

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


k = C₁ k_t + C₂ k_opt , C₁ + C₂ = 1

Коэффициенты k_t и k_opt нормируются в интервале 0<k_t,k_opt1 и вычисляются следующим образом:


,


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


,


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

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

, (1)

где    - округление до целого в большую сторону. Если алгоритм находит значение M для которого выполняется строгое равенство, то оно будет гарантированно оптимальным. Следует отметить, что варианта решения задачи для которого выполнятся строгое равенство в (1) может вообще не существовать.

Если алгоритм находит число процессоров, которое удовлетворяет строгому равенству в (1), то происходит его останов. В противном , алгоритм выполняется циклически, то есть задается начальный критерий выживаемости, а затем постепенно ужесточается. Когда алгоритм не сможет за заданное число итераций улутшить критерий выживаемости, то происходит его останов. В качестве “ужесточенного” критерия выживаемости берется наибольший в популяции и превышающий текущий критерий, если таков получен на очередной итерации.


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

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

^

Схема рулетки

На каждом поколении ГА реализуется отбор пропорционально приспособленности и мутация. Сначала, пропорциональный отбор назначает каждой структуре вероятность Ps(i) равную отношению ее приспособленности к суммарной приспособленности популяции.

Затем происходит отбор (с замещением) всех n особей для дальнейшей генетической обработки, согласно величине Ps(i). Простейший пропорциональный отбор - рулетка (roulette-wheel selection, Goldberg, 1989c) - отбирает особей с помощью n "запусков" рулетки. Колесо рулетки содержит по одному сектору для каждого члена популяции. Размер i-ого сектора пропорционален соответствующей величине Ps(i). При таком отборе члены популяции с более высокой приспособленностью с большей вероятность будут чаще выбираться, чем особи с низкой приспособленностью.

^

Элитный отбор

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

^

Отбор с вытеснением

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