|Article title||DEVELOPMENT AND PROGRAM IMPLEMENTATION OF THE HYBRID ALGORITHM SOLUTIONS OF PLACEMENT AND ROUTING PROBLEMS|
|Authors||L. A. Gladkov, N. V. Gladkova, S. N. Leiba|
|Section||SECTION I. DESIGN AUTOMATION|
|Month, Year||07, 2017 @en|
|Abstract||The article considers a hybrid algorithm for solving the problems of placement and tracing elements of circuits of digital electronic computing equipment. The relevance and importance of the problem under consideration and the variety of existing approaches to the solution of such problems are noted. The formulation of the problem is given, the limitations of the domain of admissible solutions are chosen and the criterion for estimating the quality of the solutions obtained is formulated. A new hybrid approach to the solution of the problem under consideration is proposed on the basis of a combination of evolutionary search methods, a mathematical apparatus of fuzzy logic and the possibilities of parallel organization of the computational process. In the article, it was suggested to exchange solutions between populations using a common intermediate buffer of chromosomes. New modifications of the basic genetic operators have been developed. A modified migration operator is proposed to exchange information between solution populations in the process of performing parallel computations. The structure of the parallel hybrid algorithm is developed. The implementation of the fuzzy control module based on the use of a multilayer neural network and the Gaussian function is proposed. To improve the quality of the results obtained, a fuzzy logic controller that regulates the values of the parameters of the evolution process is included in the evolution of expert information. The basic principles of the fuzzy control unit are formulated. The structural scheme of the developed hybrid algorithm is presented. The features of the software implementation of the proposed hybrid algorithm are considered in detail. The requirements to the architecture of the developed program are formulated taking into account the need to support the modularity and extensibility of the application. Examples of the description of an element of a printed circuit board on the basis of existing specifications are given. The structure of the interface is described, the main elements of the graphic interface of the developed application are presented. A brief description of the computational experiments that confirm the effectiveness of the proposed method is presented.|
|Keywords||Design automation; genetic algorithm; evolutionary computation; fuzzy logic; parallel computing; fuzzy logic controller.|
|References||1. Norenkov I.P. Osnovy avtomatizirovannogo proektirovaniya [Fundamentals of CAD]. Moscow: Izd-vo MGTU im. Baumana, 2010.
2. Shervani, N. Algorithms for VLSI physical design automation. Kluwer Academy Publisher, USA, 1995, 538 p.
3. Gladkov L.A., Kureychik V.V., Kureychik V.M. Geneticheskie algoritmy [Genetic algorithms]. Moscow: Fizmatlit, 2010.
4. Kureychik V.M., Kureychik V.V., Rodzin S.I. Kontseptsiya evolyutsionnykh vychisleniy, inspirirovannykh prirodnymi sistemami [Concept evolutionary computation is inspired by nat-ural systems], Izvestiya YuFU. Tekhnicheskie nauki [Izvestiya SFedU. Engineering Sciences], 2009, No. 4 (93), pp. 16-25.
5. Cohoon J.P., Karro J., Lienig J. Evolutionary Algorithms for the Physical Design of VLSI Circuits. Advances in Evolutionary Computing: Theory and Applications, Ghosh, A., Tsutsui, S. (eds.) Springer Verlag, London, 2003. – P. 683-712.
6. Michael A., Takagi H. Dynamic control of genetic algorithms using fuzzy logic techniques, Proceedings of the Fifth International Conference on Genetic Algorithms. Morgan Kaufmann, 1993, pp. 76-83.
7. King R.T.F.A., Radha B., Rughooputh H.C.S. A fuzzy logic controlled genetic algorithm for optimal electrical distribution network reconfiguration, Proceedings of 2004 IEEE International Conference on Networking, Sensing and Control, Taipei, Taiwan, 2004, pp. 577-582.
8. Im S.-M., Lee J-J. Adaptive crossover, mutation and selection using fuzzy system for genetic algorithms, Artificial Life and Robotics, 2008, Vol. 13, No. 1, pp. 129-133.
9. Rodriguez M.A., Escalante D.M., Peregrin A. Efficient distributed genetic algorithm for rule extraction, Applied Soft Computing, 2011, Vol. 11, pp. 733-743.
10. Alba E., Tomassini M. Parallelism and evolutionary algorithms, IEEE T. Evolut. Comput, 2002, Vol. 6, pp. 443-461.
11. Zhongyang X., Zhang Y., Zhang L., Niu S. A parallel classification algorithm based on hybrid genetic algorithm, Proceedings of the 6th World Congress on Intelligent Control and Automa-tion, Dalian, China. 2006, pp. 3237-3240.
12. Knysh D.S., Kureychik V.M. Parallel'nye geneticheskie algoritmy: Problemy, obzor i sostoyanie [Parallel genetic algorithms: Problems, overview, and status], Izvestiya RAN. Teoriya i sistemy upravleniya [Journal of Computer and Systems Sciences International], 2010, No. 4, pp. 72-82.
13. Gladkov L.A. Integrirovannyy algoritm resheniya zadach razmeshcheniya i trassirovki na osnove nechetkikh geneticheskikh metodov [The integrated algorithm of the decision of problems of placement and routing on the basis of fuzzy genetic methods], Izvestiya YuFU. Tekhnicheskie nauki [Izvestiya SFedU. Engineering Sciences], 2011, No. 7 (120), pp. 22-29.
14. Gladkov L.A. Gladkova N.V., Leyba S.N. Razmeshchenie elementov skhem EVA na osnove gibridnykh intellektual'nykh metodov [Placement circuit elements of electronic computing de-vices based on hybrid intelligent methods], Izvestiya YuFU. Tekhnicheskie nauki [Izvestiya SFedU. Engineering Sciences], 2015, No. 4 (165), pp. 25-36.
15. Gladkov L.A., Gladkova N.V., Leiba S.N. Electronic Computing Equipment Schemes Elements Placement Based on Hybrid Intelligence Approach, Advanced in Intelligent Systems and Com-puting. Vol. 348: Intelligent Systems in Cybernetics and Automation Theory. Springer Interna-tional Publishing, Switzerland, 2015, pp. 35-45.
16. Gamma E., Khelm R., Dzhonson R., Vlissides D. Priemy ob"ektno-orientirovannogo programmirovaniya. Patterny proektirovaniya [Techniques of object-oriented programming. Design patterns]. Moscow: Piter, 2010.
17. Makkonel S. Sovershennyy kod [Perfect code]. Moscow: Piter, 2005.
18. "Library Exchange Format". University of Maryland, Baltimore County, 2011.
19. Qt Documentation. Available at: http://doc.qt.io/qt-5/reference-overview.html.
20. QCustomPlot. Available at: http://qcustomplot.com/index.php/introduction.