Основные определения и понятия теории графов. Оптимизация решения задач с применением эволюционно-генетического подхода. Повышение технологичности и простоты конструктивного оформления элементов принципиальных схем на основе генетических алгоритмов.
Аннотация к работе
В данной работе рассмотрены вопросы эволюционно-генетического подхода к решению задач оптимизации, на основе которого строятся генетические алгоритмы. К теории графов проявляется всевозрастающий интерес, поскольку она признана эффективным аппаратом формализации научных и технических задач в различных отраслях знаний и деятельности человека, например, в вычислительной технике, автоматизации проектирования, микроэлектронике, радиоэлектронике, приборостроении, автоматике, кибернетике, медицине, биологии, генетике. Однако такие задачи не исчезают, и по-прежнему остается проблема их решения. Одной из задач, которая требует решения при их конструировании, является задача разбиения принципиальных схем устройств на составные части (подсхемы, функциональные блоки). Сейчас описанный там алгоритм называют «классический ГА» (иногда «канонический ГА», canonical GA), а понятие «генетические алгоритмы» стало очень широким, и зачастую к ним относятся алгоритмы, сильно отличающиеся от классического ГА.Граф или неориентированный граф - это упорядоченная пара , для которой выполнены следующие условия: · это множество вершин или узлов, · это множество (неупорядоченных) пар различных вершин, называемых ребрами. Вершины и ребра графа называются также элементами графа, число вершин в графе | | - порядком, число ребер | | - размером графа. Вершины и называются концевыми вершинами (или просто концами) ребра . Вершина называется изолированной, если она не является концом ни для одного ребра; висячей (или листом), если она является концом ровно одного ребра. Путем (или цепью) в графе называют конечную последовательность вершин, в которой каждая вершина (кроме последней) соединена со следующей в последовательности вершин ребром.Основоположником генетики является Иоганн Грегор Мендель, который в середине XIX в. открыл общий закон природы и вывел формулы расщепления признаков в гибридном потомстве. Мендель пришел к выводу, что наследственность прерывиста (дискретна), что наследуется не большая совокупность свойств, а отдельные признаки. Одна из основных заслуг И.Менделя - его гипотеза о материальных задатках, которые в двойном комплекте находятся в клетках и которые зародыш получает от обоих родителей. Через отбор происходит направленное влияние окружающей среды на наследственную изменчивость. Хуго де Фриз наследственные изменения отдельных генов назвал мутациями.Генетические алгоритмы (ГА)-это новая область исследований, которая появилась в результате работ Д.Холланда и его коллег. Само преобразование можно назвать алгоритмом поиска, или генетическим алгоритмом. Генетические алгоритмы отличаются от других оптимизационных и поисковых процедур следующим: · Работаю в основном не с параметрами задачи, а с закодированным множеством параметров; В отличие от других методов оптимизации эти алгоритмы, как правило, анализируют различные области пространства решений одновременно и поэтому они более приспособлены к нахождению новых областей с лучшими значениями целевой функции. Хромосомы состоят из генов (элементы, части закодированного решения), и позиции генов в хромосоме называется лоции или локус для одной позиции, т.е. ген - подэлемент (элемент в хромосоме), локус - позиция в хромосоме, аллель - функциональное значение гена.Оператор - это языковая конструкция, представляющая один шаг из последовательности действий или наборе описаний алгоритма. Генетические операторы необходимы, чтобы применить принципы наследственности и изменчивости к виртуальной популяции. В данном случае, неопределенность не подразумевает негативный фактор, а является своебразной "степенью свободы" работы генетического алгоритма. Оператор кроссинговера, также называемый кроссовером, является основным генетическим оператором, за счет которого производится обмен генетическим материалом между особями. Случайным образом определяется точка внутри хромосомы, в которой обе хромосомы делятся на две части и обмениваются ими.Оператор мутации - языковая конструкция, позволяющая на основе преобразования родительской хромосомы (или ее части) создавать хромосому потомка. Оператор мутации необходим для "выбивания" популяции из локального экстремума и способствует защите от преждевременной сходимости. Так же как и кроссинговер, мутация проводится не только по одной случайной точке. Необходимо также отметить, что есть мнение, что оператор мутации является основным поисковым оператором и известны алгоритмы, не использующих других операторов (кроссинговер, инверсия и т.д.) кроме мутации. Это процесс, посредством которого хромосомы (альтернативные решения), имеющие более высокое значение целевой функции (с «лучшими» признаками), получают большую возможность для воспроизводства (репродукции) потомков, чем «худшие» хромосомы.Генетические алгоритмы в разных формах применяются к решению многих научных и технических проблем. Генетические алгоритмы используются при создании других вычислительных структур, например, автоматов или сетей сортировки.
План
Оглавление
Введение
Глава 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 Задача раскраски, построения клик и независимых множеств графов