Методические указания к лабораторным работам по курсу "Автоматизация конструкторского и технологического проектирования РЭС", страница 8

Цель работы: решение задачи компоновки схемы электрической принципиальной итерационным алгоритмом.

Краткие сведение из теории.

Чаще всего схема проектируемого устройства не реализуется на одой плате. В таком случае возникает задача оптимального разбиения схемы на части, выполняемых на отдельных конструктивах. От качества решения задачи зависит количество сигнальных связей между внешними соединителями конструктивов, что в конечном итоге влияет на надёжность и помехозащищённость проектируемого устройства.

Математически эта задача компоновки сводится к разбиению исходного множества элементов Е на пересекающиеся подмножества Е₁, Е₂, …, Е_n(Е_i = 0, )                                                                                                 ().

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

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

где  x_i = 1, если i-я цель связывает элементы, находящиеся в различных конструктивах

x_i  = 0   –  в противном случае.

m – количество цепей в схеме проектируемого устройства.

Для вычисления данной характеристики используется матрица элементных комплексов Q.

Иногда при решении задачи компоновки разработчику необходимо мстить часть модулей в заданные конструктивы.

Чтобы данные модули не участвовали в перестановках, их помечают с помощью специального массива Z, элемент которого Z_i = 1, если i – модуль закреплён, Z_i = 0 в противном случае.  Алгоритм оптимизации разбиения схемы на части методом парных перестановок заключается в следующем.

Шаг I. Для начального варианта разбиения вычисляется числовая характеристика качества (количество общих цепей).

Шаг 2. Выполняется перестановка двух модулей с номерами i и j, находящихся в различных конструктивах. (При условии, что данные модули не закреплены разработчиком.)

Шаг 3. Для получения варианта разбиения вычисляется критерий качества - число общих цепей N_о.ц.      Шаг 4. Если число общих цепей полученного варианта меньше, ,чем у первоначального, то перестановка считается удачной. В противном случае перестановка считается неудачной и восстанавливается исходный вариант разбиения.       

Шаг 5. Проверяется условие окончания работы алгоритма. В зависимости от конкретной реализации используется одно из условий:

а) ни одна из возможных на данном Исходном варианте парных перестановок не привела к его улучшению.    б) Выполнено заданное количество перестановок. в) исчерпан лимит машинного времени.

При выполнении условия останова на печать выводится улучшенный вариант разбиения схемы и алгоритм свою работу заканчивает в противном случае производится обмен другой пары модулей, находящихся в различных конструктивах, (переход к шагу 2). При разбиении схемы на части (на две) число парных перестановок которые можно выполнить на исходном варианте, равно ;

( – число модулей в каждом из конструктивов).

Оптимальность полученного решения и число итераций зависят от качества первоначального варианта разбиения.

ПРОГРАММА оптимизации разбиения схемы электрической на части, выполняемые на отдельных конструктивных модулях.