Понимание генетических алгоритмов в спектре искусственного интеллекта

Понимание генетических алгоритмов в спектре искусственного интеллекта

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

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

Оглавление

1. Теорема о бесконечной обезьяне
2. Понимание генетических алгоритмов
3. Как эти принципы реализованы в генетических алгоритмах
4. Как использовать в проектах искусственного интеллекта

Теорема о бесконечной обезьяне

Теорема о бесконечной обезьяне гласит, что если обезьяна начинает случайным образом нажимать клавиши на клавиатуре в течение бесконечного количества времени, она почти наверняка напечатает заданный текст, например, полное собрание сочинений Уильяма Шекспира. Фактически, обезьяна почти наверняка наберет любой возможный конечный текст бесконечное число раз. Однако вероятность этого события настолько мала, что для него потребуется больше времени, чем предполагаемый возраст Вселенной, но шансы возникновения этого события не равны нулю.

Доказательство

Предположим, на пишущей машинке 50 клавиш, и нужно набрать слово «банан». Если клавиши нажимаются случайным образом и независимо, это означает, что каждая клавиша имеет равные шансы на нажатие. Тогда вероятность того, что первая напечатанная буква будет «b», равна 1/50, и вероятность того, что вторая напечатанная буква будет «a», также будет 1/50, и так далее. Таким образом, вероятность того, что первые шесть букв будут написаны как «банан», составляет:

(1/50) × (1/50) × (1/50) × (1/50) × (1/50) × (1/50) = (1/50) 6 = 1/15 625 000 000, т.е. менее одного из 15 миллиардов. Но все равно не ноль, значит, все же возможен исход.

Таким образом, обезьяна наберет слово «банан» 1 из 15 625 000 000 раз. Теперь предположим, что обезьяна нажимает кнопку в секунду, время, необходимое для того, чтобы это событие произошло в худшем случае, составляет примерно 495 лет.

Теперь, если я смоделирую компьютерную программу для решения указанной выше проблемы и выполню поиск методом грубой силы по слову «банан», объем вычислений и затраченное время будут огромными. .

Но если я захочу напечатать то же самое, это займет у меня меньше 6 секунд. Почему? Потому что я знаю буквы, знаю слово банан и его написание.

Итак, могу ли я использовать Теорию эволюции и значительно улучшить свою программу? Да, и это благодаря концепции генетических алгоритмов.

Понимание генетических алгоритмов

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

В теории естественного отбора Дарвина три основных принципа, необходимых для осуществления эволюции, следующие:

1) Наследственность. Должен существовать процесс, посредством которого дети получают собственность своих родителей.

2) Вариация - в популяции должно быть множество признаков или средства, с помощью которых можно ввести вариацию.

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

Как эти принципы реализованы в генетических алгоритмах

Генетический алгоритм состоит из пяти этапов:

1. Создание начальной популяции

2. Определение фитнес-функции

3. Выбор родителей

4. Создание кроссовера

5. Мутация

Создание исходной популяции

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

В нашем случае пусть это будет:

• Багама
• abcdef
• ijklmn
• ….
• Все остальные 6-символьные слова
• mnopqr
• Stuvwx
• кабина

Определение фитнес-функции

Функция приспособленности определяет, насколько вероятно, что особь пригодна для воспроизводства, и это основано на его оценке приспособленности. Предположим, наша функция пригодности назначит оценку пригодности или процент вероятности каждому элементу из совокупности для каждого символа, соответствующего нашему целевому слову банан.

В нашем случае пусть это будет:

Элементы, оценка физической подготовки

• banyan, 5 # (в этом слове присутствуют 5 знаков из букв от 'b', 'a', 'n', 'a', 'n', 'a', это 'b', 'a', 'н', 'а', 'н')
• abcdef, 2 # (Аналогично, в этом слове присутствуют 2 символа из букв от 'b', 'a', 'n', 'a', 'n', 'a', это 'a' и 'b ')
• ijklmn, 1 # (согласно приведенному выше правилу, у него есть только одно подходящее слово - ‘a’)
• ……, ..
• Все остальные 6-значные слова, ..
• mnopqr, 1
• stuvwx, 0
• кабина, 5
• так далее …

Выбор родителей

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

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

Элементы, оценка физической подготовки

• Баньян, 5
• кабина, 5

Создание кроссовера

Это наиболее важный этап генетического алгоритма. На этом этапе мы воспроизводим новую совокупность n элементов из выбранных элементов. На этом шаге мы должны переставить и объединить как можно больше слов из символов, полученных из двух родительских слов, выбранных на предыдущем шаге. В нашем случае родительскими словами являются «баньян» и «cabana».

Например, мы можем выбрать последние 3 слова из слова 'баньян' и первые 3 слова из слова 'cabana 'и сформировать новое слово как' cabyan ',

После применения всех возможных комбинаций из слов «banyan» и «cabana» мы получаем новую совокупность .

В нашем случае новыми воспроизводимыми элементами являются:

Воспроизведено n элементов

• Canyan
• кабиан
• кабина
• Babyna
• ……
• Все другие возможные комбинации родительских слов "banyan" и "cabana"
• банан
• Янбак
• так далее …

Мутация

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

Например, предположим, что от 1% предыдущего населения мы получаем такие слова, как 'баньян' и 'янбак '. Теперь мы выбираем эти элементы для создания новой популяции, поскольку эти слова имеют хорошие оценки пригодности 5 и 4 соответственно и, следовательно, имеют высокую вероятность того, что они являются родителями. Теперь, если мы возьмем последние 3 и первые 3 буквы из этих двух слов и объединим их, мы получим 'yanyan', и это слово больше не будет достаточно продуктивным, чтобы получить какие-либо новые разнообразные элементы.

Но если мы изменим наш 1% от предыдущей популяции и изменим буквы «баньян» и «yanbac 'просто перевернув первую и последнюю буквы в обоих словах, мы получим' nanyab 'и' canbay ' . Теперь, если мы применим одну и ту же комбинацию последних 3 и первых 3 букв измененных элементов, мы получим «yabcan», который сильно отличается от « янян '. (Обратите внимание, что при мутации вы можете изменять элементы любым количеством возможных способов. Переворачивание первого и последнего элемента - это просто случайный способ, используемый в этом примере).

Когда этот процесс остановится?

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

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

Конвергенция

• nnbaaa
• aaabnn
• Aabann
• Abaann
• ……
• банан
• бааанн

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

Псевдокод

• НАЧАЛО
  - создать начальную популяцию
• Вычислить фитнес
• ПОВТОР
  - Выбор
  - Кроссовер
  - Мутация
  - Вычисление пригодности
• ПОКА численность населения сблизилась
• ОСТАНАВЛИВАТЬСЯ

Отличный алгоритм, но зачем его использовать в искусственном интеллекте?

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

• Создайте популяцию из нескольких нейронных сетей.

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

• Повторите следующее

1. Обучите все нейронные сети.

2. Рассчитайте стоимость их обучения (ошибка экс-обучения и условия регуляризации).

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

4. Выберите две лучшие нейронные сети в зависимости от их пригодности.

5. Воспроизведите новые нейронные сети из этих

6. Мутировать гены ребенка.

7. Выполните шаги 5–7 для всех нейронных сетей в популяции. В конце последнего поколения у нас оптимальные гиперпараметры.

Заключение

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