1.3. Преимущественное право размножения сильнейших

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

С другой стороны, индивидуальная приспособленность особи оказывает прямое влияние на будущее популяции. Чем больше потомков данной особи доживет до репродуктивного возраста, тем большее число членов популяции будущего поколения будет нести ее аллели. «Приспособленность, рассматриваемая как мера влияния генотипа на будущее, — пишет Холланд в [1], — представляет идею, полезную во всем спектре проблем адаптации. Хороший способ рассмотреть эту идею в более широком контексте, это рассматривать тестирование генотипов как процедуру формирования

выборок (под выборкой — sample — Холланд подразумевает текущую популяцию — Прим.авт.). Пространство выборок в этом случае представляет собой набор всех генотипов а, а результатом оценивания каждой структуры становится приспособленность соответствующего фенотипа. Общий вопрос, связанный с приспособленностью, звучит так: «В какой степени оценка какой-либо структуры оказывает влияние или изменяет план формирования новой выборки?» Оглядываясь назад скорее чем вперед, мы сталкиваемся с другим взаимосвязанным вопросом: «Как история результатов тестирования предыдущих выборок оказывает влияние на текущий план формирования новых?» Ответы на эти вопросы уходят далеко к определению того, что составляет основу любого адаптивного процесса.»

«Мы уже видели, — продолжает Холланд, — что ответ на первый вопрос, что касается генетических систем, состоит в том, что будущее влияние каждой особи прямо пропорционально оценке приспособленности Вообще, это отношение не обязательно — существует много

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

Таким образом, как мы видим, отличительной чертой репродуктивных планов Холланда является право более приспособленных дать большее количество потомков.

Любопытно, но при условии неизменной численности популяции (а в компьютерном моделировании эволюции это условие невозможно игнорировать) применение принципа преимущественного размножения более приспособлению приводит к несколько неожиданному результату — в популяции размножаются как бы не сами особи, а гены. По существу, это эквивалентно понижению уровня рассмотрения системыг: мы оперируем не особями, а генами. Геныг борются друг с другом за выживание, сильныге вытесняют из генофонда популяции слабыю.

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

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

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

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

Рис. 5. Преобразование наследственной информации в ГА

Репродуктивный план Холланда

(см. скан)

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

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

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

Где же проходит сегодня граница разумной сложности задачи? Наверное, все определяется тем, какими ресурсами мы располагаем — персональной РС386 или транспьютером Т64000. Часто называют более определенный критерий — задача должна быть решена за одну ночь работы компьютера уровня Pentium-100.

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

(кликните для просмотра скана)

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

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

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

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

К сожалению, мы почти никогда (за исключением аналитически сконструированных тестовых задач) не можем с уверенностью утверждать, что найденное решение представляет собой глобальный экстремум. Фенотипическое и генотипическое вырождение популяции является необходимым, но не достаточным признаком успешности поиска. Оно только свидетельствует, что какой—то экстремум найден, но ничего не говорит о том, каков его характер. Тем не менее, нам не остается ничего другого, как довольствоваться достигнутым результатом. В противном случае лучше повторно запустить задачу в надежде на более благоприятное развитие событий, чем ждать чуда от истощенной популяции. Эволюция неповторима и при новом сочетании случайных факторов решение может оказаться более привлекательным.