ПОИСКОВЫЙ ПОПУЛЯЦИОННЫЙ АЛГОРИТМ РАЗМЕЩЕНИЯ ЭЛЕМЕНТОВ СБИС

Аннотация

В работе рассматривается поисковый популяционный алгоритм размещения компо- нентов СБИС. По аналогии с процессом возникновения и формирования кристаллов из ве- щества, процесс порождения решения путем последовательного проявления и конкретиза- ции решения на базе интегральной россыпи альтернатив назван методом кристаллизации россыпи альтернатив. Решение Qk задачи размещения представляется в виде биективного отображения Fk=A→P, каждому элементу множества A соответствует один единст- венный элемент множества P и наоборот. Лежащая в основе алгоритма метаэвристика кристаллизации россыпи альтернатив выполняет поиск решений с учетом коллективной эволюционной памяти, под которой подразумевается информация, отражающая историю поиска решения и памяти поисковой процедуры. Отличительной особенностью используе- мой метаэвристики является учет тенденции к использованию альтернатив из наилучших найденных решений. Предложены компактные структуры данных для хранения интерпре- таций решений и памяти. Алгоритм, связанный с эволюционной памятью, стремится к запоминанию и многократному использованию способов достижения лучших результатов. Разработанный алгоритм относится к классу популяционных алгоритмов. Итерационный процесс поиска решений включает три этапа. На первом этапе каждой итерации конст- руктивным алгоритмом формируется nq решений Qk. Работа конструктивного алгоритма базируется на базе показателей основной интегральной россыпи альтернатив – матрицы R, в которой хранятся интегральные показатели решений, полученных на предыдущих итерациях. Процесс назначения элемента в позицию включает две стадии. На первой ста- дии выбирается элемент, а на второй стадии – позиция pj. При этом должно выполняться ограничение: каждому элементу соответствует одна позиция pj. Рассчитывается оценка ξk решения Qk и оценка полезности δk множества позиций Pk выбранных агентами. В рабо- те используется циклический метод формирования решений. В этом случае наращивание оценок интегральной полезности δk в основной интегральной россыпи альтернатив B вы- полняется после полного формирования множества решений Q. На втором этапе итера- ции производится наращивание оценок интегральной полезности δk в основной интеграль- ной россыпи альтернатив – матрице R. На третьем этапе итерации осуществляетсяснижение оценок полезности δk интегральной россыпи альтернатив R на априори заданную величину δ*. Работа алгоритма завершается после выполнения заданного числа итера- ций. Сравнительный анализ с другими алгоритмами решения производился на стандартных тестовых примерах (бенчмарках) корпорации IBМ, при этом решения, синтезируемые ал- горитмом CAF, превосходят по эффективности решения известных методов в среднем на 6%. Временная сложность алгоритма – О(n2)-О(n3).