（道路与铁道工程专业论文）基于遗传神经网络的建筑工程快速估价研究.pdf

摘要基于遗传神经网络的建筑工程快速估价研究摘要长期以来，我国的建筑工程项目存在严重的概算超估算，预算超概算，决算超预算现象，使得工程造价不断提高。造成这种现象的一个重要原因就是我国普遍忽视工程项目前期的投资控制，对工程投资估算没有一个快速准确的计算方法使得投资估算误差太大。针对如何快速准确的得出工程投资估算，本文进行了较详细的研究和探讨。本文首先对遗传算法以及人工神经网络理论进行了介绍，然后分析现有快速估价模型的优缺点，提出用遗传算法的全局搜索性来弥补b p 神经网络的局部极小缺陷，建立基于遗传神经网络的建筑工程快速估价模型。模型首先利用遗传算法对b p 神经网络的权值和阈值进行全局搜索将误差降低在一定的范围内，然后利用b p 神经网络的局部收敛性来对网络进行训练最终得出预测结果。文章最后利用m a t l a b 语言将该模型在计算机上编程实现，将大量的已有工程造价作为训练样本输入模型，根据输出结果对模型进行检测，证明该模型具有较快的速度和较高的准确度。关键词：投资估算，快速估价，遗传算法，神经网络a b s t r a c tf a s te s t l m a t l o nr e s e a r c ho fc o n s t r u c t i o ne n g i n e e r i n gb a s e do ng e n e t i cn e u r a ln e t w o r ka b s t r a c tt h ep h e n o m e n ao fc o s t i n ge x c e e d i n ge s t i m a t e ，b u d g e te x c e e d i n gc o s t i n g ，a u d i te x c e e d i n gb u d g e th a sb e e ne x i s t e di nc o n s t r u c t i o ni n d u s t r yf o ral o n gt i m e ，w h i c hm a k e st h ec o n s t r u c t i o nc o s te s c a l a t e t h em a i nr e a s o n sa r et h a tw ea l w a y sn e g l e c tt h ec o n t r o lo fi n v e s t m e n ti nt h ep r i o rp e r i o do fac o n s t r u c t i o np r o j e c ta n dw ed o n th a v eaq u i c ka n de x a c tc o m p u t a t i o nm e t h o d ，w h i c hr e s u l t so v e r - e s t i m a t e i no r d e rt of a s ta n da c c u r a t e l ye s t i m a t et h ec o s to fap r o j e c t ，t h er e s e a r c ha n dd e t a i l e dd i s c u s s i o na b o u tt h ec o s te s t i m a t eh a sb e e nd o n ei nt h i sp a p e lt h eg e n e t i ca l g o r i t h ma n da r t i f i c i a ln e u r a ln e t w o r kh a v eb e e ni n t r o d u c e da tf i r s ta n dt h e nt h ea d v a n t a g e sa n dd i s a d v a n t a g e so ff a s te s t i m a t i o nm o d e lh a v eb e e nd i s c u s s e di nt h ea r t i c l e t h ef a s te s t i m a t i o nm o d e lo fa r c h i t e c t u r ee n g i n e e r i n g ，w h i c hu s e st h eg l o b a ls e a r c hq u a l i t yo fg e n e t i ca l g o r i t h mt oi m p r o v et h el o c a lm i n i m u mf a u l to fb pn e u r a ln e t w o r kh a sb e e np u tf o r w a r d b a s e do ng e n e t i cn e u r a ln e t w o r k ，t h ef a s te s t i m a t em o d e lw a se s t a b l i s h e d f i r s t l yt h em o d e lu t i l i z et h eg l o b a ls e a r c hq u a l i t yo fg e n e t i ca l g o r i t h mt ol o w e rt h ee r r o rw i t h i nc e r t a i nl i m i t s ，s e c o n d l yu t i l i z et h el o c a lc o n v e r g e n c eo fb pn e u r a ln e t w o r kt ot r a i nt h en e tw o r k ，a n dt h e ng e tt h ee s t i m a t i o no u t p u t a tl a s t ，t h em o d e lh a sb e e nc o d e di nm a t l a bl a n g u a g e ，a n dt h em a s s i v ec o n s t r u c t i o no ft h er e a l w o r l dp r o j e c t sa st r a i n i n gs a m p l eh a v eb e e nu s e dt ot e s tt h em o d e l a c c o r d i n gt ot h eo u t p u to f t h ee x p e r i m e n t a t i o n ，t h em o d e lc a na c c u r a t e l ye s t i m a t et h ep r o j e c tc o s t k e yw o r d s ：p r o j e c ti n v e s t m e n te s t i m a t i o n ，f a s te s t i m a t e ，g e n e t i ca l g o r i t h m ，n e u r a ln e t w o r ki i独创性声明本人郑重声明：所呈交的学位论文是我个人在导师指导下进行的研究工作及取得的研究成果。尽我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其他人已经发表和撰写的研究成果，也不包含为获得华东交通大学或其他教育机构的学位或证书所使用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文中作了明确的说明并表示了谢意。本人签名刳圭章关于论文使用授权的说明日期2 一。歹、f f本人完全了解华东交通大学有关保留、使用学位论文的规定，即：学校有权保留送交论文的复印件，允许论文被查阅和借阅。学校可以公布论文的全部或部分内容，可以采用影印、缩印或其他复制手段保存论文。保密的论文在解密后遵守此规定，本论文无保密内容。本人签名导师签名邋日期兰竺乏：! ! 笪主要符号说明主要符号说明网络输入向量网络目标向量输入层至中间层的连接权中间层至输出层的连接权中间层各单元的输出阈值输出层个单元的输出阈值 耳吩盯n第一章绪论第一章绪论1 1建筑工程快速估价的研究意义及背景长期以来我国的建筑造价存在严重的三超( 概算超估算，预算超概算，决算超预算)现象【1 棚，使得工程造价不断的提高，给国家造成了巨大的损失，而造成这种现象的根本原因就是工程造价估算的误差太大，不能正确的反映工程的实际造价，因而在设计概算、施工预算和工程决算过程中造价会不断的提高。我国加入w t o 后将逐渐消除外资建筑企业进入国内市场的壁垒，我国建筑行业的竞争必将进一步加剧，欧美发达国家在工程造价估算方面的经验和先进的方法将会对国内相关企业造成巨大的冲击1 4 。5 j 。如何面对这些问题，灵活应变，采取先进准确而快速的估价方法，是我国建筑企业不得不思考的问题。我们知道工程项目投资控制是贯穿整个项目建设过程，包括投资决策阶段的投资控制、设计阶段的投资控制以及建设实旎阶段的投资控制。研究发现，对建设实施阶段进行项目投资控制对工程投资的影响只有5 2 5 ；在设计阶段，其影响则可达到3 5 7 5 ；在项目投资决策阶段，其影响更可高达7 5 9 5 。工程前期，特别是项目决策阶段的投资控制是项目投资控制的关键所在，只有真正把控制重心转移到投资决策这个关键阶段，才找到了解决投资失控问题的关键【6 ”。现行的将控制重心放在工程施工阶段f 即建设实施阶段) 的做法，实践证明是不能够解决投资控制失控的问题的【g j 。在投资决策阶段的投资控制中，工程投资造价的合理确定( 7 - 程投资估算) 是其中最为关键的影响因素【9 。0 1 。我们只有合理地估算出工程造价，才能够对投资方案做出正确的选择，这对工程设计以及工程实施起到良好的控制作用，能够保证建设项目良好的经济和社会效益。因此投资估算是工程建设项目建设前期从投资策划至投资决策阶段的重要工作内容，也是设计、咨询单位为业主提供工程造价咨询服务的主要业务之一。其速度是否及时，质量能否达到基本要求，对工程项目的取舍有着重要影响作用。1 2 建筑工程快速估价的研究现状国外的这类研究开始较早，从6 0 年代至今主要采用了3 类模型。6 0 年代初，产生的第一代工程造价模型中较为典型的是英国的工程造价信息服务部( b c i s ) 的造价估算数学模型，其特征是按单位面积造价估算，作法是选择一个最类似的己完工程的数据，按6 个部分分别估算基础部分、主体部分、内装修部分、外部工作部分、设备安装部分和公共服务设施部分。其模型为：上c = 芝 ( t g g 。r ) ，( 1 - 1 )2第一章绪论式中，c 为单位平米造价估计：r 是每部分的单位造价：t 是用户对这部分所添加的时间调整系数；g 是数量调整系数；g 。是质量调整系数。这种模型的优点是计算简单，一个项目不管多大，仅几个部分就计算完成。缺点是灵活性差，其准确性取决于与已建工程项目的相似程度，相似程度越高，准确性越好。第二代模型出现在7 0 年代中期，以回归分析为主要特征。认为任何两个工程都不可能完全相同，因此，单纯以某一个已建工程的数据作为参照物是不恰当的，而用户又很难恰当地给出各种调整系数。基于这种观点，英国的k o u s k o u l a s 和k o e h n 在1 9 7 4 年给出了如下的回归方程，即：c = 口o + d l v l + 口2 v 2 + 0 3 v 3 + 口4 v 4 + 口5 v 5 + 口6 v 6( 1 - 2 )式中，v l 为地区指数，它反映了当地居民的生活水平，可从官方公布的统计数字中得到；v 2 为全国价格指数，国家每年都会公布这一数字：v 3 为建筑类型，它是反映不同类型建筑物成本比例的一个指数：v 4 为高度指数，一般用层高来衡量；v 5 为质量指数，主要反映在所雇工人和所用材料的质量、楼房的用途、设计水平、构件类型和质量等4个方面；v 6 为技术指数，主要反映由于使用了新技术、新工艺或新材料所带来的成本变化。为了估计公式中的参数a oa la 2a 3a 4a 5a 6 ，k o u s k o u l a s 采用随机采样的方法选取了3 8个已建工程的历史数据，用普通最小二乘法估计出了上述参数，得出以下的回归方程，即：c = 一8 1 4 9 + 2 3 9 3 v 1 + 1 0 9 v 2 + 6 2 3 v 3 + o 1 6 7 v 4 + 5 2 6 v 5 + a 3 0 9 v 6( 1 - 3 )第三代模型出现在8 0 年代初期，这一时期模型主要有两类。第一类采用计算机模拟技术建立模拟模型。模拟模型的基础认为，影响工程造价的许多因素都是不确定的，因此不应追求某个确定的值，而应估计实际造价落在某个范围内的概率是多少，根据这种思想，利用计算机来模拟实际工程的施工过程。第二类采用人工智能和知识库技术，建立工程造价估算专家系统，这种模型主要靠专家的知识对工程造价进行估算。此方法的准确性取决于估算专家的经验，并要求知识库经常更新【1 1 。“j 。国内这类的研究工作起步较晚，近几年来，针对建筑行业的快速估价问题，各个领域的研究人员也从不同的角度进行了大量的研究工作，建立了各种各样的估价模型。传统的投资估算方法是建立在统计基础上的经验公式计算法。这些经验公式根据大量工程样本统计分析而来。比较典型的有单位产品法、朗格系数法、以及回归分析方法。这种估算方法本质上是统计方法。它们的成果( 经验公式) 均以特定类型的工程对象为估算目标，精度大部分不高；公式适用性差，一旦待估算的工程属于其他的类型，就不能够利用它来估算。而建立新的经验公式需要大量工程样本才能够保证统计公式的有效性。随着信息技术的迅猛发展，一些新的信息处理技术涌入到工程投资估算研究领域，第一章绪论如灰色系统估算方法、模糊估算方法和神经网络估算方法。模糊方法最重要的步骤是计算两个工程的相似性( 贴近度) 。只有选择了正确的相似样本，最后估算的结果才会准确。相似度的计算正是建立在模糊数学方法上的。方法的最后步骤利用数个相似样本来进行待建工程项目的投资估算。研究表明如果相似样本选择合理，估算公式的参数选择合适，则估算精度较好，可以达到5 t 1 3 】以内；在一般的工程投资估算领域，其估算精度只能为1 5 【1 4 j 以内，方法的通用性不够。虽然选择复杂的隶属函数可以提高估算精度，但是究竟应该选用什么样的隶属函数，采用什么样的原则，尚没有结论。总之，模糊估算方法中隶属函数的选择以及参考系数的调整，需要有经验的工程造价专业人员的反复的试探和调整，增加了模糊估算方法的应用难度【l 孓1 7 】。灰色系统的建筑工程快速估价模型是建立在模糊估价模型所取得的成果基础之上，在建立模糊子集后，利用模糊数学相似优先比原理，进行模糊子集之间的比较与计算，确定各样板工程与待估工程的相似程度，最后根据样板工程相似性排序，采用灰色系统预测理论g m ( 1 ，1 ) 模型，估测出待估工程的造价【1 8 。2 0 】。虽然灰色系统继承了模糊估价的成果可实现长期预测，但是由于无法描述投标报价的非线性本质，以及缺乏自适应能力等缺点，使得其不能在建筑工程快速估价领域获得广泛的应用。另外一种得到广泛应用的估价方法是b p 神经网络估算方法。神经网络作为模拟人的大脑的一种机器学习方法，在预测估算领域的应用广泛1 2 ”。目前人工神经网络在土木工程领域的应用主要有两种形式，第一种是基于b p 神经网络的工程应用；另一种就是基于h o p f i e l d 神经网络的工程应用。作为人工神经网络中最为精华的部分，b p 神经网络得到了广泛的应用。在大多数的工程应用中，研究人员采用的还是b p 神经网络，h o p f i e l d 神经网络常用于工程结构优化。研究结果表明采用b p 神经网络进行工程投资估算精度较好，基本可以满足工程实践对工程投资估算的要求。但是由于b p 算法是一种梯度下降算法，易形成局部极小而得不到全局最优，而且训练次数多使得学习效率低，收敛速度慢。针对这些缺点，国内外学者提出了附加动量、采用自适应学习率以及引入坡度因子等方法来弥补b p 神经网络的缺点。这些方法虽然在一定程度上可以提高b p算法的收敛速度，但是要想彻底的解决b p 算法的缺点就必须摆脱其梯度下降算法田j 。1 3 研究的背景和主要内容本文在查阅大量文献资料的基础上，对目前较为常见的快速估价方法进行了分析，通过对遗传算法及神经网络的分析，将遗传算法的全局寻优性与b p 神经网络的局部快速收敛性相结合，建立基于遗传神经网络的建筑工程快速估价模型。最后根据收集的工程实例的造价信息作为训练样本和检测样本，对模型的估算精度进行了检验。本文结构如下：第一章本文的选题背景及其意义，简要的介绍了快速估价的研究现状，指明了本文的研究背景和主要的内容。4第一章绪论第二章介绍遗传算法的理论基础。第三章介绍人工神经网络的理论基础。第四章对现有较典型的建筑工程快速估价模型进行分析。第五章将遗传算法与人工神经网络相结合，提出建立基于遗传神经网络的建筑工程快速估价模型，使所建立的模型兼备b p 神经网络和遗传算法的优点。第六章根据遗传神经网络快速估价模型，具体在m a t l a b 软件上进行实现，将收集到的已有工程造价作为样本输入网络对网络进行训练，输出待估工程的土建单方造价，并检测模型的精确程度。第二章遗传算法理论基础第二章遗传算法理论基础2 1 遗传算法简介遗传算法( g e n e t i ca l g o r i t h m ，简称g a ) 起源于对生物系统所进行的计算机模拟研究。美国m i c h i g a n 大学的h o l l a n d 教授及其学生受到生物模拟技术的启发，创造出了一种基于生物遗传和进化机制的适合于复杂系统优化的自适应概率优化技术遗传算法。遗传算法是一种借鉴生物界自然选择( n a t u r a ls e l e c t i o n ) 和自然遗传机制的随机搜索算法( r a n d o ms e a r c h i n ga l g o r i t h m s ) 。它与传统的算法不同，大多数古典的优化算法是基于一个单一的度量函数( 评估函数) 的梯度或较高次统计，以产生一个确定性的试验解序列；遗传算法不依赖于梯度信息，而是通过模拟自然进化过程来搜索最优解( o p t i m a ls o l u t i o n ) ，它利用某种编码技术，作用于称为染色体的数字串，模拟由这些串组成的群体的进化过程。遗传算法通过有组织的、随机的信息交换来重新组合那些适应性好的串，生成新的串的群体 2 3 - 2 5 】。2 2 遗传算法的基本概念l 、基因链码生物的性状是由生物的遗传基因的链码所决定的。使用遗传算法时，需要把问题的每一个解编码成为一个基因链码。不妨假设整数1 5 5 2 是问题的一个解，我们就可以用其二进制形式11 0 0 0 0 1 0 0 0 0 来表示这个解所对应的基因链码，其中每一位代表一个基因。因此说，一个基因链码就代表问题的一个解，每个基因链码有时也被称作一个个体。在遗传算法中有时也把基因链码称为染色体。2 、群体一些个体组成了一个群体，一个群体是若干个个体的集合。由于每个个体代表了问题的一个解，所以一个群体就是问题的一些解的集合。例如，p 。= x 1x ：，x 。) 就是由1 0 0 个解( 个体) 构成的群体。3 、交叉许多生物体的繁衍是通过染色体的交叉完成的。在遗传算法中使用了这一概念，并把交叉作为一个操作算子。对该算子的实现过程如下：选择群体中的两个个体五，而，以这两个个体为双亲做基因链码的交叉，从而产生两个新个体x ：，z ：，作为它们的后代。简单的交叉方法是：随机地选取一个截断点，将置，x ，的基因链码在截断点切开，并交换其后半部分，从而组合成两个新的个体x ：，x ：。6第二章遗传算法理论基础4 、变异在很多应用中，交叉算子是以一定概率发生的，这一概率称为交叉概率。在生物的繁衍过程中变异是一个重要的步骤，通过在染色体上的某些基因位置产生突变使得新产生的个体与其他个体有所不同。在遗传算法中变异是一个重要的操作，该算子的实现方法如下：对于群体中的某个个体，即基因链码，随机选取某一位，即某基因，将该基因翻转( 0 改为1 ，l 改为0 ) 。5 、适应度生物体对环境的适应程度的不同而表现出不同的生命力。在这里，每个个体对应于优化问题的一个解置，每个解x ，对应于一个函数值z 。z 越大，则表明x ，越好，即对环境的适应度越高，所以可以用每个个体的函数值：作为它对环境的适应度。6 、选择选择的目的是为了从当前群体中选出优良的个体，使它们有机会作为父代产生后代个体。判断个体优良与否的准则就是各自的适应度值。这一操作是借用了个体适应度越高，其被选择的机会就越大这样一种法则。作为一种算子，选择操作在遗传算法中有多种实现方法，其中最简单的一种方法就是采用和适应度值成比例的概率方法来进行选择 2 6 - 2 7 。2 3 遗传算法的设计2 3 1 遗传算法计算过程1 、初始化确定种群规模n ，交叉概率p 。，变异概率p 。：设置终止进化准则；随机生成n 个个体作为初始种群x ( o ) ；置t = - o 。2 、个体评估计算或估价x ( t ) 中各个个体的适应度3 、种群进化( 1 ) 选择( s e l e c t i o n )根据各个个体的适应度，按照一定的规则或方法，从第t 代群体x ( t ) 中选择出一些优良的个体遗传到下一代群体x ( t + 1 ) 中。( 2 ) 交叉( c r o s s o v e r )将群体x ( t ) 内的各个个体随机搭配成对，对每一对个体以概率p 。交换它们之间的部分染色体。( 3 ) 变异( m u t a t i o n )对群体x ( t ) 中的每一个个体，以概率p 。改变某一个或某一些基因座上的基因值为其他的等位基因。第二章遗传算法理论基础4 、终止检验如已满足准则，则输出x ( t + 1 ) 中具有最大适应度的个体作为最优解，终止计算否则置t = t + l 并转( 3 ) 。图2 - 】遗传算法运算过程f i 9 2 1g e n e t i ca l g o r i t h m so p e r a t i o np r o c e s s2 3 2 编码编码方案的选取很大程度上依赖于问题的性质和遗传算子的设计。通常编码表示与算子设计是同步的。常用的编码方案有以下几种：1 、二进制编码二进制编码就是将原问题的解空间映射n - - 进制位串空间，在位串空间进行一系列的遗传操作，然后通过解码把结果还原，进行适应值的计算。二进制编码首先要确定二进制串的长度，串长度要根据变量的定义域和计算所需要的精度而定。例如，变量x 的定义域为【一1 ，1 ，其要求的精度为1 0 ，则需要将【1 ，l 】分成至少2 0 0 0 0 0 个等长的小区间，而每个小区间用一个二进制串表示。由于1 3 1 0 7 2 = 2 1 7 ( 2 0 0 0 0 0 ( 2 t m = 2 6 2 1 4 4所以串长至少等于1 8 。这样计算中每一个二进制串( b j 7 ，b 1 6 ，) 都对应 _ 1 ，1 1 中的一个点。其解码过程如下：首先将二进制串( b 1 7 ，b 1 6 ，b o ) 按下式转换为一个十进制整数：z ：y 6 ，2 ( 2 1 )箭然后按下式计算对应变量x 的值：x 一1 0 + 譬- 去( 2 - 2 )当变量不止一个分量时，我们可以对各个分量分别进行编码，然后合并成一个长串，第二章遗传算法理论基础分别根据其对应的子串进行编码。采用二进制编码具有以下优点：( 1 ) 二进制编码类似于生物染色体的组成，从而算法易于用生物遗传理论来解释，并使得遗传操作很容易实现。( 2 ) 采用二进制编码时，算法处理的模式最多。尽管如此，在求解连续优化问题时，二进制编码又存在以下缺点：( 1 ) 相邻整数的二进制编码可能具有较大的海明( h a m m i n g ) 距离。例如1 5 和1 6的二进制表示为o l l l l 和1 0 0 0 0 ，如果算法要从1 5 改进到1 6 ，则必须改变所有的位。这将降低遗传算子的搜索效率。二进制编码的这一缺陷也被称为海明悬崖( h a m m i n gc l i f f s ) 1 2 3 1 。( 2 ) 采用二进制编码时，一般要先给出求解的精度以确定串长。而当精度确定之后，就很难在算法执行过程中进行调整。从而使算法缺乏微调的功能。若在算法一开始就选取较高的精度，那么串长就很大，这样也将降低算法的效率。( 3 ) 在求解高维优化问题时，二进制编码串将非常长，使算法的搜索效率降低。2 、实数编码为了克服二进制编码的缺点，对于问题的变量是实向量的情况，可以直接采用实数编码。实数编码就是采用十进制数进行编码，直接在解空间上进行遗传操作。这通常在求解高维问题或者复杂优化问题时采用的较多。试验证明，对于大部分数值优化问题，通过一些专门设计的遗传算子的引入，采用实数编码比采用二进制编码时算法的平均效率要高。由于实数编码表示比较自然，容易引入相关领域的知识，加入启发式信息以增加搜索能力，所以它的使用越来越广泛。3 、其他编码对有些优化问题，目标函数值不仅与表示解的字符串中各个字符的值有关，而且与其在字符串中的位置有关，如二次分配问题、旅行商问题。对这些有序问题，就要采用有序串编码。另外有些问题的解采用树或图的形式表示更加方便，并且容易加入与领域有关的知识和一些启发式信息时，则可以采用结构编码等。以上这些编码在设计遗传算子时需注意不要产生非法的后代。通常要具体问题具体分析，一般在遗传算法中很难设计出通用的算子。2 3 3 适应度函数适应度函数的选择一般根据目标函数选取。根据具体问题的不同，可以直接把目标函数作为适应度函数，或设定为目标函数的某种变形。原始适应度函数是问题求解目标的直接表示，通常采用问题的目标函数作为个体的适应度量。比如在求极值问题m a xf ( x ) 时，f f x ) b i j 为x 的原始适应度函数。对于很多非数值优化问题，我们也可以将其转化为求某个目标函数的极值问题。如第二章遗传算法理论基础设计和训练神经网络时，我们可以将网络的实际输出和期望输出之差的平方和，作为问题的目标函数，则原问题就成为寻找一个网络使目标函数达到最小。有时遗传算法中的某些选择策略要求适应度函数是非负的，而且适应值越大表明个体的性能越好。这时候就需要将原始适应度函数作一个适当的变换以转换成标准的度量形式，即都化为极大化情形，并且为非负的。2 3 4 选择策略选择策略对算法性能起着举足轻重的作用，不同的选择策略将导致不同的选择压力，即下一代中父代个体复制数目的不同分配关系。较大的选择压力会使得最优个体具有较多的复制数目，从而使算法收敛较快。但也容易出现过早收敛现象。反之，较小的选择压力一般能使群体保持一定的多样性。从而增大算法收敛到全局最优的概率，但收敛速度一般比较慢。比较常用的选择策略有基于适应值比例的选择、基于适应值排名的选择和基于局部竞争机制的选择。1 、基于适应值比例的选择( 1 ) 繁殖池选择繁殖池选择首先根据群体中个体的适应值，按下式计算其相对适应值：纠。：#( 2 - 3 )zi = l其中f i 是第i 个个体的适应值，n 是群体规模。则每个个体的繁殖量为：n 。= r o u n d ( r e l , n )( 2 4 )计算出每个个体的繁殖量，然后将它们分别复制n i 个以生成一个临时群体，即繁殖池( b r e e d i n g p o o r ) 。再在繁殖池中随机抽取一对个体进行杂交操作，所产生的后代将取代当前群体形成下一代群体。显然，个体复制到繁殖池的数目越大，则被选择的机会也越大，而对于n t = 0 的个体，则被完全淘汰出整个遗传过程。( 2 ) 转盘式选择这种选择策略首先也是计算个体的相对适应值，计为p i 。在选择时，先生成一个【0 ，1 】内的随机数r ，若p o + p l + + p l - l ，p l + p 2 + + p ，则选择个体i ，此处假设p o - 0 。这种选择方式非常类似于轮盘赌注中的转盘，故得名。转盘式选择与繁殖池选择的不同在于，群体成员在转盘选择下都有被选择的机会，而在繁殖池选择下，具有较小适应值的个体将被剥夺生存的权利，但这些个体的适应值一般有一定的规模。2 、基于排名的选择使用基于适应值比例的选择策略有时会出现过早收敛和停滞现象。使用基于排名的选择策略可以避免这种现象，这种选择策略首先根据个体的适应值在群体中的排名来分1 0第二章遗传算法理论基础配其选择概率p i ，然后根据这个概率使用转盘选择，这样个体的绝对适应值大小不直接影响后代的数量。另外，也不需要对适应值进行标准化和调节，可以直接使用原始适应值进行排名。根据适应值的排名顺序来确定个体的选择概率有很多种实现方法，包括线形排名和非线性排名。所谓线性或非线性，指的是个体适应值排名的顺序到选择概率的映射关系，这个映射( 线性或非线性函数) 可以有多种形式，只要满足以下条件即可：( 1 ) 若f ( x 1 ) f ( x 2 ) f ( x ) ，则分配的概率满足p l p 2 p n( 2 ) p 。= li = l3 、基于局部竞争机制的选择基于适应值比例和排名的选择都是根据个体的适应值在种群中所占的比例或排名位置来确定选择概率，然后进行选择。所以这两种策略在群体规模很大时其额外的计算量不容忽视，在并行实现时有时会有一些限制。基于局部竞争机制的选择在一定程度上可以避免这些问题。基于局部竞争机制的选择策略中，使用较多的有锦标赛( t o u r n a m e n t ) 选择、( u ， ) 和( i t + ) 选择，此外还有b o l t z m a n n 选择。应用锦标赛选择策略选择时，首先随机地在群体中选择k 个个体进行比较，适应值最好的个体将被选择作为生成下一代的父体，参数k 称为竞赛规模，通常取k = 2 。这种选择方式能使得适应值好的个体具有较大的生存机会，同时又能避免超级个体的影响。( i t ， ) 选择是先从规模为u 的群体中，随机选取个体通过杂交和变异等操作生成 ( u ) 个后代，然后再从这些后代中选取u 个最优的后代作为新的一代种群。而u + 选择则是从这些后代与父体共u + 入个选取u 个最优的后代。2 3 5 遗传算法对于不同的编码表示，遗传算子的设计也有所不同。由于实数编码应用的日益广泛，下面将只讨论实数编码下的杂交算子和变异算子。为简单起见，我们假设解向量是n 维，每一个分量都在一个有限区间内定义。l 、杂交( 1 ) 离散杂交离散杂交又分为部分离散杂交和整体离散杂交。部分离散杂交是指在父解向量中选择一部分分量进行交换以生成后代。这些交换的部分分量可以是某一个分量，也可以是某分量之后的所有分量，或者是某两个分量之间的所有分量。整体离散杂交则是对解向量的所有分量都以1 2 的概率进行交换。在程序编制中，这可以通过生成与解向量相同维数的模版的形式来实现。如某一位是l ，则交换相应位置的分量，否则不交换。显然，离散杂交的后代，其分量仍在其定义的区间内。第二章遗传算法理论基础( 2 ) 算术杂交算术杂交也分为部分算术杂交和整体算术杂交。部分算术杂交也是先在父解向量中选择一部分分量( 假定为k 个) ，然后生成k 个( o ，1 ) 区间内的随机数= 口：= 一吼。设需要杂交的两个父解向量中的两个分量分别为v 黯v ；“，则两个后代中相应的分量分别为口，v ；”+ ( 1 一口) v ：”，口，v ；2 + ( 1 一) v ；”。其中，也可以简单地取口l = 口2 一一吼。整体算术杂交同部分算术杂交类似，只不过是n 个分量全部参加杂交，所以要生成n 个( o ，1 ) 区间的随机数。2 、变异( 1 ) 均匀变异均匀变异是在父解向量中随机地选择一个分量，然后在其定义区间内随机产生一个数取而代之，形成新的后代。均匀变异特别适合于遗传算法的初期运行阶段，它使得搜索点可以在整个搜索空间内自由移动，从而增加了群体的多样性。但是其搜索效率难以保证。( 2 ) 正态变异正态变异中，对每个变异的个体j = v 。，v ：，v 。】赋予一个摄动变量向量盯= b 。，o r ：，o n 】。这个摄动向量是变异个体的控制参数。对于第i 个分量，变异后的个体按下式生成：盯= 盯，e x p ( n i ( 0 ，盯) )( 2 5 )v 。= v 。+ n ( 0 ，盯，)( 2 6 )其中，仃r 称为二级步长控制参数：( 0 ，a o ) ，i = 1 , 2 ，n ，是相互独立的均值为0 ，方差为盯的正态分布随机数。由正态分布的特性知，正态变异是改进遗传算法在重点搜索区域的局部搜索性能的一种变异方法。( 3 ) 非一致性变异在传统的遗传算法中，算子的作用与演化代数没有直接关系，因而在演化后期，由于缺乏局部搜索，最终的效果不太好。z m i c h a l e w i c z 首先将变异算子与演化代数联系起来，使得初期变异范围较大，而随着算法的推进，变异的范围逐渐缩小，起到一种微调的作用。设需变异的个体的第k 个分量v k 被选为进行变异，其定义区间为h ，m ，则变异后的该分量变为：v 。：”i + 一咋) ，f 阳玎面m ( 2 ) ( 2 一一)v = l z j【v t a ( t ，v l a ) ，fr a n d o m ( 2 ) = l其中，r a n d o m ( 2 ) 表示将随机均匀产生的正整数模2 的结果，t 为当前演化的代数( t ，y ) 为一值域为【0 ，y 】的函数，具体表达式可取为：第二章遗传算法理论基础a ( t ，y ) = y ( 1 一r 1 。“7 4 )( 2 - 8 )这里的r 是 0 ，1 】上的随机数，t 表示最大演化代数， 是决定非一致性程度的参数，一般取值为2 到5 。从上式可看出，当t 增大时，函数值接近于0 的概率增加。这样就使得算法在运行初期有较大的搜索范围，而后期主要就是进行局部搜索了。( 4 ) 自适应性变异非一致性变异虽然增加了算法的局部搜索能力，但搜索范围只是与演化代数有关，而与解的质量无关。更合理的情形应该是适应值大的个体在较小的范围内搜索，而适应值小的个体在较大的范围内搜索。基于此，自适应性变异引入了解的变异温度的概念，其定义为：r ：1 一型( 2 9 )一其中f ( s ) 为当前解的适应值，丘为所解问题的最大适应值。对于很多问题- ，- 眦是难以确定的，这里只需要一个粗略的上限即可，所以也可以采用当前群体中的最大适应值来代替【2 8 】。自适应性变异和非一致性变异算子类似，只是将非一致性变异中的( 最大) 演化代数用( 最大) 适应值代替即可。2 4 遗传算法的优缺点2 4 1 遗传算法的优点1 、对可行解表示的广泛性。遗传算法的处理对象不是参数本身，而是针对那些通过参数集进行编码得到的基因个体。此编码操作使得遗传算法可以直接对结构对象进行操作。所谓结构对象，泛指集合、序列、矩阵、树、图、链和表等各种一维或二维甚至多维结构形式的对象。这一特点使得遗传算法具有广泛的应用领域。2 、群体搜索特性。许多传统的搜索方法都是单点搜索，这种点对点的搜索方法，对于多峰分布的搜索空间常常会陷于局部的单个单峰的极值点。相反，遗传算法采用的是同时处理群体中多个个体的方法，即同时对搜索空间的多个解进行评估。这一特点使遗传算法具有较好的全局搜索性能，也使得遗传算法本身易于并行化。3 、不需要辅助信息。4 、内在启发式随机搜索特性。5 、遗传算法在搜索过程中不容易陷入局部最优，即使在所定义的适应度函数是不连续的、非规则的或有噪声的情况下，也能以很大的概率找到全局最优解。6 、遗传算法采用自然进化机制来表现复杂的现象，能够快速可靠的解决求解非常第二章遗传算法理论基础困难的问题。7 、遗传算法具有固有的并行性和并行计算的能力。2 4 2 遗传算法的缺点遗传算法作为一种优化算法，它存在自身的局限性：l 、编码不规范及编码存在表示的不准确性。2 、单一的遗传算法编码不能全面的将优化问题的约束表示出来。考虑约束的一个方法就是对不可行解采用闽值，这样，计算时间必然增加。3 、遗传算法通常的效率比其他传统的优化方法低。4 、遗传算法容易出现过早收敛。5 、遗传算法对算法的精度、可信度、计算复杂性等方面，还没有有效的定量分析方法。第三章人：i ：神经网络理论基础第三章人工神经网络理论基础3 1人工神经网络简介人工神经网络( a r t i f i c i a ln e u r a ln e t w o r k ，a n n ) ，也称为神经网络( n e u r a ln e t w o r k ) ，是由大量处理单元( 神经元n e u r o n s ) 广泛互连而成的网络，是对人脑的抽象、简化和模拟，反映人脑的基本特性。人工神经网络的研究是从人脑的生理结构出发来研究人的智能行为，模拟人脑信息处理的功能。它是植根于神经科学、数学、统计学、物理学、计算机科学及工程等学科的一种技术。为了模拟大脑的基本特性，在神经科学研究的基础上，提出了神经网络的模型。但是，实际上神经网络并没有完全反应大脑的功能，只是对生物神经网络进行某种抽象、简化和模拟。神经网络的信息处理通过神经元的相互作用来实现，知识与信息的存储表现为网络元件互连分布式的物理联系。神经网络的学习和识别取决于各神经元连接权系数的动态演化过程1 2 9 。3 1 1 神经网络发展史神经网络理论的发展历史是曲折的，自1 9 4 3 年心理学家m c c u l l o c h 和数学家p i t t s提出神经元生物学模型( 简称m p 模型) 以来，至今已经有5 0 多年的历史【3 ”。在这5 0多年的发展历史中，大体可以分为以下几个发展阶段。1 、初期阶段自1 9 4 3 年m p 模型开始至该世纪6 0 年代为止为神经网络理论的发展初期，这个时期的主要特点是多种网络模型的产生与学习算法的确定，如1 9 4 4 年h e b b 提出了h e b b学习规则，该规则至今仍是神经网络学习算法的一个基本规则：1 9 5 7 年r o s e r b l a t t 提出了感知器( p e r c e p t i o n ) 模型：1 9 6 2 年w i d r o w 提出了自适应( a d a l i n e ) 线性元件模型等。这些模型和算法在很大程度上丰富了神经网络系统理论。2 、停滞期上个世纪6 0 年代到7 0 年代，神经网络理论的发展处于一个低潮期，造成这种情况的原因是发展过程中遇到了本质的困难，即电子线路交叉极限的困难( 对n 个神经元就存在n 2 条连线) 。在当时的条件下，神经元数量n 的大小受到了极大的限制，因此神经网络系统不可能完成高度集成化、智能化的计算任务。同时，神经网络系统理论本身也有很多不完善的地方。所以神经网络系统理论与应用研究工作进展缓慢。3 、黄金时期从2 0 世纪8 0 年代开始，是神经网络理论发展的黄金时期。这个时期最具标志性的人物是美国加州工学院的物理学家j o h nh o p f i e l d 。他于1 9 8 2 年和1 9 8 4 年在美国科学院院刊上发表了两篇文章，提出了模仿人脑的神经网络模型，即著名的h o p f i e l d 模型。第三章人工神经网络理论基础h o p f i e l d 网络是一个互连的非线性动力学网络，它解决问题的方法是一种反复运算的动态过程，这是符号逻辑处理方法所不具备的性质。2 0 世纪8 0 年代到9 0 年代初，由于智能计算机发展问题的提出，神经网络理论得到进一步发展，多种模型、算法和应用问题被提出，完成了很多有意义的工作【3 0 】。目前神经网络理论与技术的发展大体分为以下三个方面进行。首先是硬件方面，美国和日本均实现了规模超过1 0 0 0 个神经元的网络系统，这样的系统具有极高的运算速度。另外，为了克服电子线路交叉极限问题，很多国家都在研究电子元件之外的神经网络，如光电子元件和生物元件等。其次在神经网络理论研究方面，主要进展有b o l t z m a n n 机理论的研究、细胞网络的提出和性能指标的分析等。最后，神经网络的应用研究主要集中在模式识别、经济管理和优化控制等方面，它和数学、统计学中的许多问题有着密切的联系，如线性和非线性规划问题、统计计算等。另外，在数据压缩、编码、股市分析等领域其应用也十分广泛。3 1 2 神经元结构模型神经元是神经网络的基本处理单元，一般表现为一个多输入、单输出的非线性器件，通用的结构模型如下图所示。图3 - 1 神经元结构模型f i 9 3 1t h es t r u c t u r em o d e lo f n e u r o nj 7 警一姒) + y w “x j 一只( 3 - 1 )i y ，( t ) = f e u ，( ，) 】其中，u i 为神经元i 的内部状态，0i 为阈值，x j 为输入信号，w i i 表示与神经元x j连接的权值，s i 表示某一外部输入的控制信号。神经元模型常用一阶微分方程来描述，它可以模拟生物神经网络突触膜电位随时间变化的规律。神经元的输出由函数f 表示，一般利用以下函数表达式来表现网络的非线性特征。1 、阈值型，为阶跃函数1 6第三章人工神经网络理论基础r f “1 ：f 1“，o( 3 2 ，tmr ) 20： o3 圳2 、分段线性型1 1“，“2f ( u ，) = a n ，+ b“，0 “2( 3 3 )【0u l 0 ；- o o x o o从而右( 3 - 6 )( 3 7 )第三章人工神经网络理论基础删p ) = 裟- v p e ( n ) ( 1 - v 硇p ) ) - y 删l _ 州砌则( 一) = y 如( 甩) ( 1 一) 0 ( 甩) ) e 如( 玎) = y 扣( 疗) ( 1 一y 如( 行) ) ( d p ( 疗) 一y 印( n ) )( 3 - 8 )根据d e l t a 学习规则，w 。( n ) 得修整量为蚴卜叩器2 玎 - 器 器劬川j 式中，r 是学习步长，占：( h ) 可由式( 3 8 ) 求得，v j ( 玎) 可由信号的正向传播过程求得。则下一次迭代时隐层j 上任一节点之间的权值为：w j p ( n + 1 ) = ( ) + “口( n )( 3 - 1 0 )2 、隐层i 与隐层j 之间的权值修整量：丽a e ( n ) = 器裟= 器o u 虮一， 一一y 1 ，ljj 一j ，a ( n ) 加j ( ) a ( ”)；( n ) 一。与式( 3 3 ) 相类似，局部梯度为渺一器一器器浯冈为端掣p 砂端篇又凼为p 妇( 哟= d 肇( ，o y 扣( ) = d 肇( ) 一f ( u ；( n ) )端讥加) ) 鬻吲玎)则言焉= 一驴p 咖州h 由式( 3 1 3 ) 和式( 3 1 4 ) 得彰( 行) =