Бионический поиск решения задач транспортного типа на основе стратегии адаптации

Разработка методов и алгоритмов для решения задачи трассировки осуществляется на протяжении многих лет, но по-прежнему является актуальной. Это связано, в первую очередь, с тем, что эта задача является NP -полной, и разработать универсальный алгоритм, позволяющий находить точное оптимальное решение за приемлемое время, затруднительно. В связи с этим, с целью снижения временной сложности алгоритма (ВСА), актуальным является разработка последовательных и параллельных бионических алгоритмов для решения задач транспортного типа на основе эволюционных стратегий. Бионические алгоритмы (БА) доказали свою эффективность при решении трудоемких задач оптимизации, аппроксимации, интеллектуальной обработки данных. К преимуществам можно отнести возможность выполнения эволюционного и генетического поиска, а также то, что БА состоит в параллельной генерации наборов квазиоптимальных альтернативных решений с возможной «миграцией» решений между этими наборами. Для моделирования бионического поиска предложены схемы, отличающиеся от известных структурой построения и учетом вариации параметров. В работе приведен процесс преобразования размера популяции при переходе из одной итерации в другую в процессе работы бионического алгоритма. Проведенные исследования разработанных бионических алгоритмов решения задач транспортного типа показали преимущество по качеству решений в сравнении с известными методами. Разработанные алгоритмы позволяют получать набор квазиоптимальных альтернативных результатов

транспортная задача, методы, адаптация, эффективность, бионический поиск, генетический оператор, алгоритм, transportation problem, methods, adaptation, efficiency, bionic search, genetic operator, algorithm

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.