НГУ
http://forum.nsu.ru/

Генетический алгоритм. Нахождения мин. пути в графе
http://forum.nsu.ru/viewtopic.php?f=18&t=22595
Страница 1 из 2

Автор:  shn [ Пн авг 15, 2011 10:55 am ]
Заголовок сообщения:  Генетический алгоритм. Нахождения мин. пути в графе

Задача: Дан взвешенный граф G(X,V).
Нужно построить генетический алгоритм, который решает задачу нахождения минимального пути в графе.

Собственно вопрос состоит в том, как представлять хромосомы.

Есть вариант представления как битовый вектор длинны |V|. при этом v[i] = 1, если ребро i. Но это не очень хороший вариант (вектора имеют очень большую длину для больших графов)

Автор:  McUrgd [ Пн авг 15, 2011 3:09 pm ]
Заголовок сообщения: 

Всего лишь порядка квадрата числа вершин :)

Автор:  Ferlon Wilder [ Пн авг 15, 2011 3:27 pm ]
Заголовок сообщения: 

Можно ещё так: v[i] - это номер ребра, по которому мы пойдём дальше из той вершины, в которую пришли по предыдущим рёбрам (с номерами до i-1). Тогда длина генетического кода будет порядка числа вершин. Но это, конечно, только если в графе нет циклов отрицательного веса, достижимых из начальной вершины.

Автор:  Pavel E. Alaev [ Чт авг 18, 2011 9:49 pm ]
Заголовок сообщения:  Re: Генетический алгоритм. Нахождения мин. пути в графе

shn писал(а):
Есть вариант представления как битовый вектор длинны |V|. при этом v[i] = 1, если ребро i. Но это не очень хороший вариант (вектора имеют очень большую длину для больших графов)

"Хромосомами" здесь, насколько я понял, должны быть пути в графе. Вы имеете в виду, что v[i] = 1, если ребро i является частью пути?

Автор:  McUrgd [ Пт авг 19, 2011 11:21 am ]
Заголовок сообщения: 

Ferlon Wilder писал(а):
Можно ещё так: v[i] - это номер ребра, по которому мы пойдём дальше из той вершины, в которую пришли по предыдущим рёбрам (с номерами до i-1). Тогда длина генетического кода будет порядка числа вершин. Но это, конечно, только если в графе нет циклов отрицательного веса, достижимых из начальной вершины.
А как хромосомы скрещивать в таком случае?

Автор:  Pavel E. Alaev [ Пт авг 19, 2011 9:30 pm ]
Заголовок сообщения: 

McUrgd писал(а):
А как хромосомы скрещивать в таком случае?

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

То есть если Путь1 состоит из участков АБ, причём после А он приходит в точку Т, а Путь2 состоит из участков А'Б', причём после А' он тоже приходит в точку Т, то то они могут породить потомков АБ' и А'Б.

Автор:  Pavel E. Alaev [ Вс авг 21, 2011 12:14 am ]
Заголовок сообщения: 

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

Ссылка в тему:
http://www.masters.donntu.edu.ua/2010/f ... slate1.htm
"ГЕНЕТИЧЕСКИЙ АЛГОРИТМ ДЛЯ ОПРЕДЕЛЕНИЯ МИНИМАЛЬНОГО ВРЕМЕНИ ПУТИ В ИНТЕЛЛЕКТУАЛЬНЫХ ТРАНСПОРТНЫХ СИСТЕМАХ"

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

Автор:  [shn]max [ Пт авг 26, 2011 12:27 pm ]
Заголовок сообщения: 

Всем спасибо.
Нашел хорошее решение задачи используя код прюфера.

http://neerc.ifmo.ru/mediawiki/index.php/Коды_Прюфера

Автор:  Pavel E. Alaev [ Сб авг 27, 2011 3:28 pm ]
Заголовок сообщения: 

[shn]max писал(а):
Нашел хорошее решение задачи используя код прюфера.

Почитал статью по ссылке; честно говоря, не смог понять, как она может быть полезна для работы с путями в графе. Там идёт речь про кодирование некоторых объектов, называемых "помеченными деревьями".

А Вы генетический алгоритм как-то реализовали уже?

Автор:  [shn]max [ Сб авг 27, 2011 5:21 pm ]
Заголовок сообщения: 

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

вот еще одна ссылка там более подробно написано:
http://citeseerx.ist.psu.edu/viewdoc/do ... 1&type=pdf

Алгоритм пока не реализовали до конца.

Автор:  Pavel E. Alaev [ Ср авг 31, 2011 9:23 pm ]
Заголовок сообщения: 

[shn]max писал(а):
Код прюфера осуществляет взаимооднозначное соответствие между остовами и векторами размера n-2, где n - число вершин. А в остове существует единственный путь из одной вершины в другую.

То есть, чтобы найти путь из вершины А в вершину Б, мы сначала ищем остов всего графа, а потом по остову определяем путь?

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

Автор:  [shn]max [ Чт сен 01, 2011 5:30 pm ]
Заголовок сообщения: 

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

Автор:  fenster [ Пт сен 02, 2011 12:56 am ]
Заголовок сообщения: 

(пришёл со стороны, ссылки не читал, в генетических алгоритмах не шарю)

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

Автор:  [shn]max [ Пт сен 02, 2011 1:53 am ]
Заголовок сообщения: 

fenster писал(а):
(пришёл со стороны, ссылки не читал, в генетических алгоритмах не шарю)

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


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

Автор:  Коба [ Пт сен 02, 2011 8:42 am ]
Заголовок сообщения: 

[shn]max писал(а):
...некорректных хромосом при мутации и кроссоверенге получиться не может.

Я слышал термин "кроссинговер". "Кроссоверенг" в генетике тоже бывает, или это из области спортивной обуви?

Страница 1 из 2 Часовой пояс: UTC + 7 часов
Powered by phpBB® Forum Software © phpBB Group
https://www.phpbb.com/