�ݺ�ߣ

Казанский государственный технический университет им. А.Н. Туполева
Факультет технической кибернетики и информатики
Направление 210200 «Проектирование и технология электронных средств»
Дисциплина «Информационные технологии электромагнитной совместимости ЭС»

Лекция №34 «Оптимизация внутриаппаратурной
электромагнитной совместимости межсоединений
цифровых печатных плат»

Автор - Чермошенцев С.Ф.

Казань 2008

Оптимизация внутриаппаратурной электромагнитной
совместимости межсоединений цифровых печатных
плат

1. Формулировка задачи оптимизации внутриаппаратурной ЭМС
межсоединений цифровых печатных плат.
2. Генетические алгоритмы.
3. Задачи, эффективно решаемые с помощью генетических алгоритмов.
4. Принцип работы генетического алгоритма.

1. Формулировка задачи оптимизации
внутриаппаратурной ЭМС межсоединений
цифровых печатных плат.
Моделирование электромагнитных процессов в межсоединениях цифровых
печатных плат становится актуальным, когда длительность фронта сигнала элемента
составляет наносекунды и электрическая длина проводника соизмерима с длиной
волны сигнала. Интуитивное решение проблемы задержек сигналов,
искажений и
отражений – это уменьшение длины межсоединений и, следовательно, увеличение
плотности проводников на плате. Однако увеличение плотности способствует
возникновению перекрестных помех между соседними проводниками. Разработчик
должен принять компромиссное решение при конструировании печатной платы [297].
Для реальных цепей связь между большим количеством параметров
межсоединений и критериями разработки печатной платы становится особенно
сложной. Поэтому необходим оптимизационный подход, при котором рассчитывались
бы параметры межсоединений при проектировании всей цепи на печатной плате.
Многопроводные линии передач используются как простейшие элементы в
межсоединениях печатных плат. Традиционная модель межсоединения базируется на
предположении
о
распространении квази-ТЕМ волны в проводнике. С учетом
этого допущения многопроводную линию передачи можно описать системой
дифференциальных уравнений в частных производных во временной области или
системой обыкновенных дифференциальных уравнений в частотной области.

Существует несколько методов
решения
подобных
уравнений:
метод нормальных
волн во временной области и частотной области, метод
продвижения во времени и метод функций Грина. По сравнению с другими
методами, метод пошагового продвижения во времени позволяет анализировать
цепи с нелинейными элементами, исследовать межсоединения с потерями, прост
при программной реализации и хорошо совмещается с этапом схемотехнического
проектирования цифровых печатных плат. Ниже в анализе электромагнитных
процессов
в межсоединениях печатных плат применяется именно метод
продвижения во времени (раздел 2.2).
Поперечное
сечение
многопроводной
линии
передачи с N
межсоединениями может быть представлено матрицами (N×N): погонных
индуктивностей [L], погонных сопротивлений [R], погонных коэффициентов
электростатической индукции [B] и погонных проводимостей [G]. Эти матрицы
параметров межсоединений вычисляют по физико-геометрическим параметрам
печатной платы, используя либо эмпирические формулы, либо методы анализа
квазистатических полей (раздел 2.1).
Предположим, что вся цепь печатной платы состоит из подсетей. Типичная
подсеть – это многопроводная линия передачи. Пусть эти подсети разбиты на
группы, и внутри каждой группы разные линии передач имеют одинаковую
толщину, ширину и физические параметры, но могут отличаться длиной. Число
физико-геометрических параметров для многопроводной линии передачи гораздо
меньше числа её электрических параметров, поэтому эффективная оптимизация
отклика межсоединения может строиться через изменение геометрических
параметров проводников.

Пусть сигнал имеет трапецеидальную форму с длительностью импульса Т и
переднего фронта tфр. Вектор Φ – вектор проектных параметров, он включает в себя
ширину проводника, расстояние до слоя земли, длину проводника, расстояние до
соседнего проводника и т.д. Обозначим Vj(Φ, t) – отклик в точке j межсоединения в
момент времени t; J1 – список, содержащий все точки цепи, в которых существует
требуемый сигнал; J2 – список, содержащий все точки цепи, в которых сигнал
отсутствует. Другими словами, если точка j⊂ J1, то точка находится на пути
распространения полезного сигнала, а в случае j⊂ J2, точка лежит вне пути
распространения сигнала. Предположим, что задержка распространения сигнала в
межсоединении τj – время, за которое сигнал достигает порогового значения в точке j.
Благодаря интерференционным эффектам в межсоединениях отклик может возрастать
(падать) гораздо медленнее, чем сигнал
элемента-источника. Наличие
нежелательного сигнала (перекрестной помехи) в точках j⊂J2 обусловлено
существованием электромагнитной связи между проводниками. Предположим,
Vj(Ф, t) – наибольшая величина (амплитуда) перекрестной помехи в точке j⊂J2 в
момент времени t, 0<t<∞. Задача оптимизации заключается в том, чтобы найти
минимум τj(Ф,t) при j⊂J1 и минимум Vj(Ф,t) при j⊂J2 в области допустимых значений
вектора проектных параметров Ф.

2. Генетические алгоритмы.
В данной работе предлагается оптимизация внутриаппаратурной ЭМС
межсоединений печатных плат цифровых ЭС генетическими алгоритмами.
Генетические алгоритмы – мощная стратегия выходов из локальных оптимумов.
Она заключается в параллельной обработке множества альтернативных решений с
концентрацией поиска на наиболее перспективных из них. Генетические алгоритмы
позволяют одновременно анализировать некоторое подмножество решений, формируя
квазиоптимальные решения. Кроме того, применение данного способа оптимизации
обусловлено тем, что генетические алгоритмы наиболее эффективно работают с
многопараметрическими функциями, позволяя манипулировать одновременно многими
переменными.
Генетический алгоритм – это оптимизационный эвристиче-ский алгоритм,
основанный на принципах естественной генетики. Генетические алгоритмы берут
начало в теории эволюции [21, 87, 122, 123, 124, 125]. Основ-ной механизм эволюции –
это естественный отбор. Те особи, которые наиболее приспособлены к окружающим
условиям, будут иметь относительно больше шансов воспроизвести потомков. Слабо
приспособленные особи либо совсем не произведут потомства, либо их потомство
будет очень немногочисленным. Это означает, что гены от высоко адаптированных или
приспособленных особей будут распространяться в увеличивающемся числе потомков
на каждом последующем поколении.

Комбинация хороших характеристик от различных родителей иногда может приводить
к появлению "суперприспособленного" потомка, чья приспособленность больше, чем
приспособленность любого его родителя. Таким образом, вид развивается, все лучше
приспосабливаясь к среде обитания.
Генетические алгоритмы позволяют осуществлять поиск оптимальных решений для
целого ряда практических задач [120]. Широта сферы применения генетических
алгоритмов обусловлена, прежде всего, их универсальностью, а также способностью
одновременно оптимизировать решение задачи по нескольким критериям. Эта
способность нашла свое применение в большом числе приложений, включая
проектирование самолетов, настройку параметров алгоритмов, поиск устойчивых
состояний систем нелинейных дифференциальных уравнений.
Анализ результатов использования генетических алгоритмов позволяет выделить
следующие условия, при выполнении которых задача решается эффективно:
большое пространство поиска, ландшафт которого является негладким (содержит
несколько экстремумов);
– сложно формализуемая функция степени оценки качества решения;
– многокритериальность поиска;
– поиск по заданным критериям оптимального решения.
Генетические алгоритмы [41, 124] – это методы нулевого порядка, стратегия поиска
в которых построена только на вычислении значений критерия оптимальности и
не требует знания дополнительной информации о производных, константе Липшица и
т.д., что характерно для градиентных и квазиньютоновских методов. Генетические
алгоритмы являются робастными методами по отношению к виду минимизируемой
функции, так как при их применении не требуется, чтобы критерий оптимальности был
непрерывным, дифференцируемым, унимодальным. Они осуществляют поиск
оптимального решения по одной и той же стратегии как для унимодальных, так и для
многоэкстремальных функций.

3. Задачи, эффективно решаемые с помощью генетических алгоритмов.
Таблица 1
Применение генетических алгоритмов в ряде отраслей
Сфера применения, отрасль

Назначение

Промышленность

Самообучение и самоэволюционирование в интеллектуальных
промышленных системах

Металлургическая
промышленность

Планирование непрерывного литья

Энергетика

Оптимизация энергетических систем

Микроэлектроника

Оптимизирующий модуль для настройки DSP контроллера

Кораблестроение

Настройка режима скольжения и маневрирования подводной лодки

Экономика и финансы

Машинное обучение в финансовых прогнозах

Игры (роботы-футболисты),
гонки

Генетическое планирование и нечеткая коррекция на основе зрительной
информации для планирования пути

Электротехника [116]

Оптимизация характеристик электротехнических устройств

СВЧ техника [150]

Параметрический синтез антенн и устройств СВЧ

Управление космическими
аппаратами [217]

Оптимизация управления космическими аппаратами

4. Принцип работы генетического алгоритма.
Рассмотрим принцип работы генетического алгоритма (рис. 6.1) [294].
Вначале формируется множество потенциальных решений (гипотез), которое
представляет собой начальную популяцию. В большинстве случаев это множество
формируется случайно. После того как создана начальная популяция, выполняем
процедуры скрещивания и мутации. Скрещивание моделирует передачу
наследственности хромосомами. Эта операция обусловливает целенаправленное
закономерное "приближение" свойств хромосом к оптимальному решению. При
скрещивании хромосомы группируются в пары, случайным образом выбирается одна
точка (ген) на хромосоме и хромосомы обмениваются между собой выбранными генами.
Целью оператора скрещивания [106] является порождение из имеющегося
множества решений нового, в котором каждая хромосома будет являться потомком
некоторых двух элементов предыдущей популяции, т. е. нести в себе частично
информацию каждого родителя. Заметим, что оператор скрещивания (кроссинговер)
может применяться не ко всем представителям популяции. Задается некоторая
вероятность pс – вероятность скрещивания и алгоритм выбора пары родителей для
скрещивания. Конкретное значение pс зависит от решаемой задачи, о чем говорят и
встречающиеся в литературе оценки типа pс≈0,6 и pс∈[0,75;0,95] в работе [106], pс ≈ 0,95
[384]. Для нашей задачи выбираем вероятность скрещивания pс∈[0,8;0,9].

Начало
Создание
популяции

Скрещивание
Мутация
Вычисление
функции
пригодности
Создание
новой
популяции

–

Заканчивать
оптимизацию?

+
Выход

Рис. 6.1. Схема генетического
алгоритма

Стоит отметить, что на сегодняшний день создано множество вариантов
оператора скрещивания. В то же время их все можно разделить на два класса в
зависимости от решаемой задачи. А именно тип применяемого скрещивания зависит
от того, решается ли задача, когда работа ведется со строками конечной длины, или
приходится иметь дело с некоторыми подстановками.
Классическим вариантом оператора скрещивания является одноточечное
скрещивание, при котором случайным образом выбирается число m∈{1,…,L-1}, где L
– размер хромосомы, называемое точкой скрещивания или точкой разрыва, и все
гены, начиная с m+1 до L включительно, переставляются у выбранных хромосом.
Также известны теоретические исследования одноточечного скрещивания [390] на
основе введения понятия схемы Schemata, которая является шаблоном,
описывающим подмножество представителей популяции, имеющих одинаковые
значения некоторых генов.
Известны исследования генетических алгоритмов с применением n-точечного
скрещивания [390]. При таком способе случайно выбираются n точек разрыва, что
приводит к разбиению исходных векторов на n+1 частей различной длины. Далее
предлагается обменять у исходных хромосом участки с четными номерами, а
участки с нечетными номерами оставить без изменений. Де Янг [106] в своих
исследованиях заметил, что двухточечное скрещивание разрушает “длинные” схемы
с меньшей вероятностью, чем одноточечное. И вообще n-точечное скрещивание с
меньшей вероятностью разрушает схемы при четном n, чем при нечетном.
Дальнейшие исследования также показали, что для ряда проблем более
эффективным оказывается использование нескольких точек скрещивания.

Одним из вариантов данного вида скрещивания является равномерное
скрещивание, предложенное в работе [423]. При этом случайным образом создается
маска скрещивания, представляющая собой строку из нулей и единиц длины L.
Далее выбираются два представителя популяции (родители), и два новых решения
(дети) получаются по следующему правилу. Единица на i-й позиции в маске
скрещивания означает, что элемент, стоящий на том же месте у первого родителя,
необходимо поместить на i-е место первого ребенка. Нуль на i-й позиции в маске
скрещивания означает, что элемент, стоящий на том же месте второго родителя,
необходимо поместить на i-е место первого ребенка. Теперь, если первого родителя
считать вторым, а второго – первым, то по описанному правилу можно получить
второго ребенка. Стоит отметить, что маска скрещивания может быть одна для всех
хромосом, либо своя для каждой пары родителей.
Эффективность применения равномерного скрещивания, при котором в среднем
L/2 битов меняются местами, показана в работе [423]. Автор сравнил вероятности
разрушения схем для одноточечного, двухточечного и равномерного скрещивания.
Интересно, что, хотя равномерное скрещивание более разрушительно для схем, чем
другие два вида оператора, вероятность разрушения схемы в данном случае не
зависит от длины схемы. Также автор показал, что равномерное скрещивание более
успешно конструирует представителей новых, более качественных схем из менее
качественных, чем одноточечное и двухточечное скрещивания. Однако вопрос о
предпочтении того или иного способа скрещивания остается открытым [106] и
решается каждый раз применительно к конкретной задаче.
Система скрещивания, в которой при образовании “родительской” пары
хромосомы выбираются только на основании информации об их количественных
признаках (например, степенях приспособленности), называется предпочтительным
скрещиванием [21].

В бинарном случае оператор мутации заключается в инвертировании символов
в случайно выбираемых позициях. В случае работы с конечным алфавитом случайно
выбираемый символ заменяется на какой-либо отличный от него. Оператор мутации
применяется не ко всем генам представителей популяции. Обычно изначально задается
вероятность мутации pm и некоторый алгоритм осуществления мутации, например,
следующий. Сначала нумеруются произвольным образом все представители исходной
популяции. Затем, начиная с первого гена первой хромосомы, просматривается вся
популяция, при этом выбираются случайные числа из полуинтервала [0,1). Если на
некотором шаге выбранное число оказывается меньше pm, то текущий ген
подвергается мутации.
Как и в случае со скрещиванием, конкретное значение pm зависит от решаемой
задачи, но чаще всего вероятность мутации имеет довольно малое значение.
Например, в литературе можно встретить оценки pm≈0,001 и pm∈[0,005;0,01] в работе
[106], pm≈0,01 в [384].
Однако следует отметить, что, скорее всего, вероятность мутации не должна
быть константой [106]. Роль оператора мутации резко возрастает, например, если
популяция ущербна в “генетическом” смысле. В этом случае скрещивание не дает
улучшения, и тогда мутация может помочь изменить ситуацию.
Далее проводим непосредственно мутацию (рис. 6.1), т.е. с некоторой
достаточно малой вероятностью случайно выбранный ген меняет своё значение. Эта
процедура позволяет избежать локального экстремума. Коэффициент мутации
показывает, какой процент хромосом будет участвовать в этой операции, и
определяется экспериментально. Этот коэффициент обычно рекомендуется равным
0,1…0,01 [296].

Чтобы оптимизировать структуру, используя генетический алгоритм, нужно задать
некоторую меру качества для каждой структуры в пространстве поиска. Для этой цели
используется функция пригодности. В окружающей нас живой природе в качестве меры
приспособленности индивидуума (живого организма) выступает вероятность того, что
он выживает в данной среде и размножается, давая определенное число потомков. В
искусственном мире математических алгоритмов для оценки их пригодности
(приспособленности) используются некоторые специальные показатели, на основании
числовых значений которых делаются выводы о необходимости развития популяции в
том или ином направлении путем отбора наиболее пригодных индивидуумов и
применения к ним упомянутых выше генетических операторов.
На практике в качестве функции пригодности индивидуума Si используется одна из
следующих четырех функций:
• “исходная” функция пригодности f(Si), определяемая в естественных терминах самой
решаемой задачи;
• “стандартизованная” (“смещенная”) функция пригодности;
• “модифицированная” функция пригодности;
• “нормализованная” функция пригодности.

Контрольные вопросы

1. Назовите основные допущения в задаче оптимизации внутриаппаратурной ЭМС
межсоединений печатных плат?
2. Перечислите элементы вектора проектных параметров?
3. Сформулируйте задачу оптимизации внутриаппаратурной ЭМС межсоединений
цифровых печатных плат?
4. Поясните основные особенности и преимущества генетических алгоритмов?
5. Перечислите условия при выполнении которых задача решается эффективно именно
генетическими алгоритмами?
6. Перечислите задачи и отрасли применения генетических алгоритмов?
7. Назовите основные этапы генетического алгоритма?
8. Поясните смысл и варианты реализации оператора скрещивания?
9. Каким образом обосновывается и выбирается схема скрещивания в задаче
оптимизации ЭМС ЭС?
10. Поясните содержание и значение оператора мутации?
11. Что характеризует коэффициент мутации и каково его рекомендуемое значение?

�ݺ�ߣ

лекция 34

Recommended

More Related Content

Viewers also liked (20)

Similar to лекция 34 (20)

More from student_kai (20)

лекция 34