Некоторые методы оптимального размещения элементов электрических и электронных цепей

№120-1,

физико-математические науки

Рассматривается несколько методов оптимального размещения элементов электрических и электронных цепей на коммутационном поле. Предложен вычислительный метод, являющийся адаптацией метода Гаусса-Зейделя на основе общего подхода парных перестановок. Рассмотрен также вариант генетического алгоритма, аналогичный применяемому при решении диофантовых уравнений и также увязанный с методом парных перестановок. Предложено объединить два рассмотренных метода в одной программе. Рассмотрены примеры вычислений рассматриваемыми методами.

Похожие материалы

Введение

Предположим, что дан набор элементов, связанных между собой в соответствии с электрической схемой. Требуется разместить элементы на некотором коммутационном поле (КП) таким образом, чтобы некоторый функционал качества достигал максимального значения. Для случая равногабаритных элементов их возможные позиции на КП расположены в узлах прямоугольной сети с параметрами: nx — число позиций в горизонтальном ряду; ny — число позиций в вертикальном ряду; hx — горизонтальный шаг между позициями; hy — вертикальный шаг между позициями, xb,yb — координаты центров позиции. Критерием является требование минимума взвешенной длины (МСВД) соединений. При этом могут применяться различные метрики (прямоугольная, Эвклидова, Чебышевская, ls и т.д.).

Элементы обозначаем как e1, …, en, для каждой пары элементов заданы весовые коэффициенты r_{i,j}, i,j=1,\dots, n характеризующие связь элементов, соответствующая матрицей соединений R={r_{i,j}}_{i,j=1,\dots, n}.

Задан набор позиций размещения элементов p_1, \dots, p_n, m \ge n, где pi — номер позиции i -го элемента. Для конкретности предполагаем, что m=n. Расстояния d_{i,j},i,j=1,\dots, n между парами позиций pi,pj образуют матрицу расстояний D={d_{i,j}}_{i,j=1,\dots, n}.

Считаем, что шаг сетки единичный. Набор позиций элементов образует перестановку без повторений p=(p1, …, pn). Длина соединений элементов ei и ej равна L_{i,j}=r_{ij}d_{p(i)p(j)}, (i,j=1,\dots, n). Пусть Es — множество всех фиксированных элементов, включая элемент e0, тогда суммарная взвешенная длина соединений элемента ei с элементами из Es равна:

a_{ip(i)}=\sum_{s \in E_s}r_{is}d_{p(i)s}, (i,j=1,\dots, n),

где dp(i)s — расстояние между элементом ei , находящимся в позиции pi, и элементом es.

Суммарная взвешенная длины соединений равна:

F(p)=0.5\sum_{i=1}^n\sum_{j=1}^n r_{ij} d_{p(i)p(j)}+ \sum_{i=1}^n a_{ip(i)}.

Для прямоугольной метрики задача размещения по критерию МСВД сводится к минимизации целевой функции F(p) на множестве перестановок Р соединений:

F(p)=0.5\sum_{i=1}^n\sum_{j=1}^n r_{ij}(|x_i-x_j|+|y_i-y_j|) + \sum_{i=1}^n\sum_{s \in E_s} r_{is}(|x_i-x_s^0|+|y_i-y_s^0|).

Необходимо учитывать геометрическое ограничение — в одной ячейке размещается не более одного элемента, т.е.

\min_{i,j=1, \dots, n} \max { \frac {|x_i-x_j}{h_x}, \frac {|y_i-y_j}{h_y}} \ge 1, |

\min_{i,j=1, \dots, n} \max { \frac {|x_i-x_s^0}{h_x}, \frac {|y_i-y_s^0}{h_y}} \ge 1, |

x_i=I_i h_x, y_i=J_i h_y , i=1, \dots, n; I_i \in {1, \dots, n}, J_i \in {1, \dots, n}.

Адаптированный метод Гаусса-Зейделя в задаче размещения

Пусть целевая функция равна F(x), где x — перестановка без повторений номеров позиций n элементов. Некоторая адаптация стандартных методов оптимизации, в частности, метода Гаусса-Зейделя позволяет относительно экономично решать рассматриваемую проблему. При первом же шаге обычной процедуры оптимизации по любой координате, как правило, происходит выход за пределы допустимой области. В адаптированном методе дополнительно реализуется общий поход парных перестановок: после каждого шага перестановка корректируется, отыскивается аргумент, значение которого совпало с новым значением варьируемой координаты, а значение данного аргумента заменяется на исходное значение (до шага оптимизации) варьируемой координаты.

Пример вычислений

Матрица соединений равна r_{ij}=i+j, i\ne j; r_{ii}=0; i,j=1,\dots,n.

Шаг и количество шагов по координатам, общее число ячеек и элементов: h=1; n0=6; n=36. Начальное приближение находилось методом Монте-Карло (10 000 итераций), после чего локальный оптимум находился адаптированным методом Гаусса-Зейделя с ограничением в 100 итераций. Начальное значение шага по координате равно n, далее на каждой итерации оно уменьшалось на 1 до минимально возможного значения равного 1. Начальное приближение:

x0 = (36, 12, 6, 1, 35, 19, 5, 32, 31, 26, 29, 34, 8, 16, 28, 33, 13, 24, 10, 2, 18, 4, 27, 21, 22, 15, 7, 25, 11, 3, 17, 9, 23, 14, 20, 30), функция штрафа равна нулю, соответствующее значение целевой функции fmin0 = 177648

Вычисленное адаптированным методом Гаусса-Зейделя решение равно:

x1 = (36, 1, 6, 31, 35, 2, 12, 32, 5, 7, 25, 4, 30, 33, 34, 13, 19, 24, 3, 18, 26, 29, 8, 28, 11, 27, 9, 10, 23, 20, 17, 14, 16, 21, 15, 22). Функция штрафа нулевая, локальный оптимум fmin = 171168 (при количестве итераций 171120).

Метод решения на основе генетического алгоритма и парных перестановок

Генетический алгоритм оптимизации является примером применения бионического подхода. Он заключается в следующем.

1. На первом шаге осуществляется задание начальной популяции с определенной численностью.

2. На втором шаге в соответствии с целевой функцией вычисляются коэффициенты выживаемости, их сумма равна единице. Иногда применяются относительные оценки погрешностей и т.п. критерии.

3. Осуществляется статистическая генерация заданного числа пар для размножения. Вероятность особи попасть в пару определяется коэффициентом выживаемости.

4. Производится скрещивание отобранных пар. Векторы независимых переменных делятся на две части, которыми члены пары обмениваются. В результате потомки со смешанными векторами, образующими новую популяцию.

6. Если характеристики потомства плохие, то рационально применение мутации, основанной на рандомизации.

5. Селекции потомства позволяет отобрать особи с наилучшими свойствами выживаемости.

6. Если требуется улучшить найденное решение, то осуществляется переход к п.2.

На этапах селекции и мутации вычисления согласно генетическому алгоритму дополняются процедурой парных перестановок генов в хромосоме.

Пример вычислений

Матрица соединений, шаг ячейки, количество шагов по координатам и общее число ячеек и элементов, начальное приближение задаются как в п.3. После первой итерации методом Монте-Карло: штраф = 0, fmin0 = 185400; x0 = (6, 30, 19, 3, 12, 33, 2, 10, 9, 20, 18, 25, 7, 26, 13, 4, 24, 27, 16, 23, 17, 8, 28, 21, 5, 34, 29, 11, 22, 36, 15, 1, 35, 31, 32, 14).

Решение, вычисленное далее адаптированным методом Гаусса-Зейделя:

Штраф = 0, fmin = 171192; x(1) = (6, 1, 36, 31, 35, 12, 5, 25, 30, 2, 32, 33, 7, 3, 34, 18, 24, 4, 19, 29, 13, 8, 11, 9, 26, 28, 10, 20, 14, 17, 27, 23, 16, 15, 21, 22).

Случай разногабаритных элементов

Также поддается решению адаптированным методом Гаусса-Зейделя. Наиболее удобна прямоугольная метрика. Видоизменения метода связаны с тем, что попадание пробной точки на площадь большого элемента считается запрещенным вариантом, либо он может быть передвинут в пределах коммутационного поля на такое расстояние, чтобы можно было избежать некорректного размещения элементов. При перемещении большого элемента перестановки небольших элементов производятся по известному принципу «обтекания» (множество небольших элементов уподобляется жидкости, а большой элемент — твердому телу).

Выражаю благодарность за содействие научному руководителю проф. Некрасову С.А.

Список литературы

  1. Кулаков А.А. Метод размещения тепловыделяющих элементов в СБИС трехмерной компоновки. // Известия Южного федерального университета. Технические науки, 2013. https://cyberleninka.ru/article/n/metod-razmescheniya-teplovydelyayuschih-elementov-v-sbis-trehmernoy-komponovki
  2. Певнева А.Г. Построение классификации методов глобальной оптимизации. // МЕЖДУНАРОДНЫЙ НАУЧНО-ИССЛЕДОВАТЕЛЬСКИЙ ЖУРНАЛ. № 2 (2). 2012, С. 16-23. https://research-journal.org/technical/postroenie-klassifikacii-metodov-gl/
  3. Ермаков С.М. Метод Монте-Карло в вычислительной математике (вводный курс). Санкт-Петербург: Невский диалект, Бином, 2009.