Генетический алгоритм - кратчайший путь во взвешенном графе

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

Моя идея состоит в том, чтобы случайным образом сгенерировать путь, состоящий из n-1 узлов для каждой хромосомы в двоичной форме, где числа указывают узлы пути. Затем я выберу лучшее в зависимости от суммы весов (если я не могу перейти от A к B, я назначу ему штраф) и скрещу/мутирую биты в нем. Это будет работать? Это немного похоже на уменьшенную версию брутфорса. Есть ли способ лучше?

Спасибо!


machine-learning artificial-intelligence genetic-algorithm
person Veasst    schedule 19.03.2017    source источник

Ответы (2)


arrow_upward
0
arrow_downward

Генетический алгоритм — это в значительной степени «уменьшенная версия грубой силы». Это всего лишь метаэвристика, а не метод оптимизации, обеспечивающий достойные гарантии сходимости. В основном предоставление новых решений зависит от случайности, поэтому это «немного лучший случайный поиск».

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

person lejlot    schedule 19.03.2017

arrow_upward
0
arrow_downward

Отредактировано.

Вы можете использовать перестановочное кодирование GA. В перестановочном кодировании вы должны указать начальную и конечную точки. GA ищет лучшую хромосому с вашей фитнес-функцией. Решения-кандидаты (хромосомы) будут такими, как 2-5-4-3-1, или 2-3-1-4-5, или 1-2-5-4-3 и т. д. Таким образом, ваше решение зависит от вашей фитнес-функции. (Посмотрите пакет GA для R, чтобы легко применить перестановку GA.)

Соединения являются ограничениями для вашей проблемы. Мой лучший совет — создать такую ​​матрицу ограничений:

FirstPoint SecondPoint Connected
A          B           true
A          C           true
A          E           false
...        ...         ...

В стандартном TSP учитываются только расстояния. В вашей фитнес-функции вы должны учитывать эту матрицу и добавлять штраф к возвращаемому значению для каждого значения false.

Example chromosome: A-B-E-D-C
A-B: 1
B-E: 1
E-D: 4
D-C: 3

Fitness value: 9

.

Example chromosome: A-E-B-C-D
A-E: penalty
E-B: 1
B-C: 6
C-D: 3

Fitness value: 10 + penalty value.

Поскольку ваше ограничение является жестким ограничением, вы можете использовать максимальное целочисленное значение в качестве штрафа. GA найдет лучшее решение. :)

person akadal    schedule 19.03.2017
comment
imgur.com/a/FmSQY Что-то в этом роде. ABEDC будет кратчайшим путем, который мне нужно найти. - person Veasst; 19.03.2017