时间:2023-02-04 21:30:32
开篇:写作不仅是一种记录,更是一种创造,它让我们能够捕捉那些稍纵即逝的灵感,将它们永久地定格在纸上。下面是小编精心整理的12篇遗传算法论文,希望这些内容能成为您创作过程中的良师益友,陪伴您不断探索和进步。
影响抄板落料特性的主要因素有:抄板的几何尺寸a和b、圆筒半径R、圆筒的转速n、抄板安装角β以及折弯抄板间的夹角θ等[4,9]。在不同的参数a、β、θ下,抄板的安装会出现如图1所示的情况。图1描述了不同参数组合下抄板的落料特性横截面示意图。其中,图1(a)与图1(b)、图1(c)、图1(d)的区别在于其安装角为钝角。当安装角不为钝角且OB与OC的夹角σ不小于OD与OC夹角ψ时(即σ≥ψ),会出现图1(b)所示的安装情况;当σ<ψ时,又会出现图1(c)与图1(d)所示的情况,而两者区别在于,η+θ是否超过180°,若不超过,则为图1(c)情况,反之则为图1(d)情况。其中,点A为抄板上物料表面与筒壁的接触点或为物料表面与抄板横向长度b边的交点;点B为抄板的顶点;点C为抄板折弯点;点D为抄板边与筒壁的交点;点E为OB连线与圆筒内壁面的交点;点F为OC连线与圆筒内壁面的交点。
1.1动力学休止角(γ)[4,10]抄板上的物料表面在初始状态时保持稳定,直到物料表面与水平面的夹角大于物料的休止角(最大稳定角)时才发生落料情况。随着转筒的转动,抄板上物料的坡度会一直发生改变。当物料的坡度大于最大稳定角时,物料开始掉落。此时,由于物料的下落,物料表面重新达到最大稳定角开始停止掉落。然而,抄板一直随着转筒转动,使得抄板内物料的坡度一直发生改变,物料坡度又超过最大休止角。这个过程一直持续到抄板转动到一定位置(即抄板位置处于最大落料角δL时),此时抄板内的物料落空。通常,在计算抄板持有量时,会采用动力学休止角来作为物料发生掉落的依据,即抄板内的物料坡度超过γ时,物料开始掉落。该角主要与抄板在滚筒中的位置δ、动摩擦因数μ和弗劳德数Fr等有关。
1.2抄板持有量的计算
随着抄板的转动,一般可以将落料过程划分为3部分(R-1,R-2,R-3),如图1(a)所示。在转动过程中,当抄板转角δ超过动力学休止角γ时,落料过程从R-1区域转变到R-2区域,在这两个区域内,物料不仅受到抄板的作用还受到滚筒壁面的作用。当物料表面上的A点与D点重合时,从R-2区域转变到R-3区域,在该区域内,物料仅受抄板作用[4]。然而,抄板情况为图1(c)、图1(d)时只会经历R-1、R-3区域。因为在运转过程中,抄板上物料的A点与D点重合时抄板的转角不会超过动力学休止角γ,所以不会经历R-2区域;但是,当物料的休止角足够小时,由于物料表面只会与抄板接触(即A点不会超出D点),图1(c)、图1(d)的抄板落料过程只会经历R-3区域。以下根据不同的区域建立了不同组合下抄板持料量的数学模型。
2研究结果与分析
2.1最大落料角结果分析
通过MatLab编制以上推导公式的计算程序,模拟计算了120种不同组合(β、θ、a不同)下抄板的最大落料角。其中,物料动摩擦因数为0.53[8],转筒干燥机半径为300mm,且其抄板安装角为10°、30°、50°、70°、90°、110°,抄板间夹角为90°、110°、130°、150°,抄板纵向长度a为30、45、60、75、90mm,横向长度b为60mm。并且,根据Kelly和O'Donnell通过验证得出的公式(1)只适用于Fr小于0.4的情况[4],此次模拟的转筒干燥机角速度为0.84rad/s。表1给出了模拟结果中较为典型的数据。从模拟结果中可以得出,当a、θ不变时,δL随着安装角β的增大而增大;当a、β不变时,δL随着θ的增大而减小。当抄板情况如图1(a)、(b)、(c)时,且β、θ不变时,抄板最大落料角随着长度a的增大而增大;而图1(d)情况则反之,并且会出现最大落料角小于0°的情况,这是由于抄板无法抄起物料所导致的结果。另外,在图1(d)情况下,抄板的最大落料角非常小,这会使得干燥器的效率很低。因此,在探讨抄板优化问题上,不考虑图1(d)这种情况下的抄板。
2.2优化目标与结果分析
水平直径上均匀撒料虽好,但是物料应与热气均匀接触,如果在路径长的地方撒料多些,就可以使热效率高些。又因为圆筒中心热气量比边缘多以及在圆筒下半部分超出干燥圆的区域存在物料,所以落料均匀度考虑为物料在干燥圆横截面积上撒料均匀。评判干燥圆横截面积上落料均匀的具体方法如下:把干燥圆横截面积划分20个等分,以水平直径为X轴,铅垂直径为Y轴,圆心O为原点,采用定积分方法求解每个划分点的x坐标,每个划分点的铅垂线与干燥圆壁面(上半部分)有一个交点,连接圆心与每个点,可以得出每条连线与X轴的夹角δi(i=1~21,步长为1,δ1为0°),如图2所示。在合理的设计下,不仅希望落料过程中抄板在干燥圆面积上撒料越均匀越好,δL也应越接近180°越好。因此,优化函数为最大落料角和抄板在干燥圆而积上落料的均方差。并且,根据国内外实际情况,抄板的安装角一般为90°并且抄板间夹角一般不为锐角,由于机构的限制和不考虑图1(d)的情况,在研究抄板优化问题时只探讨安装角在70°~110°、抄板夹角在90°~130°以及抄板纵向长度在30~90mm之间的情况。其余参数同上。采用了线性加权和法来求解此多目标优化结果。其中,f1为1/δL的最优化值,f2为q的最优化值;均方差q=(1n∑ni=1(qi-qa)2)12,每相邻角度落料面积差qi=A(δi)-A(δi+1),qa为面积差的平均值。当δL≤δi+1-δi2,n=i;反之则n=i+1,且δi+1=δL。s1、s2为权重系数,由于干燥器的效率主要与抄板的撒料均匀有关,但是如果落料角很小、撒料很均匀,干燥器效率也不高,综合考虑下,取s1、s2分别为0.4、0.6。通过编写MatLab程序,确定优化函数,然后采用MatLab遗传算法工具箱进行计算,设置相关参数:最大代数为51,种群规模为20,交叉概率为0.2,选择概率为0.5。运行算法并显示结果,β、θ、a较优结果分别为:1.844rad、1.571rad、51.609mm。
3结论
关键词:量子遗传算法;多目标分配;最优化
中图分类号:TP18 文献标识码:A 文章编号:1674-7712 (2012) 12-0176-01
一、引言
遗传算法不同于传统寻优算法的特点在于:遗传算法在寻优过程中,仅需要得到适应度函数的值作为寻优的依据;同时使用概率性的变换规则,而不是确定性的变换规则;遗传算法适应度函数的计算相对于寻优过程是独立的;算法面对的是参数的编码集合,而并非参数集合本身,通用性强。它尤其适用于处理传统优化算法难于解决的复杂和非线性问题。[1]
目前,GA已经在很多领域得到成功应用,但随着问题规模的不断扩大和搜索空间的更加复杂,GA在求解很多具体问题时往往并不能表现出其优越性。于是,近年来便出现了遗传算法与其它理论相结合的实践,其中遗传算法与量子理论的结合是一个崭新的、极富前景和创意的尝试。
量子遗传算法QGA是量子计算特性与遗传算法相结合的产物。基于量子比特的叠加性和相干性,在遗传算法中借鉴量子比特的概念,引入了量子比特染色体。由于量子比特染色体能够表征叠加态,比传统GA具有更好的种群多样性,同时QGA也会具有更好的收敛性,因此在求解优化问题时,QGA在收敛速度、寻优能力方面比GA都将有较大的提高。QGA的出现结合了量子计算和遗传算法各自的优势,具有很高的理论价值和发展潜力。
本论文提出用量子遗传算法处理和解决多目标分配问题,为多目标问题的解决提供一种新的思路。
二、量子遗传算法
在传统计算机中,信息存储是以二进制来表示,不是“0”就是“1”态,但是在量子计算机中,充当信息存储单元的物质是一个双态量子系统,称为量子比特(qubit),量子比特与比特不同之就在于它可以同时处在两个量子态的叠加态,量子进化算法建立在量子的态矢量表述基础上,将量子比几率幅表示应用于染色体的编码,使得一条染色体可以表示个态的叠加,并利用量子旋转门更新染色体,从而使个体进达到优化目标的目的。
一个 位的量子位染色体就是一个量子位串,其表示如下:
其中 。在多目标优化中,一个量子染色体代表一个决策向量,在量子态中一个 位的量子染色体可以表达 个态,采用这种编码方式使得一个染色体可以同时表达多个态的叠加,使得量子进化算法比传统遗传算法拥有更好的多样性特征。
为了实现个体的进化,经典进化算法中通过染色体的交叉、变异操作推进种群的演化,而对量子进化算法而言,量子染色体的调整主要是通过量子旋转门实现的,算法流程如下:
(1)进化代数初始化: ;
(2)初始化种群 ,生成并评价 ;
(3)保存 中的最优解 ;
(4) ;
(5)由 生成 ;
(6)个体交叉、变异等操作,生成新的 (此步可省评价);
(7)评价 ,得到当前代的最优解 ;
(8)比较 与 得到量子概率门 ,保存最优解于 ;
(9)停机条件 当满足停机条件时,输出当前最优个体,算法结束,否则继续;
(10)以 更新 ,转到4)。
三、基于量子遗传算法的多目标分配应用
如今为了满足市场的需要,很多工厂的生产种类多、生产量大,从而设置了不同的生产车间,根据产品的性质分配生产车间合理与否直接影响工厂的经济收益,这同样可采用遗传算法的目标分配方法进行分配。
模型构建:设工厂有i个生产车间。 为在第i个车间生产第j种产品的收益, 为第j种产品的需求量;如果第j种产品被选中,则 为在第i个车间生产该产品的总收益。由题意知为求解 最大问题。
仿真实例:设有10个生产车间,要生产15种产品,用Matlab程序编程,设定40个粒子,迭代200次,代沟0.9。运行结果如下:
此图表明经200次迭代后的目标分配方案为:第1种产品由第3个车间生产,以此类推,车间5生产第2种产品,车间8生产第3种产品,……。次方案对应的车间总收益值为2.7030e+003,成功进行了多目标分配问题的解决。
四、结论
基于量子遗传算法的多目标分配,为多目标分配突破传统寻优模式找到了一个可行的解决方法。根据这种方法实验,仿真结果可以看出,基本符合要求,并且能够在一定的时间内得到最优的分配方案,因此,本文在探索多目标分配问题上找到了一种新的解决思路。
参考文献:
[1]吉根林.遗传算法研究综述[J].计算机应用与软件,2004,21(2):69-73
[2]肖晓伟,肖迪.多目标优化问题的研究概述[J].计算机应用研究,2011,3,28(3):805-808
[3]原银忠,韩传久.用遗传算法实现防空导弹体系的目标分配[J].火力与指挥控制,2008,3,33(3):80-83
[关键词] 配送 车辆路径问题 时间窗 遗传算法
随着经济全球化趋势的加强,科学技术尤其是信息技术的发展突飞猛进,产品营销范围日趋扩大,社会生产、物资流通、商品交易及其管理方式正在发生着深刻的变革,与此相适应,被普遍认为企业在降低物资消耗、提高劳动生产率以外的“第三利润源”的现代物流在世界范围内广泛兴起,目前正在成为全球经济发展的一个重要热点和新的经济增长点。随着传统批发、交通运输、仓储业向现代物流转化,尤其是配送方式的采用,对运输成本和时间的有效控制日渐成为城市配送车辆路径问题的一项重要目标。VRP一直以来都是车辆调度所重点研究的方向。而在城市内采取的配送方式恰恰具备了VRP问题的一般特征和优化调度条件。
一、VRP模型的条件及假设
VRP问题是指按要求用多个车辆从配送中心对顾客进行配给货物。各顾客点的位置和需求量为己知,各车辆的装载质量己知,力求寻找一个好的配送方案,使得总代价最小(车辆尽量少,行车总距离尽量短,总费用尽量低等),由VRP的定义不难看出,必须满足以下条件及假设:
1.仅考虑位置已知的单一配送中心,所有的配送车辆以配送中心为起点,并最终回到配送中心。
2.每条配送路径上各需求点的需求量之和不超过车辆的装载质量,被配送货物是可混装的货物。
3.每条配送路径的长度不超过车辆一次允许行驶的最大距离,配送中心有足够的资源以供配送,并且有足够的运输能力。
4.各个客户需求和所在地均已知,每个需求点的需求由且仅由一辆车一次送货满足。
5.满足总时间约束与时间窗口。必须在时间区间[ei,lj]访问点i客户,并允许在i处等待,车辆服务的总时间不能超过物流中心的时间约束。
6.多个客户之间存在优先关系,必须在访问客户j之前访问客户i。
二、带时间窗VRP模型的建立
基于文献一文中的模型,并考虑配送系统是一个服务系统,所提供的服务必须能够让客户方便、满意。配送系统的运作成本必须和配送系统其他性能参数综合进行考评,单纯对成本进行评价是没有任何实际意义的。需要关注和努力的是:要在保证配送满足客户要求、提升客户满意度的同时,通过各种技术和管理手段,降低运作成本。因此,本文将建立改进的运输路径模型,在传统的车辆配送成本最小化目标的基础上,兼顾客户对配送时间的要求,使车辆等待和延误时间之和最小化。
(1)
(2)
式中K――车队规模,即总的车辆数目;
k――车辆数目(k=1,2,……,K);
N――有待访问的总的客户的数目;
O――配送中心;
Q――每辆车辆的容量,这里假设所有车辆同质,容量均为Q;
i,j――顾客数(i=1,2,……,N;j=1,2,……,N);
T――个很大的数字;
C――每辆车单位运距的运费;
t0――车辆从配送中心出发的时间;
e0――车辆可离开配送中心的最早时间;
ei――到达客户i处规定最早到达时间;
l0――车辆返回配送中心的最晚时间;
li――到达客户i处规定最晚到达时间;
dij――从客户i到客户j的距离;
pj――每个客户单位卸货量的卸载费用;
mi――客户i的货运需求量;
tki、tkj――第k辆车到达客户i、j处的时间;
tij――连接客户i和客户j的行驶时间;
si――客户i处的服务时间;
wi――在客户i的等待时间,wi≥0。
两个决策变量如下:
这个模型通用性很强,经过参数的不同设定,可以转换为其它组合优化问题的数学模型。
三、带时间窗VRP模型的遗传算法求解
在模型的处理上,根据本文提出的模型单位标量不统一的特殊性来选择权重系数变化法,将变化后的多目标函数经分析和试验得出各个子目标函数的数量级大小并确定权重,最后加权化为单目标函数用遗传算法求解。
1.惩罚函数的引入。在以往的对含有时间窗约束的车辆配送系统的研究中,所研究的成本大多仅包含行驶成本,但事实上,还包括其它成本(如装卸搬运成本),将时间窗约束转化为惩罚函数而体现在模型中。
式中c1――车辆在任务点处等待单位时间的机会成本。
c2――车辆在要求时间之后到达单位时间所处以的惩罚值(c1和c2的大小,要根据实际情况来定)。
2.建立适度度函数。根据遗传算法中适应度函数的特点,需要将原目标函数式变化为:
(4)
(5)
式中A*,B* ――变化后的目标函数值,取值范围为[0,1);
Amax,Bmax――分别是原始目标函数。
适应度函数因此变化为:f(A,B)=α×A*+β×B*(6)
经过分析和实验发现,A*,B*经过处理后,A*的数量级一般是10-2,B*的数量级一般是10-1。
3.用遗传算法求解带时间窗VRP模型。本文取α=0.8,β=0.2,用遗传算法进行求解。在运用遗传算法求解后,验证了该算法易于理解,对问题的依赖性较小,对其求解的函数要求简单,实现起来简单高效,若参数选择的合理,收敛速度很快,但是遗传参数的控制对于算法的收敛速度影响很大,在参数选择方面有一定难度。虽然文中使用的是根据以往学者经验选定的参数,但计算表明最优解所在“代”数的稳定性不是很好,这也是以后需要进一步研究的地方。
四、结论
在传统的车辆配送成本最小化为目标的基础上,兼顾客户对配送时间的要求,建立了带时间窗的车辆路径优化多目标模型。在对模型的处理上,将两个量纲不统一的子目标函数除以各子目标函数的最大值后使其变成无量纲的函数,并通过权重系数变化法将各个子目标函数线性加权和作为多目标优化问题的适应度函数,使得多目标优化问题转化为单目标优化问题后再用遗传算法求解。
参考文献:
[1]王 惠:引入顾客满意度求解车辆优化调度问题.大连海事大学硕士论文,2006:1~13
[2]盛丽俊:带有时间窗的车辆路径问题的优化研究.大连海事大学硕士论文,2002:13~57
[3]牟燕妮:物流配送中路径优化的选择研究.沈阳工业大学硕士论文,2006:28~41
关键词:遗传算法;运筹学;应用
中图分类号:F27 文献标识码:A
收录日期:2011年10月28日
一、遗传算法简介
遗传算法(GAS)是由美国密执根大学的Holland等人创立的。与其他启发式方法顺序搜索解空间的工作方式不同,遗传算法采用解的种群作为工作单元,使用模仿生物进化的适者生存原则指导搜索并改进目标。种群由代表个体的定长字符串组成,每个个体表示解空间的一个点,每个解的质量,通过依赖于问题目标函数的适应值函数来进行评估。搜索过程通过进化来进行,每代中的个体以正比于它的适应值的概率遗传到下一代。它使用3个基本算子:选择、交叉和变异。选择是指个体以其适应值比例复制到池中;交叉是池中的两个个体进行,组合形成一个(或几个)新个体,复制和交叉将好的特性进行遗传;变异则是发生在少数字符串某基因位上的基因的突变,它使搜索过程能够有机会从搜索到的局部最优解逃出。
解决一个实际问题的遗传算法通常包括下列两个决策步骤:(1)将求解问题模型化为符合遗传算法的框架。可行解空间的定义,适应值函数的表现形式,解的字符串表达式方式;(2)遗传算法参数的设计。种群规模,复制、交叉、变异的概率选择,进化最大代数,终止准则设定等。
二、遗传算法的基本特点
(一)结构特点。遗传算法是以适应值提供的启发式信息进行搜索的,与其他启发式(模拟退火、爬山法、神经网络等)方法相比,在结构和工作过程方面的特点见表1。(表1)
(二)实验性能方面的特点
1、高效性。遗传算法具有大范围全局搜索的特点,与问题领域无关,前期工作量比较少。
2、健壮性。遗传算法的搜索是用种群作为基本单元,采用三个不同作用的基本算子进行搜索的,解的结果随时间增加而趋于稳定,不受初始解的影响,而且不因实例的不同而蜕变。
3、通用性和灵活性。遗传算法可用于多种优化搜索问题,解题程序可以通用,针对不同的实例,适当调整算子参数,就可以使算法执行获得最佳的解结果和占用CPU机时的关系。
三、遗传算法在解决经典运筹问题中的应用
(一)旅行商问题(TSP)。旅行商问题自诞生以来,颇受数学家推崇,今天的旅行商问题已远远超过其本身的含义,成为一种衡量算法优劣的标准。旅行商问题是采用非标准编码遗传算法求解最成功的一例,基因编码用推销员顺序经历的城市名表示,求最佳路线即是改变编码次序而求最低适应值的问题。对类似字符串使用标准交叉,产生的后代可能有重复或丢失的元素,因而成为非可行解。为克服这种困难,人们提出许多非标准的交叉和变异方法:交叉主要采用重排序方法――部分匹配重排序,顺序交叉和循环交叉等;变异主要采用位点、反转、对换、插入等方法,使旅行商问题得以有效地解决。值得一提的是,清华大学张雷博士提出的自适应多点交叉算子,能够保证多点交叉后路径的可行性,加快了搜索速度。
(二)作业调度问题。作业调度问题同样是自然变更次序的问题,可以用基于变更次序的遗传算法进行处理。(表2)
(三)背包问题。一维、二维和三维背包问题在商业和工业领域有着广泛的应用,基于遗传算法的求解方法很多。传统求解采用启发式规则,决定下一步该装哪一块和装在哪里,此时变更次序的编码与启发式安置策略是利用遗传算法解决这类问题的最为出色的方法,Lin使用一系列的惩罚项指导其搜索策略,测定单个个体的适应值。
Bortfeldt使用一个层次背包问题,个体用它们的层次代表,当两个亲代被选择交叉时,它们的层次混在一起,从中选择最好的作为子代的第一层,再从余下的组件中选择最好的作为第二层,以此类推,直至产生所有的层次。
陈国良等设计了一种“与/或”交叉方法,使子代继承双亲的同型基因,对杂型基因采用不同支配方式,这种策略为遗传算法的硬件实现创造了良好的条件。
(四)时刻表排定问题。Corne对Edinburgh大学7日内的28个时间期间安排40门课的考试问题作了处理,寻找一个可行的时间排定表,使每个学生参加的考试在时间上能够错开,时刻表用字符串代表,字符串每个位置代表一门课,该位置的值代表考试的时间,用均匀交叉和标准变异操作求解。
这类问题扩展到基于二维的矩阵代表的逼近问题,Colorini使用行代表教师列代表可用的小时数的矩阵,每个单元的值为教师在此时承担的任务,包括教室和其他一些资源配置,教师的任务是事先给定的,故行都是可行的,列代表的时间安排可能会发生冲突,将此冲突用惩罚函数表示在适应值函数中,而且采用修复算子在评价之前尽量将结论调整回可行区域内,该算法用Milan学校的实际数据进行了检验。
除此之外,遗传算法在运输问题、指派问题、分割问题及网络计划优化问题等方面都获得了非常成功的应用,这些问题被认为是NP类问题,其规模随变量的增加呈指数增长,遗传算法在这些问题的求解中,充分体现了其操作性能方面的优势。
四、应用和推广中存在的问题
在上述问题中,遗传算法求解展示了优良的性能,但遗传算法并未像其他启发式方法那样容易地被OR学者广泛接受而用于大量的实际问题中,究其原因,主要有以下几点:
(一)传播方式的障碍。遗传算法最初的工作是以密执根大学严谨的研究小组作为研究项目和学术讨论中心,当研究成员扩大时,这类讨论会演变为机构的学术会议(美国现有5个,欧洲有3个,我国目前还没有),许多研究者聚于此而远离问题导向,有关的会议论文公开出版数量很少,而且,由于历史原因,研究者常常将他们的研究结果选择在有关人工智能的杂志上发表,导致了应用遗传算法的信息很缓慢地扩散到其他不同技术应用领域的工作者中,这与模拟退火等其他启发式方法快速在运筹学会议及杂志上发表相反。由于缺乏交流导致了两方面的问题:一是许多关于遗传算法的论文不能与从其他方法得到的结论进行质量的比较,二是削弱了许多遗传算法多的潜在使用者用遗传算法与其他方法竞争的信心。
(二)术语的隔膜。初始跨入遗传算法领域的使用者常常感到起步非常艰难,遗传算法依赖于遗传学的术语也像模拟退火的术语来自于统计热力学一样。然而,温度、冷却等可能很快赋予新的意义,但遗传算法中的基因位、染色体、遗传型却难以很快被人理解和接受;另外,许多发表的研究偏重于用某些专门函数检验他们的新思路或新设想,这对于全面理解该技术固然是一件好事,但对于一个面对如此丰富复杂材料的初用者会发现,他将不知从何做起。即使一个非常愿意使用遗传算法的人,也要有足够的决心去克服上述障碍。
(三)方法的局限性。对于具有强约束的优化问题,采用惩罚函数逼近常常达不到预想的结果。Radcliffe评论说:“约束通常被认为是遗传算法面临的最大问题”因为惩罚因子选择不当时,会招致错误结论。目前,求解带约束优化问题的启发式遗传方法已经有了一些,但是,它们多数与问题领域相关,在这方面还缺少普遍适用的方法的系统研究。
(四)编码的困难。不是所有问题解空间中的点都能明显地用编码表示,作为OR研究者,常常从问题结构取得利益,用矩阵、树、网络或其他更适用的方法建立表达式;串表达中的建筑块假说建议适用较少的字符,导致人们对二进制编码的偏爱,但二进制编码具有一定的映射误差(实际计算时,我们是把问题作为整数规划),特别是它不能直接反映出所求问题本身结构特征,因此很难满足生成有意义的积木块编码原则;再者,二进制字符的长度随问题发生明显变化,当问题复杂时会因为编码太长而无法进行正常工作。
以上的种种阻力,在一定程度上减缓了遗传算法在运筹学实际问题中的推广和应用。
主要参考文献:
[1]陈国良等.遗传算法及其应用.北京:人民邮电出版社,1996.6.
关键词:电网规划;地理信息系统(GIS);遗传算法;现代启发式方法
0 引言
电网规划是电力系统规划的重要环节[1],电网规划方案的优劣直接影响到电网的建设费用以及运行费用。传统的规划很难对地理实体进行数据采集,规划模型往往也忽略地表因素(障碍物等)的影响,所以精度较低,规划结果往往不具备实用性和可操作性,此外传统的规划很难实现可视化,缺乏直观性。结合GIS 平台,对电网规划问题进行优化,既可以方便的把地貌因素运用到电网规划中,又使规划结果直观可视,从而大大提高了结果的科学性和实用性。
1 基于GIS平台电网规划的特点
在电网规划中引入GIS系统有如下特点:
(1)电网规划要求大量详细的地理信息,如变电站位置、变压器位置等。借用GIS平台可以使规划区域的整个电网直观地显示在屏幕上,规划人员能够方便地确定待选变电站和待选线路路径。
(2)把GIS引入电网规划中,用户可以考虑许多实际的约束条件,如地理位置、街道等的互连关系、街区布局等等,而且由于空间数据模型的引入,这些约束条件对用户是透明的,可以直接从地图上获得,建模工作将得到简化。
(3)结合GIS的电网提供了从文-图和从图-文的双向查询,不但能通过系统开发的查询工具对任意点取图上目标进行所见即所得的查询,而且可以对电网图层空间的每一层设置其显示范围、是否可视等属性[2]~[4]。
2、基于GIS平台的电网规划方法
电网规划分为经典方法和现代启发式方法,传统的经典方法能够得到解析解,在理论上能使得规划结果相对最优,但对问题的规模、约束条件的数量、问题的组合度比较敏感,容易陷入“维数灾”而难以在合理时间内求得结果。近几年出现的基于生物学、人工智能的现代启发式算法具有直观、灵活、计算速度快、不受限于问题规模等特点,不仅遵循配网规划常用规则,而且便于规划人员应用过去的经验,在配网规划中能很快得到近似最优解。由于现代启发式方法优势明显,所以传统的经典方法已经很少使用。
2.1 Tabu 搜索算法
Tabu 搜索方法是一种亚启发式随机搜索算法,它从一个初始可行解X0(为n维向量)出发,选择一系列的特定搜索方向(移动)作为试探,从当前解的邻域N(X)中随机产生一系列试验解X1,X2,… XK选择其中最好的解X*作为当前解,即令Xcurrent=X*,重复迭代,直到满足一定的终止准则。
文献[5]运用Tabu 搜索算法,在GIS平台上对网架模型进行优化。目标函数是年费用最小,年费用为线路的新建投资年费用、维护年费用和运行、折旧年费用,约束条件包含配网辐射限制、负荷需求限制和线路潮流限制三个方面。该文以备选网络的生成树作为Tabu搜索的初始解,使得辐射性的约束自然满足,Tabu 搜索算法中采用“交换移动”进一步判断辐射性,Tabu表是先进先出的管理模式。Tabu 搜索结果可以在GIS界面中形象的观察到。
2.2 遗传算法(GA)
遗传算法是目前比较成熟的一种启发式算法,遗传算法类似于自然进化,通过作用与染色体上的基因寻找好的染色体来求解问题[6]。
文献[7]结合GA 和GIS 提出了一种新的电网规划模型,该模型目标函数中包含线路各种设备投资、维护、运行费用和用户停电损失费用。约束条件为输送功率、电流允许范围、最小电压降以及网络的辐射性。通过根节点融合法来保证网络的辐射性,并考虑到了中间节点和分支点,形成真正可行的网络接线方案,从而使该方法可以考虑各种复杂的网络结构,更适用于电网GIS规划。GA 算子过程采用Elitism 算法:每次构造子代种群时,都从父代种群中选择一定的最优个体直接作为子代个体,在随机选择时,适应度高的以一定比例选中,经试验证明变异率为0.02时遗传算法的性能较好。该文最后对一个算例进行投资总额分析,分析表明考虑可靠性价值可以节省资本,减少配网的投资金额。但该文仅解决了单条馈线优化规划,没有考虑线路之间的接线模式的影响。
2.3电源追踪算法
所谓电源追踪就是在选中杆塔或者杆塔上设备时, 搜索给该设备供电的变电站。
文献[8]将网络拓扑技术与电网GIS的开发相结合, 为电力企业的设备管理及辅助决策提供了图形化的管理工具, 提高了电力企业的工作效率。它提出电源追踪算法,该算法即使在网络拓扑关联属性字段的数据不全时, 也能快速、准确的定位电源点, 提高了电网电源追踪模块的实用性, 更好地满足了实际工程的应用需要。具体算法原理和过程如下:当拓扑信息数据不全时, 算法转为执行基于启发式搜索的拓扑分析追踪。它不需要借助拓扑关联属性字段的值, 而是通过地理信息系统软件提供的拓扑分析函数就可建立起整个电网络, 并通过这个网络进行搜索, 从而选择出设备到其供电电源的最优路径。
3 结论
1、每种算法都有自己的优点,但任何一种算法都有自己的不足。各种算法虽然在理论上能较好的满足规划要求,但还很难便捷的应用到实际中。
2、尽管基于GIS的电网规划方法的研究已取得很多成果,但至今还没有比较完善的电网规划软件能够方便地应用到实际规划工作中。因此,研究开发相对完善实用的电网规划软件和基于GIS的电网规划软件将是电网规划研究工作者们今后工作中的首要任务。
参考文献
[1]赵帅虎,吴健,陈丁剑.基于GIS 配电网自动化分布式协同建模技术的研究[J]. 微型电脑应用.Vol.27,No.1,2011.1:6
[2]王金凤.基于GIS的配电网优化规划研究.硕士学位论文[D].郑州大学,2002.4
[3] 张志波.基于GIS技术的县级配电网架优化规划软件[D].硕士学位论文.河北农业大学,2008.6
[4]张林峰.基于地理信息系统的智能城市电网规划.硕士学位论文[D].华北电力大学,2006.12
[5]杨丽徙,王金凤,陈根永.基于GIS 和Tabu 搜索的配电网优化规划[J].郑州大学学报(公学版).VOL 23,No.3,2002.9:75-77
[6]刘娜.基于遗传算法的农村配电网检修计划方法的研究[D].沈阳农业大学,2005.10
[7]王春生,赵凯,彭建春.基于地理信息系统和遗传算法的配电网优化规划[J].电力系统自动化.2000.7.48-51
[7]赵强,杨柳.基于启发式搜索的配电网GIS拓扑分析[J]. 计算机应用与软件.Vol.25,No.9,2008.9:181-183
[8]陈珊. WebGIS中最短路径算法及其应用的研究[D]. 上海: 华东师范大学, 2005.
【关键词】云计算;DAG图;遗传;蚁群;任务;融合
本文提出一种基于DAG模型的优先级表的依赖任务调度算法。以时间触发调度,采用重复调度。当每次调度事件发生时,包含那些上一次调度事件中已经被调度但还没有开始执行或被迫中断的任务, 还有新到达的任务,。这与云计算中资源的动态性是相应的。
在算法实现方面,我们考虑将遗传算法和蚁群算法相结合,利用遗传算法进行前期训练然后利用蚁群算法进一步进行搜索收敛,最终得到最优调度方案。结合云计算任务调度的特点,本文选取遗传算法和蚁群算法的参数设置,将问题转换到云计算任务调度问题上来,提出融合遗传算法[1]和蚁群算法[2][3]的云计算任务调度算法。
一、问题提出
每个子任务用圆圈表示,圈中T表示任务号,Q表示计算量,而DAG图中的箭头表示子任务之间的优先关系,C(i,j)表示任务Ti与Tj之间的通信量。图1所示,箭头从前驱指向后继,前驱是后继的必要,只有在某个任务的所有前驱都完成时,该任务才被执行。在任务调度过程中重复调度,当每次调度事件发生时,任务组中既包含新到达的任务,。这与云计算中资源的动态性相适应的。算法使用更新的资源信息对任务进行调度,这与动态的云计算环境是相适应的。
Fig.1 DAG task graph
图1 任务DAG图
由各种任务分配方案需要进行优化。如图2任务划分后的一种方案。
Fig.2 Sub-task resource allocation plan
图2 子任务资源分配图
设有m个计算结点所组成的云计算系统P={P1,P2,…,Pm},每个结点Pj处理能力为d。需要运行m个子任务T={t1,t2,…,tm},一般地。将任务调度问题描述成如下五元组∑=(T,,Q,C,X,w)。其中:“”是T中子任务间的优先关系;Q是一个维的矩阵,其元素qij表示子任务ti在处理机Pj上的执行时间;C是一个维通信矩阵,cij表示子任务ti与tj之间的通信时间;X是一个维的任务分配矩阵,其中Xij=1,表示ti分配到处理机Pj上执行,否则Xij=0;w表示通信和执行之间的差异。
二、算法实现
利用遗传算法进行前期的训练。得到的信息素作为蚁群算法的初始值,最终得到最优或次优调度方案。
(1)设置遗传算法参数;(2)假定遗传算法结束条件;
(3)生成初始种群P(0),g=0; (4)计算P(0)中的个体适应值;
(5)反复执行,直到满足结束条件;
①根据个体适应值及选择策略确定P(g)内选择概率;
②进行PC交叉操作;
③ 进行Pm变异操作;
④计算P(g+1)中个体的适应值,g=g+1;
(6)P(G)从中选择适应能力强的个体,放入集合中,作为优化集合;
(7)对于集合中的每个优化解,将遗传算法求解结果转换为蚁群算法中的信息素值;
(8)设置蚁群算法控制参数;(9)设置蚁群算法结束条件;
(10)将m只蚂蚁散布到n个计算结点上;
(11)对蚂蚁的分配结果计算目标函数,选取当前的最佳解;
(12)更新计算结点的信息素值;
(13)若满足蚁群算法结束条件,退出;否则,返回执行步骤(10)。
三、总结
在云计算环境里调度计算是影响云计算能否成功的最重要的因素之一。由于资源在广域上分布,本质上异构,相异的存取和花费模式、负载和可用性动态变化,因此云计算环境下的任务管理十分复杂。在云计算系统中,如何协调和分配任务,这就是调度需要解决的问题。本文在广泛阅读国内外相关文献后,归纳云计算和任务调度方面的研究成果,提出基于DAG以及融合遗传算法和蚁群算法的动态云计算任务调度算法。
通过实验结果分析比较可以看出,本文提出的算法在运行性能上具有一定的优势,充分验证了算法的合理性和有效性。当然,在仿真环境的限制下,可能实验结果有细微的差别,但我们相信本文提出的算法不失为合理而有效的算法。
参考文献:
[1]Annie S W, Han Y et al.An incremental genetic algorithm approach to multiprocessor scheduling[J],2004,15(9):824-834
[2] Dorigo M,Gambardella L M.Ant colony system: A cooperative learning approach to the traveling salesman problem,IEEE Trans. Evolutionary Computation[J],1997,1(1):53-66
[3] HUI YAN,XUE-QIN SHEN et al. AN IMPROVED ANT ALGORITHM FOR JOBSCHEDULING IN GRID COMPUTING.IEEE Proceeding of the Fourth International Conference on Machine Learning and Cybernetics[C], Guangzhou, August 2005:2957-2961
[4] Foster I,Kesselman C,Tuccke. The Anatomy of the Grid:Enabling Scalable Virtual Organizations[J].International Joural of Supercomputer Application,2001;15(3):200-222
[5]I Foster,C Kesselman.Grid Services for Distributed System Integration[J].Computer,2002,35(6):37-46
[6] 孙玉涛,网格计算环境中的动态任务调度算法研究,云南师范大学硕士论文.2007
关键词:排课;NP;多约束条件;遗传算法
中图分类号:TP311文献标识码:A文章编号:1009-3044(2008)27-1958-02
Research on the Algorithms of the Course Scheduling System for College under the Multi-constrained Conditions
CHEN Xing-gang, MENG Xiang-jing, LI Jing, SONG Jian
(Electronic Science and Information Technology Institute, Guizhou University, Guiyang 550025 China)
Abstract:College course arrangement is a typical combinatorial optimization and NP-hard problem. As the current College Enrollment Expansion and consolidation trend, increasing the size of colleges and universities, the growing tension school resources, for teachers and students during school hours, school locations and other issues on the arrangements being bound by the conditions of a growing number of reality, This paper will adopt strategies to be one of the course arrangement of resources and constraints analysis, and then focus on the course arrangement commonly used in genetic algorithm.
Key words:course scheduling; NP; multi-constrained conditions; GA
排课是高校教学管理中的一项重要而且难度和复杂度都极高的基本工作。特别是近年来,随着我国高校的扩招和合并,学校的教学资源(如教室、实验室、语音室等)愈显紧张;同时,在学分制的制度下,课程的类别越分越多,有公共必修课、公共选修课、专业基础课、专业必修课、专业选修课等等;再者,上课的教师也会有一些特殊情况需要考虑。这样一来,排课人员在排课时倍感棘手,以至于开学后因排课问题还会影响到教学的正常进行。
目前,国内的许多高校都引进了不同智能化程度的排课软件,然而,其应用的效果都有些不尽如人意,虽然耗费了教务处工作人员大量的时间和精力,但遗留下的问题还是很多。
下面我们基于人工排课的宏观指导思想,列出约束限制条件,采用遗传算法,进行多轮次扫描计算,以改变目前的排课系统冲突多、调整应变能力弱,排课时间长的问题,从而求得合理性解。
1 排课时所受的约束限制条件
高校排课问题,它要求将课程、教师、班级安排在一个有限的时间和空间当中去,要求避免冲突且尽量满足一些其它条件,这实际上是五个相互制约的因素的组合优化问题。1975年,美国S.Even等人证明了高校排课问题也是一个NP(Non-deterministic Polynomial)难问题,即多项式复杂程度的非确定性问题,即找不到多项式时间求解算法。具体到高校排课系统的算法上,五个相互制约的因素它们所受到的约束限制条件有:
1) 不能在同一时间给同一位教师安排多个班级课程(合班除外) 或同时讲授多门课程。
2) 不能在同一时间给同一个教室安排多个班级上课(合班除外) 或多位教师授课。
3) 不能在同一时间给同一个班级安排多门课程或同时在不同的教室上课。
4) 不能在安排教室时使教室容纳人数小于上课学生人数。
5) 对于需要特殊场所的课程, 如体育课、实验课、语音教室等, 应安排相应地点或实验室上课。
以上是高校排课时必须满足的条件, 否则无法进行正常教学。在能够进行正常教学的情况下我们还应考虑到教学效果,学生学习效率, 教师、学生的便利等其他因素,因此,还要考虑一些尽量去实现的约束条件,这包括:
1) 一门课程的几次课在一周之内应间隔排列。
2) 上课人数尽量接近教室容量。
3) 排课时可注意文科类课程和理科类课程交叉安排,避免使学生产生倦怠感, 有利于提高学习效率。
4) 体育课最好不要安排在一天中的第1-2节, 并且在体育课后最好不要再安排其它课程, 保证教学效果。
5) 同一班级连续两次讲课之间更换教室尽可能少;同一课程的不同讲次尽量不换教室。
6) 不要在一天中给教师或学生安排太多课程, 最好不要连续上课超过 6 节, 有利于提高教学效果和学习效率。
2 排课问题描述
在排课问题中,我们的基本任务是将班级、教室、课程、教师安排在一周内且不发生时间冲突[2]。据此,对这五个相互制约的因素我们给出如下的描述:
学校有R间教室,C个班,S门课程,T位教师,P个时间段。
1) 教室集合R(R1,R2,…,Rr),每间教室分别可容纳(X1,X2,…,Xy)人;
2) 班级集合C(C1,C2,…,Cc),每个班级分别有(K1,K2,…,Kc)人,其中有x个班级上合班课;
3) 课程集合S(S1,S2,…,Ss),每门课对应Ci个班,1位教师,(1≤Ci
4) 教师集合T(T1,T2,…,Tt),每位教师对应Sm门课,Cc个班,(1≤Sm
5) 时间集合P(P1,P2,…,Pp),假设一周上五天课,每天分为五个教学单元,每个单元为2个课时,即上午2个,下午2个,晚上1个,则时间集合包含25个时间段。如11代表周一第一个教学单元,即周一1、2节,12代表周一第二个教学单元,即周一3、4节,以此类推,这些时间段构成一个时间集合P(11,12,13,…,55)。
3 算法研究
从20世纪50年代以来,国际上就有人着手研究应用计算机进行排课的问题。国外的研究表明,解决大规模的排课问题单纯依靠数学方法是行不通的,进入20世纪90年代以后,国外对排课问题的研究仍然十分活跃。国外目前较多采用着色算法、数学方法、模拟退火技术、禁忌算法、局部优化算法和遗传算法等。
3.1 遗传算法
遗传算法(Genetic Algorithm,GA)是一种有效的解决最优化问题的方法或计算模型。遗传算法的研究历史比较短,它出现在20世纪六、七十年代,主要是由美国Michigan大学教授John Holland与其同事、学生们通过对生物进化过程进行模拟,研究形成的一个较完整的理论和一种全新的概率优化方法。John Holland提出这一算法的最初目的是研究自然系统的自适应行为,并用于设计具有自适应功能的软件系统。随后经过20余年的发展,计算智能化己经作为人工智能研究的一个重要方向,以及后来的人工生命研究兴起,使遗传算法受到广泛的关注。目前,遗传算法作为具有系统优化、适应和学习的高性能计算和建模方法的研究渐趋成熟。
GA算法具有下述特点:
1) GA是对问题参数的编码组进行进货,而不是直接对参数本身。
2) GA的搜索是从问题解的编码组开始搜索,而不是从单个解开始。
3) GA使用目标函数值(适应度)这一信息进行搜索,而不需导数等其他信息。
4) GA算法使用的选择、交叉、变异这三个算子都是随机操作,而不是确定规则。
3.2 算法描述
利用遗传算法解最优化问题,首先应对可行域中的点进行编码(一般采用二进制编码),然后在可行域中随机挑选一些编码组作为进化起点的第一代编码组,并计算每个解的目标函数值,也就是编码的适应度。接着就像自然界中一样,利用选择机制从编码组中随机挑选编码作为繁殖过程前的编码样本。选择机制应保证适应度较高的解能够保留较多的样本;而适应度较低的解则保留较少的样本,甚至被淘汰。在接下去的繁殖过程中,遗传算法提供了交叉和变异两种算子对挑选后的样本进行交换。交叉算子交换随机挑选的两个编码的某些位,变异算子则直接对一个编码中的随机挑选的某一位进行反转。这样通过选择和繁殖就产生了下一代编码组。重复上述选择和繁殖过程,直到结束条件得到满足为止。进化过程最后一代中的最优解就是用遗传算法解最优化问题时所得到的最终结果。
用遗传算法解决组合优化问题的一般流程用数学语言描述如下:
1) 将待解决问题的相关参数进行编码;
2) 随机地初始化种群X(0)=(xl,x2,...,xm),其中m为群体规模;
3) 对当前代种群X(t)中的每个个体xi计算其适应度值f(xi),适应度值的大小体现了该个体性能的优劣;
4) 应用选择算子产生中间代X(t);
5) 对X(t)应用杂交、变异算子,产生新一代的种群X(t+l)。杂交和变异算子的目的在于扩展有限个体的覆盖面,体现全局搜索的思想;
f.进化到下一代,代计数器t加1。如果满足终止条件,则执行下一步7),否则转步骤3);
g.输出近似最优解。
相应的执行框图如图1所示。
参考文献:
[1] 朱莉娟,李冬.计算机排课问题中几种算法的探讨[J].新乡教育学院学报.2007,(9).
[2] 唐勇,唐雪飞,王玲.基于遗传算法的排课系统[J].计算机应用.2002,(1):93-94,97.
[3] 沈丽容,陈明磊.基于遗传算法的高校排课系统研究[J].计算机与信息技术,2006,(11).
[4] 石菁,李洪波.排课算法比较[J].福建电脑.2007,(8).
〔关键词〕知识图谱;专家系统;发展轨迹
DOI:10.3969/j.issn.1008-0821.2012.02.040
〔中图分类号〕G250.71 〔文献标识码〕A 〔文章编号〕1008-0821(2012)02-0159-08
Knowledge-based Expert System Development Overview MapLiao Yi
(Political Department,National University of Defense Technology,Changsha 410073,China)
〔Abstract〕Artificial intelligence expert system is the most important and most active areas of an application,which implements the artificial intelligence research from theory to practice,turning from the general reasoning strategies of a major breakthrough in the use of expertise.This chronological order,the expert system into the 1980s before the 1980s,1990s,2000,after four stages.Articles using bibliometric methods,analysis of the expert system development process,development and trends,pointing out that the current phase is the development of expert systems,expert systems into a variety of commercial operation,need to address the knowledge acquisition bottleneck,matching conflicts and other issues for expert systems to understand and master the subject structure,evolution,development and so provide an unique perspective and knowledge.
〔Key words〕knowledge maps;expert systems;the development trajectory
专家系统作为人工智能的一个重要分支,发展已经超过50年,在很多应用领域都获得了广泛使用,取得了丰硕成果。本文运用文献计量这一独特视角对专家系统进行了再回顾和再分析,将智能科技划分为初创期、成长期、低谷期、发展期,利用词频分析、共引分析、作者共现分析等方法揭示专家系统的学科结构、影响程度、关键节点与时间点等重要而独特的知识,为了解和掌握专家系统的发展与演化过程提供了独特视角。
1 数据来源
SCI(Science Citation Index)是美国科学情报研究所ISI(Institute for Science Information)出版的期刊文献检索工具,所收录的文献覆盖了全世界最重要和最有影响力的研究成果,成为世界公认的自然科学领域最为重要的评价工具。本文以Web of Science中的SCI数据库为数据来源,选用高级检索方式,以“Expert System/Experts System”作为主题词,于2011年5月在Web of Secience中进行检索,一共检索到14 500篇相关文献记录。获得的年度分布如图1。所示。虽然,专家系统研究从20世纪五六十年代就开始了,但是从图1可以看出直到1982年才有主题词与专家系统相关的论文出现。图1表明1991年左右,专家系统相关论文达到了峰值,但随后呈逐年下降的趋势。到1999年,只有494篇。但21世纪开始,专家系统相关论文又出现了增加的趋势,并维持在一个稳定的水平中。图1 专家系统在SCI数据库文献发表年度变化情况
2012年2月第32卷第2期基于知识图谱的专家系统发展综述Feb.,2012Vol.32 No.22 专家系统前40年的发展
本文利用基于JAVA平台的引文分析可视化软件Citespace,首先设定时间跨度为1950-1991年,时间切片长度为1年,聚类方式为共被引聚类(Cited Reference),阈值选择为(2,2,20)、(3,3,20)、(3,3,20)。Citespace得出这些引文的时间跨度为1950-1990年,可以绘制出该时间段的专家系统论文时区分布图,如图2所示。我们以年代先后为序,将20世纪80年代以前作为第一阶段,80年代至90年代作为第二阶段。图2 1950-1991年各年度专家系统论文之间的时区分布图
2.1 专家系统起源时期
根据图2显示,这段时期有7个突出节点,既有7位代表人物。第一个节点代表的是“人工智能之父”――英国著名科学家阿兰・麦席森・图灵(Alan Mathison Turing),他于1950年在《心灵》杂志上《计算机器与智能》,提出了著名的“图灵测试”,探讨了机器智能的可能性,为后来的人工智能科学提供了开创性的构思[1]。
第二个节点代表的是美国工程院院士、加州大学扎德(LA.Zadeh)教授,他于1965年在《信息与控制》杂志第8期上发表题为《模糊集》的论文,提出模糊集合理论,给出了模糊性现象定量描述和分析运算的方法,从而诞生了模糊数学。1978年,扎德教授提出了“可能性理论”,将不确定性理解为可能性,为模糊集理论建立了一个实际应用上的理论框架,这也被认为是模糊数学发展的第二个里程碑。同年,国际性期刊《International Journal of Fuzzy Sets and System》诞生,这使得模糊理论得到普遍承认,理论研究高速发展,实际应用迅速推广。
第三个节点代表的美国两院院士、卡内基-梅隆大学教授艾伦・纽厄尔(Allen Newell),1972年,他出版了《人怎样解题》(Human Problem Solving)一书,书中描述了他和西蒙试图建立一个计算机化的“通用问题求解器”的历程:20世纪50年代,他们发现,人类的问题解决,在一定知识领域内可以通过计算机实现,所以他们开始用计算机编程来解决问题,1956年,他们研发出了逻辑理论家和通用问题求解器(General Problem Solver),并建立了符号主义人工智能学派。我们可以看出,这本书是对他以前所作工作的总结与归纳,而逻辑理论家和通用问题求解器正是专家系统的雏形,为专家系统的出现奠定了坚实的基础。
但是艾伦・纽厄尔的尝试无法解决大的实际问题,也很难把实际问题改造成适合于计算机解决的形式,并且对于解题所需的巨大搜索空间也难于处理。为此,美国国家工程院院士、斯坦福大学教授费根鲍姆(E.A.Feigenbaum)等人在总结通用问题求解系统成功与失败的经验基础上,结合化学领域的专门知识,于1965年研制了世界上第一个专家系统dendral,可以推断化学分子结构。专家系统进入了初创期,其代表有dendral、macsyma(数学专家系统)等,第一代专家系统以高度专业化、求解专门问题的能力强为特点,向人们展示了人工智能应用的广阔前景[2]。
第四个节点代表人物是美国麻省理工学院著名的人工智能学者明斯基(Minsky)。1975年,他在论文《表示知识的框架》(A Framework for Representating Knowledge,McGraw-Hill)中提出了框架理论,框架理论的核心是以框架这种形式来表示知识。理论提出后,在人工智能界引起了极大的反响,并成为了基于框架的专家系统的理论基础,基于框架的专家系统适合于具有固定格式的事物、动作或事件。
第五个节点代表人物是美国普林斯顿大学教授格伦谢弗(Glenn Shafer),他在1976年出版了《数学理论的证据》(A mathematical theory of evidence)一书,介绍了由他和Dempster于1967年提出的D-S理论(即证据理论)。证据理论可处理由不知道因素引起的不确定性,后来,该理论被广泛应用于计算机科学和工程应用,是基于D-S证据理论的专家系统的理论基础。
第六个重要节点代表是美国斯坦福大学爱德华・汉斯・肖特利夫(Shortliff EH)教授,他于1975年在著名杂志《数学生物科学》上发表《A model of inexact reasoning in medicine》(《在医学模型的不精确推理》)一文,他结合自己1972-1974年研制的世界第一个医学专家系统――MYCIN系统(用于诊断和治疗血液感染及脑炎感染,是第二代专家系统的经典之作),提出了确定性理论,该理论对专家系统的发展产生了重大影响。
第七个节点代表人物是美国麻省理工学院计算机科学和人工智能实验室的戴维斯(Randall Davis)教授,他于1976年提出元知识的概念,并在专家系统的研制工具开发方面做出了突出贡献――研制出知识获取工具Teiresias,为专家系统获取知识实现过程中知识库的修改和添加提供了工具[3],关Teiresias,他于1977年在《Artificial Intelligence》杂志上中进行了详细介绍,而这也为本时期专家系统的快速增多和广泛应用奠定了坚实基础。
20世纪70年代后期,随着专家系统应用领域的不断开拓,专家系统研发技术逐渐走向成熟。但同时,专家系统本身存在的应用领域狭窄、缺乏常识性知识、知识获取困难、推理方法单一等问题也被逐渐暴露出来。人们从各种不同类型的专家系统和知识处理系统中抽取共性,人工智能又从具体研究逐渐回到一般研究。围绕知识这一核心问题,人们重新对人工智能的原理和方法进行探索,并在知识的获取、表示以及知识在推理过程中的利用等方面开始出现一组新的原理、工具和技术。
2.2 专家系统发展的黄金时期
20世纪80年代是专家系统突飞猛进、迅速发展的黄金时代,根据图2显示,这段时期共有论文982篇,有7个突出节点。
1980年,出现了第一个节点代表――美国斯坦福大学计算机科学系系主任尼尔森(NILS J.NILSSON),他出版的《人工智能原理》(《Principles of artificial intelligence》)一书,表明了拉近理论和实践的距离的目标,书中对基于规则的专家系统、机器问题解决系统以及结构对象的代表等都进行了具体的论述。
1981年,出现了第二个节点代表――英国赫特福德大学教授Clocksin,威廉F,他出版的《PROLOG语言编程》一书,引起了计算机科学界的极大兴趣,并已被证明是一个重要的编程语言和人工智能系统的新一代基础,是专家系统的重要编程语言。
1982年,出现了第三个节点代表――美国匹兹堡大学教授米勒(Miller RA),他在《英格兰医药分册》上发表了《基于计算机的医学内科实验诊断顾问》(An Experimental Computer based Diagnostic Consultant for General Internal Medicine.N Engl J Med,307,468-76,1982)一文,属当时诊断专家系统的代表力作,书中介绍了著名的内科疾病诊断咨询系统INTERNIST-1,之后将其不断完善成改进型INTERNIST-2,即后来的CADUCEUS专家系统,其知识库中包含了572种疾病,约4 500种症状。
1983年,出现了第四个节点代表――美国的海斯罗斯(Hayes-Roth,F)教授,他于1983年发表著作《建立专家系统》,对专家系统建立的原则和要素、开发的生命周期等重要问题进行了详细讲解,为研究与开发各种类型的专家系统提供了理论依据。
1984年,出现了第五个节点代表――美国匹兹堡大学计算机科学、哲学和医学教授布鲁斯・布坎南(Bruce G.Buchanan),他于1984年发表著作《规则的专家系统:斯坦福启发式编程项目Mycin实验》(《Rule Based Expert Systems:The Mycin Experiments of the Stanford Heuristic Programming Project》,这是有史以来关于医疗诊断系统MYCIN的实验规则库公布。基于规则的专家系统MYCIN是专家系统开发过程中一个里程碑,研究其开发思路与方法具有非常重要的意义。
1985年,出现了第六个节点代表――美国人工智能专家、加州大学教授哈蒙(Harmon P),他出版了《专家系统:人工智能业务》(《Expert systems:artificial intelligence in business》)一书。书中阐述了专家系统如何解决问题,代表知识,并得出推论,并介绍了人工智能的具体制度,确定了专家系统的市场。
1986年,出现了第七个节点代表――著名的专家系统学者沃特曼(Waterman DA),他出版了《专家系统指南》一书,该书对专家系统的概念、组成、建立过程、建立工具、应用领域等做了深入浅出的系统介绍与论述,是当时全面介绍专家研发与应用的经典书籍。
20世纪80年代初,医疗专家系统占主流,主要原因是它属于诊断类型系统且容易开发。80年代中期,出现大量投入商业化运行的专家系统,为各行业带来了显著的经济效益。从80年代后期开始,大量新技术成功运用到专家系统之中,使得专家系统得到更广泛的运用。在这期间开发的专家系统按处理问题的类型可以分为:解释型、预测型、诊断型、设计型等。应用领域扩展到农业、商业、化学、通信、医学等多个方面,成为人们常用的解决问题的手段之一。
然而,与此同时,现有的专家系统也暴露出了自身严重的缺陷,使不少计算机界的知名学者对专家系统产生了怀疑,认为专家系统存在的问题有以下几点:(1)专家系统中的知识多限于经验知识,极少有原理性的知识,系统没有应用它们的能力;(2)知识获取功能非常弱。为了建造专家系统,必须依赖于专家获取知识, 不仅费时, 而且很难获取完备性和一致性的知识;(3)求解问题的方法比较单一,以推理机为核心的对问题的求解尚不能反映专家从认识问题到解决问题的创造性过程;(4)解释功能不强[4]。等到学者们回过头重新审视时,20世纪90年代的专家系统理论危机已然爆发。
3 90年代专家系统向多个方向发展
由于20世纪80年代专家系统研究迅猛发展,商业价值被各行各业看好,导致90年代大批专家系统从实验室走出来,开始了它们的工程化市场化进程。从图1看以看出,在20世纪90年代,专家系统的相关论文不增反减,进入一个局部低谷期,这期间以“Expert System/Experts System”为主题词的论文共7 547篇。本文利用Citespace软件,设置参数为(4,4,20)(4,3,20)(4,4,20),获取了该时期论文的引文聚类图(如图3所示)。图2 专家系统1990-2000年的论文引文聚类图
从图3中我们可以看出,全图的节点比较分散,没有形成大的聚类,这表示该阶段没有形成重点研究方向,也没有重大科研成果和标志性著作产生,专家系统的市场化进程严重牵引了研究者们的注意力,这是专家系统研究陷入低谷期的重要原因。
这段时间专家系统的研究工作大致分以下几个方面:第一个研究方向依旧是建立在扎德(LA.Zadeh)教授模糊理论上的模糊专家系统,它同样是该年代专家系统研究的重点方向。
第二个研究方向是骨架专家系统,代表人物有美国斯坦福大学的爱德华・汉斯・肖特利夫(Shortliff EH)教授。1974年末,MYCIN系统基本建成后,MYCIN的设计者们就想到用其它领域的知识替换关于感染病学的知识,可能会得到一个新的专家系统,这种想法导致了EMYCIN骨架系统的产生。EMYCIN的出现大大缩短了专家系统的研制周期,随后,AGE、OPS5、KEE、KBMS、GESDE等骨架系统应运而生,它们在20世纪90年代专家系统的研究进程中,发挥着重要作用。
第三个研究方向是故障诊断专家系统,代表人物有美国麻省理工学院的兰德尔・戴维斯(Randall Davis)教授。他于1984年在《人工智能》杂志上发表了《基于结构和行为的诊断推理 》(《Diagnostic Reasoning Based on Structure and Behavior》)一文,该论文描述了一个利用知识结构和行为,在电子电路领域进行故障诊断排除的专家系统。之后,故障诊断专家系统在电路与数字电子设备、机电设备等各个领域已取得了令人瞩目的成就,已成为当今世界研究的热点之一。
第四个研究方向是基于规则的专家系统,布鲁斯・布坎南(Bruce G.Buchanan)的著作对基于规则的专家系统在这个时期的发展仍有着积极的指导作用。多种基于规则的专家系统进入了试验阶段。传统基于规则的专家系统只是简单的声明性知识,而目前,规则的形式开始向产生式规则转变,并趋向于提供较完善的知识库建立和管理功能。
第五个研究方向是知识工程在专家系统中的运用。代表人物是美国斯坦福大学的克兰西教授(Clancy W J),他于1985年在《人工智能》杂志上发表了重要论文《启发式分类》(《Heuristis classification》),启发式分类即对未知领域情况的类的识别过程。它是人类思维解决问题的重要方法,在人工智能、专家系统中可常用启发式设计计算机程序,模拟人类解决问题的思维活动。
第六个研究方向是机器学习在专家系统中的运用。代表人物是机器学习领域前辈、澳洲悉尼大学著名教授John Ross Quinlan。他于1986年在《机器学习》(《Mach.Learn》)杂志上发表《决策树算法》(《Induction of Decision Trees》)一文,文中他详细描述了决策树算法的代表――ID3算法。之后,有大量学者围绕该算法进行了广泛的研究,并提出多种改进算法,由于决策树的各类算法各有优缺点,在专家系统的实际应用中,必须根据数据类型的特点及数据集的大小,选择合适的算法。
第七个研究方向是神经网络专家系统,代表人物有人工智能专家Stephan I.Gallant和美国加利福尼业大学教授巴特・卡斯科(Bart Kosko)。Gallant于1988年在《ACM的通信》上发表了《连接主义专家系统》(《Connectionist expert systems》)一文,文中讲述Gallant 设计了一个连接主义专家系统(Connectionist expert system),其知识库是由一个神经网络实现的(即神经网络知识获取),开创了神经网络与专家系统相结合的先例。
第八个研究方向是遗传算法在专家系统中的运用。代表人物是遗传算法领域著名学者、美国伊利诺伊大学David Goldberg教授和人工智能专家L.Davis。1989年,Goldberg出版了专著《搜索、优化和机器学习中的遗传算法》,该书系统总结了遗传算法的主要研究成果,全面而完整地论述了遗传算法的基本原理及其应用;1991年,Davis编辑出版了《遗传算法手册》,书中包含了遗传算法在科学计算、工程技术和社会经济中的大量应用实例,该书为推广和普及遗传算法的应用起到了重要的指导作用。这些都推动了基于遗传算法的专家系统的研发推广。
第九个研究方向是决策支持系统在专家系统中的运用,代表人物是美国加利福尼亚大学伯克利分校教授埃弗雷姆・特班(Efraim Turban)。他于1990年出版了《决策支持和专家系统的管理支持系统》(《Decision support and expert systems:management support systems》)一书。20世纪80年代末90年代初,决策支持系统开始与专家系统相结合,形成智能决策支持系统,该系统充分做到了定性分析和定量分析的有机结合,将解决问题的范围和能力提高到一个新的层次。
第十个研究方向是各种理论知识在专家系统中的综合运用,代表人物是美国加利福尼业大学教授巴特・卡斯科(Bart Kosko)和美国伊利诺伊州研究所教授Abdul-Rahman K.H。卡斯科(Kosko)于1992年出版《神经网络和模糊系统:一个拥有机器智能的动力系统方法》(《Neural networks and fuzzy systems:a dynamical systems approach to machine intelligence》)一书,这是第一本将神经网络和模糊系统结合起来的读本,也是神经网络与模糊理论综合应用于专家系统建设的经典著作;Abdul-Rahman K.H教授于1995年,在美国电气和电子工程师协会的《电力系统及自动化》(《Transactions on Power Systems》)会议刊上发表了《人工智能模糊无功负荷的最优VAR控制方法 》(《AI approach to optimal VAR control with fuzzy reactive loads》)一文,论文提出了一个解决无功功率(VAR)控制问题,这个方法包含了专家系统、模糊集理论和人工神经网络的重要知识。
虽然专家系统大量建造,但投入实际运行的专家系统并不多,且效率较低,问题求解能力有待进一步提高。原因之一就是专家系统主要是模拟某一领域中求解特定问题的专家的能力,而在模拟人类专家协作求解方面很少或几乎没有做什么工作。然而在现实世界中,协作求解具有普遍性,针对特定领域、特定问题的求解仅仅具有特殊性,专家系统虽然在模拟人类专家某一特定领域知识方面取得了成功,但它仍然不能或难以解决现实世界中的问题。其次,开发的专家系统的规模越来越大,并且十分复杂。这样就要求将大型专家系统的开发变成若干小的、相对独立的专家系统来开发,而且需要将许多不同领域的专家系统联合起来进行协作求解。然而,与此相关的分布式人工智能理论和实用技术尚处在科研阶段。只有分布式系统协作求解问题得以解决,才能克服由于单个专家系统知识的有限性和问题求解方法的单一性等导致系统的“脆弱性”,也才能提高系统的可靠性,并且在灵活性、并行性、速度等方面带来明显的效益[5]。
4 21世纪专家系统进入稳定发展时期
进入21世纪,专家系统开始缓慢发展,这期间以“Expert System/Experts System”为主题词的论文共5 964篇。本文利用Citespace软件,设置参数为(6,6,20)(5,5,20)(5,5,20),获取了该时期论文的引文聚类图(如图4所示)。图4 专家系统2000-2010年的论文引文聚类图
这个时期专家系统有3个主要研究方向:第一个是研究方向是节点明显的基于模糊逻辑的专家系统研究方向。90年代以来,模糊控制与专家系统技术相结合,进一步提高了模糊控制器的智能水平。基于模糊逻辑的专家系统有以下优点:一是具有专家水平的专门知识,能表现专家技能和高度的技巧以及有足够的鲁棒性(即健壮性);二是能进行有效的推理,能够运用人类专家的经验和知识进行启发性的搜索和试探性的推理;三是具有灵活性和透明性。
第二个是研究方向是Rete模式匹配算法在专家系统中的应用,代表人物是美国卡内基―梅隆大学计算机科学系的Charles L.Forgy教授,1979年,他首次提出Rete算法。专家系统工具中一个核心部分是推理机,Rete算法能利用推理机的“时间冗余”特性和规则结构的相似性,并通过保存中间运算结果的方法来提高推理的效率。1982年,他在《人工智能》杂志上发表《Rete算法:许多模式/多对象的模式匹配问题的一个快速算法》(《Rete:A Fast Algorithm for the Many Pattern/Many Object Pattern Match Problem》)一文,该文解释了基本算法的概念,介绍了详细的算法,描述了模式和适当的对象交涉算法,并说明了模式匹配的执行操作。
第三个是研究方向是专家系统在电力系统中的运用。世界各国的专家们开始热衷于在电力生产的各个环节使用专家系统,代表人物有日本的福井贤、T.Sakaguchi、印度的Srinivasan D、美国伊利诺伊州研究所的Abdul-Rahman K.H、希腊雅典国立技术大学的Protopapas C.A、和中国的罗旭,他们在美国电气和电子工程师协会的《电力传输》(《IEEE transactions on power delivery)会议刊及《电源设备系统》会议刊(《On Power Apparatus and Systems》)上发表了多篇有影响力的论文,内容涉及系统恢复、电力需求预测、变电站故障诊断和报警处理等多方面。
这十年间,专家系统的研究不再满足于用现有各种模型与专家系统进行简单结合,形成基于某种模型的专家系统的固有模式。研究者们不断探索更方便、更有效的方法,来解决困扰专家系统的知识获取瓶颈、匹配冲突、组合爆炸等问题,而这也推动了研究不断向深层次、新方向发展。但是,由于专家系统应用的时间长、领域广,他们遭遇的瓶颈问题一时得不到有效解决,导致了这一时期末,专家系统研究呈现出暂时的下滑现象。
5 专家系统发展趋势分析
图一发展曲线上第二个时间节点是1992年,从该年起专家系统相关论文呈下降趋势,然后在2002年又开始缓慢增长,近一年多来又开始下降,这标志着专家系统研究在布满荆棘的道路上前行,前景是光明的,但道路是曲折的。本文以5年为一个单位,统计了1990-2009年20年期间专家系统相关论文中高频词的变化情况,如表1所示,从该表可以获得这个时期专家系统研究的一些特点。
(1)在1990-1999年期间,人工智能出现新的研究,由于网络技术特别是国际互连网技术发展,人工智能开始由单个智能主体研究转向基于网络环境下的分布式人工智能研究,使人工智能更加实用,这给专家系统带来了发展的希望。正因为如此,我们从词频上可以看出,人工智能(artificial intelligence)一词在这十年一直位居前两位,在专家系统研究中处于主导地位,而与其相关的知识表示(knowledge representation)、知识获取(knowledge acquisition)等,也成为了学者们研究的重点方向。
(2)该时期的第二个特点是神经网络研究的复苏。神经网络是通过模拟人脑的结构和工作模式,使机器具有类似人类的智能,如机器学习、知识获取、专家系统等。我们从词频上可以看出神经网络(neural network)一词得以快速增长,1995年时位列第一,进入21世纪也是稳居第二位,神经网络很好地解决了专家系统中知识获取的瓶颈问题,能使专家系统具有自学习能力,它的出现为专家系统提供了一种新的解决途径[6],同时也显示出他独有的生机与活力。
(3)该时期是模糊逻辑的发展时期。模糊理论发展至今已接近三十余年,应用范围非常广泛,它与专家系统相结合,在故障诊断、自然语言处理、自动翻译、地震预测、工业设计等方面取得了众多成果。我们从词频上可以看出,模糊逻辑(fuzzy logic)一词,除在1990-1994年期间位居第六位外,之后都位居前三甲,2000-2004年期间更是位列第一。模糊控制与专家系统技术相结合,进一步提高了模糊控制器智能水平,这种控制方法既保持了基于规则的方法的价值和用模糊集处理带来的灵活性,同时把专家系统技术的表达与利用知识的长处结合起来,能处理更广泛的控制问题。
(4)故障诊断成为专家系统研究与应用的又一重要领域。故障诊断专家系统的发展起始于20世纪70年代末,虽然时间不长,但在电路与数字电子设备、机电设备等各个领域已取得了令人瞩目的成就,已成为当今世界研究的热点之一。这从高频词分布可以开出,故障诊断(fault diagnosis)从1995-1999年间的最后一位攀升至2005-2009年间的第一位,足见其强大的生命力。在专家系统己有较深厚基础的国家中,机械、电子设备的故障诊断专家系统已基本完成了研究和试验的阶段,开始进入广泛应用。
(5)遗传算法的应用逐渐增多。20世纪90年代,遗传算法迎来了发展时期,无论是理论研究还是应用研究都成了十分热门的课题。尤其是遗传算法的应用研究显得格外活跃,不但应用领域扩大,而且利用遗传算法进行优化和规则学习的能力也显著提高。进入21世纪,遗传算法的应用研究已从初期的组合优化求解扩展到了许多更新、更工程化的应用方面。这在高频词分布中可以看出,以2000作为临界点,遗传算法(genetic algorithms)从20世纪90年代的10名之后,到位于高频词前六强之中,充分反映出它发展的良好势头。
6 小 结
专家系统是20世纪下半叶发展起来的重大技术之一,它不仅是高技术的标志,而且有着重大的经济效益。“知识工程之父”E.Feignbaum在对世界许多国家和地区的专家系统应用情况进行调查后指出:几乎所有的ES都至少将人的工作效率提高10倍,有的能提高100倍,甚至300倍[7]。
专家系统技术能够使专家的专长不受时间和空间的限制,以便推广稀缺的专家知识和经验;同时,专家系统能促进各领域的发展,是各领域专家专业知识和经验的总结和提炼。
专家系统发展的近期目标,是建造能用于代替人类高级脑力劳动的专家系统;远期目标是探究人类智能和机器智能的基本原理,研究用自动机模拟人类的思维过程和智能行为,这几乎涉及自然科学和社会科学的所有学科,远远超出了计算机科学的范畴。
随着人工智能应用方法的日渐成熟,专家系统的应用领域也不断扩大。有人类活动的地方,必将有智能技术包括专家系统的应用,专家系统将成为21世纪人类进行智能管理与决策的工具与助手。
参考文献
[1]百度百科[EB].http:∥baike.省略/view/2130.htm.
[2]黄可鸣.专家系统二十年[J].计算机科学,1986,(4):26-37.
[3]路耀华.思维模拟与知识工程[M].北京:清华大学出版社,1997.
[4]赵致琢.专家系统研究[J].贵州大学学报:自然科学版,1990,(6):40-48.
[5]邹光宇.专家系统发展现状及其应用前景[J].电力勘测,1994,(3):21-26.
论文摘要: 从现有安全设施来看,TDCS网络系统安全体系初步形成。但是,随着计算机网络的日益普及,各种安全威胁和计算机病毒也随之而来。现有的网络安全系统虽然起到一定的防护作用,但并不能完全解决整个骨干网络的系统安全问题。因此,拟采用基于遗传算法和神经网络的入侵检测技术,结合遗传算法和神经网络各自的优点,加强对TDCS网络的监视和防护。
1 TDCS网络安全状况
1.1 TDCS网络安全现状
TDCS(TrainOperation Dispatching Command System)是覆盖全路的列车调度指挥管理系统,分为铁道部、铁路局和车站三级建设,能及时、准确地为全路各级调度指挥管理人员提供现代化的调度指挥手段和平台,是铁路运输调度指挥现代化建设的标志。但是,随着计算机网络的日益普及,各种安全威胁和计算机病毒也随之而来,这就导致TDCS网络存在着安全隐患。
1.2 TDCS网络安全存在的问题
在TDCS网络中主要存在着以下几方面安全问题:1)间接来自于互联网的病毒威胁;2)操作系统的安全威胁;3)应用软件的安全威胁;4)计算机设置的安全隐患;5)实时监控能力弱。
2 TDCS网络安全防护
2.1 TDCS网络目前采取的安全防护措施
针对TDCS网络存在的安全问题,结合各种技术和方法,目前全路系统信息安全防护体系采取的措施有:
1)防火墙系统。防火墙技术是实现子网边界安全的重要技术。首先路由器将对网络层安全进行初步保证,但路由器的访问控制列表只能作为防火墙系统的一个重要补充,只能通过防火墙系统来实现复杂的安全控制。
2)身份认证系统。由于TDCS人员结构复杂,用户众多,安全意识参差不齐,所以用户的工作内容也不尽相同,对于如此重要的系统,目前采用的以静态密码为主的身份认证系统带来的安全威胁是非常严重的,会造成比较大的安全风险。为了解决此类安全隐患,实用动态口令对TDCS用户进行身份认证是非常必要的。
3)网络防病毒系统。根据对病毒来源的分析,TDCS网络防病毒系统主要体现在以下三个方面:第一,防病毒集中统一管理,就是在铁路局内部安装防病毒软件管理系统,对所有客户端防病毒软件进行统一管理;第二,服务器病毒防护,就是对各种服务器进行病毒扫描和清除;第三,桌面防毒防护,就是对各项桌面系统软件进行病毒扫描和清楚。
4)入侵检测系统。入侵检测的主要功能是控制对网络的非法控制,通过监视、限制通过网络的数据流,防止外对内、内对外的非法访问,隔离内部网和外部网,为监视TDCS局域网安全提供便利。
5)安全漏洞评估系统。
2.2 TDCS网络采用入侵检测进行防护的好处
通过以上介绍,我们不难发现,在TDCS网络安全体系中,入侵检测系统是唯一一个通过数据和行为模式判断其是否有效的系统。
形象地说,入侵检测系统就是网络摄像机,能够捕获并记录网络上的所有数据,同时它也是智能摄像机,能够分析网络数据并提炼出可疑的、异常的网络数据,它还是X光摄像机,能够穿透一些巧妙的伪装,抓住实际的内容。此外,它还是保安员的摄像机,能够对入侵行为自动地进行反击,如阻断连接。
在TDCS网络中引入入侵检测技术,主要是实现对网络的非法控制,通过监视、限制通过网络的数据流,给网络系统提供对外部攻击、内部攻击和误操作的安全保护,为监视TDCS局域网安全提供更多便利。
3 基于遗传算法和神经网络的入侵检测系统
3.1 传统的IDS存在的问题
1)准确性差。传统的统计方法需要依赖于一些假设,如审计数据(或用户行为)的分布符合高斯分布,实际上用户行为具有随机性,这些假设有时可能无效,从而导致较高的错误率。
2)灵活性差。传统的IDS对攻击特征的刻画只能是某些固定的序列,但现实中的入侵者利用的手段往往是有变化的,而要在入侵模式库中反映出所有可能的变化是不可能的。
3)适应性差。入侵者的攻击方法是在不断发展的,但传统的入侵检测系统无法有效地预测和识别新的攻击方法,使系统的适应性受到限制。
3.2 采用基于遗传算法的神经网络IDS的好处
将遗传算法全局搜索最优和传统神经网络局部寻优结合起来,取长补短,既可以减小遗传算法的搜索空间、提高搜索效率,又可以较容易地收敛到最优解,为求解多目标优化问题提供了新的策略。
4 结束语
目前在TDCS网络安全系统中采用的IDS一般都是基于神经网络技术的,由于神经网络的设计主要依据设计者的经验在大样本空间反复实验来进行选取,尚无理论上的指导,因此在神经网络的初始连接权以及网络结构的选择上具有很大的随机性,很难选取具有全局性的初始点,因而网络求得全局最优的可能性小。本文提出的技术很好的克服了这些缺点,较好地解决了问题。
参考文献:
[1]铁道部运输局,铁路列车调度指挥系统,北京:中国铁道出版社,2006.10.
[2]高丽,铁路站段计算机网络故障解决方法[J].铁路计算机应用,2006,13(9):13-16.
[3]周明孙、树栋,遗传算法原理及应用,北京:国防工业出版社,1999.
[关键词]拉链检测;背光照明;图像分割;遗传算法;
中图分类号:TB 文献标识码:A 文章编号:1009-914X(2015)23-0197-01
引言
目前拉链生产企业一般采用人工方法进行检测,这种检测方法,效率低、成本高、劳动强度大,拉链容易出现多齿、少齿、链齿分布不均等缺陷。本文提出一种新的自动检测拉链是否存在多齿、少齿缺陷的拉链智能检测方案。该方案采用白光LED背光照明技术使得采集的图像背景与拉链呈现对比明显的两色,采用中值滤波算法滤去干扰噪声,通过改进的Otsu法获取拉链图像阈值,然后进行图像二值化分割,并对处理后的图像采用拉链间距的判别方法进行识别判断。
1 光源照明技术
图像采集处理系统中常用的光源有白炽灯、卤素灯、碘钨灯、气体放电灯和发光二极管[1] 等,照明方式有直接照明、背光照明、暗视场照明、散射照明和同轴照明等。光源与照明方式的配合不仅要照亮物体,还要尽可能地突出物体特征量,使物体待检测区域与其它区域产生明显的区别[2],以便特征的提取和判断。通过对多种光源及照明方式的实验,本方案采用白色LED背光照明,其具有拉链背景均匀单一,拉链与背景呈现分明的两色,拉链轮廓清晰等优点,并且不存在直接照明产生的阴影及金属拉链反光等问题。
2 图像处理算法
2.1 灰度变换
彩色图像包含大量的颜色信息,直接对真彩图像进行处理会耗费较多的时间。为了提高图像处理速度,同时又不损失感兴趣区域的细节信息,通常将彩色图像变换为灰度图像。
2.2 图像滤波
在拉链图像采集的过程中,由于摄像头、光源、电磁干扰、机械振动等影响,采集的拉链图像存在着噪声干扰。中值滤波可以在去除点、线噪声的同时很好地保护图像的边缘,对抑制图像中的脉冲噪声和椒盐噪声特别有效[3],拉链图像中的噪声主要是椒盐噪声,本文案采用中值滤波法对灰度化后的拉链图像进行滤波处理。
2.3 基于遗传算法的Otsu阈值分割
Otsu阈值分割法不需要先验知识,且算法简单、分割质量好等优点[4],非常适合于目标与背景两类的图像分割问题,但其求解过程计算量大,本文将遗传算法引入Otsu阈值求解过程中,利用遗传算法所具有的快速寻优的特点,以缩短计算时间。
3 检测方案
在密闭暗箱中采用白光LED背光照明技术对拉链图像进行采集,采集的拉链图像拉链为黑色、背景为白色,拉链轮廓清晰,对比度高。为了验证该方案的检测效果,在实验过程中采用了两幅拉链图像:一幅正品拉链图像,一幅次品拉链图像,如图1所示。为提高处理速度,方便拉链图像的二值化处理,采用加权平均值法对采集的拉链图像进行灰度化处理。由于加权平均值算法中的权值都是浮点数,采用加权平均值法处理速度较慢,对此提出了改进算法。
对分割后的二值图像从左至右进行扫描,统计拉链间距的个数,并记录各个间距的值,计算链齿间距与链齿间距均值的误差和相邻链齿间距的误差,如果误差都在一定范围内则认为拉链是正品,否则就是次品。该方案采用了首次阈值计算采样,即计算第一帧采集的拉链图像的阈值并保存为标准阈值,后续图像分割只需要调用该阈值即可,减少了系统处理时间。
4 试验结果分析
整个检测方案在HHARM2410开发平台上予以实现,实验表明该方案可以准确地检测出拉链多齿、少齿、链齿分布不均的缺陷,从而判断出正品拉链和次品拉链。
图2是对图1所示的拉链采用白光LED背光照明采集得到的拉链图像,从采集的效果可以看出无论什么材质或颜色的拉链采用背光照明后,拉链都是黑色的,拉链和背景对比分明、轮廓清晰,不存在反光和暗影等缺陷,使得该方案具有较强的通用性,能够对多种类型的拉链进行处理。
采用改进的加权平均值法对图2进行灰度化处理,并采用中值滤波算法对灰度化图像进行滤波处理后的图像如图3所示,从处理结果可以看出中值滤波法很好地滤除了拉链图像中的椒盐噪声。
该实验中分别采用Otsu法和基于遗传算的改进Otsu法对滤波后的灰度图像进行阈值求取,表1给出了用两种方法求取的阈值和所用的时间,从表可以看出两种算法求得阈值相同,但引入遗传算法后的改进Otsu法处理时间有所缩短,系统的处理速度得到提高,本文采用基于GA的Otsu法对拉链图像进行分割,分割后的二值图像如图4所示,由分割结果可以看出目标与背景错分几率低,边缘清晰,噪声少。
5 结论
实验结果表明该方案能够对多种拉链自动提出特征并进行处理判断,可以准确地检测拉链多齿、少齿、链齿分布不均的缺陷,具有较高的处理速度和通用性。
参考文献
[1] 高峰. 图像处理技术在啤酒瓶在线检测系统中的应用[D]. 西安工业大学硕士学位论文. 2011.
[2] 刘圣. 工业图像检测系统关键技术的研究及应用[D]. 上海交通大学硕士学位论文. 2007.
关键词:Java 实践教学 实践能力 创新能力 教学方法
文章编号:1672-5913(2011)18-0012-04 中图分类号:G642 文献标识码:B
基金项目:甘肃政法学院青年科研基金项目(GZF2010XQNLW53)。
Java课程是应用实践性的课程。长期教学经验说明,单纯的“理论+程序演示”的理论教学方法以及 “学生自主实验+教师随堂指导”的实验教学方法存在着一些缺陷,表现为学生创新能力的欠缺和自主实践能力较差。
教学过程是一个系统过程,涉及到该门课程的所有教学和实践环节,其中任意一个环节的薄弱都会导致学生实践和创新能力培养效果不佳。因此,Java理论教学环节、实验教学环节、学期课程设计、学年论文(设计)、毕业论文(设计)环节、学科竞赛环节、校外实践环节等方面都是培养学生实践和创新能力的关键环节。
以贯穿Java教学整个过程的各个重要环节为切入点,从细节入手,扎扎实实落实好每一个关键环节,是保证培养学生的Java实践和创新能力的根本。
1 在理论教学环节中培养学生的实践和创新能力
1.1 以问题和实际项目为核心,采用以线带点的教学模式
需求是创新和应用成果产生的动力和源泉。传统的Java教材和教学内容是按知识点为模块组织的,即一个知识点,一个针对该知识点的例题,这样虽然有利于学生循序渐进地学习和掌握各个基本知识点
及其用法,但这种教学方法,有时会导致学生一听就会,一用就忘。其原因在于,学生从根本上并没有掌握该知识点到底有什么用,只是听懂了那道例题而已,没有深层的理解和举一反三的能力,学过时间不久,就会全然忘记。当学生遇到一个实际问题时,就会束手无策,不能将当时上课时感觉已经“掌握得很好”的各个知识点进行融会贯通和综合运用。因此,教师在教学中要运用几个能贯穿大部分教学知识点的综合实例和实际应用项目,有说服力地说明贯穿在其中的各知识点的重要性和用法。经过较长时间的检验,这种教学方法的优点是:其一,可以提高课堂教学的趣味性;其二,可以减少学生在学习各个知识点时的茫然和困惑;其三,可以提高学生综合各个知识点,形成知识网络,进而进行实际问题解决的能力。
所谓“以线带点”是以问题和实际项目为主线,贯穿各个分散的Java知识点,完成Java知识点的脉络化。
1.2 以学生为主体,教师为主导
在以往教学过程中,限于课时,“满堂灌”现象仍时有发生,结果是教学任务完成了,但学生的主体地位没有体现出来,没有充分参与到教学过程中,积极性不高,教学效果受到很大影响。为了克服这一点,“互问互答”的启发式和讨论式教学是一种好方式,这样可以最大程度地调动学生学习积极性和主动性,也有利于让学生在教学过程中保持精力集中的良好状态,长期以来可以培养学生创造性思维能力。教师在教学过程中,从一个较高的高度引导学生如何学习知识,提高学生学习效率和获取新知的能力,真正实现教学相长。
1.3 开拓视野,编写高效的程序
在讲授类创建方法的时候,教师除了讲授用传统的“new类构造方法”的方式外,可以介绍运用java.lang包中Class类的forName方法创建类对象[1],同时介绍运用Java设计模式中的“工厂模式”进行类对象的创建,并比较几种创建类对象方法的异同,从而培养学生运用多种方法解决同一问题的能力。
引导学生在算法设计上下功夫,一个实用软件的开发,往往需要编写高效率的算法,因此,算法的设计在Java程序教学中仍然是非常重要的。但由于课时有限,不可能占用较多课时来弥补学生在算法方面的不足,可以做到的是,引导学生总结和复习先修的算法设计课程以及其他程序设计课程中所学的算法设计知识,借助Java程序进行实现,并比较效率;介绍一些智能算法如“遗传算法”的设计和实现的相关知识,帮助学有余力的学生运用这些智能算法进行实际问题的解决,将非常有助于提高学生创新能力的培养。
2 注重实验教学课堂的效率
Java实验教学是Java教学的重要组成部分,更是提高学生动手能力和创新能力的重要途径。
2.1 落实实验预习
一般情况下,实验课时是2学时,这对于一个较大的实验项目来说,根本没有可能在2个实验学时中完成,因此,提前布置实验任务并督促学生按期完成非常重要。如一个JSP项目“学生成绩管理系统”的综合实验项目,应让学生在做该实验项目之前,就基本完成系统的设计及大部分的编码工作。在实验课堂中,主要是配置好开发环境和调试系统,在指导教师的指导下解决遇到的问题并按指导教师的要求做进一步的改进和完善。
2.2 检验实验效果
指导教师对于学生的实验成果应及时检查和提问,及时发现每个学生在做实验项目时遇到的问题以及该生对该实验理解、设计和实现的程度。
3 重视课程设计、学年论文设计与实践
Java课程设计是在学生学习完Java程序设计课程后对其进行的一次全面的综合练习和考查。课设成绩将作为本课程的期末考核成绩的重要组成部分。通过课程设计,使学生能够得到较系统的技能训练,从而巩固和加深对Java编程的基础理论知识的理解,培养学生综合运用所学知识解决实际问题的能力,使学生成为具有扎实的理论基础和较强的独立动手能力的应用型人才。
3.1 注重题目设计的目标性和归类
针对不同的Java应用,将课程设计题目合理归类,如“基于Java SE的桌面应用系统”类、“基于Java EE的Web应用开发系统”类、“基于Java ME的移动设备系统”类等。从而做到有针对性。
在指导学生选题时,告诉学生在完成该题目时,可以在哪些方面有创新点和亮点,并将这些创新点的完成情况作为评价课程设计成绩的重要依据。
3.2 强调学生所做项目的实用性和原创性
以往学生所做的课程设计、学年论文设计与实践项目大都源于教师指定的题目,而这些题目往往都是一些虚拟项目如“XX项目的设计与实现”,题目本身比较含糊,导致学生无法进行具体的需求分析,只能造出一个“需求分析和开发背景”。这样的项目完成后,即使做得比较“完美”,也是离实际应用较远,不能投入实际应用。
培养学生求真务实、追求原创的素养,克服浮躁情绪,避免仅为完成任务抄袭他人项目成果。在教学过程中,经常发现部分学生将资料查阅变成了“复制―粘贴”:不去汲取他人项目成果中的精华,也不去做任何改进,直接原封不动地套用。结果自己在“实
践”过程中不但没有学到任何知识,积累任何开发经验,反而养成了不劳而获,抄袭剽窃的坏习气。因此,在引导学生进行项目实践的过程中,在对其进行各阶段指导和检查时必须严格把关,引导和帮助学生树立良好的专业道德素质和研发精神。
4 毕业论文环节的创新能力培养
4.1 设计、指导与完成创新性、研究性题目
在前些年的毕业论文选题中,较多见的是:“基于Java SE的XX系统的设计与实现”,“基于JSP的XX系统的设计与实现”等。目前这类题目作为计算机本科生毕业论文题目,有以下一些弊端:
1) Java的开放资源非常多,以这类命题的网络及参考书资源、甚至整个软件设计开发背景、设计过程、实现过程、实现的全部源码都有现成的。
2) 虚拟项目较多,大都是自圆其说,如对系统的设计和开发背景是自定的,而不是源于实际用户的实际开发要求。学生在完成过程中,没有与用户沟通和交流的机会,没有反复满足用户具体、特殊要求的过程,从而导致学生没有通过想办法、找妙招来解决问题的磨砺过程。
3) 若有两个以上的学生选择了题目不同,但实际设计和实现过程大同小异的题目,就不能保证一人一题的原则。
毕业论文与设计是对本科生本科学习知识的大检阅,也是对本科生学术研究能力、分析和解决实际问题能力的重要培养环节,也是为本科生将来深造和从事研发相关工作所作的一个铺垫。为了突出毕业论文(或设计)环节中对学生创新能力的培养,在毕业论文的选题上,指导教师应进一步把关,设计出具有实际开发背景、创新性和一定研究性的题目。
4.2 注重对现有软件包的二次开发
基于Java的用于各种研究和实践的软件包有很多,以基于Java的多Agent开发工具包JADE(Java Agent Development Framework)[2]和遗传算法工具包JGAP(Java Genetic Algorithms Package)[3]为例,说明
利用基于Java的工具包进行二次开发来培养学生创新能力的实例。
对于基础较好、有较强科研兴趣的学生,可以引导其运用诸如JADE这样的多Agent系统开发工具包开发简单实用的多Agent系统,从而带动学生学习和研究多Agent系统的理论和实践方法。遗传算法是当前应用广泛地智能算法之一,而基于Java语言的遗传算法工具包JGAP中已实现了简单遗传算法和部分高级遗传算法的基本框架,可以引导学生快速在其基础上完成一些改进和在开发,最终达到学生理解遗传算法基本理论和实际应用的目的。
5 以竞赛高度为标杆,促进学生进行高层次编程训练
Java竞赛题目具有很强的新颖性和挑战性,其目的在于考察参赛学生的创造性解决实际问题的能力和编程思维。引导学生参与各级各类的Java编程竞赛或以历届竞赛题目作为训练,都能达到提高学生的创新意识和能力以及培养拔尖学生的目的。
6 产学研结合
6.1 创新实验室和基地建设
为了使学生具有快速适应市场Java人才的需求、能够独立创业的目的,根据学校客观条件的不同,建立一定规模的创新实验室或联系实验基地尤为重要。这是因为:
1) 较大型工程实践项目的开发都需要一个较长的周期,一般为3~5个月或更长。对参与完成项目的学生的训练和培养也需要一个较长的周期。而普通和短期的实验项目训练无法达到培养学生独立承担实际工程项目的能力。
2) 在对学生进行训练和实际项目的开发过程中,不可能占用正常的上课时间,而是充分利用课外、周末以及节假日的课余时间,有教师指导团队对学生进行辅导、训练和协同项目开发。
3) 一个固定而且全天候的实验场所和一定数量、档次的仪器设备是能否完成创新性实验和实际项目开发的重要保障。
6.2 承接软件开发项目,为学生走向市场奠定基础
由指导教师牵头,分析和研究市场对Java编程人员的需求,有针对性地承揽学校及校外的应用开发项目,组建以学生为主体的项目开发小组,进行项目开发。
6.3 进入课题组,锻炼科研能力
指导教师带领学生进入创新实验室,共同开展和完成Java相关的科研、教学改革和实践项目,让参与项目的学生体验科研过程,学习科研方法,培养科研精神。
7 教学中应用系统科学方法
系统科学方法理论是计算机科学与技术的重要的方法论之一[4]。面向对象编程思想和软件工程是系统科学方法在软件开发中的集中体现。在学生的
实践教学各个环节中,往往会做一些类似于“XX信息系统的设计与实现”之类的项目。但学生在实践过程中,急于求成,只关注系统的实现,一开始就写源码,不注重按软件工程理论和方法进行系统分析和设计,也不注重系统中类的设计和类间关系的设计,是导致项目开发失败或脱离实际应用的重要原因。更严重的是,这样的开发习惯一旦养成,将会被学生带到今后的实际项目开发中,情况会更加糟糕。
8 结语
通过长期的Java教学实践,笔者总结出“学生实践和创新能力培养效果的好坏取决于每个教学环节完成好坏”的结论。从细节入手,扎扎实实完成好每一个教学环节,不仅可以培养学生实践和创新能力,而且可以帮助学生养成良好的学习、研究习惯并为学生就业奠定坚实基础。
参考文献:
[1] 耿祥义,张跃平. Java 2实用教程[M]. 3版. 北京:清华大学出版社,2006: 95.
[2] Carie G. JADE TUTORIAL:JADE PROGRAMMING FOR BEGINNERS[EB/OL]. [2011-03-07]. /doc/ JADEProgramming-Tutorial-for-beginners.pdf.
[3] Java Genetic Algorithms Package[EB/OL]. [2011-03-07]. .
[4] 董荣胜,古天龙. 计算机科学与技术方法论[M]. 北京:人民邮电出版社,2002:117.
On Students’ Practicing and Creative Ability Training in Java Teaching
LI Ruisheng
(College of Computer Science, Gansu Institute of Political Science and Law, Lanzhou 730070, China)
【Abstract】Based on the concepts of genetic algorithm and BP neural network,the paper studies the optimization of BP neural network algorithm, and the effectiveness of the algorithm is verified by an example.
【关键词】遗传算法;BP神经网络;优化算法
【Keywords】genetic algorithm; BP neural network; algorithm optimization
【中图分类号】TPl83 【文献标志码】A 【文章编号】1673-1069(2017)04-0135-02
1 引言
神经网络是一种模仿动物神经网络行为特征,进行分布式并行信息处理的算法数学模型,凭借着复杂的系统结构,通过对系统内部节点连接关系的调节,实现对信息的高效处理。作为技术最为成熟的神经网络模拟,BP神经网络具有良好的自学习、自适应以及泛化能力,在许多领域中都有着广泛的应用。而针对BP神经网络在应用环节存在的问题,需要采取相应的优化算法,提升神经网络的收敛速度和理能力。
2 遗传算法与BP神经网络
遗传算法遵循的是生物界中适者生存的法则,其基本原理,是指将问题参数进行编码,形成染色体,通过迭代的方式,运用选择、变异、交叉等运算,对种群中染色体的信息进行交换,继而形成能够满足优化目标的染色体。
BP(Back Propagation)神经网络最初产生于1986年,属于一种依照误差逆传播算法训练的多层前馈网络,也是当前技术条件下应用最为广泛的神经网络模型之一,其可以对输入-输出模式的映射关系进行学习和存储,同时不需要对能够揭示这些映射关系的方程进行描述。神经网络具备自适应和自组织能力,在进行学习和训练的过程中,可以通过改变突触权重值的方式,更好地适应周边环境的变化。在同一个神经网络中,如果内容不同,学习方式不同,则会产生不同的功能。人工神经网络从本质上看,更加接近具备自主学习能力的系统,可以通过不断的学习,超出最初设计的知识水平。在人工神经网络中,比较常见的学习方法有两种,一是有监督的学习,可以结合标准样本,进行分类或者模仿,二是无监督的学习,在制定相应的学习规则后,系统会根据自身所处环境,进行学习内容的分析和选择,更加接近人脑的功能特点。
3 基于遗传算法的优化BP神经网络算法
3.1 算法基本原理
①BP算法。BP神经网络算法主要包括了数据流的前向计算和误差信号的反向传播两个方面的内容,结合三层BP神经网络的拓扑结构,假定x为网络输入,y为结果输出,当处于正向传播过程时,数据的传输为输入层隐层输出层,每一层神经元的状态仅仅会影响下一层神经元,而如果输出层无法获得期望输出,则会自动转向误差信号的反向传播流程。在BP神经网络中,网络的训练实际上是对阈值和权值进行调整的过程,当网络误差缩小到设定值,或者训练步数达到设定步数时,会自动停止训练。
②遗传算法。遗传算法可以从代表问题可能潜在解集的种群开始,种群中的每一个染色体都带有相应的特征,染色体可以看作若干基因的集合,为了便于分析,需要做好编码,完成从表现型到基因型的映射。在演化过程中,依照问题域中存在的个体的适应度,进行个体的挑选和交叉,然后变异出新的解集种群。选择末代种群中的最优个体进行解码,就可以得到问题的近似最优解。
3.2 优化BP算法
BP神经网络算法具有极强的局部寻优能力,但是容易陷入局部极小的问题,遗传算法具有良好的全局优化性和自适应性,但是局部寻优能力不足。对此,可以将遗传算法与BP算法结合起来,实现对于网络拓扑结构和网络权值、网络阈值的优化。
①权值优化。在传统的BP网络中,连接权值的学习算法容易陷入局部极小,无法得到全局最优。对此,可以引入遗传算法代替传统的学习方法,对神经网络的权值进行优化。在这个过程中,需要解决几个比较关键的问题,一是编码方案,可供选择的权值编码方式包括实数编码和二级制编码,前者是以实数表示权值,非常直观,不过需要对遗传算子进行重新设计,后者是利用0,1字符串表示权值;二是适应度函数,引入遗传算法后,网络的机构以确定,在这种情况下,网络的误差越大,适应度越小;三是进化过程,主要是对选择、交叉、变异算子的选择,如果必要,也可以重新设计;四是混合训练神经网络,遗传算法能够在大规模、复杂性的空间中实现可靠搜索,而且不需要有关误差函数梯度的信息,优势相当明显。可以通过在误差函数中增加惩罚项的方式,降低网络的复杂程度。
②权值和结构同时优化。BP神经网络连接权的进化,要求明确的网络结构,网络结构直接影响着神经网络本身对于信息的处理能力。神经网路的结构包括了网络连接方式(拓扑结构)和节点转换函数,完善的结构不仅需要能够对问题进行有效解决,还不能存在冗余节点和冗余连接。伴随着进化算法的应用,网络设计在很多时候被看作搜索问题,评价的标准包括了抗噪性、学习准确率以及泛化能力等。结构进化的关键体现在结构编码和算子设计,而结构编码方案则会影响算子设计的效果。以三层前馈型BP网络为例,其输入层和输出层节点的数量已经确定,优化算法需要重点研究隐含层的节点数量。考虑到问题本身的复杂性,二进制编码的方法并不适用,因此选择实数编码,在隐含层节点增加二级制编码作为控制基因,通过随机函数产生。当控制基因的数值为0时,对应的隐含层节点对输出层无用,而当控制基因的数值为1时,隐含层节点对输出层作用。需要注意的一点,当选择实数编码方案时,为了明确编码的长度,需要确定隐层的最大神经元数目。
4 仿真试验
结合已知数据,对某地区小麦吸浆虫的发生程度进行预测。对问题进行深入分析,可以转化为相应的输入输出系统,可以通过神经网络进行表达。现有的研究成果表明,小麦吸浆虫的发生与气候因素关系密切,因此可以利用气象因子对问题进行分析。选择2000年到2015年的气象数据,设置40个研究样本,以x1-x14表示需要处理的原始数据(气象因子),Y表示小麦吸浆虫的发生程度。从减小误差的角度,对原始数据进行预处理。以优化后的BP算法进行神经网络训练,结合训练结果进行MATLAB仿真。在仿真试验中,需要做好一些关键参数额的设置,遗传算法和BP算法的最大代数分别为100,BP算法均方误差为0.001,会激活函数为双曲正切S型,线性输出层,学习算法被设置为经过改进的自适应学习率的梯度下降学习算法。
设定14作为隐层神经元的上限,由于编码长度固定且迭代代数一定,在所有的试验中,遗传算法的复杂度都是相同的。结合仿真试验分析,隐含神经元的最优数目为5、6、7,与传统方法得到的结果基本一致。相比较而言,利用遗传算法同时进行结构和权值的优化,最为显著的优势在于能够对隐层神经元的数目进行自适应确定,减少尝试的次数,提升计算效率。
而结合相应的训练结果分析,利用遗传算法进行BP神经网络连接权值的优化,相比较传统算法更加有效,不过同样需要进行网络结构的尝试,换言之就是选择合适的隐层神经元数目。不仅如此,利用遗传算法同时对神经网络的权值和结构进行优化,智能型更强,可能找到合适的初始权值和优秀的网络结构,不过,如果数据烦琐,搜索的速度会变慢。