Лекция 5. Алгоритмы роевой оптимизации

Материалы к лекции:

• презентация: ссылка
• тест: ссылка
• форма для ответов: ссылка
• задание NetLogo: метод роя частиц, обязательные упражнения 3 и 6: ссылка

Ресурсы:

Алгоритм бактериального поиска

• Chemotaxis: Bacteria attracted by a sugar crystal (YouTube)
• Chemotaxis: Molecular Events (YouTube)
• K. M. Passino, Biomimicry of bacterial foraging for distributed optimization and control, IEEE Control Systems Magazine, 22, 2002, p. 52–67
• B. Bassler, How bacteria talk to each other: regulation of gene expression by quorum sensing, Current Opinion in Microbiology, Vol. 2, Issue 6, 1999, p. 582–587
• Seth L. Shipman et al. CRISPR-Cas encoding of a digital movie into the genomes of a population of living bacteria. Nature, July 12, 2017

Пчелиный алгоритм

• The Honeybee Waggle Dance – Is it a Language?
• Bee Dance (YouTube)
• The Power of Bee Democracy (YouTube)
• D. Pham, À. Ghanbarzadeh et al., The Bees Algorithm – A Novel Tool for Complex Optimisation Problems, Intelligent Production Machines and Systems 2nd I*PROMS Virtual International Conference 3–14 July 2006, pp. 454-459
• Karaboga, Dervis (2010). Artificial bee colony algorithm. Scholarpedia. 5 (3): 6915
• S. Camazine, J. Sneyd et al., A mathematical model of selforganized pattern formation on the combs of honeybee colonies, Journal of Theoretical Biology, Vol. 147, 4, 1990, p. 553–571

Алгоритмы роевой оптимизации

• List of metaphor-based metaheuristics (Wikipedia)
• Yang, X. S. (2008). Nature-Inspired Metaheuristic Algorithms (PDF)

Лекция 4. Муравьиные алгоритмы

Материалы к лекции:

• презентация: ссылка
• тест: ссылка
• форма для ответов: ссылка
• задание NetLogo: модель Рейнолдса, обязательные упражнения 3 и 4: ссылка

Ресурсы:

Модели муравьиных колоний

• Халифман И. А., Муравьи, М.: Молодая гвардия, 1963
• S. Goss S., S. Aron, J. L. Deneubourg, J. M. Pasteels, Self-organized shortcuts in the Argentine ant, Naturwissenschaften, 1989, 76, p. 579–581
• M. Muller, R. Wehner, Path integration in desert ants, Cataglyphis fortis, Proc. Nati. Acad. Sci. USA, 1988, Vol. 85, p. 5287–5290
• C++ Ants Simulation 1, First approach (YouTube)
• Deborah Gordon: The emergent genius of ant colonies (YouTube)

Задача коммивояжера

• Travelling salesman problem (Wikipedia)
• Мудров В. И., Задача о коммивояжёре. М.: Знание, 1969
• Traveling Salesman Problem Visualization (YouTube)

Муравьиные алгоритмы

• Ant colony optimization algorithms (Wikipedia)
• M. Dorigo, V. Maniezzo, A. Colorni, Ant System: Optimization by a Colony of Cooperating Agents, IEEE Transactions on Systems, Man, and Cybernetics, 1996, 26 (1), p. 29–41
• C. Blum, 2005 Ant colony optimization: Introduction and recent trends. Physics of Life Reviews, 2: 353-373 (PDF)
• T. Stutzle, H.H. Hoos, MAX MIN Ant System, Future Generation Computer Systems, 2000, Vol. 16, p. 889–914.
• Ant Colony Optimization (YouTube)

Лекция 3. Метод роя частиц

Материалы к лекции:

• презентация: ссылка
• тест: ссылка
• форма для ответов: ссылка
• задание NetLogo: метод имитации отжига, обязательные упражнения 3 и 4: ссылка

Ресурсы:

Роевой интеллект

• Swarm intelligence — Wikipedia
• What is Swarm AI? (YouTube)
• Taming the swarm - Collective Artificial Intelligence | Radhika Nagpal (YouTube)

Модель Рейнолдса

• Reynolds, Craig (1987). Flocks, herds and schools: A distributed behavioral model. Proceedings of the 14th annual conference on Computer graphics and interactive techniques SIGGRAPH'87, pp. 25–34
• Boids. Background and Update, by Craig Reynolds
• Stanley and Stella in Breaking the Ice (1987) (YouTube)
• Coding Challenge #124: Flocking Simulation (YouTube)
• T. Vicsek, et al., Novel Type of Phase Transition in a System of Self-Driven Particles, Phys. Rev. Lett. 1995, 75, 6, p. 1226–1229 (PDF)

Метод роя частиц

• J. Kennedy, R. Eberhart, Particle Swarm Optimization, Proc. of IEEE International Conference on Neural Networks, 1995, p. 1942–1948
• J. Dieterich, B. Hartke, Empirical Review of Standard Benchmark Functions Using Evolutionary Global Optimization, Applied Mathematics, Vol. 3 No. 10A, 2012, p. 1552–1564 (PDF)
• Kennedy, J., Eberhart, R. C. (1997). A discrete binary version of the particle swarm algorithm, Conference on Systems, Man, and Cybernetics, Piscataway, NJ: IEEE Service Center, pp. 4104-4109 (PDF)
• Learn Particle Swarm Optimization (YouTube)

Алгоритм CSO

• R. Cheng, Y. Jin, A Competitive Swarm Optimizer for Large Scale Optimization, in IEEE Transactions on Cybernetics, Vol. 45, No. 2, Feb. 2015, p. 191–204

Лекция 2. Методы Монте-Карло

Лекция 2. Методы Монте-Карло Материалы к лекции:

• презентация: ссылка
• тест: ссылка
• форма для ответов: ссылка
• задание NetLogo: задача Бюффона, обязательные упражнения 7 и 8: ссылка
• задание MPI-1: ссылка
• последовательный код: ссылка
• Учебное пособие Ершов Н.М., Попова Н.Н. Естественные модели параллельных вычислений с методическими рекомендациями по параллельной реализации рассматриваемых моделей и алгоритмов

Ресурсы:

Метод Монте-Карло

• Monte Carlo method — Wikipedia
• Metropolis, N. and Ulam, S. (1949) The Monte Carlo Method. Journal of the American Statistical Association, 44, 335-341 (PDF)
• Metropolis, N. (1987). The beginning of the Monte Carlo method. Los Alamos Science (1987 Special Issue dedicated to Stanislaw Ulam): 125–130 (PDF)
• Соболь И. М. Метод Монте-Карло. М., "Наука", 1968, 64 с. ("Популярные лекции по математике", вып. 46)
• Monte Carlo Methods: Data Science Basics (YouTube)

Задача Бюффона

• Buffon's needle problem — Wikipedia
• Pi and Buffon's Matches - Numberphile (YouTube)
• E. B. Mallon, N. R. Franks, Ants Estimate Area Using Buffon’s Needle, Proceedings of the Royal Society B: Biological Sciences 267.1445, 2000, p. 765–770. (PDF)
• B. J. Arnow, On Laplace’s Extension of the Buffon Needle Problem, The College Mathematics Journal, Vol. 25, No. 1, Jan. 1994, p. 40–43.
• J. F. Ramaley, Buffon’s Noodle Problem // The American Mathematical Monthly, Vol. 76, No. 8, p. 916–918.

Модели случайных блужданий

• R. Brown, A brief account of microscopical observations made in the months of June, July and August, 1827, on the particles contained in the pollen of plants; and on the general existence of active molecules in organic and inorganic bodies, Philosophical Magazine, 1828, 4: p. 161–173. (PDF)
• Эйнштейн, А. О движении взвешенных в покоящейся жидкости частиц, требуемом молекулярно-кинетической теорией теплоты, Ann. Phys., 1905, 322, p. 549–560. (PDF)
• Random walk — Wikipedia
• What is a Random Walk? | Infinite Series (YouTube)
• S. Song, J. Song, A Note on the History of the Gambler’s Ruin Problem, Communications for Statistical Applications and Methods, 2013, Vol. 20, No. 2, p. 157–168. (PDF)

Метод имитации отжига

• N. Metropolis, A. Rosenbluth, M. Rosenbluth, A. Teller, E. Teller, Equation of State Calculations by Fast Computing Machines, The Journal of Chemical Physics, 1953, 21 (6), p. 1087–1092.
• Мейлихов Е. З., Трагическая и счастливая жизнь Эрнста Изинга, Природа, №7, 2006
• S. Kirkpatrick, C. Gelatt, M. Vecchi, Optimization by simulated annealing, Science, 1983, May 13, 220 (4598), p. 671–680.
• Simulated Annealing Explained By Solving Sudoku - Machine Learning (YouTube)

Лекция 1. Введение

Материалы к лекции:

• презентация: ссылка
• тест: ссылка
• форма для ответов: ссылка
• задание NetLogo: модель из презентации

Среда NetLogo (форму можно не заполнять): ссылка

Ресурсы:

Естественные вычисления

• Natural computing — Wikipedia
• Lila Kari, Grzegorz Rozenberg (October 2008). The Many Facets of Natural Computing. Communications of the ACM. 51 (10): 72–83.
• Leandro Nunes de Castro (March 2007). Fundamentals of Natural Computing: An Overview. Physics of Life Reviews. 4 (1): 1–36

Среда моделирования NetLogo

• NetLogo Home Page
• Справочник по командам языка NetLogo
• Wilensky U., Rand W., An introduction to agent-based modeling: Modeling natural, social and engineered complex systems with NetLogo, Cambridge: MIT Press, 2015
• Vidal J., Fundamentals of Multiagent Systems Using NetLogo, 2010 (PDF)"
• Introduction to Agent Based Modeling course by Prof. Bill Rand (YouTube)

Язык программирования Logo

• Logo (programming language) — Wikipedia
• Abelson H., Goodman N., Rudolph L., Logo Manual, Artificial Intelligence Lab, Massachusetts Institute of Technology, December 1974 (PDF)

Среда моделирования StarLogo

• Catherine Griffiths, StarLogo, a programming language to support decentralized thinking by simulating complex systems
• Resnick M., Turtles, Termites, and Traffic Jams: Explorations in Massively Parallel Microworlds, 1994, MIT Press