Оптимизация размещения равногабаритных элементов РЭА модифицированным методом покоординатного спуска
Рассматривается задача оптимального размещения элементов электрических и электронных цепей. В качестве критерия выбран минимум взвешенной длины соединений. Предложен вычислительный метод, являющийся модификацией метода покоординатного спуска и одним из вариантов общего подхода на основе парных перестановок. Схема задана матрицей соединений. Рассматривается фиксированный набор позиций элементов и матрица расстояний на основе ортогональной метрики. Данная задача является вариантом общей математической модели, получившей название задачи квадратичного назначения. Геометрическое ограничение задачи - в одной ячейке размещается не более одного элемента. Констатировано, что подходы на основе парных и т.п. перестановок является экономичными, а метод функции штрафа приводит к "забуриванию" и малоэффективен. Описан модифицированный метод покоординатного спуска, являющийся вариантом метода парных перестановок, в котором пары выбираются на основе метода покоординатного спуска. В предложенном варианте метода покоординатного спуска на одном этапе вычислений меняются одновременно две координаты (а не одна, как в обычном методе оптимизации) - по одной из координат делается обычный пробный шаг, а по другой - корректировка, возврат в допустимую область. Далее вычисляется значение целевой функции в найденной точке и сравнивается с достигнутым ранее значением. Если произошло улучшение значения, то найденная точка становится новой стартовой. Иначе делается шаг по другой координате с одновременной корректировкой вектора номеров позиций элементов (возврат в допустимую область). Опыт применения модифицированного метода при решении задачи размещения элементов ЭВА показал его значительные преимущества по сравнению с другими известными методами, например, генетическим алгоритмом, а также методом штрафных функций. Рассмотрен пример вычислений предложенным методом. Матрица соединений была задана аналитически. Вначале осуществлялся поиск начального приближения методом Монте-Карло (10 000 итераций), после чего начинались вычисления локального оптимума модифицированным методом покоординатного спуска в пространстве перестановок без повторений (задавалось ограничение в 100 итераций). Начальное значение шага по координате равно размеру перестановки, далее на каждой итерации оно уменьшалось на 1 до минимально возможного значения равного 1. Преимуществом метода является отсутствие функции штрафа. Поиск автоматически осуществляется в пространстве перестановок без повторений. Вычислительные эксперименты показали высокие вычислительные качества предложенного метода.