Итерационные алгоритмы улучшения начального размещения

В качестве исходных данных выступает некоторое начальное размещение. ρ₀ - первичное размещение, F₀ = F(ρ₀) - критерий (меньше - лучше) первоначального размещения.

F(P₁)> F(P₂)>… > F(P_k) – варианты размещений, упорядоченные по возрастанию критерия оптимальности размещения. Если представить в виде графика, то получим:

Алгоритм:
1. Преобразование очередного размещения. Необходимо определить подмножество размещений, в котором ищется оптимальное размещение. Варианты правил получения подмножеств:
а) Модули обмениваются своими местами
б) Местами обмениваются группы модулей
в) Используются пустые позиции
2. Рассчитывается функция критерия размещения F(ρ_тек). Выбирается лучший вариант:
а) Если новый вариант приводит к улучшении критерия (F_i < F_i-1), то данный вариант немедленно фиксируется и осуществляется переход к п. 1
б) Оценивается все подмножество размещений и выбирается наилучшее
3. Правило остановки: если (F_k - F_k+1) / F_k ≤ δ, то процесс прекращается.

Постановка задачи трассировки соединений. Критерии.

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

Критерии:
1. Минимальная суммарная длина всех проводников
2. Минимум пересечений соединений
3. Минимум изгибов проводников
4. Минимум числа слоев и переходов
5. Минимальная длина параллельных участков соседних проводников
6. Равномерное распределение проводников по монтажной плоскости

Все соединения должны быть разведены.
Каждому критерию f_i дается весовой коэффициент значимости λ_i. Мультипликативная оценка: F = Σf_iλ_i по всем критериям.