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

71

4. Наилучшее размещение (глобальный минимум) приведено в табл. 5.6.

Табл. 5.6.

5. Гистограмма распределения этих 24 минимумов с указанием их значений

Simin и вероятности появления каждого из них Pi приведена на рис. 5.12. По оси Х отложены значения минимумов Si min, а по оси Y - вероятность Pi их появлния.

72

Pi

Si min

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

Pi

,%

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

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

73

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

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

6. ОПТИМИЗАЦИЯ РАЗМЕЩЕНИЯ ПО ДВУМ КРИТЕРИЯМ

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

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

Тоже самое происходит, если провести сначала оптимизацию по критерию минимума пересечений, а затем по критерию минимизации суммарной длины соединений.

Таким образом оптимизацию размещения элементов по двум критериям таким методом считаем неудовлетворительной.

74

Хорошие результаты оптимизации размещения получаются при следующих вариантах.

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

(рис. 4.7). Из этого набора оптимизированных размещений выбираем 30-50 % наилучших

(или с минимумами, отстоящими от наилучшего минимума на 10-50 %). Определяем для каждого из этих выбранных оптимизированных размещений число пересечений проводников. Из всех полученных значений выбираем минимальное. Размещение элементов, соответствующее этому минимальному значению пересечений будем считать оптимизированным по двум критериям: по минимуму суммарной длины соединений и минимуму пересечений проводников.

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

(рис. 5.12). Из этого набора оптимизированных размещений выбираем 30-50% наилучших

(или с минимумами, отстоящими от наилучшего минимума на 10-50%). Определяем для каждого из этих выбранных оптимизированных размещений значение суммарной длины.

Из всех полученных значений выбираем минимальное. Размещение элементов,

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

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

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

Для первого варианта второстепенным критерием является минимум пересечений, а для второго варианта – минимум суммарной длины соединений.

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

75

ЗАКЛЮЧЕНИЕ

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

1)программа оптимизации компоновки с произвольным начальным

распределением;

2) программа оптимизации компоновки с созданием множества начальных

распределений с помощью рандомизации;