7.6. Задачи распознавания изоморфизма графа

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

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

На рисунке 121 приведен график зависимости количества вершин графов от времени решения. На основе полученных данных можно определить, что экспериментальная временная сложность алгоритма ориентировочно составляет О(п^), хотя в худшем случае может составлять 0(fc!). Применение новых и модифицированных операторов позволяет ускорить процедуру поиска подстановки изоморфизма внутри подмножеств предполагаемо изоморфных вершин.

На рисунке 7.28 построен график зависимости времени получения лучшего решения для оптимизационных задач на графах от количества вершин.

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

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

По результатам тестовых испытаний сделаем краткие выводы;

1.   Реализация ГА с самоорганизацией при разбиении графов на части показала преимуш,ество по сравнению с ПГА и другими классическими методами.

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

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

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

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

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

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