现代启发式算法（共7篇）
现代启发式算法 篇1
0 引言
设计云数据中心需要考虑的因素很多, 但地点是其中应首要解决的问题, 选址对于提高正常运营时间和控制成本至关重要。
在选择数据中心用地时, 为保证中心内服务器及各种设备能够持续、安全地运行, 数据中心用地应满足以下条件: (1) 地基很牢固; (2) 发生火灾的危险性小; (3) 没有大雨等引起洪水的可能性; (4) 用地周围视野广阔; (5) 远离经常落雷的地区和变电所、输电线; (6) 远离空气污染地区。
针对数据中心的选址, 国内外的许多规范都给出选址标准。国内电子计算机机房设计规范 (GB50174-93) 中要求选址必须符合表1所示条件。
在当前环境下, 由于信息不对称, 很多人决策时无法对很多问题考虑充分, 同时由于比较缺乏系统的考察指标, 人们对于数据中心的选址, 通常会凭感觉或经验来决定, 所以一种科学、高效、智能的云数据中心选址方法显得尤为重要。
1 数学模型
根据GB50174-93标准, 云数据中心的选址问题为:如何使得选址地点尽量满足标准。以规范C级标准为例, 该问题有五个目标: (1) 距离机场、有危险的实验室、化学工厂中的危险区域、掩埋式垃圾处理厂、河岸、海岸或水坝的距离大于等于400m; (2) 距离军火库大于等于1600m; (3) 距离核电站的危险区域大于等于1600m; (4) 不处于有可能发生洪水的地区及地震断层附近或有滑坡危险区域; (5) 建设的单位成本最低。
设S={S1, S2, S3, …, Sm}为待选的云数据中心建设点的集合, E={E1, E2, …, En}为机场、有危险的实验室、化学工厂的危险区域、掩埋式垃圾处理厂位置的集合, F={F1, F2, …, Fu}为军火库位置的集合, G={G1, G2, …, Gv}为核电站危险区域位置的集合, H={H1, H2, …, Hw}为可能发生洪水、地震断层及滑坡危险区域。
定义矩阵T= (tij) mxn, C= (cij) mxn, D= (dij) mxn和向量Q= (qi) mx1。其中, tij为待选云数据中心到机场、有危险实验室、化学工厂危险区域、掩埋式垃圾处理厂位置的距离, cij为待选云数据中心到军火库位置的距离, dij为待选云数据中心到核电站危险区域位置的距离, qi为选择该位置建设云数据中心所需的建设成本。
由上述T、C、D, 可以定义矩阵A= (aij) mxn, 其中当aij-tij>=400, aij-cij>=1600, aij-dij>=1600并且aijH时, aij=1;否则aij=0。
则云数据中心选址问题的模型如下:
模型 (I) 的解可用长度为m的字符串X=x1x2…xm表示, 其中, xj (j=1, …, m) 取0或1, 代表第j个待选点是否被确定为云数据中心的选址点。
模型 (I) 是一个约束优化问题, 由于直接对其求解比较复杂, 考虑用罚函数法对其进行转化。
令选取罚函数为, 其中, N为罚因子。在求解过程中, 罚函数的函数值大小体现了对模型 (I) 约束条件的满足程度。罚函数的值越小, 表明解的可行性越高, 反之表明该解的可行性较低。当g (X) =0时, 就说明当前该解是真正的可行解。当罚因子的大小设置适当的时候, 模型 (I) 可以简化为如下问题:
当X满足模型 (I) 的约束时, pj (X) ≤0 (j=1, 2, …, n) , 则罚函数g (X) =0, 此时模型 (II) 的第二个目标可以忽略, 说明模型在 (I) 和 (II) 的可行域中有相同的最优解;当X不满足模型 (I) 的约束时, 则一定存在j∈{1, 2, …, n}使得pj (X) >0。此时通过调整罚因子N的大小, 可以使得罚函数g (X) 变得足够大, 从而不能成为最优点, 继而优化得以继续。
2 算法实现
该问题本质上属于NP-Hard一类问题, 使用普通的方法解决起来有难度。现采用现代启发式搜索算法, 即一种随机优化算法, 来进行此问题的实现。
1983年Kirkpatrick提出了SA (Simulated Annealing) 算法, SA算法是基于Monte Carlo迭代求解的策略, 用固体物质的降温退火过程来模拟组合优化问题的求解。但其参数较难控制, 主要有以下两个参数:初始温度值、退火速度。
由于SA算法将在降温的过程中不断产生更新的最优解, 所以初始温度值设置是影响SA全局搜索性能的重要因素之一。初始温度高, 搜索到全局最优解的可能性大, 但容易产生冗余的迭代;反之, 可节约计算时间, 但容易陷入局部最优解, 全局搜索性能受到影响。
同时退火衰减函数的选取决定了该方法的收敛速度。如果降温过程足够缓慢, 多数得到的解性能会比较好, 但与此相对的是收敛速度太慢。如果降温过程过快, 很可能得不到全局最优解。
现采用启发式搜索算法的策略生成最优解。本算法使用如下方法确定初始温度值:
随机产生K个初始解, 设Fmax、Fmin分别为这K个初始解对应的f (X) 目标的最大值和最小值。初始温度t0:
P (0, 1) 为初值控制接受概率。由于初态的随机性, 当K足够大时, 可以在一定程度上体现整个解空间中状态的分布情况。采用P来决定初温, 能赋予不同状态合适的跳转概率, 从而在一定程度上避免初始温度值选择的盲目性。
退火速度函数采取:
其中L为温度下降因数, L (0, 1) 。每一次迭代过程, SA算法都将破坏原有的状态, 并通过邻域函数来得到新的解以更新状态。
3 试验结果及分析
假设距离机场、有危险的实验室、化学工厂中的危险区域、掩埋式垃圾处理厂、河岸、海岸或水坝位置集合:
军火库位置集合:
核电站危险区域位置集合:
待选云数据中心集合:
待选云数据中心建设成本:
试验结果
矩阵T:
矩阵C:
矩阵D:
利用前面设计的搜索算法, 取P=0.3, K=3, N=5000, L=0.8, 求得有效解为S2, S3, S5, S6, S7, S8, S9, S11。当只选取一个数据中心时, 其最优解为S6, 且计算时间小于0.1s, 表明该算法是求解数据中心自动选址问题的有效算法。
4 结语
本文针对云数据中心自动选址问题, 讨论了基于现代启发式搜索算法的一种解决方法。其重点是构建合理有效的数学模型, 设计高效的算法实现, 以帮助用户快速、方便地拿出选址方案。所设计的选址算法具有简单、实用的特点。但是该算法也存在选择出的解为局部最优解的问题, 如一个解在很大邻域空间中是最优解, 在算法中可能会认为其是全局最优解, 这也是今后研究中要解决的问题。
摘要：考虑到云数据中心选址时的成本和安全因素, 给出了云数据中心自动选址模型, 通过罚函数将多目标约束问题简化成易于计算机求解的简单约束模型。在初始温度的选取、退火温度控制等方面为其设计了搜索算法, 并通过实验证明其有效性。
关键词：云数据中心,启发式搜索,退火,罚函数
参考文献
[1]杨建光.数据中心选址的探讨[J].智能建筑与城市信息, 2008 (8) .
[2]魏唯.一种多目标增量启发式搜索算法[J].吉林大学学报:理学版, 2009 (7) .
[3]WLODZIMIERZ O.On the distribution approach to location problems[J].Computers&Industrial Engineering, 1999 (37) :595-612.
[4]马良.多目标平面选址问题的模拟退火算法[J].系统工程理论与实践, 1997 (3) .
[5]王凌.多目标优化的一类模拟退火算法[J].计算机工程与应用2002 (8) .
[6]LUNDY M, MEES A.Convergence of an annealing algorithm[J]Mathematical Programming, 1986 (34) :111-124.
启发式库存-路径问题求解算法 篇2
集成化物流管理ILM(integrated logistics management)是一种近年来才发展起来的新的物流战略管理模式,其主张将所有的物流活动整合在一起视为一个完整的系统,并在理想的客户服务水平下追求总成本最低[1]。
库存-路径问题IRP(inventory routing problem)是在如何联合优化配送和库存这两个往往被独立考虑的物流环节的现实需求推动下成为崭新的研究领域,是企业节能增效的重要途径。库存路径问题是对一系列已知需求量的客户,组织适当的行车线路进行服务,在不违反任何约束条件下,优化路线使得总成本达到最小。有效地解决该问题可以提高车辆的利用率,降低配送成本,提高配送时间的准确率,从而提高物流服务水平。由于库存路径问题是典型的NP难题,使用传统的优化方法很难得到问题的最优解或满意解,因此构造高质量的启发式算法成为研究该问题的主要发展方向[2]。
国外IRP研究最早出现在20世纪70年代。2000年以前的IRP文献主要研究单周期、一对多、单品种、确定需求情况,通常给定车辆数或不限,决策方式则集中在确定固定的配送频率,目标只考虑客户库存成本(一般不考虑中心库存成本)。求解时,采用“分区—路径” 分解问题或者沿用EOQ(Economic Order Quantity)思路占绝大多数,寻找合适的求解方法一直是研究热点、重点和难点。2000年以来,在继续构建高效率求解方法的同时,IRP本身的研究得到了深入,随机需求IRP、三层级IRP、取送结合IRP受到更多研究的重视[3]。
SPERANZA等运用实例证明了建立混合整数规划模型较建立纯整数规划模型的优越性[4]。
CHIEN等也讨论了单周期的IRP,他们所研究的配送系统包括一个有固定供应能力的中心仓库和多个有确定需求的客户,供方可以不满足部分客户的需求,但必须对未被满足的需求支付惩罚费用,建立了一个混合整数规划模型,采用基于拉格朗日松弛的求解过程来获得理想的上界[5]。
DROR等则研究了多周期IRP,侧重于如何将长时段(如每年)的多周期问题简化为短时段(如每天)的单周期问题。通过引入惩罚因子和激励因子来反映相邻周期决策的相互影响,并且建立了相应的混合整数规划模型[6]。
BLANCHINI等在建立随机动态规划模型时将单品种、多对多的物流系统看成是一个网络[7]。
国内IRP研究文献出现在2001年以后,但论文数不多,研究工作尚处于起步阶段。
奚飞等人通过综合考虑零售商订货周期与供应商订货周期之间的大小关系,最终寻求一种最优的IR策略,从而使整个供应链的成本最小[8]。
武秀焕等人将随机IRP描述为一个马尔可夫过程MDP(Markovian decision process),根据客户数量将问题分解成N个子问题进行MDP描述,接着对状态转移矩阵进行模拟,并对每一个MDP子问题进行求解,然后运用非线性背包问题的求解方法得到IRP的初始策略来构成直接配送路线,并在此基础上构造了一种基于搜索算法的启发式算法对初始策略进行优化,得到最终的优化解[9]。
沈飞等人将IRP问题分成两个子问题:一个能够使库存储存费用最小的线性规划和在基于模拟退火理论下生成并评估可选择性组合路线的分路线排除约束函数(the route perturbation routine)。一旦确定运货车的路线,混合整数规划(MIP)就转化为相对容易解决的线性规划,这样便能在给定的路线组合中寻找到解决库存问题的最优方案[10]。
目前国内对IRP的研究都是假设产品为单一品种。本文考虑多品种、多供应商对多客户的IRP问题,使用启发式算法选择最优的可选择的组合线路,逐步生成满意解。
1模型的建立
1.1模型假设
(1) 所有产品都能在1天内送到,即不考虑配送时间。
(2) 运输成本以整车为单位计算。通常运输成本包括:过路费、油费、人工工资、各种损耗。对于确定的运输线路和运输工具,则过路费、人工工资、其他损耗可以估算出来,油费与运输距离、货车自重、载货量成正比。
(3) 只考虑产品重量,忽略产品体积,是否易燃易爆等因素对运输费用的影响。
(4) 不考虑产品装卸费用和库存成本。
(5) 货车可以有多种类型,每种货车的自重、最大载货量、固定费用不同。
(6) 只考虑点对点运输,即货车到达目的地之后,必须将所有产品全部卸下。货车数量不受限制。
(7) 任意2节点之间存在直达线路。节点之间直达线路长度为最短,比经过任何节点中转都要短。
(8) 货车必须在当天返回出发点。即货车运输路线形成汉密尔顿圈。
1.2模型的建立
设有n个节点ai,m种产品Bj,节点之间直达距离为Dij,节点产品库存为Sij,节点产品需求为Eij。
设运输费用为:
其中,F为固定费用(与货车类型有关),d为运输距离,Z为货车自重,w为载货量,u为费用系数(需事先估计)。
每辆货车的运输路线形成汉密尔顿圈,设运输路线经过k个节点,则该运输线路可表示为:L(a1,a2,…,ak,a1)。
1.3目标函数
令恰好满足所有节点产品需求的货车运输路线集合为Q={L},相应的总运输费用为:
P=∑c(Li) Li∈Q (2)
则系统目标函数为求总运输费用最低的集合Q′,即:
P(Q′)=min{P(Q)} (3)
约定:
di,t=时间段t内配件i的需求量,i=1,2,…,m;
t=1,2,…,T;
K0=仓库和装配车间的距离;
K1=仓库和最近供应商间的距离;
K2=装配车间和供应商间的距离;
K=K0+1/2K1+1/2K2;
Ci,j=供应商i与j之间的行车距离,i和j=0,1,…,m+1;
hi=配件i的库存存储成本i=1,2,…,m;
Ii=配件i的初始库存量i=1,2,…,m;
C=货车的装运量;
L=线路的最大长度。
设:
qi,t=时间段t内在供应商i处的装运量;
si,t=时间段t内在配件i的库存水平。
于是有:
s.t
qi,t≥yi,t ∀i,∀t (5)
pi,t≤qi,t ∀i,∀t (6)
si,t+1=si,t+pi,t-di,t ∀i,∀t (10)
si,0=Ii ∀i∈{1,2,…,m} (11)
si,t≥0 ∀i,∀t (12)
yi,k,t,pi,k,t∈{0,1} ∀i,j∈{0,1,…,m+1},∀k,∀t (13)
因此,目标函数(4)包括的成本项目有访问供应商的成本之和,库存存储成本,出行设置成本。而约束条件式(5)至式(7)将变量yi,t与装运数量联系起来,约束函数(9)限定了每条线路都小于或等于最长线路L,约束条件式(10)为库存平衡等式,约束函数式(14)对一辆货车能够装运的载运量进行了限定。
2启发式求解算法
Q′为汉密尔顿运输路线集合,根据贪婪法则,总能找到当前单位运输成本最低的汉密尔顿运输路线,则有算法如下:
(1) 系统初始化。
(2) 根据需求计划及库存,找出所有可能的点对点运输线段。
(3) 找出使运输线段连接成汉密尔顿圈的所有组合。
(4) 对于p种货车,分别计算汉密尔顿运输线路及其成本。
(5) 找出运输成本最低的汉密尔顿运输线路,记录该线路。
(6) 根据该线路选择具体的运输方案,并在运输源节点的库存中减去已计划运输的产品,及在目标节点的需求中减去已计划运输的产品。
重复(2)—(6),直到没有任何可能的点对点运输线段。得到的配送方案集合即为最优运输方案。
3算例分析
为验证算法的可行性与有效性,编制程序验证本文所提出的模型与算法。
算例来源于模拟现实生活。基本数据为9个节点,9种货物,货车自重1500千克,最大载货量4000千克,固定费用200元,费用系数为4500,节点之间平均间距为153.3千米,每个节点存有多种产品,平均每个节点存有4.89种产品,节点平均库存量为4137.4千克。节点的产品需求数随机产生,多次运行算例结果如表1所示。
由表1可以看出:单位产品运输成本平均为0.06883元/千克,货车平均载货量为2416.99千克,平均货车运输效率为60.425%,空驶率平均为14.785%。而我国物流运输车辆的空驶率达37%[11]。
为验证算法的可行性与有效性,本文将应用所提出的模型与算法所得出的计算结果与其他启发式算法进行比较。
若利用集合覆盖型等式,由于该等式限制了路线的长度,能够最优解决的IRP 的最大容量是6 个供应商和7 个时间段。最优总成本是1354.70 元(存货成本=97.80 元,运输成本=1256.90 元)。
若利用本文所提出的启发式算法程序解决相同的问题,总的成本是1370.43元(存货成本=118.2 元,运输成本=1252.23元)。最优解和利用启发式解法得到的解的直接数值间隙是1.15%。同时即使供应商的数量大于100 和多个时间段的问题时也是有效的。因此本文提出的模型与算法不仅具有可行性而且在所求解问题的规模上具有先进性。
通过对比可知,本文提出的启发式多产品库存路径算法大大降低了货车的空驶率,有效地提高了货车运输效率,从而降低了运输成本。
4结语
(1) 本文重点介绍了库存路径问题的启发式算法研究,分析了关于库存路径问题的模型建立和解决过程。
(2) 探讨了以贪婪法为基础的启发式算法,采用的策略是每次选取平均运输成本最低的汉密尔顿运输路线。
(3) 模型仿真结果表明,本文提出的启发式多产品库存路径求解算法生成的物流运输方案高效,成本低廉,有广泛的应用前景。
参考文献
[1]Kenderdine D J,Larson P D.Quality and Lo-gistics:A Framework forStrategic Integration[J].International Journal of Physical DistributionandMaterials Management,1988,18(7):5-10.
[2]陈雪瑛.基于启发式算法的库存路径优化问题研究[D],北京交通大学,2008.
[3]傅成红,符卓.库存路径问题及其最新进展[J].计算机应用,2010(2):453-457.
[4]Speranza M G,Ukovich W.MinimizingTransportation and InventoryCosts for Several Products on A Single Link[J].Operations Re-search,1994,42(5):879-894.
[5]Chien W,Balakrishnan A,Wong R.An Integrated Inventory Alloca-tion and Vehicle Routing Problem[J].Transportation Science,1989,23(2):67-76.
[6]Dror M,Ball M.Inventory Routing:Reduction From an Annual to AShort-period Problem[J].Naval Research Logistics,1987,34(6):891-905.
[7]Blanchini F,Queyranne M,Rinaldi F,et al.A Feedback Strategy forPeriodic Network Flows[J].Networks,1996,27(1):25-34.
[8]奚飞,周永务.基于固定分割的库存路径问题最优策略[J].系统工程与电子技术,2009(10):2389-2993.
[9]武秀焕,李延晖.马氏过程的随机库存路径问题模型与算法[J].工业工程与管理,2009(1):66-70.
[10]沈飞,管小俊,于雅岑,等.基于模拟退火理论求解库存路径问题的模型与算法研究[J].物流技术,2009,(2):74-76.
现代启发式算法 篇3
在物流中心的各项活动中,分拣是最为重要的一项活动, 其成本约是整个中心运营成本的50% ~ 65%[1],分拣的效率不仅关系到整个运营的成本还直接影响到客户服务水平。而订单分批通过将多个订单合成一个批次或更大的订单以提升拣选设备的利用率并减少工作量,使得分拣过程得以更有效的实施。随着订单数目的增加,可行批次的数量以及决策变量的数量呈指数增长,许多基于最优化算法的研究都具有比较大的局限性,所以采用启发式算法解决订单分批问题得到了广泛的共识。早期的研究主要凭借以往的经验对订单分批过程进行优化。例如对客户订单按照某种事先确定好的优先级进行分批,先到先服务( First Come First Serve,FCFS) 准则是其中最常用的一种。Elsayed[2]在1981年提出种子算法的概念,该算法对每个批次选定一个种子订单,余下的订单将按照某种配对原则添加到批次中。Ho和Tseng[3,4]等对种子的选取规则以及订单配对原则的选取进行了深入的研究。李诗珍对种子算法以及节约算法进行了初步的探讨[5,6]。Elsayed和Unal[7]在节约算法的基础上提出了一种有效的算法用于求解订单分批问题,通过比较每两个客户订单合并后的路程节约量进行分批,从节约量最大的订单对开始,余下的订单对按照节约量非增的顺序被分配到下一批次中,每次分配订单的时候都重新计算节约量。
综上所述,订单分批问题的求解方法是国内外研究的重点,一些经典的启发式方法如先到先服务,种子算法,节约算法在实际中得到了广泛的应用,这些算法的特点是直观易行并且计算快速,常用来求得问题的初始解或作为检验新算法有效性的基准。本文提出一种降批次启发式方法,并与经典的算法进行比较。
2问题描述和模型建立
订单拣选可以说是物流中心最耗费时间的作业,根据以往的经验,减少拣选所花费的时间能够有效节约人力成本。 同时,拣选时间是交付提前期的重要组成部分,减少拣选作业时间能减少客户订货周期从而提升客户服务水平。
当客户订单到达,为了完成客户订单所指定的物品的拣选,拣货人员需要花费的时间也被称作订单处理时间,其中行走时间对整个订单处理时间的影响最大。假设拣货人员在拣货过程中采用匀速行走,减少行走时间可以等效为减少总的拣选路程。
订单分批是这样一个过程: 待拣选的物品被安排到每一次往返于仓库的行走过程中,每次往返拣选一方面受限于拣选设备的容量,另一方面也取决于订单所包含品项占用的空间大小。客户订单尽量被安排到一次拣选路程中直到拣选设备的容量被用尽为止,这些需要在一次往返路程中完成的订单为一个批次。许多文献中拣选设备容量有不同的意义,即可以指订单的数目也可以是物品的数目,本文指的是物品的数目。综上,订单分批问题可以描述如下:
对于给定的拣选设备容量以及路径策略,如何将客户订单以及所要求的有固定储位的待拣选物品分批在一次往返拣选中完成从而使得所行走的路程最短?
本文采用Gademann和van de Velde[8]提出的订单分批模型,该模型具有简洁直观的特点非常适合用来进行订单分批问题的探讨,该模型明确考虑到每个可行的批次,设订单集合O有n个订单需要拣取,每个订单中含有一定数量的物品,并设B为可行的批次集合,可以建立如下数学优化模型:
目标函数:
约束条件:
式中
O———客户订单的集合,O={1,2,…,n};
C———拣货车的容量;
B———所有可行批次的集合;
cj———第j个订单中所有品项的数量;
di———拣取第i批次订单中的所有物品所行走的总的路径值;
xi———二进制决策变量,如果第i个批次被选中则xi= 1, 否则xi= 0;
ai= { ai1,ai2,…,ain} 表示第i批订单的订单组成,aij= 1表示第j个订单在第i个批次中。
该模型要求每批次订单在一次往返拣选路径中完成,以使得所有批次总的拣选路程最短。约束条件( 2) 保证了每批订单所包含的品项数不超过拣货设备的容量,约束条件( 3) 和( 4) 则保证了每个订单必须且只能被分配一次。
3路径策略下的计算方法
上述优化模型的目标是最小化拣选路径,对于启发式算法的评估依赖于相应的路径策略,由于具体选择哪种路径策略并不会对评价分批结果的好坏产生影响,本文的算法采用S型路径策略。在实际应用中,S型路径策略是最为常见的,采用S型路径策略计算拣选路程不仅直观而且易于实现。本节讨论一种S型路径的计算方法,该方法灵活易于扩展,而且最为重要的是不影响我们对订单分批问题的讨论。一个典型的单区型无交叉走道的货架摆放如图1所示:
则捡货人员在拣选过程中通过的路程可近似计算如下:
其中:
LENGTH_OF_RACK:货架(走道)的长度;
WIDTH:货架的宽度;
CONER:拣货人员到达通道尽头的转角距离;
Nl:人员通过的走道数目;
Nc: 拣选设备转过拐角的数目;
Nw: 拣选设备通过货架两侧的次数即通过货架宽度的次数;
Last: 拣选设备通过的最远的通道数。
λ 的取值取决于需要穿过的通道的数目,当需要穿过的通道数目为奇数时,拣货人员需要多穿越一次。值得注意的是,当拣货员通过的最远通道数为一即只有第一个通道有货物需要拣选时,最好拣选方法是返回策略即拣完最后一个货物就返回,本文在此进行了简化,认为此时拣货员需要通过整个通道再返回,即:
D = LENGTH_OF_RACK + CORNER。图2表示当Nl = 2, last = 3时路程的计算情况,蓝色的方块表示拐角被计算一次, 红色的方块表示货架宽度被计算一次,粉色的区域表示走道被通过。
4启发式分批算法
4. 1根据优先级规则进行分批
通常拣货员在进行拣选作业之前会对订单进行简单的分类,比如按照时间顺序,品项数目多少的顺序等,然后对这些订单按照某种规则制定拣选的优先级,先到先服务( FCFS) 是最常用的一种基于优先规则的分批算法,FCFS按照订单到达的顺序对订单进行分批。
4. 2种子算法
种子算法自从1981年被Elsayed提出,种子含有“最初” 的意思,即种子订单是每个批次的初始订单。种子算法是一种连续生成订单批次的方法,因此,初始批次的选取对后面的分批有很大影响,种子算法进行分批主要有两个过程: 一是种子订单的选取; 二是根据订单的相似度进行配对。使用种子算法进行订单分批,首先对初始批次选择一个种子订单,然后按照配对原则从剩余订单中选出一些订单加入该批次,加入时要考虑拣选设备的容量,如果当前批次无法容纳更多的订单,则考虑一个新的批次直到所有订单都在某个批次内。
4. 3节约算法
种子算法忽略了与具体目标函数的联系,使得算法性能具有某种不确定性,节约算法通过计算每两个订单合并后路径的节约量来匹配订单,所有订单间的路径节约量被存放在一个被称为节约矩阵的矩阵里,其行和列均代表订单的编号, 索引为( i,j) 的元素表示第i个订单与第j个订单合并产生的节约量。节约算法的思想来自于Clark和Wright对车辆调度问题的研究,每次将订单安排进某个批次就对节约矩阵进行更新,使得批次中的订单与剩余订单重新计算节约量,这样剩余订单更可能选择那些能获得最大节约量的批次加入。
4. 4降批次启发式算法
本节根据订单分批问题的特点提出一种降批次算法用于求解分批问题。在分批问题中,订单的分批数量是影响优化结果的一个关键性的指标,分批数量越少则结果可能越好,每个批次在一次拣选路径中完成,则越少的批次意味着越少的拣选次数,拣选的总路程也相应更少。受拣选设备容量的限制,理论的最小批次数为订单集合的物品总数与拣选设备容量的比值,一般要在理想情况下才能取到这个值。降批次算法正是出于上述考虑提出的,该算法的过程如下所述: 首先将一系列订单进行排序,排序将订单按品项数从大到小排列。然后依次将订单放入每个批次中,第i个订单放入第i个批次,批次的数量等于订单的数量,然后依次对最高的批次进行降批即逐步减少批次数量,将高批次数中的订单放入任意低批次中并检查是否满足约束条件,如果不满足则将其作为一个独立的批次,重复上述过程直到无法再进行降批次操作算法停止。
降批次算法不同于前面几种方法,无论FCFS还是种子算法或是节约算法均是采用连续产生批次的方法,降批次算法采用一种逆向的思路,先将订单分成批次,然后对批次的内容进行调整,相当于每个订单都是一个种子,从而减少了选择种子的过程。
5启发式方法求解性能比较
考察上述启发式方法在不同订单集合下的优化性能,通过设置不同的订单数量测试算法的适应性,对FCFS算法、种子算法、节约算法和降批次算法进行了比较,其中种子算法选用最小通道数目的选择策略和随机的匹配策略,节约算法按照节约矩阵选择种子订单对,然后根据随机原则将为分配订单加入到已有批次中。表1显示了在订单数目分别为10、15、 20、25、30、35时各算法平均最小批次数量以及平均路径改善率的情况,这里每个订单品项数均随机产生且均匀分布在[10,30]区间上,拣选设备容量为40,仓储布局为传统的单区型仓库拥有6条纵向走道240个储位,采用S型路径策略和随机存储策略,表中的值为10次试验所取平均值。算法路径改善率随订单数目变化情况图4所示。由图4可看出在随机产生订单的情况下不同的算法得到的结果的优异程度,节约算法的路径改善率是四种算法中最大的,降批次算法则具有几种算法中最少的分批数量。种子算法则显得中规中矩, FCFS的结果最糟糕。然而并不能据此得出某个算法比另一个更好的结论。
表2显示了在同等条件下拣选设备容量为60时的情况。 算法路径改善率随订单数目变化情况如图3所示。
表中节约算法的批次数量最大,但是仍然获得了很好的路径改善率,可见批次数量少并非是路径改善率高的必要条件,种子算法在这种情形下的表现最好。当拣选设备容量为60而订单品项数均匀分布于[10,50]区间上,其结果如表3所示。算法路径改善率随订单数目变化情况如图4所示。
可见,算法的性能受拣选设备容量以及订单品项分布情况共同的影响,当品项数分布接近拣选设备容量上限时,节约算法和降批次算法具有更好的性能,当品项分布远小于容量的限制,FCFS和种子算法则较以往有更好的表现。综合来看,在两种情况下节约算法和降批次算法都提供了更好的分批结果,尤其是节约算法,这与以往的研究结果一致。降批次算法在一些拣选设备有限的情形则可能有更好的表现。
6结论
本文分析了订单分批问题及其求解思路,然后介绍了三种启发式分批算法,并在此基础上提出了一种旨在减少批次数量启发式算法—降批次算法,最后对上述四种算法进行了比较,发现在最小化路径模型的分批问题中节约算法和降批次算法具有比较好的性能。启发式方法还受到订单品项分布和拣选设备容量限制共同的影响,采用不同的启发式算法的性能具有差异性。
摘要：订单分拣是物流中心最为关键的环节,其成本占到整个物流中心成本的50%以上。文中通过制定合理的订单分批策略以改善人工拣选系统中拣选作业的工作效率,在以往研究的基础上提出了降批次启发式算法,算法考虑到拣选过程中批次数量对于结果的影响。并且利用matlab仿真软件进行仿真实验,与经典的启发式算法进行了比较,实验结果显示降批次算法有较经典的启发式算法更好的求解结果。
现代启发式算法 篇4
对于订单式的钢结构项目生产来说, 后一种排料要求更加符合实际情况, 即利用若干规格和数量的钢板, 为指定尺寸、指定数量和指定纹理的零件下料, 在满足配套和切割便利的前提下, 使板材的利用率最高, 同时又使钢板原料的需求最少。
1 排料方法分析
在钢结构实际生产中矩形零件占一部分, 还有一部分零件是不规则零件, 其中对钢板料耗影响最大的就是不规则零件, 不同的组合次序、旋转角度都可能导致不同的排料结果。钢板排料的数学理论除了常用的遗传算法外, 启发式包络算法也是一种较为简易的方法。
1.1 启发式排料原理
启发式方法是根据板件的轮廓特征先求取最小包络矩形, 再求出聚合矩形。通过对零件外轮廓多边形进行操作, 分别求得与多边形平行或重合的最小矩形, 找出其中的最小者即为零件最小包络矩形;将原零件复制一个并旋转180°;将复制件沿原零件的四周依次移动到若干个位置, 再分别与原零件进行组合, 每次组合均求一次最小包络矩形, 面积最小的矩形即为零件聚合体的最小包络矩形。如果聚合后的聚合矩形的面积小于两个零件的最小包络矩形面积之和, 则聚合成功;反之则自动放弃聚合。
1.2 启发式排料流程
启发式排料先要对待排料板件进行简化预处理, 将不规则的二维图形简化为二维矩形, 即用板件的最小包络矩形代替板件进行排料。
单个或多个不规则零件的组合找出其最小包络矩形, 然后化为矩形件的排料问题。
(1) 单个零件的矩形替代。
采用穷举法求取板件的最小矩形包络。只有当零件的包络矩形与零件的外轮廓多边形中的一条边平行或重合时, 此包络矩形才有可能是最小包络矩形。
求解包络矩形的过程是:零件外轮廓的顶点连线形成封闭图形 (凸多边形) , 然后以凸多边形的每一边假设与所求矩形中的一边重合, 根据顶点位置即可得出此时的包络矩形, 其中面积最小者为最佳包络矩形。
(2) 多个零件的矩形替代。
当单个零件经矩形替代后, 若矩形面积较零件面积大的较多, 即又较多的面积冗余。为了提高材料利用率, 可将两个合适的零件聚合在一起, 再按单个零件的矩形替代方法求出其最小矩形包络。一般情况下, 两个同类零件相对180°转角聚合是较为理想的。
(3) 冗余域最小原则。
单 (多) 个零件的矩形替代与零件边界间的空白部分成为冗余域。
为了提高材料的利用率, 进行矩形替代预处理时, 要将适当的小零件矩形替代填充到冗余域中。
(4) 排料优化算法的描述。
假设母板编号为Bm, 每块矩形件编号为An。首先将矩形件按面积大小排序, 面积大的在前, 面积小的在后, 母板的面积为S (Bm) , 将排序后的矩形件排到母板上, 对某一个矩形件An, 它总是被排到第1个能排下它的母板Bm上, 也就是说, 矩形件An被排到已排入的矩形件面积不超过S (Bm) -S (A n) 。
其中, C (Bk) 为第k块母板上排入的矩形件的总面积。
2 注意问题
2.1 绘制排料图的注意事项
为简化排料图的绘制, 排料前应先将零件分类, 一般可分为以下三类。
(1) 零件长边大于钢板短边的一类。此类零件在钢板上只有一种排法, 对材料利用率影响较大, 应注意利用余料安排其他尺寸较小零件。
(2) 零件两边均小于钢板短边一类。此类零件排料组合情况多样, 应注意不同零件的搭配。
(3) 零件尺寸较小, 或某边长与钢板某边长成倍比关系的一类。此类零件单一下料利用率高。
绘制排料图时, 应先考虑第1类零件, 其次搭配好第2类零件, 最后将第3类零件作为余料的填充料。数量较大的第3类零件还应绘制单一排料图。
2.2 简化模型的方法
在下料问题的模型中, 每种零件对应一个约束条件, 当一批下料任务中零件品种较多时, 不尽会使排料工作复杂化, 而且模型也相应复杂, 会使计算量急剧增加。此时可采用以下方法处理。
(1) 对尺寸不大且数量较少的零件, 在排料和建模时可暂不考虑, 它们通常可在最终方案的余料中安排, 或在取整修整阶段一起解决。
(2) 对数量相同或相近, 且某边长也相同或相近的两种或多种零件, 可组合成一“新零件”进行排料和建模。
(3) 若经上述处理后零件品种仍过多时, 可将各零件适当分组。对各组零件分别排料和建模, 可将一个大的问题化为几个较小的问题来求解。这不仅可大大减少运算量, 还可简化排料工作。
3 结语
启发式包络算法对于数量不是很多、轮廓较为规则的零件效果较为明显, 但是对于轮廓不规则 (尤其是凹多边形) 、数量较多的零件排料效果不是非常理想。遗传式排料方法是对不规则零件排料的有益补充, 但是对于零件较多的时候, 排料同样非常耗时, 并且对计算机硬件要求较高。对一个钣金CAD/CAM系统而言, 如何将这两种排料算法有效的结合起来, 并尽可能在优化排料方案基础上提高排料过程自动化程度, 这是钣金CAD需要研究的新领域。
摘要：在钢结构生产中, 钢板排料是一项既重要又繁琐的工作。如何使排料更加优化、降低钢板的采购成本, 而且效率更高, 本文基于启发式包络算法对钢板排料进行了阐述。
关键词：钢板,包络,排料
参考文献
[1]黄宜军, 施德恒, 许启富.钣金CAD中一个较优的排料算法[J].计算机辅助设计与图形学学报, 2000, 5 (5) :380～383.
现代启发式算法 篇5
齿轮类零件是机械加工中的主要零件,齿轮生产正逐步从大批量连续生产向多品种、小批量生产转型。一个制造型企业的竞争能力基本上取决于产品制造过程中的调度能力。从上个世纪末到现在,学者们在不断追寻调度问题解决方案的过程中发明了很多实用的算法,启发式算法就是为了解决复杂调度问题而发明的一种新思路和新方法,其中比较经典的算法如遗传算法、蚁群算法、粒子群优化算法等对求解车间调度问题起到了很大的推动作用。本文应用启发式算法理论对齿轮生产车间的调度问题进行研究。
1齿轮生产调度问题描述
设需要加工零件的数量为n,加工机床的数量为m,每个加工零件包含多道固定顺序的加工工序,每道工序可以在不同的机器上进行加工,在不同的机器上工序的加工时间也不同。调度的任务是安排最合适的机床完成每道工序的加工,计划每台机床上各工序的最佳加工顺序以及开工时间,使生产中需要达到的交货期、库存数量、生产延迟等性能指标达到最优。
2算法的求解步骤
齿轮生产车间寻找最小化制造期的调度Fm‖Cmax问题,可以看成是否能够得到使一个零件的加工工序贯穿整个系统的排列。实际上,需要加工的零件在队列中等待忙碌机器的时候越过另一项工作先进行加工是可能的,机器不一定要按照先到先加工的规则进行加工,这样在不同机器上各零件的加工顺序可能发生变化。改变相邻两台机器间各等待加工工作的加工顺序有时能得到更短的制造期。
对有m台机器的流水车间给出一个排列调度j1,j2,…,jn,在机器i上工作的jk完成时间为:
Ci,jk=max(Ci-1,jk,Ci,jk-1)+pi,jki=1,2,3,…,m;k=1,2,3,…,n。
其中:Ci-1,jk为在机器i-1上工作jk的完成时间;Ci,jk-1为在机器i上第k-1项工作的完成时间;pi,jk为工作jk在机器i上的加工时间。
给定排列调度下的制造期可由有向图的关键路径计算得到,给定序列的有向图构造如图1所示。
对每道在机器i上进行的工序jk,存在一个节点(i,jk),其权重等于jk在机器i上的加工时间。节点 (i,jk)有弧连接到节点(i+1,jk)和(i,jk-1),与机器m相关的节点只有一条弧,这和对应工作jn的节点相同。节点(m,jn)没有出弧(见图1)。从(1,j1)到(m,jn)的最大权重路径的总权重对应于排列调度j1,j2,…,jn的制造期。
3应用实例
结合理论研究,本文设计开发了齿轮生产车间的调度系统,下面以某齿轮加工车间的实际需求为背景,验证该系统的可用性和有效性。
齿轮生产车间的生产线类型属于流水线,其基本的工艺流程为:齿轮毛坯预处理→热处理→齿轮端面加工→齿形加工→热处理→表面处理。现有3个订单生产任务,3种齿轮的型号不一样。通过数据管理模块将新工件添加到系统中,如图2所示。该模块的主要工作是对工件信息进行管理,包括新建、修改和删除等。工件信息包含工件编号、工件名称、开始加工时间、交货期、数量、状态、优先级等。
在对调度问题建模完成后,点击“调度执行”按钮,操作者可根据自己的要求相应地进行参数设置,在确认各项参数后,点“确定”就可以进行调度计算。经验证,运行结果符合实际生产情况,可用来指导实际生产。
4结束语
启发式算法在调度问题中的应用可以很好地解决复杂的调度优化问题。随着研究的不断深入,调度模型和调度算法与生产实践的结合必定会更加紧密,调度系统必定向着集成化、动态化、高效化、实用化和智能化的方向发展。
参考文献
[1]何霆,刘飞,马玉林.车间生产调度问题研究[J].机械工程学报,2000,25(5):14-18.
[2]黄友锐.智能优化算法及其应用[M].北京:国防工业出版社,2008.
[3]孙志峻,朱剑英.具有柔性加工路径的作业车间智能优化调度[J].机械科学与技术,2001,20(6):931-935.
现代启发式算法 篇6
关键词：启发式算法,汇集式,路线
一、汇集式路线概述
汇集式路线是指按照单程进行货运生产组织的车辆行驶路线。车辆由起点出发, 在货运任务规定的各货运点依次进行装货或卸货, 并且每次装货或卸货都小于一个整车, 车辆完成各货运点运输任务以后, 最终返回原出发点。因此, 一般情况下, 汇集式路线为封闭路线。车辆可能沿着一条环形式的路线行驶, 也可能在一条直线形路线上往返行驶。
汇集式的运输形式一般可分为三种形式: (1) 分送式:车辆从起点装车完成后, 沿着运行路线上的各个货运点依次进行卸货, 最终可返回起点; (2) 收集式:车辆从起点空车出发, 沿着运行路线上的各个货运点进行装货, 最终达到目的地; (3) 分送——收集式:车辆沿着运行路线上的各个货运点分别或者同时进行装货以及卸货。如为分送式路线, 其主要日运行指标如下:
(1) 货运量Q:
Qj—第j次周转车辆完成的货运量。
(2) 周转量P:
Pj—第j次周转车辆完成的货物周转量。
当车辆按照汇集式路线完成运输工作时, 由于周转货物周转量的大小与车辆沿路线上各个货运点的绕行次序有关。如果绕行次序不同, 即使完成同样的货运任务, 其周转量也会不大相同。在这种情况下, 按照总行程最短的原则来组织车辆进行运输显然最为经济。因此, 选择汇集式路线应以总行程最短为最佳准则。
二、汇集式行驶路线求解流程
前已述及, 选择汇集式路线, 即选择车辆在各货运点间绕行次序, 应以每个单程后者周转总行程最短为最佳准则。据此, 可以将汇集式路线选择问题归结为运筹学中的货郎担问题, 我们可以采用启发式算法进行近似求解。
行驶路线最短问题有很多种算法, 在这里启发式指的是在一个搜寻树的节点上定义的函数h (n) , 用于评估从此节点到目标节点最便宜的路径。启发式通常用于资讯充分的搜寻算法, 例如最好优先贪婪算法与A*。最好优先贪婪算法会为启发式函数选择最低代价的节点;A*则会为g (n) +h (n) 选择最低代价的节点, 此g (n) 是从起始节点到目前节点的路径的确实代价。如果h (n) 是可接受的, 也即h (n) 未曾付出超过达到目标的代价, 则A*一定会找出最佳解。
现仍以分送式路线选择为例, 其计算程序如图1所示。 (图1) 其中:Lj-货运点j的里程系数;R-组成循环回路的货运点数;f-货运点总数;i, j-货运点序号。
三、基于启发式算法的汇集式路线选择
某仓库K拟采用一辆中型载货汽车 (Q0=4吨) , 将瓶装氧气分送给B1、B2、B3、B4四个货运点, 各点之间的距离如图2所示。 (图2)
下面, 用图2所述的启发式算法确定分送式的最佳行驶路线。
(1) 根据图1所示, 编制里程矩阵, 求货运点的里程系数, 即Lj, 如表1。 (表1)
(2) 确定初选循环回路。按Lj值的从大到小, 依次选取三个货运点 (B0, B2, B1) 组成最初循环回路:B0→B2→B1→B0, 其货运点数R=3。
(3) 确定插入货运点。在剩余的货运点中, 选取Lj较大的B3 (L3>L4) 为待插入货运点, 即x=3。
(4) 计算各路插入货运点x后的里程增量Δij:
(5) 确定插入位置, 组织新的回路。选取Δij最小值的路段作为插入货运点的路段。因为Δ2, 1=1是三个路段增量中的最小值, 所以选择B2→B1路段作为点x的插入位置, 组成新的回路:B0→B2→B3→B1→B0。因为现有循环回路的货运点数为4, 即R
因为Δ0, 2值最小, 所以选择B0→B2作为B4的插入点, 得到最终的循环回路:B0→B4→B2→B3→B1→B0。按照此循环回路的绕行次序, 车辆的总行程为∑L=L0, 4+L4, 2+L2, 3+L3, 1+L1, 0=29.5 (公里) 。这里需要说明的是, 启发式算法求得的解是近似求解, 并不一定是最优解, 但一般也是令人较为满意的解。
汇集式的运输线路的组织工作较为复杂, 但有利于做到“取货上门, 送货到家”, 可有效满足客户需求, 在配送运输中被广泛应用, 在汇集式运输线路的选择中, 以运输费用最低为原则。运用启发式算法, 可以较为准确地确定最佳行驶路线。
参考文献
[1]孙媛.企业物流网络规划研究.同济大学学位论文, 2008.
现代启发式算法 篇7
股票投资活动主要包括两个问题,其一为股票的选择问题,其二是股票买卖的择时问题,本文主要讨论第一个问题.
自股票诞生以来,它就一直是金融市场上最主要的投资方式之一,国内外的投资者和研究者都致力于研究出一套方法,使之能够选择出具有良好未来收益的股票并将其作为投资组合的一部分。Guo和Zhang[1]应用层次分析法(Analytic Hierarchy Process,AHP),将复杂的问题抽丝剥茧,用权重代表不同底层因子对选股决策的影响程度,以得到分程度考虑了所有重要因素的选股决策。Kuo等[2]结合遗传算法和模糊理论建立了一个用于股价追踪和投资组合建立的人工智能系统。Tsumato等[3]运用粗集理论(Rough Set,RS)按设定目标进行分类以此找出收益性显著不同的几个股票类别,从收益性良好的股票集中挑选股票以建立投资组合。但是,由于股票的选择是一种多目标多约束的决策活动,而且金融数据往往是多维且大量的,传统的一些选股模型在处理高维、非线性的数据时往往会遇到挑战。例如之前提到的层次分析法(AHP)就更适合于处理线性、低维的数据。后来兴起的机器学习理论———人工神经网络由于能通过自主的机器学习探究复杂、高维数据背后的规律,并且有一定的泛化能力,因此在股票选择方面取得了一定的效果,这可参见Faria等[4],Zhang和Wu[5],国内方面也出现了很多基于人工神经网络结合各种数据预处理方法的研究,比如胡静和吴强[6],吴微等[7]。但同时它也存在着很多缺陷,比如网络结构确定比较困难;训练过程容易陷入局部极小点;经常存在过拟合、欠拟合的问题,导致了预测推广能力的降低。Vapnik[8]提出了一种新的机器学习方法———支持向量机(Support Vector Machine,SVM),能够很好地解决高维度、复杂数据的学习问题,可以克服神经网络等方法固有的过拟合和欠学习的现象,由于其特有的优点在很多方面都有应用。国内外运用支持向量机对股价走势预测,或者专门对股价的反转点进行预测方面的研究较为多见且有不错的效果,可参见Yeh等[9],黄朋朋[10]。但是应用支持向量机来建立选股模型这方面的研究却比较少,特别地,国内基于大样本股票数据的支持向量机选股模型还很不充分。
本文的研究就是将支持向量机的机器学习原理应用于国内的股票市场,建立一个行之有效的选股模型。将上证A股所有上市公司年报的财务分析指标作为原始高维样本,用一种启发式算法(HA)将该原始样本进行预处理,即在保持原有信息的基础上降维并提取特征信息,再将处理过的数据按年份分为训练样本和预测样本,利用支持向量机(SVM)的模式识别原理对训练样本进行训练,得到一个能识别出高额收益股票的选股模型(HA-SVM),再根据该模型对第二年的高收益股进行预测,并与预测样本比对以此得到该模型的分类有效性。
另外,支持向量机与神经网络一样,是一种机器学习理论,训练集对于最终模型的有效性起着至关重要的作用,多数研究者[11,12]在通常运用主成分分析法(PCA)来提取训练集,在降维的同时保持原数据大部分特征信息,以此提高训练效果。但是随着样本数的增加,主成分对总体信息的解释能力会越来越弱。因此,本文会把提出的启发式算法与被广泛使用的PCA法进行比较分析,通过最终所选股票组合的年收益率对比来说明本文HA-SVM模型的优越性。
2 启发式算法的支持向量机选股模型
本节简要叙述达到本文研究目的所需要用到的一些方法,包括主成分分析法,启发式算法和支持向量机。支持向量机的模式识别算法是本选股模型的核心方法,训练集质量的好坏对最后模型的构建起着十分重要的作用。由于原始数据量非常庞大,维度也很高,为了有效地实现分类识别,需要对原始数据进行降维和变换,得到最能反映原始数据分类本质的特征。主成分分析法是广泛使用的数据特征提取法,但在处理非线性、高维数据时表现一般,因此本文提出启发式的数据处理法与之进行对比分析。
2.1 主成分分析法(PCA)
在对实际问题的研究中往往会涉及到很多相关的变量,虽然每个变量都提供了一定的信息量,但它们的重要程度差异很大,加之变量之间也存在着相关性,比如一个上市公司的财务指标有盈利能力,成长能力,偿债能力,风险水平等多个方面,每个方面也涵盖了数个不同的指标。若将所有数据都作为输入变量则会造成数据的冗余和低效,更有可能降低实证结果的质量,因此可以对这些数据进行整合和变换,用少数的新变量来反映原始数据的极大部分信息,这些新变量即称为主成分。
(1)主成分的数学定义
设X1,X2,…,Xn为原始数据的n个变量,记X=(X1,X2,…,Xn)T,其协方差矩阵为Σ=(σij)n×n,设
在Cov(Yi,Yj)=αTi·Σ·αi=0,j=1,2,…,i-1和αTi·αi=1的约束条件下,求αi使得Var(Yi)达到最大,由αi确定的
称为X１,X２,…,Xｎ的第i个主成分。
(2)主成分的计算和选取
原数据向量X=(X1,X2,…,Xn)T的协方差阵为Σ=(σij)n×n,该阵为对称非负定阵,因此有n个特征根和n个特征向量。设其特征根为λ1≥λ2≥…≥λn≥0,正交单位特征向量为e1,e2,…,en,数据集X1,X2,…,Xn的第i个主成分
此时有:
其中,第j个主成分的贡献率为,前p个主成分的累积贡献率表示经过主成分法提取后的主成分Y1,Y2,…,Yp对原始数据的解释程度。通常要求选取的主成分个数能使累积贡献率cul(p)≥85%,否则视为丢失过多原数据信息。按要求选取主成分之后,就可将已降维的主成分数据集代替高维、复杂的原始数据作为支持向量机的训练样本。
(3)变量的标准化处理
由于上述的主成分分析法是从计算变量的协方差矩阵出发,但是协方差矩阵易受变量的数量级和量纲影响,因此要对原始数据进行标准化处理,常用的对数据X1,X2,…,Xn的标准化处理办法有两种:
1正态标准化
2均值标准化
2.2 启发式算法(HA)
影响一只股票投资价值的财务指标可以分为7个大类,即盈利能力,营运能力,股东获利能力,现金流量能力,发展能力,风险水平,偿债能力。每个大类还涵盖了若干个子指标,以盈利能力为例,其包括息税前利润率,资产报酬率,净资产收益率。由于这三个子指标反映的都是公司的同一个能力,相互之间的优劣重要程度较容易判断。本文启发式算法根据某股票每个大类里(如盈利能力)的子指标在所有样本股中所属的优劣层次给每一个子指标进行评分,再根据这三个子指标之间的相对重要程度构造判断矩阵,由判断矩阵得到每个子指标相应的权重,最后根据子指标的评分和权重可以得到该股票该大类(如盈利能力)的总分值。依据此法,最终可以得到该股票财务指标7个大类的相应分值,获取原样本代表优劣的特征信息的同时也将原数据从高维降低到了7维,将该HA算法得到的分值集作为支持向量机的训练样本。
(1)判断矩阵的构造
判断矩阵是决策者给出的各个要素之间相对重要性的主观经验判断。判断矩阵是以母要素作为评价标准,通过对子要素进行两两比较,从而确定判断矩阵的元素的。例如可用A:B1,B2,B3代表盈利能力:息税前利润率,资产报酬率,净资产收益率的所属关系,A:B1,B2,B3的判断矩阵为B=(bij)3×3,判断矩阵内的元素bij也称为标度,在此用1~9标度法来为两两元素之间的相对重要性标度。
若判断矩阵中的元素为标度值的倒数则意义为若i与j比较的重要性为bij,则j与i比较为1/bij.
(2)权重的计算和检验
以A:B1,B2,…,Bn为例,本步骤旨在计算B1,B2,…,Bn各自的权重,权重表示Bi对于A的重要程度,对于这一问题,运用特征根法[13]解决。
对于n个B1,B2,…,Bn,根据1~9标度法通过两两比较得到判断矩阵B=(bij)n×n,将解特征根问题:
得到的特征向量w=(w1,w2,…,wn)经归一化后作为要素B1,B2,…,Bn在A下的权重向量。
通过一致性检验可以确定权重向量的可靠性,保持主观判断与逻辑上的一致性,即避免出现“B1比B2极度重要,B2比B3极度重要,B3又B1比极度重要”这样的自相矛盾的情况,这将导致各个因素之间的权重计算失去合理性与科学性。因此要对判断的相容性和误差进行分析:
①设一致性指标为C.I.,即有C.I.=(λmax-n)/(n-1),其中λmax是判断矩阵的最大特征根。
②根据判断矩阵的阶数查找相应的平均随机一致性指标R.I.
平均随机一致性指标是多次(500次以上)重复进行随机判断矩阵特征根计算之后取算术平均得到的。龚木森、许树柏[14]得出的1~15阶判断矩阵重复计算1000次的平均随机一致性指标如下:
3计算一致性比例C.R.= C.I./R.I.,一般情况下,若C.R.<0.1,就可以认为判断矩阵有相容性。据此,由判断矩阵计算出来的权重向量就可以被接受。
2.3 支持向量机(SVM)
(1)SVM线性分类
SVM线性分类即在数据线性可分的情况下通过求解最优分类超平面来实现分类。数据线性可分见图1,若数据集中的两类样本(C１,C２)可用二维空间上的线性函数正确分开(如H０),则称这些数据是线性可分的,否则为线性不可分。
假设训练集为train={(x1,y1),(x2,y2),…,(xn,yn)},xi为样本信息向量(在二维坐标轴平面上就是坐标向量),Yi∈Y={+1,-1},+1代表C1类,-1代表C2类,设线性分离超平面H0:wT·x+b=0将训练集正确分离,则有:当yi=+1时,wT·yi+b≥+1;当yi=-1时,wT·xi+b≤-1。若该超平面离两类样本群的距离之和D*最大,则称该超平面为这个分类问题的最优分类超平面。
定义D*=d++d-,其中
上述寻找D*最大的最优分类超平面的问题等价于找到与H0:wT·x+b=0平行的两个超平面H1:wT·x+b=+1和H2:wT·x+b=-1,在保证这两个平面之间没有样本的同时,最大化H1和H2之间的间隔。将wT·x+b=±1代入式(6)和式(7),可以得到D*=d++d-=2/‖w‖,求H0:wT·x+b=0的问题即可转化为求能使‖w‖最小的w的最优化问题。(b在求得w后可通过样本点的代入来得到。)
另外,为了避免两个平行超平面之间距离达到极大但是没有实现有效分类的情况,即图1中H′1和H′2的情况,必须对该w的最优化问题加上约束条件(即能被该平面正确分类):当yi=+1时,wT·x+b≥+1;当yi=-1时,wT·x+b≤-1,可统一写成
最后,若样本点中出现图1中加粗样本点的情形,即极少数本属于C1类的样本因为异常情况,其特征信息却和C2类的样本特征相似。如果在寻找最优超平面时将这些离群值也考虑进去就可能最终得不到一个线性超平面,因此需要使最优化过程有一定的容错性。因此在约束条件当中加入松弛变量ξi,得到新的约束条件:
再引入惩罚因子C,将之加到目标函数中,用以表示容错离群点带来的损失。因此,支持向量机模型的训练等价于下面的二次规划问题:
求解该二次规划问题,引入拉格朗日函数:
令,得到,这三式构成(10)的KKT条件,又由于(10)是凸二次规划,它们也是(10)解的充分必要条件。把它们代回拉格朗日函数,得到(10)的对偶规划:
最优解为w*=∑yiλ*ixi,w*T·x+b*=0即为相应的最优分类超平面,那么分类决策判别函数为
f(x)=1为一类,f(x)=-1为另一类,依靠决策判别函数就可以将预测集分类,这样就达到了对目标股票池优劣分类的目的。
(2)SVM非线性分类与核函数
上节讨论的是支持向量机的线性分类,在原空间直接建立一个超平面作为分界面,这只有在样本集是线性可分的情况下才可行,本节提出SVM的非线性分类来解决二维平面上线性不可分的问题。通过事先选择的一种非线性映射(即核函数)把输入向量x映射到高维空间H,即φ:Rn→H;x→φ(x),使得数据在高维空间线性可分,然后在高维空间构造如前文所述的最优线性分类超平面,达到求解高维、非线性分类的目的。
设训练集为train={(x1,y1),(x2,y2),…,(xn,yn)},xi为高维的样本信息向量,Yi∈Y={1,-1},通过映射φ,可以得到类似(11)的如下形式的二次规划问题:
在(13)中若要求解该问题,需要知道具体的φ:Rn→H;x→φ(x),但核函数k(x,y)=<φ(x),φ(y)>可以直接得到输入向量在高维空间的内积值<φ(xi),φ(xj)>,这样就可以规避探求复杂的映射φ,只需要在原空间Rn上计算k(x,y)而不需要在空间H上运算。
大量的实证经验表明,高斯径向基核函数具有良好的可分性,即通过特征变换能够将训练样本在高维空间中线性分类,因此我们在实证模型选股中选取高斯径向基核函数。
3 数据选择与训练
3.1 数据选择
选取2009~2010 年所有上证A股(数据不全的剔除)年报数据上的财务指标总共7大类20个指标,由于金融类企业的资本结构与其他企业相差太大,所以剔除了36家金融类企业,具体见表3,数据源于国泰安数据库。2009年的数据作为训练集的原始数据,2010年的数据作为预测集的原始数据。
本文目的是根据公司的财务指标进行优劣分类,所以需要对公司公布年报之后的股票收益情况进行标识。经统计,2009年和2010年所有上证A股公司都于当年5月1日之前公布了年报,所以将2009年5月至2010年5月股票收益率位于前25%的股票标识为1,即yｉ= 1,其余yi =-1。
3.2 基于PCA的训练集提取
把2009年652个公司,每个公司7类20个财务指标作为训练集提取的原始数据集。如2.1节所述,用主成分法提取该原始数据集里累积贡献率能够大于85%的主成分来构成SVM非线性分类训练集的一部分。但是由于符合要求的主成分个数会随着所用样本数量的增大而增大。例如,对含25~39个股票的样本提取主成分,提取6个主成分就能满足85% 的要求,但若股票区间为52~118,则需要7个主成分,如图2所示。
若一次性提取所有数据的主成分,不仅会丧失局部信息,也会使得降维效果微乎其微,因此我们采取分步提取,为了兼顾降维效果和和信息提取效果,每40个样本股作一次主成分提取,将原数据降至7维。提取的主成分结合3.1节中用来标识股票收益率的yｉ,可以得到PCA法的训练集,结果如表5所示。
但上述方法仍存在缺陷,若分步对每40个样本提取7个主成分,每次提取的7个主成分对原有样本的解释能力也是不同的,其波动情况如图3。因此依靠主成分法对大样本形成训练集并不是最优的方法。
3.3 基于HA的训练集提取
同样地,HA训练集提取的原始数据也是2009年652家公司7类20个指标的财务数据。提取步骤如2.2节所述,在HA算法中首先给每个财务指标进行评分,评分标准按照该指标在所有样本股里所占的分位数,如股票600020的净资产收益率的值在所有股中为75% 分位数,则给予其75分。为了使分类更易区分出优势股并剔除异常值的影响,大于95% 分位数的均给予95分,小于30%分位数的均给予30分。由于每个大类(盈利能力、营运能力等)之间对于股票投资价值的重要程度较难判断,而每个大类里面的子指标反映该大类优劣的程度较为容易定性判断,比如盈利能力中的净资产收益率、资产报酬率、息税前利润率在体现盈利能力时有着较为明显的重要性差别,因此HA算法接着对同属一个大类的财务指标建立判断矩阵,求出每类子指标的权重向量,见表4(只以盈利能力和营运能力为例)。最后,将权重向量与各子指标评分值相乘就可得到每只股票7方面能力的分值,再结合标识股票收益率的yｉ,得到的训练集如表5所示。
注:①此处为了说明方便,用表格形式代替矩阵;②A指盈利能力,B指营运能力,子指标ai,bi如表3所示。
4 模型选股与结果分析
4.1 决策判别函数
为了实现对目标股票池股票的优劣分类,需要得到2.3节所述的决策判别函数,本文对于支持向量机的训练和测试是在Matlab下的Libsvm3.1下完成的。我们将表5中的PCA训练集(原始数据在进行主成分提取之前先分别进行均值标准化和正态标准化处理)和HA训练集分别作为Livsvm工具箱的输入数据,经过支持向量机算法(SVM)的训练(即解最优化问题)可以分别得到在PCA法和HA法下的参数wｉ＊和b＊以构成非线性分类的决策判别函数:
其中,g=1/σ2事先人为给定,w*i=yiλ*i,i为支撑向量的个数,训练参数结果如表6所示。
再将训练集内的数据回代入上述决策判别函数之后,训练集被该决策函数分为y*i=+1和y*i=-1类,分别表示被该决策函数认定的高收益股和低收益股。
由于训练集本身就有用来标识股票实际收益性的yi,将y*i和yi进行对比可以知道模型的训练分类准确率,例如:
其中,Num(y*i=+1|yi=+1)表示实际yi=+1的股票被正确分类为y*i的个数,Num(yi=+1)表示实际为+1类的股票的个数,-1类的准确率也以此类推。
PCA和HA下的训练分类准确率和整体分类准确率结果如见表7。
注:a表示训练集,b表示预测集。
4.2 SVM非线性选股和分析
相似地,用与提取训练集同样的方法对2010年的原始数据进行预测集的提取,同样也分为PCA预测集和HA预测集,将这两个预测集的数据分别代入上述决策判别函数(14)后,可以将预测集的股票分为yi=+1类和yi=-1类,+1类代表未来会产生高额收益的股票,-1类则代表低收益股。同时也能得到yi=±1的分类准确率和整体分类准确率,结果见表7。
从表中观察可得,当用均值标准化PCA法进行训练集的提取时,训练集+1类的分类准确率达到了100%,但是在预测集里的准确率却只有10.1266%,这是因为出现了过拟合的现象,即模型训练时用了数量很多的支撑向量来支持训练集的特征,仅针对训练集可能分类效果很好,但是一旦应用于测试集就会出现泛化能力差的情况。正态标准化PCA-SVM模型虽然实现了较好的准确率,但是HA-SVM模型每一个类别的分类效果都要明显好于正态标准化PCA-SVM的分类效果,这也证明了本文3.2节提到的主成分提取法的诸多缺陷,同时也从分类准确率的角度上说明了HS-SVM的优越性。
4.3 选股模型收益分析
进一步地,本节从模型选股收益的角度对两种方法进行对比分析。由于均值标准化的PCA-SVM模型出现了过拟合的现象,因此只利用正态标准化PCA-SVM和HA-SVM模型的分类结果。
如上节所述,通过对2009年训练集的学习训练可以得到用于股票优劣分类的决策判别函数,再将基于2010年原始数据的预测集代入该决策判别函数中,得到+1类和-1类两类股票作为依靠选股模型对未来的预测。本文在训练时选取的收益标识yi记录的是财务指标披露一年后的收益情况,因此,该预测覆盖的投资区间相应的是2010年5月至2011年5月。选取+1类的股票作为投资组合的成分股,在考虑上市公司资本规模的情况下,再根据其每只股的月流通市值赋予相应的投资权重。因此该投资组合的单位时段收益Rt和累计收益倍数ACRT可以表示如下:
其中,rti表示个股的单位时段收益(可以使日均,周均或月均),FCi表示个股流通市值,T表示组合持有周期。
除了对PCA和HA两种方法下构建的投资组合收益差别的对比分析之外,也有必要将这两者的收益与一个基准进行分析。由于在数据处理时已经剔除了部分股票,直接将上证A股指数作为基准不合适,因此把所有样本股按流通市值加权平均后的投资组合作为基准组合。PCA-SVM、HA-SVM和基准组合三者之间的累计收益倍数(ACRT)的对比分析结果如图4、图5所示。图5显示HA-SVM选股模型一年内取得的累计收益倍数显著优于PCA-SVM选股模型,证明本文的启发式算法在处理复杂、高维、大量并且可以局部定性分析的数据上比主成分法更有优势。图6表明PCA-SVM只在考察期最初的时间段内优于基准组合,但是HA-SVM模型在考察期大部分时间内收益状况一直优于基准组合,在考察期期末时仍略微高于基准组合,只要在考察期中挑选合适时机卖出即可获得可观收益。
下面将收益的考察期限延长为2010 年5 月至2013年5月,观察HA-SVM模型和基准组合的收益情况,结果如图6所示,表明HA-SVM模型虽然在一年之内的考察期表现良好,但是在一年之后收益表现开始出现不稳定,不能明显地优于基准组合,投资时需要灵活掌握组合的持有时间。
5 结束语
在股票市场的研究中,支持向量机多数都被用于通过历史数据来对未来股价进行预测从而获得高额收益,本文利用支持向量机的模式识别理论通过对样本股财务指标的训练来构建高维空间的最优分类超平面,相当于建立了财务指标与股票收益表现之间的一种高维、非线性关系,本质上讲是基于价值投资的理念来构建投资组合从而获得高额收益,本文的非线性SVM分类取得了很好的实际效果。
另外,支持向量机是一种机器学习理论,需要对历史数据进行学习,因此训练集对于最终模型的有效性起着至关重要的作用,多数研究者在形成训练集的数据预处理阶段通常运用主成分分析法(PCA)将高维数据降为低维,同时保持了原数据的大部分信息特征,以此来提高训练效果。在本文的研究中发现当样本是公司财务指标这类大量、高维的样本时,PCA法提取数据特征的效果存在着诸多弊端,以此提取的训练集对最后的分类效果并不是最优的。本文提出了一种启发式算法(HA)的数据预处理方法来生成支持向量机的训练集,该方法可以规避PCA法遇到的降维效果差以及对原数据解释程度不一等问题。最后将HA-SVM模型与PCA-SVM模型得到的股票累积收益对比也证明了本文基于启发式算法的支持向量机选股模型更有优势。