模拟植物生长算法与知识创新的几点思考

第13卷第3期2010年3月管理科学学报JOURNALOFMANAGEMENTSCIENCESINCHINAVo.l13No.3Mar.2010¹1,2(1.杭州电子科技大学管理学院,杭州310018;2.大连理工大学系统工程研究所,大连116024):/DNA0.,(PGSA).PGSA,,DNA(、、、、).:;DNA;(PGSA);:C934:A:1007-9807(2010)03-0087-010随着知识经济的发展,知识创新已成为国家生存和发展的灵魂.自19世纪中叶以来,许多著名学者都对知识创新进行过不同程度的研究,如休厄尔(WilliamWhewell)、马赫(EmstMach)、詹姆士(WilliamJames)和西梅尔(GeorgSimmel)等.其后的学者,如洛伦茨(KonradLorenz)、坎贝尔(DonaldCampbell)、波普尔(KarlPopper)、荷兰德(HollandJohn)等对前人的研究进行了扩展,逐步形成了知识创新的/进化认识论0(EvolutionaryEpistemology),将知识创新发展的整个历程解释为通过特定方式而进行的生物进化,其过程可理解为:已有知识通过其突变(mutation)或重组(re2combination)而引起的变异(variation),形成了大量的知识变种(variants),这些变种知识受到知识使用者的严格选择,幸存(survive)的知识变种被复制、扩散,并逐步成为新的知识体系[1-3].与西方学者不同,东方的一些学者(以日本学者为代表)更注重默会的、隐性的知识及其转化对于创新所发挥的作用[4-6].本文所探讨的/知识DNA的跨域映射0思想是知识/进化认识论0的一种发展./知识DNA0是由/知识基因0衍生出来的概念.基因理论是由美国试验胚胎学家摩尔根创立的,他认为,基因是主要的遗传单位,具有稳定性,在世代传递中表现规律性,并决定遗传性状.英国著名学者道金斯根据基因理论,提出了/思想基因0(ideaGene)的概念.他指出,思想随时间和空间的变化而移植、扩展、再现,这就是/思想基因0.印度学者斯#科#森在道金斯的理论基础上,又提出了信息基因(informationGene)概念,认为有机体通过群体的遗传基因、自然选择、复制精确度、变异来实现进化,而信息则通过信息基因遗传、试错检验、社会形态制约以及变异思想逐渐稳定来实现增长的.我国学者刘植惠将斯#科#森的/信息基因0概念置换为/知识基因0(knowledgegene)概念,知识基因具有稳定性、再现性和逐渐演变的变异性,是人类知识的继承和传递载体.虽然知识基因是知识进化的功能单位,但它在现实中是不能独立发挥作用的,必须通过知识基因之间的有机结合,构成一条有形结构的定理、学说、理论等大分子.¹收稿日期:2007-01-31;修订日期:2009-09-28.基金项目:国家自然科学基金重点项目;国家自然科学基金资助项目(70431001;70371051);中国博士后科学基金资助项目(2005038588).作者简介:李彤(1967)),男,黑龙江哈尔滨人,教授,博士后,Emai:[e-mail]知识DNA就是这种大分子,由知识基因组成的载有遗传信息的知识DNA,是知识遗传与变异的执行机构./进化认识论0所提出的知识遗传和变异理论,决定了新知识与原有知识之间的血统关系,因而也就决定了该理论是研究在近似的知识领域进行模仿和改造的创新过程.本文提出的创新思想,强调创新知识与原有知识之间的非血统性,也就是将现有知识基因所构成的知识DNA,向相差极远的知识领域进行/跨域映射0(而非遗传变异),进而形成新的知识体系.1DNA复杂科学的研究结果表明,系统间存在相似性,且相似性可变,知识创新/进化认识论0的创新思想强调新旧知识DNA之间通过繁殖而在血统上相互关联,它们是在某一领域内按时间顺序而形成的知识进化谱系.然而,与生物进化不同,一种知识DNA除了在相同或近似知识进行遗传和变异外,是否也能向非相关知识领域进行跨域映射(由于不在同一知识体系内,知识之间不存在血缘关系,因此用/跨域映射0取代/遗传变异0)呢?本文试图利用课题组的一项知识创新成果)))模拟植物生长算法为案例,对知识DNA在相差极远的知识领域内所发挥的作用,进行一些总结和思考.1.1DNA知识创新的/进化认识论0,是研究同一知识体系或相似知识体系中不同DNA结构间的借鉴.爱迪生电话的发明过程是知识DNA遗传变异的典型案例.爱迪生电话的知识DNA源自赖斯电话,在赖斯电话中,话筒是由一个椎体、隔膜和一个感应开关组成的(这些结构即是组成/赖斯电话知识DNA0的主要/知识基因0),当一个人对着椎体讲话时,胶棉隔膜发生振动,依在隔膜上的是一个金属杠杆,杠杆的支撑方式使得隔膜上产生的小的振动将会在杠杆的另一端产生大的振动.爱迪生阅读了赖斯电话报告的英译本后,将赖斯的开关(/赖斯电话知识DNA0中的一个/知识基因0)换成他取得专利的液体可变电阻(DNA中一个基因的变异),由于这一液态电阻需要一个电极在盛满水的小瓶里垂直移动,爱迪生将赖斯的杠杆从支点处折弯了90b,但仍然让杠杆产生成比例的运动.爱迪生电话的发明过程可以总结为:将/赖斯电话知识DNA0中的知识基因进行变异,创造品质更加优良的后代)))爱迪生电话.知识DNA的遗传变异过程如表1所示.1DNATable1KnowledgeDNAgeneticvariation通过以上过程可以看出,在产品知识创新中,无论是系列化产品还是个性化变型产品,大都在继承原型产品特性的基础上通过变异实现,但依然保留着原型产品某些相似性.这种创新思路即为知识DNA的遗传变异.1.2DNA知识DNA跨域映射思想是将已有知识DNA向新的知识领域进行映射的创新过程,这种创新的核心在于发现和建立不同领域知识DNA结构之间的内在联系.在我国古代,东汉张衡在5浑天仪注6中说道:/浑天如鸡子.天体圆如弹丸,地如鸡子中黄,孤居于内,天大而地小.天表里有水,天之包地,犹壳之裹黄.天地各乘气而立,载水而浮.,,0这便是天文学理论中著名的/浑天说0.该学说的提出,是知识DNA跨域映射的一个典型案例.对于鸡蛋结构的知识,是人们所熟知的,鸡蛋结构的知识DNA包括3个知识基因(蛋黄、蛋清和蛋壳).张衡将鸡蛋的知识DNA跨域映射到天体结构当中,在映射过程中DNA结构被完整保留下来,而DNA中的所有知识基因在映射过程中全部被新的知识基因所取代(/蛋黄0被/地0取代,/蛋清0被/天表0取代,/蛋壳0被/天0取代),鸡蛋的知)88)管理科学学报2010年3月识DNA经过这一跨域映射过程,就演化成了一种新的天文学的知识DNA.尽管我国古代普遍接受的是/苍天如图盖,大地如棋局0的天圆地方思想,张衡的理论在当时还不能被人们所接受,但从当今的知识体系看,/浑天说0的提出,在天文学理论发展中是一次重大的知识创新.知识DNA的跨域映射过程如表2所示.2DNATable2KnowledgeDNAinter2domainmapping基于以上分析,知识DNA遗传变异更侧重于技术层面的知识创新,而本文提出的知识DNA跨域映射则更侧重于理论层面的知识创新.为进一步阐明这一思想,将模拟植物生长算法(PGSA)的理论体系作为创新案例,解析/知识DNA跨域映射0的具体应用过程,从而对该思想有一个感性和直观的印象.2DNA自然界在长期的发展和进化过程中,已经形成了许多各具特点的自然模式,这些模式正逐步被人们所认识并形成知识,如遗传变异知识、蚂蚁觅食知识、鸟群捕食知识等等.对这些知识不断进行总结并系统化,就形成了众多的知识体系.这些知识体系中蕴藏着重要的知识DNA,这些DNA向优化领域进行映射,对智能算法的发展产生了深远的影响,出现了遗传算法、蚁群算法、粒子群算法等众多现代启发式算法,形成了新的知识DNA.这些算法尽管有各自的特点,但其知识DNA却包含着相同的5个知识基因,基因1:随机初始可行解;基因2:评价函数(常常与目标函数值有关);基因3:邻域;基因4:选择和接受解的准则;基因5:终止准则.这5大知识基因在不同智能算法中均不相同,但由它们组成的知识DNA却具有共同的属性,即随机性、正反馈性、协同性.寻找自然界具有相似基因的DNA结构,并将其作为新的超启发式准则是算法创新的一个重要任务.根据这个思维模式,将植物的向光性知识和生长演绎知识进行了基因提取,进而形成了新的模拟植物生长知识DNA.模拟植物生长知识基因是:1)植物生长细胞(随机初始可行解);2)植物向光性(评价函数);3)L-系统(邻域);4)形态素浓度(选择和接受解的准则);5)新枝生长停止(终止准则).植物系统以上5大知识基因向智能算法领域进行映射,就形成了模拟植物生长算法.将植物生长作为启发式准则应用于求解优化问题,国内外尚未见有相关研究.其知识DNA的跨域映射过程如表3所示.3DNATable3KnowledgeDNAofplantgrowthsimulationinter2domainmapping2.1模拟植物生长算法(PGSA)是本文第一作者在2005年提出的一种以植物向光性机理为启发式准则的智能优化算法[7].该算法是将植物系统演绎模式(L-系统)和植物系统概率生长模式(向光性)向优化领域进行映射和变异的典型应用.PGSA提出3年来,在整数规划、组合优化以及工程技术领域逐渐显示出其突出的稳定性、精确性和全局搜索能力,因而具有良好的应用和推广前景.PGSA的提出和应用,是本文创新思想的)89)第3期李彤等:模拟植物生长算法与知识创新的几点思考实际案例.所谓PGSA,就是将优化问题的解空间当作植物的生长环境,将最优解当作光源,模拟真实植物的向光性机理(形态素浓度理论),建立枝叶在不同光线强度环境下的快速生长的生长演绎方式(L-系统).PGSA的研究重点是建立以生长规则为基础的植物系统演绎方式和以植物向光性理论为基础的概率生长模型,两者结合所形成的优化模式,就是实现人工植物在优化问题解空间中从初始状态到完整形式的终态(没有新的树枝生长)的过程.2.2植物可看作由大量枝、节组成的系统,模拟植物的生长演绎方式是A.Lindenmayer在20世纪60年代末把乔姆斯基的生成转换语法引入生物学,以简单的重写规则和分枝规则为基础,建立了关于植物的描述、分析和发育模拟的形式语法,称为L-系统.对植物生长作形式化描述,可以根据以下几点进行:1)破土而出的茎杆在一些叫做节的部位长出新枝;2)大多数新枝上又长出更新的枝,这种分枝行为反复进行;3)不同的枝彼此有相似性,整个植物有自相似结构.用L-系统描述生长的基本概念如图1所示.1L-Fig.1L2systemfractiongrowthprocess图1为复合类萝卜叶模型.该模型操作两类模块:顶和节.在第一次繁殖中,由顶生成继续其主轴线的一个主顶、两个侧顶和两个节.在第二次繁殖中,经过一定时间间隔,节增长两倍,如此循环,形成植物.20世纪80年代,P.Prusinkiewicz等人把L-系统与计算机图形学、分形学结合起来,完善了植物生长的分枝模型.在所规定的生长规则的反复重写下,可作出如图2所示的分形生长树图(取自普鲁森科维奇专著).2Fig.2FractaltreesPGSA以L-系统作为人工植物的生长演绎方式的源模式,生长点即植物生长细胞,是模拟植物系统每一次生长的位置点.植物生长过程是在生长点按2n(n为变量的维数)个方向生长并产生新枝,分枝长度在整数规划情况下设定为1(非整数规划情况下可根据精度要求选取).按照L-系统完成的人工植物结构,仅解决了模拟植物生长的演绎问题,其关键问题还没有解决,即在众多生长点中,每一次到底确定其中哪一个进行新的生长,怎么保证树枝向最优解方向生长,其核心问题就是植物向光性特点的算法实现问题.2.3植物向光性涉及生物学理论中的形态发生模型,该模型是用复杂动力系统为生物生长建模的著名例子,模式的形成被理解为复杂过程,其中一个细胞发生分化,产