Демонстрационный пример.
Применение комбинированных биоинспирированных стратегий (генетический алгоритм и алгоритм пчелиных колоний) для реализации криптоанализа классических шифров перестановок

РефератПомощь в написанииУзнать стоимостьмоей работы

В соответствии с шагом 10 алгоритма проведем операцию универсального кроссинговера по норме 75%, при этом для получения 9 потомков Е15-Е23 выбраны следующие списки: Е9-Е10 (с позиции 3, потомки Е15, Е16), Е8 -Е12 (с позиции 2, потомки Е17, Е18), Е3-Е11 (с позиции 3, потомки Е19, Е20), Е10-Е11 (с позиции 1, потомки Е21, Е22), Е4-Е6 (потомок Е23). Пусть сформированы следующие маски: 00, 01, 10, 11… Читать ещё >

Демонстрационный пример. Применение комбинированных биоинспирированных стратегий (генетический алгоритм и алгоритм пчелиных колоний) для реализации криптоанализа классических шифров перестановок (реферат, курсовая, диплом, контрольная)

Как и ранее в [7,8], рассмотрим реализацию представленного алгоритма на демонстрационном примере. Пусть задана строка из 12 символов ДИАИОБСУРНЯЦ, требуется определить возможную перестановку символов, входящую в словарный состав языка. Как и ранее в [7,8], составим матрицу С_ij, показывающую вероятность того, что за символом i может следовать символ j. Матрица С_ij составлена на основе данных, приведенных в [13,24], и показана в табл. 1. Значения, приведенные в [13], промасштабированы и округлены до десятых долей.

Таблица № 1. Вероятность появления биграмм в тексте.


	Д И, А О Б С У Р Н Я Ц
Д И. А О. Б С. У Р. Н Я. Ц	0.1 0.8 0.9 0.8 0.1 0.7 0.8 0.6 0.5 0.2 0.1 0.7 0.8 0.4 0.5 0.6 0.8 0.1 0.7 0.8 0.5 0.1 0.8 0.7 0.2 0.4 0.8 0.7 0.2 0.7 0.8 0.5 0.4 0.8 0.5 0.2 0.2 0.9 0.9 0.1 0.9 0.8 0.1 0.1 0.1 0.6 0.7 0.8 0.1 0.1 0.5 0.5 0.2 0.1 0.1 0.3 0.7 0.8 0.9 0.1 0.1 0.6 0.4 0.7 0.1 0.1 0.3 0.1 0.1 0.1 0.4 0.3 0.1 0.7 0.5 0.1 0.1 0.3 0.7 0.9 0.9 0.1 0.3 0.4 0.1 0.3 0.2 0.1 0.2 0.8 0.9 0.9 0.1 0.2 0.4 0.1 0.2 0.3 0.1 0.2 0.1 0.1 0.1 0.1 0.2 0.1 0.2 0.3 0.1 0.1 0.1 0.5 0.4 0.2 0.1 0.1 0.2 0.1 0.1 0.1 0.1

Пространство поиска, как и ранее в [8], определим в виде матрицы, А размером 21×24 заполненной символами из алфавита шифртекста, размещенными случайным образом в ячейках с соответствующими координатами (табл. 2).

Будем предполагать, что весовой коэффициент Q используется для списков длиной более 2 символов, используется также операция универсального кроссинговера по маске. Если скрещиваются хромосомы разной длины, то случайным образом выбирается номер позиции начала скрещивания.

Таблица 2. Пространство поиска для комбинированного алгоритма.

И.

Р.

Б.

Я.

И.

У.

Н.

И.

С.

Р.

О.

А.

С.

И.

Р.

Б.

Я.

Б.

Р.

У.

Д.

И.

Н.

Я.

О.

Р.

Д.

С.

Я.

И.

Р.

Н.

Б.

О.

А.

С.

И.

Р.

Б.

Я.

И.

Р.

Д.

С.

Я.

И.

Р.

Н.

Б.

У.

С.

А.

И.

Я.

Б.

Р.

У.

И.

А.

О.

А.

Б.

Д.

И.

Н.

Я.

А.

С.

У.

С.

А.

И.

Р.

Б.

Я.

И.

У.

Н.

О.

А.

С.

И.

Р.

Б.

Я.

И.

У.

Н.

И.

С.

Р.

Я.

И.

Б.

А.

Р.

С.

У.

Б.

Я.

И.

У.

Н.

И.

С.

Р.

А.

И.

С.

У.

Б.

Р.

Я.

Д.

С.

У.

Б.

Р.

У.

И.

А.

О.

А.

С.

И.

Р.

Б.

Я.

И.

Д.

Я.

О.

Р.

И.

Р.

Н.

С.

А.

И.

Р.

Б.

Я.

И.

У.

Н.

Б.

Я.

И.

У.

Н.

И.

С.

Р.

О.

Р.

Д.

С.

Я.

И.

Р.

Н.

Б.

У.

С.

А.

И.

С.

У.

Д.

И.

Я.

Б.

У.

Б.

Д.

И.

Н.

Я.

О.

Р.

Д.

С.

Я.

И.

О.

У.

Р.

Н.

С.

У.

Б.

Р.

Д.

С.

Я.

И.

Р.

Н.

Б.

О.

А.

С.

И.

А.

С.

У.

С.

А.

И.

С.

У.

С.

А.

И.

Я.

Б.

Р.

У.

И.

А.

О.

С.

И.

Р.

Б.

Я.

И.

У.

Н.

И.

О.

Д.

И.

Н.

Я.

О.

Р.

Д.

С.

Я.

И.

Р.

Н.

Б.

Д.

С.

Я.

И.

Р.

Н.

Б.

У.

А.

Р.

С.

У.

Д.

Н.

Я.

Б.

С.

У.

С.

А.

И.

С.

У.

Б.

Р.

Я.

А.

Р.

С.

У.

Д.

Н.

Я.

Б.

С.

У.

О.

Д.

Я.

Б.

Р.

У.

И.

А.

Д.

И.

Я.

Б.

Р.

У.

И.

А.

О.

А.

С.

У.

С.

А.

И.

С.

У.

О.

Д.

А.

С.

О.

У.

Р.

Н.

С.

У.

Б.

Д.

И.

Н.

Я.

О.

Р.

Н.

С.

У.

Б.

Д.

И.

Н.

Я.

О.

Р.

Д.

С.

Я.

И.

Р.

Н.

Б.

У.

Б.

Я.

И.

У.

Н.

Б.

Я.

И.

У.

Н.

С.

А.

И.

Р.

Б.

Я.

И.

У.

Д.

С.

Р.

У.

А.

О.

И.

Н.

Р.

Д.

Я.

О.

Р.

И.

Р.

Н.

Б.

У.

С.

А.

Д.

И.

Я.

Б.

Р.

У.

И.

А.

О.

А.

С.

И.

Р.

Б.

Я.

И.

У.

Н.

И.

Б.

О.

Р.

Д.

С.

Я.

И.

Р.

Н.

Б.

У.

С.

А.

И.

С.

У.

Б.

Н.

У.

Я.

И.

Б.

А.

Р.

С.

У.

Д.

Н.

Я.

Б.

С.

У.

О.

Д.

А.

С.

Д.

С.

Р.

У.

А.

О.

И.

Н.

Р.

Д.

Я.

О.

Р.

Н.

С.

У.

Б.

Д.

И.

Итерация 1.

1. В соответствии с этапами 1−3 алгоритма определим количество агентовразведчиков n_r=10 и разместим их случайным образом в пространстве поиска, то есть выберем произвольным образом n_r символов в матрице А. Пусть это будут символы С (16,1), Р (9,8), Ц (5,11), Д (10,15), Б (13,12), И (14,18), О (7,18), Р (16,21), С (8,23), У (21,24), выделенные в табл. 2 жирным курсивом. Положим значение ЦФ R для всех позиций равным малому положительному числу R=0.001. Определим размер популяции пчел М=10.
2. В соответствии с шагом 4 алгоритма определим множество базовых решений n_b=6 и соответствующие базовые позиции с лучшими значениями ЦФ (на этом этапе, как и в [8], их выберем произвольно). Пусть это будут позиции А_b={С (16,1), Ц (5,11), И (14,18), Д (10,15), Р (16,21), Б (13,12)}.
3. В соответствие с этапами 5−9 алгоритма определим количество агентов-фуражиров n_f=8, размер максимальной окрестности л_макс=20. Пусть базовые позиции выбираются восемью агентами-фуражирами в следующем порядке а₁=Ц (5,11), а₂=И (14,18), а₃=С (16,1), а₄=И (14,18), а₅=С (16,1), а₆=Д (10,15), а₇=Б (13,12), а₈=Р (16,21). Пусть базовым позициям ставятся в соответствие следующие позиции а_s: Ц (5,11)>У (4,11); И (14,18)>И (12,16); С (16,1)>У (13,3); И (14,18)>C (14,16); С (16,1)>Я (16,7); Д (10,15)>И (10,12); Б (13,12)>Д (13,10); Р (16,21)>О (17,18).

Таким образом, в соответствии с шагом 8 будем иметь перечень позиций, списков и значений функции R, определенных в соответствии с табл. 1. Для позиций Ц (5,11), И (14,18), С (16,1), Д (10,15), Б (13,12), Р (16,21) R=0,001, списки Е₁-Е₆ состоят из одного символа, R=0.001. Для позиций: У (4,11) Е₇={ЦУ}, R=0.2; И (12,16) Е₈={ИИ}, R=0.8; У (13,3) Е₉={СУ}, R=0.6; С (14,16) Е₁₀={ИС}, R=0.8; Я (16,7) Е₁₁={СЯ}, R=0.1; И (10,12) Е₁₂={ДИ}, R=0.8; Д (13,10) Е₁₃={БД}, R=0.1; О (17,18) Е₁₄={РО}, R=0.9.

4. В соответствии с шагом 10 алгоритма проведем операцию универсального кроссинговера для списков Е₇ -Е₁₄, выбрав норму 75%. Пусть для получения 6 потомков Е₁₅ -Е₂₀ выбраны списки Е₇-Е₁₀, Е₁₃-Е₁₄, Е₁₀-Е₁₁, и сформированы следующие маски: 10; 01; 01. В этом случае получим следующих потомков: Е₁₅={ИУ}, R=0.1; Е₁₆={ЦС}, R=0.1; Е₁₇={БО}, R=0.8; Е₁₈={РД}, R=0.3; Е₁₉={ИЯ}, R=0.5; Е₂₀={СС}, R=0.1.
5. В соответствии с шагом 11 алгоритма проведем операцию точечной мутации. Будем предполагать далее, что мутация проводится путем случайного выбора хромосом популяции, случайного выбора количества генов и произвольной замены значений выбранных генов на допустимые из произвольно выбранных позиций. Пусть после выбора хромосомы (списка) Е₁₃ меняется значение гена Б на Р (16,21), после выбора хромосомы Е₁₅ меняется значение У на Н (11,17), после выбора хромосомы Е₁₆ меняется значение гена С на А (4,8). В этом случае потомки будут иметь вид: Е₁₃={РД (13,10)}, R=0,3; Е₁₅={ИН (11,17)}, R=0,8; Е₁₆={ЦА (4,8)}, R=0,4.

Таким образом, на итерации 1 мы будем иметь следующий перечень списков (хромосом), координат и значений функции R:

{Ц (5,11)}, {И (14,18)}, {C (16,1)}, {Д (10,15)}, {Б (13,12)}, {P (16,21)}, R=0.001; {ЦУ (4,11)}, R=0.2; {ЦА (4,8)}, R=0.4; {ИИ (12,16)}, R=0.8; {ИС (14,16)}, R=0.8; {ИН (11,17)}, R=0.8; {ИЯ (16,7)}, R=0.5; {СУ (13,3)}, R=0.6; {СЯ (16,7)}, R=0.1 {СС (14,16)}, R=0.1; {ДИ (10,12)}, R=0.8; {БО (17,18)}, R=0.8; {РО (17,18)}, R=0.9; РД (13,10)}, R=0.3; {РД (13,10)}, R=0,3.

6. Проводя в соответствии с шагом 13 элитную селекцию, удалим индивидуумы популяции с наименьшим значением R до сокращения размера популяции до размера М=10. Это индивидуумы {Ц (5,11)}, {И (14,18)}, {C (16,1)}, {Д (10,15)}, {Б (13,12)}, {P (16,21)}, {СС (14,16)}, {СЯ (16,7)}, {ЦУ (4,11)}, РД{(13,10)}.

7. Выбирая среди всех значений R_i лучшее значение, получим, что R^*=0,9; E^*={РО}.
8. Полагаем l=2.

Итерация 2.

1. В соответствии с шагом 17 алгоритма определим число n_b1= 3; включим во множество А_b1 позиции А_b1={РО (17,18), R=0.9; ИН (11,17), R=0.8; ДИ (10,12), R=0.8}.
2. В соответствии с шагом 18 определим количество агентов-разведчиков n_rl=6 и разместим их произвольным образом в пространстве поиска. Пусть произвольным образом выбираются символы СУ (13,3), РД (13,10), Н (19,7), А (10,4), Ц (17,3), И (9,4).
3. В соответствии с шагом 19 включим во множество А_b2 n_b2=3 позиции из множества n_rl=6 позиций, найденных агентамиразведчиками на итерации 2. Пусть это будут позиции А_b2={СУ (13,3), R=0.6; РД (13,10), R=0.3; A (10,4), R=0.001}.
4. Таким образом, на итерации l=2 n_b1+ n_b2=6 и множество базовых позиций А_b={РО (17,18), ИН (11,17), ДИ (10,12), СУ (13,3), РД (13,10), A (10,4)}. Пространство поиска показано в табл. 3, базовые позиции отмечены прямым жирным шрифтом.
5. В соответствие с этапами 5−9 алгоритма определим количество агентов-фуражиров n_f=8, размер максимальной окрестности л_макс=20. Пусть базовые позиции выбираются в следующем порядке:

а₁=РО (17,18), а₂=А (10,4), а₃=ИН (11,17), а₄=А (10,4), а₅=РД (13,10), а₆=РД (13,10), а₇=СУ (13,3), а₈=ДИ (10,12).

Пусть базовым позициям ставятся в соответствие следующие позиции а_s: РО (17,18)>Ц (19,16); А (10,4)>Ц (8,5); ИН (11,17)>ИИ (12,16); А (10,4)>Ц (4,4); РД (13,10)>ИЯ (16,7); РД (13,10)>ИИ (12,16); СУ (13,3)>БО (17,18); ДИ (10,12)>ЦА (4,8).

Таким образом, на данном шаге мы будем иметь следующий список позиций, решений и соответствующих значений функции R.

Таблица 3. Пространство поиска для комбинированного алгоритма после 1 итерации.

И.

Р.

Б.

Я.

И.

У.

Н.

И.

С.

Р.

О.

А.

С.

И.

Р.

Б.

Я.

Б.

Р.

У.

Д.

И.

Н.

Я.

О.

Р.

Д.

С.

Я.

И.

Р.

Н.

Б.

О.

А.

С.

И.

Р.

Б.

Я.

И.

Р.

Д.

С.

Я.

И.

Р.

Н.

Б.

У.

С.

А.

И.

Я.

Б.

Р.

У.

И.

А.

О.

А.

Б.

Д.

И.

Н.

Я.

А.

С.

У.

С.

А.

И.

Р.

Б.

Я.

И.

У.

Н.

О.

А.

С.

И.

Р.

Б.

Я.

И.

У.

Н.

И.

С.

Р.

Я.

И.

Б.

А.

Р.

С.

У.

Б.

Я.

И.

У.

Н.

И.

С.

Р.

А.

И.

С.

У.

Б.

Р.

Я.

Д.

С.

У.

Б.

Р.

У.

И.

А.

О.

А.

С.

И.

Р.

Б.

Я.

И.

Д.

Я.

РО БО.

Р.

И.

Р.

Н.

С.

А.

И.

Р.

Б.

Я.

И.

У.

ИН.

Б.

Я.

И.

У.

Н.

И.

С.

Р.

О.

Р.

Д.

С.

Я.

И.

Р.

Н.

Б.

У.

С.

А.

ИИ.

ИС.

У.

Д.

И.

Я.

Б.

У.

Б.

Д.

И.

Н.

Я.

О.

Р.

Д.

С.

Я.

И.

О.

У.

Р.

Н.

С.

У.

Б.

Р.

Д.

С.

Я.

И.

Р.

Н.

Б.

О.

А.

С.

И.

А.

С.

У.

С.

А.

И.

С.

У.

С.

А.

И.

Я.

Б.

Р.

У.

И.

А.

О.

С.

И.

Р.

Б.

Я.

И.

У.

Н.

И.

О.

Д.

И.

Н.

Я.

О.

Р.

Д.

С.

Я.

ДИ.

Р.

Н.

Б.

Д.

С.

Я.

И.

Р.

Н.

Б.

У.

А.

Р.

С.

У.

Д.

Н.

Я.

Б.

С.

У.

С.

А.

И.

С.

У.

Б.

Р.

Я.

А.

Р.

С.

У.

Д.

Н.

Я.

Б.

С.

У.

О.

РД.

Я.

Б.

Р.

У.

И.

А.

Д.

И.

Я.

Б.

Р.

У.

И.

А.

О.

А.

С.

У.

С.

А.

И.

С.

У.

О.

Д.

ЦА.

С.

О.

У.

Р.

Н.

С.

У.

Б.

Д.

И.

Н.

Я.

О.

Р.

Н.

С.

У.

Б.

Д.

И.

Н.

Я.

О.

Р.

Д.

С.

ИЯ.

И.

Р.

Н.

Б.

У.

Б.

Я.

И.

У.

Н.

Б.

Я.

И.

У.

Н.

С.

А.

И.

Р.

Б.

Я.

И.

У.

Д.

С.

Р.

У.

А.

О.

И.

Н.

Р.

Д.

Я.

О.

Р.

И.

Р.

Н.

Б.

У.

С.

А.

Д.

И.

Я.

Б.

Р.

У.

И.

А.

О.

А.

С.

И.

Р.

Б.

Я.

И.

У.

Н.

И.

Б.

О.

Р.

Д.

С.

Я.

И.

Р.

Н.

Б.

СУ.

С.

А.

И.

С.

У.

Б.

Н.

У.

Я.

И.

Б.

А.

Р.

С.

У.

Д.

Н.

Я.

Б.

С.

У.

О.

Д.

А.

С.

Д.

С.

Р.

У.

А.

О.

И.

Н.

Р.

Д.

Я.

О.

Р.

Н.

С.

У.

Б.

Д.

И.

О (17,18), Е₁={CУБО}, R=1.8; А (10,4), Е₂={А}, R=0.001; Н (11,17), Е₃={ИН}, R=0.8; Д (13,10), Е₄={РД}, R=0.3; У (13,3), Е₅={СУ}, R=0.6; И (10,12), Е₆={ДИ}, R=0.8; Ц (19,16), Е₇={РОЦ}, R=1; Ц (8,5), Е₈={АЦ}, R=0.4; И (12,16), Е₉={ИНИИ}, R=2.4; Ц (4,4), Е₁₀={АЦ}, R=0.4; Я (16,7), Е₁₁={РДИЯ}, R=1.6; И (12,16), Е₁₂={РДИИ}, R=1.9; А (4,8), Е₁₃={ДИЦА}, R=1.3; О (17,18), Е₁₄={РО}, R=0.9.

6. В соответствии с шагом 10 алгоритма проведем операцию универсального кроссинговера по норме 75%, при этом для получения 9 потомков Е₁₅-Е₂₃ выбраны следующие списки: Е₉-Е₁₀ (с позиции 3, потомки Е₁₅, Е₁₆), Е₈ -Е₁₂ (с позиции 2, потомки Е₁₇, Е₁₈), Е₃-Е₁₁ (с позиции 3, потомки Е₁₉, Е₂₀), Е₁₀-Е₁₁ (с позиции 1, потомки Е₂₁, Е₂₂), Е₄-Е₆ (потомок Е₂₃). Пусть сформированы следующие маски: 00, 01, 10, 11, 01. В этом случае получим потомков: Е₁₅={ИНИИ}, R=2.4, Е₁₆={ИНАЦ}, R=2.1, Е₁₇={РАИИ}, R=2.4, Е₁₈={РДЦИ}, R=0.9, Е₁₉={РДИН}, R=1.9, Е₂₀={РДИЯ}, R=1.6, Е₂₁={РДИЯ}, R=1.6, Е₂₂={АЦИЯ}, R=1.4, Е₂₃={РИ}, R=0.7.
7. В соответствии с шагом 11 алгоритма проведем операцию точечной мутации. Пусть после выбора списка Е₁₁ в нем меняется ген Я на Н (11,17), после выбора списка Е₁₅ ген Н меняется на Ц, после выбора списка Е₁₇ ген, А меняется на Я, в списке Е₂₃ ген И меняется на Д (13,10). В этом случае получим потомков: Е₁₁={РДИН}, R=1.9, Е₁₅={ИЦИИ}, R=1.4, Е₁₇={РЯИИ}, R=1.1, Е₂₃={РД}, R=0.3.
8. Таким образом, на итерации 2 мы будем иметь следующий перечень списков (хромосом), координат и значений функции R.

{CУБО (17,18)}, R₁=1.8; {А (10,4)}, R₂=0.001; {ИН (11,17)}, R₃=0.8; {РД (13,10)}, R₄=0.3; {СУ (13,3)}, R₅=0.6; {ДИ (10,12)}, R₆=0.8; {РОЦ (19,16)}, R₇=1; {АЦ (8,5)}, R₈=0.4; {ИНИИ (12,16)}, R₉=2.4; {АЦ (4,4)}, R₁₀=0.4; {РДИН (11,17)}, R₁₁=1.9; {РДИИ (12,16)}, R₁₂=1.9; {ДИЦА (4,8)}, R₁₃=1.3; {РО (17,18)}, R₁₄=0.9; {ИЦИИ (12,16)}, R₁₅=1.4; {ИНАЦ (4,4)}, R₁₆=2.1; {РЯИИ (12,16)}, R₁₇=2.4; {РДЦИ (12,16)}, R₁₈=0.9; {РДИН (11,17)}, R₁₉=1.9; {РДИЯ (16,7)}, R₂₀=1.6; {РДИЯ (16,7)}, R₂₁=1.6; {АЦИЯ (16,7)}, R₂₂=1.4; {РД (13,10)}, R₂₃=0.3.

Для списков, состоящих из 3 и более символов, применим весовой коэффициент Q. Определим для списка Е₁ Q=1 и R₁=1.8; для списка Е₇ Q=0.8 и R₇=0.8; для списка Е₉ Q=0.6 и R₉=1.44; для списка Е₁₁ Q=1 и R₁₁=1.9; для списка Е₁₂ Q=0.7 и R₁₂=1.33; для списка Е₁₃ Q=0.7, R₁₃=0.91; для списка Е₁₅ Q=0.9, R₁₅=1.26; для списка Е₁₆ Q=0.8, R₁₆=1.68; для списка Е₁₇ Q=0.5, R₁₇=1.2; для списка Е₁₈ Q=0.4, R₁₈=0.36; для списка Е₁₉ Q=1, R₁₉=1.9; для списка Е₂₀ Q=0.85, R₂₀=1.36; для списка Е₂₁ Q=0.85, R₂₁=1.36; для списка Е₂₂ Q=1, R₂₂=1.4.

В этом случае перечень списков будет следующий:

{CУБО (17,18)}, R₁=1.8; {А (10,4)}, R₂=0.001; {ИН (11,17)}, R₃=0.8; {РД (13,10)}, R₄=0.3; {СУ (13,3)}, R₅=0.6; {ДИ (10,12)}, R₆=0.8; {РОЦ (19,16)}, R₇=0.8; {АЦ (8,5)}, R₈=0.4; {ИНИИ (12,16)}, R₉=1.44; {АЦ (4,4)}, R₁₀=0.4; {РДИН (11,17)}, R₁₁=1.9; {РДИИ (12,16)}, R₁₂=1.33; {ДИЦА (4,8)}, R₁₃=0.91; {PO (17,18), R₁₄=0.9}; {ИЦИИ (12,16)}, R₁₅=1.26; {ИНАЦ (4,4)}, R₁₆=1.68; {РЯИИ (12,16)}, R₁₇=1.2; {РДЦИ (12,16)}, R₁₈=0.36; {РДИН (11,17)}, R₁₉=1.9; {РДИЯ (16,7)}, R₂₀=1.36; {РДИЯ (16,7)}, R₂₁=1.36; {АЦИЯ (16,7)}, R₂₂</…

Ранее в [25] было показано, что при использовании комбинированных биоинспирированных алгоритмов вероятность улучшения частичного решения на каждой итерации не может быть меньше вероятности улучшения частичного решения при использовании каждого классического биоинспирированного алгоритма. Отметим здесь еще раз этот существенный момент. Пусть — группа операторов комбинированного алгоритма, соответствующая операторам алгоритма пчелиных колоний (операторы 1−9, 17−21), — группа операторов, соответствующая операторам генетического алгоритма (операторы 10−16). Пусть — вероятность того, что при реализации пчелиного алгоритма на итерации получено решение, лучшее, чем на итерации. Аналогично, пусть — вероятность того, что реализации генетического алгоритма на итерации получено решение, лучшее, чем на итерации. Поскольку эти события совместны (улучшение частичного решения может иметь место одновременно при реализации обоих групп операторов), то, используя аппарат теории вероятностей, получим, что при реализации комбинированного алгоритма вероятность получения на итерации частичного решения, лучшего, чем на итерации, составит. Поскольку все значения удовлетворяют условию, , то, очевидно, произведение будет удовлетворять условию. В то же время имеет место очевидное соотношение. Отсюда следует, что будет иметь место соотношение .

Таким образом, мы еще раз показали (аналогично [25]) применительно к комбинированному алгоритму пчелиных колоний), что при реализации комбинированного биоинспирированного алгоритма вероятность улучшения частичного решения на итерации по сравнению с итерацией удовлетворяет условию, где — вероятности улучшения частичного решения при использовании классических биоинспирированных алгоритмов. При этом увеличение вероятности может быть определено из соотношения. Данные расчеты показывают, что при использовании комбинированных биоинспирированных алгоритмов вероятность улучшения частичного решения на каждой итерации не может быть меньше вероятности улучшения частичного решения при использовании каждого классического биоинспирированного алгоритма, что подтверждает целесообразность разработки и использования комбинированных биоинспирированных стратегий и их применения для решения оптимизационных однои многоэкстремальных задач. Очевидно, что данные рассуждения справедливы для любого числа биоинспирированных алгоритмов и вероятностей .

Показать весь текст

Заполнить форму текущей работой