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