《模拟植物生长算法原理及应用》系统地介绍了模拟植物生长算法的基本理论及其在各领域的应用。模拟植物生长算法是《模拟植物生长算法原理及应用》作者提出以植物向光性为启发式准则的原创性智能优化算法。《模拟植物生长算法原理及应用》共分七章：引论；丢番图方程的求解；整数规划；二层规划问题；模拟植物生长算法在管理科学中的应用；模拟植物生长算法在工程技术中的应用。目前模拟植物生长算法已经被国内外几百位学者所应用，经过十年的发展，该算法已成为各领域学者解决优化问题的一个实用、高效、可靠的工具。

第1章引论1
1.1智能计算与植物生长1
1.2植物向光性机理2
1.3植物向光性的概率生长模式3
1.4植物生长的演绎方式5
1.5多向生长的模拟植物生长算法收敛性7
1.6模拟植物生长算法的历史及发展8
1.7模拟植物生长算法创新的方法论基础13
参考文献17
第2章斯坦纳最小树问题22
2.1费马问题22
2.2斯坦纳最小树24
2.3斯坦纳比猜想26
2.4斯坦纳最小树问题的模拟植物生长算法28
2.5数值试验29
2.6地下物流网络优化的斯坦纳最小树31
参考文献47
第3章丢番图方程的求解50
3.1丢番图生平50
3.2丢番图的著作52
3.3丢番图方程54
3.4丢番图方程及其求解55
参考文献58
第4章整数规划60
4.1引言60
4.2模拟退火算法及其整数规划算法61
4.3遗传算法及其整数规划算法74
4.4整数规划的模拟植物生长算法85
参考文献92
第5章二层规划问题94
5.1二层规划94
5.2线性二层整数规划的算法96
5.3非线性二层整数规划的全局算法100
5.4二阶混合整数规划问题的全局最优算法104
5.5一类非线性两阶整数规划的近似算法111
5.6求解二层规划的模拟植物生长算法116
5.7制造企业与物流企业二层共生优化问题120
参考文献125
第6章模拟植物生长算法在管理科学中的应用128
6.1非常规突发事件的模拟植物生长演化128
6.2技术联盟投资决策优化139
6.3协作研发网络的模拟植物生长优化145
6.4多目标旅行商问题的模拟植物生长算法求解153
6.5模块化制造单元资源配置的模拟植物生长优化158
参考文献160
第7章模拟植物生长算法在工程技术中的应用166
7.1模拟植物生长算法在机械设计领域的应用166
7.2大型辐照装置自动排源171
7.3多项目资源均衡问题174
7.4电子装备备件优化配置177
7.5联合战役野战油库部署多目标优化179
7.6模拟植物生长算法在其他领域的应用183
参考文献190
后记192

精彩书摘

第1章引论
1.1智能计算与植物生长
从系统动力学的观点看，优化问题的求解过程，相当于在问题的解空间内从一个初态向吸引子不断演化的过程。就像江河湖泊都有自己的流域一样，每一个吸引子在相空间内也都有各自的流域（吸引域）。当优化问题有唯一最优解时，相当于解空间中只有一个吸引子，此时整个可行域解空间都是这个吸引子的吸引域，然而，复杂问题往往具有多个甚至无穷多个全局和局部最优解，这意味着在解空间中同时存在多个吸引子，优化过程向哪个吸引子演化，取决于初态落在哪个吸引域，这个特点是若干贪婪算法陷入局部最小点而无法得到全局最优解的根本原因。
针对以上问题，近年来智能计算取得了令人瞩目的成绩［1，2］，其成功之处在于，自然计算模拟自然界特别是生物群体对环境的自适应优化模式，建立随机性、正反馈性、协同性等能够跳出局部最小点的动力模型。在众多的自然计算中，算法启发准则逐步形成了生命、生物及生态系统（遗传算法、蚁群算法、粒子群算法、细菌觅食算法、神经计算、DNA算法等），物理系统（模拟退火算法、量子计算、混沌优化、晶体生长算法）与化学系统（分子计算、化学反应计算）等。智能算法近期的研究成果是日本学者Tero 等于2010 年1月在Science上发表了使用黏菌( slime mold，俗称鼻涕虫)的行为机理，设计连通东京及其附近城市的铁路网的研究成果。
在如此多的现代启发式算法中，对于植物向光性这种地球上最为古老和成功的植物生长优化模式，还没有给予充分的重视。拉什夫斯基和图林等的植物生长形态发生模型及林登迈耶和普鲁森科维奇等的植物生长分枝模型，主要是针对计算机图形学及分形学领域的问题，将植物生长动力学机制应用于解决优化问题，目前尚处于初始阶段。
1.2植物向光性机理
向光性是植物重要的生态反应，其机理至今仍未完全揭示和证实。高等植物受到不同方向的环境刺激而引起的趋向反应叫做向性(tropism)运动。向性运动（tropic movement）主要是单向刺激引起植物体内的生长素(indole acetic acid，IAA)和生长抑制剂(abscisic acid，ABA)分配不均匀造成的。其运动方向与刺激的方向有关。凡运动方向朝向刺激一方的为正向性，背向刺激一方的为负向性。向性运动的种类与环境影响的种类有关。环境影响包括光、接触、重力、水分、化学物质、温度与电流等，分别称做植物的向光性、向重力性、向水性和向化性。
其中光是对植物调控作用最广泛、最明显的环境因子。光作为环境信号，对植物的器官发生、形态建成、向性运动等都有深刻的影响。向光性是植物为了捕捉更多的光能而建立起来的一种对不良光照条件的适应机制，是植物最重要的向性运动机制。植物通过光信号受体和光信号传导途径来接受和转导光强、光质、光照方向和光周期等光信号并做出相应的反应。
早在1880年，达尔文就发现金丝雀绶草(phalaris canariensis)幼苗胚芽鞘在单向光下生长时，就会产生明显的向光性弯曲。这一发现引起了许多学者的关注及研究兴趣，植物向光性研究目前仍是植物向性研究领域的热点课题。
20世纪20年代末，Cholodny和Went 各自发现，在单侧蓝光的作用下，植物中的生长素向背光侧移动。基于这一实验，他们提出假说认为，光能够刺激生长素向背光侧运输，使背光侧的生长素浓度高于向光侧，继而使背光侧的生长快于向光侧，引起植物弯曲。后来，Leopold 等经试验证明，光能够大大刺激生长素从玉米胚芽鞘的向光侧向背光侧运输。Iino也证实，光可以引起植物向光侧和背光侧生长素的分布不均匀。尽管国外对植物向光性做了大量的研究，但目前光信号是如何引起植物生长素信号转变的机制尚不完全清楚。
关于植物向光性反应的机理有两种假说，一种是Cholodny-Went假说，另一种是Bruinsma-Hasegawa 假说。
（1）Cholodny-Went假说。1928年Went用生物测定法显示生长素活性的分布比率为向光面32%，背光面68%。Cholodny和Went以燕麦胚芽鞘为材料研究发现，在单侧蓝光作用下，IAA向胚芽鞘的背光侧移动。根据这些结果Cholodny和Went认为，植物的向光性反应是由于光照后引起生长素浓度的差异分布而引起的。对于胚芽鞘的正向光性则是在光照下背光侧的生长素浓度大于向光侧生长素的浓度，而使背光侧细胞的生长大于向光侧从而导致茎叶向光弯曲。1990~1991年，Iino以玉米为材料，对玉米胚芽鞘向光侧和背光侧的内源生长素含量变化进行了分析，证实了单侧蓝光引起生长素分布不均匀，从而使胚芽鞘产生向光弯曲，这些结果都支持了Cholodny-Went 假说。
（2）Bruinsma-Hasegawa假说。Bruinsma-Hasegawa假说也称为抑制剂分布不均匀假说，其是于1990年由Bruinsma和Hasegawa共同提出的，他们认为植物向光性形成的原因是由于生长抑制物在向光侧和背光侧分布不均而引起的。Bruinsma和Hasegawa以向日葵(helianthus annuus)幼苗为材料研究植物向光性运动特性时，发现单侧蓝光处理并没有引起生长素分布不均匀。Hasegawa等用液相色谱法从黄化萝卜下胚轴中分离出萝卜宁(raphanusanin)和萝卜酰胺(raphanusamide)等中性抑制物，他们用萝卜宁和萝卜酰胺单侧处理萝卜下胚轴抑制了胚轴处理侧的生长，使下胚轴向处理侧弯曲，他们认为向光性弯曲是由于光诱导了生长抑制物的合成，胚轴的生长受到抑制从而产生向光性弯曲。
1.3植物向光性的概率生长模式
植物向光性现象被揭示后，不断有科学家对其进行深入研究，其中植物的概率生长模式是主要研究方向之一。植物概率生长涉及生物学理论中的形态发生模型，该模型是用复杂动力系统为生物生长建模的著名例子，模式的形成被理解为复杂过程，其中一个细胞发生分化，产生出新的明确定义的空间结构。形态发生最初的动力学模型是拉什夫斯基、图林等提出来的。他们关于植物生长形态发生（叶序）模型如图1-1所示，葡萄茎梗发出一个枝芽的某一时刻，它出现在对于3个枝芽对称旋转的方向（模拟植物生长算法将旋转方向定为90°，也可根据实际问题设定为其他角度）。在生长中的茎梗的顶部，生长出来一个芽，包含着未分化的细胞。叶序问题涉及作为叶芽细胞、分枝细胞和其他导致叶芽和分枝的分化细胞的生长模式的形成。一个细胞被看做一个流体袋，其中有均匀的化学组分，其中的一种化学组分是生长激素，叫做形态素。这种形态素的浓度x是此模型的观察参量，随着参量在0和1之间变动，模型的状态空间是一条线段（图1-2）。这种形态素的浓度决定细胞的生长函数是否开始起作用，即细胞分裂，枝芽开始出现。
图1-1拉什夫斯基叶序模型
图1-2单细胞形态素浓度及状态空间
新的生长点（细胞）产生后，形态素浓度将根据新系统所在环境的改变，重新进行分配。在多细胞系统中，如果把任意一个细胞形态素浓度记为Pi(i=1，2，，n)，则多细胞封闭系统形态素状态空间见图1-3，且浓度和是恒定的（设定为1）。生物学实验已经证明，决定植物细胞分裂和枝芽生长的生长素信息（形态素浓度）并非是一个个预先赋予细胞的，而是细胞系统从其环境中接收到了它的位置信息，依据这种信息，植物表现出明显的向光性特点。模拟这一过程，设有n个初始生长点Si=（S1，S2，，Sn），每一个生长点的形态素浓度为Pi=（P1，P2，，Pn），各生长点形态素浓度是由各点的相对位置及该位置的环境信息（目标函数值）所确定，这与真实植物细胞的形态素浓度生成机理相一致。因此，n个生长点均对应n个形态素浓度值，每次产生新枝，该浓度值都将发生变化。形态素浓度可表示为
图1-3形态素浓度概率空间
F为优化问题初始基点（树根）目标函数值，为各生长点目标函数值，容易证明P1+P2+ +Pn =1，因此其概率空间如图1-3所示。计算机系统不断产生随机数，这些随机数就像不断向区间[0，1]上投掷的小球，小球落在P1，P2，，Pn的某一个概率空间内，所对应的生长点就得到优先生长的权利［3，4］。
1.4植物生长的演绎方式
植物的向光性理论解决了人工植物的概率生长问题，而植物在空间中的拓展和演绎方式则需要借鉴L-系统的相关研究。植物可看做由大量枝、节组成的系统，虚拟植物可以应用计算机模拟植物在不同维度空间中的生长发育状况。其主要特征是以植物个体为研究中心，以植物的形态结构为研究重点，以可视化的方式反映植物的形态结构规律，生成具有真实感的植物个体或群体。模拟植物的生长演绎方式是A.Lindenmayer在20世纪60年代末把乔姆斯基的生成转换语法引入生物学，以简单的重写规则和分枝规则为基础，建立了关于植物的描述、分析和发育模拟的形式语法，称为L-系统。对植物生长做形式化描述，可以根据以下几点进行：①破土而出的茎秆在一些叫做节的部位长出新枝；②大多数新枝上又长出更新的枝，这种分枝行为反复进行；③不同的枝彼此有相似性，整个植物有自相似结构。图1-4为L-系统分形生长过程。该模型操作两类模块：顶和节。在第一次繁殖中，由顶生成继续其主轴线的一个主顶、两个侧顶和两个节。在第二次繁殖中，经过一定时间间隔，节增长两倍，如此循环，形成植物。
图1-4 L-系统分形生长过程
20世纪80年代，P.Prusinkiewicz和A.Lindenmayer把L-系统与计算机图形学、分形学结合起来，完善了植物生长的分枝模型。在所规定的生长规则的反复重写下，可做出如图1-5所示的分形生长树图[5]。
图1-5分形生长树图
植物的形态结构，即植物在不同维度空间的占据方式，决定植物的竞争能力和资源获取强度。枝叶的空间分布状态对光辐射截获量的影响，决定了当前功能的行使如光合作用、蒸腾等光合产物的积累与分配。反过来功能的行使又决定其各部分的生长速率，从而决定下一时段植株的形态。植物的生长过程就是由许多个这样的循环构成，植物的形态结构在其中占据着重要位置，该方面的研究对明确植物的生长规律具有重要的理论意义。