牌型选择和其它问题的差异性分析
蚁群算法是由仿生蚂蚁寻食发展而来，所以其很自然的就以寻找最短路径的旅行家问题为研究对象。而旅行家问题有几个特点：
-
每一步都是从当前所在城市的所有邻接城市中挑选下一步的目标城市
-
算法的判优指标（即解评分）是总距离最短
-
单步择优的启发性信息是两邻接城市之间的路径长度
-
信息素就是本轮次最优解的路径总长度/路径中的城市数
对照我们的牌型选择问题，就存在一定的差异了：
-
牌型选择的每一步是从当前牌点（如2）目前所有可以组成的牌手中挑选，如对2、三张9带对2、23456789等等
-
算法的判优指标（即解评分）是各牌型累加调整后的剩余牌手数，越小越好
-
单步择优的启发性信息是当前牌点可组成的牌手的牌力估计（概率不能为负数，所以是剩余牌手数的一个变换，一般只要能大致反映不同选择的价值即可）
-
信息素是每轮次最优解评分/解的牌手数
我们在上一讲中谈到了我们在构思如何解决问题时，首先要完成在想象世界中的问题转换。所以我提出了用剩余牌手数这个自造的概念来衡量各牌手的价值。而更宏观的，我们也要对牌型选择问题进行转换，通过上面的对比，我们可以看出牌型选择问题和旅行家问题是截然不同的（即解的构造方式完全不同），那我们该用什么样的模型来构思牌型选择问题的解决方案呢？！
为了在遇到问题时我们能快速的构思出有效的解决方案，我们需要广泛的学习，以积累自己的见闻。这样当遇到新问题时，就能找到比较接近的参考问题，然后参照参考问题的解决办法来拟定自己的解决办法。如果大家对一些经典的计算机算法求解问题有所了解，那么就会看出来，我们的牌型选择问题其实比较类似多重背包问题。在有了这个观察之后，我们可以翻开书，看看如何用蚁群算法来解决多重背包问题的，这样来构思我们的实现就会少走很多的弯路，大幅提高了自己解决问题的效率
确定了参照多重背包模型来解决牌型选择问题，那么显然首先要把我们手中的牌所能组成的牌手全部找出，比如A234567的顺子包括了：A2345、A23456、A234567、23456、234567、34567，我们前次所举的A23456789包括的可能牌手就更多了。而三带二的组合也会非常可观，这样一来，每个牌点可能的牌手数量会非常多，而由于我们每次挑选牌手采用的是加权概率的方式，所以为了保证结果的有效，我们生成的蚂蚁数量不能太少，否则可能会导致由于每个牌点对应的牌手数量太多，蚂蚁难以覆盖到，而导致算法给出的解的质量难以满意。
这里的加权概率需要同时结合启发性知识和全局信息素。其中，启发性知识指出了优化方向，而全局信息素则保留了对之前探索质量的记忆，这两者的结合就是之前讨论过的蚁群算法的威力所在！
同时，如果当前牌点是2而蚂蚁最终挑选了A23456789，那么其实就是A、2、3、4、5、6、7、8、9这九个牌点同时挑选了A23456789的牌手，这和旅行家问题、背包问题都有着不同。
此外，如果我们有3张2，那么就2来说，2这个牌点同时关联了A23456789和对2两个牌手，这也是和其它问题的巨大不同之处。
这些不同我们需要高度关注：我们需要深入思考这是否会影响到蚁群算法的执行，并验证这些差异的影响。这是由于任何算法都有其应用前提和假设，我们需要理解并满足这些前提和假设，而差异点正是检验是否满足的关键点。
牌手的可满足性检查
当我们选择了某个牌手后就应对该牌手所涉及到的所有牌点进行提取或标记，而当对新的牌点进行挑选时，是给出在剩余的牌点中可组成的牌手。比如，2可以组成A23456789或3张2，如果我们确定组成3张2，那么我们就需要将这三张2标记为已选，这样，当后面某步的当前牌点是A时，由于2已经都被用掉了，所以A无法再组成A23456789的牌手，而只能组成单张A的牌手。
随着一个个牌手的挑出，后继牌手的选择空间越来越小。因此，为了避免固定顺序挑选牌手导致解质量太差，我们在每一次挑选牌点时，都应是从现有牌点中随机挑选。而这又和寻找最短路径的从特定的起点一步步找到特定终点是截然不同的。
初始牌型的确定
蚁群算法本意是先生成一个蚂蚁，让它在一无所知的情况下爬出一个初始结构，然后用这个初始结构的评分来生成初始信息素数据。但通过前面的讲解，我们可以看出蚁群算法其实是围绕着局部优胜解探索出局部最优解，因此对于很多问题，初始解会影响蚁群算法求解的效率和质量，所以一般都是特别的精心构造一个高质量的初始解，以试图提高解决NP难问题的效率。
但我最后采用了一种简单粗暴的方式来生成初始牌型，即按牌力大小提取出初始牌型：
-
先提取所有的炸弹
-
再提取对大鬼、对小鬼、单张大小鬼
-
再提取大的飞机带翅膀、大的飞机、大的连对
-
再提取大的顺子
-
最后，按飞机带翅膀、飞机、连对、顺子、拂绿、三张、对、单张的顺序将牌全部提完
我采取这种方式的原因很简单：对于某些问题，初始解决定了算法的效率和成本，但牌型选择不是这样的问题。
请想一下，为什么呢？！
所以，我们没必要花费太多的心思来精心生成初始蚂蚁以求得一个高质量的初始解，按上述方式快速生成一个简单的初始解即可。
局部更新
前面讨论过，蚁群算法本质并不是算出最优解，而是高效的搜索出最优解，所以我们需要扩大蚂蚁的搜索空间。但随着算法的一轮轮迭代，当优势结构慢慢呈现时，由于信息素的频繁释放，会造成优势结构的吸引力比较大，这可能会限制蚂蚁对其它潜在最优解的探索。针对这种情况，改进的蚁群算法引入了局部更新技术：即在选择了一个牌手后，立刻对本次选择做一个小的蒸发，以降低该选择的信息素浓度，这就增加了其它蚂蚁做出其它选择的可能性。
但由于局部更新会导致每只蚂蚁每步选择后都修改全局信息素的数据，这就是我们前面说过的，局部更新技术会对蚁群算法的分布式执行造成严重干扰。如果大家考虑分布式的蚁群算法，就需要去掉该技术。而针对搜索空间快速收窄的问题，可以结合爬山法来扩大搜索空间。
信息素蒸发
由于蚁群算法每轮次有一个信息素的蒸发动作，这个蒸发的目的是如果不是最优的选择，则在某次尝试后就会逐渐丧失吸引力，被再次选中的可能性会越来越小。但由于我们的评分是剩余牌手数，而剩余牌手数可能会是负数，那么负数的蒸发反而会导致信息素的值越来越大了，而且负数也会干扰加权概率的计算。所以为了避免评分出现负数，我们在计算完剩余牌手数后，对其统一增加了100以进行结构评分的正向纠正。
结构罚分
上一讲也说过，如果把对大鬼拆为两个单张的大鬼，会提升牌型的评分，所以我们会发现，蚂蚁受提高牌型质量的鼓励，导致提取出的牌型非常琐碎。因此，目前在计算牌型评分的时候，我还加入了一个针对牌手数量的惩罚性加分，但又使得牌型非常偏向简洁，似乎有过份惩罚的倾向，本来以为应当需要根据大量数据的分析来确定一个合理的惩罚系数。但是在这个调整过程中，突然发现，似乎只要调整结构惩罚系数，我们就能得到从偏向威力最大化到偏向简洁的不同情况下的一系列牌型，这倒是丰富了我们的牌型选择空间。
本来我们静态确定了一个最优的牌型，在后面打牌的过程中，随时可能需要根据牌面进行牌手的重新组合、分拆。如，最优牌型可能以炸弹、三张为主，但对家判明这一点后，始终利用单张过桥，那我们就必须不停的拆牌。但这带来了一个问题：如何判断该不该拆牌、该拆哪手牌、剩下的牌又该如何重新组合呢？笔者花了很长的时间都找不到一个合适的方法来处理这个问题:(
但现在我们有了通过动态调整结构罚分系数可以得出一系列牌型的能力，就有个了意外之喜：我们只要先生成一系列各种各样的牌型，然后根据对家出牌确定各牌型中如何应牌最有利即可。这就略去了处理拆牌、组合的烦恼:)
这个问题再次说明，数字世界和现实世界有着本质的区别，我们在想象世界中的问题变换至关重要！
综上，目前的牌型评分的计算公式为：
牌型评分 = 各类型牌的累计剩余牌手数（经过了牌力过剩处理） + 牌手数 × 结构惩罚系数（可动态指定） + 结构纠偏值（100，这个取值只要大于最大可能的剩余牌手数33就可以了）
====================================================================================================
关注我的公众号及时获取推送的最新文章
