Разработка функциональной цифровой ячейки (стр. 3 из 8)

1. Определяется последовательность выбора элементов. Для улучшения сходимости алгоритма к оптимальным решениям элементы в последовательности располагаются так, что каждый следующий элемент должен быть максимально связан с предыдущими элементами и минимально с последующими (Блок 1). Такой порядок позволяет уменьшить перебор за счет отсечения вариантов, не содержащих оптимальных решений задачи, т.к. при данной методике определения порядка выбора элементов получаются более точные нижние оценки подмножеств вариантов размещения. Будем выбирать элементы по максимальному значению фактора связности p: P=Dp-Dн. Первым элементом всегда является разъём, т.к для него выделена единственная установочная позиция.

2. Процесс оптимизации удобно представить в виде дерева решения задачи перебора. Каждая вершина соответствует одному подмножеству решения задачи перебора. На нулевом уровне находится вершина, соответствующая полному множеству всех вариантов размещения (7!), т.е. когда установлен разъём, а для остальных элементов назначение позиций не выбрано. На первом уровне располагаются 6 вершин подмножеств непересекающихся вариантов, порожденных закреплением первого элемента в различные позиции. На втором уровне располагаются (n-1) ×n вершин, соответствующих непересекающимся подмножествам всех вариантов закрепления первого и второго элементов во все установочные позиции. Продолжая деление, перейдем к n-ому уровню, на котором закреплены все элементы. Всего вершин на этом уровне N!, каждая из которых соответствует закреплению всех элементов.

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

Предположим, что выполнено директивное размещение i элементов. Остается (n-i) незакрепленных элементов. Дадим оценку F^{^} целевой функции F суммарной длины связей. Нижняя оценка состоит из трех слагаемых: оценка длины связи между не размещенными элементами F н^{^}, оценка длины связи между не размещенными и размещенными элементами F нр^{^}, значение длины связи между размещенными элементами F р.

F^{^} = F н^{^} + F нр^{^} + F р (4)

Значения нижних оценок записываются в вершинах дерева решений

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

Существуют две стратегии поиска решений.

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

Следующим шагом выполняется проверка: проверяется количество вариантов во вновь образованных подмножествах. Если эти подмножества содержат по одному варианту, то делается вывод, что получены частные решения задачи размещения. Для них рассчитывается целевая функция. Среди этих значений ищется минимальное, и найденное значение называется верхней границей целевой функции (Fв^{^}), найденной на данном шаге. Так как значения нижних оценок при детализации не уменьшается, то можно сделать вывод: подмножества решений, у которых нижние оценки хуже верхней границы могут в дальнейшем не исследоваться. Процедура повторяется до тех пор, пока не будут отсечены все подмножества вариантов кроме одного, для которого на очередном шаге была рассчитана верхняя граница. Этот вариант будет оптимальным решением.

Вторая стратегия - стратегия ныряния до дна. Алгоритм пытается получить частное решение как можно быстрее, с тем, чтобы получить расчетную Fв^ и выполнить отсечение неперспективных вершин. В этой стратегии детализация вершин выполняется по одной ветви, пока не будет по одному варианту решения. После исследования первой ветви выполняется отсечение неперспективных вариантов, выбирается вершина с минимальной оценкой Fн^{^} и снова выполняется процедура ветвления, пока не будет получено новое частное решение. Далее процесс повторяется, пока не будет получено оптимальное решение [3].

Последовательность действий для решения задачи размещения элементов:

Вводится множество элементов схемы Е={e₁, e₂,. e₇}: от 1 до 7 - разъем и 6 микросхем; а также множество посадочных мест P={p₁, p₂,... p₇}: от 1 до 7. Соответственно, исходными данными для размещения является ПЭС устройства (рис.8), чертеж ячейки, координаты посадочных мест для установки элементов (рис.9).

2) Ставим в соответствие множеству элементов схемы (микросхемам) множество вершин взвешенного графа (рис.7).

Рис.11.

В программе Placeing создаем и заполняем две матрицы: матрицу связей (по взвешенному графу на рис.11, создать файл с расширением. mxs, рис.12) и матрицу длин, расстояний (по чертежу ячейки на рис.9, создать файл с расширением. mxd, рис.13). Заполнив их, переходят к построению дерева решений. Алгоритм построения дерева описан выше.

Рис.12. Матрица связей.

Рис.13. Матрица длин.

Поставим 7 элемент в 7 позицию (е7 7p). Определим приоритетный ряд связи элементов друг с другом (последовательность выбора элементов). Начинают, как правило, с разъема, затем ищут элемент, максимально связанный с ним. После этого ищут элемент, который максимально связан с первым (который связан с разъемом). Причем, если с ним и любым другим максимально одинаково связаны несколько элементов, выбирают любой. Затем ищут элемент, наиболее связанный с разъемом и с 1-ым выбранным элементом (это определяется суммированием связей этих элементов по матрице связей) и т.д. до последнего. Получается последовательность, элементы в которой располагаются так, что каждый следующий элемент максимально связан с предыдущими элементами и минимально с последующими. Такой порядок позволяет уменьшить перебор за счет отсечения вариантов, не содержащих оптимальных решений задачи, так как при данной методике определения порядка выбора элементов получаются более точные нижние оценки подмножеств вариантов размещения. Результат данной операции:

5 9 8 9 9 11

е7 е5 е6 е2 е4 е1 е3

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

Нижняя оценка состоит из трех слагаемых: оценка длины связи между не размещенными элементами F н^{^}, оценка длины связи между не размещенными и размещенными элементами F нр^{^}, значение длины связи между размещенными элементами Fр.

Fнг^ = F н^{^} + F р + Fнр^{^}

Таким образом, построив дерево решений, была найдена ветка с минимальной оценкой (из этого следует, что найдена верхняя граница целевой функции Fв^), следовательно, найдено оптимальное решение. В соответствие с этим решением 7 элемент (разъем) устанавливается в 7 позицию, 5 элемент (5 микросхема) - в 5 позицию, 6 элемент - в 4 позицию, 2 элемент во 2 позицию, 4 элемент - в 1 позицию, 1 элемент - в 3 позицию, 3 элемент - в 6 позицию.

Рассмотрим критерий качества F (n) по шагам алгоритма n, то есть построим график увеличения нижней оценки Fн^{^} от 7 элемента к 3-ему в оптимальной ветке дерева (в оптимальном решении):

Рис.14. График зависимости значения нижней оценки по оптимальной ветви.

Таким образом, данный алгоритм удобен для нахождения оптимального варианта размещения элементов на печатной плате, так как он не подразумевает под собой перебора всех возможных N! (N! растет очень быстро) вариантов решения. Этот алгоритм основан на сокращении перебора возможных решений путем отсечения заведомо неперспективных вариантов решений, нижняя оценка которых меньше, либо равна нижней оценке (или верхней границе целевой функции) оптимального решения. Оптимальное решение находится достаточно быстро, так как используется программа Placeing. В ней есть калькулятор, быстро подсчитывающий значения нижних оценок в зависимости от варианта размещения. По ним и делается вывод о продолжении построения ветки дерева, либо об отсечении ее (их).