Статья

Название статьи МОДИФИКАЦИЯ ВЕРОЯТНОСТНОГО ГЕНЕТИЧЕСКОГО АЛГОРИТМА РЕШЕНИЯ ЗАДАЧИ РАЗМЕЩЕНИЯ ЭЛЕМЕНТОВ ЭВА С УЧЕТОМ ЭЛЕКТРОМАГНИТНОЙ СОВМЕСТИМОСТИ
Автор М. А. Жиленков, В. В. Курейчик
Рубрика РАЗДЕЛ I. АВТОМАТИЗАЦИЯ ПРОЕКТИРОВАНИЯ
Месяц, год 07, 2017
Индекс УДК 004.896
DOI
Аннотация Предлагается решение одной из важных задач этапа конструкторского проектирования – задачи размещения разногабаритных элементов электронно-вычислительной аппаратуры (ЭВА). При решении данной задачи в качестве основного критерия был выбран критерий электромагнитной совместимости (ЭМС). В связи с обработкой огромных массивов информации задача размещения разногабаритных элементов относится к классу NP-сложных и NP-трудных задач дискретной оптимизации. В статье приводится и описана постановка и математическая модель задачи размещения с учетом критерия ЭМС. Для решения данной задачи в работе предлагается продуктивная модификация вероятностного генетического алгоритма с прогнозом множества Парето на основе метода Strength Pareto Evolutionary Algorithm (SPEA2), что позволяет сократить использование вычислительных ресурсов. Также в работе определена функция оценки качества получаемых решений и описаны особенности ее вычисления, на основе доминирования альтернативных решений и механизма сортировки по нишам. Разработана модифицированная процедура обновления архива паретто-оптимальных решений. Представлен метод оценки функции плотности и разброса точек в множестве решений при определенном соотношение модифицированных генетических операторов репродукции, кроссинговера и мутации, что позволило уменьшить вычислительные затраты. Создана программная среда. Проведен вычислительный эксперимент на тестовых примерах бенчмарках. Проведенные серии тестов и экспериментов показали, что использование данного алгоритма позволяет получать наборы оптимальных и квазиоптимальных решений за полиномиальное время, что говорит о перспективности его применения.

Скачать в PDF

Ключевые слова Электромагнитная совместимость; размещение; вероятностный генетический алгоритм; множество Парето; парето-доминирование; SPEA2.
Библиографический список 1. Курейчик В.В., Курейчик В.М., Родзин С.И. Теория эволюционных вычислений. – М.: Физматлит, 2012. – 260 с.
2. Гладков Л.А. Курейчик В.В., Курейчик В.М. Генетические алгоритмы. – М.: Физматлит, 2010. – 368 c.
3. Карпенко А.П. Современные алгоритмы поисковой оптимизации. Алгоритмы, вдохновленные природой: учеб. пособие. – М.: Изд-во МГТУ им. Н.Э. Баумана, 2014. – 446 с.
4. Курейчик В.В., Запорожец Д.Ю. Современные проблемы при размещении элементов СБИС // Известия ЮФУ. Технические науки. – 2011. – № 7 (120). – С. 68-73.
5. Курейчик В.В., Заруба Д.В., Запорожец Д.Ю. Иерархический подход при размещении компонентов СБИС // Известия ЮФУ. Технические науки. – 2014. – № 7 (156). – С. 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. – P. 181-190.
7. Курейчик В.В., Курейчик Вл.Вл. Размещения фрагментов СБИС на основе механизма агрегации фракталов // Известия ЮФУ. Технические науки. – 2015. – № 2 (163).
– С. 196-205.
8. Суздальцев И.В. Методика решения задач проектирования печатных плат цифровых элек-тронных средств с учетом критериев электромагнитной совместимости, с использованием эволюционных алгоритмов // Электромагнитная совместимость и электромагнитная эко-логия: Cб. науч. докл. 9-го Междунар. симп. – СПб. : ЛЭТИ, 2011. – С. 220-222.
9. Чермошенцев С.Ф. Электромагнитная совместимость печатных плат цифровых элек-тронных средств // Информационные технологии. – 2001. – № 4. – С. 17-25.
10. Сопов Е.А. Вероятностный генетический алгоритм и его исследование // VII Королёвские чтения. – Самара: Изд-во Самарского научного центра РАН, 2003. – Т. 5. – С. 38-39.
11. Курейчик В.В., Бова В.В., Курейчик Вл.Вл. Биоинспирированный поиск в задачах конструкторского проектирования и оптимизации // В сборнике: Информационные технологии в науке, образовании и управлении / под ред. проф. Е.Л. Глориозова. – 2015. – С. 427-432.
12. Курейчик В.В., Курейчик Вл.Вл. Интегрированный алгоритм размещения фрагментов CБИС // Известия ЮФУ. Технические науки. – 2014. – № 7 (156). – С. 84-93.
13. Курейчик В.В., Жиленков М.А. Генетический алгоритм для решения оптимизационных задач с явно выраженной целевой функцией // Информатика, вычислительная техника и инженерное образование. – 2014. – № 4 (19). – С. 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. – P. 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. – P. 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. – Р. 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. – P. 82-87.
20. Ficici S.G. Solution Concepts in Coevolutionary Algorithms: A Doctor of Philosophy Diss. Brandeis University, 2004.

Comments are closed.