Гибридный алгоритм оптимизации на основе объединения моделей роевого интеллекта: роя хромосом и пчел

Аннотация: Разработан гибридный алгоритм решения задачи размещения элементов СБИС, объединяющий процедуры поведения коллектива пчел и роя хромосом. Критерий оптимизации основан на оценках числа цепей, пересекающих заданные линии области трассировки. Описывается модифицированная парадигма роя хромосом, обеспечивающая, в отличие от канонического метода, возможность поиска решений в аффинном пространстве позиций с целочисленными значениями параметров. В качестве веса аффинной связи между хромосомами на аффинно-релаксационная модели роя хромосом используются оценки степени «различия» между ними. Предложена модифицированная структура алгоритма пчел. Для каждой базовой позиции реализуется вероятностный выбор набора позиций, расположенных в ее окрестности. Временная сложность алгоритма составляет О(n2) – О(n3).

Ключевые слова: размещение, роевой интеллект, пчелиный алгоритм, рой хромосом, гибридизация, поиск.

B.К. Lebedev, O.B. Lebedev, M.A. Ganzhur

Hybrid optimization algorithm based  on the combination of swarm intelligence models: a swarm of chromosomes and bees

Summary: A hybrid algorithm for solving the problem of placing VLSI elements has been developed, which combines the procedures for the behavior of a group of bees and a swarm of chromosomes. The optimization criterion is based on estimates of the number of nets crossing the given lines of the routing area. A modified chromosome swarm paradigm is described, which, in contrast to the canonical method, provides the possibility of searching for solutions in an affine position space with integer parameter values. As the weight of the affine connection between chromosomes on the affine-relaxation model of a swarm of chromosomes, estimates of the degree of «difference» between them are used. A modified structure of the bee algorithm is proposed. For each base position, a probabilistic choice of a set of positions located in its vicinity is implemented. The time complexity of the algorithm is О(n2) – О(n3).

Keywords: placement, swarm intelligence, bee algorithm, chromosome swarm, hybridization, space

DOI: 10.34219/2078-8320-2023-14-2-80-84