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

2.2 Муравьиный алгоритм 
Работа муравьиных алгоритмов основана на особенности поведения 
муравьев в природе и их способности быстро находить кратчайший путь от 
муравейника к источнику пищи, а также адаптироваться к изменяющимся 
условиям [6]. При поиске пути к источнику пищи муравьи отмечают 
пройденный путь феромоном. Другие муравьи с большей вероятностью 
начинают двигаться по пути, наиболее обогащённому феромоном. И чем 
больше муравьев пройдет выбранным путем, тем более предпочтительным 
станет этот путь для других муравьев. Решением задачи станет путь, наиболее 
обогащенный феромоном. 
При рассмотрении бинарных ключей пути муравьев можно представить в 
виде графа, рёбра которого представляют собой возможные пути перемещения 
муравьев, а вершинами являются значения отдельных битов (см. рис. 2.1). 
Рисунок 2.1 - Граф бинарной области поиска при криптоанализе 
муравьиным алгоритмом 

---

40 
В общем случае алгоритм можно представить по шагам так:
1. Начальное распределение феромонов.
2. Поиск оптимального пути. Вероятность перехода муравья из 
вершины i в вершину j определяется соотношением [20] 
𝑃
𝑖𝑗,𝑘
(𝑡) =
[𝜏
𝑖𝑗
(𝑡)]
𝛼
∗[𝜂
𝑖𝑗
(𝑡)]
𝛽
∑
[𝜏
𝑖𝑙
(𝑡)]
𝛼
∗[𝜂
𝑖𝑙
(𝑡)]
𝛽
𝑙∈𝐽𝑖,𝑘
, 𝑗 ∈ 𝐽
𝑖,𝑘
, 
(2-2) 
где
k - муравей 
i, j — вершины графа 
t – итерация 
Ji,k –вершины графа 
Pij — вероятность перехода муравья из вершины i в вершину j 
𝜏
𝑖𝑗
- величина феромона (вес ребра) для перехода из вершины i в 
вершину j
𝜂
𝑖𝑗
- величина, обратно пропорциональная длине ребра: 
𝜂
𝑖𝑗
= 1 𝐷
𝑖𝑗
⁄
.
(2-3) 
Dij — длина ребра 
𝛼, 𝛽 
– 
эмпирические 
коэффициенты, 
которые 
управляют 
соотношением предпочтительности между информацией о феромоне 
𝜏
𝑖𝑗
и величине, обратно пропорциональной длине ребра
3. Оценка эффективности пути исходя из значения фитнесс-функции. 
4. Обновление феромона 
∆𝜏
𝑖𝑗,𝑘
=
𝑄
𝐿
𝑘
, (𝑖, 𝑗) ∈ 𝑇
𝑘
(2-4) 
где 
𝜂
𝑖𝑗
- величина изменения феромона 
Tk - маршрут 
𝑄 – параметр, значение которого выбирают одного порядка с длиной 
оптимального маршрута;

---

41 
𝐿
𝑘
(𝑡) – длина маршрута 𝑇
𝑘
. 
5.Испарение феромона 
𝜏
𝑖𝑗
(𝑡 + 1) = (1 − 𝑝) ∗ (𝜏
𝑖𝑗
(𝑡) + ∑
𝛥𝜏
𝑖𝑗,𝑘
𝑚
𝑘=1
), 
(2-5) 
где
𝑚 – количество муравьев. Количество муравьев влияет на 
сходимость: если оно достаточно велико, то происходит быстрое 
усиление некоторых маршрутов, если мало, то в процессе 
выполнения алгоритма некоторые маршруты теряются из-за быстрого 
испарения феромона; 
𝑝 – коэффициент испарения (0 ≤ p ≤ 1).
В качестве фитнесс-функции может использоваться количество 
отличающихся бит в оригинальном зашифрованном тексте и в тексте, 
зашифрованном тестируемым ключом. В случае 64-битной бинарной строке 
фитнесс-функция определяется следующим выражением 
Fitness = SumEqual / BlockLength
(2-6) 
где SumEqual — количество одинаковых бит на одинаковых позициях в 
оригинальном зашифрованном тексте и в тексте, зашифрованном тестируемым 
ключом 
BlockLength – размер блока шифрования.
Способ выбора фитнесс-функции зависит от решаемой задачи [5]. 
Также возможен выбор варианта распределения феромонов [4].