《新编绝算双色球》第七章(九):矩阵是怎么算出来的——模拟冷却与四种算法
专题八回答”旋转矩阵从哪来”。结论有两层:它不是彩票专家发明的,而是组合数学”覆盖设计”的产物;具体构造靠算法,最著名的是 Ostergard 首创的模拟冷却算法——通过模拟分子降温,在不必穷举的前提下找到接近最优的矩阵。
1. 对旋转矩阵作出突出贡献的主要数学家
有许多国外的彩票专家,声称首次提出旋转矩阵。实际上,所有的旋转矩阵都是组合数学家们经过多年的精心研究得出的,而不是某一个彩票专家所能研究出来的。
| 数学家 | 主要贡献 |
|---|---|
| Patric Ostergard | 用全新的模拟冷却算法解决构造问题;程序 COVER 可迅速产生大量矩阵 |
| Alex Sidorenko | 研究出许多矩阵与几种基于图灵(Turan)定理的一般方法 |
| Greg Kuperberg | 注意到线性 [v,t] 编码的补集可给出区组长度不定的覆盖设计,能改进现有矩阵 |
| Dan Gordon | 总结所有矩阵成果、持续跟踪进展,收集的矩阵最全面最权威,全凭个人兴趣、无经费支持 |
Dan Gordon 是圣地亚哥的通讯研究中心的研究员,个人兴趣:计数理论、组合学、代数分析。Greg Kuperberg 是美国加州大学数学系的副教授,主要研究方向是复杂性分析和微积分。
Patric Ostergard 是芬兰赫尔辛基理工大学计算科学和工程系的教授……他擅长用计算机解决离散数学中的问题……他是 1996 寇克曼奖的得主,这个奖由国际组合学协会颁发,以已故著名组合学家寇克曼的名字命名……他还是组合设计杂志的编辑。他在覆盖设计的主要贡献是开创了用模拟冷却算法构造覆盖设计的先河。
2. 旋转矩阵的主要算法
旋转矩阵的定义是很容易明白的……然而,如何快速有效地构造旋转矩阵是数学家一直研究的问题。当然,这其中最关键的就是算法。近年来最好的算法是模拟冷却算法,它主要由 Patric Ostergard 首创,并且得到了许多后来者的发展。
(1)模拟冷却算法(Simulated Annealing)
模拟冷却算法是一种随机搜索方法,它的主要特点是不用穷遍集合中每一种可能性就可以找到最优或几乎最优的状态。它是通过模拟一个分子系统的自然冷却过程来做到这一点的。在每一种状态,它随机地选择了一种相邻的状态:如这种相邻的状态有一个更低的成本,系统将会转移到该状态;如果这种相邻的状态有一个更高的成本,系统将可能会转移到该状态,也可能不会转移到该状态。转移的概率依赖于现在状态的温度参数(该值越高,转移的概率越大)和两个状态之间的成本差异(差异越大,转移的概率越大)。温度将会渐渐低下来,最终会达到均衡。
模拟算法的一般步骤如下:
第一步:给定一个初始状态和初始温度;
第二步:外部循环——① 内部循环:a. 随机选择一个相邻状态,若相邻状态的成本更低,转移;b. 若相邻状态的成本更高,转移的概率为 exp(-成本差异/温度);② 降低温度;
第三步:返回所遇到的最优状态。
模拟冷却算法的设计者需要选择以下 6 个参数:① 初始温度和初始状态;② 一种状态的成本函数;③ 一种状态的相邻函数;④ 冷却程序;⑤ 内部循环方法;⑥ 外部循环方法。
初始状态和初始温度实际上对算法影响不大,成本函数一般来说也比较容易定义,尤其是对覆盖设计来说,成本可以定义成重复数字的总个数。相邻函数也可以随机挑选一个向量来解决。而有效的冷却程序一般用 T’=rT,这里 T 指原来的温度,T’ 是新的温度,r 是常数,也叫冷却因子。
(2)非连通的集合来结合覆盖设计
如果对某个 v=v₁+v₂ 和所有的 t₁+t₂=t,都有大小为 N₁ 的覆盖设计(v₁, k₁, t₁)和大小为 N₂ 的覆盖设计(v₂, k₂, t₂)存在,那么将有大小为 N=N₁×N₂ 的覆盖设计存在。然而,可以用这种方法产生的旋转矩阵数量很少,而且构造的过程也很复杂。
(3)贪婪算法
这种算法的核心思想是:每个区组都尽量保持目前看来最好的状态,也就是尽可能少重复前面区组的数字,一直重复下去,直到你得到一个覆盖设计。你可以用顺序、逆序或灰色、随机的顺序来重复这个过程。
事实上,笔者起初的时候正是用这个方法来产生一些比较简单的矩阵,但是这种算法看起来容易,实际上却十分繁琐,如果不用计算机,即使是很简单的矩阵,也要耗费无数的精力。而且,这种算法只能保证可以产生旋转矩阵,却无法保证产生的旋转矩阵一定是最优的。当参数很大时,用它产生的矩阵离最优的矩阵还差得很远。但是,可以用这种方法产生初始解,然后利用其他的优化算法(例如模拟冷却算法)对它再进一步优化。
(4)诱致算法
Greg Kuperberg 是这种算法的主要创立者和提倡者。先利用一个巨大的参数为(V, K, t)的旋转矩阵,从 V 个点中按照某种顺序或完全随机地选出 v 个点,然后将它们用原来的长度为 K 的区组隔断,得到了每个区组个数不定的一个覆盖。最后,将这个覆盖进行修补即可:对每一个长度为 1 的区组,将该区组替换成一个(1, k, t)的覆盖设计。这是一种比较复杂的算法,然而,却是迄今最好的算法之一。
| 算法 | 思路 | 优点 | 局限 |
|---|---|---|---|
| 模拟冷却 | 随机搜索+降温,允许”暂时变差”以跳出局部最优 | 不穷举也能找到近优解,可批量生产 | 需调 6 个参数(初始温度、成本函数、冷却因子等) |
| 非连通结合 | 两个覆盖设计相乘 N=N₁×N₂ | 构造简单 | 能产生的矩阵很少,过程复杂 |
| 贪婪算法 | 每个区组尽量少重复前面的数字 | 可手工起步,能产出初始解 | 不保证最优,参数大时离最优很远 |
| 诱致算法 | 大矩阵抽样+隔断+修补 | 迄今最好之一 | 过程复杂 |
这一节最值得记住的是”成本=重复数字的总个数”这一句:覆盖设计要解决的问题,就是让每一注尽量不与前面的注重复——重复越少,同样的注数覆盖的面越大。所谓”旋转矩阵的保证”,其实是数学家把”重复”压到最低之后算出来的必然结果。这也解释了为什么原书敢说”复式投注也是矩阵的特例”:复式恰恰是”重复最多、覆盖最全”的那一端。
本文依据《新编绝算双色球》(彩天使著,中国市场出版社 2009 年 4 月第 1 版)专题八(原书正文第 153—157 页)照录整理;Ostergard(模拟冷却、COVER、1996 寇克曼奖)、Sidorenko(Turan 定理)、Kuperberg(线性编码补集)、Dan Gordon(最全收集、无经费)四人的贡献与简介、模拟冷却的定义与三步流程、六项参数、”成本=重复数字总个数”、冷却公式 T’=rT、非连通结合的 N=N₁×N₂、贪婪算法的思路与”不保证最优”、诱致算法的抽样与修补均按原书转录。须说明:原书对 Kuperberg 的 [v,t] 编码表述带方括号且上下标压叠,本文按可辨形式写作”线性 [v,t] 编码”;各数学家的论文清单(如 1996 年 J. Combin. Theory Ser. A 等)原书以英文列出,本文未逐一转引,只保留其研究方向。末表为本系列整理,非原书内容。
