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

Ищете… что-то?

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

Это связано с тем, что ИНС - это, по сути, машины отображения ввода-вывода, управляемые статистикой. Добавьте изображение, и ИНС сможет сказать вам, кошка это или нет (скорее всего, да, если вы нашли изображение в Интернете). Но попробуйте попросить ИНС найти кошку в Интернете, и вы застрянете. Какие бывают входы / выходы? Как вы его тренируете? Эта проблема усугубляется, когда проблема настолько нечетко определена, что вы не совсем уверены в том, что ищете (найти этот идеальный котик gif для канала #random вашей команды в Slack), или когда количество вариантов поиска через растет неоправданно высоко (мой поиск в Google по запросу "кошка" только что дал 7,5 миллиардов результатов, что больше, чем население планеты).

Задача о рюкзаке

Теперь кот из мешка, давайте проиллюстрируем проблему классическим примером задачи поиска / оптимизации: задачей о рюкзаке.

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

Давайте начнем решать эту проблему с пересмотра пары поисковых терминов AI, которые мы рассмотрели еще в начале этой серии Code of AI:

  • Пространство поиска - абстрактные параметры, ограничивающие поиск.
  • Состояния - позиции или наборы условий в пространстве.
  • Состояние цели - желаемый результат или решение.

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

Решение методом грубой силы

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

Запуск этого кода показывает, что мы действительно находим решение, и для 10 элементов в этом примере мы находим решение довольно быстро. Но что произойдет, если есть еще элементы для поиска? С 10 элементами нам нужно всего лишь перебрать около 1000 комбинаций, а на моей машине это занимает около 7 мс. Но с 20 элементами количество комбинаций увеличивается примерно до 1000000 и занимает 2,5 секунды. Еще пять (25) элементов составляют около 33 миллионов комбинаций, а поиск занимает около 2 минут. Эта тенденция показывает, что задача о рюкзаке имеет экспоненциальную (O (2 ^ n)) сложность, что означает, что она быстро становится непрактичной для больших значений n.

GA: другой вид поиска

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

Это именно интуиция, лежащая в основе ГА. Вдохновленные естественной эволюцией - процессом, с помощью которого простой организм со временем становится более сложным и лучше адаптируется к окружающей среде посредством естественного отбора - GA оценивают набор состояний (популяция в терминах GA) на предмет их фитнес и разработать лучшие решения («наиболее приспособленные») в следующем поколении. В конце концов, общая приспособленность населения повысится, и будет найдено наиболее подходящее решение проблемы.

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

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

Рюкзак как хромосома

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

Чтобы проиллюстрировать это, вот пример кода, который создает случайную хромосому и преобразует ее в фенотип.

Это в сумке

Вот где мы и оставим это на этой неделе. Мы рассмотрели некоторые ограничения машинного обучения и ИНС, а также необходимость более широкого взгляда на некоторые проблемы ИИ. Мы также представили генетические алгоритмы как альтернативный способ поиска в сложном пространстве и некоторые фундаментальные концепции в GA, генах, хромосомах, фенотипах и функциях пригодности .

Я предоставил код для проблемной хромосомы о рюкзаке. Если вы готовы принять вызов, можете ли вы взять код из функции bruteForceKnapsack (см. Выше) и создать функцию пригодности для оценки отдельной хромосомы?

Как всегда, исходный код всех вышеперечисленных примеров вы можете найти на нашем GitHub.

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