одного решения задачи, а случайного множества потенциальных ре-
шений. Каждое такое решение представляет собой закодированную
структуру, как правило, именуемую в литературе хромосомой.
При разработке структуры хромосомы и способа ее кодирования
определяется состав информации, которая будет храниться в хромо-
соме. Учитывая особенности типовой конструкции ЭМТК на керами-
ческих микроплатах, можно сказать, что в состав этой информации
должны входить данные о взаимном расположении группы элементов
в пределах одной микроплаты, а также данные о порядке следования
микроплатв пакете при сборке электронного модуля. Тогда каждая
хромосома должна содержать:
•
n
наборов генов, где
n
— число микроплатс элементами, а каж-
дый из этих наборов определяет состав элементов и их взаимное
расположение в пределах своей микроплаты;
•
один набор генов, определяющий последовательность располо-
жения микроплатв пакете.
Поскольку структуру закодированного решения составляют не-
сколько наборов генов, то будет удобнее называть каждое конкретное
решение не хромосомой, а особью, которая, в свою очередь, состоит
из набора хромосом. Будем называть каждый из набора генов, опре-
деляющих расположение элементов,
E
-хромосомой, а набор генов,
отвечающий за порядок микроплат, —
М
-хромосомой. Таким образом,
каждая особь состоит из одной
М
-хромосомы и из
n
Е
-хромосом.
Учитывая особенности конструкции ЭМТК, задачу размещения
элементов в объеме ЭМТК можно разделить на несколько подзадач
двумерного размещения групп элементов внутри каждой микроплаты.
Так, в работе [13] рассмотрен целый ряд алгоритмов двумерного раз-
мещения элементов на коммутационном поле. Однако большинство из
этих алгоритмов рассчитаны на применение фиксированных позиций
регулярных сеток и поэтому эффективно работают лишь с однотип-
ными элементами, имеющими примерно одинаковые габаритные раз-
меры. А поскольку в ЭМТК применяются разногабаритные элементы,
то использование этих методов становится нерациональным.
Авторы предлагают использовать метод размещения в левый ниж-
ний угол. Он относится к безуровневым стратегиям формирования
упаковок прямоугольных блоков в задаче раскроя-упаковки (Packing
Problem) [19, 20]. В данном методе реализуется такое расположение
элементов, при котором любой из элементов плотно прилегает к со-
седям (с некоторым минимально допустимым зазором, зависящим,
например, оттехнологии изготовления электронного узла) и не может
быть сдвинут влево или вниз (рис. 2).
ISSN 0236-3933. Вестник МГТУ им. Н.Э. Баумана. Сер. “Приборостроение”. 2009. № 1 115
