Алгоритм и программа трассировки цепей различной ширины

Материалы Международной конференции

“Интеллектуальные САПР”

УДК 681.3.001.63

А.В. Бородулин

АЛГОРИТМ И ПРОГРАММА ТРАССИРОВКИ ЦЕПЕЙ РАЗЛИЧНОЙ

ШИРИНЫ

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

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

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

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

УДК 658.512

Л.А. Гладков, АЛ. Гулевич ПРОГРАММНЫЙ КОМПЛЕКС ДЛЯ ГЕНЕРАЦИИ И ИССЛЕДОВАНИЯ НЕОРИЕНТИРОВАННЫХ ГРАФОВ “NEWGRAPH”

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

Для реализации поставленной задачи в среде программирования Borland C++ Builder для Windows’95 был создан программный комплекс “NEWGRAPH”, позволяющий выполнять быстрое построение графовой модели и её тестирование без выхода из основного редактора. Данный комплекс позволяет выполнять обширный набор стандартных операций с графами, проводить тестирование и самотестирова-.

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