-
Notifications
You must be signed in to change notification settings - Fork 0
/
nrpa_common.jl
130 lines (119 loc) · 4.12 KB
/
nrpa_common.jl
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
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
function playout(sn, vnr, policy, distances, solver::Function, order_links::Bool, max_bw_sn, max_bw_vnr, sum_bw_sn, sum_bw_vnr)
sequence = []
done::Bool = false
curr_node = 1
# each key identifies a state uniquely in our dictionnary
key = ""
reward::Float64 = 0
while true
if done
return reward, sequence
end
if !haskey(policy, key)
default_weight!(policy, key, distances)
end
z::Float64 = 0.0
weights_vect = Float64[]
actions_vect = Int64[]
plm = false
"""
for m in get_legal_moves(sn, vnr, curr_node)
for i in sequence
@assert m != i
end
end
"""
for m in get_legal_moves(sn, vnr, curr_node, max_bw_sn, max_bw_vnr, sum_bw_sn, sum_bw_vnr)
key_child = key * "," * string(m)
if !haskey(policy, key_child)
default_weight!(policy, key_child, distances)
end
ex::Float64 = exp(policy[key_child])
z += ex
push!(actions_vect, m)
push!(weights_vect, ex)
end
# println(weights_vect)
# if there is no more move here, it means the placement is failed since it is unfinishable
if length(actions_vect) == 0
return 0, []
end
# sample actions according to Gibbs sampling
#println(weights_vect)
#println(weights_vect ./ z)
action = sample(actions_vect, Weights(weights_vect ./ z), 1)[1]
sn, vnr, curr_node, reward, done = play(sn, vnr, curr_node, action, solver, order_links)
push!(sequence, action)
key *= ","
key *= string(action)
end
end
function adapt(policy, sequence, sn, vnr, distances, solver::Function, order_links::Bool, max_bw_sn, max_bw_vnr, sum_bw_sn, sum_bw_vnr)
polp = copy(policy)
key = ""
alpha::Float64 = 1
curr_node = 1
for action in sequence
key *= ","
key *= string(action)
if !haskey(polp, key)
default_weight!(polp, key, distances)
end
polp[key] += alpha
z::Float64 = 0
moves = get_legal_moves(sn, vnr, curr_node, max_bw_sn, max_bw_vnr, sum_bw_sn, sum_bw_vnr)
for m in moves
key_child = key * "," * string(m)
if !haskey(policy, key_child)
default_weight!(policy, key_child, distances)
end
z += exp(policy[key_child])
end
for m in moves
key_child = key * "," * string(m)
if !haskey(polp, key_child)
default_weight!(polp, key_child, distances)
end
polp[key_child] -= alpha * (exp(policy[key_child]) / z)
end
# we avoid doing the last call to place links as it is expensive and we do not need the reward here
# legal nodes are all that matters
if curr_node < nv(vnr)
sn, vnr, curr_node, reward::Float64, done::Bool = play(sn, vnr, curr_node, action, solver, order_links)
end
end
return polp
end
####################################################################
################ HELPER FUNCTIONS USED IN NRPA #####################
####################################################################
function default_weight!(policy, key)
policy[key] = 0
end
function default_weight!(policy, key, distances)
if distances == nothing
policy[key] = 0
return
end
if key == ""
policy[key] = 0
else
nodes = split(key, ",")
k = 0
# first "node" is always empty string, last one is the node we are trying to rate
for i in nodes[2:end-1]
k += distances[parse(Int64, nodes[end])][parse(Int64, i)]
end
policy[key] = -k / (length(nodes)-1)
end
end
####################################################################
################ HELPER FUNCTIONS USED IN MAIN #####################
####################################################################
function median_bw(vnr)
a = []
for e in edges(vnr)
push!(a, get_prop(vnr, e, :BW))
end
return median(a)
end