ПОИСК Статьи Чертежи Таблицы Примеры применения метода комбинирования эвристик из "Основы автоматизированного проектирования " Рассмотрим примеры постановки задач оптимизации и структурного синтеза для решения генетическими методами. В каждом из представленных ниже классов задач при использовании НСМ можно получить значительно лучшее приближение к экстремуму по сравнению с альтернативными одноэвристическими методами. [c.190] Задача компоновки оборудования, в частности, может заключаться в распределении микросхем по модулям (платам или типовым элементам замены), модулей — по панелям, панелей — по шкафам РЭА или приборов — по отсекам корабля и т. п. [c.191] С — множество связей, связь С. соединяет элементы P,viP . [c.191] Условие (4.32) свидетельствует о том, что элемент может бьггь помещен только в один блок условие (4.33) — об ограниченном объеме блоков. [c.191] В общем случае в задачах компоновки может быть несколько критериев. В частном случае используется единственный критерий — число межблочных связей. Число таких связей следует минимизировать. [c.191] При решении задачи компоновки генетическим методом можно использо-вать хромосому следующей структуры гены соответствуют конструктивам, значение z-ro гена есть номер блока, в который помещен г-й конструктив. [c.192] Формулировка правил ответственная задача, от качества решения которой зависит эффективность поиска оптимума. Однако ее решение с помощью НСМ оказывается проще, чем решение традиционными эвристическими методами. [c.192] Действительно, используя традиционный эвристический метод, следует сформ лировать единственную комплексную эвристику, в которой с некоторыми весами з тываются все требования к синтезируемому решению. Но для получения решения, близкого к оптимальному, эти веса должны изменяться от шага к шагу (от подзадачи к подзадаче), а найти корректный алгоритм изменения весов в рамках обычных эвристических методов невозможно. Веса принимаются постоянными, поэтому решение нельзя считать оптимальным. [c.192] Метод НСМ можно рассматривать именно как генетический метод определения оптимальной последовательности весов. Но вместо комплексной эвристики проще и удобнее использовать множество простых правил и вместо изменения весов производить замену правил при переходе от шага к шагу, что и делается в НСМ. Формирование таких правил не представляет существенных трудностей, так как не нужно назначать веса. Важно лишь обеспечить разнообразие правил, чтобы рациональные решения не оказались за пределами поискового пространства. [c.192] В многокритериальных задачах оптршизации проблема формирования эвристик часто решается довольно просто каждое правило должно соответствовать одному из имеющихся критериев оптимальности. Конечно, при использовании метода НСМ предоставляется возможность выбора любых разумных правил и, следовательно, формирования набора эвристик по предпочтениям пользователя. Это обстоятельство успешно используется, когда исходные критерии оптимальности нелегко трансформировать в частные критерии локальных подзадач. [c.192] Пару правил S. и Qi назьшают эвристикой Э. . В случае задачи с приведенными вьппе примерами правил имеем 3x3=9 возможных эвристик. [c.193] Из этих правил можно скомбинировать шесть разных эвристик и добавить эвристику, в которой сначала определяется кластер L по признаку минимальной загруженности, а затем для него выбирается элемент по признаку максимальной связности с уже размещенными в L элементами. Ограничения на максимально допустимое число элементов в кластере введены в эвристики. [c.194] Э ) для очередного размещения выбирается компонент с наибольшей площадью среди еще Рис. 4.14. Размещение компо- не размещенных компонентов в случае положи-нента в очередном участке тельного зазора gap. [c.194] Синтез расписаний. Задачи синтеза расписаний требуется решать во многих приложениях, например при планировании различных производственных процессов, распределении ресурсов, выборе числа и типов процессоров для многопроцессорных специализированных комплексов и т. п. [c.195] Необходимо составить расписание, при котором минимизируются затраты на вьшолнение всех работ с учетом штрафов. [c.195] Каждая эвристика при применении для синтеза расписаний метода НСМ включает два правила одно для выбора очередной работы, другое для выбора машины, обслуживающей эту работу. [c.195] Например, при синтезе многостадийных расписаний в качестве очередной может выбираться работа 1 — с наименьшим 2 — с наименьшим временем окончания обслуживания на предыдущей стадии Е.. Примеры правил выбора машин 1 — машина, на которой обслуживание данной работы будет наиболее дешевым 2 — машина, на которой работа будет обслужена за наименьшее время. Эти правила образуют четыре эвристики. Можно использовать дополнительные правила, например правило, учитьшающее затраты времени на переналадку машин. [c.195] Кроме того, для узлов-потребителей и узлов-источников заданы объемы соответственно заказанного и имеющегося продукта каждого типа, для серверов — максимальный объем перевозимого продукта, скорость движения, цена за единицу расстояния пробега, штрафы за нарушение временных ограничений (выход за пределы временных окон), причем штрафы зависят от цены единицы продукта каждого типа и от степени нарушения ограничений. [c.196] Вернуться к основной статье