Санкт-Петербург

t
A
x
X
Q
i
n
i





, 
где n=9, е=0,1, N<50 000 с вещественным кодированием хромосом и пропорциональным 
отбором при различных размерах популяции на отрезке поиска. Аналогичные зависимости 
получены и в работе. 
Из рис. 1 видно, что при количестве поколений 50 000 оптимум с требуемой точностью 
не достигается из-за «стагнации» алгоритма и ступенчатого характера сходимости, 
исследуемого ГА. Причем количество ступенек зависит от размера популяции. Такие же 
результаты получаются исследователями ГА при управлении начальной популяцией и 
использовании метамоделей для оптимизируемых функций. 
Исходя из этого, целью исследований в нашей работе являлось ускорение сходимости 
при: 
.
min
min,


N
N
хр

---

Альманах научных работ молодых ученых 
XLVII научной и учебно-методической конференции Университета ИТМО. Том 1 
125 
Рис. 1. Эволюция наилучшей хромосомы 
Несмотря на предложенные исследователями многочисленные подходы: использование 
штрафов; введение в ГА дополнительных операторов мутации; гибридизация ГА – 
добавление в колонию хромосомы, работающей по особому алгоритму, например, 
«жадному»; элитизм – сохранение и переход наилучших хромосом в следующее поколение 
без изменений; уменьшение p
мут
при успешном движении к оптимуму и другие, – управление 
работой ГА усложняется, а выигрыш в сходимости достигается незначительный и лишь на 
определенных интервалах N. 
В связи с этим для выполнения цели исследования представлялось интересным 
разработка и исследование процедур: коррекции p
мут
и интенсивного отбора наилучших 
хромосом при «стагнации» сходимости ГА, а также сравнение их эффективности. 
Закон прогресса изменяется по закону: 
)
(
exp
0
t
G
G


, 
(1) 
где G
0
– состояние эволюции в начальный момент времени; α – коэффициент, определяющий 
скорость и характер развития прогресса. 
Рассматривая метод управления мутациями, можно периодически оценивать частоту 
успеха мутаций на i-ой итерации по соотношению: 
5
1


N
N
n
n
n
хр
у спех
му т
у спех
, 
(2) 
где n
успех
– количество успешных мутаций; n
мут
– общее число мутаций. 
При выполнении соотношения (2), т.е. при 20% успешности попыток мутаций, ход 
эволюции решений ГА считается успешным. Тем не менее, универсального правила 
управления мутациями в зависимости от вида функции исследователями не выработано. 
Исследователи этого вопроса, сопоставив длины более 100 генетических деревьев 
нуклеотидных последовательностей ДНК, пришли к выводу, что отношение периодов 
интенсивного развития и скачкообразных преобразований к долгим и постепенным 
составляет в среднем 22% к 78% [3]. 
Для проведения имитационного эксперимента на персональном компьютере сделаны 
следующие преобразования. 
Соотношение (1) преобразовано для удобства к виду: 
)
(
ln
)
(
N
b
a
N
G



, 
(3) 
где a и b – коэффициенты. 
0
2
4
6
8
10
12
14
100
2300
4500
6700
8900
11100
13300
15500
17700
19900
22100
24300
26500
28700
30900
33100
35300
37500
39700
41900
44100
46300
48500
N
Q
(X
)
Nхр=50
Nхр=100
Nхр=150
Nхр=200

---

Альманах научных работ молодых ученых 
XLVII научной и учебно-методической конференции Университета ИТМО. Том 1 
126 
Условие расхождения процесса поиска с законом (3) на промежутке длиной k–i 
поколений запишем 
k
i
X
Q
X
Q
N
G
N
G
k
i
k
i




,
28
,
0
)
(
)
(
)
(
)
(
)
(
)
(
. 
(4) 
Значения a, b и k–i подбирались экспериментально. При выполнении условия (4) 
значение p
мут
увеличивалось с шагом 0,001 [4]. 
Результаты имитационных экспериментов управления мутациями представлены на 
рис. 2. 
Рис. 2. Результаты имитационных экспериментов 
Управление величиной мутации позволило ускорить сходимость ГА при оптимальном 
количестве хромосом и поколений. 
В дальнейшем планируется исследование процедуры интенсивного отбора наилучших 
хромосом при «замирании» сходимости ГА и сравнение эффективности исследуемых 
методов ускорения сходимости ГА. 
Используя полученные результаты можно будет переходить непосредственно к самой 
разработке модели эволюции управления работой ГА.