На этом шаге мы введем несколько новых понятий.
В биологии теория эволюции объясняет, каким образом генетическая мутация в сочетании с ограничениями окружающей среды с течением времени приводит к изменениям в организме, включая видообразование - создание новых видов. Механизм, обусловливающий то, что хорошо адаптированные организмы процветают, а хуже адаптированные погибают, известен как естественный отбор. В каждое поколение определенного вида входят особи с различными, а иногда и новыми чертами, которые возникают в результате генетической мутации. Все особи соревнуются за ограниченные ресурсы, чтобы выжить, и поскольку живых особей больше, чем ресурсов, то некоторые из них должны умереть.
Если особь имеет мутацию, которая делает ее лучше приспособленной к окружающей среде, то у нее выше вероятность выживания и воспроизводства. Со временем у особей, хорошо адаптированных к окружающей среде, будет больше потомков, которые унаследуют эту мутацию. Следовательно, мутация, способствующая выживанию, скорее всего, в итоге распространится на всю популяцию.
Например, если бактерии гибнут от определенного антибиотика, но у одной из них в популяции есть мутация в гене, которая делает ее более устойчивой к этому антибиотику, то эта бактерия с большей вероятностью выживет и размножится. Если антибиотик постоянно применяется в течение длительного времени, то потомки этой бактерии, унаследовавшие ее ген устойчивости к антибиотикам, также с большей вероятностью будут размножаться и иметь собственных потомков. В конце концов эта мутация может распространиться на всю популяцию бактерий, поскольку продолжающееся воздействие антибиотика будет убивать не обладающих ею особей. Антибиотик не вызывает развитие мутации, но приводит к размножению имеющих ее особей.
Естественный отбор существует не только в биологии. Социальный дарвинизм - это естественный отбор в сфере социальной теории. В информатике генетические алгоритмы - это моделирование естественного отбора для решения вычислительных задач.
Генетический алгоритм подразумевает наличие популяции (группы) особей, известных как хромосомы. Хромосомы, каждая из которых состоит из генов, определяющих ее свойства, конкурируют за решение некоей проблемы. То, насколько успешно хромосома решает проблему, определяется функцией жизнеспособности.
Генетический алгоритм обрабатывает поколения. В каждом поколении с большей вероятностью будут отобраны для размножения наиболее подходящие хромосомы. Также в каждом поколении существует вероятность того, что какие-то две хромосомы объединят свои гены. Это явление известно под названием "кроссинговер". И наконец, в каждом поколении существует важная возможность того, что какой-то из генов хромосомы может мутировать - измениться случайным образом.
Если функция жизнеспособности какой-либо из особей популяции пересекает некий заданный порог или алгоритм проходит некоторое указанное максимальное число поколений, возвращается наилучшая особь - та, которая набрала наибольшее количество баллов в функции жизнеспособности.
Генетические алгоритмы - не самое хорошее решение для любых задач. Они зависят от трех частично или полностью стохастических (случайно определенных) операций: отбора, кроссинговера и мутации, - поэтому могут не найти оптимального решения в разумные сроки. Для большинства задач существуют более детерминированные алгоритмы, дающие лучшие гарантии. Но бывают задачи, для которых не существует быстрых детерминированных алгоритмов. В таких случаях генетические алгоритмы являются хорошим выбором.
На следующем шаге мы рассмотрим обобщенный генетический алгоритм.
