Извините, этот техт доступен только в “Американский Английский”. For the sake of viewer convenience, the content is shown below in the alternative language. You may click the link to switch the active language.
COMPUTER-AIDED OPTIMISATION OF ELECTRONIC CIRCUIT LAYOUT
Abas Wisam Mahdi Abas, South Russian State Polytechnic University
(Novocherkassk Polytechnic Institute), Novocherkassk, Russia, abas.wisam.82@mail.ru
Abstract
The problem of optimal placement of elements of electrical and electronic circuits is considered. The minimum weighted length of the connections is selected as the criterion. The scheme is defined by a matrix of connections. We consider a fixed set of element positions and a distance matrix based on an orthogonal metric. This problem is a variant of the general mathematical model, called the quadratic assignment problem. The geometric limitation of the problem is that no more than one element is placed in one cell. Combinatorial analogs of the Gauss-Seidel method, the genetic algorithm, and the corresponding hybrid methods for solving the quadratic assignment problem with optimal placement of electronic equipment elements are developed and implemented on a computer. A series of computational experiments was conducted, which showed satisfactory computational qualities of the proposed methods. The proposed computational method, which is a combinatorial analog of the method of coordinate descent and one of the variants of the general approach based on paired permutations, is characterized by the best computational qualities among the methods studied in the article. According to well-known studies, the genetic algorithm is obviously no worse than the Monte Carlo method. The research conducted in the article shows that the method of penalty functions in the problem of placement and for the case of a genetic algorithm is ineffective. Therefore, it is of interest to consider permutations without repetitions as individuals of the population. This circumstance is taken into account at the stages of selection and mutation: at these stages, the standard calculations according to the genetic algorithm are supplemented by the procedure of paired rearrangements of genes in the chromosome. The article provides a detailed description of the program for the implementation of the genetic method on a computer.
Keywords: electrical circuit, placement constraints, topological parameters, metric parameters, switching field, optimization criteria and methods.
References
- Algorithms for placing elements [Electronic resource]. https://helpiks.org/8-12562.html (accessed: 03.04.2021).
- N. P. Nikolov (1985). Placement of elements of electronic nodes by the method of multilevel decomposition and macromodeling and implementation on its basis of PPP for CAD REA. Diss.. Candidate of Technical Sciences, specialty 05.13.12. Lviv.
- A. A. Gorbachev (1999). Methods and algorithms of spatial tracing of printed circuit boards. Diss. Candidate of Technical Sciences, specialty 05.13.12. Kaliningrad.
- V. A. Selyutin (1983). Computer-aided design topology BIS. Moscow: Radio and communication. 112 p.
- K. K. Morozov, V. Odinokov, V. M. Kureychik (1983). Automated design of electronic equipment. Moscow: Radio and communication. 278 p.
- V. A. Martyushev (2005). Method of whips and bounds in quadratic task of appointments: Diss…. Cand. Fiz.-Mat. science: 01.01.09. Saint-Petersburg, 100 p.
- G. S. Kolubetskis (1988). Generator of test problems of quadratic assignment with a known optimal solution. math. and Math. phys.
Vol. 28. No. 11, pp. 1740-1743. - A. D.Leushkin, E. A. Neymark (2020). Quadratic problem on the assignment. Review of methods, generation of test problems with a priori known optimum. Trudy NSTU named after R. E. Alekseev. No. 4 (131), pp. 26-35.
- N. V. Starostin, N. V. Bykova (2017). Multilevel algorithm for solving the problem of architecture-dependent decomposition. Educational and methodical manual. Nizhny Novgorod: Nizhny Novgorod State University. 24 p.
- S. A. Rashkovsky (2016). Solving problems of combinatorial optimization by the monte carlo method. Vol. 471. No. 4. P. 403-407.
- S. A. Rashkovskiy (2016). Monte Carlo solution of combinatorial optimization problems. Doklady Mathematics. Vol. 94. No. 3, pp. 720-724.
- B. S. Darkhovsky, A. Popkov, Yu. Popkov (2014). Batch iterations of Monte Carlo for solving problems of global optimization. Itis, 2014, issue 3, pp. 39-52.
- A. A. Kulakov (2016). Development and research of algorithms for optimal placement of components VLSI three-dimensional integration. dissertations and abstracts on the Higher Attestation Commission of the Russian Federation 05.13.12, Candidate of Technical Sciences. 2016, Taganrog. P. 164.
Information about author:
Abas Wisam Mahdi Abas, Post-graduate student of the South Russian State Polytechnic University (Novocherkassk Polytechnic Institute), Department of Applied Mathematics, Novocherkassk, Russia