Генетические алгоритмы являются частью семейства алгоритмов оптимизации. Они оперируют теорией эволюции, в частности генетической эволюции. Каждое решение представляет собой хромосому, состоящую из генов, и оценивается, чтобы определить, насколько хорошо оно работает. Это повторяется до тех пор, пока не будет найдено хорошее решение.
Эволюция предполагает, что живые организмы, которые мы видим сегодня, не возникли внезапно, а эволюционировали в течение миллионов лет тонких изменений, когда каждое поколение приспосабливалось к окружающей среде. Подробнее см. в этой статье: https://rhurbans.com/intelligence-through-evolution/.
Генетические алгоритмы — это алгоритмы оптимизации. Они используются для быстрой оценки больших пространств поиска хороших решений. Подробнее об алгоритмах оптимизации читайте в этой статье: https://rhurbans.com/optimization-finding-the-best-solutions/. Далее давайте углубимся в то, как работают генетические алгоритмы (ГА).
Когда мы используем GA, крайне важно правильно выполнить этап кодирования. Это требует тщательного проектирования представления возможных состояний. В этом случае мы хотим выяснить, какие предметы включить в рюкзак, чтобы максимизировать общую стоимость и не превысить лимит веса.
Двоичное кодирование представляет ген с точки зрения 0 или 1, поэтому хромосома представлена строкой двоичных битов. Для задачи о рюкзаке 0 = исключить предмет, 1 = включить предмет. Затем мы можем суммировать значения включенных элементов, чтобы определить, насколько хорошо работает эта хромосома.
Когда область поиска невелика, нам довольно легко найти хорошее решение. Но что, если бы в рюкзак можно было добавить 26 возможных предметов? Человеку становится намного сложнее решить ее вручную. Вот где GA полезны.
Генетический алгоритм оценивает производительность каждой хромосомы и использует смешивание для создания новых решений, которые, как мы надеемся, будут работать лучше — например, репродукция человека. Смешение хромосом может происходить по-разному. Простой подход состоит в том, чтобы взять пополам.
Генетические алгоритмы также используют понятие мутации. Как и в природе, случайный ген может измениться после размножения между двумя родительскими хромосомами. Весь этот процесс выполняется в течение многих циклов, называемых поколениями, до тех пор, пока не будет найдено хорошее решение.
GA может работать значительно быстрее, чем другие методы. Но помните, они не гарантируют, что найдут ЛУЧШЕЕ решение. Я буду разрабатывать генетические алгоритмы с более наглядными пояснениями в следующих статьях. Следите за новостями @RishalHurbans.
Спасибо за чтение. Если вы хотите учиться на досуге, см. Grokking AI Algorithms with Manning Publications: http://bit.ly/gaia-book. Или присоединяйтесь к моему списку рассылки для нечастых выпусков знаний: https://rhurbans.com/subscribe.
