Norenkov.Osnovy.Avtomatizirovannogo.Proektirovania.2002 (525024), страница 45
Текст из файла (страница 45)
Его можно представить матрицей X(т х п), элемент которой Xt = 1, если конструктив Р включен в блок 5, иначеX' = 0. Некоторое распределение единиц и нулей по клеткам матрицы X составляет одну конкретную компоновку, т. е. одно проектное решение. Но допустимы только такие варианты распределения 1 и 0 по клеткам матрицы X,которые удовлетворяют следующим ограничениям:£* = 1,(4-32)±Х,<Утм,(4.33)1=1где Утгк — максимальное число элементов, помещающихся в один блок.Условие (4.32) свидетельствует о том, что элемент может быть помещентолько в один блок; условие (4.33) — об ограниченном объеме блоков.В общем случае в задачах компоновки может быть несколько критериев. Вчастном случае используется единственный критерий — число межблочныхсвязей.
Число таких связей следует минимизировать.Для вычисления критерия применяют следующую модель. Формируютсяматрицы Y = X x P n W = Y x Хт. Матрица Y (т х п) есть матрица связейблоков и конструктивов, элемент yjt этой матрицы равен числу связейу-го блока с /-м конструктивом. Элемент wpg матрицы W (т х т) равен числу связеймежду блоками В и В , Хт — транспонированная матрица X.
Так как числомежблочных (внешних) связей равно общему числу связей за вычетом числавнутренних связей К, то в качестве целевой функции, подлежащей максимизации, можно принять суммарное число внутренних связей, т. е. функциюК(Х) = ± WJX).(4.34)Р=\Таким образом, задача компоновки представлена как задача дискретного(булева) математического программирования с целевой функцией (4.34), огра1914.
Математическое обеспечение синтеза проектных решенийничениями (4.32), (4.33) и множеством управляемых параметров X. Аналогично формулируется ряд других задач структурного синтеза.При решении задачи компоновки генетическим методом можно использовать хромосому следующей структуры: гены соответствуют конструктивам,значение /-го гена есть номер блока, в который помещен i'-й конструктив.В случае применения НСМ декомпозиция общей задачи приводит к локальным подзадачам, в каждой из которых выбирается один из еще не распределенных конструктивов и назначается в один из блоков. Необходимо сформулировать правила S выбора в каждой подзадаче конструктива и правила Qk выбораблока для этого конструктива. Каждая эвристика включает в себя по одномуправилу 5 и Qk.Формулировка правил — ответственная задача, от качества решения которой зависит эффективность поиска оптимума. Однако ее решение с помощьюНСМ оказывается проще, чем решение традиционными эвристическими методами.Действительно, используя традиционный эвристический метод, следуетсформулировать единственную комплексную эвристику, в которой с некоторыми весами учитываются все требования к синтезируемому решению.
Но дляполучения решения, близкого к оптимальному, эти веса должны изменяться отшага к шагу (от подзадачи к подзадаче), а найти корректный алгоритм изменения весов в рамках обычных эвристических методов невозможно. Веса принимаются постоянными, поэтому решение нельзя считать оптимальным.Метод НСМ можно рассматривать именно как генетический метод определения оптимальной последовательности весов. Но вместо комплексной эвристики проще и удобнее использовать множество простых правил и вместоизменения весов производить замену правил при переходе от шага к шагу, чтои делается в НСМ. Формирование таких правил не представляет существенных трудностей, так как не нужно назначать веса. Важно лишь обеспечитьразнообразие правил, чтобы рациональные решения не оказались за пределамипоискового пространства.В многокритериальных задачах оптимизации проблема формирования эвристик часто решается довольно просто: каждое правило должно соответствовать одному из имеющихся критериев оптимальности.
Конечно, при использовании метода НСМ предоставляется возможность выбора любых разумныхправил и, следовательно, формирования набора эвристик по предпочтениямпользователя. Это обстоятельство успешно используется, когда исходные критерии оптимальности нелегко трансформировать в частные критерии локальных подзадач.Примеры правил в задаче компоновки для выбора конструктива:SJ конструктив, которому соответствует максимальный элемент в матрице D;S2) конструктив k с максимальным числом связей с другими конструктивами, т. е. с максимальной суммой элементов в k-тл строке матрицы D (в этом ипредыдущем правилах строки и столбцы уже распределенных конструктивовне учитываются);1924 4. Методы структурного синтеза в системах автоматизированного проектированияS3) конструктив с максимальным числом связей с уже распределеннымиконструктивами, т.
е. конструктив, которому соответствует столбец в матрицеY с максимальной суммой элементов.Примеры правил выбора блока:gj) минимально загруженный блок;Q2) максимально загруженный блок;QJ блок, имеющий максимальное число связей с распределяемым конструктивом, т. е. блок с максимальным элементом у ( текущей матрицы Y в /-мстолбце, где / — номер распределяемого конструктива.Пару правил 5 и Qk называют эвристикой Эл. В случае задачи с приведенными выше примерами правил имеем 3 x 3 = 9 возможных эвристик.Кластеризация. Иногда требуется равномерное распределение элементов по имеющимся блокам.
Тогда возникает задача кластеризации, которуюможно рассматривать как разновидность задачи компоновки, отличающуюсятипом ограничений: вместо ограничения типа неравенства на объем кластера(блока) вводится ограничение типа равенства на число элементов (компонентов) в кластере.
Таким образом, ограничение (4.33) принимает вид п = егЛ(п/т)или ent(n/m) + 1:теZ » = п,7=1где п - число элементов в у'-м кластере, ent(«/w) — целая часть частного отделения числа элементов п на число кластеров т. Другими словами, требуетсяравномерное распределение элементов по кластерам, минимизирующее связность кластеров друг с другом. В частности, в некоторых алгоритмах размещения микросхем на платах предварительно решается задача дихотомическойкластеризации — разделения множества микросхем на два минимально связанных подмножества одинаковой (при четном и) мощности.Очевидно, что в задаче кластеризации после соответствующей корректировки можно использовать правила выбора очередного элемента и его размещения в одном из кластеров, аналогичные правилам в задаче компоновки. Так,в правиле Qt загрузка кластера будет оцениваться не его внутренним трафиком (связностью), а числом размещенных в нем элементов.
Во всех правилахQk возможным кластером-кандидатом может быть только тот кластер, в котором еще не исчерпан лимит на размещение. Правила 5",- S3 используются безизменений. При вычислении целевой функции штрафы за нарушение ограничений не предусматриваются, так как учет ограничений введен в эвристики.Возможны и другие варианты множества эвристик. Например, можно использовать правила, в которых очередным размещаемым элементом выбирается следующий элемент:£,) в строке которого в матрице связей находится максимальный элементматрицы;iS"2) имеющий максимальную суммарную связность с уже размещеннымиэлементами;7 Основы автоматизированногопроектирования1934.
Математическое обеспечение синтеза проектных решенийS3) имеющий минимальную суммарную связность с еще не размещеннымиэлементами.Для выбранного по одному из правил S^- S3 элемента Р определяется кластер, в котором:Q}) имеется элемент, максимально связанный с Р',Q2) уже размещенные элементы максимально связаны с Р (максимальнасуммарная связность).Из этих правил можно скомбинировать шесть разных эвристик и добавитьэвристику, в которой сначала определяется кластер L по признаку минимальнойзагруженности, а затем для него выбирается элемент по признаку максимальной связности с уже размещенными в L элементами. Ограничения на максимально допустимое число элементов в кластере введены в эвристики.Размещение двумерных разногабаритных компонентов. Эта задачаизвестна как задача размещения электронных компонентов (в кристаллах БИСили на печатных платах) или как двумерная задача упаковки грузов в контейнеры (в последнем случае ее часто обозначают 2DBPP (2D Bin Packing Problem)).Рассмотрим подход к ее решению с помощью НСМ.В этой задаче задана полубесконечная полоса (контейнер с открытым верхом и шириной W) и множество разногабаритных прямоугольных компонентоввысотой D и основанием шириной Z(, число компонентов равно N.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
