Software & Systems

Многие задачи автоматизации проектирования решаются на основе эволюционного моделирования и генетического поиска (Емельянов В.В., Курейчик В.В., Курейчик В.М. Теория и практика эволюционного моделирования. М.: Физматлит, 2003; Гладков Л.А., Курейчик В.В., Курейчик В.М. Генетические алгоритмы. Р-н-Д: Ростиздат, 2004). Генетический поиск с точки зрения преобразования информации – это последовательное преобразование одного конечного нечеткого множества альтернативных решений в другое. Само преобразование называется алгоритмом поиска, или генетическим алгоритмом (ГА). В основе ГА лежит случайный, направленный или комбинированный поиск. Целью работы является анализ путей и методов повышения скорости работы ГА при построении связывающих деревьев на этапе проектирования. Авторы предлагают новые архитектуры параллельного генетического поиска, позволяющие в отличие от стандартных и существующих ГА частично решать проблему предварительной сходимости алгоритмов построения деревьев Штейнера и повышать скорость обработки информации, не ухудшая качества решений.

Важным вопросом в автоматизации проектирования является построение минимальных связывающих деревьев цепей электрических схем. Основная задача формулируется следующим образом: по заданной схеме соединений проложить необходимые проводники на плоскости, чтобы реализовать заданные электрические соединения с учетом заранее заданных ограничений. Основными ограничениями являются ширина проводников и минимальные расстояния между ними (Naveed Sherwani. Algorithms for VLSI physical design automation. Second Edition. Kluwer Academic Publishers, Boston / Dordrecht / London, 1995).

Для решения этого вопроса используют алгоритмы построения минимальных покрывающих деревьев. Пусть имеется связный неориентированный граф G=(V,E), в котором V – множество контактов; E – множество их возможных соединений. Для каждого ребра графа G задан неотрицательный вес w(v1,v2) (длина провода, необходимого для соединения u и v). Задача состоит в нахождении подмножества , связывающего все вершины, для которого суммарный вес  минимален. Такое подмножество T можно считать деревом (в любом цикле один из проводов можно удалить, не нарушая связности). Связный подграф графа G, являющийся деревом и содержащий все его вершины, называют покрывающим деревом этого графа. Пусть разрешается вводить произвольное количество дополнительных вершин и соединяющих их ребер. Решение приводит к построению дерева Штейнера, а дополнительные вершины называются точками Штейнера. Построение дерева Штейнера является NP-трудной задачей. В общем виде данная задача формируется так: для заданных x1, x2,…, xn точек плоскости построить минимальное покрывающее дерево с n¢ ≥ n вершинами.

Перспективным классом алгоритмов при построении таких деревьев является эволюционное моделирование. Проведен анализ существующих ГА построения дерева Штейнера для этапов трассировки СБИС. Перспективным для трассировки является метод эволюционного моделирования (Калашников Р.С., Курейчик В.В. Построение дерева Штейнера методом эволюционного моделирования. Тр. Междунар. науч.-технич. конф. «Интеллектуальные системы (IEE AIS’04)» и «Интеллектуальные САПР (CAD-2004)». М.: Физматлит, 2004). Методика кодирования альтернативных решений состоит в следующем. Битовые строки включают в себя информацию о координатах точек Штейнера. При этом каждый ген содержит информацию о некоторых метках, используемых для генерации точек Штейнера, и координатах точек Штейнера в одной из областей (частей), на которые разбит граф (множество точек на координатной плоскости). Достоинство этого метода состоит в исключении получения циклов в графе и в отсутствии проблем при декодировании хромосомы (альтернативного решения). Временная сложность алгоритма зависит от выбора алгоритма оценки целевой функции. В данном случае оценка целевой функции хромосомы производится с помощью алгоритма Прима-Крускала и равна O(|N|2).

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

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

·                Множество вершин разбивается произвольным образом на области. При этом в каждой области количество точек n находится в интервале 3≤n≤K. Параметр K является входным параметром алгоритма и задается пользователем.

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

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

·                Проводится соединение вершин и точек любым эвристическим методом таким образом, чтобы в результате соединения получилось ортогональное минимальное покрывающее дерево.

·                Проводится кодирование полученного дерева Штейнера модифицированным методом. Каждое решение содержит информацию о координатах точек Штейнера в  своей области.

Затем члены популяции подвергаются репродукции, скрещиванию, мутации.

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

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

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

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

Алгоритм реализован в виде программы на языке С++ в Borland Buider 5.0 и рассчитан на функционирование в среде Windows XP. В ходе проведения вычислительного эксперимента были установлены эмпирические зависимости, диапазоны изменения входных параметров и выработан ряд рекомендаций по их оптимальному выбору. Проведено сравнение трех классических алгоритмов (Калашников Р.С. Экспериментальные исследования комбинированного эвристического алгоритма построения дерева Штейнера, основанного на методе эволюционного поиска, для этапа глобальной трассировки. // Изв. ТРТУ, 2004, №3). Результаты их исследования представлены в таблице.

Алгоритм T. Barreraх
Количество точек	ЦФ	Улучшение %	Время работы, сек
50	1738	3,98	50,85
60	1952	2,40	92,34
70	2139	3,30	130.48
80	2227	1,81	198,74
90	2320	0,68	285,47
100	2396	1,24	400,17
Алгоритм Jones J.
50	1794	6,41	53,72
60	1934	3,30	98,98
70	2151	2,76	154,38
80	2179	3,92	216,96
90	2327	0,39	318,75
100	2385	1,69	432,83
Комбинированный ГА
50	1697	7,24	42,40
60	1910	4,50	67,91
70	2140	3,25	107,83
80	2174	4,14	161,91
90	2286	2,14	226,55
100	2375	2,10	299,20

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

Результаты вычислительного эксперимента позволяют говорить о преимуществе рассмотренного алгоритма для решения задачи построения деревьев Штейнера. Временная сложность настоящего алгоритма в лучшем случае »O(nlogn), а О(n3) – в худшем случае.