Марко дориго алгоритмы муравья

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

Муравья нельзя назвать сообразительным. Отдельный муравей не в состоянии принять ни малейшего решения. Дело в том, что он устроен крайне примитивно: все его действия сводятся к элементарным реакциям на окружающую обстановку и своих собратьев. Муравей не способен анализировать, делать выводы и искать решения.

Эти факты, однако, никак не согласуются с успешностью муравьев как вида. Они существуют на планете более 100 миллионов лет, строят огромные жилища, обеспечивают их всем необходимым и даже ведут настоящие войны. В сравнении с полной беспомощностью отдельных особей, достижения муравьев кажутся немыслимыми.

Добиться таких успехов муравьи способны благодаря своей социальности. Они живут только в коллективах – колониях. Все муравьи колонии формируют так называемый роевой интеллект. Особи, составляющие колонию, не должны быть умными: они должны лишь взаимодействовать по определенным – крайне простым – правилам, и тогда колония целиком будет эффективна.

В колонии нет доминирующих особей, нет начальников и подчиненных, нет лидеров, которые раздают указания и координируют действия. Колония является полностью самоорганизующейся. Каждый из муравьев обладает информацией только о локальной обстановке, не один из них не имеет представления обо всей ситуации в целом – только о том, что узнал сам или от своих сородичей, явно или неявно. На неявных взаимодействиях муравьев, называемых стигмергией, основаны механизмы поиска кратчайшего пути от муравейника до источника пищи.

Каждый раз проходя от муравейника до пищи и обратно, муравьи оставляют за собой дорожку феромонов. Другие муравьи, почувствовав такие следы на земле, будут инстинктивно устремляться к нему. Поскольку эти муравьи тоже оставляют за собой дорожки феромонов, то чем больше муравьев проходит по определенному пути, тем более привлекательным он становится для их сородичей. При этом, чем короче путь до источника пищи, тем меньше времени требуется муравьям на него – а следовательно, тем быстрее оставленные на нем следы становятся заметными.

В 1992 году в своей диссертации Марко Дориго (Marco Dorigo) предложил заимствовать описанный природный механизм для решения задач оптимизации [1]. Имитируя поведение колонии муравьев в природе, муравьиные алгоритмы используют многоагентные системы, агенты которых функционируют по крайне простым правилам. Они крайне эффективны при решении сложных комбинаторных задач – таких, например, как задача коммивояжера, первая из решенных с использованием данного типа алгоритмов.

Классический муравьиный алгоритм для решения задачи коммивояжера

Как было сказано выше, муравьиный алгоритм моделирует многоагентную систему. Ее агентов в дальнейшем будем называть муравьями. Как и настоящие муравьи, они довольно просто устроены: для выполнения своих обязанностей они требуют небольшое количество памяти, а на каждом шаге работы выполняют несложные вычисления.

Каждый муравей хранит в памяти список пройденных им узлов. Этот список называют списком запретов (tabu list) или просто памятью муравья. Выбирая узел для следующего шага, муравей «помнит» об уже пройденных узлах и не рассматривает их в качестве возможных для перехода. На каждом шаге список запретов пополняется новым узлом, а перед новой итерацией алгоритма – то есть перед тем, как муравей вновь проходит путь – он опустошается.

Кроме списка запретов, при выборе узла для перехода муравей руководствуется «привлекательностью» ребер, которые он может пройти. Она зависит, во-первых, от расстояния между узлами (то есть от веса ребра), а во-вторых, от следов феромонов, оставленных на ребре прошедшими по нему ранее муравьями. Естественно, что в отличие от весов ребер, которые являются константными, следы феромонов обновляются на каждой итерации алгоритма: как и в природе, со временем следы испаряются, а проходящие муравьи, напротив, усиливают их.

Пусть муравей находится в узле , а узел – это один из узлов, доступных для перехода: . Обозначим вес ребра, соединяющего узлы и , как , а интенсивность феромона на нем – как . Тогда вероятность перехода муравья из в будет равна:

где и – это регулируемые параметры, определяющие важность составляющих (веса ребра и уровня феромонов) при выборе пути. Очевидно, что при алгоритм превращается в классический жадный алгоритм, а при он быстро сойдется к некоторому субоптимальному решению. Выбор правильного соотношения параметров является предметом исследований, и в общем случае производится на основании опыта.

После того, как муравей успешно проходит маршрут, он оставляет на всех пройденных ребрах след, обратно пропорциональный длине пройденного пути:

,

где – длина пути, а – регулируемый параметр. Кроме этого, следы феромона испаряются, то есть интенсивность феромона на всех ребрах уменьшается на каждой итерации алгоритма. Таким образом, в конце каждой итерации необходимо обновить значения интенсивностей:

Обзор модификаций классического алгоритма

Elitist Ant System

Одним из таких усовершенствований является введение в алгоритм так называемых «элитных муравьев». Опыт показывает, что проходя ребра, входящие в короткие пути, муравьи с большей вероятностью будут находить еще более короткие пути. Таким образом, эффективной стратегией является искусственное увеличение уровня феромонов на самых удачных маршрутах. Для этого на каждой итерации алгоритма каждый из элитных муравьев проходит путь, являющийся самым коротким из найденных на данный момент.

Эксперименты показывают, что, до определенного уровня, увеличение числа элитных муравьев является достаточно эффективным, позволяя значительно сократить число итераций алгоритма. Однако, если число элитных муравьев слишком велико, то алгоритм достаточно быстро находит субоптимальные решение и застревает в нем [3]. Как и другие изменяемые параметры, оптимальное число элитных муравьев следует определять опытным путем.

Лука Гамбарделла (Luca M. Gambardella) и Марко Дориго опубликовали в 1995 году работу, в которой они представили муравьиный алгоритм, получивший свое название по аналогии с методом машинного обучения Q-learning [4]. В основе алгоритма лежит идея о том, что муравьиную систему можно интерпретировать как систему обучения с подкреплением. Ant-Q усиливает эту аналогию, заимствуя многие идеи из Q-обучения.

Алгоритм хранит Q-таблицу, сопоставляющую каждому из ребер величину, определяющую «полезность» перехода по этому ребру. Эта таблица изменяется в процессе работы алгоритма – то есть обучения системы. Значение полезности перехода по ребру вычисляется исходя из значений полезностей перехода по следующим ребрам в результате предварительного определения возможных следующих состояний. После каждой итерации полезности обновляются исходя из длин путей, в состав которых были включены соответствующие ребра.

Ant Colony System

В 1997 году те же исследователи опубликовали работу, посвященную еще одному разработанному ими муравьиному алгоритму [5]. Для повышения эффективности по сравнению с классическим алгоритмом, ими были введены три основных изменения.

Во-первых, уровень феромонов на ребрах обновляется не только в конце очередной итерации, но и при каждом переходе муравьев из узла в узел. Во-вторых, в конце итерации уровень феромонов повышается только на кратчайшем из найденных путей. В-третьих, алгоритм использует измененное правило перехода: либо, с определенной долей вероятности, муравей безусловно выбирает лучшее – в соответствие с длиной и уровнем феромонов – ребро, либо производит выбор так же, как и в классическом алгоритме.

Max-min Ant System

В том же году Томас Штютцле (Tomas Stützle) и Хольгер Хоос (Holger Hoos) предложили муравьиный алгоритм, в котором повышение концентрации феромонов происходит только на лучших путях из пройденных муравьями [6]. Такое большое внимание к локальным оптимумам компенсируется вводом ограничений на максимальную и минимальную концентрацию феромонов на ребрах, которые крайне эффективно защищают алгоритм от преждевременной сходимости к субоптимальным решениям.

На этапе инициализации, концентрация феромонов на всех ребрах устанавливается равной максимальной. После каждой итерации алгоритма только один муравей оставляет за собой след – либо наиболее успешный на данной итерации, либо, аналогично алгоритму с элитизмом, элитный. Этим достигается, с одной стороны, более тщательное исследование области поиска, с другой – его ускорение.

ASrank

Бернд Бульнхаймер (Bernd Bullnheimer), Рихард Хартл (Richard F. Hartl) и Кристине Штраусс (Christine Strauß) разработали модификацию классического муравьиного алгоритма, в котором в конце каждой итерации муравьи ранжируются в соответствие с длинами пройденных ими путей [7]. Количество феромонов, оставляемого муравьем на ребрах, таким образом, назначается пропорционально его позиции. Кроме того, для более тщательного исследования окрестностей уже найденных удачных решений, алгоритм использует элитных муравьев.

Заключение

Задача коммивояжера является, возможно, наиболее исследуемой задачей комбинаторной оптимизации. Неудивительно, что именно она была выбрана первой для решения с использованием подхода, заимствующего механизмы поведения муравьиной колонии. Позже этот подход нашел применение в решении многих других комбинаторных проблем, в числе которых задачи о назначениях, задача раскраски графа, задачи маршрутизации, задачи из областей data mining и распознавания образов и другие.

Эффективность муравьиных алгоритмов сравнима с эффективностью общих метаэвристических методами, а в ряде случаев – и с проблемно-ориентированными методами. Наилучшие результаты муравьиные алгоритмы показывают для задач с большими размерностями областей поиска. Муравьиные алгоритмы хорошо подходят для применения вместе с процедурами локального поиска, позволяя быстро находить начальные точки для них.

Наиболее перспективными направлениями дальнейших исследований в данном направлении следует считать анализ способа выбора настраиваемых параметров алгоритмов. В последние годы предлагаются различные способы адаптации параметров алгоритмов «на лету» [8]. Поскольку от выбора параметров сильно зависит поведение муравьиных алгоритмов, именно к этой проблеме обращено наибольшее внимание исследователей на данный момент.

Литература

[1] M. Dorigo, “Ottimizzazione, apprendimento automatico, ed algoritmi basati su metafora naturale (Optimization, Learning, and Natural Algorithms)”, диссертация на соискание ученой степени “Doctorate in Systems and Information Electronic Engineering”, Politecnico di Milano, 1992 г.

[2] A. Colorni, M. Dorigo, V. Maniezzo, “Distributed Optimization by Ant Colonies” // Proceedings of the First European Conference on Artificial Life, Paris, France, Elsevier Publishing, стр. 134-142, 1991 г.

[3] M. Dorigo, V. Maniezzo, A. Colorni, “The Ant System: Optimization by a colony of cooperating agents” // IEEE Transactions on Systems, Man, and Cybernetics-Part B, 26, 1, стр. 29-41, 1996 г.

[4] L. M. Gambardella, M. Dorigo, “Ant-Q: A Reinforcement Learning Approach to the Traveling Salesman Problem” // Twelfth International Conference on Machine Learning, Morgan Kaufmann, стр. 252-260, 1995 г.

[5] M. Dorigo, L. M. Gambardella, Ant Colony System: A Cooperative Learning Approach to the Traveling Salesman Problem // IEEE Transactions on Evolutionary Computation Vol. 1, 1, стр. 53-66, 1997 г.

[6] T. Stützle, H. Hoos, “MAX-MIN Ant System and local search for the traveling salesman problem” // IEEE International Conference on Evolutionary Computation, стр. 309-314, 1997 г.

[7] Bernd Bullnheimer, Richard F. Hartl, Christine Strauß, “A new rank based version of the Ant System. A computational study” // Adaptive Information Systems and Modelling in Economics and Management Science, 1, 1997 г.

[8] T. Stützle, M. López-Ibáñez, P. Pellegrini, M. Maur, M. de Oca, M. Birattari, Michael Maur, M. Dorigo, “Parameter Adaptation in Ant Colony Optimization” // Technical Report, IRIDIA, Université Libre de Bruxelles, 2010 г.

Источник

Как муравьи решают проблемы коммивояжёров

Авторизуйтесь

Как муравьи решают проблемы коммивояжёров

кандидат технических наук, Tech Lead Bercut

В математике и программировании порой используются необычные названия явлений, объектов и алгоритмов. Но почти всегда такие названия позволяют быстро понять суть описываемых сущностей. Возьмём, к примеру, широко известную задачу о коммивояжёре — найти кратчайший путь между заданными точками. И действительно, сразу представляется себе коммивояжёр, которому нужно обойти все дома в небольшом городке, но при этом затратить минимум усилий и времени. Эта задача имеет очень широкое применение, ведь оптимизация маршрутов и различных процессов — это одна из самых насущных проблем в современном, быстро меняющемся мире. Для решения этой задачи используются разные алгоритмы, один из них называется «муравьиным». С этим названием всё немного сложнее. Если вы не в курсе, о чём идёт речь, то вам будет сложно понять, как же муравьи помогают решить эту задачу. Об этом я и хочу рассказать вам в этой статье. Но для того, чтобы разобраться с этим алгоритмом, нам для начала нужно внимательней присмотреться к поведению муравьёв в их необычном организованном мире.

Необычный мир у нас под ногами

Давайте попробуем представить себе обычный муравейник в лесу — это небольшая горка, в которой, на первый взгляд, хаотично копошатся муравьи. Несколько напоминает станцию метро в час пик. На подступах к муравейнику их становится уже не так много, перемещения отдельных муравьёв выглядят более осмысленными. Это больше похоже на оживлённый проспект где-нибудь в центре города. Если же проследить за отдельными муравьями дальше, то часто можно увидеть вереницу муравьёв, которые организованно ползут друг за другом: в одну сторону пустыми, в другую — с добычей. Чем-то похоже на шоссе с потоком грузовиков. Такая цепочка муравьёв — знакомая всем нам картина, её можно увидеть во многих научно-популярных программах и, конечно, в мультфильмах. Например, в классическом «Томе и Джерри», где такая процессия здорово досаждала отдыхающему в гамаке Тому.

Еще со школы мы знаем, что муравьи — высокоорганизованные существа. Они выполняют множество различных задач: разводят тлю как домашних животных, организованно транспортируют запасы пищи из найденных источников в специальные хранилища внутри муравейника, строят и ремонтируют этот самый муравейник, защищают его от врагов. Но как же так получается, что обычные насекомые ведут такую осмысленную коллективную деятельность? Ведь по некоторым данным, в мозге у одного муравья всего около 500 тысяч нейронов. Для сравнения, у человека их 86 миллиардов. Это значит, что сам муравей не в состоянии принять какое-то осмысленное решение. Максимум, на что он способен, это следовать простейшей программе. Единого мозгового центра у муравейника тоже нет — в нём не сидит некий суперумный ведущий муравей, который мудро управляет всеми остальными муравьями. Как же функционирует единая система «муравейник»? Наука пока не может дать однозначный ответ на все вопросы о муравьях, но исследования продолжаются, работы ведутся. О направлении этих исследований и некоторых гипотезах об устройстве муравьиного «управления», например, можно почитать в статье журнала «Наука и жизнь». Примечательно, что некоторые научные исследования муравьёв уже достигли стадии широкого практического применения в технологиях и программировании.

Следуй за этим муравьём

Давайте вернёмся к нашему примеру с цепочкой муравьёв. Как муравьи «понимают», что в определённом месте находится источник питания и нужно двигаться к нему по определённому маршруту? Учёные довольно давно выяснили, как это происходит. На основе исследования поведения муравьёв им удалось создать один из самых эффективных алгоритмов достаточно быстрого решения задачи. Этот алгоритм официально так и называется «муравьиным», по-английски — ant colony optimization, сокращённо ACO.

Проследим за одним так называемым муравьём-фуражиром, задачей которого в муравьиной семье является добыча пищи. В обычном режиме он бессистемно курсирует по местности в поисках чего-нибудь съедобного. В какой-то момент он находит источник пищи, например, сочный аппетитный фрукт. Сам муравей, естественно, этот фрукт дотащить до муравейника не может. Тогда он забирает кусочек добычи и тащит его в муравейник. При этом он помечает свой путь специальным феромоном. Дальше мы для простоты будем называть этот феромон просто «меткой». Важно то, что другие муравьи, почуяв запах такой метки, с большой охотой побегут по тому же пути. Для них это сигнал, что эта дорожка приведёт к чему-то вкусному и питательному.

25–26 ноября, Москва и онлайн, От 24 000 до 52 000 ₽

В книге Игоря Акимушкина «Проблемы этологии» (1985 год) описан такой интересный опыт:

Возьмите лист бумаги и положите его на пути муравья, возвращающегося домой с известием о богатой находке. Когда муравей проползет по листу, пометьте его путь лёгким штрихом карандаша и поверните бумагу под небольшим углом. Муравьи, вызванные из гнезда, добегут по трассе до края бумаги, упрутся в то место, где раньше трасса проходила с земли на лист, но — тут обрыв! Начнут суетиться у разрыва, искать трассу и, когда найдут её в стороне, снова побегут по прямой. Вы увидите, что путь муравьёв будет совпадать с отмеченной карандашом линией.

Немного про обратные связи

К сожалению, мы знаем, что всё вкусное имеет свойство быстро заканчиваться. Так что же произойдёт, когда муравьи по кусочкам перенесут этот сочный фрукт в муравейник? Мудрая природа предусмотрела и это. Дело в том, что метка постепенно испаряется. Пока муравьи носят добычу в муравейник, они постоянно подпитывают метку на своём пути — ведь каждый из них возвращается с добычей. Но в какой-то момент муравьи начнут возвращаться ни с чем — оставлять свою метку они уже не будут. С точки зрения математики, такое испарение метки обеспечивает отрицательную обратную связь всей системе.

Кстати, описанная организация процесса даёт муравьям ещё один замечательный «бонус» — поиск кратчайшего пути от фрукта к муравейнику. В принципе, муравей не обязан выбирать путь с меткой. Такой путь для него более привлекательный, но не единственный. Муравей может перемещаться хаотично, оставляя свою метку на любой траектории. Но за определённый период времени по кратчайшему пути пройдёт больше муравьёв, чем по всем остальным путям. А это значит, что на самом коротком пути количество метки будет больше, чем на всех остальных случайных траекториях. И это количество будет постоянно увеличиваться за счёт того, что другие муравьи с большей вероятностью будут выбирать этот путь. С математической точки зрения — это положительная обратная связь.

От муравьёв к системе

Что же в итоге мы имеем? Давайте перечислим все особенности получившейся системы:

• система является самоорганизующейся, без единого центра управления;
• система является распределённой — каждый муравей использует только доступную ему локальную информацию;
• система является устойчивой — если пара муравьёв заблудится по дороге, то это никак не повлияет на решение общей задачи;
• система успешно решает задачу самооптимизации — с помощью отрицательной и положительной обратной связи муравьи находят кратчайший маршрут.

По сути муравьи представляют собой реализацию живого алгоритма для быстрого отыскания кратчайшего пути между двумя точками. Почему бы не формализовать этот алгоритм и не использовать его для нахождения оптимальной траектории между любым количеством точек? Впервые эту задачу решил французский учёный Марко Дориго. Именно он в своей диссертации в 1992 году предложил первую версию «муравьиного алгоритма».

Алгоритмизируем муравьёв

Рассмотрим один из вариантов реализации муравьиного алгоритма. Итак, у нас есть заданное количество точек. Задача заключается в том, чтобы за несколько итераций найти кратчайший маршрут обхода всех точек. Количество муравьёв совпадает с количеством точек. Перед каждой итерацией размещаем муравьёв по одному в каждой точке.

На каждой итерации каждый муравей обходит все точки по определённой траектории. При составлении своей траектории каждый муравей несколько раз «выбирает» точку, в которую он переместится. На выбор точки для перемещения влияют следующие параметры:

1. Список точек, заходить в которые нельзя. Муравей за итерацию может посетить каждую точку только один раз.
2. Желание посетить точку — муравей с большей охотой посещает ближайшие к нему точки. Обозначим этот параметр как N. Он будет равен 1/D, где D — расстояние до рассматриваемой точки от текущего положения муравья.
3. Количество меток на пути между точкой, в которой находится муравей, и рассматриваемой точкой. Обозначим этот параметр как T.

Чтобы решить, в какую точку ему переместиться, муравей сначала составляет список точек, в которых он ещё не был. Для каждой из точек полученного списка муравей выполняет следующие действия:

• вычисляет параметры N и T;
• получает показатель H = T α ·N β , где α и β — это весовые коэффициенты, настройки алгоритма;
• вычисляет вероятность перемещения в точку — P = H / (сумма H всех точек).

После этого муравей с учётом вероятностей P выбирает точку, в которую ему нужно переместиться. Представим себе рулетку, в которой каждой точке соответствует сектор с площадью, пропорциональной вероятности P. С помощью такой гипотетической рулетки муравей и делает свой выбор.

После перемещения муравья между точками нужно увеличить количество меток на этом отрезке на величину, равную Q / L, где L — расстояние между точками, а Q — настраиваемый параметр всего алгоритма в целом (он выбирается одного порядка со средним расстоянием между точками).

Таким образом, в рамках одной итерации каждый муравей по определённой траектории обходит все заданные точки. В конце каждой итерации нам нужно обеспечить испарение метки на каждом из отрезков между точками. Для этого нужно умножить её количество на постоянную величину E (evaporation), которая больше 0, но меньше 1.

Ну и конечно, в конце каждой итерации нам нужно выбрать кратчайший маршрут. Если он лучше, чем самый короткий маршрут за все предыдущие итерации, то выбираем его как текущее решение задачи. И так — итерация за итерацией, пока кратчайший маршрут на протяжении нескольких итераций не перестанет изменяться. Тогда с достаточной степенью уверенности мы сможем сказать, что решили поставленную задачу.

Экспериментируем с алгоритмом

Здесь приведено упрощённое изложение алгоритма без сложных формул, но если вас интересуют подробности, то вы можете найти их в Сети. Начать можно, например, отсюда. Также можно найти много готовых программ с иллюстрацией работы алгоритма. Мне больше всего понравилась программа, которая так и называется — Ant Colony Algorithm. В этой программе можно управлять основными параметрами алгоритма, просматривать результаты каждой итерации, задавать тестовые примеры с любым количеством точек. Кстати, как вы думаете, каким образом можно протестировать работу этого алгоритма? Как понять, что наши муравьи нашли действительно кратчайший маршрут. Для этого есть отличный тестовый пример: точки, расположенные по кругу. Для них кратчайший путь будет всегда один — окружность. В указанной программе такое расположение можно получить, выбрав режим «Automatic placement». А ещё эта программа позволяет попробовать работу различных модификаций алгоритма. При желании в этом можно как следует разобраться, скачав исходники программы на C.

«NP-простые» муравьи

Чем же так хорош алгоритм, который мы только что изучили? Дело в том, что задача коммивояжёра относится к числу так называемых NP-сложных. Это значит, что её можно решать простым перебором только на очень маленьком числе точек. Даже незначительное увеличение числа точек даёт невообразимый рост количества вычислений (а именно n!, где n — количество точек). Поэтому для нескольких десятков точек задачу простым перебором уже не решить. Тут-то и помогают методы, вроде муравьиного алгоритма. Ведь они позволяют решить эту задачу всего за минуту, тогда как на простой перебор потребовались бы миллионы лет.

Кстати, с помощью муравьиного алгоритма можно оптимизировать не только расстояние. В качестве параметра оптимизации могут выступать цена, время и любые другие показатели. В статье Адама Харта «Эти умницы муравьи» в журнале «Наука в фокусе» (№5 [18], 2013) приводятся такие примеры использования муравьиного алгоритма: планирование маршрутов грузовиков в компании Air Liquide (США), проектирование оптимальной схемы разводки проводов в искусственных спутниках Земли компании Clyde Space (Шотландия), вычисление оптимальных маршрутов космических аппаратов с использованием гравитационных манёвров в модели, разработанной несколькими университетами в Великобритании.

В той же статье описана ещё одна задача, решение которой подсказали учёным муравьи. Это задача вычисления оптимального количества пакетов, необходимых для передачи информации. Дело в том, что муравьи-фуражиры следуют простому правилу: периодичность покидания гнезда зависит от периодичности, с которой другие муравьи возвращаются с провиантом. Этот алгоритм сейчас успешно используется в известном всем протоколе TCP/IP. Высокая частота подтверждений доставки пакетов говорит отправителю о широкой полосе пропускания и возможности увеличения частоты отправки новых пакетов.

Ещё одна сфера, в которой можно применять муравьиный алгоритм — это оптимизация различных внутренних процессов в высокотехнологичных компаниях. Как спланировать производство и разработку, тестирование и документирование, внедрение и поддержку сложных систем, чтобы одни отделы и сотрудники не были перегружены, а другие не простаивали без дела? В выборе оптимальной цепочки и сроков выполнения задач может помочь муравьиный алгоритм. У нас в компании Bercut достаточно хорошо отлажен процесс разработки, задачи последовательно проходят все этапы — от разработки требований до момента отгрузки готового решения заказчику. Но компания постоянно развивается, растёт количество систем и заказчиков, сокращается время разработки (time to market). Возможно, в дальнейшем для ещё большей оптимизации процессов нам понадобится использовать алгоритм, похожий на муравьиный.

Программная оптимизация производства и маршрутов грузоперевозок, выбор оптимальной траектории, планирование различных взаимосвязанных работ — всё это прикладные области, в которых можно успешно и эффективно применять муравьиный алгоритм. А всё началось с того, что кто-то внимательно и вдумчиво посмотрел на обычную цепочку муравьёв у себя под ногами. В мире математики и программирования очень многое начинается с простой наблюдательности и умения формализовывать и алгоритмически описывать окружающий мир.

Хинт для программистов: если зарегистрируетесь на соревнования Huawei Cup, то бесплатно получите доступ к онлайн-школе для участников. Можно прокачаться по разным навыкам и выиграть призы в самом соревновании.

Перейти к регистрации

Источник