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

  • Б.К. Лебедев Южный федеральный университет
  • О. Б. Лебедев Южный федеральный университет
  • Е. О. Лебедева Южный федеральный университет
Ключевые слова: Роевой интеллект, адаптация, кристаллизация, СБИС, разбиение, россыпь альтернатив, двудольный граф

Аннотация

Работа алгоритма разбиения базируется на использовании коллективной эволюцион-
ной памяти, под которой подразумевается информация, отражающая историю поиска
решения и хранится независимо от индивидуумов. Алгоритм, связанный с эволюционной
памятью, стремится к запоминанию и многократному использованию способов достиже-
ния лучших результатов. Коллективная эволюционная память алгоритма разбиения со-
стоит из некоторого количества статистических индикаторов, отображающих для ка-
ждого выполненного варианта число θ его вхождений в состав лучших решений на выпол-
ненных генерациях алгоритма и число, δ определяющее насколько полезна реализованная
альтернатива при формировании результатов на прошлых генерациях алгоритма. Коллек-
тив не имеет централизованного управления, и в связи с этим используется непрямой об-
мен информацией. Непрямой обмен состоит в выполнении неких действий, в различное
время, при которых происходит изменение некоторых частей эволюционной памяти одним
агентом. В дальнейшем происходит использование этой измененной информации другими
агентами, в этих частях. Вначале на каждой итерации конструктивным алгоритмом
формируется nk решений Qk,. Каждое решение Qk является отображением Fk=V→X, пред-
ставляется в виде двудольного подграфа Dk и формируется путем последовательного на-
значения элементов в узлы. Формирование каждого решения Qk выполняется множеством
агентов A, посредством вероятностного выбора каждым агентом ai узла vj. Процесс на-
значения элемента в узел включает две стадии. На первой стадии выбирается агент ai, а
на второй стадии − узел vj. При этом должно выполняться ограничение: каждому агенту
множества A соответствует один единственный узел множества V. Рассчитывается
оценка ξk решения Qk и оценка полезности δk множества альтернатив, реализованных
агентами в решении Qk. На втором этапе агенты увеличивают в интегральной россыпи
альтернатив R* интегральную полезность множества альтернатив на величину δk..
На третьем этапе осуществляется снижение оценок полезности δk интегральной россыпи
альтернатив на величину μ. В работе используется циклический метод формирования ре-
шений. В этом случае наращивание оценок интегральной полезности δk множества пози-
ций P выполняется после полного формирования множества решений Q на итерации l.
Экспериментальные исследования проводились на основе сформированных тестовых при-
меров с полученным ранее оптимальным решением. Полученные результаты сравнивались
с результатами полученными другими известными алгоритмами разбиения схем на части.
Для сравнения был сформирован набор стандартных бенчмарок. Проанализировав получен-
ные результаты, можно сделать вывод, что предложенный метод позволяет получать на
4–5 % решения качественнее, чем его аналоги.

Литература

1. Nemudrov V., Martin G. Sistemy-na-kristalle. Proektirovanie i razvitie [Systems-on-a-chip.
Design and development]. Moscow: Tekhnosfera, 2004, 157 p.
2. Kazennov G.G. Osnovy proektirovaniya integral'nykh skhem i system [Fundamentals of design
of integrated circuits and systems]. Moscow: Binom. Laboratoriya znaniy, 2005, 295 p.
3. Alpert C.J., Mehta D.P., Sapatnekar S.S. Handbook of Algorithms for Physical Design Automation.
Boston. MA: Auerbach, 2009, 245 р.
4. Karpenko A.P. Sovremennye algoritmy poiskovoy optimizatsii. Algoritmy, vdokhnovlennye
prirodoy: ucheb. posobie [Modern search engine optimization algorithms. Algorithms inspired
by nature]. Moscow: Izd-vo MGTU im. N.E. Baumana, 2014, 448 p.
5. Kureychik V.M., Lebedev B.K., Lebedev O.B. Gibridnyy algoritm razbieniya na osnove
prirodnykh mekhanizmov prinyatiya resheniy [Hybrid partition algorithm based on natural decision-
making mechanisms], Iskusstvennyy intellekt i prinyatie resheniy [Artificial intelligence
and decision making]. Moscow: Izd-vo Institut sistemnogo analiza RAN, 2012, p. 3-15.
6. Lebedev B.K., Lebedev O.B. Murav'inye algoritmy razbieniya, ispol'zuyushchie predstav-lenie
zadachi, otlichnye ot kanonicheskogo [Ant partitioning algorithms using a task representation
other than the canonical], Vestnik Rostovskogo gosudarstvennogo universiteta putey
soobshcheniya [Bulletin of the Rostov State University of Railways], 2016, No. 2 (62), pp. 71-77.
7. Lebedev B.K., Lebedev O.B. Razbienie na osnove mnogourovnevoy parallel'noy
evolyutsionnoy adaptatsii [Partitioning on the basis of multi-level parallel evolutionary adaptation],
Problemy razrabotki perspektivnykh mikro- i nanoelektronnykh system [Problems of developing
promising micro- and nanoelectronic systems], 2008: Sb. nauchnykh trudov [Problems
of developing promising micro- and nanoelectronic systems – 2008: Collection of scientific
papers], ed. by A.L. Stempkovskogo. Moscow: IPPM RAN, 2008, pp. 36-41.
8. Vorb'eva E.Yu., Karpenko A.P., Seliverstov E.Yu. Ko-gibridizatsiya algoritmov roya chastits [Cohybridization
of particle swarm algorithms], Nauka i zhizn' [Science and Life], 2012, No/ 4.
9. Zhou Y., Pei Sh. A hybrid co-evolutionary particle swarm optimization algorithm for solving
constrained engineering design problems, Journal of computers (JCP), 2010, Vol. 5, No. 6,
pp. 965-972.
10. Lebedev B.K., Lebedev V.B. Optimizatsiya metodom kristallizatsii rossypi al'ternativ [Optimization
by the method of сrystallization of alternatives field], Izvestiya YUFU. Tekhnicheskie
nauki [Izvestiya SFedU. Engineering Sciences], 2013, No. 7 (144), pp. 11-17.
11. Clerc M. Particle Swarm Optimization. ISTE, London, UK, 2006, 198 р.
12. Poli R. Analysis of the publications on the applications of particle swarm optimization, Journal
of Artificial Evolution and Applications, Article ID 685175, 2008.
13. Lebedev B.K., Lebedev V.B. Postroenie kratchayshikh svyazyvayushchikh soedineniy
metodom kristallizatsii rossypi al'ternativ [Construction of the shortest binding compounds by
the method of сrystallization of alternatives field], MES-2014. VI Vserossiyskaya nauchnotekhnicheskaya
konferentsiya «Problemy razrabotki perspektivnykh mikro- i nanoelektronnykh
sistem – 2014»: Sb. trudov [MES-2014. VI All-Russian scientific and technical conference
"Problems of developing promising micro- and nanoelectronic systems – 2014": Proceedings],
under the total. ed. akademika RAN A.L. Stempkovskogo. Moscow: IPPM RAN, 2014. Part I,
pp. 177-183.
14. Cong J., Romesis M., Xie M. Optimality, Scalability and Stability Study of Partitioning and
Placement Algorithms, Proc. of the International Symposium on Physical Design. Monterey,
CA, 2003, pp. 88-94.
15. Selvakkumaran N., Karypis G. Multi-Objective Hypergraph Partitioning Algorithms for Cut
and Maximum Subdomain Degree Minimization, ICCAD, 2003, pp. 234-249.
16. Ababei C., Selvakkumaran N., Bazargan K., Karypis G. Multi-objective Circuit Partitioning
for Cutsize and Path-Based Delay Minimization, ICCAD, 2002, pp. 118-137.
17. Agasiev T.A., Karpenko A.P. Sovremennye tekhniki global'noy optimizatsii, Informatsionnye
tekhnologii, 2018, No. 6, pp. 370-386.
18. Norenkov I.P., Uvarov M.Yu. Podderzhka prinyatiya resheniy na osnove patternov
proektirovaniya [Decision support based on design patterns], Nauka i obrazovanie: nauchnoe
izdanie [Science and Education: Scientific publication]. Moscow: Izd-vo MGTU im.
N.E. Baumana, 2011, No. 9, pp. 25-32.
19. Bozhko A.N. Metody strukturnogo analiza slozhnykh izdeliy v integrirovannykh CFD/CAMsistemakh
[Structural analysis methods for complex products in integrated CАD],
Informatsionnye tekhnologii [CAM-systems. Information Technologies]. Moscow: Izd-vo
MGTU im. N.E. Baumana, 2018, No. 8, pp. 499-506.
20. Stolyarov A.I., Donetskaya Yu.V., Gatchin Yu.A. Osobennosti SAPR pri proektirovanii
kompleksa [Features of CAD in the design of the complex], Vestnik Irkutskogo
gosudarstvennogo tekhnicheskogo universiteta [Bulletin of the Irkutsk State Technical University],
2018, No. 7 (138), pp. 88-95.
Опубликован
2020-07-20
Выпуск
Раздел
РАЗДЕЛ III. ЭВОЛЮЦИОННОЕ МОДЕЛИРОВАНИЕ