Программный комплекс для генерации и исследования неориентированных графов Newgraph

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

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

УДК 681.3.001.63

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

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

ШИРИНЫ

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

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

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

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

УДК 658.512

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

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

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

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

Известия ТРТУ

Тематический выпуск

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

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

В качестве составной части программного комплекса были созданы встроен, :

♦ разбиение графа на плоские суграфы;

♦ исследование графа на предмет планарности;

♦ укладка гра фа на плоскости.

621.381

. . , . .

САМООРГАНИЗУЮЩИЙСЯ ГЕНЕТИЧЕСКИЙ АЛГОРИТМ -ЭФФЕКТИВНЫЙ СПОСОБ ДОСТИЖЕНИЯ ОПТИМУМА

Генетические алгоритмы (ГА) представляют собой мощный оптимизацион-

, -

.

Задача компоновки элементов (узлов) коммутационной схемы электронновычислительной аппаратуры (ЭВА) является одним из этапов при проектировании .

.

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

( ). -

плекса прикладных программ в среде программирования Borland C++ Builder 3.0.

Особенностью разработанного ГАСЭС является блок самоорганизации, основными функциями которого являются:

1)

применения генетических операторов при изменении текущих параметров;

2) получение более «качественных» потомков после применения ГО.

Гибкость структуры ГАСЭС, возможность её настройки и перенастройки позволяет получать высокие результаты за приемлемое время. Так, в частности, по сравнению с простым генетическим алгоритмом качество решений получаемых ГАСЭС в 1,4-2,3 раза выше.