|
4.3.2 Тестирование реализации генетического алгоритма для DES
1.Формирование начальных популяций.
Начальная популяция заполняется ключами сформированными
случайным образом.
Population: 0
1011101x0011010x1011001x1111001x0110010x1010000x1110111x1100000x
88
Population: 1
0101101x1010010x0011000x0000100x0110111x1001110x1111111x0101101x
Population: 2
0101010x0111110x0111001x0010000x1101110x0011000x0000011x0100100x
Population: 3
1000100x1101111x1010001x0111110x0100101x0011001x0000100x1111010x
Определение значений фитнесс-функции начальной популяции по
формуле (6) (таблица 4.23).
Таблица 4.23
Значение фитнесс-функции для начальных популяций
Популяция
Число совпавших бит в
тестовом и оригинальном
шифртекстах (из всего бит)
Фитнесс-
функция
Population: 0
50 (64)
0,781250
Population: 1
55 (64)
0,859375
Population: 2
49 (64)
0,765625
Population: 3
42 (64)
0,656250
Определение лучшего ключа начальной популяции.
По результатам формирования начальных популяций
Population: 3
имеет лучшее значение фитнесс-функции 0,859375. Ключ сформированный в
Population: 3 записывается, как лучший ключ (Best key).
Сортировка популяции
по значению фитнесс-функции (таблица 4.24)
Таблица 4.24
Результат сортировки
Популяция после сортировки
Популяция
Значение фитнесс-функции
Population: 0
Population: 1
0,859375
Population: 1
Population: 0
0,781250
Population: 2
Population: 2
0,765625
Population: 3
Population: 3
0,656250
89
Population: 0
0101101x1010010x0011000x0000100x0110111x1001110x1111111x0101101x
Population: 1
1011101x0011010x1011001x1111001x0110010x1010000x1110111x1100000x
Population: 2
0101010x0111110x0111001x0010000x1101110x0011000x0000011x0100100x
Population: 3
1000100x1101111x1010001x0111110x0100101x0011001x0000100x1111010x
2. Выбор «родителей» для формирования потомка.
Случайным образом выбирается две особи. Сравниваются значения их
фитнесс-функций, в качестве первого родителя из двух отобранных выбирается
особь с лучшим значением фитнесс-функции.
Затем аналогичным образом выбирается второй родитель.
В качестве 1 родителя выбрана особь со значением фитнесс-функции
0,781250. Следующий родитель был выбран таким же образом. Значение
фитнесс-функции 0,765625.
Parents: 0, 2
Population: 0
1011101x0011010x1011001x1111001x0110010x1010000x1110111x1100000x
Population: 2
0101010x0111110x0111001x0010000x1101110x0011000x0000011x0100100x
3.Формирование «потомка»
.
Потом формируется случайным разделением ключа в одной точке.
При этом, как описано выше, д
ля того чтобы выбрать, какой из
потомков будет получен, нужно выбрать, какой из родителей будет главным.
Что также определятся случайным образом.
В тестовом примере точка разделения была определена 46 битом. С 0 по
42 бит включительно данные взяты от родителя Population: 1.
Потомок пары parents: 1, 2:
1011101x0011010x1011001x1111001x0110010x1010000x1000011x0100100x
90
4.Мутация случайных генов.
В процессе мутации также происходит случайный выбор бит, которые
будут инвертированы с учетом вероятности мутации
mutation_rate, заданной в
качестве параметра алгоритма, а также генерацией случайного числа:
Случайность или право выбора муравья следовать определенному пути
обеспечивается использованием генерации случайного числом от 0 до
RAND_MAX
(2147483647) и сравнения этого числа с величиной
(int)(mutation_rate * RAND_MAX). Если получено случайное число меньше
этой величины, то бит будет инвертирован. Значение параметра mutation_rate
0,02 означает, что в среднем будет изменено два бита.
Потомок пары parents: 0, 2:
До мутации
1011101x0011010x1011001x1111001x0110010x1010000x1000011x0100100x
После мутации
1011101x0011011x1011001x1111001x0110010x1010000x1000011x0100100x
5.Определение значений фитнесс-функции полученных потомков.
По результатам первого поколения лучшим осталось значение фитнесс-
функции начальной популяции
0,812500 (таблица 4.25). Лучшим ключом
является потомок parents: 0, 1
0101101x1010010x0011000x0000100x0110111x1001110x0111111x0100000x
Таблица 4.25
Значение фитнесс-функции для потомков
Популяция
Число совпавших бит в
тестовом и оригинальном
шифртекстах (из всего бит)
Фитнесс-
функция
Parents: 1, 2
45 (64)
0,703125
parents: 0, 1
52 (64)
0,812500
91
6.Формирование популяции следующего поколения.
При заданных параметрах на следующее поколение должны перейти
потомки, а также два представителя текущего поколения с наилучшими
значениями фитнесс-функции. Результаты полученные в ходе тестирования
соответствуют ожидаемым.
7.Фиксирование бит при условии достижении параметра delta.
Цель тестирования: убедиться, что при достижении параметра биты в
ключе фиксируются, как найденные.
Параметр delta для определения будет ли зафиксирован бит, как
определенный, задан, как входные данные и для тестирования равен 0,6. Для
определения будет ли зафиксирован бит используются соотношения (3-10) и
(3-11):
В результате работы алгоритма получено 4 ключа:
Do'stlaringiz bilan baham: |
