Дрепин А.С., Захаров Д.О.
РЕШЕНИЕ NP-ПОЛНЫХ ЗАДАЧ С ПОМОЩЬЮ ГЕНЕТИЧЕСКИХ АЛГОРИТМОВ С ИСПОЛЬЗОВАНИЕМ ПАРАЛЛЕЛИЗМА *
Аннотация:
в данной статье будет рассмотрена модель решения NP-полных задач с помощью генетических алгоритмов, возможность распараллеливания данных алгоритмов, будет поставлена задача для разработки программного средства, реализующего данный метод
Ключевые слова:
эвристический метод, генетический алгоритм, NP-полная задача, задача коммивояжера, минимаксная задача, параллелизм
Современные задачи требуют наиболее быстрого и эффективного решения. Многие из этих задач являются NP-полными, то есть, нет возможности получить оптимальное решение за полиномиальное время. Для решения данных задач используют различные эвристические алгоритмы, в том числе и генетические. Задача называется NP-полной, если она входит в NP и каждая задача из NP полиномиально сводится к ней (т.е. является NP-трудной). NP-полные задачи понимаются как самые трудные задачи из класса NP. В данной статье будет рассмотрена неоднородная минимаксная задача и задача Коммивояжёра. Так как не существует алгоритмов, позволяющих решить данные задачи за полиномиальное время, для их решения будет применён генетический алгоритм. Также, для оптимизации времени выполнения вычислений, задачи должны решаться с использованием параллелизма. Постановка задачи неоднородной минимаксной задачи заключается в том, что в систему, состоящую из нескольких несвязных устройств, поступает несколько задач. Время решения каждой задачи на разных устройствах отличается. В каждый момент времени отдельное устройство обслуживает не более одной задачи. Требуется найти решение, не допускающее больших отклонений в нагрузке на устройства. Задача Коммивояжера является одной из наиболее популярных комбинаторных задач. Изначальная формулировка звучала следующим образом «Каков кратчайший путь между конечным множеством мест, расстояние между которыми известно?». Несмотря на простоту формулировки, с ростом числа элементов задачи сложность также будет возрастать экспоненциально. Так как при решении задачи будет обрабатываться большое число объектов, было принято решение разделить нагрузку между вычислительными устройствами для оптимизации времени решения. В данном случае, будет проанализировано количество доступных вычислительных устройств, каждому из которых будет назначена работа над решением конкретной части рассматриваемой задачи. Генетический алгоритм - это эвристический алгоритм поиска, который используется для решения задач оптимизации и основывается на понятии эволюции, впервые описанной Ч. Дарвином. Суть генетического алгоритма заключается в последовательном преобразовании множества решений с учетом сильных и слабых сторон текущего набора решений на основе полученных ранее результатов.
Номер журнала Вестник науки №1 (10) том 3
Ссылка для цитирования:
Дрепин А.С., Захаров Д.О. РЕШЕНИЕ NP-ПОЛНЫХ ЗАДАЧ С ПОМОЩЬЮ ГЕНЕТИЧЕСКИХ АЛГОРИТМОВ С ИСПОЛЬЗОВАНИЕМ ПАРАЛЛЕЛИЗМА // Вестник науки №1 (10) том 3. С. 146 - 148. 2019 г. ISSN 2712-8849 // Электронный ресурс: https://www.вестник-науки.рф/article/859 (дата обращения: 19.04.2024 г.)
Вестник науки СМИ ЭЛ № ФС 77 - 84401 © 2019. 16+