Алгоритм парных перестановок для решения задач оптимизации компоновки и размещения элементов РЭС: Учебное пособие, страница 31

1

2

3

4

5

6

7

8

9

10

x

y

N

x

y

1

0

4

0

0

1

1

0

0

0

0

5

4

1

5

4

2

4

0

1

4

1

1

0

0

0

0

1

3

2

6

3

3

0

1

0

1

1

0

1

0

0

0

5

2

3

5

2

4

0

4

1

0

1

0

3

0

1

0

3

3

4

6

1

5

1

1

1

1

0

1

0

1

1

1

6

1

5

3

3

6

1

1

0

0

1

0

0

1

0

3

6

3

6

2

4

7

0

0

1

3

0

0

0

4

1

0

1

1

7

3

1

8

0

0

0

0

1

1

4

0

1

1

2

4

8

1

1

9

0

0

0

1

1

0

1

1

0

1

3

2

9

3

2

10

0

0

0

0

1

3

0

1

1

0

3

1

10

1

3

4.2. Исследование зависимости эффективности алгоритма парных перестановок от исходных начальных размещений и способы повышения его эффективности

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