Эволюционный алгоритм для проверки планарности графов

Аннотация

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

Вычислительная сложность алгоритма определяется как $I \cdot O(S \cdot 𝑙𝑜𝑔(𝑆) \cdot M^2)$ , где – количество итераций алгоритма, – размер популяции (задаётся пользователем), – количество рёбер графа.[1]

Введение

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

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

Будем рассматривать неориентированные графы без петель и кратных рёбер.

Определение. Неориентированным графом называется пара , где – множество вершин, а – множество рёбер.

Определение. Плоским графом называется граф, изображенный на плоскости так, что никакие два его ребра геометрически не пересекаются. Граф, изоморфный плоскому графу, называется планарным.[2]

Эволюционный алгоритм

Эволюционный алгоритм строит изображение графа с минимальным числом пересечений рёбер.

К недостаткам алгоритма можно отнести его асимптотическую сложность. Однако, на практике алгоритм находит оптимальное решение достаточно быстро.

К преимуществам данного алгоритма относятся простота реализации и возможность построения изображения планарного графа.

Описание эволюционного алгоритма

Кодирование решения

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

Инициализация

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

Fitness-функция

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

Стратегия отбора

Выполним сортировку особей текущей и предыдущей популяций. Выберем 50% лучших особей из каждой.

Оператор скрещивания

Случайным образом выбираем два рисунка G1, G2 из популяции. Для каждой пары соответствующих вершин G1[i], G2[i] выполняем процесс скрещивания координат. Формула скрещивания координат:

$x=x_1 \cdot \lambda + x_2 \cdot (1- \lambda),$

$y=y_1 \cdot \lambda + y_2 \cdot (1- \lambda),$

где $\lambda = \frac{1}{e}.$

В процессе скрещивания координат случайным образом выбирается одно из 3-х направлений скрещивания:

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

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

Заключение

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

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

1. Проверка планарности графа. – Текст : электронный // Справочник от Автор 24 : [сайт]. – URL:https://spravochnick.ru/informatika/proverka_planarnosti_grafa/ (дата обращения: 20.06.2023).https://ru.wikipedia.org/wiki/Планарный_граф

2. Нина, Костюкова Проверка планарности графа / Костюкова Нина. – Текст : электронный // Курс: «Графы иих применение». Лекция 3: Представления о планарном графе : [сайт]. – URL:https://intuit.ru/studies/courses/58/58/info (дата обращения: 20.06.2023).

ссылка на оригинал статьи https://habr.com/ru/articles/843342/