Authors M. A. Zhilenkov, V. V. Kureichik
Month, Year 07, 2017 @en
Index UDC 004.896
Abstract The solution of one of the important problems of design, the problem of electronic computing equipment (ECE) placement, is suggested. In solving this problem the criterion of electromagnetic compatibility (EMC) is selected as the basic one. Due to the big data processing the placement problem belongs to NP-complex and NP-difficult class of problem. The statement and the mathematical model of the placement problem are made, taking into account the electromagnetic compatibility criterion. A productive modification of the probabilistic genetic algorithm with Pareto set forecast based on the Strength Pareto Evolutionary Algorithm (SPEA2) method is proposed, which allows reducing the computing resource in comparison with the analogues algorithms. The function of assessing the quality of the obtained solutions is defined. Also, there described are the features of its calculation on the basis of dominating of alternative solutions. A modified procedure for updating the archive of the pareto-optimal solutions is developed. Also, features of calculation of the target fitness function based on the dominance of individuals and the mechanism for sorting by niches are described. A method for estimating the density and scatter function of points in a set of solutions is developed with a certain ratio of genetic reproduction, crossing-over, mutation operators, which has made it possible to reduce computational costs. The software is developed. Computational experiments are carried out on the basis of benchmarks and shows that the given algorithm allows obtaining optimal and quazi-optimal solutions in polynomial time. Time complexity of the developed algorithm is represented as O(nlogn) in the best case and О(n3) in the worst case.

Download PDF

Keywords Electromagnetic compatibility; Accommodation; Probabilistic genetic algorithm; The Pareto set; Pareto-domination; SPEA2.
References 1. Kureychik V.V., Kureychik V.M., Rodzin S.I. Teoriya evolyutsionnykh vychisleniy [The theory of evolutionary computing]. Moscow: Fizmatlit, 2012, 260 p.
2. Gladkov L.A. Kureychik V.V., Kureychik V.M. Geneticheskie algoritmy [Genetic algorithms]. Moscow: Fizmatlit, 2010, 368 p.
3. Karpenko A.P. Sovremennye algoritmy poiskovoy optimizatsii. Algoritmy, vdokhnovlennye prirodoy: ucheb. posobie [Modern algorithms of search engine optimization. Algorithms in-spired by nature: a training manual]. Moscow: Izd-vo MGTU im. N.E. Baumana, 2014, 446 p.
4. Kureychik V.V., Zaporozhets D.Yu. Sovremennye problemy pri razmeshchenii elementov SBIS [Modern placement’s problems of VLSI], Izvestiya YuFU. Tekhnicheskie nauki [Izvestiya SFedU. Engineering Sciences], 2011, No. 7 (120), pp. 68-73.
5. Kureychik V.V., Zaruba D.V., Zaporozhets D.Yu. Ierarkhicheskiy podkhod pri razmeshchenii komponentov SBIS [Hierarchical approach for VLSI components placement], Izvestiya YuFU. Tekhnicheskie nauki [Izvestiya SFedU. Engineering Sciences], 2014, No. 7 (156), pp. 75-84.
6. Kureichik Jr. V., Kureichik V.V., Bova V. Placement of VLSI fragments based on a multilayered approach, Advances in Intelligent Systems and Computing, 2016, Vol. 464, pp. 181-190.
7. Kureychik V.V., Kureychik Vl.Vl. Razmeshcheniya fragmentov SBIS na osnove mekhanizma agregatsii fraktalov [VLSI fragment placement on the basis of fractal aggregation], Izvestiya YuFU. Tekhnicheskie nauki [Izvestiya SFedU. Engineering Sciences], 2015, No. 2 (163), pp. 196-205.
8. Suzdal'tsev I.V. Metodika resheniya zadach proektirovaniya pechatnykh plat tsifrovykh elektronnykh sredstv s uchetom kriteriev elektromagnitnoy sovmestimosti, s ispol'zovaniem evolyutsionnykh algoritmov [Methods of solving problems of designing digital circuit boards of electronic means taking into account the criteria of electromagnetic compatibility with the use of evolutionary algorithms], Elektromagnitnaya sovmestimost' i elektromagnitnaya ekologiya: Cb. nauch. dokl. 9-go Mezhdunar. simp. [Electromagnetic compatibility and electromagnetic ecology: Collection of scientific papers of the 9th International Symposium].
St. Petersburg: LETI, 2011, pp. 220-222.
9. Chermoshentsev S.F. Elektromagnitnaya sovmestimost' pechatnykh plat tsifrovykh elektronnykh sredstv [Electromagnetic compatibility of printed circuit boards digital electronic media], Informatsionnye tekhnologii [Information Technology], 2001, No. 4, pp. 17-25.
10. Sopov E.A. Veroyatnostnyy geneticheskiy algoritm i ego issledovanie [The probabilistic genetic algorithm and its study], VII Korolevskie chteniya [Royal VII reading]. Samara: Izd-vo Samarskogo nauchnogo tsentra RAN, 2003, Vol. 5, pp. 38-39.
11. Kureychik V.V., Bova V.V., Kureychik Vl.Vl. Bioinspirirovannyy poisk v zadachakh konstruktorskogo proektirovaniya i optimizatsii [Bio-inspired search in problems of engineering design and optimization], V sbornike: Informatsionnye tekhnologii v nauke, obrazovanii i upravlenii [In the collection: Information technologies in science, education and management], ed. by prof. E.L. Gloriozova, 2015, pp. 427-432.
12. Kureychik V.V., Kureychik Vl.Vl. Integrirovannyy algoritm razmeshcheniya fragmentov CBIS [Integrated VLSI fragment placement algorithm], Izvestiya YuFU. Tekhnicheskie nauki [Izvestiya SFedU. Engineering Sciences], 2014, No. 7 (156), pp. 84-93.
13. Kureychik V.V., Zhilenkov M.A. Geneticheskiy algoritm dlya resheniya optimizatsionnykh zadach s yavno vyrazhennoy tselevoy funktsiey [Genetic algorithm for solution optimization problems with explicit objective function], Informatika, vychislitel'naya tekhnika i inzhenernoe obrazovanie [Information, computing and engineering education], 2014, No. 4 (19), pp. 1-8.
14. Schaffer J.D. Multiple Objective Optimization with Vector Evaluated Genetic Algorithms, Proc. of an Intern. Conf. on Genetic Algorithms and Their Applications, Pittsburgh, PA, 1985, pp. 93-100.
15. Kacprzyk, J., Kureichik, V.M., Malioukov, S.P., Kureichik, V.V., Malioukov, A.S. Experimental investigation of algorithms developed, Studies in Computational Intelligence, 2009, Vol. 212, pp. 211-223+227-236.
16. Sherwani N.A. Algorithms for VLSI Physical Design Automation. Third Edition, Kluwer Aca-demic Publisher, USA, 2013.
17. Fonseca C.M., Fleming P.J. Genetic Algorithms for Multi-Objective Optimization: Formulation, Discussion and Generalization, Proc. of the 5th Intern. Conf. on Genetic Algorithms. San Mateo, California, 1993, pp. 416-423.
18. Alpert C.J., Dinesh P.M., Sachin S.S. Handbook of Algorithms for Physical design Automation, Auerbach Publications Taylor & Francis Group, USA, 2009.
19. Horn J., Nafpliotis N., Goldberg D.E. A Niched Pareto Genetic Algorithm for Multiobjective Optimi- zation, Proc. of the 1st IEEE Conf. on Evolutionary Computation. Piscataway, 1994, Vol. 1, pp. 82-87.
20. Ficici S.G. Solution Concepts in Coevolutionary Algorithms: A Doctor of Philosophy Diss. Brandeis University, 2004.

Comments are closed.