forked from Workiva/go-datastructures
-
Notifications
You must be signed in to change notification settings - Fork 0
/
global.go
168 lines (142 loc) · 4.54 KB
/
global.go
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
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
package optimization
import (
"math"
"sort"
)
type pbs []*vertexProbabilityBundle
type vertexProbabilityBundle struct {
probability float64
vertex *nmVertex
}
// calculateVVP will calculate the variable variance probability
// of the provided vertex based on the previous best guess
// and the provided sigma. The sigma changes with each run
// of the optimization algorithm and accounts for a changing
// number of guesses.
//
// VVP is defined as:
// 1/((2*pi)^(1/2)*sigma)*(1-e^(-dmin^2/2*sigma^2))
// where dmin = euclidean distance between this vertex and the best guess
// and sigma = (3*(m^(1/n)))^-1
//
func calculateVVP(guess, vertex *nmVertex, sigma float64) float64 {
distance := -guess.euclideanDistance(vertex)
lhs := 1 / (math.Sqrt(2*math.Pi) * sigma)
rhs := 1 - math.Exp(math.Pow(distance, 2)/(2*math.Pow(sigma, 2)))
return rhs * lhs
}
// calculateSigma will calculate sigma based on the provided information.
// Typically, sigma will decrease as the number of sampled points
// increases.
//
// sigma = (3*(m^(1/n)))^-1
//
func calculateSigma(dimensions, guesses int) float64 {
return math.Pow(3*math.Pow(float64(guesses), 1/float64(dimensions)), -1)
}
func (pbs pbs) calculateProbabilities(bestGuess *nmVertex, sigma float64) {
for _, v := range pbs {
v.probability = calculateVVP(bestGuess, v.vertex, sigma)
}
}
func (pbs pbs) sort() {
sort.Sort(pbs)
}
func (pbs pbs) Less(i, j int) bool {
return pbs[i].probability < pbs[j].probability
}
func (pbs pbs) Swap(i, j int) {
pbs[i], pbs[j] = pbs[j], pbs[i]
}
func (pbs pbs) Len() int {
return len(pbs)
}
// results stores the results of previous iterations of the
// nelder-mead algorithm
type results struct {
// vertices are the results generated by the algorithm
vertices vertices
// config is useful for examining target
config NelderMeadConfiguration
// pbs contains the randomly generated guess vertices
pbs pbs
}
// search will search this list of results based on order, order
// being defined in the NelderMeadConfiguration, that is a defined
// target will be treated
func (results *results) search(result *nmVertex) int {
return sort.Search(len(results.vertices), func(i int) bool {
return !results.vertices[i].less(results.config, result)
})
}
func (results *results) exists(result *nmVertex, hint int) bool {
if hint < 0 {
hint = results.search(result)
}
// maximum hint here should be len(results.vertices)
if hint > 0 && results.vertices[hint-1].approximatelyEqualToVertex(result) {
return true
}
// -1 here because if hint == len(vertices) we would've already
// checked the last value in the previous conditional
if hint < len(results.vertices)-1 && results.vertices[hint].approximatelyEqualToVertex(result) {
return true
}
return false
}
func (results *results) insert(vertex *nmVertex) {
i := results.search(vertex)
if results.exists(vertex, i) {
return
}
if i == len(results.vertices) {
results.vertices = append(results.vertices, vertex)
return
}
results.vertices = append(results.vertices, nil)
copy(results.vertices[i+1:], results.vertices[i:])
results.vertices[i] = vertex
}
func (results *results) grab(num int) vertices {
vs := make(vertices, 0, num)
// first, copy what you want to the list to return
// not returning a sub-slice as we're about to mutate
// the original slice
for i := 0; i < num; i++ {
vs = append(vs, results.pbs[i].vertex)
}
// now we overwrite the vertices that we are taking
// from the beginning
copy(results.pbs, results.pbs[num:])
length := len(results.pbs) - num
// this next part is required for the GC
for i := length; i < len(results.pbs); i++ {
results.pbs[i] = nil
}
// and finally set the new slice as a subslice
results.pbs = results.pbs[:length]
return vs
}
// reSort will re-sort the list of possible guess vertices
// based upon the latest calculated result. It was also
// add this result to the list of results.
func (results *results) reSort(vertex *nmVertex) {
results.insert(vertex)
bestGuess := results.vertices[0]
sigma := calculateSigma(len(results.config.Vars), len(results.vertices))
results.pbs.calculateProbabilities(bestGuess, sigma)
results.pbs.sort()
}
func newResults(guess *nmVertex, config NelderMeadConfiguration, num int) *results {
vertices := make(vertices, 0, num+1)
vertices = append(vertices, guess)
vertices = append(vertices, generateRandomVerticesFromGuess(guess, num)...)
bundles := make(pbs, 0, len(vertices))
for _, v := range vertices {
bundles = append(bundles, &vertexProbabilityBundle{vertex: v})
}
return &results{
pbs: bundles,
config: config,
}
}