МЕТАЭВРИСТИКА НА ОСНОВЕ ПОВЕДЕНИЯ КОЛОНИИ БЕЛЫХ КРОТОВ
Аннотация
Алгоритмы оптимизации, вдохновленные миром природы, превратились в мощные инструменты для решения сложных задач. Однако у них все же есть некоторые недостатки, требующие исследования новых и более совершенных алгоритмов оптимизации. В связи с этим, при решении NP полных задач появляется необходимость в разработке новых методик решения данного класса задач. Одним из таких методик может стать метаэвристика на основе поведения колонии белых кротов. В этой статье предлагается новый метаэвристический алгоритм, называемый алгоритмом слепых белых кротов. Этот алгоритм был разработан на основе социального поведения слепых кротов в поисках пищи и защиты колонии от вторжений. Предлагаемое решение сможет преодолеть многие недостатки обычных алгоритмов оптимизации, включая попадание в ловушку локальных минимумов или низкую ско-рость сходимости. Цель данной работы заключается в разработке алгоритма оптимизации сложной целевой функции. Научная новизна заключается в разработке генетического алго-ритма на основе поведения колонии белых кротов для решения NP полных задач. Постановка задачи в данной работе заключается в следующем: оптимизировать поиск решения сложных функций путем применения, алгоритма на основе поведения колонии белых кротов. Практическая ценность работы заключается в создании новой архитектуры поиска, позволяющей использовать разработанный алгоритм для эффективного решения NP полных задач, а также проводить сравнительный анализ с существующими аналогами. Принципиальное отличие от известных подходов в применении новой структуры бионспирированного поиска на основе поведения колонии белых кротов, которое позволит исключить попадание в локальный минимум или низкую скорость сходимости. Приведенные результаты вычислительного экс-перимента, показали преимущества предложенного в работе многомерного подхода к решению задач размещения элементов СБИС по сравнению с существующими аналогами. Таким образом, проблема создания методов, алгоритмов и программного обеспечения для решения NP полных задач в настоящее время является актуальной задачей.
Список литературы
1. Tarasov V.B. Ot mnogoagentnykh sistem k intellektual'nym organizatsiyam: filosofiya, psikhologiya, informatika [From multi-agent systems to intellectual organizations: philosophy, psychology, computer science]. Moscow: Editorial URSS, 2002, 352 p.
2. Yang X-S. A New Metaheuristic Bat-Inspired Algorithm. Nature Inspired Cooperative Strate-gies for Optimization, Stud. Comput. Intell., 2010, Vol. 284, pp. 65-74.
3. Danil'chenko V.I., Kureychik V.M. Geneticheskiy algoritm planirovaniya razmeshcheniya SBIS [Genetic algorithm of VLSI placement planning], Izvestie YuFU. Tekhnicheskie nauki [Izvestiya SFedU. Engineering Sciences], 2019, No. 2, pp. 75-79.
4. Danil'chenko V.I., Kureychik V.M. Klassifikatsiya i analiz metodov resheniya zadachi razmeshcheniya SBIS [Classification and analysis of methods for solving the VLSI placement problem], Informatika, vychislitel'naya tekhnika i inzhenernoe obrazovanie [Computer sci-ence, computer engineering and engineering education], 2018, Issue 1.
5. Danilchenko V.I., Danilchenko Y.V., Kureichik V.M. Bio-inspired Approach to Microwave Cir-cuit Design, IEEE EAST-WEST DESIGN & TEST SYMPOSIUM. EWDTS 2020, pp. 362-366. DIO: 10.1109/EWDTS 50664.2020.9224737.
6. Kalent'ev A.A., Garays D.V., Dobush I.M., Babak L.I. Strukturno-parametricheskiy sintez SVCh tranzistornykh usiliteley na osnove geneticheskogo algoritma s ispol'zovaniem modeley monolitnykh elementov [Structural-parametric synthesis of microwave transistor amplifiers based on a genetic algorithm using models of monolithic elements], Doklady TUSURa [Re-ports of TUSUR], December 2012, No. 2 (26), Part 2, pp. 104-112.
7. Tang Maolin and Yao Xin. A memetic algorithm for VLSI floorplanning, IEEE Transactions on Systems, Man, And Cybernetics–Part B: Cybernetics, 2007, No. 37 (1).
8. Goryainov A.E., Dobush I.M., Babak L.I. Postroenie parametricheskikh modeley passivnykh komponentov SVCh monolitnykh integral'nykh skhem s ispol'zovaniem programmy Extrac-tion-P [Construction of parametric models of passive components of microwave monolithic in-tegrated circuits using the Extraction-P program].
9. Kokolov A.A., Salnikov A.S., Sheyerman F.I. and Babak L.I. Broadband Double-Balanced SiGe BiCMOS Mixer With Integrated Asymmetric MBaluns, Int. Conf. “Dynamics of Systems, Mechanisms and Machines” (Dynamics-2017), Omsk, Russia, 2017 (accepted for publication).
10. Akay B., Karaboga D. A modified Artificial Bee Colony algorithm for real-parameter optimi-zation, Inf. Sci., 2010, Vol. 192, pp. 20-142.
11. Taherdangkoo M., Shirzadi M.H., Bagheri M.H. A novel meta-heuristic algorithm for numeri-cal function optimization: blind, naked mole-rats (BNMR) algorithm, Scientific Research and Essays, 2012, No. 7 (41), pp. 3566-3583.
12. Bocklemann D.E. and Eisenstadt W.R. Combined Diff erential and Common-Mode Scattering Parameters: Theory and Simulation, IEEE Trans. on Microwave Theory and Techniques, July 1995, Vol. MTT-43, No. 7, pp. 520–523,.
13. Yang Y., Kamel M.S. An aggregated clustering approach using multi-ant colonies algorithms, Pattern Recognition, 2006, Vol. 39 (7), pp. 1278-1289.
14. Zhabin D.A., Garays D.V., Kalentyev A.A., Dobush I.M. and Babak L.I. Automated Synthesis of Low Noise Amplifi ers Using S-parameter Sets of Passive Elements, Asia-Pacifi c Micro-wave Conference (APMC 2017), Kuala Lumpur, Malaysia, 2017 (accepted for publication).
15. Kalentyev A.A., Garays D.V. and Babak L.I. Genetic-Algorithm-Based Synthesis of Low-Noise Amplifi ers with Automatic Selection of Active Elements and DC Biases, European Mi-crowave Week 2014, Rome, Italy, October 2014, pp. 520-523.
16. Babak L.I., Kokolov A.A. and Kalentyev A.A. A New Genetic-Algorithm-Based Technique for Low Noise Amplifier Synthesis, European Microwave Week 2012, Amsterdam, The Nether-lands, November 2012, pp. 520-523.
17. Mann G.K.I., Gosine R.G. Three-dimensional min–max-gravity based fuzzy PID inference analysis and tuning, Fuzzy Sets and Systems, 2005, Vol. 156, pp. 300-323.
18. Golitsyn G.A. Petrov V.M. Informatsiya i biologicheskie printsipy optimal'nosti: Garmoniya i algebra zhivogo [Information and biological principles of optimality: Harmony and al-gebra of the living]. Moscow: KomKniga 2005.
19. Kolesov Yu.B., Senichenkov Yu.B. Modelirovanie sistem. Dinamicheskie i gibridnye sistemy: ucheb.-metod. Posobie [Modeling of systems. Dynamic and hybrid systems: an educa-tional and methodological guide]. Saint Petersburg: BKhV-Peterburg, 2006.
20. Abraham A., Grosan G., Ramos V. Swarm Intelligence in Data Mining. Berlin. Heidelberg: SpringerVerlag, 2007, 267 p.
