<<
>>

Организация процесса переразмещения

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

Для организации последовательного процесса перемещения элементов в целевые позиции (но итерационного с точки зре­ния выполняемых операций и процедур) посредством механизма парных перестановок воспользуемся моделью коммутационного поля в виде сети перестановок S(V, T).

Здесь V— множество узлов, соответствующих позициям. Для каждого узла (позиции) viзаданы координаты (xi, yj∙). Между парой узлов viи Vjсуще­ствует ребро тогда и только тогда, когда любую пару элементов, помещенных в узлы viи vj∙, можно взаимно перемещать. Таким образом, множество ребер T этой сети задает множество возмож­ных парных перестановок. Вес ребра равен расстоянию между соответствующими позициями.

Конфигурация сети, т. е. множество ребер T, определяется методикой формирования и организации групп парных переста­новок элементов [7.17].

Множество ребер в сети T разбивается на r подмножеств Tj∙ ∈T, Ti∩ Tj = 0и UTj = T так, что каждое подмножество представляет собой паросочетание. Паросочетание — это мно­жество попарно не смежных ребер. Таким образом, в каждом подмножестве сформировано множество непересекающихся пар позиций, что дает возможность одновременно (параллельно) ре­ализовать перестановки во всех этих парах. Под реализацией понимается рассмотрение пары позиций и элементов, располо­женных в них, и после анализа соответствующих условий эти элементы переставляются или нет.

На каждой итерации последовательно одно за другим рас­сматриваются все подмножества Tj. Это дает возможность пере­мещаться элементу, расположенному в некотором узле vi, в лю­бой смежный ему узел Vj сети S.

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

плоского простого графа, близкого по форме к ортогональной решетке. При размещении одногабаритных элементов такая сеть имеет вид ортогональной решетки (рис. 7.3).

Тогда алгоритм разбиения Tна па- росочетания следующий. Пронумеру­ем вертикальные и горизонтальные ря­ды. Вначале рассмотрим горизонталь­ные ряды. В множество T1 войдут все пары (j, j + 1) соседних узлов в гори­зонтальных рядах, причем 1-й элемент пары занимает в горизонтальном ряду нечетную позицию, т. е. j — нечетно.

Для множества узлов на рис. 7.4, а множество T1= {(1 — 2); (3 — 4);... }. В множество T2 войдут все пары

(j, j + 1) соседних узлов в горизонтальных рядах, причем 1-й элемент пары занимает четную позицию т. е. j — четно. Для множества узлов на рис. 7.4, б множество T2 = {(2 — 3; 4 — 5;... }.

Рис. 7.4. Паросочетание в горизонтальных рядах

Аналогичным образом рассматриваются вертикальные ряды, при этом формируются подмножества T3и T4.

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

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

Структуру сети, представленной на рис. 7.3, можно услож­нить, добавив ребра, связывающие соседние позиции по диаго­нали (рис. 7.6). При этом дополнительно выделяют 2 множества

диагональных рядов: в первом множестве диагональ распростра­няется сверху вниз и слева направо; во втором — сверху вниз и справа налево.

С помощью пересчета по значениям Fj и Fj определяются значения сил Fij и Fj, действующих вдоль диагоналей. Причем, если Fj или Fj равна нулю, то Fij и Fj принимаются равными нулю. Аналогично тому, как разбивались на паросочетания гори­зонтальные и вертикальные ряды, разбиваются и диагональные ряды. В результате имеем 8 подмножеств узлов Ti - Ts, каждоеиз которых является паросочетанием.

При размещении разногабаритных элементов используется следующий подход. Множество узлов Vв соответствии с за­данным исходным размещением разбивается на подмножества

Vk таким образом, что в каждом подмножестве размещены элементы одного габарита (или близкие по га­баритам). В общем случае струк­тура посадочных мест для элемен­тов одного типа нерегулярна. Тем не менее, с помощью тривиально­го алгоритма можно построить сеть по форме, близкой к ортогональной. При этом четко выделяются горизонтальные и вертикальные ряды узлов. Сеть должна быть связной (рис. 7.7). Для каждоготипа элементов строится своя сеть.

Рис. 7.7. Сеть при размещении разногабаритных элементов

В соответствии с идеологией блочно-иерархического подхода для схем большой размерности процесс размещения можно раз­бить на следующие этапы:

а) формирование групп элементов (блоков);

б) размещение блоков на коммутационном поле;

в) размещение элементов каждого блока.

Рис. 7.8. Принципы формирования блоков и укрупненной модели задачи раз­мещения

На рис. 7.8 показаны принципы формирования блоков и укрупненной модели задачи размещения.

Элементы aι —a4 объединены в элемент A,а позиции, в ко­торых размещены эти элементы, объединены в одну позицию. Возможны различные принципы объединения элементов и пози­ций.

7.4.

<< | >>
Источник: Курейчик В. В., Лебедев Б. К., Лебедев О. Б.. Поиско­вая адаптация: теория и практика. — M.: ФИЗМАТЛИТ,2006. — 272 с.. 2006

Еще по теме Организация процесса переразмещения:

  1. 2. Принципы административного процесса
  2. 1.Сущность административного процесса
  3. Тема 13. Административный процесс
  4. 3.3 Исследование процесса спекания алюмокомпозитов системы А1- 3масс.%М-1масс.%Си с наномодификаторами
  5. 3.4 Исследование процесса спарк-плазменного спекания порошковых алюмокомпозитов системы Л1-3масс.%М-1масс.%Си с наномодификаторами
  6. Глава II МАТЕМАТИЧЕСКОЕ МОДЕЛИРОВАНИЕ ПРОЦЕССОВ ВЗАИМОДЕЙСТВИЯ СВЕТОВЫХ ПОТОКОВ C ВНУТРЕННИМИ ОБЪЕМАМИ И ПОВЕРХНОСТЯМИ КРИСТАЛЛОВ.
  7. 3. Структура административного процесса. Виды административных производств
  8. Глава 2 ОПЫТ РАЗРАБОТКИ И ИСПОЛЬЗОВАНИЯ УЧЕБНЫХ ЗАДАНИЙ, ОРИЕНТИРОВАННЫХ НА ДОСТИЖЕНИЕ ЛИЧНОСТНЫХ РЕЗУЛЬТАТОВ ШКОЛЬНИКОВ В ПРОЦЕССЕ ОБУЧЕНИЯ
  9. Разработка фондов учебных заданий, обеспечивающих достижение личностных результатов обучения в процессе опытно-экспериментальной работы
  10. 2.Административно-правовой статус организаций
  11. 3.1 Исследование процесса смешивания порошковых смесей системы Al- 3масс.%М-1масс.%Си, А1-4масс.%Си, А1-4масс.%Мд с наномодификаторами
  12. 3. Организация милиции
  13. §1.1 Профессиографический подход к анализу деятельности менеджера коммерческой организации