Материал: Основы проектирования Р Э С. Комплект учебно-методической документации по дисциплине. Учебное пособие. Самойленко Н.Э., Скоробогатов В.С

117

(p)< f (q) или f / (q)>0. Если ни одно из условий не выполнено, удваиваем расстояние от p до q до тех пор пока p,q .

3.По формуле (3.15) находим *1.

4.Проверим, можно ли точку * считать точкой минимума

с точностью , то есть f / (*k+1) ,

k=0,1, ... Если условие прекращения поиска выполнено, то задача решена и *= *k+1. В противном случае продолжаем вычисления.

5. Если f / (*k+1)>0 , то выбираем вместо интервала

(p,q) интервал (p, *k+1), в противном случае – (*k+1,q), то есть тот интервал, который содержит точку минимума и переходим к пункту 3 данного алгоритма.

3.11. Задания и вопросы для самостоятельной подготовки

1В чем основная идея любого метода поиска?

2Какие условия прекращения поиска Вы знаете?

3Проведите сравнительный анализ градиентных методов и дайте рекомендации по их применению.

3Для решения каких задач используются mетоды однопараметрической оптимизации?

4Оцените эффективность метода Давидона Флетчера Пауэлла.

4.Лабораторный практикум

4.1.Лабораторная работа 1.

Оптимизация размещения модулей на коммутационном поле методом парных перестановок

4.1.1.Общие указания по выполнению лабораторной работы

118

Целью лабораторной работы является углубление и закрепление знаний по вопросам оптимизации размещения модулей на коммутационном поле (прямоугольной или какой-либо другой формы) методом парных перестановок и получение практических навыков использования ЭВМ IBM PC для решения таких задач. В процессе выполнения лабораторной работы студент должен уметь практически применять полученные знания и приобретенные навыки для:

составления исходных данных и решения на ЭВМ задач оптимального размещения модулей;

решения вопросов оптимизации размещения модулей с помощью алгоритма парных перестановок;

исследования и оценки эффективности алгоритма оптимального размещения модулей.

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

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

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

изучить инструкцию по технике безопасности по эксплуатации ЭВМ.

119

4.1.2.Домашнее задание и методические указания по его выполнению

При выполнении домашнего задания студент должен ознакомиться с алгоритмом оптимизации размещения модулей на коммутационном поле путем парных перестановок. Для этого необходимо воспользоваться учебником [I, с. 188-212]. В связи с тем, что в учебнике вопрос оптимизации размещения модулей на коммутационном поле методом парных перестановок рассматривается недостаточно подробно необходимо проработать также следующий материал.

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

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

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

120

снижение трудоемкости изготовления и количества используемого провода при проводном монтаже.

4.2.Лабораторная работа 2.

Минимизация числа пересечений проводников при автоматизированном размещении элементов РЭС на коммутационном поле

4.2.1. Общие указания по выполнению лабораторной работы

Целью лабораторной работы является углубление и закрепление знаний по вопросам оптимизации размещения модулей на коммутационном поле (прямоугольной или какой-либо другой формы) методом парных перестановок и получение практических навыков использования ЭВМ IBM PC для решения таких задач. В процессе выполнения лабораторной работы студент должен уметь практически применять полученные знания и приобретенные навыки для:

составления исходных данных и решения на ЭВМ задач оптимального размещения модулей;

решения вопросов оптимизации размещения модулей с помощью алгоритма парных перестановок;

исследования и оценки эффективности алгоритма оптимального размещения модулей.

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

Студент, явившийся на занятия, должен иметь методические указания по данной лабораторной работе, полученные в библиотеке. 121

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

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

предварительно изучить инструкцию по технике безопасности по эксплуатации ЭВМ.

4.2.2.Домашнее задание и методические указания по его выполнению

При выполнении домашнего задания студент должен ознакомиться с алгоритмом оптимизации размещения модулей на коммутационном поле путем парных перестановок. Для этого необходимо воспользоваться учебником [I, с. 188-212]. В связи с тем, что в учебнике вопрос оптимизации размещения модулей на коммутационном поле методом парных перестановок рассматривается недостаточно подробно необходимо проработать также следующий материал.

4.2.2.1. Оптимизация размещения с помощью алгоритма парных перестановок

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

микросхемы, транзисторы, диоды, резисторы и т. д. ), так и типовые элементы замены ( ТЭЗы), блоки, панели и т. д. При

122

этом предполагается , что модули определенным образом ( согласно электрической схеме ) соединяются между собой.

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

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

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

Сначала по заданной исходной схеме составляется матрица связей , в которой каждый элемент показывает количество связей между i-м и j-м модулями. После этого по специально выведенной формуле производится вычисление значений Sij - величин, показывающих изменение числа пересечений проводников при перестановке местами i-го и j-го модулей. Если Sij меньше или равно нулю, то перестановка считается нецелесообразной. Если жеSij - больше нуля, то перестановка считается целесообразной, i-й и j-й модули переставляются местами и вычисление значений Sрк для нового размещения модулей в позициях производится вновь и так до

123

тех пор, пока не наступит оптимизация, т. е. все значения Sрк будут отрицательными или равными нулю. Для достижения оптимизации часто бывает достаточно 2-4 перестановок, снижение числа пересечений проводников после оптимизации по сравнению с исходным происходит обычно в 1,5 - 10 раз.

Рассмотрим эту задачу математически и выведем формулу для вычисления значений величины Sij.

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

установленный в эту позицию модуль характеризуется двумя координатами xi и yi (рис.4.1).

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

124

Задачу будем решать с помощью алгоритма парных перестановок . Для иллюстрации решения этой задачи представим схему в виде графа (рис. 4.2), в котором вершинами являются элементы (модули) схемы, а ребрами – соединения между элементами. Размещение позиций , в которые устанавливаются вершины графа, задается их координатами x и y, а соединения между элементами задаются матрицей связей (табл. 4.1).

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

125

Осуществим парную перестановку первой и четвертой вершин графа, в результате чего получим граф без пересечений

(рис. 4.3).

Общее количество пересечений для графа с n вершинами можно определить по формуле

где n – число вершин графа;

1,если между ребом (i, j) и ребром (k,l) есть пересечение p[(i, j), (k,l)]

0, в противном случае;

mij, mkl - элементы матрицы смежности. В другой форме можно записать

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

Пусть в некотором графе ребра, инцидентные вершине A, имеют следующее число пересечений с остальными ребрами графа:

j 1 k 1 l k 1

126

После перестановки местами вершин A и B число пересечений изменится и станет равным

Тогда изменение числа пересечений в результате перестановки вершин A и B выразится формулой

n n 1 n

{p[(A, j);(k, l)] p[(B, j);(k, l)]} (mAj mBj) mkl ,

j 1 k 1 l k 1

где j A, j B.

Если SAB > 0, то перестановка вершин A и B целесообразна,

так как ведет к уменьшению числа пересечений. Определить наличие пересечений p[(i,j);(k,l)] между

ребрами (i,j) и (k,l) можно следующим образом в соответствии с рис.

4, 5.

Ребра А1А2 и В1В2 являются отрезками прямых линий. Прямая линия описывается уравнением [2]:

y = kx + b.

Прямая, на которой лежит отрезок А1А2, описывается уравнением

xA1 xA2

Аналогично для В1В2:

y = a2x+b2,