Статья

Название статьи БИОИНСПИРИРОВАННЫЙ АЛГОРИТМ КОМПОНОВКИ БЛОКОВ ЭВА НА ОСНОВЕ МОДИФИЦИРОВАННОЙ РАСКРАСКИ ГРАФА
Автор В.В. Курейчик, Д.В. Заруба, Д.Ю. Запорожец
Рубрика РАЗДЕЛ I. МОДЕЛИРОВАНИЕ И ПРОЕКТИРОВАНИЕ
Месяц, год 04, 2015
Индекс УДК 004.896
DOI
Аннотация Рассматривается решение одной из ключевых задач этапа автоматизированного конструкторского проектирования – компоновки блоков электронно-вычислительной аппаратуры. Данная задача относится к классу NP-трудных и NP-сложных задач, т.е. для нахождения ее решения за полиномиальное время целесообразно разрабатывать эвристические подходы и методы, позволяющие получать наборы квазиоптимальных решений. Приведена классическая постановка задачи компоновки блоков ЭВА с учетом количества разбиений графа, соответствующего коммутационной схеме, а также сформулирован критерий оптимизации. Предложен новый биоинспирированный подход к решению задачи компоновки блоков ЭВА на основе модифицированной раскраски графа. Построена архитектура биоинспирированного поиска на основе использования эволюционного подхода, который позволяет повысить эффективность поиска квазиоптимальных решений. Разработан модифицированный генетический алгоритм компоновки, позволяющий получать решения заданной точности за полиномиальное время. Предложенная архитектура биоинспирированного поиска на основе использования эволюционной модели позволяет эффективно управлять процессом поиска. Для демонстрации работы алгоритма приведено описание примера решения задачи компоновки блоков ЭВА на основе модифицированной раскраски графа. Для проведения экспериментальных исследований была разработана программная среда, реализующая разработанный генетический алгоритм компоновки блоков ЭВА. Был проведен вычислительный эксперимент по сравнению простого и модифицированного генетических алгоритмов с классическими последовательным и итерационным алгоритмами. Результаты экспериментальных исследований выявили зависимость временной сложности разработанного модифицированного генетического алгоритма от значений входных параметров. Серии экспериментов позволили уточнить теоретическую временную сложность алгоритма, которая ориентировочно составляет О(n2).

Скачать в PDF

Ключевые слова Конструкторское проектирование; оптимизация; компоновка блоков ЭВА; биоинспирированный поиск; генетический алгоритм.
Библиографический список 1. Гладков Л.А., Курейчик В.В., Курейчик В.М., Сороколетов П.В. Биоинспирированные методы в оптимизации. – М.: Физматлит, 2009. – 384 с.
2. Гладков Л.А., Курейчик В.В., Курейчик В.М. Генетические алгоритмы. – М.: Физматлит, 2010. – 368 с.
3. Курейчик В.В., Курейчик В.М., Родзин С.И. Теория эволюционных вычислений. – М.: Физматлит, 2012. – 260 с.
4. Емельянов В.В., Курейчик В.В., Курейчик В.М. Теория и практика эволюционного моделирования. – М.: Физматлит, 2003. – 432 c.
5. Норенков И.П. Основы автоматизированного проектирования. – М.: Изд-во МГТУ им. Н.Э. Баумана, 2006. – 360 с.
6. Sherwani N.A. Algorithms for VLSI Physical Design Automation. Third Edition, Kluwer Academic Publisher, USA, 2013.
7. Lim S.K. Practical Problems in VLSI Physical Design Automation, Springer Science + Business Media B.V, Germany, 2008.
8. Alpert C.J., Dinesh P.M., Sachin S.S. Handbook of Algorithms for Physical design Automation, Auerbach Publications Taylor & Francis Group, USA, 2009.
9. Alpert C.J. et all. Hypergraph Partitioning with Fixed Vertices // IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems. – February 2002. – Vol. 19, № 2. – P. 267-271.
10. Zaporozhets D.U., Zaruba, D.V., Kureichik, V.V. Representation of solutions in genetic VLSI placement algorithms // IEEE East-West Design & Test Symposium – (EWDTS’2014) Kiev, Ukraine, 2014. – P. 1-4.
11. Курейчик В.М., Курейчик В.В. Генетический алгоритм разбиения графа // Известия Российской академии наук. Теория и системы управления. – 1999. – № 4. – С. 580-588.
12. Kureichik V.V., Kureichik V.V. Jr., Zaruba D.V. Partitioning of ECE schemes components based on modified graph coloring algorithm // IEEE East-West Design & Test Symposium – (EWDTS’2014) Kiev, Ukraine, 2014. – P. 1-4.
13. Vose M.D. Modeling simple genetic algorithms // In Whitley L.D. (ed): Foundations of Genetic Algorithms 2. Morgan Kaufmann, 2003.
14. Курейчик В.М., Курейчик В.В. Генетические алгоритмы в комбинаторно-логических задачах искусственного интеллекта // Известия ТРТУ. – 1999. – № 3 (13). – С. 126-128.
15. Курейчик В.В., Курейчик Вл.Вл. Биоинспирированный алгоритм разбиения схем при проектировании СБИС // Известия ЮФУ. Технические науки. – 2013. – № 7 (144). – С. 23-29.
16. Курейчик В.В. Алгоритмы разбиения графа на основе генетического поиска // Известия ТРТУ. – 1999. – № 3 (13). – С. 97-104.
17. Курейчик В.В., Сороколетов П.В. Композитные бионические алгоритмы в компоновке блоков // Известия ЮФУ. Технические науки. – 2006. – № 8 (63). – С. 41-46.
18. Курейчик В.В., Сороколетов П.В. Эволюционные алгоритмы разбиения графов и гиперграфов // Известия ТРТУ. – 2004. – № 3 (38). – С. 42-49.
19. Gladkov L.A., Kureichik V.V., Kravchenko Y.A. Evolutionary algorithm for extremal subsets comprehension in graphs // World Applied Sciences Journal. – 2013. – P. 1212-1217.
20. Kacprzyk, J., Kureichik, V.M., Malioukov, S.P., Kureichik, V.V., Malioukov, A.S. Experimental investigation of algorithms developed // Studies in Computational Intelligence, 212. – 2009. – P. 211-223+227-236.

Comments are closed.