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

Question

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

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

Ввод: График G = (V, E)
Вывод: Набор назначений, {(xi, yi) for each vi in V}. Другими словами, каждой вершине будет назначена позиция (x, y), где все координаты целые и> = 0.

Вот критерии, которые я буду использовать для оценки решения (я приветствую любые предложения):

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

Кроме; У меня есть первоначальная конфигурация (назначение позиций вершинам), выполненная вручную. Это очень грязно, и именно поэтому я пытаюсь автоматизировать процесс.

Мои вопросы,

• Насколько разумно было бы использовать местные методы поиска? Насколько вероятно приведет ли это к желаемому результату?

• А с чего мне начать? Имитация отжига, генетические алгоритмы или что-то еще?

• Должен ли я посеять случайным образом в начале или использовать начальный конфигурация для начала?

• Или, если вы уже знаете о подобной реализации / псевдокоде / штуке, укажите мне на это.

Любая помощь будет принята с благодарностью. Спасибо.

РЕДАКТИРОВАТЬ: Это не должно быть быстро - не в режиме реального времени. Более того; | V | = ~ 200, и каждая вершина имеет в среднем около 1,5 исходящих ребер. На графике нет отключенных компонентов. Это включает в себя циклы.

Answer 1

Я бы посоветовал взглянуть на http://www.graphviz.org/Theory.php, поскольку graphviz является одним из ведущих графических визуализаторов с открытым исходным кодом.

В зависимости от назначения, возможно, имеет смысл использовать graphviz для визуализации вообще.

Answer 2

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

Answer 3

function String generateGenetic()
String genetic = "";
for each vertex in your graph
    Generate random x and y;
    String xy = Transform x and y to a fixed-length bit string;
    genetic + = xy;
endfor
return genetic;

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

ваша программа:

int population = 1000;
int max_iterations = 1000;
double satisfaction = 0;
String[] genetics = new String[population]; //this is ur population;
while((satisfaction<0.8)&&(count<max_iterations)){
    for (int i=0;i<population;i++){
        if(evaluate(genetics[i])>satisfaction)
            satisfaction = evaluate(genetics[i]);
        else
            manipulate(genetics[i]);
    }
}

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

Answer 4

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

• Как быстро это должно быть (нужно ли это делать в режиме реального времени?)
• Сколько существует вершин
• Сколько существует ребер по сравнению с количеством вершин (т. Е. Плотный или разреженный граф?)

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

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

Теперь перейдем к вашим вопросам о реализации локального поиска.

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

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

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

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

РЕДАКТИРОВАТЬ: В свете параметров вашего графика, я думаю, вы можете просто использовать любой алгоритм, который проще всего кодировать.С V = 200, даже алгоритм O (V ^ 3) будет достаточно.Лично я чувствую, что имитация отжига будет самым простым и лучшим маршрутом.

Answer 5

http://oreilly.com/catalog/9780596529321 - В этой книге вы можете найти реализацию генетического алгоритма для тонкой визуализации 2D-графика.

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

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

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