КОМБИНИРОВАННЫЙ ПОДХОД ДЛЯ РЕШЕНИЯ ЗАДАЧИ КОМПОНОВКИ СБИС
В данной статье рассматривается комбинированный подход для решения задачи компоновки СБИС, повышающий эффективность поиска альтернатив- ных решений. Сформулирована постановка задачи компоновки, как разбиение графа на части с минимизацией критерия межблочных связей. Реализован метод решения наиболее распространенных задач автоматизированного конструктор- ского проектирования. В работе представлено решение задачи разбиения в виде процедуры комбинированного поиска, совмещающего в себе генетический алго- ритм (ГА) и эволюционный (ЭА). Совмещение алгоритмов позволило распаралле- лить процесс поиска и получить наборы квазиоптимальных решений за полино- миальное время. Рассмотрены основные принципы построения данного подхода. Разработана программная среда. Проведен вычислительный эксперимент. Вре- менная сложность разработанных алгоритмов (ВСА) составляет (ВСА ≈ О(n2)).