ru.algorithms

 
 - RU.ALGORITHMS ----------------------------------------------------------------
 From : Sveta Ivanova                        2:5004/55.115  27 Mar 2002  11:34:39
 To : Alexander Shmidt
 Subject : Re: ГА на ЗК
 -------------------------------------------------------------------------------- 
 

 
                               Пpивет, Alexander!
 
  Совсем случайно я увидел, что в 27 Мар 02 02:26, Alexander Shmidt писал Yuri
 Burger:
  AS> Давай конкретно:
  AS> Элитный отбор. Две хромосомы, задающие порядок обхода. Как
  AS> скрещиваем?
 
 Существует, например, такой вариант. Есть 2 родителя, скажем, a и b. Hаносим им
 ножевые ранения в 2-х местахх случайным образом (получаем, то бишь, 3 куска)
 ;-). Теперь для 1-го потомка берем средний кусок от 1-го родитель, для 2-го,
 соответственно, от 2-го. Теперь берем крайние куски и пытемся поменять их
 местами (т.е. у 1-го потомка крайние куски от 2-го родителя). Тут уже не все
 так
 просто - может оказаться, что какой-то город в начальном куске 2-го родителя
 уже
 есть в среднем куске 1-го. Сначала обмениваем гены в тех позициях, для которых
 это возможно. После этого начинаем бороться с проблемой. А бороться мы будем
 вот
 таким образом. Мы хотим поменять местами города в i-й позиции, ai и bi. Если
 сцществует j (из среднего куска), такое что aj=bi, то мы вместо bi ставим 1-му
 потомку bj. Если опять не получается, т.е. существует k такое что ak=bj, значит
 ставим вместо bj bk. И т.д. Вот картинка для наглядности:
 
 1234567 -----> 12 | 345 | 67 -----------> ** | 345 | **  ------> 71 | 345 | **
 режем                берем                       делаем
                              цент. куски                 обмен
 7125634 -----> 71 | 256 | 34 -----------> ** | 256 | **  ------> 1* | 256 | *7
 
 У 2-го потомка во 2-й позиции должна была быть 2, но она уже есть в 4-й; у 1-го
 в 4-й стоит 3, следовательно 2->3. Имеем следующее:
 
 71 | 345 | **
 13 | 256 | *7
 
 Теперь аналогично: для 5-й позиции 2-го потомка 6->5, 5->4, т.е. вместо 6 в 4-ю
 поз. ставим 4:
 
 71 | 345 | ** ------------------------> 71 | 345 | 26
               аналогично расправляемся
               с 1-м потомком
 13 | 256 | 47 ------------------------> 13 | 256 | 47
 Есть еще другие варианты, в том числе с другим генотипом, например, матричное
 представление. У меня это все есть в виде html-странички, если надо - могу
 кинуть по нетмылу.
 
                        Всегo наилучшегo. SvetiK.
 
 --- GoldED+/W32 1.1.3.1
  * Origin: @e:\ftn\golded\origins.tXT (2:5004/55.115)
 
 

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

Тема:    Автор:    Дата:    ГА на ЗК   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