延迟接受算法
延迟接受算法是一个比较经典的优化算法，也叫做盖尔-沙普利算法，是盖尔和沙普利为了寻找一个稳定匹配而设计出的市场机制。从算法的角度来讲，延迟接受就是对当前解不会立即接受，而是暂时的不被拒绝，当迭代次数停止以后，会从手上选择最优的那一个作为最终解。
问题描述
我们有一个要优化的目标\(f(x,y,z)=x^2 \ast z-y^3 \ast z^2+x^2 \ast y^3-x/y\)，\(x,y,z\)的范围都是[0, 100]，我们就要在这个范围内求出函数\(f(x,y,z)\)的最小值。由于解空间比较大，我们无法在常数时间内取得最优解，所以只能考虑启发式的方式来寻求局部最优解。启发式方法可以简单的理解为我们给定一个初始解，然后在该初始解的邻域范围内进行搜索，最终获得一个局部最优解(全局最优解)。延迟接受就是一种求解方法。
算法描述
延迟接受算法就是将当前的新解与\(n\)步之前的解进行对比，若当前解优于\(n\)步以前的解，则直接接受当前解，若比\(n\)步之前的解差，则拒绝当前解。
延迟接受还有一个变种，就是带爬山的延迟接受( Late Acceptance Hill-Climbing)，从名字上也可以看出，“带爬上”其实就是引入了爬上的思路，即当前解与上一步的解来比较，若优于上一步解，则直接接受新解，否则拒绝。
lahc
延迟接受算法的流程如上图所示，
1、\(s\)为初始解，\(C\left(s\right)\)为初始解的函数值，\(Lfa\)就是延迟接受的步长，我们可以以一个队列或者数组来存储延迟接受的\(Lfa\)个解，初始解都为\(C(s)\)。
2、开始迭代，构建新解\(s\ast\)，计算新解的函数值\(C(s\ast)\)。
3、计算\(Lfa\)步之前的解的函数值\(f(v)\)，\(v := I \% Lfa\)，\(v\)相对于\(I\)就是\(Lfa\)步之前解的函数值。
4、比较 \(C(s\ast)\) 和 \(f(v)\)，比较 \(C(s*)\) 和 \(C(s)\)，若\(C(s\ast)\)优于\(f(v)\)或者\(C(s)\)，则直接接受当前新解\(s\ast\)，并更新\(f(v)=C(s\ast)\)。
5、若\(C(s*)\) 差于\(f(v)\) 或者 \(C(s)\)，则更新 \(f(v)=C(s)\)。
6、I=I+1，直到迭代终止。
上面就是延迟接受的整个流程，最关键的是第4和第5步，尤其第5步，当前新解比之前n步的解或者上一步的解要差时，应该是将上一步的解重新更新到n步之前的位置。
算法应用
我们可以将延迟接受算法应用到TSP问题中，TSP问题也是一个NP-hard问题，可以采用启发式算法的方式去进行求解。
部分代码如下
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
| package algorithm
import (
"TSP/ioinfo"
"TSP/util"
"fmt"
"math/rand"
"time"
)
type LateAcceptance struct {
n int
tScore []float64
}
func (l *LateAcceptance) Init(n int, pStartScore float64) {
l.n = n + 1
for i := 0; i < l.n; i++ {
l.tScore = append(l.tScore, pStartScore)
}
}
func (l *LateAcceptance) Accept(pScore float64) bool {
var pAccept bool
if pScore <= l.tScore[0] {
pAccept = true
} else if pScore <= l.tScore[len(l.tScore) - 1] {
pAccept = true
} else {
pAccept = false
}
if pAccept {
l.tScore = append(l.tScore, pScore)
} else {
l.tScore = append(l.tScore, l.tScore[len(l.tScore) - 1])
}
if len(l.tScore) >= l.n {
l.tScore = l.tScore[1:]
}
return pAccept
}
func changCity1(dataSrc []ioinfo.Data, R1 rand.Rand) []ioinfo.Data {
pos1 := R1.Intn(len(dataSrc)-3) + 1
pos2 := R1.Intn(len(dataSrc)-pos1-1) + pos1
dataDest := make([]ioinfo.Data, len(dataSrc))
copy(dataDest, dataSrc)
r := R1.Intn(2)
if r == 0 {
for pos1 < pos2 {
dataDest[pos1], dataDest[pos2] = dataDest[pos2], dataDest[pos1]
pos1 ++
pos2 --
}
} else {
dataDest[pos1], dataDest[pos2] = dataDest[pos2], dataDest[pos1]
}
return dataDest
}
func La(pFileName string) float64 {
data := util.GetSampleData(pFileName, false)
r := util.GetResult(data)
pLa := new(LateAcceptance)
pLa.Init(215, r)
var R1 = rand.New(rand.NewSource(0))
s1 := time.Now().UnixNano()
pIterNum := 200000
for pIterNum > 0 {
temp := changCity1(data, *R1)
rn := util.GetResult(temp)
if pLa.Accept(rn) {
data = temp
}
pIterNum--
}
s2 := time.Now().UnixNano()
fmt.Println(data, s2 -s1)
return util.GetResult(data)
}
|
1
2
3
4
| 延迟接受启动：
[ 1 -> 43 -> 23 -> 56 -> 41 -> 42 -> 64 -> 61 -> 69 -> 36 -> 37 -> 71 -> 60 -> 70 -> 20 -> 15 -> 57 -> 27 -> 52 -> 13 -> 54 -> 19 -> 59 -> 14 -> 53 -> 11 -> 66 -> 65 -> 38 -> 31 -> 10 -> 58 -> 72 -> 39 -> 9 -> 40 -> 12 -> 17 -> 76 -> 26 -> 7 -> 35 -> 8 -> 46 -> 34 -> 67 -> 75 -> 4 -> 45 -> 29 -> 5 -> 48 -> 47 -> 21 -> 74 -> 30 -> 2 -> 68 -> 6 -> 51 -> 3 -> 44 -> 32 -> 50 -> 25 -> 55 -> 18 -> 24 -> 49 -> 16 -> 63 -> 33 -> 73 -> 62 -> 28 -> 22 -> 1 ->] 170124000ns
588.1953208548182
|
76个点需要170ms，最终结果588.195
全局最优解为545.3875524687445，延迟接受的解比全局最优解差7%左右，结果还是可以接受的。