Статья

Название статьи БИОНИЧЕСКИЙ ПОИСК РЕШЕНИЯ КОНСТРУКТОРСКИХ ЗАДАЧ
Автор Н.В. Холопова, А.Н. Самойлов, Э.В. Кулиев
Рубрика РАЗДЕЛ II. ВЫЧИСЛИТЕЛЬНАЯ ТЕХНИКА И ИНФОРМАТИКА
Месяц, год 07, 2015
Индекс УДК 004.82
DOI
Аннотация Рассмотрена ключевая проблема роевых алгоритмов и бионического подхода, которая заключается в определении функции близости решений и исследовании возникающих окрестностей для решения задач оптимизации. Подробно рассмотрена одна из важнейших задач этапа конструкторского проектирования, а именно задача размещения компонентов сверхбольших интегральных схем (СБИС), качество решения которой напрямую влияет на качество трассировки схем и их тепловых, временных, энергетических характеристик. Решение поставленной проблемы окрестностей и близости решений внутри них продемонстрировано на примере исследования гибридными методами поиска решений. В основе гибридизации заложена последовательная работа генетических алгоритмов, в том числе генетического поиска и эволюционного моделирования, а также методов инспирированных поведением биологических систем, на примере работы колонии пчел. В статье предложена интегрированная схема поиска, позволяющая улучшать решения на каждой стадии процесса размещения. Бионический поиск при решении задачи размещения компонентов СБИС включает в себя последовательную работу двух алгоритмов: генетического и роевого. Отличительной особенностью разработанного бионического подхода является его универсальность в поиске оптимальных решений, за счет смены направления поиска. Предлагается технология построения генетических операторов, адаптированных для задачи размещения компонентов СБИС. Для получения эффективных решений предлагается использовать модифицированные генетические операторы. Применение «слепого» подхода подразумевает изменение структуры данных хромосомы (перестановка пары хромосом). Проведены экспериментальные исследования, подтверждающие, что временная сложность разработанного бионического поиска, не выходит за пределы полиномиальной зависимости, и может быть выражена формулой: O(nlogn)- O(n2), где n – число элементов схемы.

Скачать в PDF

Ключевые слова Роевой алгоритм; генетический алгоритм; адаптация; окрестность; популяция.
Библиографический список 1. Курейчик В.В., Запорожец Д.Ю. Современные проблемы при размещении элементов СБИС // Известия ЮФУ. Технические науки. – 2011. – № 7 (120). – С. 68-73.
2. Норенков И.П. Арутюнян Н.М. Эволюционные методы в задачах выбора проектных решений // Электронный журнал «Наука и образование». – 2007. – № 9.
3. Курейчик В.В., Курейчик Вл.Вл. Биоинспирированный поиск при проектировании и управлении // Известия ЮФУ. Технические науки. – 2012. – № 11 (136). – С. 178-183.
4. Teodorović D., Dell’Orco M. Bee Colony Optimization – a Cooperative Learning Approach to Complex Transportation Problems // Advanced OR and AI Methods in Transportation: Proceedings of 16th Mini–EURO Conference and 10th Meeting of EWGT (13-16 September 2005). – Poznan: Publishing House of the Polish Operational and System Research, 2005. – P. 51-60.
5. Неупокоева Н.В., Курейчик В.М. Квантовые и генетические алгоритмы размещения компонентов ЭВА: Монография. – Таганрог: Изд-во ТТИ ЮФУ, 2010. - 144 с.
6. . Курейчик В.В., Курейчик В.М., Родзин С.И. Теория эволюционных вычислений. – М.: Физматлит, 2012. – 260 c.
7. Кулиев Э.В., Лежебоков А.А. О гибридном алгоритме размещения компонентов СБИС // Известия ЮФУ. Технические науки. – 2012. – № 11 (136). – С. 188-192.
8. Курейчик В.В., Курейчик Вл.Вл. Архитектура гибридного поиска при проектировании // Известия ЮФУ. Технические науки. – 2012. – № 7 (132). – С. 22-27.
9. Курейчик В.В., Запорожец Д.Ю. Роевой алгоритм в задачах оптимизации // Известия ЮФУ. Технические науки – 2010. – № 7 (108). – С. 28-32.
10. Lučić P., Teodorović D. Computing with Bees: Attacking ComplexTransportation Engineering Problems// International Journal on Artificial Intelligence Tools. – 2003. – No. 12. – P. 375-394.
11. Quijano N., Passino K.M. Honey Bee Social Foraging Algorithms for Resource Allocation: Theory and Application. – Columbus: Publishing house of the Ohio State University, 2007. – 39 p.
12. Курейчик В.В., Полупанова Е.Е. Эволюционная оптимизация на основе алгоритма колонии пчел // Известия ЮФУ. Технические науки. – 2009. – № 12 (101). – С. 41-46.
13. Курейчик В.В., Сороколетов П.В. Концептуальная модель представления решений в генетических алгоритмах // Известия ЮФУ. Технические науки. – 2008. – № 9 (86). – С. 7-12.
14. Лебедев Б.К., Лебедев О.Б. Методы размещения: Монография. – Таганрог: Изд-во ТРТУ, 2006.
15. Гладков Л.А., Курейчик В.В., Курейчик В.М., Сороколетов П.В. Биоинспирированные методы в оптимизации. – М.: Физматлит, 2009. – 384 с.
16. Pham D.T., Ghanbarzadeh A., Koз E., Otri S., Rahim S., Zaidi M. The Bees Algorithm. 2008.
17. Курейчик В.М. Кажаров А.А. Использование роевого интеллекта в решении NP-трудных задач // Известия ЮФУ. Технические науки. – 2011. – № 7 (120). – С. 30-37.
18. Лебедев Б.К. Методы поисковой адаптации в задачах автоматизированного проектирования СБИС: Монография. – Таганрог: Изд-во ТРТУ, 2000. – 192 с.
19. Кулиев Э.В. Задача размещения элементов ЭВА с использованием генетического алгоритма и алгоритма пчелиной колонии // Труды конгресса по интеллектуальным системам и информационным технологиям «IS–IT’12». Научное издание в 4-х т. Т. 3. – М.: Физматлит, 2012. – С. 99-104.
20. Кулиев Э.В., Заруба Д.В. Работа гибридного поиска размещения компонентов СБИС // Труды молодых ученых Южного федерального университета и Южного научного центра РАН «Высокопроизводительные вычислительные системы». Вып. 2. Изд-во Ростов-на-Дону – Таганрог, 2012. – С. 43-46.
21. Кулиев Э.В., Лежебоков А.А. Исследование характеристик гибридного алгоритма размещения // Известия ЮФУ. Технические науки. – 2013. – № 3 (140). – С. 255-261.

Comments are closed.