Генетические алгоритмы могут быть распараллелены, по меньшей мере, двумя способами.
Первый способ относится к параллельному выполнению операций внутреннего цикла базового ГА. Очевидно, что в этом случае имитируется эволюция одной и той же популяции хромосом. Реализация алгоритма целесообразна на компьютере с числом процессоров, не меньшем размера популяции Npop.
Второй способ заключается в имитации эволюции нескольких популяций, периодически обменивающихся между собой частью своих генотипов. Разновидности этого способа определяются расписанием межпопуляционных обменов. В расписании должны быть указаны следующие сведения: а) период автономной эволюции, измеряемый числом смен поколений в популяциях между обменами; б) матрица B обменов, элемент bij которой равен 1, если генный материал передается от популяции i к популяции j, иначе bij=0 ; в) содержание обменов, т.е. список хромосом, передаваемых при обмене от популяции i к популяции j. Например, возможен круговой обмен (bij=1, только если j=i+1, за исключением популяции с максимальным номером j, для которой b1j=1). Генетический алгоритм с межпопуляционными обменами по второму способу находит применение и на однопроцессорных компьютерах.
Если популяции обмениваются своими лучшими представителями, то обычно после нескольких обменов во всех популяциях начинают доминировать генотипы лучшего из поколений, т.е. происходит выравнивание качества генофонда во всех популяциях на уровне лучшей из популяций. Другими словами, результаты применения параллельного ГА приблизительно совпадают с результатами выполнения нескольких попыток решения задачи обычным (непараллельным) способом, но получаются они, конечно, с меньшими временными затратами.
Гибридным алгоритмом оптимизации называют алгоритм, в котором для поиска экстремума используются идеи двух или более методов оптимизации. Типичным примером гибридного алгоритма является генетический алгоритм с улучшением каждого генерируемого потомка с помощью метода локального поиска. Локальный поиск выполняется посредством макромутаций. Размер макромутаций, т.е. число мутируемых генов, определяет окрестность текущей точки поиска, в которой ищется лучшая точка. Число безуспешных попыток найти такую точку ограничено величиной k. Если найдена точка с лучшим значением функции полезности, то происходит переход в эту точку и вновь допускается поиск с числом попыток, равным k.
Как показали результаты экспериментов, гибридный алгоритмы не имеют заметных преимуществ по точности получаемых решений перед негибридными ГА, в то же время затраты времени на решение могут существенно возрасти.