Open AccessIntegrated algorithm for elements placement on the printed circuit board
Author(s) -
Vladimir Kureichik,
Elmar Kuliev
Publication year - 2020
Publication title -
iop conference series. materials science and engineering
Language(s) - English
Resource type - Journals
eISSN - 1757-899X
pISSN - 1757-8981
DOI - 10.1088/1757-899x/734/1/012146
Subject(s) - computer science , algorithm , convergence (economics) , time complexity , printed circuit board , ant colony optimization algorithms , graph , heuristic , realization (probability) , process (computing) , genetic algorithm , mathematical optimization , theoretical computer science , mathematics , artificial intelligence , statistics , machine learning , economics , economic growth , operating system
The paper discusses one of the priority design problem – the placement of elements on the printed circuit board (PCB). It relates to the NP-hard class of discrete optimization problems. The paper describes the placement problem and provides its formal statement. A complex criterion considers critical connections and total length of connections. The connection graph is selected to simulate the placement problem. To respond effectively to the challenge, there is proposed a heuristic for isolating the connected fragments of the graph model as building blocks. The developed integrated algorithm based on genetic, evolutionary and ant search strategies is organized hierarchically. This algorithm obtains quasi-optimal solutions in polynomial time, as well as parallelize the search process and partially eliminate the preliminary convergence problem. In order to conduct experiments, a software realization of the integrated algorithm has been developed. A series of tests and experiments clarify theoretical estimates of the time complexity and behavior of the developed algorithm for various structures of schemes. The time complexity has been represented by O(nlogn) at the best case and O(n 3 ) in the worst case.