Preview

Вестник Донского государственного технического университета

Расширенный поиск

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

https://doi.org/10.12737/11586

Полный текст:

Аннотация

Разработка методов и алгоритмов для решения задачи трассировки осуществляется на протяжении многих лет, но по-прежнему является актуальной. Это связано, в первую очередь, с тем, что эта задача является 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.


Для цитирования:


Чернышев Ю.О., Полуян А.Ю., Панасенко П.А., Паскевич Д.Ю. Бионический поиск решения задач транспортного типа на основе стратегии адаптации. Вестник Донского государственного технического университета. 2015;15(2):85-90. https://doi.org/10.12737/11586

For citation:


Chernyshev Y.O., Poluyan A.Y., Panasenko P.A., Paskevich D.Y. Bionic search for transportation problem solution on the basis of adaptation strategy. Vestnik of Don State Technical University. 2015;15(2):85-90. (In Russ.) https://doi.org/10.12737/11586

Просмотров: 58


Creative Commons License
Контент доступен под лицензией Creative Commons Attribution 4.0 License.


ISSN 1992-5980 (Print)
ISSN 1992-6006 (Online)