Муравьи и Python: ищем самые короткие пути
Часто бывает, что для того, чтобы найти лучшее решение задачи методом полного перебора, необходимо проанализировать слишком много вариантов, следовательно, потратить время и вычислительные ресурсы. Алгоритмы оптимизации помогают найти решение задачи, приближенное к идеальному. Возможно, не самое лучшее из всех возможных, но точно одно из лучших.
4452 просмотров
Алгоритмов оптимизации существует очень много. В этой статье будет разобран один из самых известных алгоритмов, заимствованных у природы – муравьиный алгоритм (ACO – Ant Colony Optimization).
Идея муравьиного алгоритма возникла в результате наблюдения за поведением реальных муравьёв. Отправной точкой положили исследования аргентинских муравьёв в 1989-1990 годах. Затем, в начале 90-х годов, Марко Дориго начал исследования для применения этой информации в практике. Он первый смог применить их стратегию для задачи по нахождению кратчайших маршрутов в графе.
Этот алгоритм оптимизации основан на поведении муравьиной колонии, которое позволяет насекомым находить наиболее удачный маршрут.
МУРАВЬИ — ЧТО МЫ О НИХ НЕ ЗНАЕМ? Удивительная жизнь самых организованных насекомых на планете
Суть алгоритма довольно проста: изначально муравьи доставляют еду в муравейник беспорядочно каждый своей дорогой, охватывая тем самым самые различные маршруты. Во время движения муравьи оставляют пахучий след из феромонов на своём пути, тем самым обозначая маршруты.
Соответственно, чем дорога короче, тем большее количество раз за одинаковое время муравьи успеют по ней пройти и смогут оставить на ней больше феромонов. Феромоны имеют свойство испаряться с течением времени. Из-за этого на длинных маршрутах остаётся меньше феромонов, чем на коротких, даже если по ним будет передвигаться одинаковое количество муравьёв. Таким образом, муравьи будут чаще выбирать самую «пахучую тропинку» и забывать пути с меньшим количеством феромонов.
Этот механизм решения проблемы является примером отличной самоорганизации системы. Подобные механизмы, в которых даже самые простые индивиды могут сотрудничать и без контроля и планирования создавать сложные структуры, имеют научное название – стигмергия.
Пока (не выполнены условия выхода) выполняются следующие операции алгоритма:
1. Создание муравьёв.
В разных задачах начальное размещение муравьёв может быть разным. Это зависит от условий задачи. Ещё на этом шаге происходит первоначальное размещение небольшого количества феромона для того, чтобы на первом шаге вероятность перехода в соседнюю вершину была не нулевой.
2. Поиск решений.
Формула для вычисления вероятности перехода муравья из вершины i в j:
где τij(t) – количество феромона между вершинами i и j, ηij – расстояние между этими вершинами. α, β – константные параметры. Их необходимо подбирать опытным путём, их значение должно быть такое, чтобы алгоритм не был слишком жадным и не застревал в локальных минимумах.
Чем ближе к нулю параметр β, тем меньше муравьи в выборе пути будут руководствоваться расстоянием между вершинами и будут ориентироваться только на феромон. С увеличением β значение близости растёт. Параметр α действует так же, но для уровня феромона.
Верхняя часть формулы описывает желание муравья перейти из вершины i в вершину j. Оно пропорционально близости вершины и уровню феромона на пути к ней.
Таким образом, вероятность перехода из вершины i в вершину j равняется желанию перейти в неё, делённому на сумму желаний перейти из вершины i ко всем доступным вершинам, которые ещё не были посещены. Сумма всех вероятностей равна 1.
Разложив все вероятности на числовой прямой от 0 до 1, можно сгенерировать рандомное вещественное число в этом интервале. Результат покажет, в какую вершину перейдёт муравей.
3. Обновление феромона.
Формула для пересчёта уровня феромона на каждой итерации алгоритма:
где ρ – скорость испарения, t – номер итерации, Lk(t) – цена текущего решения для k-ого муравья, а Q – параметр, имеющий значение порядка цены оптимального решения, то есть Q/Lk(t) – феромон, откладываемый k-ым муравьём, использующим ребро (i, j).
Таким образом, количество феромона на ребре между i и j на новой итерации равно количеству феромона на старой итерации, умноженное на коэффициент испарения (феромон постоянно испаряется), и к полученному результату добавляется сумма всех новых порций феромона, который отложили все муравьи на этом участке. Добавка феромона, которую делает муравей, проходя по ребру, равна константе Q, делённой на длину маршрута L, пройденную муравьём k, при условии, что это ребро попало в маршрут муравья.
Сложность муравьиного алгоритма зависит от количества вершин, количества муравьёв и времени жизни колонии.
При помощи алгоритма эффективно решать задачу на нахождение оптимального маршрута. Эту задачу принято называть задачей коммивояжёра (TSP – Travelling Salesman Problem).
Есть разные варианты постановки этой задачи. В классической постановке коммивояжёр (странствующий торговец) должен объехать определённое количество городов по замкнутому маршруту, посетив каждый из них только один раз. При этом, чем длина маршрута будет меньше, тем лучше.
Например, торговцу нужно посетить 5 городов и вернуться в исходный. Находясь в городе отправления, у него для выбора доступно 4 города. Дальше он делает выбор из трёх городов и так далее. Значит, количество всех возможных вариантов равно 4*3*2*1 = 24, то есть (n-1)!, где n – количество городов.
В этой постановке задачи торговцу нужно объехать все города и вернуться в исходный, а направление движения не имеет значения. Это называется симметричной задачей коммивояжёра. Следовательно, половину вариантов можно не учитывать, так как, например, варианты ABCDEA и AEDCBA будут эквивалентны. Значит, количество маршрутов для 5 городов равно 24/2=12, а конечная формула количества вариантов для симметричной задачи будет выглядеть так: (n-1)!/2.
Сложность задачи методом полного перебора растёт факториально. Несложно по формуле вычислить количество вариантов для большего количества городов:
Как мы видим, количество возможных путей при увеличении количества городов очень быстро растёт, и простым перебором вариантов (методом грубой силы) задачу становится решить гораздо менее возможно.
Задача коммивояжёра – одна из трансвычислительных задач. Это значит, что уже на довольно небольшом количестве городов (66 и более) лучшее решение простым методом перебора вариантов не может быть найдено никакими самыми мощными компьютерами меньше чем за миллиарды лет. Поэтому, гораздо разумнее находить решение этой задачи при помощи алгоритмов оптимизации.
Рассмотрим реализацию алгоритма на языке Python.
Код написан в соответствие с описанием алгоритма и формулами выше. В алгоритме есть два важных фактора: феромон τ и видимость η. Феромон τ относится к оставшейся информации на каждом пути, по которому проходят муравьи. Видимость η обозначает обратное расстояние между узлами. Вероятность P состоит из произведения феромона τ и видимости η и их суммы.
При кратчайшем пути, высоком уровне феромона τ, а также высокой видимости η вероятность P становится выше. Следовательно, в строках 39-40 происходит подсчёт вероятности P. Затем, строка 41 выбирает последовательность кратчайших путей при помощи вероятности P. Наконец, строки 55-64 обновляют феромон τ с коэффициентом испарения ρ. Параметр Q – это сумма феромонов в постоянном значении. Вернувшись к строке 37, новая последовательность маршрутов определена для следующего вычисления.
class ACO_TSP: # класс алгоритма муравьиной колонии для решения задачи коммивояжёра def __init__(self, func, n_dim, size_pop=10, max_iter=20, distance_matrix=None, alpha=1, beta=2, rho=0.1): self.func = func self.n_dim = n_dim # количество городов self.size_pop = size_pop # количество муравьёв self.max_iter = max_iter # количество итераций self.alpha = alpha # коэффициент важности феромонов в выборе пути self.beta = beta # коэффициент значимости расстояния self.rho = rho # скорость испарения феромонов self.prob_matrix_distance = 1 / (distance_matrix + 1e-10 * np.eye(n_dim, n_dim)) # Матрица феромонов, обновляющаяся каждую итерацию self.Tau = np.ones((n_dim, n_dim)) # Путь каждого муравья в определённом поколении self.Table = np.zeros((size_pop, n_dim)).astype(int) self.y = None # Общее расстояние пути муравья в определённом поколении self.generation_best_X, self.generation_best_Y = [], [] # фиксирование лучших поколений self.x_best_history, self.y_best_history = self.generation_best_X, self.generation_best_Y self.best_x, self.best_y = None, None def run(self, max_iter=None): self.max_iter = max_iter or self.max_iter for i in range(self.max_iter): # вероятность перехода без нормализации prob_matrix = (self.Tau ** self.alpha) * (self.prob_matrix_distance) ** self.beta for j in range(self.size_pop): # для каждого муравья # точка начала пути (она может быть случайной, это не имеет значения) self.Table[j, 0] = 0 for k in range(self.n_dim — 1): # каждая вершина, которую проходят муравьи # точка, которая была пройдена и не может быть пройдена повторно taboo_set = set(self.Table[j, :k + 1]) # список разрешённых вершин, из которых будет происходить выбор allow_list = list(set(range(self.n_dim)) — taboo_set) prob = prob_matrix[self.Table[j, k], allow_list] prob = prob / prob.sum() # нормализация вероятности next_point = np.random.choice(allow_list, size=1, p=prob)[0] self.Table[j, k + 1] = next_point # рассчёт расстояния y = np.array([self.func(i) for i in self.Table]) # фиксация лучшего решения index_best = y.argmin() x_best, y_best = self.Table[index_best, :].copy(), y[index_best].copy() self.generation_best_X.append(x_best) self.generation_best_Y.append(y_best) # подсчёт феромона, который будет добавлен к ребру delta_tau = np.zeros((self.n_dim, self.n_dim)) for j in range(self.size_pop): # для каждого муравья for k in range(self.n_dim — 1): # для каждой вершины # муравьи перебираются из вершины n1 в вершину n2 n1, n2 = self.Table[j, k], self.Table[j, k + 1] delta_tau[n1, n2] += 1 / y[j] # нанесение феромона # муравьи ползут от последней вершины обратно к первой n1, n2 = self.Table[j, self.n_dim — 1], self.Table[j, 0] delta_tau[n1, n2] += 1 / y[j] # нанесение феромона self.Tau = (1 — self.rho) * self.Tau + delta_tau best_generation = np.array(self.generation_best_Y).argmin() self.best_x = self.generation_best_X[best_generation] self.best_y = self.generation_best_Y[best_generation] return self.best_x, self.best_y fit = run
Граф, на котором будет происходить поиск решения, можно сгенерировать случайным образом. Сначала генерируются координаты точек, затем при помощи модуля spatial из библиотеки scipy происходит вычисление матрицы расстояний (расстояние от каждой вершины до каждой вершины).
import numpy as np from scipy import spatial num_points = 2000 # количество вершин points_coordinate = np.random.rand(num_points, 2) # генерация рандомных вершин print(«Координаты вершин:n», points_coordinate[:10], «n») # вычисление матрицы расстояний между вершин distance_matrix = spatial.distance.cdist(points_coordinate, points_coordinate, metric=’euclidean’) print(«Матрица расстояний:n», distance_matrix)
Источник: vc.ru
Исполнитель Муравей
Сегодня во многих школах изучение темы «Алгоритмизация» начинается на уроках информатики с 3 класса. Это обусловлено тем, что психологические возрастные особенности учеников позволяют учителю провести первое знакомство с алгоритмами и бездумными исполнителями в игровой, занимательной форме. Бездумный исполнитель воспринимается детьми как сказочный герой, персонаж компьютерной игры, поэтому очень важен выбор исполнителя и его компьютерной среды.
Творческим коллективом под руководством главного методиста ОблЦИТ Дедовой Ларисой Викторовной был разработан комплекс программ, предназначенный для компьютерного сопровождения темы «Алгоритмизация» в 3 — 6 классах. Исполнитель Муравей — это программа, содержащая учебную компьютерную среду для формирования и закрепления у учащихся 4-6 классов знаний и навыков по теме «Алгоритмизация». Основой для создания компьютерного исполнителя послужила книга «Муравьиные сказки» Г.Н. Гутмана и О.М. Карпиловой.
При работе с Муравьем учащиеся получают:
- представление об алгоритме как упорядоченной последовательности действий и способах записи этой последовательности;
- представление о бездумном исполнителе и системе его команд;
- представление об обусловленных и циклически повторяющихся действиях;
- навыки выполнения алгоритмов;
- представление о зависимости результата выполнения алгоритма от исходных условий;
- представления о переменной, изменении значения переменной во время выполнения алгоритма.
Среда позволяет работать с исполнителем в ручном, отладочном и автоматическом режимах.
В настоящее время библиотека задач для Исполнителя Муравья содержит более 300 заданий для решения задач по всем алгоритмическим конструкциям.
Проведена классификация заданий по степени сложности.
Знакомьтесь: Исполнитель Муравей
Что такое Исполнитель Муравей? Ответ на этот вопрос Вы найдете в данном разделе.
Знакомьтесь: Компания Муравья
Из опыта работы
В данном разделе размещены примеры уроков.
Наступающие события
Следите за рубрикой! В данном разделе будет появляться информация о предстоящих мероприятиях (дата, время и форма проведения, условия для принятия участия и другое).
Архив событий
В данном разделе будут представлены материалы по прошедшим мероприятиям (олимпиады, конкурсы, семинары).
Источник: letopisi.org
Чуждый интеллект: виртуальный муравейник против искусственного разума
Компьютерам, умеющим самостоятельно адаптироваться к изменяющейся ситуации, совсем не нужно быть разумными по-человечески. На Земле есть существа, которые, несмотря на свою примитивность, успешно решают сложнейшие проблемы — и делают это решительно не человеческими методами. Не стоит ли поучиться у них?
Вспомните муравьёв. Эти насекомые образуют поразительно сложные коллективы, для описания которых требуются слова, почти никогда не применяемые в отношении животных. Они используют разделение труда. Они воюют и обращают пленников в «рабство». У некоторых видов есть даже что-то вроде сельского хозяйства: они разводят съедобные грибы и пасут тлю, выделяющую сладкое вещество, которое муравьи употребляют в пищу.
При этом отдельные муравьи не отличаются умом даже по меркам насекомых. Мозг муравья состоит всего из 250 тысяч нейронов. По этому показателю они уступают не только пчёлам, но даже тараканам, у которых целый миллион нейронов (у человека, для сравнения, их 86 миллиардов). Об уровне интеллекта нельзя судить лишь по количеству нейронов, но в данном случае эту цифру подкрепляют и другие факты. Многие виды насекомых обладают более разнообразными поведенческими реакциями, чем муравьи.
Как может сочетаться такая сложность с такой простотой? Ответ на этот вопрос учёные выяснили не сразу. В 1953 году молодой энтомолог Эдвард О. Уилсон поставил перед собой задачу: разобраться, как муравьи-разведчики передают рабочим муравьям информацию о том, где находится найденная ими еда.
Очевидно, что они не могут объяснить это на словах — у муравьёв нет речи. И не только речи — они вообще не издают звуков, да и слух у них, как правило, так себе. Пчёлы кодируют навигационные сведения в замысловатых «танцах», но за муравьями не водится ничего подобного. Муравьи большинства видов не отличаются хорошим зрением, что закрывает для них такой метод общения.
Если не зрение и не слух, то что же? Остаётся запах.
Правдоподобная догадка — это хорошо, но на одних догадках далеко не уедешь. Необходимо экспериментальное подтверждение (или, если не повезёт, опровержение). Уилсон обустраивает искусственный муравейник из оргстекла, населяет его огненными муравьями и начинает наблюдения.
Вскоре он замечает, что муравьи, возвращающиеся с добычей, волочат брюшко по земле — вероятно, выделяя при этом вещество, которое могут учуять другие. Это уже весомый довод в пользу предположения, что коммуникация происходит химическим путём, но довода этого по-прежнему мало.
Следующий шаг — определить, какое вещество выделяют эти насекомые. Уилсон начинает препарировать муравьёв, пытаясь найти источник того самого запаха. Это не так уж просто: в огненном муравье не больше трёх-четырёх миллиметров, а брюшко — и того меньше.
Учёный проверяет орган за органом, но муравьи никак не реагируют на их запах. Наконец, он обнаруживает крохотную железу непонятного назначения — и муравейник сходит с ума. Муравьи наперегонки бросаются к мазку вещества из этой железы. Уилсон пишет этим веществом своё имя, и через мгновенье сотни муравьёв заполняют проложенную дорожку, складываясь в латинские буквы.
Позже «сигнальные» вещества вроде того, которое нашёл Уилсон, назовут феромонами. Лексикон среднего муравья состоит из десятка-другого феромонных сигналов. Встречая их, он действует как конечный автомат: без вопросов и размышлений переходит к алгоритму, который соответствует сигналу, и отрабатывает его до тех пор, пока не произойдёт переход в другое состояние.
Вот прекрасный пример того, насколько жёстко запрограммированы реакции муравьёв. Когда муравей гибнет внутри муравейника, поначалу никто не обращает на него внимания, даже если он лежит на пути и мешает движению. Через пару дней его разложение приводит к образованию олеиновой кислоты. Запах олеиновой кислоты — это сигнал.
Первый же муравей, учуявший его, переходит в режим могильщика: он хватает источник запаха и тащит на свалку. Действительно ли это муравей и мёртв ли он — не играет роли. Если измазать в олеиновой кислоте здорового муравья, его так или иначе выкинут из муравейника. Сопротивление бесполезно: лишь когда запах выветрится, муравью позволят «вернуться в мир живых».
Окрестности каждого муравейника покрыты густой сетью невидимых химических записей. Эта сеть представляет собой своего рода внешнюю память колонии. Муравьи следуют записанным в ней инструкциям с беспрекословностью компьютеров, исполняющих программу, попутно дописывая, улучшая и отлаживая её.
Создание невидимой феромонной программы начинается с муравья, который сбился с готовой дорожки. Без неё он вынужден хаотично рыскать в окрестностях муравейника, разыскивая еду для колонии. Найдя что-то, заслуживающее внимания, муравей возвращается в гнездо, оставляя за собой пахучий след.
«Внешняя память» муравьёв не застрахована от ошибок. Если феромонный путь замкнётся, муравьи попадут в бесконечный цикл, из которого нет выхода. Каждый новый круг по замкнутому маршруту усиливает запах следа, привлекая всё новых и новых жертв. Так продолжается до тех пор, пока муравьи не погибнут от истощения.
Новые добытчики движутся уже по его следам, и каждый из них тоже отмечает пройденный путь феромонами. Чем больше муравьёв достигают хлебного места и возвращаются обратно, тем мощнее становится феромонный след.
И вот тут есть интересная подробность: муравьи далеко не сразу выстраиваются гуськом и идут друг за другом след в след. Пока запах слабый, они добираются до цели как придётся и часто отклоняются от траектории, по которой следовал разведчик и которая, скорее всего, далека от идеала.
Рано или поздно кому-то удаётся наткнуться на более короткий и быстрый маршрут. Пока другие добираются до цели окружной дорогой, этот муравей и его последователи успевают совершить три захода. В результате их феромонный след усиливается гораздо быстрее. Запах привлекает других муравьёв, и вскоре самый короткий путь превращается в главную магистраль. Менее удачные дорожки оказываются заброшены и постепенно утрачивают запах.
Что произошло? Муравьи нашли оптимальное решение довольно сложной задачи. Даже их ошибки и случайные блуждания в итоге принесли пользу: с их помощью колония изучила все возможные варианты, а затем сделала выбор в пользу лучшего.
Если найденную дорогу перегородит препятствие, процесс повторится: муравьи ринутся в обход, найдут несколько альтернативных вариантов, кратчайший путь быстрее накопит феромонные следы, победит более длинные и всё вернётся на круги своя. Нарушенная программа скорректируется.
Тут самое время перейти от компьютерных метафор к настоящим компьютерам. В 1991 году особенности поведения муравьёв привлекли внимание бельгийского математика Марко Дориго. Он заметил, что муравьи фактически занимаются решением задачи коммивояжёра и это у них неплохо получается.
Задачу коммивояжёра обычно формулируют следующим образом: проложите наиболее выгодный маршрут, по которому следует отправиться странствующему торговцу, если необходимо посетить такие-то города, а в финале вернуться в исходную точку. Множество практических задач, начиная с проектирования микропроцессоров и заканчивая секвенированием ДНК, сводится к той или иной вариации на эту тему.
Для человека поиск решения не составляет труда (достаточно одного взгляда на карту), а вот для компьютера задача коммивояжёра — это грандиозная проблема. Дело в том, что её нельзя решить «в лоб». Маршрутов оказывается невероятно много даже при относительно скромном количестве городов. Так много, что их невозможно перебрать и проанализировать по очереди. Приходится искать лазейки и хитрить.
Дориго предположил, что компьютерную модель поведения муравьёв можно использовать для поиска пути, проходящего через заданные вершины графа. Виртуальные муравьи, стартуя из исходной точки, будут тестировать различные маршруты, отмечая виртуальными феромонами вершины, где они побывали. Спустя несколько итераций оптимальный путь станет очевиден: вершины, через которые он проходит, накопят больше всего отметок.
Метод назвали алгоритмом муравьиной колонии. С одной стороны, он положил начало исследованиям в области так называемого «интеллекта роя» — области информатики, изучающей алгоритмы, основанные на тех же принципах, что и самоорганизация и спонтанный порядок в природе. С другой стороны, его хоть и осторожно, но начинают применять на практике.
Малоизвестный факт: персонажи игры Sims спроектированы по образу и подобию муравьёв. Уилл Райт, придумавший Sims, разрабатывал симулятор муравейника SimAnt, и результат настолько впечатлил его, что он решил воспроизвести удачный подход в новом проекте. Каждый предмет в игре распускает невидимые «феромоны» определённого типа: еда, энергия, гигиена, общение или развлечения.
Когда у персонажа возникает какая-то потребность, он направляется по самой сильной феромонной дорожке соответствующего типа. Один из пионеров в этой области — швейцарская компания AntOptima, в 2001 году отпочковавшаяся от располагающегося в Лугано Института Далле Молле по изучению искусственного интеллекта. За прошедшее с тех пор время она успела внедрить продукты, основанные на алгоритме муравьиной колонии, в несколько европейских компаний.
Один из крупнейших клиентов AntOptima — главная швейцарская сеть супермаркетов Migros. Муравьиный алгоритм используется для организации движения 1200 грузовиков, которые развозят товары по 600 магазинам, разбросанным по всей Швейцарии. Задача усложняется тем, что, во-первых, автопарк Migros неоднороден и состоит из трёх видов грузовиков разной вместительности и, во-вторых, часть магазинов не приспособлена для разгрузки некоторых типов грузовиков.
В AntOptima разработали замысловатую модификацию алгоритма муравьиной колонии, учитывающую все эти тонкости. Используется не один «муравейник», а два: один оптимизирует расстояние, а другой — сроки доставки. Чтобы учесть разнотипность транспорта, муравьям случайным образом присваивается один из типов грузовиков. Алгоритм запускают каждое утро, чтобы получить маршруты для каждого грузовика на весь день.
Схожая проблема стояла перед корпорацией Air Liquide, занимающейся производством сжиженных газов, используемых в промышленности и медицине. У корпорации около сотни заводов в Соединённых Штатах, ежедневно отправляющих продукцию в шесть тысяч пунктов, находящихся в разных частях континента. Для доставки применяются четыре сотни грузовиков, железная дорога и трубопроводы. Кроме того, для полноты картины нужно учитывать стоимость электроэнергии. Она не только везде своя, но ещё и постоянно меняется.
Систему, ежедневно планирующую эффективную доставку с учётом всех этих факторов, для Air Liquide написали в компании BiosGroup. Любопытный побочный эффект: идеальные маршруты оказались настолько противоестественными, что поначалу вызвали ропот у водителей. Алгоритм запросто мог отправить машину к дальнему заводу, пропустив завод, который находится рядом с клиентом. При ближайшем рассмотрении неизменно оказывалось, что прав он, а не люди: если учесть не только расстояние, но и все прочие факторы, сделать крюк бывает выгоднее.
Во France Telecom муравьиный алгоритм попытались применить для маршрутизации информации в сети. Проектом руководил эксперт в области сложных систем Эрик Бонобо. «Компьютерра» рассказывала об этом в 2004 году:
Бонобо разработал специальные программные агенты, которые могут пересылаться по сети от маршрутизатора к маршрутизатору как сообщения. Когда агент достигает маршрутизатора, он оставляет на нём особую пометку. Если там побывал не один агент, а несколько, их пометки скапливаются. Одним словом, всё как у муравьёв.
Как ни странно, этот подход сработал.
И даже ошибки, которые неизбежно возникают поначалу, постепенно сами собой исчезли. «У общественных насекомых ошибки и случайное поведение не приводят к сбоям, — объясняет Бонобо. — Наоборот, делая ошибки, они добиваются успеха и отыскивают новые способы решения проблем в дополнение к старым».
Есть и другие примеры. Подражание муравьям неплохо помогает и в управлении группами автономных роботов (в этой области экспериментировал Виджай Кумар из университета Пенсильвании, сейчас более известный своими роящимися квадрокоптерами), и в борьбе с пробками на дорогах, и даже при решении некоторых задач в области искусственного интеллекта (впрочем, чему тут удивляться: специалисты подозревают, что между взаимодействиями нейронов в мозге и отдельных особей в рое есть много общего).
Впрочем, одна из интересных возможностей пока остаётся нераскрытой. Все описанные модели муравейника, как правило, просчитывались на единственном компьютере. А ведь у интеллекта муравейника есть редкое достоинство: его работа потрясающе распараллеливается, поскольку муравьи действуют хоть и с общей целью, но при этом совершенно независимо друг от друга. Ситуация, в которой это качество будет полезным, может возникнуть совсем скоро.
Если верны прогнозы, согласно которым вот-вот наступит время интернета вещей и повсеместного компьютинга, вскоре инженерам придётся думать, как наладить автоматическое взаимодействие десятков, а то и сотен независимых устройств. Возможно, ответ дадут как раз наблюдения за общественными насекомыми вроде муравьёв.
Источник: www.computerra.ru
[WF — RU] FrolSpeed (муравей) — не банят! 28.03.2017
Всем привет!
Программа работает на все игры, ускоряет клиенты (windows).
Играю месяц, на своей версии не банят.
Тестите и пишите, эта программа 1 в 1 как муравей, который продают за деньги.
Что дает программа? По вам очень слабо будет проходить урон, быстрая стрельба, также все взаимодействие!
(ВЕРСИЯ ПОЛНОСТЬЮ ПЕРЕДЕЛАНА)
1. Скачиваем
2. Распаковываем
3. Запускаем «FrolSpeed»
4. Выбираем скорость
5. Заходим в настройку
(и остаемся там если будем играть).
Чтобы вернуть в исходное состояние ставьте +1.07
Что-бы отключить горячие клавиши, для удобств!
Выбирайте скорость, и открывайте «ОКНО» как на картинке.
Источник: chitachok.com