Дискретно-непрерывная математика. Кн. 0 : Алгоритмы. Ч. Генетические алгоритмы

3.9.6. 
Ниши в генетическом алгоритме 
В различных оптимизационных задачах часто приходится иметь дело с 
функциями, имеющими несколько оптимальных решений. Основной 
генетический алгоритм в таких случаях находит только глобальный 
оптимум, но если имеется несколько оптимумов с одним и тем же 
значением, то он отыскивает только один из них. В некоторых задачах 
бывает важным найти не только глобальный оптимум, но и локальные 
оптимумы (не обязательно все). Концепция реализации в генетических 
алгоритмах подхода, основанного на известных из биологии понятиях 
ниш и видов, позволяет находить большую часть оптимумов. 
Практически применяемый в генетическом алгоритме метод 
образования ниш и видов основан на так называемой 
функции соуча-
стия (sharing function). 
Эта функция определяет уровень близости и 
степень соучастия для каждой хромосомы в популяции. Функция 
соучастия обозначается s(d
ij
), где d
ij
- мера расстояния между хромосо-
мами ch
i
и ch
j
. В программе 
FlexTool 
это расстояние определяется по 
формуле





p
k
min
,
k
max
k
j
,
k
i
,
k
ij
)
x
x
(
x
x
d
1
2

---

А.Е. Кононюк Дискретно-непрерывная математика 
157 
где 
р
означает размерность задачи, х
k,min
и 
x
k,
max
определяют соответ-
ственно минимальное и максимальное значение k-го параметра, 
x
ki
 
и 
x
kj
 
- 
обозначают соответственно 
k-й 
параметр i-й и j-й особей. Очевидно, 
что расстояние между хромосомами рассчитывается на основе 
соответствующих им фенотипов.
Функция соучастия s(d
ij
) должна обладать следующими свойствами:
0 ≤ 
s(d
ij
) ≤ 
1 для каждого d
ij
,
s(0) = 1,


ij
d
lim
s(d
ij
) = 0
Одна из функций, для которой эти условия выполняются, имеет вид
s(
d
ij
)=






случае
противном
в
,
d
если
,
)
/
d
(
s
ij
s
ij
0
1



 
где σ
s
и ω
- константы.
В программе