The goal of knapsack problems is to put as much stuff into a container as it will hold, optimizing for constraints such as item weight and size and value. The standard Knapsack Problem adds the limitation that there is only one of each particular item available. In the unbounded variant of the Knapsack Problem there is no limit. This project solves the Unbounded Knapsack Problem (UKP) by improving upon the genetic solver used in the previous post. The code is written in Go.
We’ll start with an easy one so we can understand how it works. We’ll do that by using the item weights, sizes and values from the Rosetta Code page for the Unbounded Knapsack Problem, but with different names, as follows:
| Name |
Value (each) |
Weight |
Volume (each) |
| Bark |
3000 |
0.3 |
.025 |
| Herb |
1800 |
0.2 |
.015 |
| Root |
2500 |
2.0 |
.002 |
The knapsack contents cannot weigh more than 25 units and its maximum volume is 0.25 units. Our goal is to maximize the value of the contents of the knapsack without exceeding either of the weight or volume limits.
Let’s think about how we would solve this problem by hand. We want to maximize the value within the constraints. So we want a high ratio of value to weight and value to volume. And we want as many of those in the bag as we can get. When we can’t stuff any more of the top item into the bag, we fill in the remaining space with the next most valuable item, and so on. This process is known as hill climbing.
First we need a struct to hold the resource information.
type resource struct {
name string
value int
weight float64
volume float64
}
This project uses genes in a new way – as indexes and counts. Each chromosome will have two parts. The first will represent an index into the list of available resources. The second will be the quantity of that resource to take. The candidate gene sequence will be decoded as follows:
func decodeGenes(candidate string, resources []resource, geneSet string) map[resource]int {
resourceCounts := make(map[resource]int, len(candidate)/2)
for i := 0; i < len(candidate); i += 2 {
chromosome := candidate[i : i+2]
resourceId := scale(strings.Index(geneSet, chromosome[0:1]), len(geneSet), len(resources))
resourceCount := strings.Index(geneSet, chromosome[1:2])
resource := resources[resourceId]
resourceCounts[resource] = resourceCounts[resource] + resourceCount
}
return resourceCounts
}
func scale(value, currentMax, newMax int) int {
return value * newMax / currentMax
}
The fitness function will use the decoded resource counts and the resource constraints to determine an appropriate fitness for the candidate.
func getFitness(resourceCounts map[resource]int, maxWeight float64, maxVolume float64) int {
weight := 0.0
volume := 0.0
value := 0
for resource, count := range resourceCounts {
weight += resource.weight * float64(count)
volume += resource.volume * float64(count)
value += resource.value * count
}
if weight > maxWeight || volume > maxVolume {
return -value
}
return int(value)
}
Next is a display function that tells us which resources and how many of each to take and their value (fitness).
func display(resourceCounts map[resource]int, fitness int, elapsed time.Duration) {
label := ""
for resource, count := range resourceCounts {
label += fmt.Sprint(count, " ", resource.name, " ")
}
fmt.Println(
fitness,
"\t",
label,
"\t",
elapsed)
}
The only thing left is to define the resources and invoke the solver:
func main() {
resources := []resource{
{name: "Bark", value: 3000, weight: 0.3, volume: .025},
{name: "Herb", value: 1800, weight: 0.2, volume: .015},
{name: "Root", value: 2500, weight: 2.0, volume: .002},
}
const maxWeight = 25.0
const maxVolume = .25
geneSet := "0123456789ABCDEFGH"
calc := func(candidate string) int {
decoded := decodeGenes(candidate, resources, geneSet)
return getFitness(decoded, maxWeight, maxVolume)
}
start := time.Now()
disp := func(candidate string) {
decoded := decodeGenes(candidate, resources, geneSet)
fitness := getFitness(decoded, maxWeight, maxVolume)
display(decoded, fitness, time.Since(start))
}
var solver = new(genetic.Solver)
solver.MaxSecondsToRunWithoutImprovement = .1
solver.MaxRoundsWithoutImprovement = 2
var best = solver.GetBestUsingHillClimbing(calc, disp, geneSet, 10, 2, math.MaxInt32)
fmt.Println("\nFinal:")
disp(best)
}
Sample output:
$ go run samples/ukp/rosetta/rosetta.go
30000 12 Root 0
33600 12 Root 2 Herb 2.0001ms
36000 2 Bark 12 Root 2.0001ms
37200 12 Root 4 Herb 3.0002ms
39600 2 Herb 2 Bark 12 Root 3.0002ms
44100 2 Herb 9 Root 6 Bark 5.0003ms
49500 9 Root 5 Herb 6 Bark 5.0003ms
50100 2 Herb 9 Root 8 Bark 5.0003ms
51500 8 Bark 11 Root 6.0003ms
52600 8 Bark 10 Root 2 Herb 6.0003ms
54500 11 Root 5 Herb 6 Bark 6.0003ms
Final:
54500 11 Root 6 Bark 5 Herb 248.0142ms
Excellent. A success with a sub-second run time. Also, that result matches one of the four optimal combinations for this problem from the RosettaCode page.
Now, just as there are standard problem sets for the Travelling Salesperson Problem, there are also standard problem sets available for the Unbounded Knapsack Problem. One such set, named exnsd16, comes from the PYAsUKP site.
Let’s use the structure of the code above as a guide to implementing a solver for standard problem sets.
First, the resource data must be imported from the file. The file has the following format:
...
c: 1234 <-- constraint
...
begin data <-- resource data
55 32 <-- weight and value
91 3212
...
832 88
end data
...
sol: <-- begin optimal solution
83 21 58 65 <-- item index, count, weight, value
71 51 13 20
...
This means the parser will have several transitions because we need the constraint and resource data as a minimum. It would also be nice to have the optimal solution info for result verification.
The resource type doesn’t need a volume field:
type resource struct {
name string
value int
weight int
}
Here’s the parser:
func loadResources(routeFileName string) ([]resource, int, map[resource]int) {
parts := make(chan part)
lineHandler := ukpResourceFileHeader
go func() {
for line := range File.EachLine(routeFileName) {
lineHandler = lineHandler(line, parts)
}
close(parts)
}()
resources := make([]resource, 0, 10)
solution := make(map[resource]int)
maxWeight := -1
for part := range parts {
switch {
case part.partType == constraintPart:
maxWeight = parseConstraint(part.line)
case part.partType == resourcePart:
resources = append(resources, parseResource(part.line, len(resources)))
case part.partType == solutionPart:
resourceId, count := parseSolutionResource(part.line)
solution[resources[resourceId-1]] = count
}
}
return resources, maxWeight, solution
}
func parseConstraint(line string) int {
parts := strings.Fields(line)
constraint, err := strconv.Atoi(parts[1])
if err != nil {
panic("failed to parse constraint from '" + line + "'")
}
return constraint
}
func parseResource(line string, totalResources int) resource {
parts := strings.Fields(line)
weight, err := strconv.Atoi(parts[0])
if err != nil {
panic("failed to parse weight from '" + line + "'")
}
value, err := strconv.Atoi(parts[1])
if err != nil {
panic("failed to parse value from '" + line + "'")
}
return resource{
name: fmt.Sprint("Item_" + strconv.Itoa(1+totalResources)),
weight: weight,
value: value,
}
}
func parseSolutionResource(line string) (int, int) {
parts := strings.Fields(line)
resourceId, err := strconv.Atoi(parts[0])
if err != nil {
panic("failed to parse resourceId from '" + line + "'")
}
count, err := strconv.Atoi(parts[1])
if err != nil {
panic("failed to parse count from '" + line + "'")
}
return resourceId, count
}
type ukpLineFn func(line string, parts chan part) ukpLineFn
func ukpResourceFileHeader(line string, parts chan part) ukpLineFn {
if strings.Index(line, "c:") != 0 {
return ukpResourceFileHeader
}
parts <- part{line: line, partType: constraintPart}
return ukpDataHeader
}
func ukpDataHeader(line string, parts chan part) ukpLineFn {
if strings.Index(line, "begin data") != 0 {
return ukpDataHeader
}
return ukpData
}
func ukpData(line string, parts chan part) ukpLineFn {
if strings.Index(line, "end data") != 0 {
parts <- part{line: line, partType: resourcePart}
return ukpData
}
return ukpSolutionHeader
}
func ukpSolutionHeader(line string, parts chan part) ukpLineFn {
if strings.Index(line, "sol:") != 0 {
return ukpSolutionHeader
}
return ukpSolution
}
func ukpSolution(line string, parts chan part) ukpLineFn {
if len(line) > 0 {
parts <- part{line: line, partType: solutionPart}
return ukpSolution
}
return ukpFooter
}
func ukpFooter(line string, parts chan part) ukpLineFn {
return ukpFooter
}
type partType int
type part struct {
line string
partType partType
}
const (
constraintPart partType = 1 + iota
resourcePart
solutionPart
)
A chromosome will still have two parts, the index and count, but this time it will need more genes because the problem we’re solving has 2000 possible resources and the quantities may need to go as high as 160.
If we use hexadecimal values for the geneSet we’ll need 3 genes for the resource index and 2 for the quantity.
const hexLookup = "0123456789ABCDEF"
const numberOfGenesPerChromosome = 5
Here is the decoder:
func decodeGenes(candidate string, resources []resource) map[resource]int {
resourceCounts := make(map[resource]int, len(candidate)/numberOfGenesPerChromosome)
const maxHexValue = 16 * 16 * 16
for i := 0; i < len(candidate); i += numberOfGenesPerChromosome {
chromosome := candidate[i : i+numberOfGenesPerChromosome]
resourceId := scale(hexToInt(chromosome[0:3]), maxHexValue, len(resources))
resourceCount := hexToInt(chromosome[3:numberOfGenesPerChromosome])
resource := resources[resourceId]
resourceCounts[resource] = resourceCounts[resource] + resourceCount
}
return resourceCounts
}
func hexToInt(hex string) int {
value := 0
multiplier := 1
for i := len(hex) - 1; i >= 0; i-- {
value += multiplier * strings.Index(hexLookup, hex[i:i+1])
multiplier *= len(hexLookup)
}
return value
}
func scale(value, currentMax, newMax int) int {
return value * newMax / currentMax
}
Once we’ve decoded the candidate’s gene sequence we can get its fitness:
func getFitness(resourceCounts map[resource]int, maxWeight, optimalFitness int) int {
weight := 0
value := 0
for resource, count := range resourceCounts {
weight += resource.weight * count
value += resource.value * count
}
if weight > maxWeight {
if value == optimalFitness {
return optimalFitness + weight - maxWeight
}
return -value
}
return int(value)
}
And the last utility function is one to display the decoded genes and quantities in a useful format:
func display(resourceCounts map[resource]int, fitness int, elapsed time.Duration, shorten bool) {
label := ""
for resource, count := range resourceCounts {
if count == 0 {
continue
}
if len(label) > 0 {
label += ", "
}
label += fmt.Sprint(count, " of ", resource.name)
}
if shorten && len(label) > 33 {
label = label[:33] + " ..."
}
fmt.Println(
fitness,
" ",
label,
"\t",
elapsed)
}
Finally, here’s the code that glues all the parts together to try to solve the problem.
func main() {
flag.Parse()
if flag.NArg() != 1 {
fmt.Println("Usage: go run standard.go RESOURCEFILEPATH")
return
}
var resourceFileName = flag.Arg(0)
if !File.Exists(resourceFileName) {
fmt.Println("file " + resourceFileName + " does not exist.")
return
}
fmt.Println("using resource file: " + resourceFileName)
resources, maxWeight, solution := loadResources(resourceFileName)
optimalFitness := 0
for resource, count := range solution {
optimalFitness += resource.value * count
}
calc := func(candidate string) int {
decoded := decodeGenes(candidate, resources)
return getFitness(decoded, maxWeight, optimalFitness)
}
start := time.Now()
disp := func(candidate string) {
decoded := decodeGenes(candidate, resources)
fitness := getFitness(decoded, maxWeight, optimalFitness)
display(decoded, fitness, time.Since(start), true)
}
var solver = new(genetic.Solver)
solver.MaxSecondsToRunWithoutImprovement = 5
solver.MaxRoundsWithoutImprovement = 3
var best = solver.GetBestUsingHillClimbing(calc, disp, hexLookup, 10, numberOfGenesPerChromosome, optimalFitness)
fmt.Print("\nFinal: ")
decoded := decodeGenes(best, resources)
fitness := getFitness(decoded, maxWeight, optimalFitness)
display(decoded, fitness, time.Since(start), false)
if fitness == optimalFitness {
fmt.Println("-- that's the optimal solution!")
} else {
percentOptimal := float32(100) * float32(fitness) / float32(optimalFitness)
fmt.Printf("-- that's %f%% optimal\n", percentOptimal)
}
}
Sample output:
using resource file: samples/ukp/data/exnsd16.ukp
1001881 137 of Item_730 3.0002ms
1016358 147 of Item_1698 5.0003ms
1023272 148 of Item_1698 5.0003ms
1023775 155 of Item_480 283.0162ms
1025480 155 of Item_1227 1.2450713s
1025681 157 of Item_1331 2.7771589s
1027260 156 of Item_288 3.4291962s
1027500 156 of Item_288, 6 of Item_1567 3.9722272s
1027540 7 of Item_1567, 156 of Item_288 3.9732273s
1027860 156 of Item_288, 15 of Item_1567 3.9732273s
1028783 156 of Item_288, 1 of Item_1692 4.212241s
1028950 156 of Item_288, 1 of Item_1801 4.212241s
1029261 1 of Item_1810, 156 of Item_288 4.213241s
1029581 156 of Item_288, 1 of Item_1790 4.2452429s
1029663 156 of Item_288, 1 of Item_1248 4.2492431s
1029664 1 of Item_1767, 156 of Item_288 7.4734275s
1029680 156 of Item_288, 1 of Item_987 8.8265049s
Final: 1029680 1 of Item_987, 156 of Item_288 14.0928061s
-- that's the optimal solution!
It doesn’t achieve an optimal solution every time but it does find a solution that’s better than 99 percent optimal almost every time. Here’s the fitness results across 100 runs with 5 seconds to run and a maximum of 3 rounds without improvement:
1029680 21
1029582 3
1029504 1
1029477 1
1029459 1
1029356 1
1029094 1
1028950 2
1028926 1
1028911 1
1028905 2
1028891 1
1028890 1
1028888 1
1028872 1
1028603 1
1028209 1
1028205 1
1028198 1
1028183 10 <- median
1028176 1
1028166 4
1028127 1
1028101 14
1028100 1
1028058 1
1028050 2
1027991 1
1027776 1
1027416 3
1027311 1
1027042 1
1026972 1
1026799 5
1026747 1
1026721 1
1026345 1
1026285 1
1026204 1
1025834 2
1025681 3 <- 99.611626% optimal
The source code for this project is available from my GitHub repository.
Go on to part 6.
Like this:
Like Loading...
