-
Notifications
You must be signed in to change notification settings - Fork 1
/
knapsack_problems_test.go
109 lines (88 loc) · 2.68 KB
/
knapsack_problems_test.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
package genetic_test
import (
"crypto/rand"
"testing"
"github.com/kklash/bits"
"github.com/kklash/genetic"
)
type KnapsackItem struct {
Weight, Value int
}
type KnapsackProblem struct {
Items []*KnapsackItem
WeightLimit int
}
func (problem *KnapsackProblem) RandomSolution() *KnapsackSolution {
randomBits := make(bits.Bits, len(problem.Items))
randomBits.ReadFrom(rand.Reader)
return &KnapsackSolution{
PackingList: randomBits.Bools(),
Problem: problem,
}
}
type KnapsackSolution struct {
PackingList []bool
Problem *KnapsackProblem
}
func (solution *KnapsackSolution) String() string {
return bits.BoolsToBits(solution.PackingList).String()
}
func solutionFitness(solution *KnapsackSolution) int {
if len(solution.PackingList) != len(solution.Problem.Items) {
panic("received solution with incorrect packing list length")
}
weight := 0
value := 0
for i, item := range solution.Problem.Items {
if solution.PackingList[i] {
weight += item.Weight
if weight > solution.Problem.WeightLimit {
return -1
}
value += item.Value
}
}
return value
}
func solutionCrossover(s1, s2 *KnapsackSolution) (o1, o2 *KnapsackSolution) {
o1 = new(KnapsackSolution)
o2 = new(KnapsackSolution)
o1.PackingList, o2.PackingList = genetic.SinglePointCrossover(s1.PackingList, s2.PackingList)
o1.Problem = s1.Problem
o2.Problem = s1.Problem
return
}
func solutionMutation(mutationRate float64) genetic.MutationFunc[*KnapsackSolution] {
mutatePackingList := genetic.RandomizedBinaryMutation(mutationRate)
return func(solution *KnapsackSolution) {
mutatePackingList(solution.PackingList)
}
}
func TestGenetic(t *testing.T) {
t.Parallel()
for _, perfectSolution := range knapsackSolutionFixtures {
perfectFitness := solutionFitness(perfectSolution)
maxGenerations := 1000
elitism := 2
population := genetic.NewPopulation(
60,
perfectSolution.Problem.RandomSolution,
solutionCrossover,
genetic.StaticFitnessFunc(solutionFitness),
genetic.TournamentSelection[*KnapsackSolution](3),
solutionMutation(0.1),
)
expectedAccuracy := 0.99
minimumFitness := int(float64(perfectFitness)*expectedAccuracy) + 1
population.Evolve(minimumFitness, maxGenerations, elitism)
bestSolution, bestFitness := population.Best()
accuracy := float64(bestFitness) / float64(perfectFitness)
if accuracy < expectedAccuracy {
t.Errorf("expected to solve knapsack problem with accuracy of at least %.2f%%; got %.2f%%", expectedAccuracy*100, accuracy*100)
t.Errorf("evolved fitness: %d", bestFitness)
t.Errorf("evolved solution: %s", bestSolution)
t.Errorf("perfect fitness: %d", perfectFitness)
t.Errorf("perfect solution: %s", perfectSolution)
}
}
}