本章讲的是如何使用一系列被称为随机优化的技术来解决协作类问题。比如本书中例子:一个家庭成员在不同地方的家庭要到纽约聚会,如何安排航班行程,使得费用与等待时间最少。

成本计算

要想安排行程,首先要明确有哪些变量控制着行程成本,本书中给出了机票价格,时间两个变量。所有家庭成员要等到所有人到齐后才走,回去时也是要同时到达机场。

假定他们选择了一组往返航班,就可以根据航班算出价格,时间则是每个人在机场等待的时间相加之和,这样就能够简单的将成本量化。

优化

有了成本,我们就可以计算最优解。我们假定每个人做的航班有 10 种选择,家庭成员有 6 个人,往返就是 12 个航班。那么组合高达 10^12 次方,直接遍历不是个好的选择,所以我们应该选择优化算法来计算较优解而不是最优解。

随机搜索

随机搜索不是一种很好的算法,但却是所有算法的真正意图,不管算法在如何复杂,只要不是遍历所有值,那就是在一组随机数据中寻找最优解。

按照之前所说,假定 6 个成员,12 个航班,每个航班有 10 种选择。那么我们建立一个二元组

1
domain = [(0, 9)] * len(people*2)

我们对每一个选择进行 random 操作,取 0~9 之间的随机数

1
2
select = [random.randint(domain[i][0], domain[i][1]) 
for i in range(len(domain))]

然后我们随机 1000 次,每次都比较出最好的那个值。这就是随即搜索,十分简单但也不完善,后面我们会在随机搜索之上添加一些新的算法。

爬山法

爬山法从一个随机解法开始,然后再临近的解集中寻找更优解法,就好像人在半山腰往下走一样。

首先我们如上创建一个随机解 select

进入循环

在随机解的基础上偏离一点

1
2
neighbors.append(select[0:i] + [select[i]+1] + select[i+1:])
neighbors.append(select[0:i] + [select[i]-1] + select[i+1:])

不断的计算更优解,将更优解替换为 select 如此循环直到无法找到更优解。

这就是爬山法的思路,但爬山法有一个问题。我们的问题并不是像2次函数一样只有一个最低点,而是一个很多弯弯曲曲的函数,直接食用爬山法有时得到的解还不如随机搜索。

模拟退火

另外一种算法是模拟退火算法,退火算法是从物理学领域启发而来的一种优化算法。退火是指将合金加热后在慢慢冷却的过程,大量原子因为受到激发而向周围跳跃然后又逐渐过渡到低能阶的状态。

退火算法也是由一个随机解开始,它用一个变量 template 表示温度,温度一开始非常高,而后逐渐迭代降低。每次迭代期间,算法会随机选择题解的某个数组,然后朝某个方向变化。

算法关键在于,如果新的值更低,新的题解就会成为当前题解,这与爬山算法相同。但不同的是新的值比当前值高时,当前值也有概率变成新值,这取决于温度的高低。这样算的好处是可以避免陷入局部最小值的问题。

算法除了接受更优解,还有「概率」接受较差的解,概率的大小由 template 决定

P(A) = e^(-(hightcost-lowcost)/template)

一开始的温度很高 -(hightcost-lowcost)/template 趋近于 0,所以 P(A) 趋近于 1,随着温度下降到 0,P(A) 趋紧于 0

1
2
3
4
5
# costf 函数为成本算法,返回成本值
ea = costf(vec) # 当前成本
eb = constf(vecb) # 经过某个值偏移的成本
if (eb < ea or random.random() < pow(math.e, -(ea-eb)/T)):
vec = vecb

这就是模拟退火算法。

遗传算法

遗传算法来自于生物学的启发,这类算法的运行过程是先随机生成一组解,称之为种群,然后对种群中较优的个体进行变异和配对。

变异很好理解,就是将某个值加一位或减一位,比如将父亲选择的3号航班改为4号。
配对则是将两个解法之前某一段进行交换得到新的解法,类比于染色体。

整个遗传算法就跟自然选择一样,从一代中挑选出较优的个体,然后变异和配对,在对下一代进行选择。如此反复。

以上所有算法在 Github 上的 optimization.py 内

可视化

优化算法的另一例子,是根据连接关联绘制图形,在展示一大群人及其彼此的关联,如何清晰的绘制出关系图,如图所示

在关系网中,最重要的是防止交叉线的出现,这是我们可以选择构造一个成本函数,然后使用前面的优化算法得出最小交叉线的排列方式,假设4个点 A(x1,y1) B(x2,y2) C(x3,y3) D(x4,y4),如何判断该 AB 与 CD 不交叉。

首先判断直线是否平行,很好证就不说了

(y4-y3) (x2-x1) - (x4-x3) (y2-y1) = 0

其次,根据「向量AC」至「向量AD」和「向量BC」至「向量BD」的方向是否一致,不一致则说明交叉。具体推导可参考判断相交的最简方法

1
2
3
4
5
dir1 = (x3-x1) * (y4-y1) - (x4-x1) * (y3-y1)
dir2 = (x3-x2) * (y4-y2) - (x4-x2) * (y3-y2)

if dir1 * dir2 < 0:
total += 1

然后将其带入随机算法等即可,domain 限制在 10-370 附近表示在这个区域内取坐标值

1
2
domain = [(10,370)] * (len(people) * 2)
sol = optimization.randomoptimize(domain, crosscount)

接下来使用 Image 绘制网格即可,详细代码在Github 上的 socialnetwork.py 内