用L-systems和遗传算法实现的叶子形状建模

第30卷．第1l期 VoL30№jl 计算机工程 ComputerEngineering 2004年6月 June2004 ‘多媒体技术及应用· 文章螭号l1000—3428(2004)11—m13}枷3文献标识码：A 中圈分类号lTP306 hIL—systems和遗传算法实现的叶子形状建模 吕慧强。，事益嘲2，孔鬟雎 (I浙}工工业大学多媒体与虚拟现实研究所，杭州310032；2温州大学多媒体与虚拟现实研究所，温州325027) 摘要：阐述了组合两类技术的一种方法：用L-systems}ff遗传算{击(GA)获取一种改写表达式描述叶子形状。一个L-systems用于构造给定 改写表达式，而GA是用于改写表达式的适应参数。介绍了用目标函数实现实值参数替换方法，研究结果表明提出的方法产生可以接受的输 出效果。 关量菌：L-system；遗传算法(GA)；叶子；建模 ModelingoftheLeafShapesUsingL—systemsandGeneticAlgorithms LVHuiqiang’，LIYimingz，KONGFanshen窖 (I InstituteofMultimediaandVisualReality，ZhejiangUniversityofTechnology，tlangzhou310032； 2 fnstituteofMugimediaandVisualReality，WenzhouUniversily，Wenzhou325027} [AbstractIThispaperpresentsamethodthatcombinestwotechniques：L-systemsandgeneticalgorithmsrGAltosearchfo*arewritingexpression describingleafshapesAnL-systemisusedtocons”ucttheshapeofagivenrewritingexpressionandGAisusedtosearchfortherewritingexpression’s fittingparametersThereplacementofrealvalueparameterswithtag-lhnctionsisintroducedTheresultshowsthattheprop(Hedmethodproducesan acceptableoutput [KeywordslL-systems；Geneticalgorithms(GA)；Leaf；Modeling 本文的目的在于为一片叶子网络寻找一个改写表达式 (图1)。这种方法力图用一个给定的表达式构造一个基本的 分支网络，叶子形状可以通过人为修改参数来改变”l。尽管 如此，要人去修改参数是困难的，因为有太多的参数需要修 改。本文提出～种方法，用GApI构造一个基本分支网络以及 解决参数自动匹配的问题。 《黼 圉I叶子卉形状和叶子两络 1 L—systems 从文献[I】可以看出， ·个带属性的L-systems是一个上 F文无关文法，它是定义在参数字上的运算，参数字由字母 和参数组成的串，称为语义模块。有限字母的集合记作V，有 限参数集合记作R。每一个语义模块属于集合M=V×R_，其 中R+是R上的任意正规式集合。所有模块串的集合表示为M+ =(vxR‘)’，即M+是(V×R’)上任意的正规式集合以及 所有非空语义模块串集合表示为M+=(VxR‘)‘。实值实参与 形参字对应，当然形参出现在文法的规则中。一个参数化L— systems定义成四元组G=(V，E，￡，P)，其中： V是系统字母表； E是形参的集合； ￡∈(V×R’)’是非空参数字，称为文法识94字； PE(V×E‘)是有限规则的集合。 系统可以包含带有形参的逻辑表达式和算术表达式。 例如，设系统字母表为{F，R}，系统中F和R可以在一个 串中出现任意多次。每个字母对应一条改写规则。规则F 一132一 _+FRF表示F用FRF代替成为串FRF。改写处理推导从初始 符号开始，设初始符号为F删由F町以推出无限的语义解释。 1．1L．systems的绘图执稍 在L—systems中，绘图是基于龟的爬行图形。龟的状态 定义为一个三元组(x,y，a)，其中笛卡尔坐标(x,y)表示龟 的位置，晾示龟的爬行方向。一步尺寸为13，一个增量角度 6。在图2中，给定萨5．0，6=900。。符号F表示“向前”一 步，符号L表示“左转”6角度，符号R表示“右转”6角 度。如串FRFRFRF画一个矩形(图2(b”。符号[和】表示’ 个堆栈操作。符号[把当前的(x,y，a)压进堆栈，符号]弹出 堆栈顶部的(x,y，a)，同时把这当前的三元组(x，Y，a)(如豳2 (c))进行处理。 (a)龟状态(b)从串FRllRFRF获得的图彤 (c)从串F[LFRI‘】【RFLFIF获得的图形 图2 L—systems帕绘图机村 1．2参熬字 一个或多个参数可以与一个符号关联。如果F表示向 前，那么F(5)表示向前5个像素。 Ha)向前移动Ⅱ像索； R(a)右转Ⅱ角度；． 基金项目：浙江省自然科学基金资助项目(602002) 柞者倚介：吕慧强(1961一)，男，讲师，研究方向为多媒体与虚拟 现实计算理论；李益明，副教授；孔繁胜。教授、博导 收稿H期：2003-05-19E-mail：huiqianglu@hzcnccorn 万方数据 L(a1左转a角度 用户可以自己定义一个新的参数规则。用一个算术表达 式￡(E)，下面的定义在L-systems中有效： ￡：A斗Bfll PI：B(a卜·C(aa+¨ P2：C(a，b)_．B(a)C(b，a曲) 第J次推导结果是C(1,2)，第2次推导的结果是B(1)C(2， 3)，第3次推导的结果是C(1，2)B(2)C(3，5)，第4次推导结果 是B(1)c(2，3)C(2，3)B(3)C(5，8)。 1．3目标函数 参数字需要推导得出；符号和参数变化取决于L— systems产生规则。然而，必须认识到构造适当的产生规则 生成真实叶子形状的确非常难。也就是说，单纯用12节的 描述表达方式是难以实现叶子模型的。因此本文引入目标函 数替代参数。 ·个目标函数可以有任意适应度的功能。另 外，一个目标函数可以诚少计算复杂度，因为它重复替换推 导是通过存储目标函数表；因此它可以重用参数值的计算。 当然，若没有一个初始推导规则约定的话，用户可以改变一 个函数值。 本文使用的目标函数描述如表1。在一个串中，一个目 标函数以符号<开始，以符号>结束，如，从语法分析角度而言在一个推 导阶段有一个句型。 袁1目标函t 目标函数 含义 输出范围 v=S(n) 左转P(n)角度 (0驴 右转Q(m角瘦 v=G(m) II：fTILII¨P2a／．!I"’ 一k篇ILfl“n”．|。*“(2t。'；‰，。(Dmn> 、t^tll¨5Htf 左转e角度 ．但是右转e角度 田3从日标西藏封●藏翻转换 非终结符号L，R分别表示左转6，右转6和向前B，描述如 1 1节。常量6，13由用户指定。表1中符号v表示一个步长为 p的标量值。这意味符号F指示龟向前(v×B)像素。目标函 数D和E定义成线性插值L．，L：，和b。终结符号!表示一个状 态复位。 在这个方法中，确定7个函数S，P，Q，G，b，k和b很重要， 以便产生一个良好的叶子形状。以下，为方便起见本文用术 语“目标函数”表示这7个函数，尽管L．，k和k不是真正意 义上的目标函数。第2节中将描述获得适应函数的方法。 1．4实验的删定义 在本文的实验时，下面的文法用于产生叶子形状： ∞：A_LM州 PI：M呻【BBBBBBBBBBB] P2：N_+fCCCCCCCCCCC] P3：B呻F[H】 P4：c斗F[q P5：H叶L

J P6：hR㈣QG>K P7：J斗(DS>K 推导8次的序列如下。 第1次：L[BB·B】。[Ccc】 第2次：L[F【H】F[H]F[HJ]![FI[IF[I]F[啪 第3次：L[F[LJlF[LK1F【R‘q><0，>K卜FIR(Gl>‘s|>卟】’ 吼R‘q>(Gl>KJ】 第5次：L[F[L(s4>“I)J1]’ IF[R“l>KI】 第8次：“ 上面目标函数下标值表示为n和m。当给定目标函数作 为参数值，这些值在f0，I】上是正态分布的。例如，设计

领导形象设计圆作业设计ao工艺污水处理厂设计附属工程施工组织设计清扫机器人结构设计