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

1

2

3

4

5

6

7

8

9

10

11

12

1

0

4

0

0

0

0

1

0

0

0

0

0

2

4

0

4

0

0

0

1

1

1

0

0

0

3

0

4

0

6

0

0

0

0

1

0

0

0

4

0

0

6

0

5

2

0

0

0

0

0

0

5

0

0

0

5

0

2

0

0

0

0

0

0

6

0

0

0

2

2

0

0

0

0

0

0

0

7

1

1

0

0

0

0

0

2

0

0

0

0

8

0

1

0

0

0

0

2

0

3

0

0

0

9

0

1

1

0

0

0

0

3

0

1

0

0

10

0

0

0

0

3

0

0

0

1

0

3

0

11

0

0

0

0

0

0

0

0

0

3

0

2

12

0

0

0

0

0

0

0

0

0

0

2

0

Результаты оптимизации:

Наилучшая матрица распределения 

Блок N1 с элементами:(8)(11)(12)(9)(10)(7)

Блок N2 с элементами:(6)(1)(2)(5)(4)(3)

Наименьшее количество межблочных соединений при данном распределении=5

кол-во связей - 5 встречается 4844 раз кол-во связей - 7 встречается 4493 раз кол-во связей - 9 встречается 663 раз

Особенности результатов решения : число минимумов - 3 (из них первый глобальный);

наилучший минимум (глобальный) дает 5 межблочных соединений с вероятностью 0,48;

второй (локальный) дает 7 межблочных соединений с вероятностью 0,45;

третий (локальный) дает 9 межблочных соединений с вероятностью 0,07;

отношение числа связей наихудшего минимума к числу связей наилучшего - 1,8;

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

По результатам исследований можно отметить следующее.

1) При оптимизации любого исходного начального распределения число межблочных связей снижается по сравнению с неоптимизированным в 1,5 - 4 раза.

2) Для 1000-10000 начальных распределений после оптимизации каждого из них число минимумов обычно равно 3 - 5 в зависимости от схемы соединений.

3) Вероятность появления глобального минимума равна 0,4 - 0,8 в зависимости от схемы соединений.

4) Значение локального минимума обычно отличается от глобального в несколько раз (в 2 - 4 раза), но в некоторых случаях это отличие составляет 15 - 20 %. Чем выше значение отношения наихудшего минимума к наилучшему (то есть глобальному) и чем меньше их отличия по вероятности появления, тем меньше степень оптимизации.

5) В большинстве случаев, вероятность появления каждого последующего по эффективности минимума монотонно убывает (рис. 2.8).