Эволюционное моделирование. Проблемы формы и содержания

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

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

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

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

Фенотип. Роль фенотипа в ГА сводится исключительно к возможности оценки качества особи. В ГА фенотип особи определяется как точка, принадлежащая гиперкубу пространства поиска соответствующего генотипа. А отсюда следует взаимно однозначное соответствие между генотипом и фенотипом особи. Причем этот факт нисколько не смущает «генетических алгоритмистов», напротив, о нем говорится как о неотъемлемом, центральном свойстве ГА.

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

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

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

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

Беда в том, что при таком подходе выпадают важнейшие факторы эволюции как таковой.

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

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

Роль мутаций в ГА. Главная роль в процессе «видообразования» в ГА принадлежит кроссинговеру. Мутации носят лишь вспомогательный, дополнительный характер. Однако совершенно очевидно, что в природе перекрестное «перемешивание» 60 тыс. генов, суммарная длина которых составляет более 90 млн. нуклеотидов, вряд ли позволит без случайных мутаций получить столь разнообразные даже внутривидовые отличия, какие имеются, скажем, в человеческой популяции.

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

Но самое главное, что происходит ничем не обоснованный перенос «ДНК-подобного» механизма, механизма полового размножения с «высших» организмов на предельно примитивные формы - строки хромосом в ГА или деревья в генетическом программировании. Впрочем, пусть о достоинствах и недостатках партеногенеза и полового размножения спорят биологи.

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

Заключение

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

Рассмотренная выше модель особи в виде модифицированного конечного автомата вряд ли может считаться наиболее эффективной и/или бесспорно предпочтительной. Просто это очень хороший пример объекта, который, во-первых, достаточно прост и формален, а во-вторых, позволяет очень легко и естественно реализовывать практически все эволюционные механизмы. Например, то же старение организма и его «естественная» смерть может осуществляться путем введения штрафа, зависящего от количества состояний автомата. А создание более сложных организмов может легко быть осуществлено как за счет мажоритарной логики, так и путем перекоммутации входных/выходных сигналов.

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

Литература

1. Букатова И.Л., Михасев Ю.И., Шаров А.М. Теория и практика эволюционного моделирования. -М.: Наука, 1991. -206 с.

2. Варшавский В.И., Поспелов Д.А. Оркестр играет без дирижера: размышления об эволюции некоторых технических систем и управлении ими. - М.:Наука. Гл.ред. физико-математической литературы, 1984. - 208 с.

3. Горбань А.Н. Обучение нейронных сетей. - М.:СП ПараГраф, 1990, -159с.

4. Горбань А.Н., Хлебопрос Р.Г. Демон Дарвина. Идея оптимальности и естественный отбор. -М.:Наука, 1988. -208 с.

5. Дунаев Б.Б. Математическая модель эволюции биологических популяций. //Кибернетика, N 1, 1990. с.107-111.

6. Животовский Л.А. Наследование приобретенных признаков: эволюция по Ламарку-Дарвину. Первое международное рабочее совещание «Биоразнообразие и динамика экосистем Северной Евразии: информационные технологии и моделирование» (WITA-2001), Новосибирск, Россия.

7. Завадский К.М. К проблеме прогресса живых и технических систем. - В сб.: "Теоретические вопросы прогрессивного развития живой природы и техники". - Л.:Наука, 1970, с. 3-28.

8. Тихомиров О.К. Эвристика человека и машины. - Вопросы философии, 1966, №4

9. Фогель Л., Оуэнс А., Уолш М. Искусственный интеллект и эволюционное моделирование. -М.: Мир, 1969. -230 с.

10. Фогель Ф., Мотульски А. Генетика человека: в 3-х т. Т.2: Пер.с англ.-М.:Мир, 1990. -378 с.

11. Фокс Р. Энергия и эволюция жизни на Земле: Пер.с англ. -М.:Мир, 1992, 216с.

12. Фор А. Восприятие и распознавание образов /Пер. с фр. - М.:Машиностроение, 1989. -272 с.

13. Цетлин М.Л. Исследования по теории автоматов и моделирование биологических систем. -М.:Наука, 1969. -316 с.

14. Шмальгаузен И.И. Факторы эволюции. -М.:Наука, 1968. -451с.

15. Шмальгаузен И.И. Кибернетические вопросы биологии. Новосибирск: Наука, 1968, -224 с.

16. Baldwin J. M. Development and Evolution. New York, London, Macmillan, 1902

17. Fogel L. a.o. Artificial intelligence through simulated evolution. New York, Wiley, 1966.

18. Fogel L. a.o. Adaptation of evolutionary programming to the prediction of solar flares. CR-417. Washington, 1966.

19. Goldberg D.E. Genetic Algorithms in Search, Optimization, and Machine learning. Addison-Wesley, 1989.

20. Holland J.H. Adaptation in Natural and Artificial Systems. Ann Arbor: The University of Michigan Press, 1975.

21. John R. Koza. “Genetic Programming: On the Programming of Computers by Means of Natural Selection”. MIT Press, Cambridge, Massachusetts, 1992.

22. Mitchell M. An introduction to Genetic Algorithm. MIT Press, 1996.

Размещено на Allbest.ru