Статья

Название статьи ПОДХОД К ИССЛЕДОВАНИЮ ОКРЕСТНОСТЕЙ В РОЕВЫХ АЛГОРИТМАХ ДЛЯ РЕШЕНИЯ ОПТИМИЗАЦИОННЫХ ЗАДАЧ
Автор Э.В. Кулиев, А.А. Лежебоков, А.Н. Дуккардт
Рубрика РАЗДЕЛ I. ЭВОЛЮЦИОННОЕ МОДЕЛИРОВАНИЕ, ГЕНЕТИЧЕСКИЕ И БИОНИЧЕСКИЕ АЛГОРИТМЫ
Месяц, год 07, 2014
Индекс УДК 004.82
DOI
Аннотация Рассмотрена ключевая проблема роевых алгоритмов и биоинспирированного подхода, которая заключается в определении функции близости решений и исследовании возникающих окрестностей для решения задач оптимизации. Подробно рассмотрена одна из важнейших задач этапа конструкторского проектирования, а именно задача размещения компонентов сверхбольших интегральных схем, качество решения которой напрямую влияет на качество трассировки схем и их тепловых, временных, энергетических характеристик. Решение поставленной проблемы окрестностей и близости решений внутри них продемонстрировано на примере их исследования гибридными методами поиска решений. Представлена методика поиска окрестностей в роевом алгоритме, на основе принципов самоорганизации и жадного подхода. Важным механизмом в работе алгоритма колонии пчел является исследование перспективных решений и позиций их окрестностей в пространстве решений. Авторами предлагается новый принцип формирования окрестности позиций в пространстве решений, для этого используется понятие окрестности в круговом пространстве поиска. Рассмотрен биоинспирированный подход к исследованию окрестности поиска решений. Основная идея данного подхода заключается в последовательной работе генетического и эволюционного алгоритмов. В методе биоинспирированного поиска оптимальных решений авторами предложен адаптивный фильтр, отсекающий решения с низким значением целевой функции. Проведены экспериментальные исследования, подтверждающие, что вычислительная и временная сложность разработанного подхода не выходит за пределы полиномиальной зависимости. Результаты исследований позволили авторам отметить, что в генетическом алгоритме в большей степени имеет место фактор случайности, а в эволюционном алгоритме фактор направленности.

Скачать в PDF

Ключевые слова Роевой алгоритм; генетический алгоритм; эволюционный алгоритм; «жадный» оператор; адаптация; окрестность; популяция.
Библиографический список 1. ебедев Б.К. Методы поисковой адаптации в задачах автоматизированного проектирования СБИС: Монография. – Таганрог: Изд-во ТРТУ, 2000. – 192 с.
2. Норенков .П., Арутюнян Н.М. Эволюционные методы в задачах выбора проектных решений // Электронное научно-техническое издание «Наука и образование». – 2007. – № 9.
3. Кулиев Э.В., ежебоков А.А. Исследование характеристик гибридного алгоритма размещения // Известия ЮФУ. Технические науки. – 2013. – № 3 (140). – С. 255- 261.
4. Кулиев Э.В. Задача размещения элементов ЭВ с использованием генетического алгоритма и алгоритма пчелиной колонии // Труды конгресса по интеллектуальным системам и информационным технологиям «IS–IT’12». Научное издание в 4-х томах. Т. 3. – М.: Физматлит, 2012. – С. 99-104.
5. Курейчик В.В., Запорожец .Ю. Современные проблемы при размещении элементов СБИС // Известия ЮФУ. Технические науки. – 2011. – № 7 (120). – С. 68-73.
6. Кулиев Э.В., Заруба .В. Работа гибридного поиска размещения компонентов СБИС // Труды молодых ученых Южного федерального университета и Южного научного центра Р Н «Высокопроизводительные вычислительные системы». Вып. 2. – Ростов-на-Дону – Таганрог, 2012. – С. 43-46.
7. Кулиев Э.В. Генетический алгоритм решения задачи размещения элементов СБИС // IX Всероссийская научная конференция молодых ученых, аспирантов и студентов «Ин-формационные технологии, системный анализ и управление». – Таганрог: Изд-во ТТИ ЮФУ, 2012. – Т. 2. – С. 55-59.
8. Лебедев Б.К., Лебедев О.Б. Методы размещения: Монография. – Таганрог: Изд-во ТРТУ, 2006.
9. Лебедев Б.К., Шашелов А.А. Исследование механизмом муравьиной адаптации при решении задачи покрытия функциональной схемы // Труды Конгресса по интеллектуальным системам и информационным технологиям «AIS-IT’10». Научное издание в 4-х томах. Т. 3. – М.: Физматлит, 2010. − С. 118-127.
10. Курейчик В.М., Лебедев Б.К., Лебедев О.Б. Поисковая адаптация. Теория и практика. – М.: Физматлит, 2006. − 272 с.
11. Курейчик В.М., Лебедев Б.К., Лебедев О.Б. Адаптация в задачах проектирования топологии // Проблемы разработки перспективных микро- и наноэлектронных систем – 2010: Сб. науч. тр. / Под ред. .Л. Стемпковского. – М.: ИППМ Р Н, 2010. – С. 170-177.
12. Lučić P., Teodorović D. Computing with Bees: Attacking Complex Transportation Engineering Problems // International Journal on Artificial Intelligence Tools. – 2003. – № 12. – P. 375-394.
13. 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.
14. 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.
15. Курейчик В.В., Полупанова Е.Е. Эволюционная оптимизация на основе алгоритма колонии пчел // Известия ЮФУ. Технические науки. – 2009. – № 12 (101). – С. 41-46.
16. Курейчик В.М., Лебедев Б.К., Лебедев О.Б. Решение задачи размещения на основе эволюционного моделирования // Известия академии наук. Теория и системы управления. – 2007. – № 4. – С. 78-90.

Comments are closed.