НГУ

Форумы НГУ
Текущее время: Пт ноя 15, 2019 7:42 pm

Часовой пояс: UTC + 7 часов




Начать новую тему Ответить на тему  [ Сообщений: 19 ]  На страницу 1, 2  След.
Автор Сообщение
СообщениеДобавлено: Пн авг 15, 2011 10:55 am 
Не в сети
Редкий гость

Зарегистрирован: Пн авг 15, 2011 10:32 am
Сообщения: 1
Задача: Дан взвешенный граф G(X,V).
Нужно построить генетический алгоритм, который решает задачу нахождения минимального пути в графе.

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

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


Вернуться к началу
 Профиль  
 
 Заголовок сообщения:
СообщениеДобавлено: Пн авг 15, 2011 3:09 pm 
Не в сети
Начинающий автор

Зарегистрирован: Сб сен 16, 2006 11:23 am
Сообщения: 290
Всего лишь порядка квадрата числа вершин :)

_________________
No regret, no remorse, no mercy.
Я мёртв.


Вернуться к началу
 Профиль  
 
 Заголовок сообщения:
СообщениеДобавлено: Пн авг 15, 2011 3:27 pm 
Не в сети
Опытный автор

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


Вернуться к началу
 Профиль  
 
СообщениеДобавлено: Чт авг 18, 2011 9:49 pm 
Не в сети
Весьма плодовитый автор

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

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


Вернуться к началу
 Профиль  
 
 Заголовок сообщения:
СообщениеДобавлено: Пт авг 19, 2011 11:21 am 
Не в сети
Начинающий автор

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

_________________
No regret, no remorse, no mercy.
Я мёртв.


Вернуться к началу
 Профиль  
 
 Заголовок сообщения:
СообщениеДобавлено: Пт авг 19, 2011 9:30 pm 
Не в сети
Весьма плодовитый автор

Зарегистрирован: Чт сен 27, 2001 7:00 am
Сообщения: 1637
McUrgd писал(а):
А как хромосомы скрещивать в таком случае?

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

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


Вернуться к началу
 Профиль  
 
 Заголовок сообщения:
СообщениеДобавлено: Вс авг 21, 2011 12:14 am 
Не в сети
Весьма плодовитый автор

Зарегистрирован: Чт сен 27, 2001 7:00 am
Сообщения: 1637
Менее понятно, как определять мутации. Если мы возьмём путь и случайным образом заменим в нём одно ребро на какое-нибудь другое, то результат уже не будет путём. То есть все простейшие мутации дают нежизнеспособные хромосомы.

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

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


Вернуться к началу
 Профиль  
 
 Заголовок сообщения:
СообщениеДобавлено: Пт авг 26, 2011 12:27 pm 
Не в сети
Редкий гость

Зарегистрирован: Чт авг 25, 2011 11:32 pm
Сообщения: 10
Всем спасибо.
Нашел хорошее решение задачи используя код прюфера.

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


Вернуться к началу
 Профиль  
 
 Заголовок сообщения:
СообщениеДобавлено: Сб авг 27, 2011 3:28 pm 
Не в сети
Весьма плодовитый автор

Зарегистрирован: Чт сен 27, 2001 7:00 am
Сообщения: 1637
[shn]max писал(а):
Нашел хорошее решение задачи используя код прюфера.

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

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


Вернуться к началу
 Профиль  
 
 Заголовок сообщения:
СообщениеДобавлено: Сб авг 27, 2011 5:21 pm 
Не в сети
Редкий гость

Зарегистрирован: Чт авг 25, 2011 11:32 pm
Сообщения: 10
Код прюфера осуществляет взаимооднозначное соответствие между остовами и векторами размера n-2, где n - число вершин. А в остове существует единственный путь из одной вершины в другую.

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

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


Вернуться к началу
 Профиль  
 
 Заголовок сообщения:
СообщениеДобавлено: Ср авг 31, 2011 9:23 pm 
Не в сети
Весьма плодовитый автор

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

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

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


Вернуться к началу
 Профиль  
 
 Заголовок сообщения:
СообщениеДобавлено: Чт сен 01, 2011 5:30 pm 
Не в сети
Редкий гость

Зарегистрирован: Чт авг 25, 2011 11:32 pm
Сообщения: 10
Остова удобно использовать потому, что тогда у хромосом одинаковый размер получается. А целевая функция считает только вес пути.
Код прюфера же удобен тем, что некорректных хромосом при мутации и кроссоверенге получиться не может. Но вот беда в том, что последнее утверждение верно только для полных графов, а мы оперируем в основном с неполными.
Так, что проблема того, что получается много некорректных хромосом остается открытой.


Вернуться к началу
 Профиль  
 
 Заголовок сообщения:
СообщениеДобавлено: Пт сен 02, 2011 12:56 am 
Не в сети
Весьма плодовитый автор

Зарегистрирован: Сб сен 01, 2001 7:00 am
Сообщения: 1577
Откуда: Александр Фенстер
(пришёл со стороны, ссылки не читал, в генетических алгоритмах не шарю)

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

_________________
АФ


Вернуться к началу
 Профиль  
 
 Заголовок сообщения:
СообщениеДобавлено: Пт сен 02, 2011 1:53 am 
Не в сети
Редкий гость

Зарегистрирован: Чт авг 25, 2011 11:32 pm
Сообщения: 10
fenster писал(а):
(пришёл со стороны, ссылки не читал, в генетических алгоритмах не шарю)

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


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


Вернуться к началу
 Профиль  
 
 Заголовок сообщения:
СообщениеДобавлено: Пт сен 02, 2011 8:42 am 
Не в сети
Непрерывный писатель

Зарегистрирован: Пт июн 18, 2004 10:34 pm
Сообщения: 4435
Откуда: Сергей Подзоров
[shn]max писал(а):
...некорректных хромосом при мутации и кроссоверенге получиться не может.

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

_________________
Don't let the sun blast your shadow
Don't let the milk float ride your mind


Вернуться к началу
 Профиль  
 
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 19 ]  На страницу 1, 2  След.

Часовой пояс: UTC + 7 часов


Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей и гости: 4


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Перейти:  
Создано на основе phpBB® Forum Software © phpBB Group
Русская поддержка phpBB