Конструирование приближенных алгоритмов
Изучение задачи маршрутизации транспорта. Построение математической модели. Оценка способов решения задач маршрутизации. Обзор алгоритмов: муравьиного, Particle Swarm Optimization, Artificial Bee Colony, меметического, биоиспирированных в задачах VRP.
| Рубрика | Программирование, компьютеры и кибернетика |
| Вид | дипломная работа |
| Язык | русский |
| Дата добавления | 11.08.2017 |
| Размер файла | 2,4 M |
Отправить свою хорошую работу в базу знаний просто. Используйте форму, расположенную ниже
Студенты, аспиранты, молодые ученые, использующие базу знаний в своей учебе и работе, будут вам очень благодарны.
Список использованной литературы
1. Кормен, Томас. Алгоритмы: построение и анализ / Т. Кормен, Ч. Лейзерсон, Р. Ривест ; [пер. с англ. под ред. А. Шеня]. -- М. : МЦНМО, 2002. -- 955 с.
2. Современные алгоритмы поисковой оптимизации. Алгоритмы, вдохновленные природой : учебное пособие / А. П. Карпенко. -- Москва : Издательство МГТУ им. Н. Э. Баумана, 2014. -- 446 с.
3. Dawkins R. Universal Darwinism in D.S. Bendall (ed.), Evolution: From Molecules to Men, Cambridge University Press, Cambridge, 1983, P. 403-425.
4. Dawkins R. The Selfish Gene. Oxford University Press, 1976, 192 p. 26
5. Moscato P. On Evolution, Search, Optimization, Genetic Algorithms and Martial Arts: Towards Memetic Algorithms // Caltech Concurrent Computation Program (report 826), 1989.
6. Ong Y.S., Keane A.J. Meta-Lamarckian learning in memetic algorithms // IEEE Transactions on Evolutionary Computation. V.8 (2), 2004. P. 99-110.
7. Krasnogor N. Coevolution of genes and memes in memetic algorithms. Graduate Student Workshop. 371 p.
8. Kendall G., Soubeiga E., Cowling P. Choice function and random hyperheuristics // 4th Asia-Pacific Conference on Simulated Evolution and Learning, SEAL 2002, P. 667- 671.
9. Майника Э. Алгоритмы оптимизации на сетях и графах. М: Мир, 1981. 323 с.
10. R. G. Ghanem and P. D. Spanos, Stochastic Finite Elements: A Spectral Approach, Courier Corporation, 2003.
11. S. Binitha and S.S. Sathya, “A survey of bio inspired optimization algorithms,” International Journal of Soft Computing and Engineering, vol. 2, pp. 137-151, 2012.
12. Vasek Chvatal, William J. Cook, George B. Dantzig, Delbert Ray Fulkerson,and Selmer M. Johnson. Solution of a large-scale traveling-salesman problem. In 50 Years of Integer Programming 1958-2008 - From the Early Years to the State-of-the-Art, pages 7-28. 2010.
13. F. Dressler and O. B. Akan, “A survey on bio-inspired networking, ”Computer Networks, vol. 54, no. 6, pp. 881-900, 2010.
14. A.R. Mehrabian and C. Lucas, “A novel numerical optimization algorithm inspired from weed colonization,” Ecological Informatics, vol. 1, no. 4, pp. 355-366, 2006.
15. M.Dorigo, G. Di Caro, and L.M. Gambardella, “Ant algorithms for discrete optimization,” Artificial Life, vol. 5, no. 2, pp. 137-172, 1999.
16. M. Clerc, Particle Swarm Optimization, vol. 93, John Wiley & Sons, 2010.
17. D. Karaboga, B. Akay, “A survey: algorithms simulating bee swarm intelligence,” Artificial Intelligence Review, vol. 31, no. 1-4, pp. 61-85, 2009.
18. Z. Yuan, M. A.M. deOca, M. Birattari, T. Stutzle, “Continuous optimization algorithms for tuning real and integer parameters of swarm intelligence algorithms,” Swarm Intelligence, vol.6, no. 1, pp. 49-75, 2012.
19. Dorigo, M., Stutzle, T. Ant colony optimization. The MIT press, 2004
20. Hitoshi K., Junichi O. Solving Time-Dependent Traveling Salesman Problems Using Ant Colony Optimization Based on Predicted Traffic // Advances in Intelligent and Soft Computing. 2012. ќ 151.
21. J.F. Cordeau, M. Gendreau, G. Laporte, J.Y. Potvin, and F.Semet. A guide to vehicle routing heuristics. Journal of the Operational Research Society, pages 512-522, May 2002.
22. Stutzle, T., Hoos, H. H. MAN-MIN ant system. Future Generation Computer System, Vol. 16, No. 8, 2000, 889-914.
23. Jean-Francois Cordeau, Michel Gendreau, and Gilbert Laporte. A tabu search heuristic for periodic and multi-depot vehicle routing problems. Networks, 30(2):105-119, 1997.
24. V.V. Zakharov and A.N. Shchegryaev. Multi-period cooperative vehicle routing games. Contributions to Game Theory and Management, 7(2):349- 359, April 2014.
25. X.S. Xu, J. Ma, J.S. Lei. An improved ant colony optimization for the maximum clique problem, Proceedings of the 3rd International Conference on Natural Computation, pp. 766-770, IEEE Press, 2007.
26. V. Zakharov and M. Dementieva. Multistage cooperative games and problem of time consistency. International Game Theory Review, 6:157-170, 2004.
27. M. Wineberg, F. Oppacher. Enhancing the GAs ability to cope with dynamic environments, Proceedings of the 2000 International Conference on Genetic and Evolutionary Computation, pp. 3-10, 2000.
28. J.Q. Yang, J.G. Yang, G.L. Chen. An improved ant colony system based on negative biased, Proceedings of the International Conference on Advanced Measurement and Test, Y.W. Wu, editors, pp. 439-440, pp. 558-562, 2010.
29. L.N. Xing, Y.W. Chen, P. Wang, Q.S. Zhao, J. Xiong. Knowledge-based ant colony optimization for flexible job shop scheduling problems, Applied Soft Computing, 10(3), pp. 888-896, Elsevier Science, 2010.
30. L. P. Wong, M. Y. H. Low, C. S. Chong, Bee colony optimization with local search for travelling salesman problem. International Journal on Artificial Intelligence Tools, 19, pp. 305-334, 2010.
A. Isaacs, V. Puttige, T. Ray, W. Smith, S. Anavatti. Development of a memetic algorithm for dynamic multi-objective optimization and its application for online neural network modelling of UAVs. Proceedings of the 2008 IEEE International Joint Conference on Neural Networks, pp. 548-554, IEEE Press, 2008
31. X. Yao. Unpacking and understanding evolutionary algorithms. Advances in Computational Intelligence, LNCS 7311, pp. 60-76, Springer-Verlag, 2012.
32. M. Mavrovouniotis, S. Yang. A memetic ant colony optimization for the dynamic travelling salesman problem, Soft Computing - A Fusion of Foundations, Methodologies and Applications”, 15(7), pp. 1405-1425, Springer-Verlag, 2011.
33. Кажаров А.А., "Модификация муравьиного алгоритма и его применение к задаче коммивояжера", Перспективные информационные технологии и интеллектуальные системы, 2007.
34. Karypis G., Aggarwal R., Kumar V., and Shekhar S., "Multilevel Hypergraph Partitioning: Applications in VLSI Domain", IEEE Trans. VLSI SySt., Vol. 7, No. 1, March 1999. pp. 69-79.
35. Кажаров А.А. Построение минимального дерева Штейнера на основе муравьиных алгоритмов // Труды молодежной конференции "Интеллектуальные системы-2009". Москва. 2009.
36. Karypis G and Kumar V, "Multilevel k-way hypergraph partitioning.," Department of Computer Science, University of Minnesota, Minnesota, Technical Report TR 98-036 1998.
37. Macedo, R., Alves, C., Valйrio de Carvalho, J.M.,Clautiaux, F., Hanafi, S. (2011). Solving the vehicle routing problem with time windows and multiple routes exactly using a pseudopolynomial model, European Journal of Operational Research 2014 536-545
38. Mingozzi, A., Roberti, R., and Toth, P. (2012): An Exact Algorithm for the multi-trip vehicle routing problem. INFORMS Journal on Computing, Articles in Advance, pp. 1-15
39. Olivera, A. and Viera, O. (2007).Adaptive Memory Programming for the Vehicle Routing Problem with Multiple Trips. Computers and Operations Research, 34, 28-47
40. Moscato, P. (1989). On Evolution, Search, Optimization, Genetic Algorithms and Martial Arts: Towards Memetic Algorithms". Caltech Concurrent Computation Program (report 826).
41. Prins C. (2002). Efficient Heuristics for the Heterogeneous Fleet Multi trip VRP with Application to a Large-Scale Real Case. Journal of Mathematical Modeling and Algorithms 1: 135-150.
42. Petch, R.J. and Salhi, S. (2004). A Multi-phase Constructive Heuristic for the Vehicle Routing Problems with Multiple Trips. Discrete Applied Mathematics, 69-92
43. Salhi, S. and Petch, R.J. (2007). A GA Based Heurisric for the Vehicle Routing Problem with Multiple Trips, Journal of Mathematical Modeling and Algorithms, 591-613
Размещено на Allbest.ru
...Подобные документы
Цель маршрутизации - доставка пакетов по назначению с максимизацией эффективности. Построение алгоритмов поиска кратчайшего пути маршрутизации, расчёт пути с минимальным количеством переходов. Характеристики протокола RIP и построение маршрутных таблиц.
курсовая работа [74,1 K], добавлен 26.08.2010Использование понятий из теории графов при разработке сетей и алгоритмов маршрутизации. Построение матрицы смежности и взвешенного ориентировочного графа. Результаты работы алгоритмов Дейкстры и Беллмана-Форда. Протоколы обмена маршрутной информацией.
курсовая работа [334,1 K], добавлен 20.01.2013Анализ проблемы обеспечения информационной безопасности при работе в сетях; обоснование необходимости разработки алгоритмов безопасной маршрутизации пакетов сообщений в глобальной информационной сети. Алгоритмизация задач безопасной маршрутизации пакетов.
дипломная работа [1,0 M], добавлен 21.12.2012Понятие и классификация алгоритмов маршрутизации. Основное определение теории графов. Анализ и разработка алгоритмов Дейкстры и Флойда на языке программирования C# для определения наилучшего пути пакетов, передаваемых через сеть. Их сравнительный анализ.
курсовая работа [1,2 M], добавлен 16.05.2015"Рой частиц" как наиболее простой метод эволюционного программирования, основанный на идеи о возможности решения задач оптимизации с помощью моделирования поведения групп животных. Схема работы алгоритма, составление кода программы и блок-схемы.
курсовая работа [38,5 K], добавлен 18.05.2013Обзор алгоритмов методов решения задач линейного программирования. Разработка алгоритма табличного симплекс-метода. Составление плана производства, при котором будет достигнута максимальная прибыль при продажах. Построение математической модели задачи.
курсовая работа [266,4 K], добавлен 21.11.2013Описание широкополосных сетей интегрального обслуживания, классификация алгоритмов маршрутизации. Реализация логического способа формирования плана распределения информации в схеме маршрутизатора. Математическая модель и метод анализа маршрутизации.
дипломная работа [1,1 M], добавлен 31.10.2010Краткий обзор решения транспортных задач. Экономическая интерпретация поставленной задачи. Разработка и описание алгоритма решения задачи. Построение математической модели. Решение задачи вручную и с помощью ЭВМ. Анализ модели на чувствительность.
курсовая работа [844,3 K], добавлен 16.06.2011Изучение особенностей создания алгоритмов вычислительных задач. Визуальное программирование стандартных компонентов среды программирования Delphi. Технология создания компонента Delphi для решения производственной задачи. Выполнение блок-схемы алгоритма.
курсовая работа [638,0 K], добавлен 30.01.2015Межсетевой уровень модели TCP/IP. Понятие IP-адреса. Адрес узла для решения задачи маршрутизации. Схема классовой адресации, специальные адреса. Определение IP-адреса и маски подсети для каждого узла. Таблица маршрутизации IP, алгоритм выбора маршрута.
презентация [63,2 K], добавлен 25.10.2013Исследование асимптотической временной сложности решения шахматной задачи; разработка наиболее эффективных алгоритмов и структуры данных; аналитическая и экспериментальная оценка методов сокращения перебора в комбинаторных задачах; программная реализация.
курсовая работа [36,6 K], добавлен 25.06.2013Описание систем управления процессами маршрутизации пакетов, передаваемых через компьютерную сеть. Изучение методов теории выбора кратчайших путей. Разработка программы маршрутизации данных и определение кратчайших путей их маршрутов методом Дейкстры.
курсовая работа [495,7 K], добавлен 24.06.2013Основные положения, связанные с маршрутизацией компьютерных сетей и её видами, протоколами маршрутизации и их разновидностями, алгоритмами маршрутизации, их классификацией, типами и свойствами. Разработка программы и моделирование компьютерной сети.
курсовая работа [1,8 M], добавлен 04.11.2012Переход от словесной неформальной постановки к математической формулировке данной задачи. Оценка различных вариантов с целью выбора наиболее эффективных структур данных и алгоритмов обработки. Реализация алгоритмов на одном из языков программирования.
курсовая работа [35,0 K], добавлен 25.06.2013Анализ математических алгоритмов решения задачи, постановка задач по критериям. Выбор программной платформы для создания системы и описание 1С:Предприятие 8. Функционал создания индивидуальных учебных планов, формирования и реорганизации учебных групп.
дипломная работа [2,1 M], добавлен 13.10.2016Описание формальной модели алгоритма на основе рекурсивных функций. Разработка аналитической и программной модели алгоритма для распознающей машины Тьюринга. Разработка аналитической модели алгоритма с использованием нормальных алгоритмов Маркова.
курсовая работа [1,5 M], добавлен 07.07.2013Концепция мультисервисных сетей, их архитектура и основные предъявляемые требования. Главные понятия и виды маршрутизации, методы ее реализации, классификация алгоритмов. Анализ и оценка функционирования мультисервисной сети с адаптивной маршрутизацией.
курсовая работа [46,5 K], добавлен 22.07.2012Создание схем алгоритмов и составление программы на языке Pascal для вычисления значений заданных функций. Сущность и порядок нахождения значения определенного интеграла. Анализ работы подпрограмм. Разработка тестов для проверки правильности алгоритмов.
контрольная работа [831,0 K], добавлен 24.11.2013Метод решения математической модели на примере решения задач аналитической геометрии. Описание согласно заданному варианту методов решения задачи. Разработка математической модели на основе описанных методов. Параметры окружности минимального радиуса.
лабораторная работа [310,6 K], добавлен 13.02.2009Исследование элементов эллиптических кривых, необходимых для реализации криптографических протоколов. Изучение алгоритмов арифметики точек эллиптической кривой и способов генерации кривых для криптографических алгоритмов. Описание алгоритмов шифрования.
курсовая работа [371,2 K], добавлен 07.08.2012
