|
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
Do'stlaringiz bilan baham: | 
