Сравнение эйлеровых и гамильтоновых циклов

Несмотря на внешнюю схожесть определений эйлерова и гамильтонова циклов, задачи нахождения циклов этих двух типов в данном графе разительно отличаются по сложности. Задача о нахождении эйлерова цикла − это простая с математической точки зрения задача: существует эффективный критерий существования эйлерова цикла (теорема Эйлера); если критерий выполнен, имеется эффективный алгоритм для нахождения цикла (например, алгоритм Флери). «Эффективный» в данном случае означает «требующий проведения небольшого числа операций относительно размера графа». Ни критерия гамильтоновости графа, ни эффективного алгоритма нахождения гамильтонова цикла в произвольном гамильтоновом графе, неизвестно (и скорее всего, не существует). Задача о нахождении гамильтонова цикла − это NP-трудная задача.

Следующие четыре графа демонстрируют отсутствие тесной взаимосвязи между существованием эйлеровых и гамильтоновых циклов (рис. 10.2).

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

Реберный граф G_l графа G имеет столько же вершин, сколько ребер у графа G. Ребро между двумя вершинами графа G_l существует тогда и только тогда, когда ребра графа G, соответствующие этим двум вершинам, смежны (т.е. инцидентны одной и той же вершине графа G).

 

 

x1

x3

x4

x2

x5

х1

х2

х6

х4

х3

х5

х1

х2

х3

х4

x1

x3

x4

x2

x5

б

в

г

а

 

 

Рисунок 10.2. Графы: эйлеров и гамильтонов (а); неэйлеров и гамильтонов (б); эйлеров и негамильтонов (в); неэйлеров и негамильтонов (г)

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

1. Если граф G имеет эйлеров цикл, то граф G_l имеет как эйлеров, так и гамильтонов циклы.

2. Если граф G имеет гамильтонов цикл, то граф G_l также имеет гамильтонов цикл.

Обращение этих утверждений неверно!

Эволюционные алгоритмы оптимизации

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

Природа поражает своей сложностью и богатством проявлений. Среди примеров можно назвать сложные социальные системы, иммунные и нейронные системы, сложные взаимосвязи между видами. Они всего лишь некоторые из чудес, ставшие очевидными при глубоком исследовании природы вокруг нас. Наука − это одна из систем, которая объясняет окружающее и помогает приспособиться к новой информации, получаемой из внешней среды. Многое из того, что мы видим и наблюдаем, можно объяснить теорией эволюции через наследственность, мутацию и отбор.

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

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

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

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

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

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

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

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

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

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

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

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

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

Одноточечный кроссинговер работает следующим образом.

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

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

Кроссинговер

Родитель 1	000~0000000
Родитель 2	111~1111111
Потомок 1	111~0000000
Потомок 2	000~1111111

 

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

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

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

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

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

Генерация начальной популяции особей

Выбор индивидуумов

Скрещивание

Мутация

 

Рисунок 11.1. Схема генетического алгоритма

 

 

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

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

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

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

⇐ Предыдущая10111213141516171819Следующая ⇒

Поделиться:

Популярное:

1. Использование циклов в реальном мире
2. Коэффициент использования станка есть отношение фактической производительности к цикловой.
3. Область видимости переменных-счетчиков циклов for
4. Опыт 1. Сравнение химической активности кислот
5. Отличие циклов с предусловием от циклов с постусловием заключается в том, операторы цикла с постусловием всегда выполняются хотя бы один раз.
6. Рассмотрено цикловой методической комиссией
7. Расчёт основных цикловых показателей
8. СРАВНЕНИЕ ВЫСОКОГО И НИЗКОГО НАКЛОНА
9. Сравнение гибридов и помесей независимо от их фертильности.
10. Сравнение двигателей различных систем возбуждения
11. Сравнение качества товаров с товарами двух конкурентов, используя трех позиционную шкалу: «хуже», «такое же», «лучше»
12. Сравнение количества предоставляемые услуг в сфере экстремального спорта среди команд Красноярска и Красноярского края