Бионические алгоритмы многокритериального синтеза печатных плат электронных средств

И.В. Суздальцев,
ст. преп., м.н.с., iliasuzd@mail.ru,
 С.Ф. Чермошенцев
зав. каф., в.н.с., д.т.н., профессор, sapr@kai.ru,
КНИТУ-КАИ, г. Казань

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

 

This paper describes the developed genetic, ant colony and bee algorithms for solving the following printed circuit board (PCB) design multiobjective optimization problems:  PCB elements packaging  within modules,   irregularly shaped components placement on PCB,  and multilayer PCB routing. The results of the simulation experiments confirm that the bionic algorithms have the better convergence and better design decisions quality in comparison with another well-known algorithms used for multiobjective automated synthesis.

Введение

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

·      наличием значительного (от 5 до 10) числа критериев оценки качества проектных решений и ограничений задачи, что обусловлено наличием большого количества требований, предъявляемых к проектируемому объекту;

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

·      NP- сложностью задачи, при значительной мощности множества альтернативных проектных решений.

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

Широкое применение для решения различного рода практических задач, в последнее время получили бионические методы и алгоритмы. Ключевая идея бионических методов и алгоритмов основывается на имитации, в процессе поиска оптимального решения задачи, законов, механизмов и принципов, заимствованных из естественно-научных (биология, физика, химия) или гуманитарных (социология, культурология) дисциплин. Классификация бионических методов, в настоящее время, включает себя  алгоритмы, основанные на моделировании: законов эволюционного развития живой природы (эволюционные, генетические и коэволюционные алгоритмы);  поведения отдельных видов животных, насекомых, растений и бактерий (муравьиный, пчелиный, светлячковый, сорняковый, бактериальный алгоритмы; алгоритмы летучих мышей, косяков рыб, стаи птиц, прыгающих лягушек, растущих деревьев; а также алгоритмы кукушкиного, обезъяньего поиска; и прочие алгоритмы); физические законы (алгоритмы роя частиц, имитации отжига; гармонического, гравитационного, электромагнитного, стохастического диффузионного поиска и др.);  законы развития и поведения человеческого социума (культурный, меметический, миграционный алгоритмы и др.) [1]. В большинстве случаев, использование подхода, основанного на заимствовании общих принципов самоорганизации сложных систем живой и неживой природы, заложенных в основу бионических алгоритмов, оказывается весьма эффективным при синтезе сложных технических систем, что подтверждается результатами многочисленных научных исследований [1, 2, 3]. Данное обстоятельство создает необходимые научные основы (предпосылки) для проведения научных работ по разработке и исследованию эффективности применения бионических алгоритмов к решению задач многокритериального синтеза печатных плат электронных средств для достижения более качественных результатов проектирования.

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

1. Задачи многокритериального синтеза печатных плат электронных средств

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

ú  компоновка элементов электрических принципиальных схем по модулям;

ú  размещение разногабаритных элементов на печатных платах;

ú  трассировка межсоединений многослойных печатных плат.

Задача компоновки заключается в поиске оптимального распределения элементов электрической принципиальной схемы электронного устройства по конструктивным модулям (печатным платам) [4], с учетом следующих критериев:

·      минимума числа компонуемых модулей;

·      минимума связей между конструктивными модулями;

·      минимума внешних связей конструктивных модулей;

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

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

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

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

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

-     минимума суммарной взвешенной длины соединений;

-     равномерности тепловыделения компонентов по поверхности печатной платы;

-     максимума числа компонентов, размещаемых в одной зоне печатной платы и принадлежащих одному классу электромагнитной или тепловой совместимости;

-     минимума числа соединений, длина которых больше заданной;

-     минимума числа пересечений проводников.

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

Размещение элементов на печатной плате можно интерпретировать как задачу двумерной упаковки прямоугольных объектов на полубесконечную полосу [4], с учетом определенных критериев и ограничений.

При решении задачи трассировки определяется оптимальная конфигурация проводников в трехмерном монтажном пространстве многослойной печатной платы, с учетом следующих критериев:

·      минимума суммарной длины проводников;

·      минимума межслойных переходов; 

·      минимума числа изгибов проводников;

·      минимальной протяженности параллельных участков проводников; 

·      минимальной площади контуров, образованных межсоединениями на печатной плате;

·      равномерности распределения проводников на печатной плате;

·      минимума числа неразведенных трасс.

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

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

Математической моделью монтажного пространства печатной платы является граф трехмерной решетки. Тогда трассировку проводников на печатной плате рассматривают как задачу поиска оптимальных покрывающих деревьев в графе-решётки. Каждое дерево Штейнера соединяет некоторое подмножество вершин, расположенных в узлах графа-решетки и соответствующих эквипотенциальным контактным площадкам одной электрической цепи.

Для свёртки критериев в рассматриваемых задачах используется аддитивная целевая функция.

2. Эволюционные алгоритмы синтеза печатных плат электронных средств

Базовая идея эволюционных алгоритмов заключается в моделировании законов, механизмов и принципов эволюции организмов в живой природе [2, 3]. Альтернативное решение оптимизационной задачи в эволюционных алгоритмах  ассоциируется с биологической особью. Информация об альтернативном решении представляется в закодированной форме, в виде одной или нескольких хромосом. На первом шаге работы алгоритма, происходит формирование начального множества потенциальных решений (начальной популяции особей). Поиск оптимального решения в эволюционных алгоритмах отождествляется с процессом эволюционного развития особей и включает в себя итерационное выполнение процедур скрещивания, мутации и селекции. При выполнении процедуры скрещивания, особи популяции группируются в родительские пары. Из каждой пары родительских особей, с использованием процедуры скрещивания, образуются особи-потомки, т.е. новые потенциальные решения задачи. На следующем шаге эволюционного алгоритма, выполняется процедура мутации, в рамках которой происходит изменение генетической информации в хромосомах особей (модификация существующих альтернативных решений), что также позволяет получить новые потенциальные решения задачи. В рамках следующего шага эволюционного алгоритма происходит декодирование хромосом всех особей текущей популяции и оценка их приспособленности, в соответствии с критериями качества решений, определенными в условиях задачи. Для отбора особей в следующее поколение эволюции выполняется процедура селекции. Далее происходит повторное выполнение эволюционных процедур до тех пор, пока значение функции пригодности лучшей особи в популяции не будет оставаться неизменным на протяжении определенного числа последних поколений. Искомым решением задачи является особь, обладающая наилучшей степенью  приспособленности в последнем поколении эволюции.

В данной работе исследовалась эффективность применения эволюционных алгоритмов для решения задач компоновки  элементов электрических принципиальных схем по модулям и размещения разногабаритных элементов на печатных платах [5]. Формирование начальной популяции особей в рассматриваемых эволюционных алгоритмах происходит случайным образом, с использованием стратегии «дробовика». Для формирования родительских пар особей применяется оператор панмиксии. Отбор особей в следующее поколение эволюции происходит с использованием оператора элитной селекции.

В эволюционном алгоритме решения задачи компоновки хромосома X имеет структуру, представленную на  рис. 1.

Рис. 1. Структура хромосомы эволюционного алгоритма компоновки

Количество  генов  хромосомы X определяется количеством элементов в схеме электронного средства. Порядковый номер гена (i) в хромосоме указывает на номер элемента в схеме, а значение гена X[i] – номер конструктивного модуля, в котором располагается соответствующий элемент схемы.

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

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

Рис. 2. Структура хромосом эволюционного алгоритма размещения

Количество генов в хромосомах эквивалентно количеству размещаемых элементов. Первая хромосома особи эволюционного алгоритма представляет собой одномерный вектор целочисленных значений. Каждое значение гена X1[i] соответствует номеру размещаемого элемента и является уникальным в рамках одной хромосомы. Последовательность значений генов в первой хромосоме {X1[1], X1[2], … , X1[i], …, X1[n]} определяет порядок размещения элементов на печатной плате процедурой «блочного» декодера. В соответствии с данной процедурой каждый элемент занимает на печатной плате крайнюю левую вакантную позицию. Вторая хромосома имеет вид одномерного вектора булевых значений. Ген X2[i] - приобретает значение равное единице в том случае, если элемент c соответствующим номером X1[i] ориентирован на печатной плате горизонтально и нулевое значение в противном случае.

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

3. Муравьиные алгоритмы синтеза печатных плат электронных средств

Основная идея муравьиных алгоритмов заключается в моделировании поведения колонии муравьев, при поиске пути от муравейника к источнику пищи. В процессе работы алгоритма каждый муравей колонии осуществляет построение своего пути в графе поиска решений. При этом, выбор каждой последующей вершины в пути муравья происходит с использованием метода «колеса рулетки». Количество секторов колеса рулетки эквивалентно количеству непройденных вершин, смежных некоторой текущей вершине с номером current. Площадь  секторов «колеса рулетки» определяется величиной вероятности перехода муравья из текущей current в каждую смежную непройденную вершину графа, по формуле:

,           (1)

где: ρcurrent,j– текущий уровень феромона на ребре между вершинами current и j (начальный уровень феромона на всех ребрах графа принимается равным единице); υij– весовая характеристика ребра между вершинами current и j; α, β - весовые коэффициенты; pcurrent,j – вероятность перехода из текущей вершины current в j-ую вершину; Scurrent - множество вершин, смежных вершине current. Номер сектора, выпавшего при однократном повороте колеса рулетки, определяет номер следующей вершины в пути муравья. Наиболее вероятным является выбор сектора колеса рулетки, обладающего наибольшей площадью (соответствующего вершине с наибольшим значением величины pcurrent,j).

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

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

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

Муравьиный алгоритм трассировки [6]  осуществляет построение оптимального покрывающего дерева в трехмерном графе-решётки, моделирующим монтажное пространство многослойной печатной платы. Конфигурация искомого дерева определяет рисунок проводников печатной платы.

4. Пчелиные алгоритмы синтеза печатных плат электронных средств

Основная идея пчелиного алгоритма заключается в моделировании поведения медоносных пчел при поиске источников нектара. Источник с нектаром ассоциируется в пчелином алгоритме с потенциальным решением задачи. Информация о потенциальном решении, также как и в эволюционных алгоритмах, представляется в закодированной форме, в виде числового вектора. На первом шаге алгоритма происходит формирование источников нектара (потенциальных решений задачи) случайным образом. Число формируемых потенциальных решений равняется количеству пчел-разведчиков в рое. Полезность каждого потенциального решения оценивается некоторой величиной, определяемой в соответствии с критериями качества оптимизационной задачи. Все найденные источники нектара сортируются по величине их полезности. При этом выбираются лучшие и перспективные источники нектара. Оставшиеся источники нектара признаются неперспективными и исключаются из дальнейшего рассмотрения.

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

В работе исследовалась эффективность применения пчелиных алгоритмов для решения задачи компоновки элементов электрических принципиальных схем по модулям [7] и размещения разногабаритных элементов на печатных платах [8].

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

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

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

Кроме того, в работе проводились исследования зависимостей параметров эффективности бионических алгоритмов от значений их управляемых параметров (размерности начальной популяции особей, вероятности скрещивания, вероятности мутации, размерности колонии муравьев, роя пчел и др.). Также, при проведении вычислительных экспериментов, оценивалась величина изменения показателя качества результирующего решения задачи (устойчивость решения) при многократных запусках программы и неизменных исходных данных. На основании проведенных исследований предлагаются следующие выводы:

1.  Эволюционные алгоритмы превосходят  рассмотренные бионические (муравьиные, пчелиные), а также другие известные алгоритмы компоновки и размещения (последовательные, итерационные) на 5-7% по качеству результирующих решений. Однако, скорость сходимости эволюционных алгоритмов оказывается меньше, по сравнению с другими алгоритмами.

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

3.  Величина изменения показателя качества  результирующего решения при повторных запусках бионического алгоритма не превышает 3 %.

4.  Временная сложность бионических алгоритмов синтеза печатных плат электронных средств является полиноминальной функцией от размерности исходных данных и находится в пределах от O(n3) до O(n5).

Заключение

Таким образом, основными результатами данной работы являются:

1.  Сформулированы содержательные и математические постановки задач синтеза печатных плат электронных средств: компоновка элементов электрических принципиальных схем по модулям; размещение разногабаритных элементов на печатных платах; трассировка межсоединений многослойных печатных плат.

2.  Определен набор критериев и ограничений для задач синтеза печатных плат.

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

4.  Разработаны научно-исследовательские прототипы программных модулей синтеза печатных плат электронных средств, на основе бионических алгоритмов.

5.  Проведены вычислительные эксперименты  для оценки эффективности использования бионических алгоритмов для решения задач синтеза печатных плат электронных средств.

Основные результаты данной работы использовались при разработке математического и программного обеспечения системы автоматизированного проектирования печатных плат электронных средств [9, 10].

Литература

1.  Карпенко А.П. Современные алгоритмы поисковой оптимизации. Алгоритмы, вдохновленные природой: Учебное пособие. — М. : Изд-во МГТУ им. Н. Э. Баумана, 2014. — 446 с.

2.  Курейчик В.В., Курейчик В.М., Гладков Л.А., Сороколетов П.В. Бионспирированные методы в оптимизации. – М.: Физмалит, 2009. – 384 с.

3.  Скобцов Ю. А., Сперанский Д. В. Эволюционные вычисления: Учебное пособие. — М.: Национальный Открытый Университет «ИНТУИТ» 2012. — 331 с.

4.  Норенков И.П. Основы автоматизированного проектирования: Учебник для вузов  – М.: Изд-во МГТУ, 2006. – 442 с.

5.  Суздальцев И.В., Чермошенцев С.Ф., Богула Н.Ю. Эволюционные алгоритмы проектирования печатных плат цифровых электронных средств // Мягкие вычисления и измерения (SCM’2015): сб. докл. Межд. конф. -  СПб.: Изд-во СПбГЭТУ «ЛЭТИ», 2015.  Т. 1. C. 383-387.

6.  Никитин Т.О., Суздальцев И.В. Автоматизация трассировки печатных плат электронных средств с использованием муравьиного алгоритма // XXII Туполевские чтения (школа молодых ученых): сб. докл. Междунар. молодеж. науч. конф.– Казань.: Изд-во «Фолиант». С. 120-125.

7.  Потяшин П.О., Суздальцев И.В. Методика автоматизированной компоновки схем по модулям электронных средств с использованием пчелиного алгоритма// Поиск эффективных решений в процессе создания и реализации научных разработок в российской авиационной и ракетно- космической промышленности (АКТО-2014): сб. тр. Междунар. науч.-практ. конф. – Казань: Изд-во Казан. гос. техн. ун-та, 2014. – С. 141-145.

8.  Емелин П.В., Суздальцев И.В. Применение модифицированного роевого алгоритма для размещения разногабаритных электронных компонентов на печатной плате // Поиск эффективных решений в процессе создания и реализации научных разработок в российской авиационной и ракетно- космической промышленности (АКТО-2014): сб. тр. Междунар. науч.-практ. конф. – Казань: Изд-во Казан. гос. техн. ун-та, 2014. – С. 456-458.

9.  Суздальцев И.В., Чермошенцев С.Ф. Разработка системы автоматизированного проектирования печатных плат электронных средств, с использованием бионических алгоритмов // Системы проектирования технологической подготовки производства и управления этапами жизненного цикла промышленного продукта (CAD/CAM/PDM-2015): тр. Междунар. конф. - М.: Изд-во ИПУ им. В.А. Трапезникова РАН, 2015. C. 167-171.

10.  Суздальцев И.В., Макеев П.А. Технология автоматизированного проектирования печатных плат электронных средств на основе бионических методов // Новые технологии, материалы и оборудование российской авиакосмической отрасли (АКТО-2016): сб. докл. Всеросс. науч.-практ. конф. с Междунар. Участием. – Казань: Изд-во Академии наук РТ, 2016. – Т. 2. – С. 239-246.