451
Задача размещения элементов вторичного ис-
точника питания является NP-полной. Получение
точного решения NP-полной задачи за полиномиаль-
ное время невозможно. Для нахождения оптималь-
ного, приемлемого решения NP-полных задач ис-
пользуются эвристические алгоритмы.
В настоящей работе, для решения задачи, пред-
лагается использовать разновидность эвристических
алгоритмов – генетический алгоритм (ГА).
Алгоритм решения задачи размещения
ГА моделируют естественный эволюционный
процесс с учётом изменчивости, наследования и от-
бора, осуществляя случайно-направленный поиск
решения.
Достижение лучшего, чем случайный поиск,
способа отыскания решения с помощью ГА заключа-
ется в подборе структуры кодирования информации
о решаемой задаче, выборе генетических операторов
(ГО) и определении их параметров.
Решением задачи размещения является список
координат размещаемых элементов.
Непосредственное кодирование координат в
хромосоме после применения ГО, производящих
случайные изменения приведёт к образованию не-
легальных решений, в которых отдельные элемен-
ты будут накладываться друг на друга. Структурой
кодирования, лишённой этого недостатка является
перестановка, то есть n-арное кодирование, где n
– количество размещаемых элементов. Решение за-
дачи – размещение элементов определяется поряд-
ком их следования, координаты вычисляются при-
менением однозначных правил нахождения точки
установки текущего элемента.
Предлагается использовать следующие ГО [6]:
кроссовер порядка, инверсию и мутацию.
Кроссовер порядка случайным образом выбира-
ет в паре родительских хромосом точку деления.
Часть родительских генов, расположенная до точки
деления переходит к потомку. Остальная часть хро-
мосомы потомка, после точки деления, заполняется
недостающими в первой части хромосомы генами в
порядке их следования в хромосоме второго родите-
ля (рис. 1).
Оператор инверсии случайным образом приме-
няется к генам потомков, расположенным после точ-
ки деления. Он изменяет соответствующую позицию
гена, отвечающую за горизонтальную или верти-
кальную ориентацию размещаемого элемента.
Оператор мутации случайным образом выбирает
в хромосоме потомка два гена и меняет их местами.
При конструировании печатных плат с разнога-
баритными навесными элементами позиции для эле-
ментов заранее не фиксированы и определяются по-
сле трассировки соединений[5]. Поэтому удобно
представить размещаемый элемент зоной размеще-
ния элемента, размеры которой связанны с техноло-
гическими условиями монтажа и температурным
режимом функционирования элемента.
Рис. 1. Работа генетического оператора кроссовер
порядка: a – хромосомы родители; b – хромосомы
потомки; c – ген; d – точка деления; e – группа генов
родителей, сохраняющая порядок следования
элементов в хромосоме потомка; f – группа генов
недостающих в хромосоме потомка, заполняющих
оставшуюся часть хромосомы потомка.
Пространство размещения представляется пря-
моугольником, на котором задана декартова система
координат [7]. По оси x расположена ширина комму-
тационного пространства. Элементы размещаются
рядами, от начала координат, вдоль оси x. Площадь
пространства превышает суммарную площадь раз-
мещаемых элементов на определенную величину,
характеризующую плотность размещения элементов.
Начальная популяция формируется случайным
образом, в неё отбираются варианты размещения,
полученные в соответствии с правилами нахождения
точки установки текущего элемента и не выступаю-
щие за пределы коммутационного пространства по
оси y. Количество хромосом в начальной популяции
должно превышать количество размещаемых эле-
ментов и быть чётным.
Правила нахождения точки установки текущего
элемента исключают возможность наложения эле-
ментов и служат минимизации незадействованной
площади пространства размещения.
Критерии размещения
При решении задачи размещения элементов
ВИП эффективно выделение главного критерия.
Критерии выстраиваются в порядке приоритета по
степени возможности преодоления создаваемых ими
ограничений на реализацию устройства конструк-
торско-технологическими средствами. Все критерии
осуществляют лишь предварительную оптимизацию
связанных с ними параметров. По отношению к ре-
шаемой задаче порядок критериев будет следующий:
критерий ЭСМ, критерий осуществимости после-
дующей трассировки и критерий тепловой совмес-
тимости.
В результате работы алгоритма отбирается
группа лучших решений по главному критерию.
Размер группы зависит от количества элементов
схемы и априорной оценки диапазона погрешности
критерия. Для этих решений вычисляется следую-
щий по приоритету критерий и выбирается группа
лучших. И так далее до последнего критерия [3].