РАЗРАБОТКА МОДИФИЦИРАВАННЫХ МЕТОДОВ И МОДЕЛЕЙ ПОИСКОВОЙ АДАПТАЦИИ ДЛЯ РЕШЕНИЯ ЗАДАЧИ ПЛАНИРОВАНИЯ СБИС

Аннотация

В работе для решения задачи планирования СБИС разработан поисковый алгоритм на основе модифицированного метода муравьиной колонии. Задача формирования плана СБИС сводится к задаче формирования соответствующего польского выражения. Разра- ботанный метод синтеза польского выражения включает построение дерева разрезов, выбор типов разрезов (H или V), идентификацию и ориентацию модулей. Эволюционирую- щая популяция разбита на пары агентов. Каждый член популяции – пара агентов, рабо- тающих совместно. При этом конструктивные алгоритмы A1 и A2, используемые аген- тами пары различаются. Задача, решаемая алгоритмом А1, формулируется как задача поиска взаимно однозначного отображения Fk=M*→P множества модулей M c выбранны- ми ориентациями, |M*|=|M| в множество P позиций шаблона Sh. Фактически решение за- ключается в выборе на графе G1 подмножества ребер E*1E1, входящих в соответствующее отображение Fk. В алгоритме A2 в качестве модели пространства поиска реше- ний для выбора типа, последовательности и места расположения разрезов в шаблоне Sh разработан граф G2=(X, E2). X={(x1i,x2i)|i=1,2,…,n} множество вершин графа G2, соот- ветствует множеству P потенциальных позиций шаблона Sh для возможного размещения в них имен символов разрезов. Каждая потенциальная позиция piP шаблона Sh моделиру- ется двумя альтернативными вершинами (x1i,x2i). Выбор при размещении разрезов верши- ны x1i указывает на то, что в позицию pi помещен разрез типа V, выбор вершины x2i – ука- зывает на то, что в позицию pi помещен разрез типа H. Каждая итерация l общего алго- ритма включает начальный и три основных этапа. Начальный этап заключается в сле- дующем. Обнуляются матрицы ко-эволюционной памяти КЭП*1 и КЭП*2. На первом этапе каждая пара агентов dk=(a1k, a2k): – конструктивными алгоритмами A1 и A2 синтезирует свое решение Wk=(E1k *,Sk); – формируется польское выражение Shk, соответствующее решению Wk; – на базе Shk формируется дерево разрезов Tk; – на базе Tk формируется план Rk и рассчитывается оценка решения Fk; – агенты откладывают (добавляют) феромон в ячейки матриц коллективной эволюционной памяти КЭП*1 и КЭП*2, соответствующие ребрам решения Wk=(E1k *,Sk) в графах поиска решений G1 и G2 в количестве пропорциональном оценке решения Fk. На втором этапе феромон, накопленный в КЭП*1 и КЭП*2 агентами популяции на итерации l, добавляется в КЭП1 и КЭП2. На третьем этапе осу- ществляется испарение феромона на ребрах графов G1 и G2. Тестовые испытания под- твердили эффективность предложенного метода. Временная сложность алгоритма, по- лученная экспериментальным путем, совпадает с теоретическими исследованиями и для рассмотренных тестовых задач составляет О(n2).