189 8069 5689
1. 工具产生的背景
导航对人们的生活起着越来越重要的作用，由于公司一直在做导航产品，所以为了从深度上保证产品的质量（已经通过大量的case从广度上来保证产品质量），做为Routing的测试负责人，我对导航算法进行了深入的研究。
在做Map Data的Regression时，我们是基于导航对底层的数据进行测试，而MapData是经过Tools Team 转换的，所以原始数据的改动、Tools的改动都会引起导航的变化，而这两层对从上层测试的我们来说都是blackbox。测试时，用自动化工具找出difference很容易，但check起来相当困难，因为我们不光需要知道路线变了，而且需要知道它是怎么变的，否则你不知道你的模型是不断优化的。当时一天也就check十几条路线变化的case，对于五六千条case的一轮Regression，测试工作量是呈指数增长的，已经不是增加一两个人就能解决问题的。
导航，本身就是机器学习的过程，所以用传统的功能测试抽取case覆盖各个feature的方法在这种情况下不是完全适用：一是因为一条规划的路线会涉及到几百、甚至上万条link，每条link又有多个影响因子，如果有一个或几个因子变化，都可能引起导航路径的变化，更何况是这么多个可变因子，而且以前设计的覆盖Feature的case，可能会因为数据变了就cover不到了；二是因为机器学习本身就是通过大量的数据，对原型不断进行训练、不断优化的过程，所以减少case进行测试，很可能会使模型陷入局部最优。所以作为数学系的我，认为机器学习的原型用机器学习的方法测试才是最好的解决方案，于是想到了神经网络。
在这个时期饱受折磨的不光是我们team的QA，ToolsTeam的dev也被要求用我们的Regression工具check case，要知道他们对导航的逻辑不了解，check起来难度多大（即使知道导航变了，但为什么变，你得知道）。这使我深刻意识到自动化工具的思想，比自动化工具的开发要重要得多，Tools Team的lead曾经说过一句话：只要你有想法，我们就能把工具做出来。所以经过大概两周的折磨，在凌晨四点的睡梦中终于有了solution，而不是idea，当时那叫一个兴奋啊JJ
第二天，跟mgr讨论了之后，他同意了我的solution，于是找到ToolsTeam的一个牛人，仅用了几天时间，就把工具生成出来了。
2. 人工神经网络ANN (Artificial Neural Network)
主要类型：
· 前向神经网络
· 反馈网络
· 自组织网络
· 相互结合型网络
为了使模型相对简单、准确，我们采用三层前向神经网络（即含一个隐含层）
3. 实现的思想
· 抽取difference
采用第三方工具(diff.exe)将新旧地图的difference进行对比（类似Beyond Compare的功能）并且输出。
· 使用神经网络模型
输入层：diff.exe的output。
隐含层：内部处理逻辑
输出层：分类的结果和变化的cost
输入层到隐含层的权重：w(ih)
隐含层到输出层的权重：w(ho)
· 实现分类
根据feature 进行分类，通过config.xml手动配置来定义分类的优先级：
· 计算从输入层到隐含层的权重w(ih)
将priority 转换成 [0, 1]之间的数（当时就卡在了这个转换过程上，想到了神经网络，但就是不知道怎么将现有的输入和期望的输出转换成数学模型）：
F1 = (1/2)^1
F2= (1/2)^2
F3 =(1/2)^3
F4 = (1/2)^4
F5 =(1/2)^5
F6 = (1/2)^6
F7=(1/2)^7
…
Notes:
1） Fn:代表第n个feature
2） 根据等比数列1/2^n给每个分类因素定义权重，这样做的目的是为了使每个weight最后加起来的值无限接近但<1，即使所有的expectedresult全变化了，大值不会超过1
3）分类的顺序可以根据每次的改动调整
4）Config.xml的格式可修改为：
…
因此每个分类的weight=(1/2)^value
（对于不需要check的difference，不用计算，value设为0）
4. 定义隐含层到输出层的权重w(ho)：
对于每个feature，可能不止一处发生变化，根据经验，设置可能变化的大个数（config.xml里配置，可手动修改）
Config.xml可定义为
…
· 由于之前把主要的精力放到了check路线变化的case上，既慢又发现不了什么问题，后来经过经验和简单利用了下统计的原理，证明了引起长路径的变化的主要因子是路的等级和速度（通常这两个因子会引起一些列link都变），所以根据路线变化的段数计算cost，而非长路径导航。
· 这里比较麻烦的地方是Maneuver，因为每个Maneuver的提示（左转、右转、上高速等等）还有另外一整套逻辑，是分类工具比较复杂的地方。
· 权重的计算思想为：通过对Tools调研，知道Tools对哪些属性进行了处理（因为Tools的复杂度较高，了解详细的逻辑cost非常大，所以只是通过代码复杂度和逻辑复杂度知道个大概的情况）。根据line by line的读导航的 code，知道Maneuver的产生条件，并计算出Tools处理过的属性占每个maneuver的cost；根据Tools的代码复杂度和逻辑复杂度（复杂度越高，bug可能越多）以及客户（Customer bug is very important）报的bug类型，计算出每类maneuver的cost, 根据这两个cost，计算出Tools的影响和客户发现的bug占每个maneuver的cost；最后进行归一化处理。即：从导航的逻辑、客户、Tools的改动，以及最后的表现形式上计算cost。
· config.xml可定义为：
…
5. 计算从输入层到输出层的cost：
· F1: cost = w(ih)(F1)*(1/2+n*w(ho)(F1))=(1/2)^1*(1/2+1/2*n*1/5)
· F2: cost = w(ih)(F2)*(1/2+each w(ho)(F2))=(1/2)^2*(1/2+ 1/2*each maneuver weightfrom hidden layer to output layer)
· F3: cost = w(ih)(F3)*(1/2+n*w(ho)(F3))=(1/2)^3*(1/2+1/2*n*1/10)
· F4: cost = w(ih)( F4)*(1/2+n*w(ho)( F4))=(1/2)^4*(1/2+1/2*n*1/3)
· Fm: cost = w(ih)( Fm)*(1/2+n*w(ho)( Fm))=(1/2)^9*(1/2+1/2*n*1/30)
(n 代表每类feature的变化数量)
Notes:
1） 由此可见，F1的取值范围应该是[1/4, 1/2],F2的取值范围是[1/8, 1/4], F3的取值范围是[1/16, 1/8], …
2） 由于一条case里，可能既含有F1的，又含有F2, 所以F1的权重应该在[1/4,1],同理类推F2分类里权重的总和应该在[1/8, 1/2],,…（在已经正确分类的基础上，即使F2的cost比F1的大，也不会影响case的选取）
6. 用聚类分析方法根据最终的cost大小抽取指定数量的case。
7. 优点：
1. 在不减少Test Scope的情况下，可以合理的抽取case；在有限的时间内，check变化大的case。
2. 通过了解Tools的改动，手动配置测试范围和优先级，来保证产品质量。
3. 由于人工check结果时会把difference里的所有变化全check，所以此工具也是在模拟人的操作。
8. 缺点：
1．由于Case的output是基于Maneuver的，而非Routing，所以计算时存在分类错误，但考虑到改动开发的code cost比较高，只能根据现有的结果和经验进行优化。
2．神经网络本身可能陷入局部最优，所以即使权重调整再大，期望结果也可能会很小。