ОПТИМИЗАЦИЯ НА ОСНОВЕ ОБЪЕДИНЕНИЯ МОДЕЛЕЙ АДАПТИВНОГО ПОВЕДЕНИЯ РОЯ АГЕНТОВ
Аннотация
Разработана архитектура бионического поиска для решения задачи размещения элемен-
тов СБИС на основе гибридизации алгоритмов пчелиной колонии и роя хромосом, что позволя-
ет выходить из «локальных ям» и увеличивает сходимость алгоритма размещения. Начальные
итерации реализует пчелиный алгоритм, чтобы обеспечить широкий обзор области поиска, а
завершающие – алгоритм роя хромосом, обеспечивающий точную локализацию экстремума,
найденного пчелиным алгоритмом. Агенты представляются в виде популяции хромосом, яв-
ляющихся генотипами решения задачи размещения. В работе описывается модифицированная
парадигма роя хромосом, обеспечивающая, в отличие от канонического метода, возможность
поиска решений в аффинном пространстве позиций с целочисленными значениями параметров.
В поисковом популяционном методе оптимизации роем хромосом агентами популяция являют-
ся хромосомы. Хромосома является генотипом объекта оптимизации. Суть поисковой проце-
дуры заключается в последовательной смене оператором направленной мутации состояний
объекта оптимизации (хромосомы) и поиске оптимального состояния. Предложена аффинно-
релаксационная модель (АРМ) роя хромосом – это граф вершины которого соответствуют
хромосомам, а дуги соответствуют аффинным связям между ними. Переход хромосомы в
новое состояние осуществляется с помощью релаксационной процедуры. В работе в качестве
средства изменения решения выступает оператор направленной мутации (ОНМ), суть кото-
рого заключается в изменения целочисленных значений генов в хромосоме. Целью перехода явля-
ется сокращении веса аффинной связи между хромосомами. Описаны механизмы ОНМ. Пред-
ложена модифицированная структура алгоритма пчел. Для каждой базовой хромосомы реали-
зуется вероятностный выбор набора хромосом, расположенных в окрестности базовой хромо-
сомы. Улучшить качество работы разработанного алгоритма можно при помощи настройки
значений управляющих параметров. Временная сложность алгоритма при фиксированных зна-
чениях размера популяции и количества генераций составляет О(n). В общем зависимость вре-
мени работы гибридного алгоритма составляет О(n2) – О(n3).
Литература
integrated circuits and systems]. Moscow: Binom. Laboratoriya znaniy, 20105.
2. Tuchin A.V., Bormontov E.N., Ponomarev K.G. Vvedenie v sistemy avtomatizirovannogo
proektirovaniya integral'nykh mikroskhem [Introduction to computer-aided design of integrated
circuits]. Voronezh: Izdatel'skiy dom VGU, 2017.
3. Norenkov I.P. Osnovy avtomatizirovannogo proektirovaniya [Fundamentals of computer-aided
design]. Moscow: Izd-vo MGTU im. N.E. Baumana, 2006.
4. Alpert C.J., Mehta D.P., and Sapatnekar S.S. Handbook of Algorithms for Physical Design
Automation. Boston, MA: Auerbach, 2009.
5. Lebedev B.K., Lebedev V.B., Lebedev O.B. Metody, modeli i algoritmy razmeshcheniya
[Methods, models and placement algorithms]. Rostov-on-Donu: Izd-vo YuFU, 2015.
6. Jason Cong, Joseph R., Shinnerl и Min Xie (UCLA Computer Science), Tim Kong (Magma
Design Automation) и Xin Yuan (IBM Corporation, Microelectronics Division). Large-Scale
Circuit Placement, ACM Transactions on Design Automation of Electronic Systems. April
2005, Vol. 10, No. 2.
7. Poli R. Analysis of the publications on the applications of particle swarm optimization, Journal
ofArtificial Evolution and Applications, Article ID 685175, 2008.
8. Karpenko A.P. Sovremennye algoritmy poiskovoy optimizatsii. Algoritmy, vdokhnovlennye
prirodoy: ucheb. posobie [Modern search engine optimization algorithms. Algorithms inspired
by nature: textbook]. Moscow: Izd-vo MGTU im. N.E. Baumana, 2014.
9. Wang X. Hybrid nature-inspired computation method for optimization: Doctoral Dissertation.
Helsinki University of Technology, TKK Dissertations, Espoo 2009, 161 p.
10. Clerc M. Particle Swarm Optimization. ISTE, London, UK, 2006.
11. Kennedy J., Eberhart R.C. Particle swarm optimization, In Proceedings of IEEE International
Conference on Neural Networks, 1995, pp. 1942-1948.
12. Lebedev B.K., Lebedev O.B.,. Lebedev V.B. Gibridnyy metod stokhasticheskoy optimizatsii na
osnove integratsii modeley evolyutsii i roevogo (staynogo) povedeniya zhivotnykh v affinnykh
prostranstvakh poiska [A hybrid method of stochastic optimization based on the integration of
models of evolution and swarm (packing) behavior of animals in affine search spaces], Sb.
trudov Shestnadtsatoy natsional'noy konferentsii po iskusstvennomu intellektu s
mezhdunarodnym uchastiem KII-2018 [Proceedings of the Sixteenth National Conference on
Artificial Intelligence with International Participation KII-2018]. In 2 vol. Vol. 2. Moscow:
FGP ITAR-TASS filial RKP, 2018, pp. 148-156.
13. Lebedev B.K., Lebedev O.B., Lebedeva E.O., Nagabedyan A.A. Gibridnyy roevoy algoritm
global'noy optimizatsii v affinnom prostranstve poiska [Hybrid swarm algorithm of global optimization
in affine search space], Elektronnyy zhurnal “Programmnye produkty, sistemy i
algoritmy” [Electronic journal "Software products, systems and algorithms"], 2019, No. 1.
14. Lučić P., Teodorović D. Computing with Bees: Attacking Complex Transportation Engineering
Problems, International Journal on Artificial Intelligence Tools, 2003, No. 12, pp. 375-394.
15. Quijano N., Passino K.M. Honey Bee Social Foraging Algorithms for Resource Allocation:
Theory and Application. Columbus: Publishing house of the Ohio State University, 2007, 39 p.
16. Lebedev B.K., Lebedev V.B. Razmeshchenie na osnove metoda pchelinoy kolonii [Placement
based on the bee colony method], Izvestiya YuFU. Tekhnicheskie nauki [Izvestiya SFedU. Engineering
Sciences], 2010, No. 12, pp. 12-18.
17. Cong J., Romesis M., and Xie M. Optimality, Scalability and Stability Study of Partitioning
and Placement Algorithms, Proc. of the International Symposium on Physical Design, Monterey,
CA, April 2004, pp. 88-94.
18. MCNC. Electronic and Information Technologies (Online). Available: www.mcnc.org.
19. Wang M., Yang X. and Sarrafzadeh M. Dragon2000: Standard-cell Placement Tool for Large
Industry Circuits, ICCAD 2000, pp. 260-263.
20. Caldwell A.E., Kahng A.B. and Markov I.L. Can Recursive Bisection Alone Produce Routable
Placements?, DAC 2000, pp. 477-482.
21. Chan T., Cong J., Kong T., Shinnerl J. и Sze K. An enhanced multilevel algorithm for circuit
placement, In Proceedings of the IEEE International Conference on Computer Aided Design
(San Jose, Calif.). IEEE Computer Society Press, Los Alamitos, Calif. 2003.
22. Yang X., Choi B.-K. and Sarrafzadeh M. Routability-driven white space allocation for fixeddie
standard-cell placement, IEEE Trans. on Computer-Aided Design of Integrated Circuits
and Systems, 2003, 22 (4), pp. 410-419.
23. CADENCE DESIGN SYSTEMS, INC. QPlace version 5.1.55, compiled on 10/25/1999.
Envisia ultra-placer reference.
