Алгоритм парных перестановок для решения задач оптимизации компоновки и размещения элементов РЭС: Учебное пособие, страница 9

Пусть в результате произвольного начального распределения нами сформированы Z блоков. Обозначим их через X^a, X^b, X^g,...,X^Z. Подсчитав количество соединений между двумя блоками, например, между блоком Х^a и блоком Х^b, меняем взаимно местами по одному модулю из блока Х^a и из блока Х^b. После этого вновь считаем количество соединений между блоками. Если после перестановки количество соединений уменьшилось, то перестановка целесообразна. Если же увеличилось или осталось прежним, то перестановка нецелесообразна. Можно производить перестановку каждого модуля блока Х^a с каждым модулем блоков Х^b, Х^g, ..., Х^z, а затем каждого модуля блока Х^b с каждым модулем остальных блоков и т.д. В результате можно получить минимизацию соединений между блоками. Чтобы упростить вычисления выведем формулу для определения целесообразности перестановки местами i и j модулей, находящихся в разных блоках. При этом следует учесть что при перестановке местами этих модулей количество соединений между блоком X^a и блоком X^b меняется на величину, равную изменению количества межблочных соединений переставляемых модулей с остальными, а непереставляемые модули на изменение количества межблочных соединений не влияют.

Обозначим через -количество внешних соединений модуля с блоком Х^b;

- количество внешних соединений модуля  с блоком Х^a;

- количество внутренних соединений модуля  блока Х^a с другими модулями этого же блока;

 - количество внутренних соединений модуля  блока Х^b с другими модулями этого же блока;

- количество общих (прямых) соединений между переставляемыми модулями  и.

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

Таким образом:

F_o =  +  - .

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

, а изменение количества межблочных соединений:

.

Таким образом целесообразность перестановки i - го модуля, находящегося в блоке Х^a, с  j - м модулем, находящимся в блоке Х^b,  определяется по формуле

,     (2.2)

где  - функционал для модулей   и ;

 - количество внешних соединений модуля  с блоком Х^b;

- количество внешних соединений модуля  с блоком Х^a;

 - количество внутренних соединений модуля  блока Х_a с другими модулями этого же блока;

 - количество внутренних соединений модуля  блока Х^b с другими модулями этого же блока;

- количество общих (прямых) соединений между переставляемыми модулями  и .

Если  £ 0, то перестановка этих модулей нецелесообразна, то есть эта перестановка не ведет к уменьшению числа межблочных соединений, а ведет к их возрастанию или не изменяет их количество. Если  > 0, то перестановка целесообразна. В рассмотренном выше случае предполагается, что производится первая попавшаяся целесообразная перестановка. Однако лучше использовать алгоритм, в котором вычисляются значения функционалов DF для всех пар модулей и из всех возможных целесообразных перестановок пар модулей выбирается та пара модулей, перестановка которых дает максимальное уменьшение количества межблочных соединений (рис. 2.1), а не первая попавшаяся целесообразная перестановка. Подсчитав функционалы всех пар модулей и, произведя перестановку двух модулей, для которых функционал имеет максимальное положительное значение, вновь производят вычисления всех функционалов для этих двух блоков. Если окажется, что для каких-либо двух модулей максимальный функционал больше нуля, то снова производят перестановку и так несколько раз, до тех пор, пока все функционалы будут равны или меньше нуля. Следует подчеркнуть, что после каждой перестановки все функционалы вычисляются вновь. В результате таких перестановок достигается обычно локальный минимум межблочных соединений. Близость его к глобальному минимуму, то есть степень оптимизации, существенно зависит от начального (исходного) распределения модулей между блоками.