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

31

Для данной схемы при следующем произвольном начальном распределении:

число соединений между блоками до оптимизации равно 44.

Результаты работы алгоритма парных перестановок при произвольном

начальном распределении, указанном выше; таковы:

Число соединений между блоками равно 12.

2

2

32

Результаты работы только алгоритма начального распределения

Число соединений между блоками равно 10

Результаты работы алгоритма парных перестановок с использованием алгоритма начального распределения:

33

Число соединений между блоками равно 5.

Результаты работы алгоритма полного перебора (глобальный оптимум):

Число соединений между блоками равно 5. (рис. 3.7.)

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

34

3.3. Исследование зависимости эффективности алгоритма парных перестановок от

исходных начальных распределений и пути повышения его эффективности

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

35

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

Поставленные задачи были нами решены.

1. Разработана программа оптимального распределения элементов с получением большого количества (1000-10000) исходных начальных распределений методом рандомизации;

Для создания начального распределения методом рандомизации была написана подпрограма, работающая следующим образом.

а) в цикле заполняем промежуточную матрицу именами элементов по возрастанию;

б) для введения случайного фактора выбора ячейки промежуточной матрицы подключаем процедуру RANDOMIZE языка PASCAL;

в) организуем цикл по проходу всех блоков и всех элементов в блоке.

В этом цикле промежуточной переменной q присваиваем случайное значение с помощью функции RANDOM языка PASCAL, имеющей в качестве параметра общее количество элементов в блоках, а затем увеличиваем значение q на 1, так как функция

RANDOM возвращает значение в пределах ( 0 <= возвращаемое значение < параметр ).

Если не увеличить значение переменной q на 1, то произойдет обращение к нулевому элементу промежуточной матрицы, который содержит ошибочную информацию и не произойдет обращение к последнему элементу матрицы, т.е. мы потеряем одно имя элемента из промежуточной матрицы, что приведет к ошибке.

г) далее организуем поиск в промежуточной матрице имен элементов, которые не равны нулю т.к. у нас нет элементов с именем 0, а в матрице могут находиться нули;

д) если найденное имя элемента не равно нулю, то присваиваем его элементу матрицы распределения;

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