Главная | RSS News
 
 

Принцип работы генетического алгоритма

Вначале формируется множество потенциальных решений (гипотез), которое представляет собой начальную популяцию. В большинстве случаев это множество формируется случайно. После того как создана начальная популяция, выполняем процедуры скрещивания и мутации. Скрещивание моделирует передачу наследственности хромосомами. Эта операция обусловливает целенаправленное закономерное "приближение" свойств хромосом к оптимальному решению. При скрещивании хромосомы группируются в пары, случайным образом выбирается одна точка (ген) на хромосоме и хромосомы обмениваются между собой выбранными генами.
Целью оператора скрещивания [106] является порождение из имеющегося множества решений нового, в котором каждая хромосома будет являться потомком некоторых двух элементов предыдущей популяции, т. е. нести в себе частично информацию каждого родителя. Заметим, что оператор скрещивания (кроссинговер) может применяться не ко всем представителям популяции. Задается некоторая вероятность pс – вероятность скрещивания и алгоритм выбора пары родителей для скрещивания. Конкретное значение pс зависит от решаемой задачи, о чем говорят и встречающиеся в литературе оценки типа pс0,6 и pс[0,750,95] в работе [106], pс  0,95 [384]. Для нашей задачи выбираем вероятность скрещивания pс[0,80,9].
Стоит отметить, что на сегодняшний день создано множество вариантов оператора скрещивания. В то же время их все можно разделить на два класса в зависимости от решаемой задачи. А именно тип применяемого скрещивания зависит от того, решается ли задача, когда работа ведется со строками конечной длины, или приходится иметь дело с некоторыми подстановками.
Классическим вариантом оператора скрещивания является одноточечное скрещивание, при котором случайным образом выбирается число m{1,…,L-1}, где L – размер хромосомы, называемое точкой скрещивания или точкой разрыва, и все гены, начиная с m+1 до L включительно, переставляются у выбранных хромосом. Также известны теоретические исследования одноточечного скрещивания [390] на основе введения понятия схемы Schemata, которая является шаблоном, описывающим подмножество представителей популяции, имеющих одинаковые значения некоторых генов.
Известны исследования генетических алгоритмов с применением n-точечного скрещивания [390]. При таком способе случайно выбираются n точек разрыва, что приводит к разбиению исходных векторов на n+1 частей различной длины. Далее предлагается обменять у исходных хромосом участки с четными номерами, а участки с нечетными номерами оставить без изменений. Де Янг [106] в своих исследованиях заметил, что двухточечное скрещивание разрушает “длинные” схемы с меньшей вероятностью, чем одноточечное. И вообще n-точечное скрещивание с меньшей вероятностью разрушает схемы при четном n, чем при нечетном. Дальнейшие исследования также показали, что для ряда проблем более эффективным оказывается использование нескольких точек скрещивания.
Одним из вариантов данного вида скрещивания является равномерное скрещивание, предложенное в работе [423]. При этом случайным образом создается маска скрещивания, представляющая собой строку из нулей и единиц длины L. Далее выбираются два представителя популяции (родители), и два новых решения (дети) получаются по следующему правилу. Единица на i-й позиции в маске скрещивания означает, что элемент, стоящий на том же месте у первого родителя, необходимо поместить на i-е место первого ребенка. Нуль на i-й позиции в маске скрещивания означает, что элемент, стоящий на том же месте второго родителя, необходимо поместить на i-е место первого ребенка. Теперь, если первого родителя считать вторым, а второго – первым, то по описанному правилу можно получить второго ребенка. Стоит отметить, что маска скрещивания может быть одна для всех хромосом, либо своя для каждой пары родителей.

Прочитало: 1616
 
 
Календарь
 
«    Октябрь 2013    »
ПнВтСрЧтПтСбВс
 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
 
 
 

Меню
  »  Классификация портов проникновения ЭМИ
»  Задачи ЭМС ЭС при внешних воздействиях
»  Средства электромагнитного террора
»  Методы и средства анализа воздействия ЭМИ на ЭС
»  Анализ эффективности экранирования корпусов ЭС
»  Экранирование э.-м. воздействий стенами ИЗ
»  Цель и методы оптимизации
»  Оптимизация внутриаппаратурной ЭМС межсоединений
»  Многокритериальная оптимизация
 
 

Архивы
 Октябрь 2008 (17)
Сентябрь 2008 (30)
Август 2008 (19)
 
 

Популярное
   
 

Реклама
 
Статьи
Ещё
 
 

 
 
E-M-P.Ru 1, 2