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



Download 2,21 Mb.
Pdf ko'rish
bet14/38
Sana24.02.2022
Hajmi2,21 Mb.
#242470
TuriРеферат
1   ...   10   11   12   13   14   15   16   17   ...   38
Bog'liq
programm

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]. 

Download 2,21 Mb.

Do'stlaringiz bilan baham:
1   ...   10   11   12   13   14   15   16   17   ...   38




Ma'lumotlar bazasi mualliflik huquqi bilan himoyalangan ©hozir.org 2024
ma'muriyatiga murojaat qiling

kiriting | ro'yxatdan o'tish
    Bosh sahifa
юртда тантана
Боғда битган
Бугун юртда
Эшитганлар жилманглар
Эшитмадим деманглар
битган бодомлар
Yangiariq tumani
qitish marakazi
Raqamli texnologiyalar
ilishida muhokamadan
tasdiqqa tavsiya
tavsiya etilgan
iqtisodiyot kafedrasi
steiermarkischen landesregierung
asarlaringizni yuboring
o'zingizning asarlaringizni
Iltimos faqat
faqat o'zingizning
steierm rkischen
landesregierung fachabteilung
rkischen landesregierung
hamshira loyihasi
loyihasi mavsum
faolyatining oqibatlari
asosiy adabiyotlar
fakulteti ahborot
ahborot havfsizligi
havfsizligi kafedrasi
fanidan bo’yicha
fakulteti iqtisodiyot
boshqaruv fakulteti
chiqarishda boshqaruv
ishlab chiqarishda
iqtisodiyot fakultet
multiservis tarmoqlari
fanidan asosiy
Uzbek fanidan
mavzulari potok
asosidagi multiservis
'aliyyil a'ziym
billahil 'aliyyil
illaa billahil
quvvata illaa
falah' deganida
Kompyuter savodxonligi
bo’yicha mustaqil
'alal falah'
Hayya 'alal
'alas soloh
Hayya 'alas
mavsum boyicha


yuklab olish