EA交易的自我优化: 进化与遗传算法
目录
- 简介
- 1. 进化算法最初是如何出现的
- 2. 进化算法 (方法)
- 3. 遗传算法 (GA)
- 3.1. 应用程序的领域
- 3.2. 用以解决的问题
- 3.3. 经典 GA
- 3.4. 搜索策略
- 3.5. 与经典的最优搜索的区别
- 3.6. GA 的术语
- 4. GA 的优点
- 5. GA 的缺点
- 6. 实验部分
- 6.1. 搜索预测器的最佳组合
- 6.2. 搜索交易系统(TS)的最佳参数:
- 7. 提高质量特性的方法
- 结论
简介
很多交易者很久之前就意识到了EA交易自我优化,也就是它们不需要停止交易的必要性,有一些相关文章(文章1, 文章2, 文章3, 文章4)已经发布,这些文章中的实验室基于这里提出的开发库的,然而,因为它们是以前发布的,而随后又出现了一些新的强大的算法以及应用它们的新方法,并且,我觉得这些文章是开发人员写的,而且也是面向开发人员的。
在本文中,我会尝试介绍遗传算法(GA)的实际应用,而不深入讨论技术细节,是特别针对交易人员的。对于像我这样的用户,了解GA运行的原则,影响GA收敛的质量和速度的重要性和参数值,以及它的其它实用属性是很重要的,所以,我可以将心比心,我将从GA出现的历史开始说起,进而介绍它并认识提高的GA的参数,另外,我们还将把GA与一些进化算法做比较。
1. 进化算法最初是如何出现的
进化计算的历史是从几个不同独立模式的出现开始的,遗传算法和Holland分类系统发布于60年代早期,并且在"自然与人造系统中的适应性(Adaptation in Natural and Artifical Systems)"一书于1975年发表之后得到了广泛的关注,它也是此领域的经典之一。在70年代,在随机搜索框架中, L.A. Rastrigin 介绍了一些使用生物行为的思路的算法。这些思路的实现是通过I.L. Bukatova 在进化建模方面的工作发展进行的。而在实现 M.L. Tsetlin 有关随机发生机器的适应与优化行为时,Y.I. Neumark 提出了基于物种的发展与消亡的模型而搜索全局极值的方法。Fogel 和 Walsh 分别为进化编程的发展做出了很大贡献,尽管他们采用的方法不同,他们的方法都是基于自然界中若干原则并加以简化的策略,这样它们就可以在一台计算机上使用,
它们致力于模拟进化的自然系统,可以主要分为两类,
- 基于生物学原则的建模系统,它们已经在优化任务中成功应用,并且可以简单地使用非生物学语言进行描述。
- 从生物学角度看更加真实的系统,但是从应用方面看没有特别的优势,它们是更类似于生物学的系统并且导向偏少(或者根本没有导向),它们有一些复杂而有趣的行为,并且显然在短期内也将找到实际应用。
当然,我们无法在实际应用中严格分开这些方面,这些类别实际上是两个极点,而在它们之间是各种计算机系统,与第一个极点更接近的是进化算法,例如进化编程,遗传算法以及进化策略等,与第二个极点接近的是可以被划归为人工生命的系统。
2. 进化算法 (方法)
进化算法 — 人工智能的一个分支(进化建模的一部分), 它利用自然选择的过程来建模。我们列举它们中的一些:
- 遗传算法 — 启发式搜索算法,用于通过随机选择,组合和改变想要的参数进行优化和建模。
遗传编程 — 自动创建或者修改使用遗传算法的程序;
进化编程 — 与遗传编程类似,但是程序的结构是固定的,只有数值需要改变;
进化策略 — 类似于遗传算法,但是只有正向的突变转移到下一代;
不同的进化;
神经进化— 与遗传编程类似,但是基因组是人工神经网络,所进化的是特定网络拓扑下的权重,或者除了权重的进化还会进行拓扑的进化。
它们都是根据生物学进化的理论进行建模的 - 选择,交叉孕育,突变和复制的过程。物种的行为是由环境决定的,多个物种构成种群,种群根据由环境设定的目标函数进行选择的规则而进化,这样,种群中的每个物种(个体)都有环境给予的赋值,只有最适合的物种会倍增,重组和突变使得个体可以改变以适应环境,这样的算法就是自适应搜索机制。
进化方法 (EM) — 用于解决优化和结构整合任务的接近(启发式)方法。大部分的EM是基于静态方法的,通过搜索条件并对想要的解决方案做迭代的逼近。
进化式计算构成了人工智能的一部分,当使用这种方法创建人工智能系统时,重点是基于它可能改变(进化)的规则建立初始化模型,同时,模型可以通过各种不同方法来创建,例如,可以通过神经网络或者设置一系列逻辑规则,退火,遗传算法,PSO, ACO, 以及与主进化方法相关的遗传编程。
与明确的数学编程方法不同,进化方法允许在合理时间范围内找到接近最优的方法,而且和其他的启发式优化方法不同,它们的特征是对应用程序的特性依赖更少(也就是说更为通用),并且在大多数情况下可以提供更好的接近最优的方案。EM的通用性也是由任务的可行性决定的,它可以使用不可度量的变量空间(意思是可以有语义上的变量,包括那些无法量化的变量),
在模拟退火中,就是模仿减少潜在体能的过程中,在当前点会有一些管理参数的改变,当有功能提高时,新点总会被接受而也有少部分可能在变坏时也被接受,
EM 是遗传方法和算法中最重要的应用。遗传算法 (GA) 是基于使用继承和在模拟进化的过程中强化某个特定应用的多个对象的有用特性的,
对象的属性用参数值表示,被称为遗传方法中的染色体,染色体的子集被称为种群,在遗传算法中进行操作。遗传原则的模拟 — 在种群的成员中随机选择父母,染色体交叉,基于目标功能的进化来选择后代,构成新一代对象,这个过程引起世代之间目标功能(用途功能)数值的提高,
在EM中还有方法与GA不同,它们操作的是单个染色体而不是多个染色体。通过这种方式,在被称为Hillclimbing的本地搜索方法中,基于独立参数的随机改变(记录中的栏位数值,或者换句话说,染色体中的基因),这样的改变被称为变异,在每次变异以后,会评估适应度功能。只有适应度提高的情况下,变异的结果才会被保存在染色体中。在"退火建模"中, 变异的结果根据所得的数值以某个可能性值来保存,
在粒子群优化方法中, 会模拟多代理的行为,以其中最佳代理的状态来协调它们的状态。
ACO方法是基于模仿蚂蚁的行为,它们会在食物来源和蚂蚁窝之间找到最短的线路。
3. 遗传算法 (GA)
遗传算法 — 后来在解决功能优化任务时的常用自适应搜索方法,它们是基于生物机体的遗传过程的:生物种群在世代之间进化,遵从自然选择和适者生存的原则,这些是由查尔斯.达尔文发现的。通过模拟这个过程,如果正确编码,遗传算法可以用于解决真实案例。
在自然界,种群中的物种会相互竞争各种资源,例如食物和水,另外,种群中的同一种类的成员会竞争以吸引配偶。越能适应环境的物种就有更好的创造后代的机会,较差的物种或者无法繁殖,或者后代很少。这就意味着适应性更好的物种的基因才能在每个新的世代中传播到更多的后代中,从不同父母继承而来的成功特征的组合有时可能产生出"超级适应"的后代,它的适应性比它父母任一方都更好,通过这种方式,会产生新的种类而更好地适应环境。
遗传算法就是模拟这种机制,它们操作一系列"物种" — 种群, 它们中的每一种都提供解决某一问题的方案,每个"物种"都根据它相关解决方案的"好坏"进行"适应性"评估,适应性最好的物种获得与其他种群物种使用"交叉培育"而"创造"后代的机会。这使新的物种得以出现并从它们的父母那里继承一些组合的特征。最不适应的物种很难创造后代,所以它们拥有的特征将会在进化的过程中逐渐从种群中消失。
这就是新的代表解决方案的种群如何能够通过选择前一代的最佳代表,交叉培育并获得新的物种而进行繁殖,新的世代包含了前一代中更高比例的"好"的特征,通过这种方式,好的特征可以一代一代在整个种群中传播。交叉培育最具适应性的物种可以发现搜索空间内最具优势的区域,最终,种群会达到最佳解决方案,
使用GA来实现生物学进化的想法有多种方式。
3.1. 应用领域
真实解决的任务可以认为是对最佳值的搜索,这个值可以是依赖于几个输入参数的复杂函数。在一些情况下,就是为了找到参数的数值以达到最精确的函数值。在另外的情况下,不需要精确的最佳值,而是比集合中其他值更好就可以认为是解决方案。在这种情况下,遗传算法通常是搜索"最佳"值的最合适的方法。遗传算法的强大之处在于它可以同时操作多个参数,GA的这种特性在数以百计的应用程序中得到应用,包含了飞机的设计,非线性微分方程系统中算法参数的设置和搜索稳定条件等。
然而,有时GA没有能够达到预期中的效果。
让我们假定,有个真实的任务,需要搜索最优决定,怎样才能知道它是否适合使用 GA 呢?直到现在这个问题也没有严格的答案。但是,很多研究人员分享了他们的经验,认为GA在以下情况下可以作为有效的搜索方法:
- 如果需要作研究的搜索领域很大,并且不是完全平滑和一致的(也就是说,包含一个平滑极点);
- 如果适应性函数包含噪声;
- 或者如果任务并不严格要求找到全局最优。
换句话说,当所要求的是找到可以接受的"好的"方案(这在实际工作中更为常见),GA和其他不使用搜索领域专门知识的方法相比是具有竞争力的,
如果搜索范围较小,而方案可以通过穷举搜索来找到的话,您可以休息等到找到最佳方案,因为GA很可能只能找到局部的最优方案,而不是全局的最佳方案。如果空间是平滑和一致的,则其他一些渐进算法(例如梯度下降法)将比GA更为有效。
如果关于搜索范围还有额外的知识(例如,著名的"旅行商问题"的范围), 使用由区域决定的启发式算法也会超过GA。考虑到适应性函数的结构相对复杂,一些搜索方法会一次使用一个方案,例如简单的下降方法,可能会“跌入”一个局部方案。然而,遗传算法很少会在多极值环境下只找到局部最优,因为它是在整个解决方案的“种群”中运行。
当然,这样的假定并不能严格预测何时GA是比其他方法更为有效的,GA 的有效性在很大程度上依赖于解决方案的编码,算子,设置参数,成功的标准等。关于遗传算法的所记录的理论知识中并没有讨论到严格的正确预测机制的发展。
3.2. 用以解决的问题
遗传算法用于解决以下的任务:- 优化功能
- 优化数据库的请求
- 各种图论中的任务(旅行商问题,颜色,寻找配对等)
- 设置和训练人工神经网络
- 分布任务
- 创建日程表
- 游戏策略
- 逼近理论
3.3. 经典 GA
简单 GA 的操作简单的 GA 随机生成初始族群结构,GA 的操作是一个迭代的过程,会一直运行直到达到一定的代数或者满足了其他一些终止条件。在算法的每一代中都实现了适应度的比例选择,单点交叉和变异。
首先, 比例选择应用于每个结构中,Ps(i) 概率等于它的适应度与种群总适应度的比例。
根据Ps(i)的值,会一共选择n个物种(有替换)用于未来的遗传数据处理,最简单的比例选择是轮盘选择(Goldberg, 1989c) — 物种是根据轮盘的第n"圈"来做选择的,轮盘在每个部分中包括了种群中的各个成员,第i个部分的比例就对应着 Ps(i) 的数值。在这种选择方式下,种群中适应性最好的成员比适应较差的物种更加容易被选择,
在选择之后,n个被选择的物种会进行使用Pc的概率进行交叉(有时候被称为重组)。n个字符串随机分成 n/2 对,对于每个配对,使用 Pc 的概率进行交叉,相应地,没有交叉的概率为 1-Pc , 而继续达到变异阶段的物种数量是常数。如果有交叉,获得的后代会替换它们的父母而继续变异。
单点交叉是如下运行的:首先,从l-1个断点中随机选取一个,(断点就是字符串中相邻字节之间的区域。) 每个父母的结构都根据这个点分成两个片段,然后,不同父母的对应片段相互连接,从而创建出子女的两个基因组。
在交叉阶段结束后,再进行变异操作,在每个字符串中,每个字节以 Pm 的几率变成相反,这就是变异。在变异后,获得的种群覆盖原有的种群,这样循环中的一代就结束了。之后的世代以同样方式处理: 选择,交叉和变异。
GA的研究人员现在提供了许多其他的选择,交叉和变异的算子,以下是最常用的一些:首先, 联赛选择算法(tournament selection) (Brindle, 1981; Goldberg и Deb, 1991). 它通过实现n轮联赛来选择n个物种,每轮联赛都从种群中选择k个元素,并在其中选择最好的物种,联赛选择法中,k=2 是最常用的。
精英选择方法(Elite selection methods) (De Jong, 1975) 保证在选择中会保留种群中的最佳成员,最常见的过程是,对于最佳的物种,假如它与其它物种一样,没有通过选择,交叉和变异的过程,会给它复活的机会。精英选择法可以被集成用于几乎所有的标准选择方法中。
双点交叉 (Cavicchio, 1970; Goldberg, 1989c) 和 均匀交叉 (Syswerda, 1989) — 是单点交叉算子的后继替代者,在双点交叉中,会选择两个断点,而父母染色体在这两点之间会交换染色体,在均匀交叉中,第一个父母会有一定几率把每个字节都继承到第一个子女中,否则,这个字节就转移到第二个子女中,反之亦然。
遗传算法中的基本算子
选择算子
在本阶段,会选择用于将来繁殖的更优种群,通常会选择指定数量的最适应的部分,对于"克隆者", 也就是那些具有相同基因的部分,是需要排除的。
交叉孕育算子
最常见的情况是,在两个最佳的物种之间进行交叉孕育,通常的结果是获得两个物种,分别从它们的父母处取得对应的组件,这个算子的目的是在种群间传播"好的"基因,并且对种群密度高的区域加以限制。
变异算子
变异算子就是在物种中把一定数量的元件该变成另外某个数量,实际上,它在一方面减小局部极值,而在另外一方面在种群中加入了新的信息,
- 如果是二进制符号,就会反转一个字节,
- 它可以改变数字标记到一定数值,(很可能是最接近的数值),
- 它替换成其它的数字标量。
停止标准
- 找到全局或者次优的方案
- 退出回到"稳定状态"
- 用完进化中指定数量的世代
- 用完了进化的时间
- 用完了对目标函数的调用次数
3.4. 搜索策略
搜索是当达到最优的方法未知时来找到解决方案的通用方法之一,有两种搜索策略: 探索最佳方案以及解决方案空间中进行研究,梯度方法就是一种策略的一个例子,它选择最可能提高的方案,而忽略整个搜索区域的研究。随机搜索是另外一种策略的例子,它与前者相反,它研究方案而不是对搜索区域的某个角度进行研究。遗传算法是一类搜索方法,它是综合了这两种策略的通用方法。使用这些方法可以在研究和探索最佳方案之间得到可以接受的平衡。在遗传算法的开始,种群是随机的,拥有各种元素,因而,交叉孕育算子会进行搜索范围中的大范围研究,通过增加取得方案的适应性函数,交叉孕育算子可以搜索它们的边界,换句话说,这种搜索策略 (探索最佳方案或者研究方案区域)的交叉孕育算子是通过种群密度定义的,而不是算子本身。
3.5. 与经典的最优搜索的区别
一般来说,用于解决优化问题的算法就是通过一系列计算过程逐渐聚合到优异的方案中,大多数经典的优化方法根据梯度或者在更大范围派生出目标函数而生成一个固定的计算序列,这些方法应用于搜索区域内的一个单点输出,然后,结果会向目标功能增加或者减小而逐渐进步,通过这样的方法,有一定风险会达到仅仅局部的最优结果。
遗传算法则使用可能方案的种群在各个方向上进行同时搜索,从一个种群切换到另外一个种群会避免只达到局部最优。种群经历的事情与进化类似: 相对好的方案在每一代中繁殖,而相对不好的会死去。遗传算法使用概率的原则来分辨复制或者损坏的染色体,从而把搜索引导到可能向目标功能发展的区域。
在近些年实现了很多种遗传算法,其中的大多数都与初始的经典算法大相径庭,这也是为什么有许多算法类都有些类似,都叫做"遗传算法",而并不是只有一个模型。研究人员从不同角度进行各种实验,使用交叉算子,变异算子,特殊算子等各种不同算法进行繁殖和选择。
尽管在GA中使用的进化发展模型是与自然界类比得来的,然而GA是一个强大的工具,它可以被成功应用于许多类型的任务中,包括那些很困难,使用其他方法有时无法解决的任务。然而,GA以及其他进化计算相关的方法并不能保证在一定时间内找到一个全局最佳的方案,也不能保证全局最佳方案能够被找到。然而,遗传算法擅长于"相对较快"地找到"相对较好"的方案。当可以使用特定方法来寻找方案时,几乎这些方法都会比GA更加高效和准确,而GA的主要优势是它们可以用于更加复杂的人物,即使没有特定方法可用,即使已经有了不错的方法,GA也可以用于进一步的提高。
3.6. GA 的术语
因为GA是来源于自然科学(遗传学)和计算机科学的,所以使用的术语是自然与人工的混合,GA以及解决优化问题的相关术语在以下表格中提供。1.1.
表格 1.
遗传算法 | 解释 |
---|---|
染色体 | 可能的方案 (参数集) |
基因 | 用于优化的参数 |
位置(Locus, location) | 染色体中基因的位置 |
等位基因 | 基因的值 |
表现型 | 未编码方案 |
基因型 | 编码方案 |
经典(单点)交叉.
"传统"的遗传算法在两个染色体在某一特定位点截断时使用单点交叉,随后交换得到的部分。其他的各种算法也包含了有一个或者多个截断点时的其它类型的交叉。DeJong 曾经研究了多点交叉的效率,并且得到的结论是,双点交叉是有提高的,但是再增加更多的截断点会降低遗传算法的活跃度。. 增加额外交叉点的问题是,标准阻断很可能会被打断,然而,多点交叉的优点是,可以更加详细地研究状态区域。
双点交叉
在双点交叉(以及通常的多点交叉)中, 当把线形的染色体首尾连到一起时就形成了环形,为了把一个环的某个片段改到另一个环上,就要选择两个截断点。在这种表现方式中,单点交叉也可以被看作是两个点的交叉,只是一个点固定在字符串的开始部分。所以,双点交叉也可以解决单点交叉所解决的任务,只是方法更复杂一些。把染色体看作可能包含标准模块的环形,因为它们在字符串末尾可能会"循环回来",许多研究人员现在也同意,一般来说,双点交叉比单点交叉更好。
均匀(同类)交叉。
均匀交叉和单点交叉有本质的不同,在一代中的每个基因都是根据随机生成的交叉掩码从父母的一方复制而来,如果交叉掩码中有1,基因就从第一个父母那里复制,如果是0,基因就从第二个父母那里复制。创建第二代的过程是一样的,相反的是交换了父母,而对每对父母随机生成新的交叉掩码。
微分交叉.
除了交叉之外,还有其他的交叉繁殖方法,例如,为了搜索许多物理量的最大/最小函数值时,"微分交叉法"是最成功的。我们将简要描述它的概念。我们假设a和b是种群中的两个个体,也就是说,我们函数所以来的两个物理向量。其子女(c) 通过公式 с=a+k*(a-b)获得, 其中 k — 是某个物理比例 (可能依赖于 ||a-b|| — 矢量间的距离)。
该模型的变异是增加一个随机的长度较短的向量个体,如果输出函数是连续的,模型就运行得很好,如果是平滑的就更好了。
反转和重排。
染色体中基因的顺序在构建模块,有效地运行算法中经常是很关键的,在算法的运行中,会提出在染色体中对基因位置进行重排的方法。其中一种这样的方法就是反转,它在染色体中反转两个随机选择的基因的位置。(当使用这些方法时,基因需要进行某种"标记",这样就能在染色体中不考虑它们的位置而识别它们。)
重排的目的是尝试寻找基因的顺序来发现最佳的进化潜力。许多研究人员在他们的工作中使用反转,尽管他们很少进行评估或者估算它的贡献。Goldberg 和 Bridges 在一个很小的任务重分析了重排算子,显示了它可能提供某种便利,但是他们确定他们的方法在大的任务中没有同样的作用。
重排也可以认为是扩大了搜索区域,遗传算法不仅尝试找到好的基因数值集合,也尝试它们"正确"的顺序,这是对解决问题的更大挑战。
什么是上位性(epistasis)?
遗传学中"上位性"名词的意思是,一个个体的基因的适应性由另外一处的基因决定,换句话说,遗传学中使用"上位性"来表示"开关"或者"掩盖"效应: "一个基因的表现被其他位点的基因抑制而不能表达,就是上位性。上位基因有时候被称为抑制基因,因为根据描述它们会影响其它基因。在GA的术语中,听起来就像: "物种的适应度依赖于染色体中的某个基因型"。
什么是假性最适度(false optimum)?
遗传算法中的一个基本原则就是,全局最适合的物种的模板染色体会以一定频率增加,这在较短的模板,即基因块中式正确的,最终,这些优质的模板会在交叉中相遇,而创建出全局优质的染色体。但是,如果全局最适合物种中不包含的模板以更快频率增加,遗传算法将会被错误引导而远离全局最优,而不是接近它。这种现象就叫做假性最适度(false optimum)。
假性最适度是上位的一个特例,Goldberg 和其他人曾深入分析过。在遗传算法中,假性最适度是直接与上位的负面影响相关联的。
在统计中,如果模板的适应度高于种群中全部模板的平均适应度,它将在种群中按一定频率增长。任务就是如果模板不包含在全局最优中而还会比其他模板以更快频率增长,就把它标记为假性最适度。假性最适度标记的任务很是复杂。但是,Grefenstette 机智地演示了,该任务并非总是那么复杂。在第一代之后,遗传算法在搜索范围内不获得对象选择点,所以它也就不能针对性地评估模板的全局平均适应度,它只能获得模板适应度的有一定偏颇的评估,有时候这种偏颇有助于遗传算法的匹配(就算任务中可能出现很强的假性最适度)。
什么是近亲繁殖(inbreeding),远亲繁殖(outbreeding),选择性选择(selective choice), 随机繁殖(panmixia)?
选择父母对有几种方法,其中最简单的是随机繁殖,这种方法的意思是随机选择父母对,就是父母双方都是从整个种群中随机选择的。这种条件下,任何物种都可能成为几个父母对的成员。尽管这很简单,这种方法还就是解决各种任务的通用方法。但是,这对种群中的数量要求相对严格,因为使用这种方法的算法在种群数量增加时,效率会明显降低。
使用选择性的办法来选择作为父母对的物种,只有那些种群中适应度高于平均适应度的物种能够成为"父母",这样的候选者在配对时有相同的概率,
这种方法使得算法可以有更快的收敛性,然而,因为是快速收敛,当必须找到多个极值的时候就不适合使用这种选择父母对的方法了,因为这种算法只会快速找到其中的一个解。另外,有些任务的适应度比较复杂,快速收敛可能把不够成熟的收敛变成一个类似最优的方案。这个缺点可以通过使用合适的选择机制,"减缓"算法的快速收敛来部分缓解。近亲繁殖是这样一种方法,当配对的第一个成员是随机时,第二个物种的选择离第一个成员尽可能接近。
类似的物种概念也应用于远亲繁殖,只是现在配对由尽可能远的物种来组成。
最后两种方法在遗传算法中对行为有不同影响。其中,近亲繁殖的特点是集中搜索局部结点,实际上,这样会把种群分成多个独立的局部群组,围绕在区域中的可能极值点周围。远亲繁殖的目标是防止算法收敛到已经找到的方案,它迫使算法搜索新的还需要探索的区域。
GA参数的动态自组织
很多时候,遗传算法中参数的选择和特定遗传算子的选择是凭直觉选择的,因为没有迹象表明哪些设置和算子更好,但是,我们不应该忘记,GA的特点是动态的,在进行计算时算法是"可变"的。那么为什么不让算法自我配置,在解决任务时适应自身呢?
最简单的方法就是进行所应用算子的自适应,为此,我们将在算法中构建几个(越多越好)不同的选择算子(精英,随机,轮盘,...),交叉算子(单点,两点,均匀,...)以及变异算子(随机单个元素,绝对,...)。让我们把每个算子的应用概率设为相同,在算法的每次循环中,我们将从每组中选择一个算子(选择,交叉,变异),然后再进行传播。我们将会标记出收到算子的物种,然后,如果新的传播概率可以基于种群中的信息进行计算(应用某算子的概率是种群中通过此算子获得物种的数量的比例),那么遗传算法就能拥有动态自适应的机制。
这种方法还带来了另外的好处: 现在,不需要担心使用的随机图生成工具了(线性,指数,等等),因为算法会动态改变传播模式。
迁移与人工选择方法
与通常的 GA 不同, 进行宏进化, 也就是说,不是只有一个,而是创建多个种群。这里的遗传搜索是通过联合来自不同种群的父母而进行的。
间断平衡法
这种方法是基于间断平衡理论,描述了通过火山和其他地壳改变而快速进化的状况。为了在技术任务中应用此方法,建议在种群中随机选择个体,然后形成新的当前的世代。这里使用的是野生动物中,父母配对的无意识随机与组合的选择。然后,这两种选择的结果也随机混合,要根据最佳个体存在的状况,而不是把种群大小固定。这样的修改过的间断平衡法可能减少了不健全的种群而增加了含有最佳物种的种群大小。间断平衡法是一种强大的压力方法,可以改变环境而更有效地退出局部的陷阱。
4. GA 的优点
遗传算法与经典的优化方法比较有两个主要优点:
1. GA 对目标函数的类型和限制没有多少数学上的需求。研究人员不需要简化模型,牺牲它的特点来人工保证应用程序使用数学方法。差别很大的目标函数和限制类型(线性与非线性)都可以被定义,连续的以及混合的通用的数据集都可以使用。
2. 当使用经典的步骤方法时,全局最优只有在问题有突出属性的时候才能找到,同时,遗传算法的进化操作使得可以更加高效地搜索全局最优。
GA的不算关键但是很重要的优点:
大量的参数使得可以高效地构建启发式优化;
高效的并行;
与随机搜索一样好;
与生物学相关联,可以期待GA有指数级的高效。
5. GA 的缺点
多个自由的参数把"GA的操作"转变成"GA的游戏"
缺乏覆盖率的证据支持
在简单的目标函数中(平滑,单个极值,等等), 遗传算法通常比简单的搜索算法更慢。
6. 实验部分
所有的试验都将使用 R 3.2.4 语言环境进行。我们使用来自前一篇文章的一组数据和大量的函数来训练模型。
CRAN托管部分包含了大量的用于优化和数学编程相关任务的功能包,我们将使用其中的GA和EM相关的方法来解决上述任务。在优化过程中建立模型的唯一要求就是 — 速度,如果训练要好几百秒,这样的方法就不作建议。考虑到每一代中至少有100个物种,并且种群还要通过几个世代(从一个到几十),优化过程可能延长为不可接受的时间。在前面的文章中,我们使用了两种深度网络(使用了SAE和RBM 初始化),着两种方法都展示出很高的速度并且可能在遗传优化中很好地应用。
我们将解决两类优化任务:搜索最佳的预测器组合以及选择指标的最佳参数。我们将使用XGBoost(极限梯度推进,Extreme Gradient Boosting)算法,它经常用于解决第一种任务(预测器选择),这样来学习新的算法。在来源中提到,它在分类任务中有很好的结果。这种算法在 R, Python, Java 语言中都有,在 R 语言中,这个算法在“xgboost” v 功能包中实现。0.4-3.
为了解决第二个任务(选择指标的最佳参数), 我们将使用 MACDsample EA交易作为最简单的例子 , 来看通过遗传算法优化我们可以收获什么。
6.1. 搜索预测器的最佳组合
在解决优化任务时,很重要的是定义以下内容:
将要优化的参数;
优化标准 — 需要最大化/最小化的标量. 可以有多个标准;
目标(适应度)函数,用于计算优化标准的数值。
在我们的实例中,适应性函数将一直实现以下内容:
构建初始数据桢;
把它分为训练部分/测试部分;
训练模型;
测试模型;
计算优化标准.
优化标准可以是标准度量,例如准确率(Accuracy),Recall, Kappa, AUC,以及开发人员自己提供的数值。我们将在此使用分类误差。
对预测器最佳组合的搜索将使用"tabuSearch" v.1.1 功能包进行,它是HillClimbing算法的扩展。TabuSearch 算法使用由用户指定的目标函数来优化二进制字符串,结果是,它输出目标函数最高值的二进制配置。我们将使用这个算法来搜索预测器的最佳组合。
主函数:
tabuSearch(size = 10, iters = 100, objFunc = NULL, config = NULL, neigh = size, listSize = 9, nRestarts = 10, repeatAll = 1, verbose = FALSE)
参数:
size – 优化的二进制配置的长度;
iters – 搜索算法的迭代数量;
objFun – 一个由用户提出的方法,用来评估特定二进制串在目标函数的结果;
config – 开始配置;
neigh – 每次迭代中检验的相邻配置的数量,默认情况下,它等于二进制串的长度。如果数量小于串的长度,就随机选择邻居;
listSize – taboo 列表的大小;
nRestarts – 搜索算法中重新开始的最大次数;
repeatAll – 重复搜索的次数;
verbose – 逻辑值,如果为 true, 会打印当前算法的阶段名称,例如,准备阶段,强化阶段,区分阶段等。
我们将写一个目标函数并继续试验。
ObjFun <- function(th){ require(xgboost) # 如果二进制串全部为0就退出 if (sum(th) == 0) return(0) # 在二进制串中,对应着1的预测器名称 sub <- subset[th != 0] # 创建用于训练模型的结构 dtrain <- xgb.DMatrix(data = x.train[ ,sub], label = y.train) # 训练模型 bst = xgb.train(params = par, data = dtrain, nrounds = nround, verbose = 0) # 使用文本设定计算预测 pred <- predict(bst, x.test[ ,sub]) # 计算预测偏差 err <- mean(as.numeric(pred > 0.5) != y.test) # 返回质量标准 return(1 - err) }
为了进行计算,我们应当准备用于训练和测试该模型的数据集,并且定义该模型的参数和优化的初始配置,我们使用与前一篇文章相同的数据和函数 (EURUSD/M30, 6000 bars 至 14.02.16)。
含有注释的代码序列:
#---tabuSearch---------------------- require(tabuSearch) require(magrittr) require(xgboost) # 输出的数据桢 dt <- form.data(n = 34, z = 50, len = 0) # 在初始集合中所有预测器的名称 subset <- colnames(In()) set.seed(54321, kind = "L'Ecuyer-CMRG") # 准备用于训练和测试的数据集 DT <- prepareTrain(x = dt[ ,subset], y = dt$y, balance = FALSE, rati = 4/5, mod = "stratified", norm = FALSE, meth = method) train <- DT$train test <- DT$test x.train <- train[ ,subset] %>% as.matrix() y.train <- train$y %>% as.numeric() %>% subtract(1) x.test <- test[ ,subset] %>% as.matrix() y.test <- test$y %>% as.numeric() %>% subtract(1) # 初始的二进制矢量 th <- rep(1,length(subset)) # 模型的参数 par <- list(max.depth = 3, eta = 1, silent = 0, nthread = 2, objective = 'binary:logistic') nround = 10 # 初始配置 conf <- matrix(1,1,17) res <- tabuSearch(size = 17, iters = 10, objFunc = ObjFun, config = conf, listSize = 9, nRestarts = 1) # 对应函数的最大值 max.obj <- max(res$eUtilityKeep) # 二进制数组的最佳组合 best.comb <- which.max(res$eUtilityKeep)%>% res$configKeep[., ] # 预测器中的最佳 best.subset <- subset[best.comb != 0]
我们开始10次迭代的优化,从而看看最佳质量的标准和预测器集合。
> system.time(res <- tabuSearch(size = 17, iters = 10, + objFunc = ObjFun, config = conf, listSize = 9, nRestarts = 1)) user system elapsed 36.55 4.41 23.77 > max.obj [1] 0.8 > best.subset [1] "DX" "ADX" "oscDX" "ar" "tr" "atr" [7] "chv" "cmo" "vsig" "rsi" "slowD" "oscK" [13] "signal" "oscKST" > summary(res) Tabu Settings Type = binary configuration No of algorithm repeats = 1 No of iterations at each prelim search = 10 Total no of iterations = 30 No of unique best configurations = 23 Tabu list size = 9 Configuration length = 17 No of neighbours visited at each iteration = 17 Results: Highest value of objective fn = 0.79662 Occurs # of times = 2 Optimum number of variables = c(14, 14)
计算大约花费了37秒,预测准确率为0.8,使用了14个预测器。取得的默认设置的质量指标是很好的。让我们进行另一次计算,只是使用100次迭代。
> system.time(res <- tabuSearch(size = 17, iters = 100, + objFunc = ObjFun, config = conf, listSize = 9, nRestarts = 1)) user system elapsed 377.28 42.52 246.34 > max.obj [1] 0.8042194 > best.subset [1] "DX" "ar" "atr" "cci" "chv" "cmo" [7] "sign" "vsig" "slowD" "oscK" "SMI" "signal" >
我们看到,迭代的增加使得计算时间部分增加,但和预测的精度不同,它只是少许增加了。这就意味着质量指标的提高必须通过设置模型的参数。
使用GA来选择最佳的预测器集合并不是唯一的算法和功能包,您可以使用kofnGA, fSelector 功能包。 除此之外,在使用了GA的"caret"功能包的gafs()函数中也实现了预测子的选择。
6.2. 搜索TC的最佳参数
1. 用于预测的输出数据我们将使用 MACDSampl EA交易作为例子,
在 MACDSample EA交易中, 实现了这样的算法:当macd 和信号线交叉时会生成信号,使用了一个指标。
MACD(x, nFast = 12, nSlow = 26, nSig = 9, maType, percent = TRUE, ...)参数
x |
一个变量的时间序列; 通常是价格,但是也可以是交易量,等等。 |
nFast |
快速 MA 的周期数。 |
nSlow |
慢速 MA 的周期数 |
nSig |
信号 MA 的周期数 |
MaType – 所应用 MA 的类型
percent – 逻辑值,如果为 true, 就返回快速和慢速MA差异的百分比,否则 — 就是简单的差值。
MACD 函数返回两个变量: macd — 快速MA和慢速MA之间的差,或者快速MA和慢速MA之间距离变化的速度; signal — 这个差距的MA. MACD 是把震荡指标应用于价格的一个特定实例,它也可以用于任意时间框架内的某个变量。常用的 MACD 时间周期数是26和12,但是函数初始使用的指数常数是0.075和0.15,它们更接近25.6667和12.3333周期数,
所以,我们的函数有7个在一定范围内改变的参数:
p1 — 计算的价格 (收盘价,中间价,典型价,加权收盘价)
p2 — nFast (8:21)
p3 — nSlow(13:54)
p4 — nSig (3:13)
p5 — MAtypeMACD – MACD 字符串的MA类型
p6 — MatypeSig – Signal 字符串的MA类型
p7 — 百分比 (TRUE, FALSE)
p5,p6 = Cs(SMA, EMA, DEMA, ZLEMA).
交易信号可以通过不同方式产生:
选项 1
买入(Buy) = macd > signal
卖出(Sell) = macd < signal
选项 2
Buy = diff(macd) > 0
Sell = diff(macd) <= 0
选项 3
Buy = diff(macd) > 0 & macd > 0
Sell = diff(macd) < 0 & macd < 0
这是另外一个优化参数 signal(1:3).
另外,最终还有最后一个参数 — 优化历史的深度 len = 300:1000 (停止优化的柱数).
我们总共有9个参数需要优化,我有意增加了它们的数量,就是为了展示任何事物都可以用作参数 (图形,字符串,等等)。
优化标准 — К 点数的质量比 (在我的前一篇文章中已经详细介绍过)。
为了优化参数,我们需要找到一个适应性(目标)函数,从而计算质量标准并选择优化程序。让我们从程序开始,
我们将使用安全,快速,还有最重要的,经过多次测试的"rgenoud"功能包。它的主要限制是,所有的参数必须是整数或者物理的,这个限制可以轻易绕过。genoud()函数综合了进化搜索算法和基于派生的方法(牛顿或者类牛顿方法),来解决各种优化难题。Genoud() 可以用于解决派生物没有定义的优化问题。另外,使用集群选项, 该函数支持使用多个计算机,处理器和核心,以进行大规模并行计算。
genoud(fn, nvars, max = FALSE, pop.size = 1000, max.generations = 100, wait.generations = 10, hard.generation.limit = TRUE, starting.values = NULL, MemoryMatrix = TRUE, Domains = NULL, default.domains = 10, solution.tolerance = 0.001, gr = NULL, boundary.enforcement = 0, lexical = FALSE, gradient.check = TRUE, BFGS = TRUE, data.type.int = FALSE, hessian = FALSE, unif.seed = 812821, int.seed = 53058, print.level = 2, share.type = 0, instance.number = 0, output.path = "stdout", output.append = FALSE, project.path = NULL, P1 = 50, P2 = 50, P3 = 50, P4 = 50, P5 = 50, P6 = 50, P7 = 50, P8 = 50, P9 = 0, P9mix = NULL, BFGSburnin = 0, BFGSfn = NULL, BFGShelp = NULL, control = list(), optim.method = ifelse(boundary.enforcement < 2, "BFGS", "L-BFGS-B"), transform = FALSE, debug = FALSE, cluster = FALSE, balance = FALSE, ...)
参数
- fn – 最小化的目标函数 (或者如果 max = TRUE,就是最大化的). 此函数的第一个参数必须是一个向量,其中含有用于最小化的参数,函数应该返回标量(除非 lexical = TRUE)
- nvars – 将用于最小化函数的选择的参数的数量
- max = FALSE 最大化 (TRUE) 或最小化 (FALSE) 目标函数
- pop.size = 1000 种群的大小. 这是在解决优化问题中使用的物种数量,对这个数据有一些限制,尽管种群的数量是由用户指定的,这个数字会自动修正以保证符合相关的限制。这些限制来自一些GA算子的要求,专门来看的话,Р6 算子 (简单交叉) 和 Р8 (启发式交叉) 需要种群数量为偶数,也就是说,它们要求父母双方,所以,pop.size 变量必须是偶数,如果不是,种群就会增长以满足这些限制。
- max.generations = 100 — 最大代数,这是genoud在尝试优化功能时使用的最大世代数量,这是一个宽松的限制, genoud会运行最多的次数, 只有当hard.generation.limit设为TRUE时才会起作用, 否则当genoud必须停止时会使用两个软触发器: wait.generations 和 gradient.check,
即使max.generations变量默认下不会限制世代的数量,它也很重要,因为许多算子会使用它来调节它们的行为。实际上,许多算子会变得不那么随机,特别是世代的数量变得接近max.generations限制的时候,如果超出了这个限制,genoud还需要继续,它会自动增加max.generation的限制。
- wait.generations = 10. 如果目标函数在这个数量的世代后不再提高,genoud就将认为已经找到了最优值。如果启用了gradient.check触发器,genoud就会开始计算wait.generations,看是否solution.tolerance 等于0。其他用于管理结束的变量还有max.generations 和 hard.generation.limit.
- hard.generation.limit = TRUE. 这个逻辑变量决定了max.generations变量是否是genoud的强制限制,当hard.generation.limit 是 FALSE 的时候, 如果目标函数在任何代数中有提高(由wait.generations决定), 或者如果梯度(由gradient.check决定)不等于0,genoud 可以超出max.generations的数量。
- starting.values = NULL — 包含着genoud开始时将会使用的参数值的向量或者矩阵,通过使用这个选项, 用户可以在开始的种群中输入一个或者多个物种,如果使用了矩阵,数据列必须是参数和字串 — 物种,genoud 将会以随机顺序创建其他的物种。
- Domains = NULL . 这是 nvars *2 matrix. 对于第一列中的每个参数 — 底部边界, 第二列 — 顶部边界,genoud 初始种群中没有物种在生成时可以超出边界,但是如果没有启用boundary.enforcement标志,一些算子可能会生成超出边界的元素。
- 如果用户没有指定domains的数值,那么genoud 会通过default.domains来设置默认的domains值.
- default.domains = 10. 如果用户不想提供 domains 的矩阵, 也没有关系,domains 可以由用户简单设置这个标量选项,Genoud 将会创建 domain 矩阵,把所有参数的底部边界设为等于 (-1 )* default.domains, 而顶部边界设为等于 default.domains。
- solution.tolerance = 0.001. 这是genoud中使用的安全级别,数字间的差小于等于solution.tolerance,就认为是相等的。这在达到评估wait.generations 并进行 gradient.check时尤为重要。
- gr = NULL. 提供了 BFGS 优化器的梯度函数,如果等于 NULL, 就会使用数值梯度。
- boundary.enforcement = 0. 这个变量决定了genoud要达到搜索区域边界限制时的水平,不管这个变量的数值如何,没有物种的参数值会超出搜索区域的边界。
boundary.enforcement 有三个可能的数值: 0 (全部符合), 1 (部分限制), 以及 2 (不能超出边界):
0: 全部符合, 这个选项允许任何算子都能创建出超出搜索区域的物种,如果它们的适应度足够好,这些物种将包含在种群中,边界只是当随机生成物种时是重要的。
1: 部分限制它允许算子(特别是那些使用派生优化的, BFGS), 在创建物种时超出搜索边界,但是当算子选择物种时,它必须在合理边界之内。
2: 不能超出边界超出了搜索区域,就不用评估了。在这种情况下,边界的限制也适用于 BFGS 算法,它避免候选者超出由domains决定的边界。请注意,它使得可以使用 L-BFGS-B 优化算法,这个算法需要所有的合适的数值和梯度最终都进行评估,如果这引起了误差,则建议使用 BFGS 算法并使用 boundary.enforcement=1 设置。
- lexical = FALSE. 这个选项包含了词汇的优化,这是一个由几个标准的优化,他们决定顺序在适应度函数的顺序。这个选项使用的适应度函数必须返回的数值向量的适应度值的词汇顺序。这个选项可以是 FALSE, TRUE 或者等于由适应度函数返回的适合标准的数量。
- gradient.check = TRUE. 如果这个变量等于 TRUE, 那么 genoud 就不会计数 wait.generations, 知道每个梯度都接近solution.tolerance. 这个变量在超出了max.generations的限制,并且hard.generation.limit选项为 TRUE的时候就不起作用了。如果 BFGSburnin < 0, 它就被忽略, 如果 gradient.check = TRUE.
- BFGS = TRUE. 这个变量就会查询类牛顿派生优化器(BFGS),应该初始者之后在每一代的最优物种中加以应用,设为 FALSE 并不意味着不使用 BFGS,另外,如果你希望从不使用 BFGS, 必须重置 Р9 算子 (局部最小交叉)。
- data.type.int = FALSE. 这个选项设置优化函数的参数类型,如果变量为TRUE, 那么 genoud 将在优化参数时在证书范围内搜索方案,
使用整数型参数时,genoud不会使用派生信息,也就是说 BFGS 优化器不会被使用 — 也就是说, BFGS 标志设为 FALSE. 这也意味着 P9 算子(局部最小交叉)被重置, 梯度检查(检验标准)被禁止。即使设置了其他的选项, data.type.int 也具有更高的优先级 — 就是说, 如果 genoud 声明搜索应该是整数区域内的参数,梯度相关信息就不会被考虑在内。
没有选项能使得整数参数和浮点数参数一起使用。如果希望混合这两种类型,则可以表示一个整数参数,并且可以将整数范围转换为目标函数中的浮点数的范围。例如,您需要获取从 0.1 到 1.1的搜索范围,您就要指示 genoud 搜索从 10 到 110, 然后在适应度函数中把这个参数除以100。
- hessian = FALSE. 当这个标志被设为 TRUE时, genoud 在方案的返回列表中有部分 Hessian 矩阵,用户可以使用这个矩阵计算标准差。
- unif.seed = 812821. 它设置了伪随机生成器的种子,用于使用genoud时的浮点数,这个种子的默认值是 81282, genoud 使用它生成伪随机数(Tausworthe-Lewis-Payne 生成器),使得可以递归和平行调用genoud.
- int.seed = 53058. 它设置了整数生成器中的种子,也是在genoud中使用,种子的默认值是 53058. genoud 使用它作为内部伪随机数生成器 (Tausworthe-Lewis-Payne 生成器) 使得可以递归和并行调用 genoud.
- print.level = 2. 此变量管理genoud打印内容的级别,有四个可能的级别: 0 (最小打印), 1 (普通), 2 (详细) 和 3 (调试)。如果选择了 2, genoud就将在每个世代中打印种群的详细信息。
- share.type = 0. 如果share.type 等于 1, 那么 genoud 就将在开始检查项目文件是否存在 (参见 project.path),如果此文件存在,就使用它初始化输出的种群。这个选项可以在lexical中使用, 但是不能在 transform 选项中使用。
算子. Genoud 拥有并使用9个算子,这些算子都使用整数来编号(P1... P9). Genoud 计算它们的和 s = P1+P2 +... +P9. 每个算子都有权重, 等于W_n = s / (P_n)。算子的调用次数通常等于c_n = W_n * pop.size.
Р6 算子 (简单交叉) 和 Р8 (启发式交叉) 需要物种数量为偶数方能继续运行 — 换句话说它们需要父母双方,所以, pop.size变量和算子集必须确保这三个算子使用物种数量为偶数,如果不这样,genoud会自动增加种群以满足这个要求。
在算子中会强制检查唯一性,以保证算子生成的子女会与它们的父母不同,但也不总是这样。
genoud中使用的9个算子描述如下。
- P1 = 50 – 克隆克隆算子 简单地在当前世代重覆之最佳的测试方案 (独立于此算子之外, rgenoud会一直保存最佳测试方案的一个实例).
通用变异, 边界变异 和 异源变异 只影响测试的方案.
- P2 = 50 – 通用变异通用变异 改变测试方案的一个参数,把它变成随机值,然后把它传播到由此参数定义的域中。
- P3 = 50 – 边界变异边界变异把一个参数改成此域内的一个边界值。
- P4 = 50 – 异源变异异源变异在代数将要达到最大的时候,把一个参数减小到边界。
- P5 = 50 – 多平面交叉。多平面交叉(由单一搜索引发, Gill and other. 1981, p. 94–95), 计算测试解决方案,该解决方案具有与参数相同的测试解决方案的相同数量的凸性组合。
- P6 = 50 – 简单交叉。简单交叉通过在选择的点中把方案随机分开再交换,而从两个输入测试方案中计算两个测试方案。这个算子在测试参数有顺序时特别有效。
- P7 = 50 – 整数型异源变异整数型异源变异在测试方案中对所有参数进行异源变异。
- P8 = 50 – 启发式交叉启发式交叉把两个测试方案变成一个新的方案。
- P9 = 0 — 局部最小交叉: BFGS. 局部最小交叉 使用两步计算一个新的方案,首先 BFGS 执行初步定数的迭代开始从输入解决方案;然后,输入解凸组合计算,和BFGS迭代。
注意:
影响质量的最重要的选项是定义种群大小的 (pop.size) 和算法中的代数参数 (max.generations, wait.generations, hard.generation.limit and gradient.check). 搜索的效率,与期待的一样,如果种群的大小,和代数的增加将会提高。这些以及其他选项在解决各种问题时要人工修改,请多加注意搜索区域(Domains 和 default.domains),
参数中线性与非线性的限制可能会在它们的适应度函数中出现,例如,如果参数1和2的和小于 725, 那么条件就隐含在适应度函数中, 用户将最大化 genoud, : if((parm1 + parm2)>= 725) {return (-99999999)}. 在这个例子中,如果违反了线性约束,不好的适应度数值将会返回到genoud,而genoud 会尝试找到其他符合约束的参数数值。
我们将要写我们的适应度函数,它应该能够计算:
MACD
signals(信号)
quality rate(质量分数)
# 适应度函数-------------------------fitness <- function(param, test = FALSE){ require(TTR) require(magrittr) # 定义变量 x <- pr[param[1]] nFast <- param[2] nSlow <- param[3] nSig <- param[4] macdType <- MaType[param[5]] sigType <- MaType[param[6]] percent <- per[param[7]] len <- param[9]*100 # macd的线性限制 if (nSlow <= nFast) return(-Inf) # 计算 macd md <- MACD(x = x, nFast = nFast, nSlow = nSlow, nSig = nSig, percent = TRUE, maType = list(list(macdType), list(macdType), list(sigType))) # 计算 signals 并右移 1 个柱 sig <- signal(md, param[8]) %>% Lag() #使用 len 长度计算历史余额 bal <- cumsum(tail(sig, len) * tail(price[ ,'CO'], len)) if(test) {bal <<- cumsum(tail(sig, len) * tail(price[ ,'CO'], len))} # 计算质量分数 (转换为整数) K <- ((tail(bal,1)/length(bal))* 10 ^ Dig) %>% floor() # 返回取得的优化标准 return(unname(K)) }
以下是所有变量和函数计算的列表
require(Hmisc) # 平均的类型 = 4 ------------------------------------------- MaType <- Cs(SMA, EMA, DEMA, ZLEMA) require(dplyr) # 价格类型 = 4 ----------------------------------------------- pr <- transmute(as.data.frame(price), Close = Close, Med = Med, Typ = (High + Low + Close)/3, WClose = (High + Low + 2*Close)/4) # 如何计算? per <- c(TRUE, FALSE) # 信号类型 = 3 -------------------------- signal <- function(x, type){ x <- na.omit(x) dx <- diff(x[ ,1]) %>% na.omit() x <- tail(x, length(dx)) switch(type, (x[ ,1] - x[ ,2]) %>% sign(), sign(dx), ifelse(sign(dx) == 1 & sign(x[ ,1]) == 1, 1, ifelse(sign(dx) == -1 & sign(x[ ,1]) == -1,-1, 0)) ) } # 初始配置--------------------------- par <- c(2, 12, 26, 9, 2, 1, 1, 3, 5) # 搜索区域-------------------------------------- dom <- matrix(c(1, 4, # 用于价格类型 8, 21, # 快速MA周期数 13, 54, # 慢速MA周期数 3, 13, # signal MA 周期数 1, 4, # 快速和慢速MA类型 1, 4, # 信号 MA 类型 1, 2, # 百分比类型 1, 3, # 信号选项 3,10), # 历史长度 [300:1000] ncol = 2, byrow = TRUE) # 创建用于处理核心的集群 puskCluster<-function(){ library(doParallel) library(foreach) cores<-detectCores() cl<-makePSOCKcluster(cores) registerDoParallel(cl) #clusterSetRNGStream(cl) return(cl) }
使用初始(通常是默认)参数定义质量分数
> K <- fitnes(par, test = TRUE) > K [1] 0 > plot(bal, t="l")
图1 默认参数的余额
结果很糟。
为了比较计算速度,我们将在一个核上进行优化,然后再在双核的集群上进行。
单核:
pr.max <- genoud(fitnes, nvars = 9, max = TRUE, pop.size = 500, max.generation = 300, wait.generation = 50, hard.generation.limit = FALSE, starting.values = par, Domains = dom, boundary.enforcement = 1, data.type.int = TRUE, solution.tolerance = 0.01, cluster = FALSE, print.level = 2) 'wait.generations' limit reached. No significant improvement in 50 generations. Solution Fitness Value: 1.600000e+01 Parameters at the Solution: X[ 1] : 1.000000e+00 X[ 2] : 1.400000e+01 X[ 3] : 2.600000e+01 X[ 4] : 8.000000e+00 X[ 5] : 4.000000e+00 X[ 6] : 1.000000e+00 X[ 7] : 1.000000e+00 X[ 8] : 1.000000e+00 X[ 9] : 4.000000e+00 Solution Found Generation 5 Number of Generations Run 56 Thu Mar 24 13:06:29 2016 Total run time : 0 hours 8 minutes and 13 seconds
优化的参数 (基因型)
> pr.max$par [1] 1 14 26 8 4 1 1 1 4
我们来解码 (表现型):
- price type pr[ ,1]= Close
- nFast = 14
- nSlow = 26
- nSig = 8
- macdType = ZLEMA
- sigType = SMA
- percent = TRUE
- signal = macd 与信号线的交叉
- 历史长度 = 400 个柱
让我们看一下使用优化参数的余额线。为此我们将使用这些参数来运行适应度函数,并且设置 test = TRUE 选项。
> K.opt <- fitnes(pr.max$par, test = TRUE) > K.opt [1] 16 > plot(bal, t="l")
图2. 优化参数的余额
这是可以接受的结果了,EA交易可以使用了。
我们将在双核组成的集群中进行同样的计算。
# 开始集群 cl <- puskCluster() # 最大化适应度函数 # 把需要的变量和函数发送到集群中的每个核 clusterExport(cl, list("price", "pr", "MaType", "par", "dom", "signal", "fitnes", "Lag", "Dig", "per" ) ) pr.max <- genoud(fitnes, nvars = 9, max = TRUE, pop.size = 500, max.generation = 300, wait.generation = 50, hard.generation.limit = FALSE, starting.values = par, Domains = dom, boundary.enforcement = 1, data.type.int = TRUE, solution.tolerance = 0.01, cluster = cl, print.level = 2) # only for experiments. # 在 EA 中设置0 # 停止集群 stopCluster(cl) 'wait.generations' limit reached. No significant improvement in 50 generations. Solution Fitness Value: 1.300000e+01 Parameters at the Solution: X[ 1] : 1.000000e+00 X[ 2] : 1.900000e+01 X[ 3] : 2.000000e+01 X[ 4] : 3.000000e+00 X[ 5] : 1.000000e+00 X[ 6] : 2.000000e+00 X[ 7] : 1.000000e+00 X[ 8] : 2.000000e+00 X[ 9] : 4.000000e+00 Solution Found Generation 10 Number of Generations Run 61 Thu Mar 24 13:40:08 2016 Total run time : 0 hours 3 minutes and 34 seconds
花费时间看起来好很多,但是质量有少许下降。为了解决如此简单的一个任务,"调整"参数也是很重要的。
我们将计算最简单的选项
pr.max <- genoud(fitnes, nvars = 9, max = TRUE, pop.size = 500, max.generation = 100, wait.generation = 10, hard.generation.limit = TRUE, starting.values = par, Domains = dom, boundary.enforcement = 0, data.type.int = TRUE, solution.tolerance = 0.01, cluster = FALSE, print.level = 2) 'wait.generations' limit reached. No significant improvement in 10 generations. Solution Fitness Value: 1.500000e+01 Parameters at the Solution: X[ 1] : 3.000000e+00 X[ 2] : 1.100000e+01 X[ 3] : 1.300000e+01 X[ 4] : 3.000000e+00 X[ 5] : 1.000000e+00 X[ 6] : 3.000000e+00 X[ 7] : 2.000000e+00 X[ 8] : 1.000000e+00 X[ 9] : 4.000000e+00 Solution Found Generation 3 Number of Generations Run 14 Thu Mar 24 13:54:06 2016 Total run time : 0 hours 2 minutes and 32 seconds
这显示出一个不错的结果,那么余额怎么样呢?
> k [1] 15 > plot(bal, t="l")
图3. 优化参数的余额
在合理时间内得到的非常好的结果。
让我们进行几个实验来比较遗传算法与进化算法的结果。首先,我们将测试SOMA(自组织迁移算法,Self-Organising Migrating Algorithm),它在"soma"功能包中实现。
随机优化的自组织迁移算法 — 与遗传算法类似,尽管它是基于"迁移"系列的概念,并且使用的是固定集合的物种, 而不会进一步生成新的世代。它不会得到局部极值,并且可以用于以最小的代价在有限参数范围内取得结果的任何任务。主函数:
soma(costFunction, bounds, options = list(), strategy = "all2one", …)
参数
costFunction |
|
bounds |
|
options |
|
strategy |
|
... |
costFunction 的其他参数 |
详细内容
对于优化的设置和结束的标准还有多个选项,这里使用的是由作者 Zelinka (2004) 推荐的默认值.
- pathLength: 物种与迁移目标之间的距离。数值 1 对应着最领先的位置,大于1的值(推荐值)是控制过的,默认值为 3。
- stepLength: 评估可能的步数时使用的最小步长,推荐不要使用能使用距离整除得到的数值,默认值为 0.11.
- perturbationChance: 在任何阶段所选的参数发生改变的概率,默认值是 0.1.
- minAbsoluteSep: 价格函数最大与最小值之间的最小绝对差距,如果差距小于最小值,算法就结束。默认值是 0. 意思是永远不会满足终止条件。
- MinRelativeSep: 价格函数最大与最小值之间的最小相对差距,如果差距小于最小值,算法就结束。默认值是 0.001.
- nMigrations: 终止前的最大迁移数,默认值是 20.
- populationSize: 种群中的物种数量,推荐的这个数的值比优化参数数量大一些,不应该小于2,默认值是 10.
因为该算法只进行最小化,我们将回顾我们的适应性函数,这样它可以提供相反的符号而开始优化。
require(soma) x <- soma(fitnes, bounds = list(min=c(1,8,13,3,1,1,1,1,3), max = c(4,21,54,13,4,4,2,3,10)), options = list(minAbsoluteSep = 3, minRelativeSep = -1, nMigrations = 20, populationSize = 20), opp = TRUE) Output level is not set; defaulting to "Info" * INFO: Starting SOMA optimisation * INFO: Relative cost separation (-2.14) is below threshold (-1) - stopping * INFO: Leader is #7, with cost -11
最佳参数:
> x$population[ ,7] [1] 1.532332 15.391757 37.348099 9.860676 1.918848 [6] 2.222211 1.002087 1.182209 3.288627 Round to > x$population[ ,7]%>% floor [1] 1 15 37 9 1 2 1 1 3
适应性函数的最佳值 = 11. 这对实际应用是可以接受的,但是有提升的空间。
这个算法很快,但是结果不稳定,需要更好的调整。
通用模拟退火函数
这个算法是在«GenSA”功能包中实现的,这个函数可以进行全局最小值的搜索,使用的是复杂的非线性目标函数以及大量的优化,
GenSA(par, fn, lower, upper, control=list(), …)
参数:
- lower – 长度为length(par)的向量,组件底部的边界。
- upper — 长度为length(par)的向量,组件顶部的边界。
- … 使得用户可以发送fn 函数的其他参数。
- control — 控制参数,这是一个可以用于管理算法行为的列表。
- maxit – 整数,算法的最大迭代数。
- smooth — 逻辑值. TRUE, 当函数是平滑的或者区域内的参数分布平均,否则为FALSE. 默认值 — TRUE
- temperature — 数字值. 温度的初始值。
- trace.mat — 逻辑值. 默认是TRUE它的意思是在GenSA调用的返回值中有可用的跟踪矩阵。
对于一个复杂的优化任务,控制组件的数值使用默认值设定。对于一个通常的,平均复杂程度的优化任务,GenSA 可以较快地找到合理的方案,所以建议用户让 GenSA 早一点结束:
通过设置 threshold.stop, 如果 threshold.stop 是所期待的函数值;
或者根据max.time来终止, 如果用户只是简单地希望把 GenSA 运行max.time秒;
或者通过设置max.call, 如果用户只是简单地希望运行 GenSA,使它调用max.call次函数。
对于很复杂的优化任务,用户应该加大maxit和temperature.
让我们通过限制最大运行时间为60秒来运行优化。
require(GenSA) pr.max <- GenSA(par, fitnes, lower = c(1,8,13,3,1,1,1,1,3), upper = c(4,21,54,13,4,4,2,3,10), control = list(verbose = TRUE, simple.function = TRUE, max.time = 60), opp = TRUE)
适应度函数的值和优化的参数值:
> pr.max$value * (-1) [1] 16 > par1 <- pr.max$par > par1 [1] 1.789901 14.992866 43.854988 5.714345 1.843307 [6] 1.979723 1.324855 2.639683 3.166084
四舍五入:
> par1 <- pr.max$par %>% floor [1] 1 14 43 5 1 1 1 2 3
使用这些参数来计算适应度函数的值,可以看到余额线:
> f1 <- fitnes(par1, test = TRUE) > plot(-1 * bal, t="l")
图4 余额 4
质量指标 — 在一定的较好水平上, 计算出乎意料的快。
许多类似的算法(dfoptim, nlopt,CEoptim, DEoptim,RcppDE 功能包,等等)通过某个标准优化了函数,对于多个标准的优化,则更加倾向于使用mco功能包。
7. 提高质量特性的方法
我们进行的实验展示了遗传算法的效率,为了进一步提高指标的质量,我们推荐使用应用程序进行更多的探索:
- 多标准优化. 例如,对质量分数和最大回撤进行优化,"mco"封包就实现了这样的功能,
- 尝试实现一个动态自组织GA参数,这个包是可能实现的 — "GA". 它提供了大范围的算子,用于选择,交叉和变异,
- 用于在交易系统中应用遗传编程进行测试。
结论
我们已经探讨了在进化算法中的基本原则,它们的不同类型和特性,使用一个简单的 MACDSample EA交易,我们已经在实验中演示了参数优化的应用,即使在这样基本的交易应用中也有好的效果,
进行优化的时间和编程中的简单性使得可以不进入市场就能在EA的运行中进行,对优化参数的类型不做严格限制也使得可以在EA运行的不同阶段进行各种类型的优化,
最重要的工作部分是正确写出适应度函数。
我希望本文会帮您明白这并不困难,所以您可以尝试自己在您的EA交易中实现优化。
本文由MetaQuotes Ltd译自俄文
原文地址: https://www.mql5.com/ru/articles/2225