Трассировка на коммутационном пространстве
генетическим алгоритмом

Р.Р. Гумербаев



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

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

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

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

Известные алгоритмы трассировки печатных плат можно условно разбить на три большие группы:

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

Генетические алгоритмы - адаптивные методы поиска, которые в последнее время часто используются для решения задач функциональной оптимизации. Они основаны на генетических процессах биологических организмов: биологические популяции развиваются в течении нескольких поколений, подчиняясь законам естественного отбора и по принципу "выживает наиболее приспособленный" (survival of the fittest), открытому Чарльзом Дарвином. Подражая этому процессу генетические алгоритмы способны "развивать" решения реальных задач, если те соответствующим образом закодированы. Основные принципы генетичексого алгоритма были сформулированы Голландом (Holland, 1975), и хорошо описаны во многих работах. В отличие от эволюции, происходящей в природе, генетический алгоритм только моделируют те процессы в популяциях, которые являются существенными для развития. Точный ответ на вопрос: какие биологические процессы существенны для развития, и какие нет? - все еще открыт для исследователей.

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

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

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

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

В разработанной программе применяется один из видов генетических алгоритмов в совокупности с волновым алгоритмом Ли.

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

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

Литература:

  1. Емельянов В.В., Курейчик В.М., Курейчик В.В. Теория и практика эволюционного моделирования.-М.: ФИЗМАТЛИТ, 2003.-432 с.
  2. Курейчик В.М., Лебедев Б.К., Лебедев О.Б. Поисковая адаптация: теория и практика. -М.: ФИЗМАТЛИТ, 2006.- 272 с.
  3. Гладков Л.А., Курейчик В.В., Курейчик В.М. Генетические алгоритмы. - М.: ФИЗМАТЛИТ, 2006. -320 с.