Как изобразить путь для генетического алгоритма?

Question

Я хочу использовать GA, чтобы определить оптимальный путь от A до B, удовлетворяющий определенным условиям (длина, количество витков и т. Д.)

Пример пути: Вверх 4, Влево 8, Вниз 3, Вправо 3, Вниз 1, Влево 10, Вверх 4, Влево 1, Вверх 3

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

У кого-нибудь есть хорошая идея, как сделать что-то подобное?

Answer 1

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

Answer 2

Я точно не знаю, в чем заключается ваша проблема с представлением, поэтому я подозреваю, что у вас возник этот вопрос из-за неправильного понимания строки хромосомы GA. Теоретически говоря, хромосомная строка не обязательно должна быть явно рекомбинирована на целочисленных границах, если вы предпримете дополнительный шаг по разграничению ваших индивидуальных генов, который позволит вам рекомбинировать по генам. Это решает проблему гена переменной длины, такого как ваш «путь». Для рекомбинации генов переменной длины достаточно добавить еще один вариант к методу мутации, в частности «использовать этот элемент или уничтожить этот элемент» в дополнение к стандартному «использовать элемент из A или элемент из B», если ваш ген можно разбить на дискретный элементы, как ваш путь.

Answer 3

GA может обрабатывать хромосомы с переменной длиной. Фактический Человек может быть очень сложным. например, он может содержать некоторое количество битов фиксированной длины, строки символов (без фиксированной длины) и, возможно, некоторый набор пар сопряженных комплексных чисел. Кроме того, пары сопряженных комплексных чисел должны всегда сохранять некоторые условия. Это можно сделать, но чем сложнее становится индивидуум, тем сложнее становятся генетические операции (например, переход, мутация). Вероятно, функция Fitness заняла бы еще несколько строк кода. Но это все еще возможно.

Возможно, как и предполагалось, вы можете выбрать представление пути с кодовым номером, но это все еще можно сделать с вашим примером, закодированным как Усама ALASSIRY предложил: UUUULLLLLLLLDDDRRRDLLLLLLLLLLUUUULUUU .
Для перехода:

• разрешить мутирующему оператору считывать текущую длину1 данного человека,
• генерирует два случайных числа x1, y1, оба x1, y1 = <длина1 и x1! = Y1 (это ваши точки нарезки для индивидуума 1), </li>
• сделать то же самое для индивидуума 2, теперь у вас есть две пары (x1, y1) и (x2, y2),
• скопировать из индивидуума 1 то, что находится между x1 и y1, и вставить его в индивидуума 2 между значениями x2 и y2. Новая версия Individual 2 может изменить свою длину, так как количество генов между x1y1 и x2y2 может отличаться, но это нормально,
• то, что было в исходной версии индивида 2 между x2y2, должно быть вставлено в новую версию индивида 1 между x1y1 (его длина также изменится),

Чтобы было понятно:
родитель A: UUUULLLLLLLLDDDRRRDLLLLLLLLLLUUUULUUU
родитель B: DRRRRLULUDDDR
вы генерируете случайные пары pairA (4,18), pairB (0,5) предполагая, что вы считаете гены от 0, вы меняете следующие строки:
UUUU LLLLLLLLDDDRRRD LLLLLLLLLLUUUULUUU
DRRRRL ULUDDDR
Итак, после перехода вы получите
UUUU DRRRRL LLLLLLLLLLUUUULUUU
LLLLLLLLDDDRRRD ULUDDDR
Теперь вы только что перешли. Вы можете использовать также одну точку резки или умножить точки.

Что касается мутации:

• генерирует число от 0 до длины индивидуума,
• генерирует число от 1 до 4 и обновляет этот ген. (если сгенерировано 1, замените его на U, 2-D, 3-L, 4-R)

Вы только что сделали мутацию. Вы также можете мутировать более одного гена.

Но, как я уже сказал, есть и другие возможности.

Answer 4

Я бы использовал U, D, L, R ....

Таким образом, «Вверх 4, Влево 8, Вниз 3, Вправо 3, Вниз 1, Влево 10, Вверх 4, Влево 1, Вверх 3» будет:

UUUULLLLLLLLDDDRRRDLLLLLLLLLLUUUULUUU

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

Для A (15 символов) и B (3 символа) моя функция разведения между A и B будет:

• Выберите произвольную желаемую длину (len) от 1 до MAX (LEN (A), LEN (B)) {от 1 до 15}
• Выберите случайную точку (точки) разделения между 1 и len.
• Выберите, хотите ли вы, чтобы A или B шли первыми в случайном порядке.
• Возьмите первые s символов из того, который идет первым, и последние (len-s) символы из другого.

Answer 5

Для меня это звучит очень похоже на проблему Путешествующий продавец , содержит ли эта страница некоторую полезную информацию?