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

·

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

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

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

похожие публикации

  1. Помогите найти правильную формулу
  2. Друзья, как мне недавно стало известно
  3. Необходимо определить вероятность двух тузов подряд
  4. Помогите найти ошибку
  5. Помогите найти решение без графика
Tagged with → • • •  

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

  1. PeBam:
    15/12/2011 в 17:53

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

    Ответить
  2. TeApp:
    15/12/2011 в 18:03

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

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

    Ответить
  3. TeApp:
    15/12/2011 в 18:11

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

    Ответить
  4. PeBam:
    15/12/2011 в 18:30

    Первый вектор: (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:
    15/12/2011 в 18:36

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

    Ответить
  6. PeBam:
    15/12/2011 в 21:17

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

    Ответить
  7. TeApp:
    15/12/2011 в 21:24

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

    Ответить
  8. PeBam:
    15/12/2011 в 21:36

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

    Ответить
  9. TeApp:
    15/12/2011 в 21:41

    да!

    Ответить
  10. TeApp:
    15/12/2011 в 21:50

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

    Ответить
  11. PeBam:
    15/12/2011 в 21:50

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

    Ответить
  12. TeApp:
    16/12/2011 в 10:14

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

    Ответить

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