Учебное пособие москва мади 2020 ббк 32. 81 В 683 Волосова, А. В. В683


Анализ Первый цикл алгоритма устанавливает начальные значения. Его  выполнение требует  N / p



Download 5,19 Mb.
Pdf ko'rish
bet62/101
Sana16.10.2022
Hajmi5,19 Mb.
#853454
TuriУчебное пособие
1   ...   58   59   60   61   62   63   64   65   ...   101
Bog'liq
fel20E533

Анализ
Первый цикл алгоритма устанавливает начальные значения. Его 
выполнение требует 
N / p
шагов, поскольку количество начальных значений, 
устанавливаемых каждым процессором, пропорционально числу вершин, за 
которые он отвечает. Первый параллельный блок в главном цикле for всякий 
раз выполняет 
N / p ­ 1
сравнений, ровно столько сравнений требует 
последовательный алгоритм поиска максимума или минимума. Следующий 
шаг состоит в том, чтобы выбрать минимальное расстояние из всех 
сообщенных р процессорами, на что уходит еще р ­ 1 сравнений. Шаг 
распределения значений в модели CREW занимает, как было показано, два 
цикла. В последнем параллельном блоке одно сравнение уходит на то, чтобы 
проверить, отвечает ли данный процессор за вновь добавленный узел, а 
исправление массивов closest и distance требует 
N / p
операций. Итак, при 
одном проходе главного цикла обработки
выполняется 
2(N / p) + p + 1
операций, а число проходов равно 
N ­ 1
. Поэтому общее число операций в 
главном цикле 
(N ­ 1) * (2 * (N/p) + р + 1)
, а общая сложность алгоритма 
равна 
O(N
2
/p)
при стоимости 
р * O(N
2
/p)
, или 
O(N
2
)
. Как мы уже видели в 
других случаях, оптимальность достигается при числе процессоров около 
N / 
log N. 
11.3. Генетические параллельные алгоритмы
Механизм наследственности в биологических популяциях впервые 
был использован Джоном Холландом для решения задач оптимизации. Он 
был назван репродуктивным планом Холланда. Свое название ­ 
генетические алгоритмы, получили в работах Гольдберга и Де Йонга.


107 
Цель генетического алгоритма при решении задачи оптимизации 
состоит в том, чтобы найти лучшее возможное, но не гарантированно 
оптимальное решение. Для реализации генетического алгоритма необходимо 
выбрать подходящую структуру данных для представления решений. В 
постановке задачи поиска оптимума, экземпляр этой структуры должен 
содержать информацию о некоторой точке в пространстве решений. 
Структура данных генетического алгоритма состоит из набора хромосом. 
Хромосома, как правило, представляет собой битовую строку. Хромосомы 
также могут быть реализованы как векторы вещественных чисел. В 
настоящее время используются структуры фиксированной длины - битовые 
строки. Каждая хромосома (строка) представляет собой последовательное 
объединение ряда подкомпонентов, которые называются генами. Гены 
находятся в локусах хромосомы. Их значения называются алелями. В 
представлении хромосомы бинарной строкой, ген является битом этой 
строки, локус ­ есть позиция бита в строке, а аллель ­ это значение гена, 0 или 
1. Биологический термин «генотип» ставится в соответствие полной
генетической модели особи. Генотип соответствует структуре в генетическом 
алгоритме.
Термин «фенотип» соответствует вектору в пространстве параметров 
задачи. Фенотип относится к внешним наблюдаемым признакам и В генетике 
под мутацией понимается преобразование хромосомы, случайно изменяющее 
один или несколько генов. Часто встречается следующий вид мутаций ­ 
случайное изменение только одного из генов хромосомы. Термин 
кроссинговер обозначает порождение из двух хромосом двух новых путем 
обмена генами. В литературе по генетическим алгоритмам также 
употребляется термин кроссовер, скрещивание или рекомбинация. В 
простейшем случае кроссинговер в генетическом алгоритме реализуется так 
же, как и в биологии. При скрещивании происходит разрезание хромосом в 
случайной точке и их обмен частями между собой. В частности, если 
хромосомы (11, 12, 13, 14) и (0, 0, 0, 0) разрезать между вторым и третьим 


108 
генами и обменять их части, то получатся следующие потомки (11, 12, 0, 0) и 
(0, 0, 13, 14).

Download 5,19 Mb.

Do'stlaringiz bilan baham:
1   ...   58   59   60   61   62   63   64   65   ...   101




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