ABSTRACTS OF ARTICLES OF THE JOURNAL "INFORMATION TECHNOLOGIES".
No. 4. Vol. 24. 2018

DOI: 10.17587/it.24.239-244

V. V. Kureichik, D. Sc., Professor, Head of Department, e-mail: vkur@sfedu.ru, M. A. Zhilenkov, Graduate Student, e-mail: MZhilenkov777@gmail.com, Vl. Vl. Kureichik Jr., Graduate Student, e-mail: kureichik@yandex.ru, South Federal University

Genetic Algorithm or Partitioning Problem in Viev of Electromagnetic Compability

The paper deals with one of the important design problems — a partitioning of elements on a printed circuit board (PCB). The authors provide a problem formulation with restriction and describe a mathematical model as a decision tree. As a main criterion was selected electromagnetic elements compability. The partitioning problem belongs to NP-hard class of combinatorial optimization problems, which is suggested to solve by modified genetic algorithm. As a modification of the genetic algorithm there are introduced modified genetic operators. To avoid a preliminary converges of the algorithm the authors apply procedures of global and local improvements. They are based on elite and random transformations in the modified genetic algorithm. It possible to obtain optimal and quazi-optimal problem solutions more quickly and to vary of an alternative solution population. To confirm the effectiveness the developed approach there are created a software and carried out computational experiments on benchmarks. As a result, configuration parameters of the algorithm were specified. The obtain results on the average by 15 % are better in the value of the objective function of the developed modified genetic algorithm than in other tested algorithms. Time complexity of the developed modified genetic algorithm can be represented as O (nlogn) in the best case and 0(n2) in the worst case.
Keywords: electromagnetic compatibility, layout of PCB elements, multi-criteria optimization, genetic algorithm, mutation, crossing-over

P. 239–244

To the contents