Муравьиный алгоритм определения критических связей в СБИС Зав. каф. САПР ИКТиИБ ЮФУ, д.т.н., проф. В.В. Курейчик, аспирант каф САПР ИКТиИБ ЮФУ, Д. Ю. Запорожец, - презентация

1 Муравьиный алгоритм определения критических связей в СБИС Зав. каф. САПР ИКТиИБ ЮФУ, д.т.н., проф. В.В. Курейчик, аспирант каф САПР ИКТиИБ ЮФУ, Д. Ю. Запорожец, аспирант каф САПР ИКТиИБ ЮФУ, Д.В. Заруба VI Всероссийская научно-техническая конференция «Проблемы разработки перспективных микро- и наноэлектронных систем Москва, 29 сентября – 3 октября 2014 г.

2 VI Всероссийская научно-техническая конференция «Проблемы разработки перспективных микро- и наноэлектронных систем Москва, 29 сентября – 3 октября 2014 г. Развитие нанометровых технологий в области производства требует развития новых методов и алгоритмов проектирования. Одним из таких подходов являются бионические методы и биоинспирированные алгоритмы, использующие стратегии эволюционного моделирования и принципы природных механизмов принятия решений. Бионика – есть решение инженерных и технических задач на основе изучения структуры и жизнедеятельности живых организмов. Бионические методы включают в себя генетические алгоритмы, эволюционные алгоритмы, алгоритмы, моделирующие механизмы принятия решений природными системами. Это методы роевого интеллекта, основанные на принципах коллективного поведения децентрализованной самоорганизующейся системы. Данный класс алгоритмов анализирует различные области пространства решений одновременно, и они более приспособлены к нахождению новых областей с оптимальными значениями целевой функции (ЦФ) при решении задач проектирования. Биоинспирированные методы

3 VI Всероссийская научно-техническая конференция «Проблемы разработки перспективных микро- и наноэлектронных систем Москва, 29 сентября – 3 октября 2014 г. Основные положения поведения муравьев в биологических системах 1 Изолированный муравей перемещается произвольно. 2 Муравей, сталкивающийся с прежде проложенным следом, может обнаружить это и решить с высокой вероятностью следовать за первым муравьем, таким образом, усиливая след своим собственными метками. Коллективное поведение, которое возникает при этом, – форма автокаталитического поведения, при котором чем больше муравьев следует по уже проложенному пути, тем более привлекательным становится след для последующих. 3 Процесс, таким образом, охарактеризован положительным циклом обратной связи, где вероятность, с которой муравей выбирает путь, увеличивается с ростом числа муравьев, которые прежде выбирали тот же путь

4 VI Всероссийская научно-техническая конференция «Проблемы разработки перспективных микро- и наноэлектронных систем Москва, 29 сентября – 3 октября 2014 г. Пример моделирования поведения муравьев в природе

5 VI Всероссийская научно-техническая конференция «Проблемы разработки перспективных микро- и наноэлектронных систем Москва, 29 сентября – 3 октября 2014 г. Модель муравьиного алгоритма Муравьиный алгоритм (Ant Colony) не копирует существующую природную экосистему, а использует имитацию колонии как средство оптимизации, при котором система несколько отличается от естественной: 1 искусственные муравьи (агенты) имеют некоторую память, 2 они не полностью слепы, 3 они находятся в пространстве, где время дискретно

6 VI Всероссийская научно-техническая конференция «Проблемы разработки перспективных микро- и наноэлектронных систем Москва, 29 сентября – 3 октября 2014 г. Пример решения задачи коммивояжера муравьиным алгоритмом

7 VI Всероссийская научно-техническая конференция «Проблемы разработки перспективных микро- и наноэлектронных систем Москва, 29 сентября – 3 октября 2014 г.. При решении задач конструкторского проектирования возникает вопрос оценки полученных результатов. Одной из таких оценок (критерием) является длина критической связи. Под критической связью – понимается гамильтонова цепь – гамильтонов цикл без возвращения в стартовую вершину Этот подход позволит свести поиску критических связей к определению гамильтоновых цепей в неориентированном конечном графе.

8 VI Всероссийская научно-техническая конференция «Проблемы разработки перспективных микро- и наноэлектронных систем Москва, 29 сентября – 3 октября 2014 г. Пример представления цепи в виде гамильтоновой цепи

9 VI Всероссийская научно-техническая конференция «Проблемы разработки перспективных микро- и наноэлектронных систем Москва, 29 сентября – 3 октября 2014 г. Постановка задачи Коммивояжеру необходимо посетить W городов, не заезжая в один и тот же город дважды, и вернуться в исходный пункт по маршруту с минимальной стоимостью. Имеем: полный граф G=(X,U), где |X| = n – множество вершин (города), |U| = m – множество ребер (возможные пути между городами). Дана матрица смежности R(i,j), где i, j {1… n}, задающая стоимости путей из вершины x i в x j. Требуется найти перестановку из элементов множества X, такую, что целевая функция (ЦФ)

10 VI Всероссийская научно-техническая конференция «Проблемы разработки перспективных микро- и наноэлектронных систем Москва, 29 сентября – 3 октября 2014 г. Архитектура поиска

11 VI Всероссийская научно-техническая конференция «Проблемы разработки перспективных микро- и наноэлектронных систем Москва, 29 сентября – 3 октября 2014 г. Свойства муравья bi(t) (i = 1,..., n) – количество муравьев в i вершине в момент времени t. При этом общее количество муравьев m Муравьи обладают «зрением» Каждый муравей способен улавливать след феромона, который определяет желание муравья пройти по данному ребру. эффективность промежутка (i,j) на протяжении маршрута, выбранного k-тым агентом: Вероятность перехода муравья из вершины i в вершину j определяется следующим соотношением

12 VI Всероссийская научно-техническая конференция «Проблемы разработки перспективных микро- и наноэлектронных систем Москва, 29 сентября – 3 октября 2014 г. Э КСПЕРИМЕНТАЛЬНЫЕ ИССЛЕДОВАНИЯ График зависимости времени решения от числа популяций Наилучший полученный маршрут в ЗК eilons 50 График зависимости времени решения от числа генераций График зависимости длины пути от числа генераций Временная сложность алгоритмов O(n logn), в худшем случае – О(n 3 )

13 VI Всероссийская научно-техническая конференция «Проблемы разработки перспективных микро- и наноэлектронных систем Москва, 29 сентября – 3 октября 2014 г. Спасибо за внимание!