Об ИИ без мифов. Путеводитель по истории Искусственного Интеллекта

• Муравьиный алгоритм (ACO). В начале 90-х Марко Дориго, ученый из Брюссельского свободного университета, первым применил математические процедуры, основанные на SI, для решения таких задач как организация грузоперевозок, управление авиалиниями, координация действий боевых роботов. Дориго – автор алгоритмов метаэвристической (metaheuristic – «поиск за пределами») оптимизации, базирующейся на подражании муравьиной колонии, которая оказалась эффективной для нахождения приближенных решений задач, сводящихся к задаче коммивояжера. Суть подхода заключается в анализе и использовании модели поведения муравьев, ищущих пути от колонии к источнику питания. Первая версия алгоритма, предложенная Дориго в 1992 году, была направлена на поиск оптимального пути в графе. Сущность ACO чрезвычайно проста – алгоритм имитирует действие феромонов, биологически активных веществ, выделяемых животными и специфически влияющих на поведение других особей. Выделяя феромоны, насекомые подают разные сигналы, например, так они обозначают метками пройденный ими путь, по этим меткам муравей может найти путь обратно в муравейник или метки показывают дорогу другим к найденной добыче. Простой эксперимент – на отмеченном пути от муравейника к источнику пищи поставлен барьер, причем так, что обход с одной стороны длиннее, чем с другой, в изменившейся ситуации сначала выбор направления обхода будет случайным, но потом окажется, что с той стороны, где путь короче, плотность потока муравьев больше, поскольку насекомые выделяют больше фермента и сильнее привлекают в нужную сторону оставшихся. Через какое-то время колония будет пользоваться только коротким путем. Примерно так же решаются и более сложные задачи – например, распределение работы по добыче еды и ремонту муравейника. Система моделирования Ant Colony System, предложенная Дориго, имитирует эту схему на графах, в ней могут видоизменяться способы распространения и восприятия «феромонов».

• Метод оптимизации роем частиц (PSO) возник из попыток объяснить синхронное перемещение птичьих или рыбьих стай, он был предложен психологом Джеймом Кеннеди и инженером Расселом Эберхартом, которые в 1995 году выпустили книгу Swarm Intelligence. В основе их метода лежит эволюционный алгоритм (Evolutionary Algorithm, EA), имитирующий социальное поведение особей в стае. Совокупное поведение всей стаи складывается из поведения каждой отдельной особи, которое лишено малейших признаков антагонизма и даже несет на себе оттенок альтруизма. Эти особенности поведения особей позволяют сложиться своего рода кооперации, где за счет возможных небольших ущербов для каждого выигрывает вся популяция в целом. Средствами SI моделируются виртуальные стаи, состоящие из условных организмов – частиц, существование которых состоит в перемещении в многомерном пространстве решений. Изменение положения отдельной частицы, точно так как особи в рое живых существ, определяется не только стремлением к конкуренции за доступные ей ресурсы, но одновременно примитивным альтруизмом, выражающемся в координации собственного поведения с поведением и соседей с возможным ущербом для себя. Каждая частица может менять свое положение и скорость в пространстве поиска ресурсов, она стремится занять оптимальный для себя участок в пространства решений, но так, чтобы улучшая собственное положение в минимальной степени затрагивать интересы соседних частиц.

• Пчелиный алгоритм BCO имеет более чем десятилетнюю историю, в отличие от ACO и PSO здесь воспроизводится более сложная иерархическая система отношений, состоящая из особей с разным статусом: матка, рабочие пчелы и трутни. Для практических исследований в области интеллекта роя используются простейшие роботы. В 2003 исследовательская группа из нескольких университетов, возглавляемая Стэнфордским исследовательским центром (SRI International, SRI) построила специальный рой из 100 роботов Centibots, в задачу которого входил поиск объектов в заданном регионе. Из этих исследований выросло новое направление, именуемой групповой робототехникой, ставящее своей целью координированную работу систем, которые состоят из большого числа в основном простых физических роботов.