Гибридный алгоритм решения квадратичной задачи о назначениях
Authors: Полупанова Е.Е. , Нигодин Е.А. 
Published: December 2024

Данная работа посвящена решению квадратичной задачи о назначениях с помощью гибридного алгоритма, который использует принципы генетического и эволюционного алгоритмов. Квадратичная задача о назначениях – одна из фундаментальных задач комбинаторной оптимизации в области математической оптимизации, принадлежащая к категории задач размещения объектов. В статье приводится простая постановка данной задачи и её более подробная математическая модель. Так как квадратичная задача о назначениях является NP-трудной и даже небольшие входные данные могут потребовать больших вычислительных затрат для точного алгоритма, разумно применить гибридный эвристический подход в решении данной проблемы. В статье подробно освещено построение гибридного алгоритма, последовательность его шагов, блок-схема. Далее в статье приводятся графический интерфейс с возможностью регулировки различных параметров алгоритма, позволяющий оптимально их настроить. В последней части статьи освещается сравнительный анализ эффективности работы полученного алгоритма: сравнение точности разработанного гибридного алгоритма с новым методом оптимизации сорной травой, сравнение с лучшими известными решениями для современных бенчмарков. Удалось установить, что гибридный алгоритм показывает уверенное преимущество в точности над алгоритмом сорной травы. Также гибридный алгоритм смог найти решение равное лучшему известному для задачи tai12a. Для задачи tai15a алгоритм показал отклонение 0,2% от лучшего известного решения. Для остальных рассматриваемых бенчмарков алгоритм показал отклонение от лучших решений не более чем 4,2%, что доказывает высокую эффективность созданного алгоритма в сравнение с лучшими мировыми решениями. Кроме того, данный алгоритм имеет высокую экономическую ценность ввиду широкого применения решения рассматриваемой задачи на практике, например в размещении фабрик или предприятий по местам, размещении связанных электронных компонентов на печатных платах или в интегральных схемах и т.д.

This article is devoted to solving the quadratic assignment problem using a hybrid algorithm contains both genetic and evolutionary algorithms. The quadratic assignment problem is one of the fundamental problems of combinatorial optimization in the field of mathematical optimization, belonging to the category of object placement problem. The article provides a simple statement of this problem and its more detailed mathematical model. Since the quadratic assignment problem is NP-hard and even small input data can take large computational costs for an accurate algorithm, it is reasonable to use a hybrid heuristic approach to solve this problem. The article describes in detail the construction of a hybrid algorithm, the sequence of its steps, and the flowchart. Further, the article provides a graphical interface with the ability to adjust various parameters of the algorithm, allowing it to be optimally configured. The last part of the article covers a comparative analysis of the effectiveness of the resulting algorithm: comparing the accuracy of the developed hybrid algorithm with a new method of invasive weed optimization algorithm, comparing it with the best-known solutions for modern benchmarks. It was found that the hybrid algorithm shows a strong advantage in accuracy over the invasive weed optimization algorithm. Also, the hybrid algorithm was able to find a solution equal to the best known for the tai12a problem. For the tai15a problem, the algorithm showed a deviation of 0.2% from the best-known solution. For the rest of the considered benchmarks, the algorithm showed a deviation from the best solutions of no more than 4.2%, which proves the high efficiency of the created algorithm in comparison with the world's best solutions. In addition, this algorithm has a high economic value due to the wide application of the solution to the problem in practice, for example, in placement of factories or enterprises in places or in placement of associated electronic components on printed circuit boards or integrated circuits, etc.