УДК 004.272.2
УСКОРЕНИЕ ГЕНЕТИЧЕСКОГО АЛГОРИТМА РЕШЕНИЯ ТРАНСПОРТНОЙ ЗАДАЧИ СРЕДСТВАМИ МНОГОПОТОЧНОГО ПРОГРАММИРОВАНИЯ
С. В. Скворцов, д.т.н., профессор РГРТУ, Рязань, Россия;
orcid.org/0000-0001-9495-4953, e-mail: Этот адрес электронной почты защищён от спам-ботов. У вас должен быть включен JavaScript для просмотра.
М. С. Дьяков, магистрант РГРТУ, Рязань, Россия;
orcid.org/0000-0001-7809-0294, e-mail: Этот адрес электронной почты защищён от спам-ботов. У вас должен быть включен JavaScript для просмотра.
Рассматривается применение генетического алгоритма для решения транспортной задачи по критерию стоимости. Целью работы является организация параллельных вычислений при реализации основных генетических операторов, направленная на ускорение работы генетического алгоритма. Представлены возможные подходы к реализации многопоточных приложений для решения транспортной задачи на основе генетического алгоритма с использованием современных технологий программирования. Выполнен вычислительный эксперимент по оценке ускорения генетического алгоритма при обработке больших популяций средствами технологий многопоточного программирования CUDA и OpenMP. Исследованы особенности архитектуры операционной системы Linux, связанные с буферизацией данных при обращении к памяти ЭВМ, использование которых также позволяет повысить эффективность генетического алгоритма при обработке больших популяций особей. Получены экспериментальные оценки ускорения многопоточного приложения на основе технологии OpenMP, достигаемые при программном отключении буферизации данных.
Ключевые слова: транспортная задача, генетический алгоритм, селекция, скрещивание, мутация, последовательный алгоритм, многопоточный алгоритм, графический процессор.