跳到主要内容

模拟退火算法原理及应用

输入方案的优化​

我们设计一个输入方案，在确定初始的想法、完成第一次编码之后，绝大多数时间花在优化上、输入方案最终效果也多取决于这些优化。可以说，优化的能力决定了最终输入方案的质量。

优化再进行细分，可以分为三个模块：

  • 编码：根据现有方案生成码表。
  • 测试：根据码表测试方案特性。
  • 调整：根据测试结果调整方案，得到优化后的方案。

不是说优化只包含三步，而是说优化的每一小步都包含这三个模块，每一轮优化的终点就是下轮优化的起点，如此循环往复，最终得到满意的结果。

那么这三个模块哪一个比较困难呢？编码好说，有了拆分表就能编码。测试也好说，统计重码、码长、当量等等的代码都是现成的。但是调整就不是那么简单了。我总结了调整的一些问题：

  • 怎么做调整。在 86 五笔的年代，王永民通过手写卡片的制作，分析了不同字根的布局重码，根据布局重码的多少逐个调整字根，经过数年的优化达到了最优。虽然手动调整也能够达到较好的效果，但毕竟费时费力，所能尝试的布局数量也有限。今天，我们作为输入方案的一般爱好者，很难有耐心再进行这样的手动调整。
  • 做什么样的调整。方案的变化非常多，不可能穷尽所有变化，我们只能经过有限次调整、尝试有限种方案并从中选出局部最优而非全局最优的方案。在这种逻辑下，如果我们进行的某次调整有利于优化（下图中，从 C 点到 A 点），我们很可能会接受这样的调整；但是，如果我们进行的某次调整不利于优化（下图中，从 A 点到 E 点），我们是不是一定不能接受这样的调整呢？不是的。如果我们想达到全局最优（下图中 B 点），则 E 是必经之路；如果因为 A 到 E 的一点点下降而放弃 B 点的极大上升，那么我们就失去了达到全局最优的机会。问题的复杂之处在于，我们到达 E 的时候，并不知道再往前走到底是下降还是上升，那么我们到底怎么才能知道要不要接受某次调整呢？

所以，在这里，我们介绍一种自动的、考虑全局的优化方法，名为模拟退火算法。

原理​

什么是退火？​

退火是获得结构高度有序的固体材料的方法。首先将固体加热至充分高的温度，再让其缓慢冷却。在高温时，固体中粒子动能大，不仅能发生降低能量的结构变化，也有一定概率发生升高能量的结构变化；这使得固体结构有一定概率逃逸出能量的局部极小值，而到达全局最小值。随着温度降低，发生升高能量的结构变化的概率越来越低，最终几乎只发生降低能量的结构变化而达到稳定的结果。

什么是模拟退火算法？​

如前所述，我们为了完成更好的优化，我们需要有时接受一次更差的调整。模拟退火算法吸取了固体退火中的精髓，即接受更差结果的概率随着时间慢慢降低，这样既能保证一开始不陷入局部极小值出不来，又能保证最终达到稳定状态。虽然模拟退火算法未必能够获得全局最小值，但也比单纯地只接受更优的调整有着大得多的搜索范围。

模拟退火算法有哪些控制参数？​

最高温tmax、最低温tmin、步骤数steps。

最高温的设定应该使得在一开始能够接受大多数的移动；最低温的设定应该使得确保在这个温度下不会再发生任何优化；步骤数越多优化效果越好。但是，这些参数通常一开始并不知道，这个问题会在下面具体讨论。

退火算法使用实例​

作者不是计算机学历背景，仅仅会一些 Python，故用这一语言讲解。其余不难类推。

首先，在命令提示符中安装现成的退火模块：

pip install simanneal

然后，新建sa.py，在其中导入这个模块和一些其他必要模块：

from simanneal import Annealer
from __future__ import print_function
import math
import random

假设我们现在要处理一个四码全码的字根分布问题。考虑最简单的情况，所有字都是四个字根，字根的键位任意分布。我们首先读入拆分表和初始布局，然后定义编码函数：

##拆分表
d = {}
f = open('split.txt', encoding = 'utf-8', mode = 'r')
for line in f:
    char, split = line.strip('\r\n').split('\t')
    d[char] = split
f.close()
##字根表
init_state = {}
f = open('comps.txt', encoding = 'utf-8', mode = 'r')
for line in f:
    comp, key = line.strip('\r\n').split('\t')
    init_state[comp] = key
f.close()

##编码函数
def code(char, state):
    split = d[char]
    return state[split[0]] + state[split[1]] + state[split[2]] + state[split[3]]
##表示取码方法，依次取四个字根的代码

现在我们定义一个新的类并初始化，用来处理我们用到的函数。ComponentsDistributionProblem就是我们的字根分布问题。

class ComponentsDistrbutionProblem(Annealer):

    def __init__(self, state, components):
        super(ComponentsDistrbutionProblem, self).__init__(state)

接下来我们定义我们优化需要的其他两大函数：

    #测试函数    
    def energy(self):
        chars = list(d.keys())
        chars_to_code = [code(char) for char in chars] #首先生成所有编码
        distinct_code = set(chars_to_code) #然后将这些编码去重
        dup = len(chars_to_code) - len(distinct_code) #所有编码数减去去重后编码数就是重码数
        return dup

    #调整函数
    def move(self):
        a = random.choice(self.state)
        b = random.choice(self.state)
        self.state[a], self.state[b] = self.state[b], self.state[a] #随机交换两个字根的键位

最后，我们结束了这个类中所有函数的定义，实际运行：

if __name__ == '__main__':
    cdp = ComponentsDistrbutionProblem(init_state) #先把init_state作为参数传入
    cdp.copy_strategy = "method"
    #auto_schedule = cdp.auto(minutes=10) 如果不确定用什么参数，先提供时间参数让它自己探索一下
    auto_schedule = {'tmax': 0.14, 'tmin': 6.7e-07, 'steps': 10000000} #如果确定用什么参数，就提供
    cdp.set_schedule(auto_schedule)
    cdp.updates = 100
    print(auto_schedule) #把优化参数打印出来
    state, dup = cdp.anneal() #开始优化

运行完毕，保存结果。

    #优化完成，把结果保存下来
    f = open('result.txt',encoding='utf-8',mode='w')
    for comp in state:
        f.write(comp+'\t'+state[comp]+'\n')
    f.close()

4. 站在模拟退火算法之上​

有了模拟退火算法，对于一般复杂度的体系，我们可以在 10 分钟内完成一次彻底的优化，大大节省了时间。从而，我们可以节省出更多的脑力资源考虑更加复杂的问题，诸如输入方案结构设计等等。

但是，仅仅采用算法也有它的问题。上面展示单一指标优化仅仅是最简单的一种情况，在复杂、通向实用的输入方案设计中，我们还有其他因素要考虑。当情况变复杂时，需要注意下列几个问题：

  • 不同指标之间的加权（码长、手感、重码……）
  • 考虑有理性、易学性（字根的音托、形托、二笔分布……）
  • 编码、测试函数优化（最好优化到 0.01 s 以内）
  • ……

另一方面，模拟退火算法不是唯一的全局优化算法，还有遗传算法等各具特色的算法，可以根据需要选用。但是一般来讲模拟退火是一种比较通用的方法，它常常是一个好的开始。

祝大家折腾愉快！