Вадим Шмаль - Применения элементов искусственного интеллекта на транспорте и в логистике

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

Гетерогенное оборудование способно предоставлять генетические алгоритмы со скоростью и гибкостью обычного компьютера, используя при этом меньше энергии и компьютерного времени. Большинство реализаций генетических алгоритмов основаны на подходе генетической архитектуры.

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

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

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

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

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

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

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