Привет, коллективный разум, есть такая проблема:
генетическим методом найти упорядочение n элементов.

Как построить соответствие каждого конкретного упорядоченья двоичному вектору?
Или я чего–то принципиально не понял в ГА и представлять особь двоичным вектором совсем даже и не обязательно?

GD Star Rating
loading...
генетическим методом найти упорядочение n элементов., 6.0 out of 10 based on 1 rating

12 Responses to генетическим методом найти упорядочение n элементов.

  1. PeBam:

    Двоичный вектор не обязательно должен быть. Просто особь должна позволять мутации и кроссовер.
    Стандартный способ тут — представить в виде вектора случайных (действительных) чисел от 0 до 1.
    Упорядочение задается сортировкой такого вектора. Кроссовер и мутации очевидны.
    Еще один способ — представлять в виде именно упорядочения (т.е. графа–цикла) и определить мутации и кроссовер чуть менее очевидным, но тоже не самым хитрым способом (мутация, к примеру = транспозиция двух элементов, а кроссовер — совмещение начала первого пути и конца второго). Оба способа распространены и должны гуглиться на ура.

  2. TeApp:

    > Упорядочение задается сортировкой такого вектора
    не понятно, не мог бы тут поподробней?

    Вопрос собственно именно в кроссовере двух упорядочиний, да. Что–то ничего очевидного и прилично выглядещего в голову не приходит.

  3. TeApp:

    Первое что в голову пришло — в качестве особи использовать конкатенацию строк верхней полуматрицы отношения порядка, но тогда для каждой особи придется полученную матрицу проверять на транзитивность и антисимметричность, а это несколько пагубно для скорости по–моему

  4. PeBam:

    Первый вектор: (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», найдешь еще кучу вариантов.

  5. TeApp:

    так числа (0.3, 0.4, 0.1, 0.9) всё равно так или иначе получаются дискретно распределены и могут в итоге вырасти одинаковыми, не?

  6. PeBam:

    Получатся одинаковыми — предпочитай то, что левее. Но вероятность этого, если использовать 32хбитные числа, пренебрежимо мала.

  7. TeApp:

    ну к этому я тоже пришел, но мне показалось, что это не слишком обоснованное решение.

  8. PeBam:

    А в чем проблема? Тебе нужно отдельное обоснование для использования в изначально эвристическом алгоритме эвристического способа разрешения «ничьих», причем в ситуациях, вероятность которых сравнима с вероятностью падения метеорита?

  9. TeApp:

    ладно, это я иронизирую
    спасибо за помощь

  10. PeBam:

    Да ты теоретик!

  11. TeApp:

    Хм, в общем насколько я понял подход к кроссоверу приминительно к маршруту у людей примерно «поделим — скрестим — точки дублируются? — и фиг с ними — заменим что бы нет». Ну да и почему бы и нет, собственно.

Добавить комментарий