36
2. Разработана программа, реализующая алгоритм полного перебора для проверки глобальности оптимума, получаемого в результате работы алгоритма парных перестановок с рандомизацией начального распределения.
Исследования проводились на пяти различных схемах соединений с использованием 1000 - 10000 исходных начальных распределений для каждой схемы.
Рассмотрим несколько контрольных примеров и дадим анализ их результатов. Контрольный пример №1 Исходные данные:
количество элементов = 12 количество блоков = 2
количеcтво элементов в блоке 1 = 6 количеcтво элементов в блоке 2 = 6 количество начальных распределений = 1000 матрица связей:
|
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
10 |
11 |
12 |
1 |
0 |
5 |
0 |
0 |
0 |
0 |
2 |
2 |
0 |
0 |
0 |
0 |
2 |
5 |
0 |
8 |
0 |
0 |
0 |
0 |
3 |
2 |
0 |
0 |
0 |
3 |
0 |
8 |
0 |
2 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
4 |
0 |
0 |
2 |
0 |
4 |
0 |
0 |
0 |
0 |
0 |
2 |
0 |
5 |
0 |
0 |
0 |
4 |
0 |
5 |
0 |
0 |
0 |
0 |
0 |
0 |
6 |
0 |
0 |
0 |
0 |
5 |
0 |
0 |
0 |
0 |
0 |
2 |
3 |
7 |
2 |
0 |
0 |
0 |
0 |
0 |
0 |
2 |
0 |
0 |
0 |
0 |
8 |
2 |
3 |
0 |
0 |
0 |
0 |
2 |
0 |
4 |
0 |
0 |
0 |
9 |
0 |
2 |
0 |
0 |
0 |
0 |
0 |
4 |
0 |
3 |
0 |
0 |
10 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
3 |
0 |
4 |
0 |
11 |
0 |
0 |
0 |
2 |
0 |
2 |
0 |
0 |
0 |
4 |
0 |
4 |
12 |
0 |
0 |
0 |
0 |
0 |
3 |
0 |
0 |
0 |
0 |
4 |
0 |
Результаты оптимизации: Наилучшая матрица распределения
Блок N1 с элементами:(1)(3)(8)(9)(2)(7)
Блок N2 с элементами:(10)(4)(11)(12)(5)(6)
Наименьшее количество межблочных соединений при данном распределении=5
кол-во связей - 5 встречается 867 раз кол-во связей - 16 встречается 56 раз кол-во связей - 21 встречается 77 раз
37
Особенности результатов решения :
-число минимумов - 3 (из них первый глобальный);
-наилучший минимум (глобальный) дает 5 межблочных соединений с
вероятностью 0,87;
-второй (локальный) дает 16 межблочных соединений с вероятностью 0,06;
-третий (локальный) дает 21 межблочное соединение с вероятностью 0,08;
-отношение числа связей наихудшего минимума к числу связей наилучшего - 4,2
-вероятность появления каждого последующего минимума убывает
немонотонно.
Расчеты показывают, что у начального распределения, приводящего к глобальному минимуму до оптимизации было 20 связей, у начального распределения, приводящего ко второму минимуму, до оптимизации было 29 связей, у начального распределения, приводящего к третьему минимуму до оптимизации было 37 связей, то есть при оптимизации число связей уменьшается в 1,76 - 4 раза.
Контрольный пример №2
Исходные данные: количество элементов = 12 количество блоков = 2
количество элементов в блоке 1 = 6 количество элементов в блоке 2 = 6 количество начальных распределений = 10000 матрица связей:
|
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
10 |
11 |
12 |
1 |
0 |
4 |
1 |
0 |
0 |
2 |
0 |
0 |
1 |
0 |
1 |
0 |
2 |
4 |
0 |
0 |
0 |
0 |
2 |
0 |
1 |
0 |
0 |
1 |
1 |
3 |
1 |
0 |
0 |
3 |
1 |
0 |
1 |
0 |
1 |
1 |
0 |
0 |
4 |
0 |
0 |
3 |
0 |
1 |
0 |
1 |
0 |
1 |
1 |
0 |
1 |
5 |
0 |
0 |
1 |
1 |
0 |
0 |
4 |
3 |
0 |
1 |
0 |
0 |
6 |
2 |
2 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
4 |
0 |
7 |
0 |
0 |
1 |
1 |
4 |
0 |
0 |
1 |
0 |
0 |
0 |
1 |
8 |
0 |
1 |
0 |
0 |
3 |
0 |
1 |
0 |
0 |
3 |
0 |
4 |
9 |
1 |
0 |
1 |
1 |
0 |
0 |
0 |
0 |
0 |
3 |
3 |
0 |
10 |
0 |
0 |
1 |
1 |
1 |
0 |
0 |
3 |
3 |
0 |
1 |
0 |
11 |
1 |
1 |
0 |
0 |
0 |
4 |
0 |
0 |
3 |
1 |
0 |
1 |
12 |
0 |
1 |
0 |
1 |
0 |
0 |
1 |
4 |
0 |
0 |
1 |
0 |
38
Результаты оптимизации: Наилучшая матрица распределения
Блок N1 с элементами:(6)(2)(10)(11)(9)(1)
Блок N2 с элементами:(12)(4)(3)(5)(8)(7)
Наименьшее количество межблочных соединений при данном распределении =
12
кол-во связей - 12 встречается 6687 раз кол-во связей - 18 встречается 2125 раз кол-во связей - 20 встречается 894 раз кол-во связей - 21 встречается 304 раза
Особенности результатов решения :
-число минимумов - 4 (из них первый глобальный);
-наилучший минимум (глобальный) дает 12 межблочных соединений с
вероятностью 0,67;
-второй (локальный) дает 18 межблочных соединений с вероятностью 0,21;
-третий (локальный) дает 20 межблочных соединений с вероятностью 0,09;
-четвертый (локальный) дает 21 межблочное соединение с вероятностью 0,03;
-отношение числа связей наихудшего минимума к числу связей
наилучшего - 1,75
-вероятность появления каждого последующего минимума убывает монотонно.
Контрольный пример №3
Исходные данные: количество элементов = 12 количество блоков = 2
количество элементов в блоке 1 = 6 количество элементов в блоке 2 = 6 количество начальных распределений = 10000 матрица связей:
|
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
10 |
11 |
12 |
1 |
0 |
0 |
0 |
2 |
0 |
0 |
5 |
0 |
3 |
0 |
0 |
0 |
2 |
0 |
0 |
2 |
0 |
0 |
0 |
6 |
0 |
0 |
0 |
0 |
0 |
39
3 |
0 |
2 |
0 |
0 |
0 |
0 |
0 |
4 |
0 |
0 |
0 |
0 |
4 |
2 |
0 |
0 |
0 |
0 |
0 |
3 |
0 |
4 |
0 |
4 |
0 |
5 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
2 |
0 |
0 |
2 |
4 |
6 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
3 |
0 |
4 |
7 |
5 |
6 |
0 |
3 |
0 |
0 |
0 |
0 |
0 |
0 |
2 |
0 |
8 |
0 |
0 |
4 |
0 |
2 |
0 |
0 |
0 |
0 |
5 |
0 |
0 |
9 |
3 |
0 |
0 |
4 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
10 |
0 |
0 |
0 |
0 |
0 |
3 |
0 |
5 |
0 |
0 |
0 |
2 |
11 |
0 |
0 |
0 |
4 |
2 |
0 |
2 |
0 |
0 |
0 |
0 |
0 |
12 |
0 |
0 |
0 |
0 |
4 |
4 |
0 |
0 |
0 |
2 |
0 |
0 |
Результаты оптимизации: Наилучшая матрица распределения
Блок N1 с элементами:(2)(9)(4)(7)(1)(11) Блок N2 с элементами:(5)(10)(3)(8)(6)(12)
Наименьшее количество межблочных соединений при данном распределении=4
кол-во связей - 4 встречается 7520 раз кол-во связей - 17 встречается 1382 раз кол-во связей - 21 встречается 1098 раз
Особенности результатов решения :
-число минимумов - 3 (из них первый глобальный);
-наилучший минимум (глобальный) дает 4 межблочных соединения с
вероятностью 0,75;
-второй (локальный) дает 17 межблочных соединений с вероятностью 0,14;
-третий (локальный) дает 21 межблочное соединение с вероятностью 0,11;
-отношение числа связей наихудшего минимума к числу связей наилучшего - 5,25
-вероятность появления каждого последующего минимума убывает монотонно.
Контрольный пример №4
Исходные данные: количество элементов = 12 количество блоков = 4
количество элементов в блоке 1 = 3
40
количество элементов в блоке 2 = 3
количество элементов в блоке 3 = 3
количество элементов в блоке 4 = 3
количество начальных распределений = 1000
матрица связей:
|
1 |
2 |
3 |
4 |
5 |
|
6 |
7 |
8 |
9 |
10 |
11 |
12 |
|
1 |
0 |
4 |
1 |
0 |
0 |
|
2 |
0 |
0 |
1 |
0 |
1 |
0 |
|
2 |
4 |
0 |
0 |
0 |
0 |
|
2 |
0 |
1 |
0 |
0 |
1 |
1 |
|
3 |
1 |
0 |
0 |
3 |
1 |
|
0 |
1 |
0 |
1 |
1 |
0 |
0 |
|
4 |
0 |
0 |
3 |
0 |
1 |
|
0 |
1 |
0 |
1 |
1 |
0 |
1 |
|
5 |
0 |
0 |
1 |
1 |
0 |
|
0 |
4 |
3 |
0 |
1 |
0 |
0 |
|
6 |
2 |
2 |
0 |
0 |
0 |
|
0 |
0 |
0 |
0 |
0 |
4 |
0 |
|
7 |
0 |
0 |
1 |
1 |
4 |
|
0 |
0 |
1 |
0 |
0 |
0 |
1 |
|
8 |
0 |
1 |
0 |
0 |
3 |
|
0 |
1 |
0 |
0 |
3 |
0 |
4 |
|
9 |
1 |
0 |
1 |
1 |
0 |
|
0 |
0 |
0 |
0 |
3 |
3 |
0 |
|
10 |
0 |
0 |
1 |
1 |
1 |
|
0 |
0 |
3 |
3 |
0 |
1 |
0 |
|
11 |
1 |
1 |
0 |
0 |
0 |
|
4 |
0 |
0 |
3 |
1 |
0 |
1 |
|
12 |
0 |
1 |
0 |
1 |
0 |
|
0 |
1 |
4 |
0 |
0 |
1 |
0 |
|
Результаты оптимизации: |
|
|
|
|
|
|
|
|
|
|||||
Наилучшая матрица распределения |
|
|
|
|
|
|
|
|||||||
Блок N1 |
с элементами:(12)(4)(3) |
|
|
|
|
|
|
|
||||||
Блок N2 |
с элементами:(10)(9)(11) |
|
|
|
|
|
|
|
||||||
Блок N3 |
с элементами:(8)(5)(7) |
|
|
|
|
|
|
|
||||||
Блок N4 |
с элементами:(2)(1)(6) |
|
|
|
|
|
|
|
||||||
Наименьшее количество межблочных соединений при данном распределении =
28
кол-во связей - 28 встречается 499 раз кол-во связей - 30 встречается 323 раз кол-во связей - 31 встречается 106 раз кол-во связей - 32 встречается 42 раза кол-во связей - 33 встречается 30 раз Особенности результатов решения :
-число минимумов - 5 (из них первый глобальный);
-наилучший минимум (глобальный) дает 28 межблочных соединений с
вероятностью 0,50;