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

Анализ
Первый цикл алгоритма устанавливает начальные значения. Его 
выполнение требует 
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).