首先
这份实现非常匆忙，能够使用了就没有再进一步改造。一些地方还有很大的改进空间。
例如，这里可能需要对魔兽世界APL形式化的研究。运用例如命题逻辑等理论工具，将APL化成某种“范式”，在进行模拟之前就将等价APL识别出来，会更有利于此算法的实际使用。目前这份实现中，种群单一化非常严重，大多数时候，现有最优解与次优解及它们的等价APL占领整个种群；没有了多样性，就失去了进化的原材料。

WoW的DPS问题及其理论，可以归结为两个部分：硬件构建和战斗策略。 其中硬件构建类问题大多比较简单，偶有像5.4猎人属性收益峰值这样的复杂的问题，llxibo引入爬山法，将其漂亮地解决了(5.4野兽控制属性收益峰值分析)。可以说这一部分已经充分得解。

战斗策略问题的核心就是APL。与前一类问题不同，长期以来，APL是依靠人工探索的。数理研究者利用一些理论工具(例如战士用的双限制分析，猎人用的块模型)，依据个人的理解，来建立并优化APL。
用机器自动化优化APL的想法初步来自于我与黑锋要塞的那次争论。一位版主指出要我写出脓疮邪的APL，试图以此让我闭嘴。在那之后，我和黑锋区几位大师都有对脓疮邪APL的探索，因为逻辑繁杂，条件中还有许多数值需要确定，我此时产生了用机器自动化处理APL的想法。

在我的一篇小日记当中，我提到了APL自动化生成的愿景。实际上，希望做到自动化生成APL的远不止我一个人——llxibo曾做过尝试，使用SimC作为模拟器，用一个启发式、完全的宽度优先搜索来进行APL的优化。我们简单讨论过一点相关内容，这次尝试催生了试水的LuaCL，因为以SimC的低效率，爬山或许仍可忍受，而对一个解空间无穷无尽的APL问题进行搜索，SimC就太慢了。
现在，运用LuaCL现有的雏形作为模拟器，我将遗传算法引入APL问题，成功解决了自动化生成APL的难题。

我在这个模拟器中写入了简化的猝死-一心狂暴战的模型，并且进行了验证。这个模拟器采用OpenCL 1.1标准，能够运行于绝大多数异构计算设备，包括CPU、GPU、MIC乃至FPGA。虽然它只是一个雏形，功能尚不完备，性能也有待调优，但是它已经展现出百倍于SimC的计算速度。在我的机器上(一颗1.06G双核的Westmere)，它能够在2～4秒内完成50000次×平均450秒的模拟。它必将会在未来广泛应用的遗传法和爬山法中大放异彩。

概述
遗传算法是常见的全局优化算法中的一种，提出于1960年代，用来解决那些难以用传统方法建立模型的问题。它是人类向大自然学习的典范，模仿“适者生存”的思想，模仿生物学中染色体的遗传和变异，遗传算法将现有解中优良的信息遗传给下一代解，逐代演化逼近全局最优。从本质上来说，遗传算法属于启发式的、不完全的宽度优先搜索。
本次实验的完整实现可以在[https://github.com/AeanSR/aplga]访问。
由于模拟器不同，APL的词法语法形式也与SimC不同，但我会给出自然语言的解释。
 
下面给出SimC为猝死-一心狂暴战预设的APL，并将它翻译成我们所用的APL语法。它在我们使用的模拟器中，得到的DPS为20029.486。这将是我们期望达到的DPS，如果自动化生成的APL能够超过此APL，我们可以认为生成是成功的。
Code (c):
/* 非斩杀，怒气达到110以上，使用狂风打击 */ 
if(power_check(rti, 110)&&enemy_health_percent(rti)>=20.0f)SPELL(wildstrike); 
/* 未激怒，或者怒气不足80，使用嗜血 */ 
if(!(UP(enrage.expire)&&power_check(rti, 80)))SPELL(bloodthirst); 
/* 猝死触发，使用斩杀 */ 
if(UP(sudden_death.expire))SPELL(execute); 
/* 血涌触发，使用狂风打击 */ 
if(rti->player.bloodsurge.stack>=1)SPELL(wildstrike); 
/* 激怒下使用斩杀 */ 
if(UP(enrage.expire))SPELL(execute); 
/* 怒击 */ 
SPELL(ragingblow); 
/* 非斩杀，激怒下，使用狂风打击 */ 
if(UP(enrage.expire)&&enemy_health_percent(rti)>=20.0f)SPELL(wildstrike); 
/* 嗜血 */ 
SPELL(bloodthirst);
 
基本操作
要理解遗传算法，首先需要理解两个关键操作：交叉和变异。它们与染色体交叉和变异的概念是一致的。
APL由两部分组成：一部分是动作列表，表述不同动作之间的优先关系；一部分是条件，表示每个动作执行所需满足的附加条件。首先来看条件，图1用树的形状描述了一个典型的条件(!A || (B && C))。  
首先来看交叉。交叉是在两个不同的个体间进行的，它们各自取下自己的一部分，与对方互换。以上面的条件为例，此时，有另一棵较为简单的条件树，它只包含一项“条件D”。这两棵条件树要进行交叉。  
简单的条件将自己仅有的一个组件拿出来交换，复杂的条件则有可能拿出自己的一个子树。互换后，可能会产生这样的两棵条件树。  
仍然以上面举例的图1中条件为例，变异则是在一个个体内部完成的，变异将个体中的组成成分进行重排、修改、增加或删除等操作将旧个体改变为一个新的个体。例如图4使用额外的“与”节点，将条件D添加到了整个条件树中，完成了一次添加变异。  
因为条件具有树形结构，交叉和变异操作可能比较复杂。动作列表则简单得多，因为它是链式结构的。例如一个动作列表a1-a2-a3-a4，执行一次修改变异则可能产生a1-a5-a3-a4；动作列表a1-a2-a3-a4与另一动作列表b1-b2-b3-b4进行交叉，则可能产生a1-a2-b3-b4和b1-b2-a3-a4两个新的动作列表。
 
对整个APL进行交叉和变异，则是对它们的动作列表和条件分别进行交叉和变异。
 
遗传算法的总体结构可以表述如下：
1.随机产生一个初始种群，其中包含N个个体
2.从N个个体中随机抽取少量个体，进行交叉、变异，产生M个新个体。此时种群数量为N+M
3.对整个种群进行适应性评价，得到每个个体的适应度
4.将适应度最差的M个个体淘汰。此时种群数量回到N
5.重新进行2～5，直至充分进化为止
 
对APL问题而言，适应性评价采用的评价函数，就是模拟器。

一些实现细节
为了防止重复计算，有必要引入重复检测技术。如果一个个体已经被评价过，那么它有两种可能的状态：已经被淘汰，或者仍在种群中。将一个已被淘汰的个体重新加入种群，会导致演化的倒退；将一个已经在种群中的个体重复加入种群中，会导致种群的多样性下降。这些都不是我们期望的，所以，只要发现一个新个体曾在之前的计算中被评价过，就可以有充分的理由直接丢弃它了。
这里，检测重复的技术简单地采用了对APL字符串的Hash。
 
另外，还有必要引入对APL复杂度的控制。复杂的APL能表述更多的信息，当然也就容易达到简洁的APL无法达到的DPS高度。如果不加以控制，种群进化会趋于复杂化，最后得到让人类难以理解的超级复杂的APL，其中会包含大量冗余的、可被化简掉的内容。
这里，对复杂度的控制表现在两个方面。首先，发生变异时，增性变异和删性变异的几率不是相等的，而是与复杂度有关。使用一个正态分布的随机数对增性变异和删性变异进行控制，使得复杂度越高，变异越趋于删减；复杂度越低，变异越趋于增添。
另外，在种群进行选择淘汰时，不仅仅按照DPS进行，在DPS相等(等价APL之间)采用复杂度作为第二优先级的适应度指标，让等价APL当中简洁者生存，复杂者淘汰。
这样，种群进化过程将会有对自身进行化简的趋向。化简过后的APL包含的有用信息更稠密，也有助于提高进化的速度。
 
模拟器得到的DPS不是固定的，而是按照一个较小的方差围绕均值上下波动的。在评价中得到的DPS比实际均值高的那些个体，可能会获得不正当的竞争优势，排挤那些在随机性中失利的更优的解。为了让方差的影响消失，我将模拟器的RNG种子值固定，这样等价APL将得到完全相等的DPS，它们之间的竞争将按照复杂度来进行。

实验结果
实验仍在进行，目前得到的结果已经达到20084.039的DPS，超过了作为对比的SimC预设20029.486。
目前得到的最优APL为：
Code (c):
/* 怒击、血涌、猝死三项全部触发，使用斩杀 */ 
if((rti->player.ragingblow.stack>=1&& 
    (rti->player.bloodsurge.stack>=1&&UP(sudden_death.expire)))) 
    SPELL(execute); 
/* 怒击和血涌两项触发，使用狂风打击 */ 
if((rti->player.ragingblow.stack>=1&& 
    (rti->player.ragingblow.stack>=1&&rti->player.bloodsurge.stack>=1))) 
    SPELL(wildstrike); 
/* 有怒击，激怒不足4.5秒或有血涌，使用嗜血 */ 
if((rti->player.ragingblow.stack>=1&&rti->player.bloodsurge.stack>=1)) 
    SPELL(bloodthirst); 
if((rti->player.ragingblow.stack>=1&&REMAIN(enrage.expire)<=FROM_SECONDS(4.5))) 
    SPELL(bloodthirst); 
/* 无意义项 */ 
if(REMAIN(bloodthirst.cd)>=FROM_SECONDS(1))SPELL(bloodthirst); 
/* 嗜血冷却剩余1秒以上，使用斩杀 */ 
if(REMAIN(bloodthirst.cd)>=FROM_SECONDS(1))SPELL(execute); 
/* 怒气超过90，使用斩杀 */ 
if(power_check(rti,90))SPELL(execute); 
/* 嗜血 */ 
SPELL(bloodthirst); 
/* 没有血涌，使用怒击 */ 
if((rti->player.bloodsurge.stack==0||rti->player.bloodsurge.stack==0))SPELL(ragingblow); 
/* 嗜血冷却剩余0.5秒以上，使用狂风 */ 
if(REMAIN(bloodthirst.cd)>=FROM_SECONDS(0.5))SPELL(wildstrike); 
/* 使用怒击 */ 
SPELL(ragingblow);
 
到目前为止程序已经执行了约一天时间。图5是程序记录的收敛速度信息，横轴单位为代。黑色粗横线表示SimC对照DPS水平，红色表示种群中最大值，绿色表示种群中最小值。可以看到在54代时，SimC对照就已经被超越了。