ОПТИМИЗАЦИЯ НА ОСНОВЕ ОБЪЕДИНЕНИЯ МОДЕЛЕЙ АДАПТИВНОГО ПОВЕДЕНИЯ РОЯ АГЕНТОВ
Ключевые слова:
СБИС, размещение, роевой интеллект, пчелиный алгоритм, рой хромосом, гибридизация, аффинное пространство поиска, оператор направленной мутации, бионический поискАннотация
Разработана архитектура бионического поиска для решения задачи размещения элемен-
тов СБИС на основе гибридизации алгоритмов пчелиной колонии и роя хромосом, что позволя-
ет выходить из «локальных ям» и увеличивает сходимость алгоритма размещения. Начальные
итерации реализует пчелиный алгоритм, чтобы обеспечить широкий обзор области поиска, а
завершающие – алгоритм роя хромосом, обеспечивающий точную локализацию экстремума,
найденного пчелиным алгоритмом. Агенты представляются в виде популяции хромосом, яв-
ляющихся генотипами решения задачи размещения. В работе описывается модифицированная
парадигма роя хромосом, обеспечивающая, в отличие от канонического метода, возможность
поиска решений в аффинном пространстве позиций с целочисленными значениями параметров.
В поисковом популяционном методе оптимизации роем хромосом агентами популяция являют-
ся хромосомы. Хромосома является генотипом объекта оптимизации. Суть поисковой проце-
дуры заключается в последовательной смене оператором направленной мутации состояний
объекта оптимизации (хромосомы) и поиске оптимального состояния. Предложена аффинно-
релаксационная модель (АРМ) роя хромосом – это граф вершины которого соответствуют
хромосомам, а дуги соответствуют аффинным связям между ними. Переход хромосомы в
новое состояние осуществляется с помощью релаксационной процедуры. В работе в качестве
средства изменения решения выступает оператор направленной мутации (ОНМ), суть кото-
рого заключается в изменения целочисленных значений генов в хромосоме. Целью перехода явля-
ется сокращении веса аффинной связи между хромосомами. Описаны механизмы ОНМ. Пред-
ложена модифицированная структура алгоритма пчел. Для каждой базовой хромосомы реали-
зуется вероятностный выбор набора хромосом, расположенных в окрестности базовой хромо-
сомы. Улучшить качество работы разработанного алгоритма можно при помощи настройки
значений управляющих параметров. Временная сложность алгоритма при фиксированных зна-
чениях размера популяции и количества генераций составляет О(n). В общем зависимость вре-
мени работы гибридного алгоритма составляет О(n2) – О(n3).
