Генетический алгоритм — это один из методов решения задач, который разработан на основе эволюции. Такой алгоритм используют тогда, когда количество решений настолько большое, что протестировать их все нереально. Расскажем, как устроены эти алгоритмы, и почему с ними нейросети работают на порядок лучше.
Эволюция в математике
Составление алгоритма начинается с создания реестра моделей — популяции. Причем каждая модель должна быть представлена набором чисел — генов. Этот набор генерируют случайным образом.
Список решений — это и есть популяция. Из нее выбираются самые жизнеспособные модели для следующей популяции. Этот процесс многократно запускается до тех пор, пока не будет найдено оптимальное решение.
Чтобы понять, насколько качественным вышло решение, применяют функцию приспособленности. Например: F-score и точность предсказания. Чем качественнее решение, тем больше шансов, что особь будет отобрана для следующей популяции.
Анализ данных не останавливается на Excel. Пройдите онлайн-курс «Google Таблицы для бизнеса». Научитесь работать с Google Таблицами с любого устройства, синхронизируйте вашу работу с коллегами и интегрируйтесь с Google Forms и Google Analytics.
Основные стадии
После того, как будет создана первая популяция, алгоритм проходит четыре стадии:
1. Отбор.
Смысл отбора в том, чтобы найти самые жизнеспособные модели и передать их гены следующему поколению. Приспособленность — главное качество, по которому отбирают родителей. Причем количество родителей (пар особей) может быть любым, но всегда одинаковым для каждого последующего цикла.
Есть два основных метода отбора::
- Ранговый. Популяцию делят на несколько рангов (групп). Ранги назначают на базе функции приспособленности. А затем пропорционально отбирают по несколько особей из каждого ранга.
- Турнирный. Несколько особей выбирают случайным образом. Из отобранной группы выделяют лучших. Процесс повторяют до тех пор, пока не наберут нужное число особей из этой популяции.
У каждого метода свои плюсы. Ранговый помогает сохранить разнообразие особей. Турнирный подходит тогда, когда модели можно сравнивать только попарно, а выражение функции приспособленности числом недоступно. Например, его используют для игровых стратегий.
2. Скрещивание.
На этой стадии происходит обмен информацией между родителями. Из популяции отбирают пары особей и смешивают отдельные фрагменты их хромосом. В результате получается новый набор генов.
Часто применяют метод одноточечного скрещивания — внутри хромосом родителей выбирают случайное место и разделяют каждую из них на две части. Далее эти части меняют местами, а затем новые данные загружают в популяцию.
3. Мутация.
Запускается редко и в случайном порядке переставляет местами числа отдельных генов (например: меняет 1 на 0).
Мутация способствует сохранению разнообразия внутри популяции. При этом степень приспособленности мутировавшей особи может повыситься, а может понизиться.
4. Завершение алгоритма.
Процесс заканчивается тогда, когда новая созданная популяция почти не отличается от предыдущей. Это означает, что полученное решение оптимально.
Онлайн. На практике.
r_d помогает в этом — учит людей создавать будущее уже сегодня.
Генетические алгоритмы или нейросети: что лучше
Алгоритм идеально работает с большим объемом дискретных данных, так как простой перебор занимает на порядок больше времени.
Data scientist Мишель Берк запрограммировал алгоритм расставить в верном порядке буквы зашифрованного предложения: Genetic Algorithms are wild. Алгоритму потребовалось сделать выбор из всех вероятных комбинаций — 2753. У него было 30 особей в популяции, а решил задачу он на 51-м поколении. Для этого ему пришлось проверить 1 530 комбинаций.
Алгоритм может быстро найти кратчайший путь между двумя точками. Поэтому его применяют для построения маршрутов GPS-систем и расчета траектории движения.
Для расчета распространения коронавируса ученые также воспользовались генетическим алгоритмом. На его базе был проведен анализ распространения инфекции в 40 странах мира.
Нейросети лучше работают с непрерывными данными. Так они лучше понимают языки или распознают изображения. А еще нейросети используют для задач линейной регрессии, когда нужно найти зависимость между переменными.
Мы разработали онлайн-курс «Excel для финансов» для тех специалистов, которым нужно быстро и качественно составлять отчеты в Excel. Вы научитесь рассчитывать зарплаты сотрудников, готовить налоговую и финансовую отчетность. После курса ваша работа с данными в Excel станет намного эффективнее.
Алгоритмы и нейросети в симбиозе
Существуют примеры удачного объединения нейросетей и алгоритмов в одной системе.
Так алгоритмы могут оптимизировать функциональность модели. Например: подобрать вес, функцию активации. Но их использование для подбора требует больших затрат времени и вычислительных мощностей. Например: чтобы научить нейросети обыгрывать реальных людей в видеоиграх.
Так в 2017 году OpenAI применила алгоритм, для отбора тех ботов в игру Dota 2, которые выигрывали матчи. А затем они провели обучение нейросетей на основе этих данных.
Узнать подробнее об обучении в геймдеве можно тут.
Онлайн. На практике.
r_d помогает в этом — учит людей создавать будущее уже сегодня.
Хотите узнать больше? Подписывайтесь на каналы и соцсети онлайн-школы robot_dreams:
Начать дискуссию