• Archive by category "程序算法"

Blog Archives

算法,如何改变命运

架构师的信仰系列文章,主要介绍我对系统架构的理解,从我的视角描述各种软件应用系统的架构设计思想和实现思路。

从程序员开始,到架构师一路走来,经历过太多的系统和应用。做过手机游戏,写过编程工具;做过大型Web应用系统,写过公司内部CRM;做过SOA的系统集成,写过基于Hadoop的大数据工具;做过外包,做过电商,做过团购,做过支付,做过SNS,也做过移动SNS。以前只用Java,然后学了PHP,现在用R和Javascript。最后跳出IT圈,进入金融圈,研发量化交易软件。

架构设计就是定义一套完整的程序规范,坚持架构师的信仰,做自己想做的东西。

关于作者:

  • 张丹(Conan), 程序员R,Nodejs,Java
  • weibo:@Conan_Z
  • blog: http://blog.fens.me
  • email: bsspirit@gmail.com

转载请注明出处:
http://blog.fens.me/architect-algorithm/

前言

近年来,随着大数据的飞跃式的发展,已经越来越深地开始影响到我们的生活,社交有腾讯大数据,购物有阿里大数据,搜索有百度大数据,出行有滴滴大数据等等。当数据越来越多地被积累,就需要算法来挖掘出数据的价值。特别是进入到大数据时代,算法显得越来越重要。

让死的数据变得有价值,就是算法的力量。进入到全民大数据的时代后,数据已经不再是门槛儿,最重要的是算法,算法才是真正能够创造生产力的地方。算法工程师的价值也会越来越大,但是你们真的发掘出来你们的价值了吗?

目录

  1. 算法在各个行业的应用
  2. 投身于哪个行业好?
  3. 金融最靠谱

1. 算法在各个行业的应用

大数据的兴起冲击着各行各业,带来机遇也带来挑战,没有数据你就没有核心价值。当有了数据作为基础,你要继续需要思考如何让数据变的有价值。过去的2016年的投资市场很惨淡,唯有人工智能大火了一把。从深度挖掘(Deep Learning)技术在图像识别领域的精确识别,迭代决策树(GBDT)在数据挖掘算法比赛中频繁获奖,到AlphaGo在围棋领域打败在人类选手,百度小度机器人在最强大脑的舞台上挑战人类脑王等等,这些事件都是算法领域的突破。

算法,真的已经应用到了各行各业,在慢慢地改变着人们的生活和习惯,比如说图像识别,自动驾驶,用户行为,金融征信,量化投资等领域,都在发生着变化。

图像识别领域,深度学习算法异军突起,不仅可以进行准确的人脸识别、指纹识别,还可以进行复杂的图像对比。我深刻记得,2016年参加的光谷人工智能大会上,听西安电子科技大学公茂果教授分享的“深度神经网络稀疏特征学习与空时影像变化检测”主题,利用图像识别技术,对比汶川地震前后的卫星照片和光感照片,准确地找到了受到地震影响最严重的区域,即震前和震后地貌发生变化最大的区域,快速地为救援队定位到最需要帮助的地点,解救伤者,投放救援物资。

自动驾驶领域,可以通过识别路面的状况来实现自动驾驶、自动停车。Uber无人驾驶汽车已经在匹兹堡上路测试,自动驾驶汽车配备了各式传感器,包括雷达、激光扫描仪以及高分辨率摄像头,以便绘制周边环境的细节。自动驾驶汽车有望改善人类的生活质量,也可挽救数百万人的性命,为人们提供更多的出行方便。5年前,我在听Andrew Ng的斯坦福大学机器学习公开课的时候,就被当时的自动驾驶视频介绍所震撼,科幻电影中的世界就快变成现实了。

用户行为分析,人类有各种各样的行为和需求。衣食住行,吃喝玩乐,都是人的最基本的行为。大多数人的行为是共性的,商家可以收集这些行为数据,通过数据挖掘算法来找到人们行为共性的规律。根据用户的购物行为,商家可以为用户推荐喜欢的商品,这样就有了推荐系统; 根据用户对信息的查询行为,可以发现用户对信息的需求,这样就有了搜索引擎;根据用户位置的变化,可以发现用户的出行需求,这样就有了地图应用;针对用户个性化的行为,可以给用户打上标签,用来标注用户的特征或身份,这样就有了用户画像。用户行为分析,让商家了解用户习惯,同时也让用户了解自己,有巨大的商业价值。

在金融领域也有很多,算法应用的场景。

金融征信领域,传统信贷业务都是银行核心业务,但由于中国人数众多且小客户居多,银行无法负担为小客户服务的高成本,导致民间信贷的兴起。2014年底互联网金融P2P的开始爆发,贷款需求被满足的同时,却暴露出了违约风险。征信体系缺失,导致很多P2P公司坏账率很高,到2016年底P2P跑路的多达数千家。征信需求,变得非常迫切。比如,某个人想买车但现金不够,这时就需要进行贷款。商家给用户进行贷款时,通过信用风险的评级就能判断出这个用户的还款能力,从而来决定给他贷多少钱,以什么周期还款,减少违约风险。支付宝的芝麻信用分,是目前被市场一致认可的信用评分模型。

量化投资领域,我认为这个领域最复杂的,最有挑战性的,同时也是最有意思的。可以通过量化算法模型实现赚钱,是最容易变现的一种方法。在金融投资领域中,有各式各样的数据,反应的各种金融市场的规则,有宏观数据,经济数据,股票数据,债券数据,期货数据,还有新闻数据,情绪数据等等,金融宽客(Quant)通过分析各种各样的数据,判断出国家的经济形势和个股的走势,进行投资组合算法,实现投资的盈利。

看到这里,我想问问大家,你们脑子里那些聪明的想法,有没有被金融行业的魅力撩出些许的荷尔蒙?

2. 投身于哪个行业好?

从上面各个行业的算法应用来说,都有很广阔的应用前景。作为一个算法的研究者,那我们究竟投身到哪个行业更好呢?

这个其实要从多个方面进行考虑,我们的目标是个人价值最大化。那么,你要选择一个自己能够接触到的、完全竞争的、短流程的渠道,利用你的算法技术和对业务的理解实现变现的过程。

其实,满足个人可变现的渠道其实非常有限,你很难通过一个图像识别的算法,直接面向市场进行收钱,你需要有一个承载的产品,而产品研发的过程是非常漫长的。同样地,自动驾驶算法需要汽车生产场商的实验。用户行为分析算法,需要电子商务平台的以用户购买行为进行验证。

量化投资,可以用个人账号在中国二级投资交易市场,完成交易过程。这种方式没有很多的中间环节,你获得交易所的数据,自己编写算法模型,然后用自己的钱去交易,完全自己把握。只要算法有稳定的收益率,你就可以赚到钱。这种变现方法,其实就是量化投资,从金融的角度才是最靠谱的一种变现方法。

3. 金融最靠谱

作为IT人,我们懂编程,懂算法,只要再了解金融市场的规则,就能去金融市场抢钱了。中国的金融二级投资交易市场,是一个不成熟的市场,同时又是情绪化的市场。市场中,每天都存在着大量的交易机会,每天都会有“乌龙指”。量化投资的技术,可以帮助我们发现这些由于信息不对称出现的机会,赚取超额的收益。

那么到底怎么做量化投资呢?。

下面举个例子,一个私募基金,募集了1亿资金准备杀入金融市场。基金经理决定按照投资组合的建模思路,对各类金融资产进行组合配置。下图就反应了各类资产,以均值-方差的标准来创建投资组合,符合资本资产定价模型(CAPM)的原理。关于资本资产定价模型详细介绍,请参考文章R语言解读资本资产定价模型CAPM

图中,x轴为收益率的标准差,y轴为收益率的均值,图中的点构建了可投资区域,每个点代表一个可投资产品,每条虚线连接的点的集合,就是一个有效的投资组合。

对于,图中近百个点来说,假设每次要配置5种资产做投资组合,那么就是75287520种组合方法;如果配置10种资产,可选方案就是一个非常大的数字了。

我可以用R语言来计算一下,投资组合的数量。


# 100个选5个,做组合
> choose(100,5) 
[1] 75287520

# 100个选10个,做组合
> choose(100,10) 
[1] 1.731031e+13

对于金融市场来说,有非常多的金融资产可供我们来选择。中国A股股票有3000多只,基金2000多支, 债券3000多支,期货100多支,还有大综商品,货币市场产品,汇率产品,海外投资市场等。如果把这个多种的资产进行组合,将有无限多的投资组合可以进行选择,是一个无限大的计算量。我们需要利用算法进行组合优化,从而找到市场上最优的投资组合。算法本身,才是最能体现价值的部分。

那么传统的基金是如何进行投资组合的?大多都是靠投资经理的主观投资经验来完成的。在金融市场里,每支基金都配置了不同的资产做组合,我们随便找支基金看看,它的投资组合是如何配置的。比如,华夏成长(000001.OF)基金,它是股债混合型的。数据来源于万得, 2017年2月8日的数据。

从业绩表现来看,这支基金最辉煌的时代在2006-2007年,连续6个月回报101.49%,那么最低1年表现就比较差,为仅落后于沪深300指数,整体排名也都在后面。今年以来收益率0.58%,同类排名144/507;1年收益率-1.45%,同类排名400/487;3年收益11.67%,同类排名378/426;5年收益39.96%,同类排名290/352。

我们再来看一下,这支基金的组合成分,主要是股票和债券。

债券占比 :

证券名称 占净值比 近3月涨跌
12石化01 2.34%↑ -0.49%
116国泰君安CP008 2.12%↑ -0.03%
116农发01 1.91%↑ -0.08%
110营口港 1.70%↑ -1.59%
109常高新 1.62%↑ -0.65%

股票占比:

证券名称 占净值比 近3月涨跌
中工国际 4.09%↑ -0.95%
中国医药 3.85%↑ 0.34%
神雾环保 3.81%↑ 2.56%
东方网络 2.89%↑ -13.00%
立讯精密 1.52%↑ -1.82%
高能环境 1.42%↑ -14.96%
上汽集团 1.38%↑ 7.88%
田中精机 1.31%↑ -12.28%
上海医药 1.25%↑ 5.39%
中牧股份 1.21%↑ -4.25%

从市场上几千支的股票和债券中进行选择,并配置不同的权重,之前都是基金经理干的活,那么我们用算法一样也可以干,说不定用算法模型构建的组合业绩会更好。如果我们用算法模型,取代了年薪几百万的基金经理,那么你就能够获得这个收益。最终实现个人价值,从而用算法改变命运。所以,通过金融变现才是最靠谱的。

转载请注明出处:
http://blog.fens.me/architect-algorithm/

打赏作者

R语言解读资本资产定价模型CAPM

用IT技术玩金融系列文章,将介绍如何使用IT技术,处理金融大数据。在互联网混迹多年,已经熟练掌握一些IT技术。单纯地在互联网做开发,总觉得使劲的方式不对。要想靠技术养活自己,就要把技术变现。通过“跨界”可以寻找新的机会,创造技术的壁垒。

金融是离钱最近的市场,也是变现的好渠道!今天就开始踏上“用IT技术玩金融”之旅!

关于作者:

  • 张丹(Conan), 程序员R,Nodejs,Java
  • weibo:@Conan_Z
  • blog: http://blog.fens.me
  • email: bsspirit@gmail.com

转载请注明出处:
http://blog.fens.me/finance-capm

前言

伴随2016年中国金融交易市场的跌宕起伏,风险越来越不确定,利率持续走低,理财等无风险资产收益持续下降的情况,唯有投资组合才能让我们的资产保值、增值。根据资本资产定价模型(CAPM),通过对金融数据的分析,构建投资组合,帮助我们在有效的市场中控制风险、稳定收益。

本文将深入浅出地介绍资本资产定价模型,从理论到建模,再到程序现实。资本资产定价模型反应的是资产的风险与期望收益之间的关系,风险越高,收益越高。当风险一样时,投资者会选择预期收益最高的资产;而预期收益一样时,投资者会选择风险最低的资产。

由于本文为非金融教材类文章,所以当出现与教课书不符的描述,请以教课书为准。本文力求用简化的语言,来介绍自资本资产定价模型的知识,同时配合R语言的实现。

目录

  1. 故事背景
  2. 资本市场线
  3. 资本资产定价模型
  4. 用R构建投资组合模型
  5. Beta VS Alpha

1. 故事背景

1952年,马科维茨(Markowitz)提出了投资组合选择理论,他认为最佳投资组合应当是,风险厌恶特征的投资者的无差异曲线和资产的有效边界线的交点。投资者在选择资产时会在收益和风险之间做出平衡:当风险一样时,会选择预期收益最高的资产;而预期收益一样时,会选择风险最低的资产。

01

图1 投资组合选择示意图

到1964年,威廉-夏普(William Sharp),约翰-林特纳(John Lintner)与简-莫森(Jan Mossin)则在马科维茨基础上提出的单指数模型,将市场组合引入均值-方差模型,极大地简化了计算,他们认为获得了市场任意资组合的收益与某个共同因素之间是有线性关系,最终将其发展为资本资产定价模型(Capital Asset Pricing Model, CAPM)。从马科维茨的投资组合选择理论,发展到资本资产定价模型经历了一个漫长的过程。

简单一句话概括,资本资产定价模型的核心思想,资产价格取决于其获得的风险价格补偿。

假设条件

资本资产定价模型,是基于一系列假设条件而成立的。但这些条件,可能并不符合现实的标准,资本资产定价模型也一度遭到质疑。

  • 资产可以无限分割。
  • 不存在交易成本和个人所得税。
  • 可以无限卖空。
  • 存在一种无风险利率,投资者在此利率水平下,可以无限制地贷出和借入任意数额的资金。
  • 投资者是价格接受者,市场是完全竞争的。
  • 投资者是理智的,通过比较资产的期望收益和方差来作出投资决策,在相同预期收益下会选择风险最小的资产。
  • 投资者在相同的投资期限出作出决策,而市场信息是公开免费的,并可以及时获得。
  • 投资者对市场中的经济变量有相同的预期,他们对任意资产的预期收益率、市场风险的看法是一致的。

资本资产定价模型的核心假设是认为市场满足完全、无摩擦和信息完会对称的条件,市场中的投资人都是Markowitz理论中的理性经济人。

2. 资本市场线

由于涉及到金融专业领域,有几个概念是我们应该提前知道的。

  • 风险资产:风险资产是指具有未来收益能力的资产,但收益率不确定且可能招致损失,比如股票、债券等。
  • 无风险资产:没有任何风险或者风险非常小的资产,有确定的收益率,并且不存在违约的风险。
  • 收益率:指从投资开始到投资结束时,所获得的投资回报率。
  • 无风险收益率:无风险资产,所产生的投资回报率。
  • 投资组合:由投资人或金融机构所持有的股票、债券、基金、衍生金融产品等组成的集合,目的在于分散风险。
  • 杠杆交易:就是利用小资金来进行数倍于原始金额的投资,以期望获取相对投资标的物波动的数倍收益率的盈利或亏损。

2.1 风险资产

对于风险资产来说,我们可以用预期收益和风险,通过二维的坐标来进行描述。

对上图的解释:

  • X轴,为风险
  • y轴,为收益率
  • 灰色区域,为金融资产可投资区域
  • 黑色线,为有效投资边界
  • A和B点,为2个风险资产

A和B有相同的x值,表示具有相同的风险。B点在A点上面,表示B的收益率高于A。对于理性的投资者来说,如果只在A点和B点之间做投资选择,那么大家都会投资到B点,而不投资于A点。

2.2 无风险资产

在下图中,我们加入无风险资产,来比较无风险资产和风险资产的关系。

对上图的解释:

  • B点,为1个风险资产,在有效投资边界上
  • C点,为无风险资产,在y轴上
  • X轴,为风险
  • y轴,为收益率
  • 灰色区域,金融资产为可投资区域
  • 黑色线,为有效投资边界

C点为无风险资产,他的位置在图示的y轴上,这时x为0,即风险为0。我们可以把投资,分配到C点或B点上。如果都投到C点,那么我们将获得的是R0部分的无风险收益;如果都投到B点,那么我们需要承担σB的风险,同时获得RB的风险收益。如果我们把资金,一部分投资到B点对应的风险资产上,另一部分投资到C点对应的无风险资产上,那么将构成一个由B和C资产组成的投资组合,而且风险和收益部分,将体现在B和C的连线上。

2.3 最优组合

那么,有没有最优的投资组合呢?收益最大、风险最小。下面就让我们来,发现这个最优的组合M。

对上图的解释:

  • M点,为最优组合的风险资产
  • B点,为1个风险资产,在有效投资边界上
  • C点,为无风险资产,在y轴上
  • X轴,为风险
  • y轴,为收益率
  • 灰色区域,金融资产为可投资区域
  • 黑色线,为有效投资边界

假设有最优的组合,在上图中M点处,当我们把C和M进行连线,使得CM的连线与灰色区域相切。从图上看,CM的连线会比任意的C与可投资区域点的连线斜率都要大,比如C和B的连线。我们取CB的连线的延长线,在CB的延长线上找到,与M具有相同x的点B’,这时M与B’风险相同,M点在B’点的上面,所以M点的收益率大。也就是说,当风险相同的时候,我们都会选择收益率最大的资产。

不论从可投资区域中怎么选取,M点都是斜率最大的点,那么我们可以认为,M点为市场上各资产的最优的投资组合.

对于最优的投资组合,其实不管投资者的收益风险的偏好是什么样子的,只要找到了最优的风险资产组合,再加上无风险的资产,就可以为投资者获得最佳的投资方案了。那么对于理性的投资者,如果发现了最优的组合,他们只会投资于这个组合,这时与收益和风险偏好无关。

M点构建的投资组合,一般是由所有可投资证券产品组成的,每种证券资产构成的比例,为证券的相对市值。无风险资产C,并没有包括在M中,人们都会选择CM的连接线进行投资,来构建最优的投资组合。

在实际的市场交易中,金融资产的价格会发生偏离,因为价格受市场的供需关系所影响,当价格发生偏离后,市场会自动修复会回均衡价格水平。

2.4 资本市场线

对于CM的连线,就是马科维茨提出了投资组合选择理论,风险厌恶特征的投资者的无差异曲线和资产的有效边界线的交点。这条线就叫,资本市场线(Capital Market Line)。

资本市场线是指表明有效组合的期望收益率和标准差之间的一种简单的线性关系。

资本市场线决定了证券的价格。因为资本市场线是证券有效组合条件下的风险与收益的均衡,如果脱离了这一均衡,则就会在资本市场线之外,形成另一种风险与收益的对应关系。

2.5 投资组合构建

资本市场线,就是我们最优的投资组合,当我们发现这个投资组合,所有资金都会投到这个组合上。通过对无风险资产C和风险资产M分配不同的投资权重,我们可以自己配置出自己想要的风险和收益来,同时可以利用金融工具来加杠杆放大风险和收益的范围。

如果我们把投资者分成,风险厌恶型和风险激进型。

对于风险厌恶型,他们对于资金安全有非常高的要求,不追求高收益但求本金安全,这些资金通常都是用来生活的。那么在为这些资金做资产配置方案的时候,可以把一部分资金配置无风险资产上,同时少量资金配置到M点的最优组合上,保证低风险并获得少量收益。

如图中CM1点,如果配置50%的风险资产M和50%的无风险资产C,来实现投资组合。公式如下:

CM1 = 0.5C + 0.5M

对于风险激进型,他们对于资金有非常高的收益要求,本金可以部分或全部损失,这些资金通常都是“闲钱”,就是用来进行投资活动的。那么在为这些资金做资配置方案时,可以全部都投到M上,再激进点,可以通过借钱、融资的方式,增加杠杆,把资金放大进行投资。这种操作风险会随着杠杆的放大剧增,当然同时你也会有更大的收益。

如图中CM2点,落在了CM的延长线上。我们可以配置150%的风险资产M,同时用50%的钱去抵押以无风险资产C的收益率去借钱。公式如下:

CM2 = -0.5C + 1.5M

2.6 风险和收益的关系

上面我们描述风险和收益的关系,主要是从思路上定性介绍,没有进行定量描述,那么究竟风险和收益从数学上怎么进行定义呢。

对上图的解释:

  • M点,为最优组合的风险资产
  • C点,为无风险资产,在y轴上
  • r0,为无风险资产的收益率
  • rM,为M点的收益率
  • x轴,σp为风险资产的收益率的方差
  • y轴,rp为收益率

根据威廉-夏普所引入的均值-方差模型,极大地简化了计算,就是解决了公式计算的问题。用方差来刻画风险,建立收益和风险的一元线性关系。可以用下面公式来表示:

公式

E(rm) – r0 = A * σM^2

公式解释:

  • E(rm):市场投资组合的预期收益率
  • r0:无风险收益率
  • E(rm)–r0, 市场投资组合的风险溢价
  • σM^2: 市场投资组合方差Var(rM)
  • A:风险厌恶水平

有了公式,我们就明确的知道了,风险和收益的定量关系,并且可以利用数据来进行计算。

3. 资本资产定价模型

对于市场的投资组合,风险溢价和市场投资组合的方差成线性关系。但对于单个资产来说,收益和风险是市场投资组合组成的一分部,受市场共同变化的影响。

3.1 单个资产风险溢价

对于单个资产的风险来说,在资本资产定价模型中,用β来进行表示。β是衡量单个金融资产与市场收益的共同变化程度,通过协方差来计算。单个资产的风险为,当前资产与投资组合收益率的协议差,除以投资组合收益率的方差。

单个资产的风险的计算公式:


βi = Cov(ri, rm) / Var(rm) 
   = Cov(ri, rm) /  σm^2

单个资产的风险溢价的计算公式:


E(ri) – rf = (Cov(ri, rm) / σm^2)*[E(rm) – rf] 
           =  βi  *  [E(rm) – rf]

对公式的解释:

  • E(ri),为风险资产i的预期收益
  • E(rm),为市场投资组合的预期收益
  • rf,为无风险资产收益
  • Cov(ri, rm),为风险资产收益率和市场投资组合收益率的协议差
  • Var(rm),为市场投资组合的收益率的方差

从公式可以看出,单个资产的风险溢价与市场投资组合M的风险溢价成正比,受β影响。

3.2 资本资产定价模型

资本资产定价模型,是现化金融学中的基石理论。在上述假设条件下,可以推到出资本资产定价模型的具体公式。整个和推到过程,就是上面文章介绍的过程,从后人学习的角度看,这个理论比较简单的,仅用到了简单地统计学知识,但是前人却花了很长的时间研究和探索。

判断单个资产的风险时,当β=1时,则说明当前资产与整个市场的趋势是完全保持一致的;当β为2时,代表高风险,其回报的变化将大于市场大盘的变化幅度;当β为0.5时,代表是低风险的资产配置。

3.3 2种风险

在资本资产定价模型,定义了2种风险,即系统性风险和非系统性风险。

系统性风险,就是由外部因素引起的风险,比如:通货膨胀,GDP,重大政治事件等等。这一类事件对于资产收益率的影响不能通过组合本身来消除的,所以这一类风险对于投资者来说是无法回避的。

非系统性风险,就是组合内部结构引起的风险,比如:A股与B股高度相关,A股的收益率出现大幅波动的时候,B股也会出现相似幅度的波动,波峰叠加或波谷叠加,就会增加整个组合的风险;反之,如果A与B为负相关,则A与B的波动就会相互抵消。这样,风险是由组合里的资产类型决定的,所以通过多样化分散的投资策略,无论在理论还是实际上,这种风险都是可以最小化甚至消除的。而这个消除的过程中,整个投资组合的收益率是不会下降的。

3.4 2种收益

与风险相对应是收益,我们承受了2种风险的同时,也获得了风险所带来的收益。一部分是与市场完全相关收益部分,即beta(β)收益;另一部分与市场不相关的收益部分,即alpha(α)收益。

  • beta收益,相对容易获得,例如,你看好一个市场,可以持有成本低廉的对应市场的指数基金,等待市场上涨。
  • alpha收益,比较难获得,alpha是体现投资水平的策略收益。

alpha是,投资组合的实际期望收益与预期收益之间的差。计算alpha的公式为:


E(ri) – rf = αi + βi  *  [E(rm) – rf]
αi         = [E(ri) – rf] -  βi * [E(rm) – rf]

alpha是衡量投资人投资水平的,我们举个例来说明。比如:市场收益率为14%,A证券的β=1.2,短期国债利率6%,投资者对这只股票的进行了交易,获得的实际收益为17%,那么我们怎么判断投资人的水平呢?

首先,先求出A证券的预期收益率 = 6% + 1.2*(14-6)% = 15.6%,再用投资者实际收益减去A证券预期收益 17% – 15.6% = 1.4%。最后获得的1.4%就是alpha,表示投资者能力,可以额外获得1.4%的收益。

3.5 资本资产定价模型的应用场景

进行组合投资分散风险:投资者可以按市场组合的构成比例分散持有多种风险资产,使持有的风险资产组合最大限度地接近市场组合,以达到消除非系统风险的目的。

调整收益风险比例:将无风险资产与风险资产市场组合进行再组合,以获得所希望的个性化的风险收益组合。

指数化投资:将资产配置在与某一指数相同的权重的投资方法,通过微调权重或成分,获得比指数更好的alpha。

资产定价:资本资产定价模型可以用来判断有价证券或其他金融资产的市场价格是否处于均衡水平,是否被高估或低估,以便通过套利活动获取超额收益。

基金购买:举一个贴近市场的例子,当我们要购买基金时,也可以用到资本资产定价模型帮我们分析。比如,基金A的期望收益率12%,风险β=1,基金B期望收益率13%,β=1.5。市场期望收益率11%,无风险资产收益率r0 = 5%。 那么哪只基金更值得买?

当你每天打开支付宝,看到里面的各种基金推荐。你就会发现这是一个实际的问题。如果你懂学了本文,按照资本资产定价模型的思路,其实就是求alpha,哪个基金的alpha高,就买哪个。

求alpha,我们就直接套用公式。


αA = 12 – 5 – 1 * [11 - 5] = 1%
αB = 13 – 5 – 1.5* [11 -5 ] = -1%

基金A的alpha为1%,而基金B的alpha为-1%。结论就很明显,基金A的管理人能力很好,超额收益1%;而基金B的管理人,就差一些,盈利低于市场1%。所以,我们会投资基金A,而不会投资基金B。

4. 用R构建投资组合模型

花了大量的篇幅介绍了资本资产定价模型的原理,对于程序实现其实是相当简单地。因为R语言中,已经把资本资产定价模型相关的计算函数都封包好了,我们仅仅是调用就能完成整个的计算过程。

R语言程序实现,我们主要会用到2个包,quantmod和PerformanceAnalytics。对于为什么要用R语言,可以参考文章R语言为量化而生

  • quantmod,用于下载数据。
  • PerformanceAnalytics,用于进行各种评价指标计算。

我们设计一个应用场景,假如我有10万美金想投资于美国的股市,我想获得比标普好(SP500)的投资收益,那么我应该如何购买股票。

首先,我们先想清楚,我的最终的目标是“比标普好的投资收益”。其次,我们基于资本资产定价模型理论基础,从投资组合角度思考投资策略,而不是技术指标的角度。比标普好,那么我们就需要以标普指数做为理想投资组合。然后,我们去市场上选择几个股票,分别计算出收益率,beta,alpha等指标,判断是否符合的预期,反复测试,直到找到合适的股票或股票组合。

本文只是案例介绍,用于说明投资思路和方法,不购成任何的股票推荐。

本文的系统环境

  • Win10 64bit
  • R version 3.2.3 (2015-12-10)

从yahoo下载IBM,GE(通用电器),YHOO(Yahoo)的3只股票,从2010年01月01日的日行情数据,同时下载标普指数(SP500)的日行情数据。

下面代码并不完整,但思路已经给出,请大家不要太随意地张嘴要数据和代码,毕竟写一篇文章非常辛苦。如果你想直接用我的代码,请扫文章下面二维码,请作者喝杯咖啡吧。 :_D

执行R语言程序。


# 加载程序包
> library(quantmod) 
> library(PerformanceAnalytics)

# 从yahoo下载3只股票的数据,和SP500的数据
> getSymbols(c('IBM','GE','YHOO','^GSPC'), from = '2010-01-01')

# 打印前6行和后6行数据
> head(GSPC)
              open    high     low   close     volume adjusted
2010-01-04 1116.56 1133.87 1116.56 1132.99 3991400000  1132.99
2010-01-05 1132.66 1136.63 1129.66 1136.52 2491020000  1136.52
2010-01-06 1135.71 1139.19 1133.95 1137.14 4972660000  1137.14
2010-01-07 1136.27 1142.46 1131.32 1141.69 5270680000  1141.69
2010-01-08 1140.52 1145.39 1136.22 1144.98 4389590000  1144.98
2010-01-11 1145.96 1149.74 1142.02 1146.98 4255780000  1146.98

> tail(GSPC)
              open    high     low   close     volume adjusted
2016-12-20 2266.50 2272.56 2266.14 2270.76 3298780000  2270.76
2016-12-21 2270.54 2271.23 2265.15 2265.18 2852230000  2265.18
2016-12-22 2262.93 2263.18 2256.08 2260.96 2876320000  2260.96
2016-12-23 2260.25 2263.79 2258.84 2263.79 2020550000  2263.79
2016-12-27 2266.23 2273.82 2266.15 2268.88 1987080000  2268.88
2016-12-28 2270.23 2271.31 2249.11 2249.92 2392360000  2249.92

# 画出SP500的K线图
> barChart(GSPC)

把4个品种的调整后的价格进行合并。


> # 改列名
> names(IBM)<-c("open","high","low","close","volume","adjusted")
> names(GE)<-c("open","high","low","close","volume","adjusted")
> names(YHOO)<-c("open","high","low","close","volume","adjusted")
> names(GSPC)<-c("open","high","low","close","volume","adjusted")

# 数据合并
> dat=merge(IBM$adjusted,GE$adjusted,YHOO$adjusted,GSPC$adjusted)
> names(dat)<-c('IBM','GE','YHOO','SP500')

# 打印前6行
> head(dat)
                IBM       GE  YHOO   SP500
2010-01-04 112.2859 12.27367 17.10 1132.99
2010-01-05 110.9295 12.33722 17.23 1136.52
2010-01-06 110.2089 12.27367 17.17 1137.14
2010-01-07 109.8274 12.90920 16.70 1141.69
2010-01-08 110.9295 13.18724 16.70 1144.98
2010-01-11 109.7680 13.31435 16.74 1146.98

计算每日收益率,合并收益率到dat_ret


> dat_ret=merge(IBM_ret,GE_ret,YHOO_ret,SP500_ret)
> names(dat_ret)<-c('IBM','GE','YHOO','SP500')
> head(dat_ret)
                    IBM           GE         YHOO        SP500
2010-01-04  0.009681385  0.015111695  0.009445041 0.0147147759
2010-01-05 -0.012079963  0.005177994  0.007602339 0.0031156762
2010-01-06 -0.006496033 -0.005151320 -0.003482298 0.0005455205
2010-01-07 -0.003461515  0.051779935 -0.027373267 0.0040012012
2010-01-08  0.010034759  0.021538462  0.000000000 0.0028817272
2010-01-11 -0.010470080  0.009638554  0.002395150 0.0017467554

定义无风险收益率为4%,计算4个资产的平均年化收益率。


# 无风险收益率
> Rf<-.04/12

# 计算平均年化收益率,平均年化标准差,平均年化Sharpe 
> results<-table.AnnualizedReturns(dat_ret,Rf=Rf)
> results
                               IBM      GE    YHOO   SP500
Annualized Return           0.0345  0.1108  0.1257  0.1055
Annualized Std Dev          0.1918  0.2180  0.3043  0.1555
Annualized Sharpe (Rf=84%) -2.8892 -2.3899 -1.6911 -3.3659

统计指标分析,每个资产有1760个样本点,没有NA值。日最小收益率,YHOO最小为-0.0871。日最大收益率,在GE为0.1080。算数平均,几何平均,方差,标准差都是YHOO最大。


# 计算统计指标
> stats
                      IBM        GE      YHOO     SP500
Observations    1760.0000 1760.0000 1760.0000 1760.0000
NAs                0.0000    0.0000    0.0000    0.0000
Minimum           -0.0828   -0.0654   -0.0871   -0.0666
Quartile 1        -0.0060   -0.0065   -0.0098   -0.0039
Median             0.0002    0.0004    0.0005    0.0005
Arithmetic Mean    0.0002    0.0005    0.0007    0.0004
Geometric Mean     0.0001    0.0004    0.0005    0.0004
Quartile 3         0.0067    0.0077    0.0112    0.0053
Maximum            0.0567    0.1080    0.1034    0.0474
SE Mean            0.0003    0.0003    0.0005    0.0002
LCL Mean (0.95)   -0.0004   -0.0001   -0.0002    0.0000
UCL Mean (0.95)    0.0008    0.0012    0.0015    0.0009
Variance           0.0001    0.0002    0.0004    0.0001
Stdev              0.0121    0.0137    0.0192    0.0098
Skewness          -0.5876    0.3084    0.0959   -0.3514
Kurtosis           4.6634    4.7294    2.9990    4.0151

画出IBM股票,日收益和月收益的图,4个资的累积收益率图,并对4个资产做相关性分析。

IBM股票,每日收益图

IBM股票,每月收益图

4个品种的累积收益率图

从上图中可以看出,红线(GE)和蓝线(SP500)的走势基本稳合,说明GE在从2010开始在跟着美国经济持续发展。绿线(YHOO)从2013初到2015年初大幅拉升,领先于SP500很多,说明这段时期YHOO所处的互联网行业,带来了非常大的市场红利;从2015年到2016年,又下跌很大,大起大落,受市场影响非常敏感。黑线(IBM)大部分时间都处于SP500的下方,说明美国经济这几年的高速发展,并没有给IBM带来很大的发展空间。如果从我们的目标来说,”比标普好的投资收益”那么我们只能选择GE或YHOO。

相关性分析

对4个品种进行相关性分析,发现GE和SP500相关系数为0.78,是3只股票中最相关的。而YHOO是与其他3个品种走势最不一样的。

最后,以SP500为市场组合,分别计算出3只股票的alpha和beta。


# 计算alpha
> CAPM.alpha(dat_ret[,1:3],dat_ret[,4],Rf=Rf)
                      IBM           GE         YHOO
Alpha: SP500 -0.000752943 0.0003502332 0.0003944279

# 计算beta
> CAPM.beta(dat_ret[,1:3],dat_ret[,4],Rf=Rf)
                  IBM       GE     YHOO
Beta: SP500 0.8218135 1.098877 1.064844

3只股票中,IBM的alpha是最小的,而且是负的,说明IBM落后于市场,买IBM不如直接SP500更好。GE的Beta是最大的,在上升时期beta越大,获得的市场收益也会越大。YHOO从Alpha和Beta上看,虽然与GE接近,但由于标准差,最大回撤等指标过大,会导致波动太大。

综上分析,我们如果配置部分GE和部分YHOO,就可以获得比标普好的收益,但由于GE和YHOO的beta都高于SP500,所以风险也会高于SP500,需要增加新的股票来分散风险,具体的定量分析,将在以后的文章中再进行介绍了。

5. Beta VS Alpha

最后,补充一些Alpha和Beta的说明。Alpha和Beta的认知最早是一个股市起源的概念,是一个关于投资组合的收益率分解的问题

  • Alpha:一般被认为是投资组合的超额收益,也既管理人的能力;
  • Beta:市场风险,最初主要指股票市场的系统性风险

Alpha是平均实际回报和平均预期回报的差额。

  • α>0,表示一基金或股票的价格可能被低估,建议买入。
  • α<0,表示一基金或股票的价格可能被高估,建议卖空。
  • α=0,表示一基金或股票的价格准确反映其内在价值,未被高估也未被低估。

Beta反映了单个证券与整体市场组合的联动性。

  • β>1,攻击性,市场上升时涨幅大。
  • β<1,防御性,市场下跌时跌幅小。
  • β=1,中立性,与市场波动一致。

从资本资产定价模型开始发展到现今,已经有很长的时间了。金融理论在一直发展,继资本资产定价模型之后又一重要的理论突破是套利定价理论,我将在下一篇文章中进行介绍。

本文中,我详细地介绍了资本资产定价模型的金融理论、推到过程、以及R语言实现,用我自己的理解进行阐述。希望能给走在量化道路上的朋友带来入门的指引和帮助,也希望找到像我一样,通过IT转金融的人,让我一起用IT技术+金融的思维在金融市场抢钱吧。

转载请注明出处:
http://blog.fens.me/finance-capm

打赏作者

均值回归,逆市中的投资机会

用IT技术玩金融系列文章,将介绍如何使用IT技术,处理金融大数据。在互联网混迹多年,已经熟练掌握一些IT技术。单纯地在互联网做开发,总觉得使劲的方式不对。要想靠技术养活自己,就要把技术变现。通过“跨界”可以寻找新的机会,创造技术的壁垒。

金融是离钱最近的市场,也是变现的好渠道!今天就开始踏上“用IT技术玩金融”之旅!

关于作者:

  • 张丹(Conan), 程序员Java,R,PHP,Javascript
  • weibo:@Conan_Z
  • blog: http://blog.fens.me
  • email: bsspirit@gmail.com

转载请注明出处:
http://blog.fens.me/finance-mean-reversion/

meanReversion

前言

在股票市场中有两种典型的投资策略:趋势追踪(Trend Following) 和 均值回归(Mean Reversion)。 趋势追踪策略的特点在大行情的波动段找到有效的交易信号,不仅简单而且有效,我之前写的一篇文章 两条均线打天下 就属于趋势追踪策略。而均值回归策略则是一种反趋势策略,一波大幅上涨后容易出现下跌,而一波大幅下跌后容易出现上涨。其特点在振荡的在震荡的市场中非常有效,捕捉小的机会,本文就将介绍这种策略。

目录

  1. 均值回归原理
  2. 均值回归模型和实现
  3. 量化选股

1. 均值回归原理

在金融学中,均值回归是价格偏离均衡价格水平一定程度后向均衡价格靠拢的规律。本质上,均值回归就是哲学思想中所说的物极必反,可以简单地概括为“涨多必跌,跌多必涨”的规律。

均值回归是指股票价格无论高于或低于均值(均衡价格水平)都会以很高的概率向均值回归。根据这个理论,股票价格总是围绕其均值上下波动。一种上涨或者下跌的趋势不管其延续的时间多长都不能永远持续下去,最终均值回归的规律一定会出现:涨得太多了,就会向均值移动下跌;跌得太多了,就会向均值移动上升。如果我们认为事物总要回归常态,并且基于这样的预期来做任何决策的时候,我们就是在应用均值回归的理论。

下面以平安银行(000001)股票日K线图为例,可以非常直观的了解均值回归这种现象, 截取2005年到2015年7月的股票数据,股价为向前复权的价格。

01

上图中有3条曲线,黑色线是平安银行向前复权后的每日股价,红色线为20日均线,蓝色线为60日均线。关于均线的介绍,请参考文章 两条均线打天下。图中还有一条红色的水平线虚线,是这10年的股价平均值等于7.14元。这10年间,平安银行的股价经历了几波上涨和下跌,多次穿越7.14平均值。那么这个现象就是我们要讨论的均值回归。

1.1 均值回归的3个特性

均值回归是价值投资理论成立的一个核心理论,具有3个特性:必然性、不对称性、政府调控。

必然性,股票价格不能总是上涨或下跌,一种趋势不管其持续的时间多长都不能永远持续下去。在一个趋势内,股票价格呈持续上升或下降,我们称之为均值回避(Mean Aversion)。当出现相反趋势时就呈均值回归(Mean Reversion),但回归的周期有随机性是我们不能预测。不同的股票市场,回归的周期会不一样的,就算是相同的市场,回归的周期也是不一样的。

我们换支股票,以苏宁云商(002024)股票日K线图为例, 同样截取2005年到2015年7月的向前复权的股价数据,如下图所示。我们看到苏宁云商在2006年到2007年有一波大涨随后下跌;从2009到2010年时,第二波大涨;2013年下半年迎来第三波大涨;2014年下半年到2015年第四波大涨。从图形上可以直观看到,2015年这波涨的最急,波动率也是最大的;从现象中,我们可以判断一种趋势不管其持续的时间多长都不能永远持续下去。

02

不对称性,股价波动的幅度与速度是不一样的,回归时的幅度与速度具有随机性。对称的均值回归才是不正常的、偶然的,这一点也也可以从股票中所验证。

我们合并平安银行(000001)和苏宁云商(002024)股票日K线图为例,所下图所示。两支股票在2007年中,都赶上了大的上涨行情,曲线基本吻合。到2008年2支股票都遇到了大跌,但波动率和速度都是不一样的,随后在2010年到2012年出现了完成不一样的走势,无规律可寻,体现了均值回归时的随机性和不对称性。

03

政府行为,股票收益率不会偏离价值均值时间太久,市场的内在力量会促使其向内在价值回归。市场在没有政府政策的作用下,股票价格会在市场机制下自然地向均值回归。但这并不否定政府行为对促进市场有效性的作用,因为市场偏离内在价值后并不等于立即就会向内在价值回归,很可能会出现持续地均值回避。政府行为会起到抑制市场调节市场的作用,是必不可少的因素之一,市场失灵也是政府参与调控的直接的结果。

对于政府政策行为,比如升准、降准、升息、降息,在股市中都会有比如明显的体现。房地产股、银行股,都会受到国家宏观调控的直接的影响。下如所示,在图中增加万科A(0000002)的股票,图中3条线分别是平安银行,万科A,苏宁云商3支股票。我们发现地产和银行的股价走势是比较相近的,而电商的走势是不太一样的。

另外,增加2种颜色的辅助线,红色为升息的时间点和利率变动值,黄色为降息的时间点和利率变动值。当2007年股市超涨的时候,国家宏观调控通过升息鼓励存款,抑制高股价;当股票超跌的时候,通过降息推动投资和消费。2015年金融改革,政府一直都在降息拉动股市。从图中,我们看到万科A和平安银行对于升息和降息的调控是比较明显的,对于苏宁云商就不是特别的明显了。

04

通过对市场的回顾,我们基本验证了均值回归的理论是和市场的行为是一致的。那么,接下来我们应该如何应用这个理论来找到投资的切入点呢?

1.2 计算原理和公式

从价值投资的角度,我们发现股价会在平均值上下波动,但如果考虑到资金的时间成本,把钱都压在股市中,等待几年的大行情,也是很不划算的。那么我们就需要对价值均值进行重新定义,以20日均值来代替长期均值,找到短周期的一种投资方法。

计算原理:取日K线,以N日均线做为均值回归的短期均衡价格水平(均值),计算股价到均值的差值,求出差值的N日的平均标准差,从而判断差值的对于均值的偏离,当偏离超过2倍标准差时,我们就认为股价超涨或超跌,股价会遵循均值回归的理论,向均值不停地进行修复。

计算公式:


N日平均值     =  [T日股价 + (T-1)日股价 + ... + (T-(N-1))日股价]/N
差值          =  N日平均值 - N日股价
N日差值均值   =  [T日差值 + (T-1)日差值 + ... + (T-(N-1))日差值]/N
N日差值标准差 =  sqrt([(T日差值 - T日差值均值)^2 + ... + ((T-(N-1))日差值 - (T-(N-1))日差值均值)^2 ]/N)

如果N为20日,则


20日平均值     =  [T日股价 + (T-1)日股价 + ... + (T-19)日股价]/20

计算偏离点


T日差值 > T日差值标准差 * 2

我们以偏离点作为买入信号点,以均线和股价的下一个交点做为卖出信号点。这样我们就把均值回归的投资理论,变成了一个数学模型。

2. 均值回归模型和实现

接下来,我们利用R语言对股票数据的进行操作,来实现一个均值回归模型的实例,从而验证我的们投资理论,是否能发现赚钱的机会。

2.1 数据准备

R语言本身提供了丰富的金融函数工具包,时间序列包zoo和xts,指标计算包TTR,数据处理包plyr,可视包ggplot2等,我们会一起使用这些工具包来完成建模、计算和可视化的工作。关于zoo包和xts包的详细使用可以参考文章,R语言时间序列基础库zoo可扩展的时间序列xts

我本次用到的数据是从 况客 直接导出的,况客 会提供各种类型的金融数据API,让开发者可以免费下载。当然,你也可以用quantmod包从Yahoo财经下载。

本文用到的数据,包括A股日K线(向前复权)数据,从2014年7月到2015年日7月,以CSV格式保存到本地文件stock.csv。

数据格式如下:


000001.SZ,2014-07-02,8.14,8.18,8.10,8.17,28604171
000002.SZ,2014-07-02,8.09,8.13,8.05,8.12,40633122
000004.SZ,2014-07-02,13.9,13.99,13.82,13.95,1081139
000005.SZ,2014-07-02,2.27,2.29,2.26,2.28,4157537
000006.SZ,2014-07-02,4.57,4.57,4.50,4.55,5137384
000010.SZ,2014-07-02,6.6,6.82,6.5,6.73,9909143

一共7列:

  • 第1列,股票代码,code,000001.SZ
  • 第2列,交易日期,date,2014-07-02
  • 第3列,开盘价,Open,8.14
  • 第4列,最高价,High,8.18
  • 第5列,最低价,Low,8.10
  • 第6列,收盘价,Close,8.17
  • 第7列,交易量,Volume,28604171

通过R语言加载股票数据,由于数据所有股票都是混合在一起的,而进行计算时又需要按每支票股计算,所以在数据加载时我就进行了转换,按股票代码进行分组,生成R语言的list对象,同时把每支股票的data.frame类型对象转成XTS时间序列类型对象,方便后续的数据处理。


#加载工具包
> library(plyr)
> library(xts)
> library(TTR)
> library(ggplot2)
> library(scales)

# 读取CSV数据文件
> read<-function(file){ 
+   df<-read.table(file=file,header=FALSE,sep = ",", na.strings = "NULL") # 读文件
+   names(df)<-c("code","date","Open","High","Low","Close","Volume")      # 设置列名
+   dl<-split(df[-1],df$code)                                             # 按ccode分组
+   
+   lapply(dl,function(row){                                              # 换成xts类型数据
+     xts(row[-1],order.by = as.Date(row$date))
+   })
+ }

# 加载数据
> data<-read("stock.csv")

# 查看数据类型
> class(data)
[1] "list"

# 查看数据的索引值
> head(names(data))
[1] "000001.SZ" "000002.SZ" "000004.SZ" "000005.SZ" "000006.SZ" "000007.SZ"

# 查看包括的股票数量
> length(data)
[1] 2782

# 查看股票000001.SZ
> head(data[['000001.SZ']])
               Open     High      Low    Close   Volume
2014-07-02 8.146949 8.180000 8.105636 8.171737 28604171
2014-07-03 8.171737 8.254364 8.122162 8.229576 44690486
2014-07-04 8.237838 8.270889 8.146949 8.188263 34231126
2014-07-07 8.188263 8.204788 8.097374 8.146949 34306164
2014-07-08 8.130424 8.204788 8.072586 8.204788 34608702
2014-07-09 8.196525 8.196525 7.915596 7.973434 58789114

把数据准备好了,我们就可以来建立模型了。

2.2 均值回归模型
为了能拉近我们对市场的了解,我们取从2015年1月1日开始的数据,来创建均值回归模型。以平安银行(000001)的为例,画出平安银行的2015年以来的日K线和均线。


# 获得时间范围
> dateArea<-function(sDate=Sys.Date()-365,eDate= Sys.Date(),before=0){  #开始日期,结束日期,提单开始时
+     if(class(sDate)=='character') sDate=as.Date(sDate)
+     if(class(eDate)=='character') eDate=as.Date(eDate)  
+     return(paste(sDate-before,eDate,sep="/"))
+ }
 
# 计算移动平均线
> ma<-function(cdata,mas=c(5,20,60)){
+     if(nrow(cdata)<=max(mas)) return(NULL)
+     ldata<-cdata
+     for(m in mas){
+         ldata<-merge(ldata,SMA(cdata,m))
+     }
+     names(ldata)<-c('Value',paste('ma',mas,sep=''))
+     return(ldata)
+ }

# 日K线和均线
> title<-'000001.SZ'
> SZ000011<-data[[title]]                             # 获得股票数据
> sDate<-as.Date("2015-01-01")                        # 开始日期
> eDate<-as.Date("2015-07-10")                        # 结束日期
> cdata<-SZ000011[dateArea(sDate,eDate,360)]$Close    # 获得收盘价
> ldata<-ma(cdata,c(5,20,60))                         # 选择移动平均指标

# 打印移动平均指标
> tail(ldata)
           Value    ma5    ma20     ma60
2015-07-03 13.07 13.768 15.2545 15.84355
2015-07-06 13.88 13.832 15.1335 15.82700
2015-07-07 14.65 13.854 15.0015 15.79850
2015-07-08 13.19 13.708 14.8120 15.74267
2015-07-09 14.26 13.810 14.6910 15.70867
2015-07-10 14.86 14.168 14.6100 15.67883

我们设置3条移动平均线,分别是5日平均线,20日平均线,60日平均线,当然也可以按照自己的个性要求设置符合自己的周期。画出日K线和均线图。


> drawLine<-function(ldata,titie="Stock_MA",sDate=min(index(ldata)),eDate=max(index(ldata)),breaks="1 year",avg=FALSE,out=FALSE){
+     if(sDate<min(index(ldata))) sDate=min(index(ldata))
+     if(eDate>max(index(ldata))) eDate=max(index(ldata))  
+     ldata<-na.omit(ldata)
+     
+     g<-ggplot(aes(x=Index, y=Value),data=fortify(ldata[,1],melt=TRUE))
+     g<-g+geom_line()
+     g<-g+geom_line(aes(colour=Series),data=fortify(ldata[,-1],melt=TRUE))
+ 
+     if(avg){
+         meanVal<<-round(mean(ldata[dateArea(sDate,eDate)]$Value),2) # 均值
+         g<-g+geom_hline(aes(yintercept=meanVal),color="red",alpha=0.8,size=1,linetype="dashed")
+         g<-g+geom_text(aes(x=sDate, y=meanVal,label=meanVal),color="red",vjust=-0.4)
+     }
+     g<-g+scale_x_date(labels=date_format("%Y-%m"),breaks=date_breaks(breaks),limits = c(sDate,eDate))
+     g<-g+ylim(min(ldata$Value), max(ldata$Value))
+     g<-g+xlab("") + ylab("Price")+ggtitle(title)
+     g
+ }

> drawLine(ldata,title,sDate,eDate,'1 month',TRUE)    # 画图

05

如图所示,60日的移动平均线是最平滑的,5日的移动平均线是波动最大的。5日平均线和股价的交叉,明显多于60日平均线和股价的交叉。那么可以说在相同的时间周期内,短周期的移动平均线,比长周期的移动平均线更具有均值回归的特点。

我们分别计算不同周期的,股价与移动平均线的差值的平均标准差。


> getMaSd<-function(ldata,mas=20,sDate,eDate){}) # ...代码省略

# 5日平均线的差值、平均标准差
> ldata5<-getMaSd(ldata,5,sDate,eDate)
> head(ldata5)
              Value      ma5        dif        sd  rate
2015-01-05 13.23673 12.78724 -0.4494869 0.1613198 -2.79
2015-01-06 13.03842 12.89961 -0.1388121 0.1909328 -0.73
2015-01-07 12.79055 12.99215  0.2016081 0.3169068  0.64
2015-01-08 12.36089 12.90292  0.5420283 0.4472248  1.21
2015-01-09 12.46004 12.77733  0.3172848 0.3910700  0.81
2015-01-12 12.20390 12.57076  0.3668606 0.2533165  1.45


# 20日平均线的差值、平均标准差
> ldata20<-getMaSd(ldata,20,sDate,eDate)
> head(ldata20)
              Value     ma20         dif        sd  rate
2015-01-05 13.23673 12.18613 -1.05059293 0.6556366 -1.60
2015-01-06 13.03842 12.23778 -0.80064848 0.6021093 -1.33
2015-01-07 12.79055 12.24810 -0.54244141 0.4754686 -1.14
2015-01-08 12.36089 12.29975 -0.06114343 0.5130410 -0.12
2015-01-09 12.46004 12.33651 -0.12352626 0.5150453 -0.24
2015-01-12 12.20390 12.37163  0.16773131 0.5531618  0.30


# 60日平均线的差值、平均标准差
> ldata60<-getMaSd(ldata,60,sDate,eDate)
> head(ldata60)
              Value     ma60       dif       sd  rate
2015-01-05 13.23673 10.06939 -3.167340 1.264792 -2.50
2015-01-06 13.03842 10.14678 -2.891644 1.271689 -2.27
2015-01-07 12.79055 10.22087 -2.569677 1.269302 -2.02
2015-01-08 12.36089 10.28752 -2.073368 1.258813 -1.65
2015-01-09 12.46004 10.35527 -2.104766 1.247967 -1.69
2015-01-12 12.20390 10.41821 -1.785691 1.233989 -1.45

5日的平均线的差值和平均标准差是最小的,而60日的平均线的差值和平均标准差是最大的。如果我们以5日移动平均线做为均值时,会频繁进行交易,但每次收益都很小,可能都不够手续费的成本;另一方面,如果我们以60日移动平均线做为均值时,交易次数会较少,但可能会出现股票成形趋势性上涨或下跌,长时间不能回归的情况,可能会造成现金头寸的紧张。综合上面的2种情况,我们可以选择20日均线作为均值的标的。

根据模型的计算公式,当差值超过2倍的平均标准差时,我们认为股价出现了偏离,以偏离点做为模型的买入信号,当均线和股价再次相交时做为卖出信号。

上一步,我们已经计算出了偏离值,并保存在rate列中。下面我们要找到大于2倍标准化差的点,并画图。


# 差值和平均标准差,大于2倍平均标准差的点
> buyPoint<-function(ldata,x=2,dir=2){})     # ...代码省略

# 画交易信号点
> drawPoint<-function(ldata,pdata,titie,sDate,eDate,breaks="1 year"){
+     ldata<-na.omit(ldata)
+     g<-ggplot(aes(x=Index, y=Value),data=fortify(ldata[,1],melt=TRUE))
+     g<-g+geom_line()
+     g<-g+geom_line(aes(colour=Series),data=fortify(ldata[,-1],melt=TRUE))
+     
+     if(is.data.frame(pdata)){
+         g<-g+geom_point(aes(x=Index,y=Value,colour=op),data=pdata,size=4)
+     }else{
+         g<-g+geom_point(aes(x=Index,y=Value,colour=Series),data=na.omit(fortify(pdata,melt=TRUE)),size=4)  
+     }
+     g<-g+scale_x_date(labels=date_format("%Y-%m"),breaks=date_breaks(breaks),limits = c(sDate,eDate))
+     g<-g+xlab("") + ylab("Price")+ggtitle(title)
+     g
+ }
 
> buydata<-buyPoint(ldata20,2,2)                                       # 多空信号点
> drawPoint(ldata20[,c(1,2)],buydata$Value,title,sDate,eDate,'1 month')  # 画图

06

图中蓝色的点就是买入的信号点,由于股票我们只能进行单向交易,即低买高卖,并不能直接做空,所以我们要过滤股价高于移动平均线的点,只留下股价低于移动平均线的点,就是我们的买入信号点。

画出买入信号点,只保留股价低于移动平均线的点。


> buydata<-buyPoint(ldata20,2,1)        # 做多信号点
> drawPoint(ldata20[,c(1,2)],buydata$Value,title,sDate,eDate,'1 month') # 画图

07

计算卖出的信号点,当买入后,下一个股价与移动平均线的交点就是卖出的信号点,我们看一下是否可以赚到钱?!


# 计算卖出的信号点
> sellPoint<-function(ldata,buydata){})     # ...代码省略
> selldata<-sellPoint(ldata20,buydata)

# 买出信号
> selldata
           Value  ma20   dif        sd  rate
2015-07-10 14.86 14.61 -0.25 0.7384824 -0.34

我们把买入信号和卖出信号,合并到一张图上显示,如图所示。


> bsdata<-merge(buydata$Value,selldata$Value)
> names(bsdata)<-c("buy","sell")
> drawPoint(ldata20[,c(1,2)],bsdata,title,sDate,eDate,'1 month') #画图

08

从图上看,我们在绿色点位置进行买入,而在蓝色点位置进行卖出,确实是赚钱的。那么究竟赚了多少钱呢?我们还需要精确的计算出来。


# 合并交易信号
> signal<-function(buy, sell){})    # ...代码省略

# 交易信号数据
> sdata<-signal(buydata,selldata)                                   
> sdata
           Value    ma20     dif        sd  rate op
2015-06-19 14.63 16.0965  1.4665 0.6620157  2.22  B
2015-06-26 13.77 15.7720  2.0020 0.8271793  2.42  B
2015-06-29 13.56 15.6840  2.1240 0.9271735  2.29  B
2015-07-03 13.07 15.2545  2.1845 1.0434926  2.09  B
2015-07-10 14.86 14.6100 -0.2500 0.7384824 -0.34  S

利用交易信号数据,进行模拟交易。我们设定交易参数和规则:

  • 以10万元人民币为本金
  • 买入信号出现时,以收盘价买入,每次买入价值1万元的股票。如果连续出现买入信号,则一直买入。若现金不足1万元时,则跳过买入信号。
  • 卖出信号出现时,以收盘价卖出,一次性平仓信号对应的股票。
  • 手续费为0元

# 模拟交易
> trade<-function(sdata,capital=100000,fixMoney=10000){})    # ...代码省略

# 交易结果
> result<-trade(sdata,100000,10000)  

来看一下,每笔交易的明细。


> result$ticks
           Value    ma20     dif        sd  rate op      cash amount     asset     diff
2015-06-19 14.63 16.0965  1.4665 0.6620157  2.22  B  90007.71    683 100000.00     0.00
2015-06-26 13.77 15.7720  2.0020 0.8271793  2.42  B  80010.69   1409  99412.62  -587.38
2015-06-29 13.56 15.6840  2.1240 0.9271735  2.29  B  70016.97   2146  99116.73  -295.89
2015-07-03 13.07 15.2545  2.1845 1.0434926  2.09  B  60018.42   2911  98065.19 -1051.54
2015-07-10 14.86 14.6100 -0.2500 0.7384824 -0.34  S 103275.88      0 103275.88  5210.69

一共发生了5笔交易,其中4笔买入,1笔卖出。最后,资金剩余103275.88元,赚了3275.88元,收益率3.275%。

在卖出时,赚钱的交易有1笔。


> result$rise
           Value  ma20   dif        sd  rate op     cash amount    asset    diff
2015-07-10 14.86 14.61 -0.25 0.7384824 -0.34  S 103275.9      0 103275.9 5210.69

在卖出时,赔钱的交易,没有发生。


> result$fall
 [1] Value  ma20   dif    sd     rate   op     cash   amount asset  diff  
<0 行> (或0-长度的row.names)

接下来,我们再对比一下,资产净值和股价。


# 资产净值曲线
> drawAsset<-function(ldata,adata,sDate=FALSE,capital=100000){
+     if(!sDate) sDate<-index(ldata)[1]
+     adata<-rbind(adata,as.xts(capital,as.Date(sDate)))
+     
+     g<-ggplot(aes(x=Index, y=Value),data=fortify(ldata[,1],melt=TRUE))
+     g<-g+geom_line()
+     g<-g+geom_line(aes(x=as.Date(Index), y=Value,colour=Series),data=fortify(adata,melt=TRUE))
+     g<-g+facet_grid(Series ~ .,scales = "free_y")
+     g<-g+scale_y_continuous(labels=dollar_format(prefix = "¥"))
+     g<-g+scale_x_date(labels=date_format("%Y-%m"),breaks=date_breaks("2 months"),limits = c(sDate,eDate))
+     g<-g+xlab("") + ylab("Price")+ggtitle(title)
+     g
+ }

> drawAsset(ldata20,as.xts(result$ticks['asset']))  # 资产净值曲线

09

刚才我们是对一支股票进行了测试,发现是有机会的,那么我再换另外一支股票,看一下是否用同样的效果呢?我们把刚才数据操作的过程,封装到统一的quick函数,就可以快速验证均值回归在其他股票的表现情况了。


> quick<-function(title,sDate,eDate){}  # ...代码省略

我们用乐视网(300104)试一下,看看有没有赚钱的机会!!


> title<-"300104.SZ"
> sDate<-as.Date("2015-01-01") #开始日期
> eDate<-as.Date("2015-07-10") #结束日期

> quick(title,sDate,eDate)
$ticks
           Value    ma20     dif       sd  rate op      cash amount     asset     diff
2015-06-19 55.04 69.9095 14.8695 5.347756  2.78  B  90037.76    181 100000.00     0.00
2015-06-23 54.30 68.8075 14.5075 5.477894  2.65  B  80046.56    365  99866.06  -133.94
2015-06-24 56.21 67.8735 11.6635 5.404922  2.16  B  70097.39    542 100563.21   697.15
2015-06-25 51.80 66.8775 15.0775 5.770806  2.61  B  60099.99    735  98172.99 -2390.22
2015-06-26 46.79 65.9830 19.1930 6.580622  2.92  B  50133.72    948  94490.64 -3682.35
2015-06-29 47.05 64.9445 17.8945 7.096230  2.52  B  40159.12   1160  94737.12   246.48
2015-07-07 47.86 58.8150 10.9550 5.401247  2.03  B  30204.24   1368  95676.72   939.60
2015-07-10 57.92 57.3520 -0.5680 5.625309 -0.10  S 109438.80      0 109438.80 13762.08

$rise
           Value   ma20    dif       sd rate op     cash amount    asset     diff
2015-07-10 57.92 57.352 -0.568 5.625309 -0.1  S 109438.8      0 109438.8 13762.08

$fall
 [1] Value  ma20   dif    sd     rate   op     cash   amount asset  diff  
<0 行> (或0-长度的row.names)

从数据结果看,我们又赚到了。一共发生了8笔交易,其中7笔买入,1笔卖出。最后,资金剩余109438.80元,赚了9438.80元,收益率9.43%。

画出交易信号图


> title<-"300104.SZ"
> sDate<-as.Date("2015-01-01") #开始日期
> eDate<-as.Date("2015-07-10") #结束日期

> stock<-data[[title]]
> cdata<-stock[dateArea(sDate,eDate,360)]$Close
> ldata<-ma(cdata,c(20))
> ldata<-getMaSd(ldata,20,sDate,eDate)
> buydata<-buyPoint(ldata,2,1)  
> selldata<-sellPoint(ldata,buydata)
> bsdata<-merge(buydata$Value,selldata$Value)
> drawPoint(ldata[,c(1,2)],bsdata,title,sDate,eDate,'1 month') #画图

10

在恐慌的6月份,当别人都被套牢30%以上的情况下,我们还朿9%正收益,那么应该是多么舒心的一件事情啊!!

3. 量化选股

上文中,我们用2支股票进行了测试,发现均值回归模型是适合于股票交易的。如果我们利用模型对全市场的股票进行扫描,应用会产生更多的交易信号,找到更多的投资机会,这样我们就能如何能获得更大的收益。

那么,接下来我们就根据均值回归的理论进行量化选股。

根据我们之前的经验,当股价与平均标准差的偏离越大,有可能带来的收益就越大。那么通过量化的手段,在整个的市场2700多支股票中,把每天偏离最大股票的找出来进行交易,就可以有效地分配我们的资金,进行更有效的投资。我们要试一下,市场是否是和我们的思路是一致的。

对全市场股票进行扫描,首先计算差值、平均值和平均标准差。


> sDate<-as.Date("2015-01-01")                # 开始日期
> eDate<-as.Date("2015-07-10")                # 结束日期

# 计算差值、平均值和平均标准差
> data0<-lapply(data,function(stock){})       # 代码省略

# 去掉空数据
> data0<-data0[!sapply(data0, is.null)]      

# 全市场股票
> length(data)
[1] 2782

# 有效的股票
> length(data0)
[1] 2697

# 查看第1支股票
> head(data0[[1]])
              Value     ma20         dif        sd  rate
2015-01-05 13.23673 12.18613 -1.05059293 0.6556366 -1.60
2015-01-06 13.03842 12.23778 -0.80064848 0.6021093 -1.33
2015-01-07 12.79055 12.24810 -0.54244141 0.4754686 -1.14
2015-01-08 12.36089 12.29975 -0.06114343 0.5130410 -0.12
2015-01-09 12.46004 12.33651 -0.12352626 0.5150453 -0.24
2015-01-12 12.20390 12.37163  0.16773131 0.5531618  0.30

第一次扫描后,有2697支股票是符合条件的,有85支股票由于数据样本不足被排除。

接下来,继续对2697支股票进行筛选,找到符合要求的买入信号点。


# 计算买入信号
> buys<-lapply(data0,function(stock){})  # ...代码省略 

# 去掉空数据
> buys<-buys[!sapply(buys, is.null)] 

# 查看有买入信号的股票
> length(buys)
[1] 1819

# 查看买入信号
> head(buys)
$`000001.SZ`
           Value    ma20    dif        sd rate
2015-06-19 14.63 16.0965 1.4665 0.6620157 2.22
2015-06-26 13.77 15.7720 2.0020 0.8271793 2.42
2015-06-29 13.56 15.6840 2.1240 0.9271735 2.29
2015-07-03 13.07 15.2545 2.1845 1.0434926 2.09

$`000002.SZ`
           Value   ma20   dif        sd rate
2015-03-05 11.90 12.568 0.668 0.2644101 2.53
2015-03-06 11.94 12.509 0.569 0.2674732 2.13

$`000004.SZ`
           Value    ma20     dif        sd rate
2015-01-05 15.69 17.7210  2.0310 0.7395717 2.75
2015-07-06 26.03 39.1540 13.1240 6.3898795 2.05
2015-07-07 23.43 38.2025 14.7725 6.9421723 2.13
2015-07-08 22.22 37.2635 15.0435 7.4287088 2.03

$`000005.SZ`
           Value    ma20    dif       sd rate
2015-07-06  6.02 10.9600 4.9400 2.381665 2.07
2015-07-07  5.42 10.5655 5.1455 2.333008 2.21

$`000006.SZ`
              Value     ma20       dif      sd rate
2015-01-19 5.829283 6.519462 0.6901792 0.26929 2.56

$`000007.SZ`
           Value    ma20    dif        sd rate
2015-02-06 12.47 14.4200 1.9500 0.6182860 3.15
2015-02-09 12.52 14.3270 1.8070 0.7440473 2.43
2015-02-10 12.10 14.1845 2.0845 0.8484250 2.46

通过计算发现,有1819支股票,在这半年中产生过买入信号。每支股票产生的买入信号的时间和频率都是不同,这样我们就可以把钱分散投资到不同的股票上,同时分散风险。如果交易信号同一天出现在多支的股票上,而我们资金有限,又想让收益最大化,那么我们可以选择偏离值最大的股票进行交易。

接下来,我们用程序找到每日偏离最大的股票。


# 合并数据,从list转型到data.frame
buydf<-ldply(buys,function(e){})    # ...代码省略

# 选出同一日rate最大的股票,做为买入信号
buydatas<-ddply(buydf, .(date), function(row){}) # ...代码省略

# 查看买入信号
> nrow(buydatas)
[1] 81

# 查看买入信号细节
> head(buydatas)
         .id       date      Value       ma20        dif         sd rate
1  002551.SZ 2015-01-05  16.573846  19.565446  2.9916000 0.74591596 4.01
2  002450.SZ 2015-01-06  18.548809  19.766636  1.2178275 0.34008453 3.58
3  300143.SZ 2015-01-07  11.480000  12.603000  1.1230000 0.32028018 3.51
4  300335.SZ 2015-01-08  12.113677  13.139601  1.0259238 0.21760484 4.71
5  300335.SZ 2015-01-09  12.243288  13.043888  0.8005994 0.22940845 3.49
6  300335.SZ 2015-01-12  11.994036  12.941694  0.9476584 0.23168313 4.09

最后,我们选出81个买入信号点,基本上每个交易日都是买入信号。有了买入信号,继续找到卖出信号。


# 卖出信号
> selldatas<-data.frame()     # ...代码省略

# 卖出信号去重
> selldatas<-unique(selldatas)  
> nrow(selldatas)
[1] 33

# 查看买出信号
> head(selldatas)
                Value      ma20         dif        sd  rate       .id       date op
2015-01-12  19.232308 18.848908 -0.38340000 0.9051374 -0.42 002551.SZ 2015-01-12  S
2015-01-08  19.814257 19.729006 -0.08525126 0.3782955 -0.23 002450.SZ 2015-01-08  S
2015-01-28  11.210000 11.019500 -0.19050000 0.7781848 -0.24 300143.SZ 2015-01-28  S
2015-01-21  13.190448 12.899321 -0.29112706 0.3871871 -0.75 300335.SZ 2015-01-21  S
2015-01-213  7.140000  6.989500 -0.15050000 0.2007652 -0.75 002505.SZ 2015-01-21  S
2015-01-22   5.561561  5.490668 -0.07089242 0.2127939 -0.33 600077.SH 2015-01-22  S

通过计算,一共有33个买出信号点。最后,合并买入信号和卖出信号,并计算收益。


> buydatas$op<-'B'                              # 买入标志
> selldatas$op<-'S'                             # 卖出标志
> sdatas<-rbind(buydatas,selldatas)             # 合并数据
> row.names(sdatas)<-1:nrow(sdatas)             # 重设行号
> sdatas<-sdatas[order(sdatas$.id),]            # 按股票代码排序

# 查看合并的信号
> head(sdatas)
          .id       date Value     ma20       dif         sd  rate op
36  000002.SZ 2015-03-05 11.90 12.56800  0.668000 0.26441011  2.53  B
100 000002.SZ 2015-03-16 12.49 12.38050 -0.109500 0.23702768 -0.46  S
58  000553.SZ 2015-05-06 14.35 15.50882  1.158824 0.38429912  3.02  B
110 000553.SZ 2015-05-21 16.57 15.18903 -1.380972 0.55647152 -2.48  S
26  000725.SZ 2015-02-09  2.80  3.11400  0.314000 0.07934585  3.96  B
94  000725.SZ 2015-02-16  3.09  3.06500 -0.025000 0.08182388 -0.31  S

最后,按照股票进行分组,分别计算个股的收益。


# 计算个股的收益
> slist<-split(sdatas[-1],sdatas$.id)      # 按股票代码分组
> results<-lapply(slist,trade)

# 查看信号的股票
> names(results)
 [1] "000002.SZ" "000553.SZ" "000725.SZ" "000786.SZ" "000826.SZ" "002240.SZ" "002450.SZ"
 [8] "002496.SZ" "002505.SZ" "002544.SZ" "002551.SZ" "002646.SZ" "002652.SZ" "300143.SZ"
[15] "300335.SZ" "300359.SZ" "300380.SZ" "300397.SZ" "300439.SZ" "300440.SZ" "300444.SZ"
[22] "600030.SH" "600038.SH" "600077.SH" "600168.SH" "600199.SH" "600213.SH" "600375.SH"
[29] "600490.SH" "600536.SH" "600656.SH" "600733.SH" "600890.SH" "601179.SH" "601186.SH"
[36] "601628.SH" "601633.SH" "601939.SH" "603019.SH"

我们查看万科A(000002)的股票。


> results[['000002.SZ']]$ticks
          date Value    ma20     dif        sd  rate op     cash amount    asset  diff
36  2015-03-05 11.90 12.5680  0.6680 0.2644101  2.53  B  90004.0    840 100000.0   0.0
100 2015-03-16 12.49 12.3805 -0.1095 0.2370277 -0.46  S 100495.6      0 100495.6 495.6

通过优化的规则设计,一共有2笔交易,赚了495元。如要我们没有进行算法优化,一直交易万科A,那么会发生3笔交易,我们可以赚955.95元。


> quick('000002.SZ',sDate,eDate)$ticks
           Value    ma20     dif        sd  rate op      cash amount    asset   diff
2015-03-05 11.90 12.5680  0.6680 0.2644101  2.53  B  90004.00    840 100000.0   0.00
2015-03-06 11.94 12.5090  0.5690 0.2674732  2.13  B  80010.22   1677 100033.6  33.60
2015-03-16 12.49 12.3805 -0.1095 0.2370277 -0.46  S 100955.95      0 100955.9 922.35

本文到此就要结束了!但其实还有很多的事情要做,比如对模型参数的优化,用10日均线代替20日均线,用3倍标准差偏移代替2倍标准差偏移,对样本进行正态分布的检验,结合其他趋势类模型共同产生信号等,这些就不是一篇文章可以解决的事情了。大家可以况客金融平台的网站上,发现更多不一样的策略。

本文从均值回归的理论的介绍开始,到市场特征检验,再到数学公式,R语言建模,历史数据回测,最后找到投资机会,是一套完整的从理论到实践的学习方法。虽然困难重重,但做为有理想的极客,我们是有能力来克服这些困难的。

本文同时用到了计算机、金融、数学、统计等多学科知识的结合,我认为这是技术复合人才未来的发展方向。如果说过去10年是房地产的黄金10年,那么未来的10年将是金融的黄金10年。当我们IT人掌握了足够的金融知识,一定会有能力去金融市场抢钱的。

抓住机会!!程序员,加油!

######################################################
看文字不过瘾,作者视频讲解,请访问网站:http://onbook.me/video
######################################################

转载请注明出处:
http://blog.fens.me/finance-mean-reversion/

打赏作者

R语言中的遗传算法

算法为王系列文章,涵盖了计算机算法,数据挖掘(机器学习)算法,统计算法,金融算法等的多种跨学科算法组合。在大数据时代的背景下,算法已经成为了金字塔顶的明星。一个好的算法可以创造一个伟大帝国,就像Google。

算法为王的时代正式到来….

关于作者:

  • 张丹(Conan), 程序员Java,R,PHP,Javascript
  • weibo:@Conan_Z
  • blog: http://blog.fens.me
  • email: bsspirit@gmail.com

转载请注明出处:
http://blog.fens.me/algorithm-ga-r/

ga-r

前言

人类总是在生活中摸索规律,把规律总结为经验,再把经验传给后人,让后人发现更多的规规律,每一次知识的传递都是一次进化的过程,最终会形成了人类的智慧。自然界规律,让人类适者生存地活了下来,聪明的科学家又把生物进化的规律,总结成遗传算法,扩展到了更广的领域中。

本文将带你走进遗传算法的世界。

目录

  1. 遗传算法介绍
  2. 遗传算法原理
  3. 遗传算法R语言实现

1. 遗传算法介绍

遗传算法是一种解决最优化的搜索算法,是进化算法的一种。进化算法最初借鉴了达尔文的进化论和孟德尔的遗传学说,从生物进化的一些现象发展起来,这些现象包括遗传、基因突变、自然选择和杂交等。遗传算法通过模仿自然界生物进化机制,发展出了随机全局搜索和优化的方法。遗传算法其本质是一种高效、并行、全局搜索的方法,它能在搜索过程中自动获取和积累有关搜索空间的知识,并自适应的控制搜索过程,计算出全局最优解。

遗传算法的操作使用适者生存的原则,在潜在的种群中逐次产生一个近似最优解的方案,在每一代中,根据个体在问题域中的适应度值和从自然遗传学中借鉴来的再造方法进行个体选择,产生一个新的近似解。这个过程会导致种群中个体的进化,得到的新个体比原来个体更能适应环境,就像自然界中的改造一样。

如果从生物进化的角度,我们可以这样理解。在一个种群中,个体数量已经有一定规模,为了进化发展,通过选择和繁殖产生下一代的个体,其中繁殖过程包括交配和突变。根据适者生存的原则,选择过程会根据新个体的适应度进行保留或淘汰,但也不是完全以适应度高低作为导向,如果单纯选择适应度高的个体可能会产生局部最优的种群,而非全局最优,这个种群将不会再进化,称为早熟。之后,通过繁殖过程,让个体两两交配产生下一代新个体,上一代个体中优秀的基因会保留给下一代,而劣制的基因将被个体另一半的基因所代替。最后,通过小概率事件发生基因突变,通过突变产生新的下一代个体,实现种群的变异进化。

经过这一系列的选择、交配和突变的过程,产生的新一代个体将不同于初始的一代,并一代一代向增加整体适应度的方向发展,因为最好的个体总是更多的被选择去产生下一代,而适应度低的个体逐渐被淘汰掉。这样的过程不断的重复:每个个体被评价,计算出适应度,两个个体交配,然后突变,产生第三代。周而复始,直到终止条件满足为止。

遗传算法需要注意的问题:

  • 遗传算法在适应度函数选择不当的情况下有可能收敛于局部最优,而不能达到全局最优。
  • 初始种群的数量很重要,如果初始种群数量过多,算法会占用大量系统资源;如果初始种群数量过少,算法很可能忽略掉最优解。
  • 对于每个解,一般根据实际情况进行编码,这样有利于编写变异函数和适应度函数。
  • 在编码过的遗传算法中,每次变异的编码长度也影响到遗传算法的效率。如果变异代码长度过长,变异的多样性会受到限制;如果变异代码过短,变异的效率会非常低下,选择适当的变异长度是提高效率的关键。
  • 变异率是一个重要的参数。
  • 对于动态数据,用遗传算法求最优解比较困难,因为染色体种群很可能过早地收敛,而对以后变化了的数据不再产生变化。对于这个问题,研究者提出了一些方法增加基因的多样性,从而防止过早的收敛。其中一种是所谓触發式超级变异,就是当染色体群体的质量下降(彼此的区别减少)时增加变异概率;另一种叫随机外来染色体,是偶尔加入一些全新的随机生成的染色体个体,从而增加染色体多样性。
  • 选择过程很重要,但交叉和变异的重要性存在争议。一种观点认为交叉比变异更重要,因为变异仅仅是保证不丢失某些可能的解;而另一种观点则认为交叉过程的作用只不过是在种群中推广变异过程所造成的更新,对于初期的种群来说,交叉几乎等效于一个非常大的变异率,而这么大的变异很可能影响进化过程。
  • 遗传算法很快就能找到良好的解,即使是在很复杂的解空间中。
  • 遗传算法并不一定总是最好的优化策略,优化问题要具体情况具体分析。所以在使用遗传算法的同时,也可以尝试其他算法,互相补充,甚至根本不用遗传算法。
  • 遗传算法不能解决那些“大海捞针”的问题,所谓“大海捞针”问题就是没有一个确切的适应度函数表征个体好坏的问题,使得算法的进化失去导向。
  • 对于任何一个具体的优化问题,调节遗传算法的参数可能会有利于更好的更快的收敛,这些参数包括个体数目、交叉率和变异率。例如太大的变异率会导致丢失最优解,而过小的变异率会导致算法过早的收敛于局部最优点。对于这些参数的选择,现在还没有实用的上下限。
  • 适应度函数对于算法的速度和效果也很重要。

遗传算法的应用领域包括计算机自动设计、生产调度、电路设计、游戏设计、机器人学习、模糊控制、时间表安排,神经网络训练等。然而,我准备把遗传算法到金融领域,比如回测系统的参数寻优方案,我会在以后的文章中,介绍有关金融解决方案。

2. 遗传算法原理

在遗传算法里,优化问题的解是被称为个体,它表示为一个变量序列,叫做染色体或者基因串。染色体一般被表达为简单的字符串或数字串,也有其他表示法,这一过程称为编码。首先要创建种群,算法随机生成一定数量的个体,有时候也可以人工干预这个过程进行,以提高初始种群的质量。在每一代中,每一个个体都被评价,并通过计算适应度函数得到一个适应度数值。种群中的个体被按照适应度排序,适应度高的在前面。

接下来,是产生下一代个体的种群,通过选择过程和繁殖过程完成。

选择过程,是根据新个体的适应度进行的,但同时并不意味着完全的以适应度高低作为导向,因为单纯选择适应度高的个体将可能导致算法快速收敛到局部最优解而非全局最优解,我们称之为早熟。作为折中,遗传算法依据原则:适应度越高,被选择的机会越高,而适应度低的,被选择的机会就低。初始的数据可以通过这样的选择过程组成一个相对优化的群体。

繁殖过程,表示被选择的个体进入交配过程,包括交配(crossover)和突变(mutation),交配对应算法中的交叉操作。一般的遗传算法都有一个交配概率,范围一般是0.6~1,这个交配概率反映两个被选中的个体进行交配的概率。

例如,交配概率为0.8,则80%的“夫妻”个体会生育后代。每两个个体通过交配产生两个新个体,代替原来的“老”个体,而不交配的个体则保持不变。交配过程,父母的染色体相互交換,从而产生两个新的染色体,第一个个体前半段是父亲的染色体,后半段是母亲的,第二个个体则正好相反。不过这里指的半段並不是真正的一半,这个位置叫做交配点,也是随机产生的,可以是染色体的任意位置。

突变过程,表示通过突变产生新的下一代个体。一般遗传算法都有一个固定的突变常数,又称为变异概率,通常是0.1或者更小,这代表变异发生的概率。根据这个概率,新个体的染色体随机的突变,通常就是改变染色体的一个字节(0变到1,或者1变到0)。

遗传算法实现将不断的重复这个过程:每个个体被评价,计算出适应度,两个个体交配,然后突变,产生下一代,直到终止条件满足为止。一般终止条件有以下几种:

  • 进化次数限制
  • 计算耗费的资源限制,如计算时间、计算占用的CPU,内存等
  • 个体已经满足最优值的条件,即最优值已经找到
  • 当适应度已经达到饱和,继续进化不会产生适应度更好的个体
  • 人为干预

算法实现原理:

ga

  • 1. 创建初始种群
  • 2. 循环:产生下一代
  • 3. 评价种群中的个体适应度
  • 4. 定义选择的适应度函数
  • 5. 改变该种群(交配和变异)
  • 6. 返回第二步
  • 7. 满足终止条件结束

3. 遗传算法R语言实现

本节的系统环境

  • Win7 64bit
  • R: 3.1.1 x86_64-w64-mingw32/x64 (64-bit)

一个典型的遗传算法要求:一个基因表示的求解域, 一个适应度函数来评价解决方案。

遗传算法的参数通常包括以下几个:

  • 种群规模(Population),即种群中染色体个体的数目。
  • 染色体的基因个数(Size),即变量的数目。
  • 交配概率(Crossover),用于控制交叉计算的使用频率。交叉操作可以加快收敛,使解达到最有希望的最优解区域,因此一般取较大的交叉概率,但交叉概率太高也可能导致过早收敛。
  • 变异概率(Mutation),用于控制变异计算的使用频率,决定了遗传算法的局部搜索能力。
  • 中止条件(Termination),结束的标志。

在R语言中,有一些现成的第三方包已经实现的遗传算法,我们可以直接进行使用。

  • mcga包,多变量的遗传算法,用于求解多维函数的最小值。
  • genalg包,多变量的遗传算法,用于求解多维函数的最小值。
  • rgenoud包,复杂的遗传算法,将遗传算法和衍生的拟牛顿算法结合起来,可以求解复杂函数的最优化化问题。
  • gafit包,利用遗传算法求解一维函数的最小值。不支持R 3.1.1的版本。
  • GALGO包,利用遗传算法求解多维函数的最优化解。不支持R 3.1.1的版本。

本文将介绍mcga包和genalg包的遗传算法的使用。

3.1 mcga包

我们使用mcga包的mcga()函数,可以实现多变量的遗传算法。

mcga包是一个遗传算法快速的工具包,主要解决实值优化的问题。它使用的变量值表示基因序列,而不是字节码,因此不需要编解码的处理。mcga实现了遗传算法的交配和突变的操作,并且可以进行大范围和高精度的搜索空间的计算,算法的主要缺点是使用了256位的一元字母表。

首先,安装mcga包。


> install.packages("mcga")
> library(mcga)

查看一下mcga()函数的定义。


> mcga
function (popsize, chsize, crossprob = 1, mutateprob = 0.01, elitism = 1, minval, maxval, maxiter = 10, evalFunc) 

参数说明:

  • popsize,个体数量,即染色体数目
  • chsize,基因数量,限参数的数量
  • crossprob,交配概率,默认为1.0
  • mutateprob,突变概率,默认为0.01
  • elitism,精英数量,直接复制到下一代的染色体数目,默认为1
  • minval,随机生成初始种群的下边界值
  • maxval,随机生成初始种群的上边界值
  • maxiter,繁殖次数,即循环次数,默认为10
  • evalFunc,适应度函数,用于给个体进行评价

接下来,我们给定一个优化的问题,通过mcga()函数,计算最优化的解。

题目1:设fx=(x1-5)^2 + (x2-55)^2 +(x3-555)^2 +(x4-5555)^2 +(x5-55555)^2,计算fx的最小值,其中x1,x2,x3,x4,x5为5个不同的变量。

从直观上看,如果想得到fx的最小值,其实当x1=5,x2=55,x3=555,x4=5555,x5=55555时,fx=0为最小值。如果使用穷举法,通过循环的方法找到这5个变量,估计会很费时的,我就不做测试了。下面我们看一下遗传算法的运行情况。


# 定义适应度函数
> f<-function(x){} # 代码省略

# 运行遗传算法
> m <- mcga(  popsize=200, 
+             chsize=5, 
+             minval=0.0, 
+             maxval=999999, 
+             maxiter=2500, 
+             crossprob=1.0, 
+             mutateprob=0.01, 
+             evalFunc=f)

# 最优化的个体结果
> print(m$population[1,])
[1]  5.000317    54.997099   554.999873  5555.003120 55554.218695

# 执行时间
> m$costs[1]
[1] 3.6104556

我们得到的最优化的结果为x1=5.000317, x2=54.997099, x3=554.999873, x4=5555.003120, x5=55554.218695,和我们预期的结果非常接近,而且耗时只有3.6秒。这个结果是非常令人满意地,不是么!如果使用穷举法,时间复杂度为O(n^5),估计没有5分钟肯定算不出来。

当然,算法执行时间和精度,都是通过参数进行配置的。如果增大个体数目或循环次数,一方面会增加算法的计算时间,另一方面结果也可能变得更精准。所以,在实际的使用过程中,需要根据一定的经验调整这几个参数。

3.2 genalg包

我们使用genalg包的rbga()函数,也可以实现多变量的遗传算法。

genalg包不仅实现了遗传算法,还提供了遗传算法的数据可视化,给用户更直观的角度理解算法。默认图显示的最小和平均评价值,表示遗传算法的计算进度。直方图显出了基因选择的频率,即基因在当前个体中被选择的次数。参数图表示评价函数和变量值,非常方便地看到评价函数和变量值的相关关系。

首先,安装genalg包。


> install.packages("genalg")
> library(genalg)

查看一下rbga()函数的定义。


> rbga(stringMin=c(), stringMax=c(),
     suggestions=NULL,
     popSize=200, iters=100,
     mutationChance=NA,
     elitism=NA,
     monitorFunc=NULL, evalFunc=NULL,
     showSettings=FALSE, verbose=FALSE)

参数说明:

  • stringMin,设置每个基因的最小值
  • stringMax,设置每个基因的最大值
  • suggestions,建议染色体的可选列表
  • popSize,个体数量,即染色体数目,默认为200
  • iters,迭代次数,默认为100
  • mutationChance,突变机会,默认为1/(size+1),它影响收敛速度和搜索空间的探测,低机率导致更快收敛,高机率增加了搜索空间的跨度。
  • elitism,精英数量,默认为20%,直接复制到下一代的染色体数目
  • monitorFunc,监控函数,每产生一代后运行
  • evalFunc,适应度函数,用于给个体进行评价
  • showSettings,打印设置,默认为false
  • verbose,打印算法运行日志,默认为false

接下来,我们给定一个优化的问题,通过rbga()函数,计算最优化的解。

题目2:设fx=abs(x1-sqrt(exp(1)))+abs(x2-log(pi)),计算fx的最小值,其中x1,x2为2个不同的变量。

从直观上看,如果想得到fx的最小值,其实当x1=sqrt(exp(1))=1.648721, x2=log(pi)=1.14473时,fx=0为最小值。同样地,如果使用穷举法,通过循环的方法找到这2个变量,估计会很费时的,我也不做测试了。下面我们看一下rbga()函数的遗传算法的运行情况。


# 定义适应度函数
> f<-function(x){}  #代码省略

# 定义监控函数
> monitor <- function(obj){}  #代码省略

# 运行遗传算法
> m2 = rbga(c(1,1),
+           c(3,3),
+           popSize=100,
+           iters=1000,
+           evalFunc=f,
+           mutationChance=0.01,
+           verbose=TRUE,
+           monitorFunc=monitor
+           )

Testing the sanity of parameters...
Not showing GA settings...
Starting with random values in the given domains...
Starting iteration 1
Calucating evaluation values... ....................................................... done.
Sending current state to rgba.monitor()...
Creating next generation...
  sorting results...
  applying elitism...
  applying crossover...
  applying mutations... 2 mutations applied
Starting iteration 2
Calucating evaluation values... ...................... done.
Sending current state to rgba.monitor()...
Creating next generation...
  sorting results...
  applying elitism...
  applying crossover...
  applying mutations... 4 mutations applied
Starting iteration 3
Calucating evaluation values... ....................... done.

# 省略输出...

程序运行截图

rbga-run

需要注意的是,程序在要命令行界面运行,如果在RStudio中运行,会出现下面的错误提示。


Creating next generation...
  sorting results...
  applying elitism...
  applying crossover...
  applying mutations... 1 mutations applied
Starting iteration 10 
Calucating evaluation values... .......................... done.
Sending current state to rgba.monitor()...
Error in get(name, envir = asNamespace(pkg), inherits = FALSE) : 
  object 'rversion' not found
Graphics error: Error in get(name, envir = asNamespace(pkg), inherits = FALSE) : 
  object 'rversion' not found

我们迭代1000次后,查看计算结果。


# 计算结果
> m2$population[1,]
[1] 1.650571 1.145784

我们得到的最优化的结果为x1=1.650571, x2=1.145784,非常接近最终的结果。另外,我们可以通过genalg包的可视化功能,看到迭代过程的每次的计算结果。下面截图分为对应1次迭代,10次迭代,200次迭代和1000次迭代的计算结果。从图中可以看出,随着迭代次数的增加,优选出的结果集变得越来越少,而且越来越精准。

rbga-all

默认图输出,用于描述遗传过程的进展,X轴为迭代次数,Y轴评价值,评价值越接近于0越好。在1000迭代1000次后,基本找到了精确的结果。


> plot(m2)

rbga-ev

直方图输出,用于描述对染色体的基因选择频率,即一个基因在染色体中的当前人口被选择的次数。当x1在1.65区域时,被选择超过80次;当x2在1.146区域时,被选择超过了80次。通过直方图,我们可以理解为更优秀的基因被留给了后代。


> plot(m2,type='hist')

rbga-hist

参数图输出,用于描述评价函数和变量的值的相关关系。对于x1,评价值越小,变量值越准确,但相关关系不明显。对于x2,看不出相关关系。


> plot(m2,type='vars')

rbga-vars

对比mcga包和genalg包,mcga包适合计算大范围取值空间的最优解,而用genalg包对于大范围取值空间的计算就表现就不太好了。从另一个方面讲,genalg包提供了可视化工具,可以让我们直观的看遗传算法的收敛过程,对于算法的理解和调优是非常有帮助的。

在掌握了遗传算法后,我们就可以快度地处理一些优化的问题了,比如接下来我会介绍的金融回测系统的参数寻优方案。让我们远离穷举法,珍惜CPU的每一秒时间。

参考文章
http://zh.wikipedia.org/zh/遗传算法

转载请注明出处:
http://blog.fens.me/algorithm-ga-r/

打赏作者

桶排序的Nodejs实现

算法为王系列文章,涵盖了计算机算法,数据挖掘(机器学习)算法,统计算法,金融算法等的多种跨学科算法组合。在大数据时代的背景下,算法已经成为了金字塔顶的明星。一个好的算法可以创造一个伟大帝国,就像Google。

算法为王的时代正式到来….

关于作者:

  • 张丹(Conan), 程序员Java,R,PHP,Javascript
  • weibo:@Conan_Z
  • blog: http://blog.fens.me
  • email: bsspirit@gmail.com

转载请注明出处:
http://blog.fens.me/algorithm-bucketsort-nodejs/

bucket-nodejs

前言

一个好的程序算法,可以提升百倍的程序性能。但并没有一种通用的算法,适用于所有场景。选择合适的算法,用在正确的地方,是一个好算法的开始。

本文将用Nodejs实现桶排序算法。

目录

  1. 桶排序介绍
  2. 桶排序算法演示
  3. Nodejs程序实现
  4. 案例:桶排序统计高考分数

1. 桶排序介绍

桶排序(Bucket sort)是一种基于计数的排序算法,工作的原理是将数据分到有限数量的桶子里,然后每个桶再分别排序(有可能再使用别的排序算法或是以递回方式继续使用桶排序进行排序)。当要被排序的数据内的数值是均匀分配的时候,桶排序时间复杂度为Θ(n)。桶排序不同于快速排序,并不是比较排序,不受到时间复杂度 O(nlogn) 下限的影响。关于快速排序,请参考文章:快速排序的Nodejs实现

桶排序按下面4步进行:

  • 1. 设置固定数量的空桶。
  • 2. 把数据放到对应的桶中。
  • 3. 对每个不为空的桶中数据进行排序。
  • 4. 拼接从不为空的桶中数据,得到结果。

桶排序,主要适用于小范围整数数据,且独立均匀分布,可以计算的数据量很大,而且符合线性期望时间。

2. 桶排序算法演示

举例来说,现在有一组数据[7, 36, 65, 56, 33, 60, 110, 42, 42, 94, 59, 22, 83, 84, 63, 77, 67, 101],怎么对其按从小到大顺序排序呢?

bucketsort

操作步骤说明:

  • 1. 设置桶的数量为5个空桶,找到最大值110,最小值7,每个桶的范围20.8=(110-7+1)/5 。
  • 2. 遍历原始数据,以链表结构,放到对应的桶中。数字7,桶索引值为0,计算公式为floor((7 – 7) / 20.8), 数字36,桶索引值为1,计算公式floor((36 – 7) / 20.8)。
  • 3. 当向同一个索引的桶,第二次插入数据时,判断桶中已存在的数字与新插入数字的大小,按照左到右,从小到大的顺序插入。如:索引为2的桶,在插入63时,桶中已存在4个数字56,59,60,65,则数字63,插入到65的左边。
  • 4. 合并非空的桶,按从左到右的顺序合并0,1,2,3,4桶。
  • 5. 得到桶排序的结构

3. Nodejs程序实现

像桶排序这种成熟的算法,自己实现一下并不难,按照上文的思路,我写了一个简单的程序实现。我感觉其中最麻烦的部分,是用Javascript操作链表。

现实代码如下:


'use strict';

/////////////////////////////////////////////////
// 桶排序
/////////////////////////////////////////////////
var _this = this
    , L = require('linklist');//链表

/**
 * 普通数组桶排序,同步
 *
 * @param arr Array 整数数组
 * @param num 桶的个数
 *
 * @example:
 * sort([1,4,1,5,3,2,3,3,2,5,2,8,9,2,1],5)
 * sort([1,4,1,5,3,2,3,3,2,5,2,8,9,2,1],5,0,5)
 */
exports.sort = function (arr, count) {
    if (arr.length == 0) return [];
    count = count || (count > 1 ? count : 10);

    // 判断最大值、最小值
    var min = arr[0], max = arr[0];
    for (var i = 1; i < arr.length; i++) {
        min = min < arr[i] ? min : arr[i];
        max = max > arr[i] ? max : arr[i];
    }
    var delta = (max - min + 1) / count;
    // console.log(min+","+max+","+delta);

    //初始化桶
    var buckets = [];

    //存储数据到桶
    for (var i = 0; i < arr.length; i++) {
        var idx = Math.floor((arr[i] - min) / delta); // 桶索引

        if (buckets[idx]) {//非空桶
            var bucket = buckets[idx];
            var insert = false;//插入标石
            L.reTraversal(bucket, function (item, done) {
                if (arr[i] <= item.v) {//小于,左边插入
                    L.append(item, _val(arr[i]));
                    insert = true;
                    done();//退出遍历
                }
            });
            if (!insert) { //大于,右边插入
                L.append(bucket, _val(arr[i]));
            }
        } else {//空桶
            var bucket = L.init();
            L.append(bucket, _val(arr[i]));
            buckets[idx] = bucket; //链表实现
        }
    }

    var result = [];
    for (var i = 0, j = 0; i < count; i++) {
        L.reTraversal(buckets[i], function (item) {
            // console.log(i+":"+item.v);
            result[j++] = item.v;
        });
    }
    return result;
}

//链表存储对象
function _val(v) {
    return {v: v}
}

运行程序:


var algo = require('./index.js');
var data = [ 7, 36, 65, 56, 33, 60, 110, 42, 42, 94,  59, 22, 83, 84, 63, 77, 67,101 ];
console.log(data);
console.log(algo.bucketsort.sort(data,5));//5个桶
console.log(algo.bucketsort.sort(data,10));//10个桶

//output
[ 7, 36, 65, 56, 33, 60, 110, 42, 42, 94, 59, 22, 83, 84, 63, 77, 67, 101 ]
[ 7, 22, 33, 36, 42, 42, 56, 59, 60, 63, 65, 67, 77, 83, 84, 94, 101, 110 ]
[ 7, 22, 33, 36, 42, 42, 56, 59, 60, 63, 65, 67, 77, 83, 84, 94, 101, 110 ]

需要说明的是:

  • 1. 桶内排序,可以像程序中所描述的,在插入过程中实现;也可以插入不排序,在合并过程中,再进行排序,可以调用快度排序。
  • 2. 链表,在Node的底层API中,有一个链表的实现< href="https://github.com/joyent/node/blob/master/lib/_linklist.js" target="_blank" ref="nofollow">_linklist.js,我没有直接使用,而是通过linklist包调用的。

程序源代码已上传到github, https://github.com/bsspirit/ape-algorithm。下载后,可以参考example.js文件中,来调用桶排序程序。

同时也在npm发布了,安装命令:

npm install ape-algorithm

4. 案例:桶排序统计高考分数

桶排序最出名的一个应用场景,就是统计高考的分数。一年的全国高考考生人数为900万人,分数使用标准分,最低200 ,最高900 ,没有小数,如果把这900万数字进行排序,应该如何做呢?

算法分析:

  • 1. 如果使用基于比较的排序,快速排序,平均时间复杂度为O(nlogn) = O(9000000*log9000000)=144114616=1.44亿次比较。
  • 2. 如果使用基于计数的排序,桶排序,平均的时候复杂度,可以控制在线性复杂度,当创建700桶时从200分到900分各一个桶,O(N)=O(9000000),就相当于扫描一次900W条数据。

我们跑一个程序,对比一次快速排序和桶排序。


//产生100W条,[200,900]闭区间的数据
var data = algo.data.randomData(1000*1000,200,900);
var s1 = new Date().getTime();
algo.quicksort.sort(data);//快速排序
var s2 = new Date().getTime();
algo.bucketsort.sort(data,700);//装到700个桶
var s3 = new Date().getTime();

console.log("quicksort time: %sms",s2-s1);
console.log("bucket time: %sms",s3-s2);

//output
quicksort time: 14768ms
bucket time: 1089ms

所以,对于高考计分的案例来说,桶排序是更适合的!我们把合适的算法,用在适合的场景,会给程序带来超越硬件的性能提升。

转载请注明出处:
http://blog.fens.me/algorithm-bucketsort-nodejs/

打赏作者