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

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

Одним из методов оптимизации размещения элементов является алгоритм парных перестановок [1,2]. Согласно этому алгоритму, сначала все элементы схемы произвольным образом размещаются по заданному количеству установочных позиций, а затем производятся перестановки тех пар элементов, находящихся в разных позициях, которые дают уменьшение суммарной длины соединений. В результате таких перестановок достигается локальный минимум. Близость его к глобальному минимуму, т.е. степень оптимизации, существенно зависит от исходного начального (обычно произвольного) размещения элементов в позициях. В связи с этим целесообразно исследовать зависимость степени оптимизации от начальных размещений. Для этого необходимо разработать программу, реализующую алгоритм парных перестановок с использованием большого количества начальных размещений. Для каждого начального размещения должна быть проведена своя оптимизация. Для создания большого количества начальных размещений можно использовать функцию рандомизации, включив эту функцию в программу. Для облегчения обработки статистических данных в программе следует предусмотреть вывод результатов оптимизации в порядке уменьшения степени оптимизации с указанием количества появлений каждого оптимума. Отдельно вывести наилучший оптимум с указанием размещения элементов по позициям. Для оценки степени оптимизации необходимо сравнить оптимумы между собой.

Поставленные задачи были нами решены. Была разработана программа оптимального размещения элементов с получением большого количества (10000-100000) исходных начальных размещений методом рандомизации.

Исследования проводились на различных схемах соединений с различным расположением установочных позиций для элементов с использованием 10000 - 100000 исходных начальных размещений для каждой схемы.

Из многих рассмотренных примеров приведем следующий.

Исходные данные:

количество элементов = 12;

количество исходных начальных размещений: 10000;

матрица соединений представлена в табл. 3.3;

координаты установочных позиций даны в табл. 3.4.

Таблица 3.3                      Таблица 3.4 Таблица 3.5