В истории хорошо известно описание демографической политики идеального государства в описании философа Платона. В своей краткой форме, описание можно свести к евгенической программе, формулировка которой содержится в трактате «Государство». На некоторых празднествах невест и женихов будут соединять, как их учат верить, якобы по жребию в таком количестве, которое необходимо для сохранения постоянной численности населения; но на самом деле правители города будут производить манипуляцию с жребиями, исходя из евгенических принципов. Они будут устраивать так, чтобы лучшие производители имели больше всего детей. Все дети будут после рождения отбираться у своих родителей, и будут приняты серьезные меры предосторожности, чтобы родители не знали, которые дети являются их детьми, а дети не должны знать, кто их родители. Детей с физическими недостатками и детей худших родителей «станут скрывать как следует в тайном и неизвестном месте».В конце 20 века биологические идеи, отдаленно напоминающие воззрения Платона, получили свою формальную реализацию в виде так называемых генетических алгоритмов. Краткое описание основных положений теории генетических алгоритмов приведено по материалам сайта «Искусственный интеллект», а также с использованием монографии Панченко «Введение в генетические алгоритмы».
Селекция – это выбор тех хромосом, которые будут участвовать в создании потомков для следующей популяции, т.е. для очередного поколения. Такой выбор производится согласно принципу естественного отбора, по которому наибольшие шансы на участие в создании новых особей имеют хромосомы с наибольшими значениями функции приспособленности. Существуют различные методы селекции.
Рассмотрим их.
Основанный на принципе колеса рулетки (жребии) метод селекции считается для генетических алгоритмов основным методом отбора особей для родительской популяции с целью последующего их преобразования генетическими операторами, такими как скрещивание и мутация. Несмотря на случайный характер процедуры селекции, родительские особи выбираются пропорционально значениям их функций приспособленности: каждой хромосоме сопоставлен сектор колеса рулетки, величина которого устанавливается пропорциональной значению функции приспособленности данной хромосомы, поэтому, чем больше значение функции приспособленности, тем больше сектор на колесе рулетки. Отсюда вытекает, что чем больше сектор на колесе рулетки, тем выше шанс, что будет выбрана именно эта хромосома. Слабая сторона этого метода заключается в том, что особи с очень малым значением функции приспособленности слишком быстро исключаются из популяции, что может привести к преждевременной сходимости генетического алгоритма. Кроме того, особенности алгоритма не исключают варианты, в которых потомство субоптимальных особей достигает оптимума в следующиъ поколениях. В связи с вышесказанным, созданы и используются альтернативные алгоритмы селекции.
Турнирная селекция
При турнирной селекции все особи популяции разбиваются на подгруппы с последующим выбором в каждой из них особи с наилучшей приспособленностью. Различаются два способа такого выбора: детерминированный выбор и случайный выбор. Детерминированный выбор осуществляется с вероятностью, равной 1 , а случайный выбор – с вероятностью, меньшей 1. Подгруппы могут иметь произвольный размер, но чаще всего популяция разделяется на подгруппы по 2-3 особи в каждой.
Турнирный метод пригоден для решения задач как максимизации, так и минимизации функции. Помимо того, он может быть легко распространен на задачи, связанные с многокритериальной оптимизацией, т.е. на случай одновременной оптимизации нескольких функций. В турнирном методе допускается изменение размера подгрупп, на которые подразделяется популяция. Исследования подтверждают, что турнирный метод действует эффективнее, чем метод рулетки.
На рисунке ниже представлена схема, которая иллюстрирует метод турнирной селекции для подгрупп, состоящих из двух особей. Такую схему легко обобщить на подгруппы большего размера.
Ранговая селекция
При ранговой селекции особи популяции ранжируются по значениям их функции приспособленности. Это можно представить себе как отсортированный список особей, упорядоченных по направлению от наиболее приспособленных к наименее приспособленным (или наоборот), в котором каждой особи приписывается число, определяющее ее место в списке и называемое рангом. Количество копий каждой особи, введенных в родительскую популяцию, рассчитывается по априорно заданной функции в зависимости от ранга особи. Пример такой функции может быть следующий график.
Достоинство рангового метода заключается в возможности его применения как для максимизации, так и для минимизации функции.
Существуют различные варианты алгоритмов селекции. Представленные выше методы (рулетки, турнирный и ранговый) применяются чаще всего, но существуют так называемые особые процедуры селекции: элитарная стратегия и генетический алгоритм с частичной заменой популяции.
Элитарная стратегия заключается в защите наилучших хромосом на последующих итерациях. В классическом генетическом алгоритме самые приспособленные особи не всегда переходят в следующее поколение. Это означает, что новая популяция не всегда содержит хромосому с наибольшим значением функции приспособленности из предыдущей популяции. Элитарная стратегия применяется для предотвращения потери такой особи. Эта особь гарантированно включается в новую популяцию.
Генетический алгоритм с частичной заменой популяции, иначе называемый генетическим алгоритмом с зафиксированным состоянием, характеризуется тем, что часть популяции переходит в следующее поколение без каких-либо изменений. Это означает, что входящие в эту часть хромосомы не подвергаются операциям скрещивания и мутации. Часто в конкретных реализациях алгоритма данного типа на каждой итерации заменяются только одна или две особи вместо скрещивания и мутации в масштабе всей популяции.
Заметки о генетике 