Привет, коллективный разум, есть такая проблема:
генетическим методом найти упорядочение n элементов.
Как построить соответствие каждого конкретного упорядоченья двоичному вектору?
Или я чего–то принципиально не понял в ГА и представлять особь двоичным вектором совсем даже и не обязательно?
GD Star Rating
loading...
генетическим методом найти упорядочение n элементов.,
loading...
Двоичный вектор не обязательно должен быть. Просто особь должна позволять мутации и кроссовер.
Стандартный способ тут представить в виде вектора случайных (действительных) чисел от 0 до 1.
Упорядочение задается сортировкой такого вектора. Кроссовер и мутации очевидны.
Еще один способ представлять в виде именно упорядочения (т.е. графацикла) и определить мутации и кроссовер чуть менее очевидным, но тоже не самым хитрым способом (мутация, к примеру = транспозиция двух элементов, а кроссовер совмещение начала первого пути и конца второго). Оба способа распространены и должны гуглиться на ура.
> Упорядочение задается сортировкой такого вектора
не понятно, не мог бы тут поподробней?
Вопрос собственно именно в кроссовере двух упорядочиний, да. Чтото ничего очевидного и прилично выглядещего в голову не приходит.
Первое что в голову пришло в качестве особи использовать конкатенацию строк верхней полуматрицы отношения порядка, но тогда для каждой особи придется полученную матрицу проверять на транзитивность и антисимметричность, а это несколько пагубно для скорости помоему
Первый вектор: (0.3, 0.4, 0.1, 0.9) задает упорядочение (3,1,2,4).
Второй вектор: (0.1, 0.8, 0.7, 0.05) задает упорядочение (4, 1, 3, 2).
Кроссовер, например: (0.3, 0.4 | 0.7, 0.05).
Погугли «Traveling salesman genetic algorithms», найдешь еще кучу вариантов.
так числа (0.3, 0.4, 0.1, 0.9) всё равно так или иначе получаются дискретно распределены и могут в итоге вырасти одинаковыми, не?
Получатся одинаковыми предпочитай то, что левее. Но вероятность этого, если использовать 32хбитные числа, пренебрежимо мала.
ну к этому я тоже пришел, но мне показалось, что это не слишком обоснованное решение.
А в чем проблема? Тебе нужно отдельное обоснование для использования в изначально эвристическом алгоритме эвристического способа разрешения «ничьих», причем в ситуациях, вероятность которых сравнима с вероятностью падения метеорита?
да!
ладно, это я иронизирую
спасибо за помощь
Да ты теоретик!
Хм, в общем насколько я понял подход к кроссоверу приминительно к маршруту у людей примерно «поделим скрестим точки дублируются? и фиг с ними заменим что бы нет». Ну да и почему бы и нет, собственно.