Элементов на подмножества в задачах компоновки

Последовательные алгоритмы не требуют начального разделения множества Е. из исходного множества выделяется первое подмножество Т₁. Затем из оставшегося множества выделяется второе подмножество Т₂ и т.д., пока не произойдет полное разделение множества Е на подмножества Т_i, .

Обобщенная схема последовательного алгоритма показана на рис. 14.

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

Возможны различные процедуры формирования подмножества T_t. В качестве примера рассмотрим метод максимальной конъюнкции и минимальной дизъюнкции. В нем используется матрица Q. Пусть А – множество нераспределенных элементов, а В – некоторое подмножество А, не содержащее e_i .Вводим показатели:

(10)

(11)

где – множество цепей (комплексов), связанных с элементом e_i и с элементами множества В соответственно.

Показатель С (e_i , В) определяет число цепей, соединяющих элемент e_i иэлементы множества В, а показатель d(e_i, В) – число цепей, которые не являются общими у e_i и элементов из В. Для вычисления показателей С и d можно использовать операции над множествами, либо скалярные произведения векторов – строк S_i матрицы Q. В этом (втором) случае

(12)

Нет

Да

Нет Да

Рис. 16. Обобщенная схема последовательных алгоритмов разделения множества

элементов на подмножества в задачах компоновки

(13)

(14)

(15)

Вначале принимается A=E\e₀. Процедура формирования подмножества Т_i содержит четыре шага:

1. В качестве первого элемента из множества Е выбирается такой, который наибольшим числом цепей связан с внешними выводами схемы. С этой целью для всех вычисляется показатель . Выбирается элемент e_s с наибольшим значением этого показателя. Если их несколько, то из них выбирается e_j, у которого минимален показатель . Выбранный элемент включается в подмножество Т_i и исключается из множества А.

2. Пусть в подмножестве уже находится несколько элементов. На очередном шаге выбирается элемент, для которого значение максимально. Если их несколько, то выбирается с наименьшим значением . Поэтому процедура и называется методом максимальной конъюнкции и минимальной дизъюнкции.

3. Перед назначением элемента в подмножество проверяется ограничение по числу внешних соединений g_i для подмножества . Если ограничения соблюдаются, то элемент включается в подмножество и исключается из множеств А. В противном случае в соответствии с п.2 выбирается другой кандидат для включения в .

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

При наличии двух ограничений на число элементов К и на число внешних выводов g число V подмножеств заранее неизвестно.

Допустимое число внешних выводов g в узлах, содержащих по К элементов, также заранее неизвестно. Часто имеется возможность изменять число g, выбирая различный тип разъема.В этом случае задачу разделения Е сначала решают без ограничений на число внешних выводов, затем по полученным подмножествам анализируют требуемые значения

5.1. Процедура формирования подмножеств с использованием ВГС

– множество элементов, (включая e₀), не вошедших в подмножество . Для элементов введем показатель – коэффициент связности:

, (16)

где и – суммарный все связей элемента e_i c элементами из и соответственно. Показатель может быть как положительным, так и отрицательным. Пусть А – множество нераспределенных элементов. Сначала

A=E\e₀.

Процедура содержит три шага:

1. Первым элементом в формируемое подмножество выберем такой e_i, у которого значение r_Qi в матрице R максимально. Если их несколько, то из них выберем элемент e_j с минимальным значением .

Этотэлемент помещается в и исключается из А.

2. После того, как часть элементов помещена в формируемое подмножество ,ищется элемент из А с максимальным коэффициентом связности . Если их несколько, то выбирается с меньшим номером.

3. Формирование подмножества заканчивается, если число элементов в нем достигает заданного значения К либо А = Ø.

Иногда в п. 2 выбор элемента производят в два этапа: сначала выбираем элемент с максимальным значением , а если их несколько, то из них – с минимальным значением .

Очевидно, что при последовательных процедурах разделения первые подмножества содержат сильно связанные элементы, а последние – слабо связанные. Такой результат оптимальным можно назвать условно. Его можно улучшить, используя итерационные алгоритмы. При этом меняются местами элементы (или их группы), принадлежащие различным подмножествам с целью уменьшения суммарного веса связей между подмножествами. Чаще всего – парные перестановки, т.е. меняют местами два элемента. Для оценки эффективности перестановки рассматривают изменение суммарного веса связей между выделенными подмножествами до и после перестановки

.

Сначала делаются попытки перестановок каждого из элементов со всеми остальными элементами из . Находится вариант с и эта перестановка выполняется, если . Процедура многократно повторяется. Если все пробы перестановок имеют , то итерации перестановок элементов из Т₁ заканчиваются. Затем берутся элементы из Т₂ и осуществляются попытки перестановок с элементами из и т.д. При этом необходимо следить за изменением числа внешних выводов.

Для определения первого или очередного элемента, включаемого в формируемое подмножество T_i в последовательных алгоритмах, а также для выбора пары элементов очередной перестановки в итерационном алгоритме удобно использовать ВГС с матрицей R, учитывающей вероятностный характер соединений элементов в цепях (комплексах), эти операции требуют меньше машинного времени, объем ОЗУ, чем операции с элементами матрицы Q ГЭК. ГЭК необходим для определения числа внешних выводов формируемых подмножеств. Выполнение каждой перестановки требует К(n-к) проб, где К – число элементов в подмножестве, n – общее число элементов. Число итераций для экономии машинного времени можно ограничить.

Оптимум функции F(N) может быть в случае парных перестановок локальным, например

Глобальный оптимум

°

локальный

° ° ° N

°

0 1 2 3 4 5 6

°

Рис. 17. Оптимум функции F(N)

Использование многократного применения алгоритма парных перестановок, когда работа алгоритма не прекращается после снижения . N=1 – локальный оптимум, N=4 – глобальный оптимум. Нужна групповая перестановка с номерами 1,2,3,4.