Норенков И.П. - Основы автоматизированного проектирования (1060628), страница 44
Текст из файла (страница 44)
д. Генетический поиск в этом случае есть поиск последовательностиэвристик, обеспечивающей оптимальный вариант размещения.Второй подход получил название метод комбинирования эвристик. Этотметод оказывается предпочтительным во многих случаях. Например, в задачах синтеза расписаний распределяется заданное множество работ во времени и между обслуживающими устройствами — серверами, т. е. проектнымипараметрами для каждой работы будут номер сервера и порядковый номер вочереди на обслуживание.
Пусть N— число работ, М— число серверов. Еслигены соответствуют номерам работ, то в первом подходе в хромосоме нужноиметь 2N генов и общее число отличающихся друг от друга хромосом W заметно превышает наибольшее из чисел N ! и MN.Согласно методу комбинирования эвристик, число генов в хромосоме в 2раза меньше, чем в первом подходе, и равно N. Поэтому если число используемых эвристик равно К, то мощность множества возможных хромосом уженесравнимо меньше, а именно:Очевидно, что меньший размер хромосомы ведет к лучшей вычислительной эффективности, а меньшее значение Ж позволяет быстрее найти окрестности искомого экстремума. Кроме того, в методе комбинирования эвристик всехромосомы, генерируемые при кроссовере, будут допустимыми.
В то же время при применении обычных генетических методов необходимо использоватьпроцедуры типа РМХ для корректировки генов, относящихся к номерам в очереди на обслуживание, что также снижает эффективность поиска.Примеры применения метода комбинирования эвристикРассмотрим примеры постановки задач оптимизации и структурного синтеза для решения генетическими методами. В каждом из представленных нижеклассов задач при использовании НСМ можно получить значительно лучшееприближение к экстремуму по сравнению с альтернативными одноэвристическими методами.1904.4.
Методы структурного синтеза в системах автоматизированного проектированияКомпоновка. Содержательная суть задачи компоновки — распределениеработ по исполнителям, оборудования — по помещениям, прикладного ПО и БД— по подсетям виртуальной локальной вычислительной сети и т. п.Задача компоновки оборудования, в частности, может заключаться в распределении микросхем по модулям (платам или типовым элементам замены),модулей — по панелям, панелей — по шкафам РЭА или приборов — по отсекамкорабля и т. п.Пусть задача характеризуется следующими исходными данными:Р — множество элементов (конструктивов) Р, /' = 1,..., п;В — множество блоков В ,j = 1, ..., т;С — множество связей, связь Сл соединяет элементы Р и ?k.D — матрица п х и, элемент которой Dik равен числу связей между элементами Р и Р .Опишем множество альтернатив А.
Его можно представить матрицей 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) — целая часть частного отделения числа элементов п на число кластеров т.
Другими словами, требуетсяравномерное распределение элементов по кластерам, минимизирующее связность кластеров друг с другом. В частности, в некоторых алгоритмах размещения микросхем на платах предварительно решается задача дихотомическойкластеризации — разделения множества микросхем на два минимально связанных подмножества одинаковой (при четном и) мощности.Очевидно, что в задаче кластеризации после соответствующей корректировки можно использовать правила выбора очередного элемента и его размещения в одном из кластеров, аналогичные правилам в задаче компоновки.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
