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