Tal Cual

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

• media-savvy
• 05.04.202210.06.2023
• 5

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

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

Область, которая не смогла бы обойтись без алгоритмов в ней, – это новые технологии. Для каждой конкретной задачи используются свои алгоритмы и многие изобретения просто не смогли бы действовать без них. Алгоритмы применяются для разных целей. Во-первых, это создание таких систем, которые вмещают в себя различные законы физики и апеллируют к ним для работы устройств. Быстрое преобразование Фурье (основанный на преобразовании Фурье алгоритм) – это как раз такой алгоритм, который преобразует сигналы из временных интервалов в диапазоны частот и наоборот. Интернет, Wi-Fi, смартфон, телефон, компьютер, маршрутизатор, спутники – почти всё, что имеет внутри себя электронно-вычислительное устройство, так или иначе использует этот алгоритм для функционирования. В каком-то смысле знание особенностей работы преобразования Фурье – это азы электроники, вычислительной техники и телекоммуникаций.

Во-вторых, это работа с данными. Лучше всего в этом разделе новых технологий проявили себя алгоритмы сортировки (быстрой, пирамидальной, слиянием). Ранее до этого использовались другие подходы, например как сортировка пузырьком, но они не так хорошо себя зарекомендовали. По сути, благодаря алгоритмам сортировки в новых технологиях есть глубинный анализ данных, искусственный интеллект, анализ связей и большинство вычислительных инструментов в мире, среди прочего присутствует и интернет.
Вообще, интернет не смог бы работать эффективно без существования алгоритма Дейкстры. Цели, для которых он применяется – это создание архитектуры сети. Алгоритм используется в задачах, где проблему можно представить в виде графа для поиска кратчайшего пути между двумя узлами. Сегодня среди решений подобных задач есть и более оптимальные, но алгоритм Дейкстры используется в системах, требующих особой стабильности.
Кроме того, алгоритмы используются для шифрования данных. Разработанный наукой криптографии алгоритм RSA (в недрах одноимённой компании) сделал криптографию доступной для многих организаций и предопределил будущее этой технологии. Алгоритм RSA определяет как делиться открытыми ключами между независимыми платформами и конечными пользователями так, чтобы была возможность использовать шифрование. Пока стоит отметить, эта проблема до сих пор решена не полностью. Ещё один алгоритм, использующийся в этой области – это алгоритм безопасного хэширования. Он представляет из себя семейство хэш-функций (SHA-1, SHA-2, и т.д.), выдвинутых Национальным институтом стандартов и технологий США. Магазины приложений, антивирусы, электронная почта, браузеры – все они используют хэш, который вычисляется этим алгоритмом, чтобы определить, загрузилось ли из интернета желаемое и не было ли произведено атаки «человек посередине» или фишинга. Также нужно отметить алгоритмы факторизации целых чисел, как факторы, за счёт которых работают многие криптографические протоколы, в частности RSA. RSA основан на практически невозможном случае разложении числа на простые множители при взламывании кода. Однако такая даже минимальная возможность есть угроза для особо важных компаний и она может преодолеваться, например, с помощью квантового компьютера, используя который какой-либо алгоритм факторизации чисел создаёт более совершенную систему.

Среди прочих целей, которым отвечают алгоритмы сегодня – возможность структурировать те или иные интернет-ресурсы под свои потребности. От поисковых систем и социальных сетей до инструментов анализа рынка – везде применяется алгоритм анализа связей. Этот алгоритм был разработан в 1976 г. Габриэлем Пински и Фрэнсисом Нарином. Идея анализа связей проста: можно представить график в виде матрицы, что сводит задачу к проблеме собственной значимости каждого узла. Такой подход к структуре графа даёт возможность представить структуру ресурса с соответствующей важностью каждого объекта, включённого в систему. При ранжировании страниц во время поиска в Google, при генерации ленты новостей в Facebook, при составлении списка возможных друзей на Google+ и Facebook, при работе с контактами в LinkedIn – каждый раз в вышеперечисленных сервисах используется этот алгоритм. Да, все эти сервисы работают с разными параметрами и объектами, но математический эквивалент везде будет одним и тем же.

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

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

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

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

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

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

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

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

Данная структура позволяет упростить процесс обучения и часто используется в области компьютерных игр и робототехники, когда количество действий и варианты поведений заранее предопределены. Говоря об играх, то в пример использования можно привести серию игр о тёмном рыцаре (Batman: Arkham series) и Alien: Isolation, основанную на мире фильма «Чужой». В последней дерево решений имеет по сотне узлов для любых непредвиденных в игре ситуаций. Что интересно, некоторые узлы деревьев были заблокированы для того, чтобы в процессе прохождения игрок видел всё новые и новые особенности и интересные механики, которые ему преподносит игра, на самом деле, просто открывая то или иное заблокированное ранее поддерево способностей.

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

Конечные автоматы – ещё одна модель управления принятием решений, реализуемая в компьютерных играх для систем с конечным множеством состояний. Чтобы определить конечный автомат необходимо задать конечное множество состояний игровой системы и набор переходов из одних состояний в другие. Реализуется данный подход с помощью графа по причине того, что с увеличением числа состояний не возникает проблем с его расширением и общей производительностью системы. В данном случае узлы графа – состояния игровой системы, а его ребра – переходы из одних состояний в другие. Получается, что такой граф может как дерево решений отсылать каждый раз к новому узлу, который в этой схеме как бы перекрещивается с другими деревьями. Схожесть в управлении процессами этими моделями заставляет разработчиков использовать оба алгоритма в разных играх, в частности, таких, как Halo, F.E.A.R. и приключенческих играх вместе с RPG и стратегиями реального времени.

И, наверное, самый последний алгоритм, который стал появляться в играх в 2005-2010 гг., называется системами планирования. Данный подход базируется на очень простой идее – сделать поведение персонажей более естественными, определив их цели, мотивацию и соответствующие действия. При таком подходе каждый несобственный игровой персонаж будет иметь цель или целое множество целей, которые будут ранжироваться по системе приоритета. В игровой индустрии имеется несколько удачных примеров реализации этого алгоритма, во-первых – это не только мод A-Life но и, кроме того, сама игра для него S.T.A.L.K.E.R. вся взятая. Суть систем планирования заключается в том, что персонажи в игре живут своей жизнью и существуют всё время, а не только когда их видит игрок. Это идёт вразрез с привычными оптимизациями, используемыми при разработке игр. В зависимости от обстановки окружающего мира среди всех операторов целей выбирается один и дальнейшие поведенческие особенности персонажа определяются именно его работой. Таким образом, из-за того, что разные персонажи в одни и те же моменты времени имеют различные цели, создаётся эффект реальности происходящего.

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