ru.algorithms

 
 - RU.ALGORITHMS ----------------------------------------------------------------
 From : Yuri Burger                          2:468/85.3     28 Mar 2002  22:12:26
 To : Alexander Shmidt
 Subject : ГА на ЗК
 -------------------------------------------------------------------------------- 
 

 
 27 Mar 02 02:26, Alexander Shmidt wrote to Yuri Burger:
 
  AS>>> Вот, заинтересовался, как бы получше прикрутить ГА к задаче
  AS>>> коммивояжера. Если с оценочной и так все понятно, то как делать
  YB>> время хромосома - это набор перестановок в некоторой исходной
  YB>> последовательности обхода городов, включающей в себя все города.
  AS> Все равно не пойму, к чему ты все это сказал...
  AS> Давай конкретно:
  AS> Элитный отбор. Две хромосомы, задающие порядок обхода. Как скрещиваем?
 
     Пусть есть города 1, 2, 3, 4 (в задаче из ясен пень будет много больше, но
 не это есть суть важно).
 
     Тогда, пусть хромосомой будет заданное число пар (I,J), значения I и J
 лежат от 0 до 3 включительно (от 0 до число кородов минус 1). Тогда, при
 оценивании особи делаем:
 
     буфферный массив Buf размером в число городов. Заполняем его
 последовательностью: Buf={1,2,3,4} В нём теперь есть по одному городу, тоесть
 перечислены все города и сам массив может выступать в роли решения - очереди
 обхода городов.
     теперь пробегаем по массиву пар (I,J) образованному конкретной хромосомой.
 Допустим мы задали длину хромосомы в 4 пары, и на оценивание попала такая
 последовательность: (1,2)(3,4)(2,1)(1,3). В цикле рассматриваем каждую пару и
 делаем перестановку: I-й элемент массива Buf меняем местами с J-ым элементом
 того же массива. Тоесть, в рассмотренном случае:
    шаг
     0. Buf={1,2,3,4}
     1. меняем 1й и 2й элементы; Buf={2,1,3,4}
     2. .. 3,4; Buf={2,1,4,3}
     3. .. 2,1; Buf={1,2,4,3}
     4. .. 1,3; Buf={3,2,4,1}
 
     получили в Buf последовательность обхода городов, соответствующую
 хромосоме.
 
     так для любой другой хромосоме. Тоесть, хромосома - это набор перестановок
 некоторой постоянной исходной последовательности, а не сама последовательность
 обхода.
 
     Тогда, если число городов является степенью двойки, определяем сколько
 нужно выделить бит каждой паре (I,J). В рассмотренном примере это будет 4 бита
 (по 2 на I и J). Выбираем количество перестановок, скажем 16. Имеем хромосому
 длиной 16*4=64 бита. При этом любой набор из этих 64 бит будет верным решением.
 Если число городов не есть степень двойки, тогда либо вводим фиктивные города,
 либо выделяем количество бит с запасом, а при обработки подгоняем неверные
 значения (скажем, I=13, а городов 10, а значит и длина Buf 10, то делаем I=9
 или I=I%10).
 
     Тогда можно пользовать любой из кроссоверов, не боясь получить битое
 решение, где в обходе нет нескольких городов или наоборот, встречаются
 несколько раз.
 
     Тэсты что я делал для статей показывают что наилучший кросовер -
 двухточечный, при этом используется элитарный отбор.
 
 зы: такой же метод я пользовал в вариации на тему задачи рюкзака (принцип
 тэтриса) - результаты вполне удовлетворительные.
 
                                                  Kрюгер.
 ---
  * Origin: А хто тут есть, у кого есть за что поесть? (2:468/85.3)
 
 

Вернуться к списку тем, сортированных по: возрастание даты  уменьшение даты  тема  автор 

Тема:    Автор:    Дата:    ГА на ЗК   Alexander Shmidt   23 Mar 2002 00:13:44   ГА на ЗК   Alexander Grischuk   28 Mar 2002 03:14:40   ГА на ЗК   Yuri Burger   24 Mar 2002 18:52:22   ГА на ЗК   Alexander Grischuk   04 Apr 2002 23:00:42   ГА на ЗК   Alexander Shmidt   27 Mar 2002 03:26:19   ГА на ЗК   Yuri Burger   28 Mar 2002 22:12:26   Re: ГА на ЗК   Sveta Ivanova   27 Mar 2002 11:34:39