Разработка методов и алгоритмов для решения задачи трассировки осуществляется на протяжении многих лет, но по-прежнему является актуальной. Это связано, в первую очередь, с тем, что эта задача является NP-полной, и разработать универсальный алгоритм, позволяющий находить точное оптимальное решение за приемлемое время, затруднительно. В связи с этим, с целью снижения временной сложности алгоритма (ВСА), актуальным является разработка последовательных и параллельных бионических алгоритмов для решения задач транспортного типа на основе эволюционных стратегий. Бионические алгоритмы (БА) доказали свою эффективность при решении трудоемких задач оптимизации, аппроксимации, интеллектуальной обработки данных. К преимуществам можно отнести возможность выполнения эволюционного и генетического поиска, а также то, что БА состоит в параллельной генерации наборов квазиоптимальных альтернативных решений с возможной «миграцией» решений между этими наборами. Для моделирования бионического поиска предложены схемы, отличающиеся от известных структурой построения и учетом вариации параметров. В работе приведен процесс преобразования размера популяции при переходе из одной итерации в другую в процессе работы бионического алгоритма. Проведенные исследования разработанных бионических алгоритмов решения задач транспортного типа показали преимущество по качеству решений в сравнении с известными методами. Разработанные алгоритмы позволяют получать набор квазиоптимальных альтернативных результатов с полиномиальной временной сложность
транспортная задача, методы, адаптация, эффективность, бионический поиск, генетический оператор, алгоритм.
Введение. При решении задач об экстремальных путях эффективно используют стратегии, концепции, методы и
механизмы эволюционного моделирования на основе различных стратегий адаптации. Основные цели адаптации
связаны с экстремальными требованиями, предъявляемыми к объекту адаптации в виде максимизации эффективности
его функционирования.
1. Полуян, А. Ю. Параллельный бионический поиск для решения задач оптимизации / А. Ю. Полуян // Безопасность жизнедеятельности. Охрана труда и окружающей среды : межвуз. сб. науч. тр. — Ростов на-Дону, 2009. — С. 53–54.
2. Luger, G. Artificial Intelligence: Structures and Strategies for Complex Problem Solving, [Artificial Intelligence: Structures and Strategies for Complex Problem Solving] FourthEdition Addison-Wesley Publishing Company, 2002. — P. 928.
3. Полуян, А. Ю. Эволюционный подход к решению задач о нахождении кратчайшего пути в графе / А. Ю. Полуян // Информационные технологии в профессиональной деятельности и научной работе : сб. материалов Всерос. науч.-практ. конф. с междунар. участием. — Йошкар-Ола, 2008. — Т. 2. — С. 143–147.
4. Курейчик, В. М. Совместные методы квантового и бионического поиска / В. М. Курейчик // IEEE AIS’04, CAD-2004 : труды конф. — Москва, 2004. — С. 12–19.
5. Курейчик, В. М. Бионический метод определения путей оптимальной длины в графовых моделях / В. М. Курейчик, М. Н. Мищенко // Интегрированные модели и мягкие вычисления в искусственном интеллекте : сб. трудов III-го междунар. научно-практ. семинара. — Москва, 2005. — С. 261–266.
6. Курейчик, В. М. Поисковая адаптация: теория и практика / В. М. Курейчик, Б. К. Лебедев, О. Б. Лебедев. —Москва : Физматлит, 2006. — 272 с.
7. Курейчик, В. М. Адаптация в задачах проектирования топологии / В. М. Курейчик, Б. К. Лебедев, О. Б. Лебедев // Проблемы разработки перспективных микро- и наноэлектронных систем – 2010 : сб. науч. трудов. —Москва, 2010. — С. 170–177.
8. Емельянов, В. В. Модели искусственной жизни в оптимизационных задачах / В. В. Емельянов, В. П. Афонин // Интеллектуальные системы (AIS’04). Интеллектуальные САПР (CAD’-2004) : сб. трудов междунар. науч.- техн. конф. — Москва, 2004. — С. 39–47
9. Курейчик, В. М. Адаптация на основе самообучения / В. М. Курейчик, Б. К. Лебедев, О. Б. Лебедев, Ю. О. Чернышев. — Ростов-на-Дону : изд-во РГАСХМ, 2004. — 142 с.
10. Рейнгольд, Э. Комбинаторные алгоритмы. Теория и практика / Э. Рейнгольд, Ю. Нивергельт, Н. Део. —Москва : Мир, 1980. — 476 с.
11. Цой, Ю. Р. К выбору размера популяции / Ю. Р. Цой, В. Г. Спицын // Интеллектуальные системы (IEEAIS’04). Интеллектуальные САПР (CAD-2004): тр. междунар. науч.- техн. конф. — Москва, 2004. — С. 90–96.
12. Развитие теории эволюционного моделирования на основе генетических методов поисковой адаптации при решении оптимальных задач проектирования, сверхбольших интегральных схем (СБИС) : отчет о НИР / РГАСХМ; рук. Чернышев Ю. О.; исп. Басова А. В., Венцов Н. Н., Полуян А. Ю. — Ростов-на-Дону, 2009. — 119 с.
13. Чернышев, Ю. О. Решение задач транспортного типа генетическими алгоритмами / Ю. О. Чернышев, А. В. Басова, А. Ю. Полуян. — Ростов-на-Дону : изд-во ЮФУ, 2008. — 73 с.
14. Чернышев, Ю. О. Эволюционный подход к решению задачи о назначении через определение кратчайшего пути / Ю. О. Чернышев, П. Г. Белявский, А. Ю. Полуян // Известия ЮФУ. Технические науки. — 2008. — № 9. — С.18–24.
15. Кремер, Н. Ш. Теория вероятностей и математическая статистика / Н. Ш. Кремер. — Москва : ЮНИТИ-ДАНА, 2004. — 565 с.
16. Полуян, А. Ю. Адаптивный генетический алгоритм для решения задачи оптимизации на основе стратегии элитизма / А. Ю. Полуян // Известия ЮФУ. Технические науки. — 2008. — № 9. — С. 36–39.
17. Holland, John H. Adaptation in natural and artificial systems. [Adaptation in natural and artificial systems] The MIT Press edition, Massachusetts, London, England, 1992, 210 р.
18. Курейчик, В. М. Биоинспирированные методы в оптимизации / Л. А. Гладков, В. В. Курейчик, В. М. Курейчик, П. В. Сороколетов. — Москва : Физматлит, 2009. — 384 с.
19. Kling, R.M. Placement by Simulated Evolution [Placement by Simulated Evolution], IEEE Trans. on CAD, 1989. — Vol.8, no.3., P. 245–255.
