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

3.2.4 Генетический алгоритм 
Решается задача нахождения ключа по известному оригинальному и 
зашифрованному тексту. Оригинальный текст, ключи, зашифрованный текст 
обрабатываются в виде бинарных строк, аналогично муравьиному алгоритму, 
что позволяет использовать достаточно простую фитнесс-функцию сравнения 
бинарных битовых строк.
Структура, содержащая данные особи struct genotype. Структура, 
содержащая дополнительные параметры для работы алгоритма struct gen_cfg. 
Структура, управляющая работой генетического алгоритма Часть 
параметров аналогична параметрам, используемым в муравьином алгоритме 
struct gen. 
Для реализации генетического алгоритма в OPS добавлены следующие 
функции: 
Функция порождения ключа-«ребенка» по заданным параметрам 
void ops_data_breed (struct ops_data ops,

---

59 
void *parent_key1, void *parent_key2, void *child_key) 
Родители выбираются из популяции методом турнирной селекции с 
учетом значения фитнесс-функций. В качестве родителей выбираются ключи с 
лучшим значением фитнесс-функции. При этом соблюдается условие, чтобы 
потом появлялся от двух разных родителей.
Выбор родителей для скрещивания реализован в gen.c. В функции 
static struct genotype* gen_select_tournament(struct gen *p) 
происходит проведение турниров, в которых выбирают одного победителя из 
текущей популяции с учетом наилучшего значения фитнесс-функции и 
функции
static void gen_select(struct gen *p,struct genotype **parent1,struct genotype 
**parent2), 
которая выбирает двух различных победителей турниров, которые будут 
являться родителями. 
Как отмечалось выше, в классическом варианте кроссовер 
одноточечный. Точка раздела бинарных строк определяется случайным 
образом, потомки получаются путем обмена отрезками. При этом возможно 
создание двух видов потомков (см. рис. 3.2) 
Рисунок 3.2 - Формирование ключа-потомка в генетическом алгоритме 
Для того чтобы выбрать, какой из потомков будет получен, нужно 
выбрать, какой из родителей будет главным (главным считается тот, чьи биты в 

---

60 
ключе будут первыми). В представленной реализации это делается следующим 
образом: диапазон разреза удваивается 2 * (key_length - 1), и точка разделения, 
принадлежащая диапазону, определяется случайным образом
pos = rand() % (2 * (key_length - 1)), где 
pos – бит разделения 
key_length – длина ключа 
Если позиция разреза не выходит за рамки длины ключа [0..key_length-
1], значит, основным родителем будет родитель 1 (parent_key1), в противном 
случае родитель 2 (parent_key2). В последнем случае необходимо пересчитать 
позицию разреза. Реализация данное положения приведена в листинге 3.1. 
Листинг 3.1 — Реализация определения позиции разреза при формировании 
ключа-потомка 
if (pos >= ops->key_length - 1) 
{ 
// swap parents 
tmp = parent_key1; 
parent_key1 = parent_key2; 
parent_key2 = tmp; 
// fix position 
pos -= ops->key_length - 1; 
} 
Основная функция работы генетического алгоритма void gen_run(struct 
gen *p). Эта функция работает следующим образом: 
1. Создаются случайные особи для начальной популяции population; 
2. Определение значения фитнесс-функции для созданных особей. Проверка 
значения фитнесс-функции. Сохраняется лучшее полученное значение и 
соответствующая особь (тестовый ключ); 

---

61 
3. Полученная популяция сортируется по значению фитнесс-функции в 
убывающем порядке; 
4. Алгоритм для создания нового поколения tmp: 
4.1 В новое поколение сохраняется заданное количество особей с 
наилучшими значениями фитнесс-функции; 
4.2 Создание потомков с одноточечным кроссовером 
- выбор родителей — турнирная селекция 
- создание потомка 
- мутация потомка 
4.3. Определение значений фитнесс-функции для полученных особей 
4.4. Проверка полученных значений фитнесс-функции с наилучшим 
значением, сохраненном в п.3. Если получено значение лучше, чем 
предыдущее, полученное значение сохраняется как лучшее и сохраняется 
соответствующая особь (тестовый ключ). 
5. Полученная популяция tmp сортируется по значению фитнесс-функции 
6. Новое поколение tmp сохраняется, как текущее поколение population 
7. Алгоритм повторяется с п.5 
В конце работы алгоритма собирается статистика по последнему 
поколению, позволяющая установить, какие гены проявляются чаще всего. Эти 
гены будут считаться известными. 
Проверка происходит следующим образом: 
- определяется sum - сколько раз бит на определенной позиции ключа 
установлен в 1 
- общее полученное количество сравнивается с размером популяции c учетом 
заданного параметра delta и правилу 
sum ≥ population_size * delta
=>
bit = 1
(3-10) 
sum ≤ population_size * (1 - delta) =>
bit = 0
(3-11) 
в остальных случаях бит остается не определенным (known_bits[i] = -1). 
sum - сколько раз бит на определенной позиции ключа установлен в 1 
population_size - размером популяции 

---

62 
delta – параметр для определения будет ли зафиксирован бит, как 
определенный
bit – установка значения бита
known_bits[i] – массив фиксированных битов.
Значение основных параметров для работы алгоритма задается для AES 
и DES соответственно в функциях: int test_gen_aes() и int test_gen_des() 
В случае работы с алгоритмом шифрования DES добавляется количество 
раундов des_rounds шифрования, для которых возможно проводить 
эксперименты. 
Реализованная система для муравьиного и генетического алгоритмов 
позволяет легко дополнять разные фитнесс-функции, определять начальное 
распределение феромонов, дополнять различные способы селекции, то есть 
разработанная система является достаточно гибкой для дальнейшей работы.
Технические характеристики: 
Реализация на языке: С 
Среда разработки: Code::Blocks 16.01 
Компилятор: gcc 
Операционная система: Linux Debian GNU 9.0 
Процессор: 4 Intel Core™ I5-2430M 2.40 GHz 
Память: 6065 MB