Проектирование и разработка информационных систем

2.1 Генетический алгоритм 
Основной принцип работы эволюционных алгоритмов основан на 
компьютерном моделировании процесса эволюции с учетом факторов 
изменчивости, наследования и отбора наиболее приспособленных особей. При 
решении задачи оптимизации строится множество (популяция) допустимых 
решений, к которым применяются случайные преобразования для того, чтобы 
найти лучшее решение. Популяция развивается за счет отбора родительских 
особей с помощью оператора селекции и применения к ним случайных 
операторов, имитирующих мутацию генов и рекомбинацию родительских 
генотипов (кроссинговер). Особи с большим значением приспособленности, 
которая определяется целевой функцией (функцией приспособленности), или 
фитнесс-функцией, получают большее число потомков на следующем 
поколении. В случае применения алгоритма для криптоанализа особь 
представляет собой ключ в виде бинарной строки с длиной равной длине 
ключа. 
Инициализация процедуры алгоритма поиска заключается в создании 
популяции возможных решений. Классический вариант генетического 
алгоритма состоит из трёх основных стадий: отбор, скрещивание (кроссовер), 
мутация. Так как для получения следующего поколения, то есть потомков, 
отбираются лучшие особи, следующее поколение получается лучше 
предыдущего. Мутация требуется, чтобы избегать локальным экстремумов. В 
результате работы алгоритма определяется экстремум фитнесс-функции, 
заданной на дискретном множестве допустимых решений. 
Для использования генетического алгоритма в задаче нахождения 
допустимых решений, в случае криптоанализа – ключа шифра, необходимо 
выбрать способ кодирования допустимых решений, правила скрещивания и 
мутации, стратегии отбора, а также выбрать подходящую фитнесс-функцию, 

---

38 
чья точка глобального максимума или минимума будет являться искомым 
значением ключа шифра. 
Генетический алгоритм строится следующим образом: 
1. Инициализация начальной популяции (в общем случае может быть 
сформирована случайным образом из бинарных строк). 
2. Скрещивание. Представители текущей популяции в соответствии со 
стратегией отбора образуют пары и после этого скрещиваются, то есть 
применяется оператор кроссовера. В классическом варианте кроссовер 
одноточечный. Выбирается точка раздела бинарных строк, потомки 
получаются путем обмена отрезками. 
3. У особей нового поколения с некоторой вероятностью происходит 
мутация (инверсия) отдельных генов. Вероятность инвертирования является 
одним из параметров алгоритма. 
4. Шаги 2-3 повторяются до тех пора, пока не будет достигнут заданный 
параметр количества поколений или схождения популяции, то есть все строки 
популяции находятся в области экстремума и почти одинаковые, то есть 
скрещивание практически не изменяет популяции, а мутирующие строки не 
включаются в следующее поколение, так как менее приспособлены. Итоговым 
решением будет наиболее приспособленная строка последнего поколения.
Способ выбора фитнесс-функции зависит от решаемой задачи. 
Например, в работе [10] для криптоанализа подстановочного шифра Виженера 
в качестве фитнесс-функции используется : 
𝐹(𝐾) = ∑ |𝐷
𝑖𝑗
𝐾
− 𝐸
𝑖𝑗
|
𝑖𝑗
(2-1),
где 
𝐷
𝑖𝑗
𝐾
– частоты встречаемости двухбуквенного слова («биграммы») в тексте, 
полученном из зашифрованного текста после его расшифрования с помощью 
предполагаемого ключа K; 
𝐸
𝑖𝑗
- частоты встречаемости биграммы в 
среднестатистическом осмысленном тексте, которые заранее известны или 
могут быть вычислены на основании статистического анализа текстов.

---

39 
В других задачах в качестве фитнесс-функции может использоваться 
количество отличающихся бит в оригинальном зашифрованном тексте и в 
тексте, зашифрованном тестируемым ключом. 
Недостатком генетического алгоритма можно назвать проблему 
нахождения экстремума немонотонной функции, то есть значение функции в 
каждой точке является, по сути, случайной величиной и невозможно получение 
информации о приближении к глобальному экстремуму.