Автоматизированное проектирование. Норенков И.П. - 120 стр.

 5@!"! 4                              %!#*%!#&F*:,$*     $I*:+*F*)&* :&)#*'! +($*,#)KH (*L*)&M

случае есть поиск последовательности эвристик, обеспечивающей оптимальный вариант размещения.
      Второй подход получил название — /$&#- %#/2'*'"#()*'9 B("'+&'%. Этот метод оказывается
предпочтительным во многих случаях. Например, в задачах синтеза расписаний распределяется за-
данное множество работ во времени и между обслуживающими устройствами — серверами, т.е. про-
ектными параметрами для каждой работы будут номер сервера и порядковый номер в очереди на об-
служивание. Пусть N — число работ, M — число серверов. Если гены соответствуют номерам работ,
то в первом подходе в хромосоме нужно иметь 2N генов и общее число отличающихся друг от друга
хромосом W заметно превышает наибольшее из чисел N! и MN.
      Согласно методу комбинирования эвристик, число генов в хромосоме в два раза меньше, чем в
первом подходе, и равно N. Поэтому если число используемых эвристик равно K, то мощность мно-
жества возможных хромосом уже несравнимо меньше, а именно
         W = KN.
      Очевидно, что меньший размер хромосомы ведет к лучшей вычислительной эффективности, а
меньшее значение W позволяет быстрее найти окрестности искомого экстремума. Кроме того, в мето-
де комбинирования эвристик все хромосомы, генерируемые при кроссовере, будут допустимыми. В
то же время при применении обычных генетических методов необходимо использовать процедуры ти-
па PMX для корректировки генов, относящихся к номерам в очереди на обслуживание, что также сни-
жает эффективность поиска.


                        P38:L0.0+> + 94384,1 5D> ,:/4740-84D>
       1. Дайте формулировку задачи математического программи-
рования.
       2. В чем заключаются трудности решения многокритериаль-
ных задач оптимизации?
       3. Что такое “множество Парето”?
       4. Для функции, заданной своими линиями равного уровня
(рис. 4.14), постройте траектории поиска методами конфигураций,
деформируемого многогранника, наискорейшего спуска из исход-
ной точки N0.
     5. Как Вы считаете, можно ли применять метод проекции
градиента для решения задач оптимизации с ограничениями типа
неравенств?
     6. Что такое “овражная целевая функция”? Приведите при-
мер такой функции для двумерного случая в виде совокупности
линий равного уровня.                                         %+,. 4.)4. Пример для построения траекторий
     7. Какие свойства характеризуют класс NP-полных задач?                      поиска
     8. Морфологическая таблица содержит 8 строк и 24 столбца. Сколько различных вариантов структуры
представляет данная таблица?
     9. Приведите пример И-ИЛИ графа для некоторого знакомого Вам приложения.
     10. Приведите примеры продукций из знакомого Вам приложения.
     11. Дайте предложения по постановке задачи компоновки модулей в блоки для ее решения генетически-
ми методами. Какова структура хромосомы?




 &.+.)$(*),$" . !"#$%!#&'&($"!))$*           +($*,#&($"!)&*                                      120