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

58

Наилучшее размещение модулей представлено в табл. 4.5.

Минимальная суммарная длина (глобальный минимум) при данном размещении равна 126 единиц.

Особенности результатов решения.

В результате оптимизации с помощью алгоритма парных перестановок 10000

различных исходных размещений получили 35 различных минимумов суммарных длин,

различающихся в 1,3 раза, что означает существенную зависимость значения минимума от исходного начального размещения

Гистограмма распределения этих 35 минимумов с указанием их значений Wi min

и вероятности появления каждого из них Pi приведена на рис. 4.7.

Значение глобального минимума Wo min равно 126 единиц длины. Оптимальное размещение элементов для глобального минимума показано в табл. 4.5.

По результатам исследований можно отметить следующее:

1) При оптимизации любого исходного начального размещения элементов суммарная длина соединений уменьшается по сравнению с неоптимизированным в 1,3 - 3

раза.

2)Степень оптимизации, т.е. значение минимума суммарной длины соединений,

взначительной степени зависит от начального размещения элементов в установочных позициях (рис. 4.7).

η Wi min - Wo min 100 %, показывающей насколько процентов полученный результат

Wo min

оптимизации отличается от глобального, монотонно возрастает, асимптотически приближаясь к единице при значениях , равных 18-22 % (рис. 4.8). По этому рисунку можно определить суммарную вероятность появления результата оптимизации,

отличающегося от глобального на заданное значение в процентах. Суммарная вероятность Pi - это сумма вероятностей i-го и всех предыдущих (лучших) минимумов.

59

Рис. 4.7. Гистограмма распределения минимумов суммарной длины с указанием вероятности их появления

Рис. 4.8. Вероятность появления результата оптимизации, отличающегося от глобального не более, чем на процентов.

60

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

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

возрастает, а самых удаленных - уменьшается (рис. 4.7).

5. АЛГОРИТМ ПАРНЫХ ПЕРЕСТАНОВОК ДЛЯ ОПТИМИЗАЦИИ РАЗМЕЩЕНИЯ С МИНИМИЗАЦИЕЙ ПЕРЕСЕЧЕНИЙ ПРОВОДНИКОВ

5.1. Метод парных перестановок

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

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