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

Оглавление

Введение

Глава 1. Основные определения и понятия

1.1 Основные определения и понятия теории графов

1.2 Основные понятия генетики

1.3 Основные определения и понятия генетических алгоритмов

1.4 Генетические операторы

1.4.1 Оператор скрещивании (кроссинговера)

1.4.2 Оператор мутации

1.4.3 Оператор репродукции (селекция)

1.5 Генетический алгоритм (ГА)

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

Глава 2. Оптимизационные задачи на графах

2.1 Генетический алгоритм разбиения графов

2.2 Задача раскраски, построения клик и независимых множеств графов

Заключение

Список литературы

Введение

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

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

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

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

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

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

Родителем современной теории генетических алгоритмов (ГА) считается Холланд (J. Holland), чья работа «Adaptation in Natural and Artificial Systems» (1975), стала классикой в этой области. В ней Холланд впервые ввел термин «генетический алгоритм». Сейчас описанный там алгоритм называют «классический ГА» (иногда «канонический ГА», canonical GA), а понятие «генетические алгоритмы» стало очень широким, и зачастую к ним относятся алгоритмы, сильно отличающиеся от классического ГА.

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

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

Модели систем эволюции по аналогии с природными системами к настоящему времени можно разбить на две большие категории:

· системы, которые смоделированы на биологических принципах. Они успешно использовались для задач типа функциональной оптимизации и могут легко быть описаны на небиологическом языке;

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

Надо отметить, что это деление условное, и во многих исследованиях эти направления комбинируются друг с другом. Рассмотренные категории представляют собой два полюса, между которыми лежат различные вычислительные системы. Ближе к первому полюсу расположены эволюционные алгоритмы, такие как эволюционное программирование (Evolutionary Programming), генетические алгоритмы (Genetic Algorithms) и эволюционные стратегии (Evolution Strategies). В настоящее время наблюдается взаимное проникновение указанных парадигм и их сращивание в единую концепцию эволюционных вычислений. Системы, которые могут быть классифицированы как «искусственная жизнь» (Artificial Life), находятся ближе ко второму полюсу

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

Глава 1. Основные определения и понятия

1.1 Основные определения и понятия теории графов

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

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

Граф или неориентированный граф -- это упорядоченная пара , для которой выполнены следующие условия:

· это множество вершин или узлов,

· это множество (неупорядоченных) пар различных вершин, называемых рёбрами.

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

Вершины и рёбра графа называются также элементами графа, число вершин в графе | | -- порядком, число рёбер | | -- размером графа.

Вершины и называются концевыми вершинами (или просто концами) ребра . Ребро, в свою очередь, соединяет эти вершины. Две концевые вершины одного и того же ребра называются соседними.

Два ребра называются смежными, если они имеют общую концевую вершину.

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

Ребро называется петлёй, если его концы совпадают, то есть .

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

Вершина называется изолированной, если она не является концом ни для одного ребра; висячей (или листом), если она является концом ровно одного ребра.

Ориентированный граф (сокращённо орграф) -- это упорядоченная пара , для которой выполнены следующие условия:

· это множество вершин или узлов,

· это множество (упорядоченных) пар различных вершин, называемых дугами или ориентированными рёбрами.

Дуга -- это упорядоченная пара вершин , где вершину называют началом, а -- концом дуги. Можно сказать, что дуга ведёт от вершины к вершине .

Смешанный граф -- это граф, в котором некоторые рёбра могут быть ориентированными, а некоторые -- неориентированными. Записывается упорядоченной тройкой , где определены так же, как выше.

Понятно, что ориентированный и неориентированный графы являются частными случаями смешанного.

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

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

Циклом называют путь, в котором первая и последняя вершины совпадают. При этом длиной пути (или цикла) называют число составляющих его рёбер. Заметим, что если вершины являются концами некоторого ребра, то согласно данному определению, последовательность является циклом. Чтобы избежать таких «вырожденных» случаев, вводят следующие понятия.

Путь (или цикл) называют простым, если ребра в нём не повторяются; элементарным, если он простой и вершины в нём не повторяются. Несложно видеть, что:

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

· Всякий простой неэлементарный путь содержит элементарный цикл.

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

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

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

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

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

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

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

Приведем примеры нескольких важных типов графов.

Вполне несвязный граф. Граф, у которого множество ребер пусто, называется вполне несвязным (или пустым) графом. Заметим, что у вполне несвязного графа все вершины изолированы.

Полный граф. Простой граф, в котором любые две вершины смежны, называется полным графом.

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

Платоновы графы. Среди регулярных графов особенно интересны так называемые платоновы графы - графы, образованные вершинами и ребрами пяти правильных многогранников - платоновых тел: тетраэдра, куба, октаэдра, додекаэдра и икосаэдра.

1.2 Основные понятия генетики

Основоположником генетики является Иоганн Грегор Мендель, который в середине XIX в. открыл общий закон природы и вывел формулы расщепления признаков в гибридном потомстве.

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

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

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

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

Приведем факторы, которые меняют генетический состав природной популяции:

1. Мутационный процесс. Согласно закону Харди-Вайнберга равновесие устанавливается после первого скрещивания. В каждом поколении возникают новые мутации, происходит скрещивание, вызывающее новое равновесие и т.д.

2. Изоляции. Чем меньше размер популяции, тем более вероятно, что в ней появятся скрытые изменения.

3. «Волны жизни». Изоляция ведет к уменьшению величины популяции. Объем популяции может меняться в зависимости от окружающей среды.

4. Отбор. Факторы 1,2,3 - ненаправленные, они изменяют состав популяции случайным образом. Фактор 4 в отличие от них действует в определенном направлении, которое наилучшим образом соответствует условиям жизни.

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

1. Все признаки организмов находятся под контролем генов.

2. Гены - элементарные единицы наследственной информации - находятся в хромосомах.

3. Гены могут изменяться, т.е. мутировать.

4. Мутации отдельных генов приводят к изменению отдельных элементарных признаков.

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

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

Хромосомы, представляющие собой отображения решений, должны быть гомологичны, так как являются взаимозаменяемыми альтернативами.

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

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

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

Существует много систем классификации мутаций их можно разделить:

1. По способу возникновения: спонтанные мутации, индуцированные мутации. Возникают редко. Процесс зависит от внутренних и внешних факторов.

2. По адаптивному значению выделяют мутации положительные, отрицательные, нейтральные.

3. По изменению генотипа: генные, хромосомные, геномные.

4. По локализации в клетке: ядерные, цитоплазматические.

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

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

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

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

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

1. Естественный отбор, вызывающий изменения, связанные с приспособлением к новым условиям.

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

3. Методический отбор, при котором проводится целенаправленное изменение популяций в сторону установленного идеала.

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

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

1.3 Основные определения и понятия генетических алгоритмов

Генетические алгоритмы (ГА)- это новая область исследований, которая появилась в результате работ Д.Холланда и его коллег. ГА представляет собой адаптивный поисковой метод, основанный на селекции лучших элементов в популяции, подобно эволюционной теории Ч.Дарвина.

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

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

Цель генетических алгоритмов состоит в том, чтобы:

· Абстрактно и формально объяснять адаптацию процессов в естественной системе и интеллектуальной исследовательской системе;

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

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

· Работаю в основном не с параметрами задачи, а с закодированным множеством параметров;

· Осуществляет поиск не путем улучшения одного решения, а путем использования сразу нескольких альтернатив на заданном множестве решений;

· Используют целевую функцию, а не различные приращения для оценки качества принятия решений;

· Применяют не детерминированные, а вероятностные правила анализа оптимизационных задач.

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

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

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

Популяция есть множество элементов , t = 0,1,2,… - номер генерации алгоритма, - размер популяции. Каждый элемент такой популяции представляет собой одну или несколько хромосом или особей, или индивидуальностей (альтернативных упорядоченных или неупорядоченных решений). Хромосомы состоят из генов (элементы, части закодированного решения), и позиции генов в хромосоме называется лоции или локус для одной позиции, т.е. ген - подэлемент (элемент в хромосоме), локус - позиция в хромосоме, аллель - функциональное значение гена.

Элементы в генетических алгоритмах часто называют родителями. Родители выбираются из популяции на основе заданных правил, а затем смешиваются (скрещиваются) для производства «детей» (потомков). Дети и родители в результате генерации создают новую популяцию. Генерация называется поколением.

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

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

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

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

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

· «одеяло» - генерируется полная популяция, включающая все возможные решения в некоторой заданной области.

· «дробовик» - подразумевает случайный выбор альтернатив из всей области решений данной задачи.

· «фокусировка» - реализует случайный выбор допустимых альтернатив из заданной области решений данной задачи.

· «комбинирование» - состоит в различных совместных реализациях первых трех принципов.

Популяция обязательно является конечным множеством.

1.4 Генетические операторы

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

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

Генетический оператор по аналогии с оператором алгоритма - средство отображения одного множества на другое.

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

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

1.4.1 Оператор скрещивании (кроссинговера)

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

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

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

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

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

Вероятность кроссинговера самая высокая среди генетических операторов и равна обычно 60% и больше.

1.4.2 Оператор мутации

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

Оператор мутации необходим для "выбивания" популяции из локального экстремума и способствует защите от преждевременной сходимости.

Оператор мутации (четвертый ген мутировал)

Так же как и кроссинговер, мутация проводится не только по одной случайной точке.

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

Вероятность мутации значительно меньше вероятности кроссинговера и редко превышает 1%.

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

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

1.4.3 Оператор репродукции (селекция)

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

Существует несколько методов операторов селекции:

· Метод рулетки

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

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

· Турнирный отбор

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

1.5 Генетический алгоритм (ГА)

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

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

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

Генетические алгоритмы в разных формах применяются к решению многих научных и технических проблем.

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

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

Тем не менее, возможно популярное применение генетических алгоритмов - оптимизация многопараметрических функций.

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

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

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

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

Глава 2. Оптимизационные задачи на графах

2.1 Генетический алгоритм разбиения графов

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

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

,

(1.1)

, , , . (1.2)

Целевая функция для разбиения графа G запишется так:

, ,

где - число связей между частями и при разбиении графа на части; - количество частей в разбиении; - суммарное количество ребер при разбиении графа на части.

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

Здесь в первом блоке строится текущая (начальная) популяция решений, т.е. определяется заданное подмножество .

На построение популяции оказывает влияние внешняя среда в виде ЛРП или ЭС. Отметим, что такое подмножество решений может быть получено случайным, направленным или случайно-направленным методами.

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

Критерии и А являются взаимообратными, т.е. минимизация максимизирует А и наоборот.

Для каждого элемента текущей популяции вычислим и определим Кср - среднее значение целевой функции для данной популяции.

Для каждого элемента текущей популяции в блоке 2 вычисляется и определяется Кср.

Блок 3 осуществляет сортировку популяции на основе целевой функции.

Здесь могут быть применены все существующие методы сортировки. Сначала расставляются элементы с наименьшим значение и так далее по возрастанию.

Блок 4 выполняет селекцию популяции для получения родительских пар.

Селекция выполняется одним из методов, описанных выше.

Блок 5 осуществляет реализацию генетических операторов и их модификаций.

Блок 6 собирает и анализирует неперспективные решения задачи разбиения.

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

Блок 8 осуществляет построение новой популяции решений.

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

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

При этом в стандартном случае количество элементов в новой популяции не должно превышать число элементов в старой популяции.

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

2.2 Задача раскраски, построения клик и независимых множеств графов

Рассмотрим задачу раскраски графа.

Раскраской вершин графа называется разбиение множества вершин непересекающихся классов (подмножеств):

; ; ; i,j =1,2,.., L,

Таких, что внутри каждого подмножества не должно содержаться смежных вершин.

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

Основной стратегией для задачи раскраски графа являются последовательные и «жадные» эвристики, которые позволяют получать результаты с локальным оптимумом.

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

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

Основные «жадные» эвристики для раскраски:

Эвристика 1: «Первые наибольшие». Вершины графа упорядочиваются по убыванию локальных степеней. Затем по порядку каждая вершина после анализа связности раскрашивается в возможный цвет.

Эвристика 2: «Наименьшие последние». Построение порядка из хаоса производится следующим образом. Выбирается вершина графа с наименьшей локальной степенью и удаляется из графа вместе с инцидентными ребрами.

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

Эвристика 3: «Разбиение по смежности». В начале алгоритма выбирается вершина графа максимальной степени и раскрашивается в цвет 1.

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

Далее процесс продолжается аналогично до заполнения цвета 1. После этого вершины, раскрашенные цветом 1, удаляются. И процедура продолжается до полной раскраски графа.

Эвристика 4: «Раскраска ранее упорядоченных вершин». Для вершины выбирается цвет k, и если среди вершин, смежных с , уже существуют раскрашенные цветов с=1,2,…,k-1,k+1,k+2,… и нет вершин, помеченных цветом k.

Эвристика 5: «Специальная раскраска в предписанные цвета». Предварительно для каждой вершины задан набор цветов, в которые она может быть раскрашена.

Упорядочение вершин производится следующим образом. Определяются вершины с минимальным числом , где - локальная степень вершины графа G=(X,U), - число запрещенных цветов для заданной вершины, С - общее число цветов. Вершина с минимальным значением W удаляется из графа вместе с ребрами. Для оставшегося графа повторяется такая же процедура, и так далее. Затем вершины красятся в возможный цвет в порядке, обратном порядку удаления.

Простой алгоритм на основе одной из рассмотренных «жадных» эвристик:

1. Упорядочить вершины по убыванию локальных степеней.

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

3. Шаг 2 продолжать до полной раскраски графа.

4. Конец работы алгоритма.

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

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

Запишем алгоритм реализации модифицированного универсального оператора кроссинговера. Даны родители 1 и 2, первый потомок получается следующим образом:

1. Сгенерировать бинарную строку-шаблон, количество элементов в которой совпадает с длинной хромосомы родителей.

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

3. Создать список из генов первого родителя, соответствующих нулю в бинарной строке.

4. Последовательно просматривая элементы второго родителя, произвести заполнение пустых позиций.

5. Объединяя частичные альтернативные решения без повторений, получить первого потомка.

6. Конец работы алгоритма.

Построение второго потомка производится аналогичным образом.



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

Задача раскраски графа тесно связана с построением независимых или внутренне устойчивых подмножеств, а так же определением клик графа. Если две любые вершины подмножеств X' графа G=(X,U), , не смежны, то оно называется внутренне устойчивым. Подмножество графа G=(X,U) называется максимальным внутреннее устойчивым подмножеством или независимым, если добавление к нему любой вершины делает его не внутренне устойчивым. Подмножество , будет независимым, если .

Независимые подмножества различаются по числу входящих в ни элементов. В произвольном графе G можно выделить семейство всех независимых подмножеств вида или его части. «Жадные» стратегии, используемые для задачи раскраски графа, также эффективно применяются для построения семейства независимых подмножеств.

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

1. Ввести параметр алгоритма.

2. Сгенерировать начальную популяцию.

3. Выбрать хромосомы-родителей на основе случайной селекции.

4. Реализовать оператор кроссинговера с заданной вероятностью.

5. Реализовать оператор мутации для каждой хромосомы с заданной вероятностью.

6. Реализовать оператор отбора лучших хромосом.

7. конец работы алгоритма.

Заключение

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

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

Список литературы

1. Гладков Л.А., Курейчик В.В., Курейчик В.М. Генетические алгоритмы / Под ред. В.М. Куруйчика. - 2-е изд., испр. и доп. - М.: ФИЗМАТЛИТ. 2006.

2. О. Оре. Графы и их применение/ Перевод с английского Л.И. Головиной. Под редакцией И.М. Яглома. Издательство «Мир». Москва, 1965.

3. Р. Уилсон. Введение в теорию графов/ Перевод с английского И.Г. Никитиной. Под редакцией Г.П. Гаврилова. Издательство «Мир». Москва, 1977.

4. Батищев Д.И., Неймарк Е.А., Старостин Н.В. Применение генетических алгоритмов к решению задач дискретной оптимизации. Учебно-методический материал по программе повышения квалификации «Информационные технологии и компьютерное моделирование в прикладной математике». Нижний Новгород, 2007, 85 с.

5. Курейчик В. М., Лебедев Б. К., Лебедев О. К. Поисковая адаптация: теория и практика. -- М: Физматлит, 2006.

6. Методические указания «Улучшающий генетический алгоритм» по курсу «Генетические алгоритмы: теория и приложения решения оптимизационных задач» для студентов факультета ВМК специальности «Прикладная информатика»/Нижегородский государственный университет, 2008

Размещено на Allbest.ru

...