Xl Туполевские чтения : всероссийская (с международным участием) молодежная научная конференция. Казань, 8-10 октября 2003 г., тезисы докладов. Т. 3

Алгоритм размещения разногабаритных конструктивных элементов на печатной плате С.Ю. Володин Научный руководитель: В.В. Воронова, к.т.н., доцент Казанский государственный технический университет им. А. Н. Туполева Данный метод основан на применении генетических алгоритмов. От оптимальности решения этой задачи зависит плошадь монтажного про- страннства, которая будет занята конструктивными элементами, и .следовательно, размеры и вес прибора. Кроме этого от полученного раз­ мещения зависит последующая трассировка. Оптимизация проводилась по двум критериям: минимизация суммарной взвешенной длины межсоеди­ нений и минимизация максимальной длины межсоединения. За основу взят принцип «гильотинного разреза». Решение задачи ко­ дируется четырьмя хромосомами: хромосома ХР1 кодирует структуру де­ рева разрезов, хромосома ХР2 определяет вид разреза, хранящийся в вер­ шине, ХРЗ - разметку листьев дерева (элементов), ХР4 - ориентацию эле­ мента на монтажном пространстве. Популяции новых решений получают­ ся благодаря тому, что операторы кроссинговера и хромосомной мутации применяются к трем наиболее приспособленным родительским парам, причем ХР2, ХРЗ и ХР4 подвергаются скрещиванию, а ХР1 подвергается хромосомной мутации в каждом поколении для каждой особи. Затем в расширенной популяции происходит удаление гомологичных особей (та­ ким образом, чтобы осталась только одна такая особь), так как они приво­ дят к остановке развития популяции. Вакантные места, получившиеся в ре­ зультате этого заполняются случайно сгенерированными особями. После этого происходит подсчет фитнесс-функции и упорядочивание особей по­ пуляции по ее убыванию. Решения с большими значениями фитнесса име­ ют большую вероятность стать родительскими парами. Таким образом в популяции по истечении некоторого числа итераций находятся оптималь­ ные или близкие к оптимальным решения. Использование ГА для этой задачи показало себя достаточно высо­ коэффективным. В случае оптимизации одногабаритных элементов алго­ ритм эффективнее известных методов на 20-40%. От предварительной сходимости удалось избавиться за счет заполнения вакантных мест в по­ пуляции после удаления гомологичных особей случайно сформированны­ ми особями. Следует добавить, что использование четырех хромосом при реше­ нии данной задачи позволяет сгенерировать и оценить любой возможный план разбивки печатной платы. Программа, реализованна в среде Delphi. 97