Компоновка

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

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

Пусть задача характеризуется следующими исходными данными:

· — множество элементов (конструктивов) ;

· — множество блоков ;

· — множество связей, связь соединяет элементы и .

· — матрица размера , элемент которой равен числу связей между элементами и .

Опишем множество альтернатив . Оно представляется матрицей размера , элемент которой , если конструктив включен в блок , иначе . Некоторое распределение единиц и нулей по клеткам матрицы представляет одну конкретную компоновку, т.е. одно проектное решение. Но только такие варианты распределения 1 и 0 по клеткам матрицы допустимы, которые удовлетворяют следующим ограничениям:

(1)

где суммирование производится для конструктива по всем от до ;

(2)

где суммирование производится для блока по от до , — максимальное число элементов, помещающихся в один блок.

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

В общем случае в задачах компоновки может быть несколько критериев. В частном случае используется единственный критерий — число межблочных связей. Число таких связей нужно минимизировать.

Для вычисления критерия применяют следующую модель.

Формируются матрицы и . Матрица размера есть матрица связей блоков и конструктивов, элемент этой матрицы равен числу связей -го блока с -м конструктивом. Матрица имеет размер , ее элемент равен числу связей между блоками и , — транспонированная матрица . Так как число межблочных (внешних) связей равно общему числу связей минус число внутренних связей , то в качестве целевой функции, подлежащей максимизации, можно принять суммарное число внутренних связей, т.е. функцию

(3)

где суммирование выполняется по от до .

Таким образом, задача компоновки представлена как задача дискретного (булева) математического программирования с целевой функцией (3), ограничениями (1), (2) и множеством управляемых параметров .

Аналогичным образом, формулируется ряд других задач структурного синтеза.

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

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

Формулировка правил — ответственная задача, от качества решения которой зависит эффективность поиска оптимума. Однако ее решение в HCM оказывается проще, чем в традиционных эвристических методах.

Действительно, в традиционном эвристическом методе нужно сформулировать единственную комплексную эвристику, в которой с некоторыми весами были бы учтены все требования к синтезируемому решению. Но для получения решения, близкого к оптимальному, эти веса должны изменяться от шага к шагу (от подзадачи к подзадаче), а найти корректный алгоритм изменения весов в рамках обычных эвристических методов невозможно. Веса принимаются постоянными, решение оказывается далеким от оптимума.

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

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

Примеры правил в задаче компоновки для выбора конструктива:

· ) выбирается конструктив, которому соответствует максимальный элемент в матрице ;

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

· ) выбирается конструктив с максимальным числом связей с уже распределенными конструктивами, т.е. конструктив, которому соответствует столбец в матрице с максимальной суммой элементов.

Примеры правил выбора блока:

· ) выбирается минимально загруженный блок;

· ) выбирается максимально загруженный блок;

· ) выбирается блок, имеющий максимальное число связей с распределяемым конструктивом, т.е. блок с максимальным элементом текущей матрицы в -м столбце, где — номер распределяемого конструктива.

Пару правил и называют эвристикой . В случае задачи с приведенными выше примерами правил имеем возможных эвристик.