Документ взят из кэша поисковой машины. Адрес оригинального документа : http://www.abitu.ru/en2002/closed/viewwork.html?work=262 Дата изменения: Fri May 5 15:26:03 2006 Дата индексирования: Tue Oct 2 02:38:28 2012 Кодировка: koi8-r Поисковые слова: ngc 5128

Несколько новых биоподобных L-систем

Калмыков А. В.
Член-корр. Физтех-Академии
Лаборатория компьютерной бионики,
Пущинская средняя общеобразовательная школа РАО,
142290, город Пущино, Московской области, м-н АБ, дом 24, кв. 229(

Научный руководитель к.б.н. Калмыков В. Л. Институт биофизики клетки РАН,
E-mail: kalmykov@psn.ru

Введение

L-системы иначе называются переписываемыми алгоритмами генерации
математических структур. Данный тип алгоритмов был предложен в 1904 году
математиком Хельгой фон Кох (H. von Kokh) (генерация кривой, огибающей
снежинку). В конце пятидесятых годов Хомский использовал эти алгоритмы для
описания формальных грамматик, а в 1968 году биолог Аристид Линденмаер (по
имени которого и были названы L-системы) использовал генерацию структур на
основе последовательно (итерационно) перезаписываемых правил для
моделирования морфогенеза растений. В 1975 году подобные структуры были
названы Бенуа Мандельбротом «фракталами». L-системы, получающиеся на каждом
из последовательных этапов генерации масштабируются к исходно заданным
размерным ограничениям («чувствительны к окружающей среде»). Главные
свойства графических объектов L-структур - симметрия и фрактальность
(самоподобие). Красота (сложная симметрия) и фрактальность лежат, по-
видимому, в основе мира живого. Логические формулы генерации L-систем могут
рассматриваться как аналог генома. Новые структуры были получены мною в
основном в результате перекомбинирования данных логических формул
генерации. Использовались принципы генетических алгоритмов (кроссинговера).
Применялось также прямое логическое проектирование новых L-систем и
комбинированные подходы.
Актуальность создания новых биоподобных L-систем связана не только с
поисками решения проблем биологического морфогенеза, но и с возможностями
использования биологических идей в информатике. L-системы могут быть
отнесены к «искусственной жизни» (www.alife.org). Эта область воспроизводит
с помощью компьютеров характерные свойства живого. Создаваемые сегодня
системы искусственного интеллекта осваивают последнюю пока еще «чисто
человеческую» функцию - сравнительную эстетическую оценку случайно
генерируемых решений. Создание все новых и новых, все более красивых и все
более биологически подобных L-систем является вкладом в освоение
компьютерами (пока еще с помощью человека) мира эстетики, лежащего в основе
принятия человеком наиболее сложных решений.
Целью работы было создание новых биоподобных L-систем с
использованием принципов генетических алгоритмов.


Оборудование и метод

Использовались компьютеры уровня Pentium I (166 MHz) и бесплатная
свободно распространяемая (с www.rechka.ru) Java-программа моделирования L-
систем - «MKokh». В основе работы программы лежат итерационные
подстановочные модификации исходной формулы так называемой черепашьей
графики. Черепашья графика - это такой способ рисования линий на экране
компьютера. Он состоит в том, что программист как бы управляет движением
черепашки. Черепашка, ползая по экрану, оставляет за собой след. При этом
цель программиста - управлять черепашкой так, чтобы она нарисовала нужную
линию. Команды управления черепашкой просты: сделать шаг вперёд
(обозначается F), повернуть направо (обозначается +), повернуть налево
(обозначается -), сделать шаг вперёд без перерисовки (прыжок, обозначается
B). Вот из этих команд и составляется сценарий построения линии - строка
команд. Величина одного шага и угол одного поворота при движении черепашки
всегда остаются постоянными и задаются предварительно.
Например, F++F++F это равносторонний треугольник, если угол поворота равен
(/3 (т.е. 180(/3).
А вот данные для построения «куста» (формула взята с www.rechka.ru).
axiom = F
newF = -F+F+[+F-F-]-[-F+F+F]
Угол поворота = ( / 8
При последовательном увеличении числа шагов, выполняемых программой с
использованием этого стиля генерации L-систем, получаются развивающиеся
структуры (результат каждый раз автоматически масштабируется к заданному
формату рамки):
|2 итерационных шага |3 итерационных шага |4 итерационных шага |
|[pic] |[pic] |[pic] |

Итерационные модификации исходной формулы черепашьей графики реализуются
как последовательные замены простейших элементов исходной формулы-аксиомы
(элементы «F», «B», «X», «Y») на определенные заданные структуры (так
называемые «новые элементарные элементы» - «New F», «New B», «New X», «New
Y» соответственно), написанные на том же языке. В частности:
new F - логическая формула графики, которая подставляется вместо F на
каждом следующем шаге работы программы.
new B - логическая формула графики, которая подставляется вместо B.
Надо заметить, что программа MKokh может нарисовать график сразу, а может
осуществлять его пошаговое выполнение - тогда новый элемент (например,
очередная ветка «растущего» куста) появляется на экране только после
очередного нажатия кнопки. Это удобно для иллюстрации последовательных
стадий процесса (например, роста и ветвления растения).
L-системы можно создавать логическим проектированием по определенному
задуманному плану. Предварительно проводится расчет углов и проектируются
формулы подстановки фигур в элементы формулы-аксиомы. Такой принцип работы
приводит к более или менее запланированному результату, который в
дальнейшем редактируется для получения наиболее совершенной системы. Пример
такого подхода - работа В.О. Бариновой и автора данной статьи (Баринова и
Калмыков, 2002). Второй метод создания новых L-систем можно назвать методом
генетических алгоритмов. Этот метод был заимствован у живых организмов. Он
включает в себя в основном механизмы кроссинговера. В качестве «хромосом»
(генотипа) L-систем выступают записи формул алгоритмов, на основании
которых происходит генерация графического объекта.

Полученные результаты

Из прототипа «Дерево», взятого из стандартных образцов программы MKokh
приемами генетических алгоритмов мною получены последовательно: Дерево,
Морской ёж, Ветка 1 можжевельника казацкого, Ветка 2 можжевельника
казацкого. Интересно, что превращение «Дерева» в «морского ежа» происходит
при весьма незначительном изменении генома - удаляется один знак - в
подстановочной формуле (См. Табл. 1, рисунки1, 2).

Таблица 1 Последовательность 1-4 графических объектов L-систем, полученных
с использованием принципов генетических алгоритмов
|1 Дерево (прототип взят с www.rechka.ru) |2 Морской ёж (автор А. В. |
|[pic] |Калмыков) |
| |[pic] |
|Axiom: |F |F |
|New F: |-F[-F+F-F]+[+F-F-F] |F[-F+F-F]+[+F-F-F] |
|XY угол pi: |1\9 |1\9 |
|Число шагов: |5 |5 |
| | |
|3 «Ветка 1 можжевельника казацкого» (автор |4 «Ветка 2 можжевельника |
|А. В. Калмыков) |казацкого» (автор А. В. |
|[pic] |Калмыков) |
| |[pic] |
|Axiom: |F-F[-F+F-F]+[+F-F-F] |-[F-F[-F+F-F]+[+F-F-F]]+[F-F[|
| | |-F+F-F]+[+F-F-F]] |
|New F: |-F[-F+F-F]+[+F-F-F]-F[-F+F-F]+[+F-|-F[-F+F-F]+[+F-F-F]-F[-F+F-F]|
| |F-F]-F[-F+F-F]+[+F-F-F] |+[+F-F-F]-F[-F+F-F]+[+F-F-F] |
|XY угол |1\9 |1\9 |
|pi: | | |
|Число |3 |3 |
|шагов: | | |

Семейство L-систем «Лоза» (Таблица 2) возникло как результат свободной игры
с формулами без опоры на конкретный прототип. Однако идея использования
переменных X и Y для получения двумерных L-систем была заимствована из
формул «Кривая Серпинского» и «Ковер Серпинского», «Кривая Гильберта» и
«Кривая Госпера», входящих в состав стандартных образцов программы "MKokh".
Переменные X и Y, а также их подстановки "New X" и "New Y" зарезервированы
в программе для создания трехмерных L-систем. Оказывается, их можно
задействовать и в двумерном моделировании. Отличие между «Клубком лианы» и
«Веточкой лианы» заключается в отсутствии у «Клубка лианы» внешних скобок в
формуле "New Y".

Таблица 2 Семейство L-систем «Лоза»
|5 «Веточка лианы» |6 «Клубок лианы» |
|(автор А. В. Калмыков) |(автор А. В. Калмыков) |
|[pic] |[pic] |
| | |
|Axiom: |FYX |FYX |
|New F: |FFFXYFXY-[FFFXYFXY] |FFFXYFXY-[FFFXYFXY] |
|New X: |Y[[XY]+X]+F[+FX]+XF |Y[[XY]+X]+F[+FX]+XF |
|New Y: |[FFF[[YX]+Y]+F[+FY]+F] |FFF[[YX]+Y]+F[+FY]+F |
|XY угол pi:|1/9 |1/9 |
|Количество |4 |4 |
|шагов: | | |


Обсуждение


Живые организмы можно представить себе как векторные графические
трехмерные анимации, нарисованные молекулами. При этом аналогом генома
служат математические формулы, на основе которых происходит генерация этих
векторных графических систем. С другой стороны и компьютеры могут быть
объектами изучения биологов т.к. и те и другие относятся к специфическому
миру информационных процессов и к миру сложных систем одновременно. Если бы
на Марсе были найдены компьютеры, можно было бы уверенно утверждать, это
след живых существ. Современное научное направление «искусственная жизнь»
(www.alife.org) рассматривает живое независимо от типа элементной базы его
реализации. В качестве аналога фенотипов мною рассматриваются генерируемые
графические объекты. Саму программу можно рассматривать как некий организм,
осуществляющий все подстановки, задаваемые геномом. Все это очень похоже на
наш собственный организм - наш генотип является специфической записью
выполнения ряда подстановок, на основе которых формируется фенотип. Один
тип подстановок продуцирует рибонуклеиновые кислоты, другой тип подстановок
продуцирует белки, «дирижирующие» многими биохимическими процессами в
организме. При этом сам организм выполняет функции программы. Эта аналогия
позволяет создавать новые типы L-систем с помощью таких же модификаций
«генома» (совокупности формул сценария создания L-системы), которые
реализуются в мире живого - т.е. с помощью кроссинговера, дупликаций,
инверсий, включений, выпадений, разрывов и точечных модификаций алгоритмов
их генерации. В современных компьютерных науках совокупность этих приемов
носит название «генетических алгоритмов». Эти же приемы модификации генома
активно используются и в современных генно-инженерных технологиях.
Интересна и обратная аналогия - живые организмы могут рассматриваться как
графические объекты, нарисованные молекулами. Кроме механизма
кроссинговера, метод генетических алгоритмов включает весь набор возможных
способов модификации генома: точечные мутации (замена единичных букв
алфавита, возникновение разрывов), выпадения (делеции) или вставки
отдельных сегментов генетической записи, в том числе и чужеродной для
данного генома (взятой из другой хромосомы, из другого вида организмов или
из формулы другой L-системы), инверсии (перевороты отдельных сегментов),
мультипликации (удвоения, утроения, ...) отдельных сегментов или целых
хромосом. В отличие от логического проектирования L-системы, при котором
она строится предопределенным образом (как результат проектирования),
использование генетических алгоритмов зачастую приводит к неожиданным
результатам. Разработчик (или природа) отбирает из полученных результатов
лучшие и может использовать их для дальнейшего генетического скрещивания. В
данной работе были использованы оба подхода создания новых L-систем, но
предпочтение отдавалось методу генетических алгоритмов. Это предпочтение
связано с тем, что в случае сложных L-систем, предсказание всех возможных
вариантов их дальнейшего совершенствования затруднительно из-за слишком
большого объема переборов. Применение генетических алгоритмов позволяет
идти большими шагами в пространстве возможных структурных переборов и
получать самые неожиданные результаты. Наилучшие полученные результаты
можно «скрещивать» друг с другом, ускоряя достижение искомого результата.
Этот метод можно использовать даже не зная формального языка построения L-
систем. Однако, использование логического проектирования L-систем иногда
необходимо для окончательной доводки полученных результатов.


Заключение

С использованием принципов генетических алгоритмов и логического
проектирования создано 5 новых биоподобных L- систем (систем Линденмаера).
В работе приведены как графические объекты, так и логические формулы этих L-
систем (аксиомы, подстановки, углы поворотов и число итераций перезаписи).
Обсуждается важность данного типа моделирования для решения проблем
биологического морфогенеза и использования биологических идей в
информатике. Данная работа, по-видимому, может быть отнесена к
исследованиям по «искусственной жизни» (artificial life).

Планы дальнейших исследований

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


Литература


1. Баринова В.О. и Калмыков А.В. «Фракталы. Использование фрактальной
графики на уроках биологии», Биология, N27-28; 2002 г., Изд. Первое
сентября http://bio.1september.ru/2002/28/14.htm
2. Kalmykov V.L. (1997) "The Abstract Theory of Evolution of the Living",
in Lecture Notes in Computer Science, Springer Verlag, vol. 1305, pp.
43-51, http://www.stormloader.com/theory/atel.htm

http://www.iteb.serpukhov.su/gentl/atel.htm
3. Lindenmayer A (1968). Mathematical models for cellular interaction in
development I. Filaments with one-sided inputs. Journal of Theoretical
Biology 18:280-289
4. Пайтген Х.-О., Рихтер П.Х. Красота фракталов. М.: Мир, 1993. (1986 -
оригинал) 176 с.

Prusinkiewicz, P. and Hammel, M. (1995) Visual Models of
Morphogenesis: A Guided Tour -
http://www.cpsc.ucalgary.ca/projects/bmv/vmm/intro.html, Department of
Computer Science, University of Calgary
5. Федер Е. Фракталы. Пер. с англ.-М.: Мир,1991.-254с. (Jens Feder,
Plenum Press, NewYork, 1988)