You've decided to embrace the outdoor lifestyle. This is your first camping trip and you've just had a whole bunch of brand-new camping items delivered. Unfortunately, you ordered the wrong size of knapsack - it can only carry 3.5kg of items and you don't have sufficient time to get it replaced.
So, what items will you take with you? Fortunately, the camping site has agreed to lend you essential items, for example a tent (but not your nice, new tent and fluffy sleeping bag).
Here is the list of the original 20 items that you intended to pack, before the smaller knapsack arrived:
Radio: weight 0.5 kg
Additional canned food: 1.5g
Your favourite mug: 0.2kg
Change of walking boots: 2kg
Pullover: 0.5kg
Protein drink: 0.3kg
Slab of cake: 0.25kg
Fruit: 1.25kg
Tent: 2.15kg
Water bottle: 0.15kg
Kettle: 0.2kg
Pan, plates: 1.1kg
Gas cooker incl cartridge: 0.75kg
Sleeping mat: 0.3kg
Sleeping bag: 0.9kg
Lantern incl. battery: 0.2kg
First Aid kit: 0.175kg
Thick socks: 0.15kg
Rainproof coat cover: 0.1kg
Woolly hat: 0.175kg
Clearly, you can no longer pack all of these items in the knapsack, so which do you select?
The Knapsack Problem
This is an example of what is known as the knapsack problem - determining the optimum combination of items that meet - in this instance - a constraint; the 3.5kg limit of the knapsack.
You decide to assign a relative benefit to each of the items; the list now becomes:
Radio: 0.5kg, benefit: 10
Additional canned food: 1.5g, benefit: 15
Favourite mug: 0.2kg, benefit: 4
Change of walking boots: 2kg, benefit: 17
Pullover: 0.5kg, benefit: 6
Protein drink: 0.3kg, benefit: 4
Slab of cake: 0.25kg, benefit: 3
Fruit: 1.25kg, benefit: 12
Tent: 2.15kg, benefit: 6
Water bottle: 0.15kg, benefit: 4
Kettle: 0.2kg, benefit: 4
Pan, plates: 1.1kg, benefit: 6
Gas cooker incl cartridge: 0.75kg, benefit: 5
Sleeping mat: 0.3kg, benefit: 5
Sleeping bag: 0.9kg, benefit: 7
Lantern incl. battery: 0.2kg, benefit: 3
First Aid kit: 0.175kg, benefit: 4
Thick socks: 0.15kg, benefit: 3
Rainproof coat cover: 0.1kg, benefit: 3
Woolly hat: 0.175kg, benefit: 2.5
The higher the benefit, the more valuable it is for you to pack the item.
Based on the above list, what combination of items provides the highest (or close to it) benefit?
One way to solve the problem is to calculate the total benefit for every combination of the items, ignoring those whose total weight exceed the limit of 3.5kg.
Of course, there may be more than one combination that delivers the same benefit. But that's ok, just use an additional criterion, for example go with the lightest combination.
Consider the scenario where there are only three items to choose from; each item could be included or excluded. Hence, this would give rise to 8 combinations (for example: pack item#1, leave #2, pack #3), ie 2 to the power of 3 (or 2^3). The total weight is calculated for each combination and if it exceeds 3.5kg, it is given a total benefit of 0.
Applying the same approach to all 20 items, means we would need to check 2^20 = 1,048,576 combinations. Too laborious to do by hand, but no problem for a computer.
However, imagine that there were 40 items available from which to choose - not a very large number of items - how many combinations would then need to be processed?
The answer is 2^40 = 1,099,511,627,776 , or more than 1 trillion items! And therein lies the problem. Yes, this approach will identify the optimum combination(s), but it will require a lot of computing power and time - even with a processing power of 10 million combination per second, will take more than a day.
Is there an alternative approach which could provide an acceptable total benefit, but without the exponential demands on processing power and associated time?
Enter the Genetic Algorithm.
Darwin and the Genetic Algorithm (GA)
In the same way that Deep Learning is loosely modelled on the brain's cognitive function, GA's have their roots in another natural process, Darwin's Theory of Evolution and Natural Selection.
A GA begins with a population of random chromosomes. Each chromosome represents an outcome that we may be interested in. Using our knapsack example, each chromosome would represent the potential state of each item. This is represented in a binary code, with '1' meaning an item (eg radio) is included in the knapsack and a '0' meaning it is excluded. This string of binary digits that represent the included/excluded status of the items is referred to as a chromosome.
In our knapsack example, each chromosome would consist of 20 bits (or genes in GA parlance), one bit to represent each of the items above. A binary '1' would signify the presence of the item in the knapsack, a '0' its absence. Hence, assuming the list of 20 items above is read from top to bottom, the following chromosome:
10001000010010100000
represents the scenario where only the radio, pullover, water bottle, gas cooker+cartridge, and sleeping bag are included in the knapsack, all other items would be excluded. Of course, given the combinations are determined randomly, the total weight of the selected items may exceed the 3.5kg limit; such chromosomes would be rejected and would not make it through to the next generation (unless recombination or mutation - see below - grants them some benefit).
To reiterate, for the initial state, these chromosomes are generated randomly. Then, as in natural selection, each is assessed for fitness. In our example, this means the total calculated benefit.
If the total calculated benefit, for a specific chromosome, exceeds the minimum benefit that we require, then that chromosome(s) is the solution and only needs to be decoded to identify the relevant items that are to be packed in the knapsack.
If the total benefit falls below the minimum requirement, we iterate over another generation. But, the question is, what chromosomes are promoted to the next generation?
A set of stratagems are available to determine what chromosomes are promoted to the next generation, including:
elitism: for example, promoting the 5% of chromosomes with the highest benefits in the existing generation
tournament selection: randomly selecting (usually) 4-8 chromosomes and promoting the chromosome with the highest benefit. This process is continued until the next generation's population has been created
crossover/recombination: pairs of chromosomes from the current generation are selected and parts of their chromosomes are interchanged, so the resultant chromosomes have genes from both 'parents'
mutation: just as in nature, mutations occur at the gene level. Similarly, in GA, there is a small probability that each gene, ie bit, may flip state, for example from a '1' to '0'.
Each of these stratagems help to increase the probability that fitness will continually improve through successive generations.
Please note, as in the natural world, simply selecting the highest benefit chromosomes (elitism) to promote to the next generation may not result in the highest benefit overall. After all, Einstein's parents were not genius' also!
We then repeat the process, until the relevant minimum benefit has been achieved, or it is no longer improving (for example, after 100 generations).
Let's talk about fitness
Determining fitness has a central role in identifying candidates that will be promoted to the next generation. Unlike the underlying differential calculus of Deep Neural Networks, there is no requirement for fitness to be mathematically-based, For example, with our knapsack, we could have added an extra item, 'spare gas cartridge'. This would have a conditional benefit - specifically, if the 'Gas cooker' had been selected, the spare cartridge would have a benefit of (say) '2', but zero otherwise.
The GA timescale does not increase exponentially with the length of the chromosome (ie number of items), so provides an effective approach for determining an iterative solution that can be bounded by multiple constraints across many items.
The GA does have two potential drawbacks:
Because the initial population is drawn at random, it may never reach a high-level of fitness. However, this risk can be minimised by having a suitable large, random population.
The trade-off for avoiding an exponential growth in computer processing requirements as the chromosome length increases is that the best outcome may never be selected. Again, the element of randomness and population size reduces that risk. It also requires careful consideration for setting the 'required fitness level'.
Machine Learning
The GA is a good example of Machine Learning as it is not deterministic in nature.
Instead, it applies an iterative approach to transforming a set of input conditions to a target output.
Back to our knapsack
The above GA was implemented as a computer model and run for 8 'generations', using a population of 500 chromosomes. Using elitism, the top 5% of chromosomes were promoted to succeeding generations. In addition, tournament selection was used across the population; for each successive chromosome, the highest benefit chromosome out of 6 randomly chromosomes was selected.
Initially, a significant number of chromosomes had zero benefit (due to the total weight of their items exceeding 3.5kg). However, the selection processes outlined in the previous paragraph rapidly eliminated these chromosomes in succeeding generations.
After about 5 generations, the peak benefit was found - not necessarily the highest possible, but within this set of generations.
Two 'highest benefit' chromosomes were observed; both delivering a total benefit of 51:
Outcome #1: Pack the following in the knapsack: Thick socks, First Aid kit, Sleeping bag, Sleeping mat, Kettle, Water bottle, Protein drink, Pullover, Favourite mug, Radio. Total weight: 3.375kg.
Outcome #2: Pack: Thick socks, First Aid kit, Lantern incl. battery, Sleeping mat, Gas cooker incl cartridge, Kettle, Water bottle, Slab of cake, Protein drink, Pullover, Radio. Total weight: 3.475kg
And how good are these results?
As an indicator of performance, we can calculate the average benefit per kg and then use this to determine what the total benefit would be, based on an 'average' outcome. And then compare this with our results.
Across all 20 items, there is an average benefit of 9.61 per kg.
Hence, for Outcome #1, with at total weight of 3.375kg, the average benefit would be 32.44, whereas the actual outcome is 51, therefore exceeding the average by 57.2%. Following the same approach for Outcome #2,Outcome #2 also exceeds the average, but by slightly less; 52.7% as it is slightly heavier.
This code was run on a desktop computer and took 0.21 seconds to execute.
A further run produced a benefit of 55.5, using all 3.5kgs of available weight:
the knapsack would contain: Woolly hat, Rainproof coat cover, Thick socks, First Aid kit, Sleeping mat, Kettle, Water bottle, Fruit, Protein drink, Favourite mug, Radio
the total benefit exceeded the average by 65%
the run time for this outcome: 0.22 seconds.
Going in DEAP
DEAP (Distributed Evolutionary Algorithms in Python) is a framework to facilitate the development of genetic algorithms. Unlike the examples above - which were coded from scratch - DEAP was used to model the same knapsack problem below:
As can be seen, this also hits a maximum fitness of 55.5 - with a different set of items, but with the same all-up weight of 3.5kg. In this DEAP example, more sophisticated genetic modelling was used, including a population of 300, tournament selection, recombination (or 'mating' as it's more commonly called!) and mutations. As you can see, it hit the maximum fitness in fewer than 20 generations (with a tournament size of 3; increasing it to 6 results in maximum fitness being reached in 5 generations.
UPDATE: a subsequent run delivered the same total benefit with a total weight of 3.2kgs. The knapsack would then contain:
Radio, Favourite mug, Pullover, Protein drink, Slab of cake, Water bottle, Kettle,
Lantern incl battery, First Aid kit, Thick socks, Rainproof coat cover, Woolly hat
the total benefit exceeded the average by 79%
See if you can come up with a higher total benefit, or the same total benefit for a lower weight!
Vehicle Routing Problem
Although simple in concept, because of the potential number of different route combinations, planning efficient vehicle routes can be notoriously challenging,
Consider the following example: you have to visit 29 locations, all starting from the same location. How many different routes are there? The answer is 28!/2, or more than 152,144,172,305,857,000,000,000,000,000 !
Just to spice things up a bit, let's also assume that you have 6 vehicles available to cover these routes (as the locations are some significant distance apart).
Our aim is to minimise the greatest distance travelled by each vehicle along any given route. Finally, to ensure that the distances driven are reasonably well-divided between the 6 vehicles, let's seek to minimise the standard deviation of the 6 journeys.
Stop for a minute and imagine how you would set about solving this problem. Pretty tough, huh?
Improving vehicle routes is another challenge that is well-suited to GAs.
The example below shows a potential solution to our problem - a minimum single journey of 2,658 kms and a standard deviation of 56 kms across all 6 related journeys.
Train timetables
Determining a train timetable is notoriously difficult, because of the many hard and soft constraints, and variables. The 'iterate and select to improve fitness' approach of the GA provides a viable approach to establishing solutions.
For example, see the paper by Omid Gholami and Yuri Sotskov, Train routing and timetabling via a genetic algorithm (IFAC Symposium, 2012).
Conclusion
Genetic algorithms often provide an effective means of solving problems that have constraints (whether hard or soft) and require an iterative approach to improving fitness. Importantly, the computational complexity does not increase exponentially with the length of the GA chromosomes.
Problem types that are well-suited to GA include:
Vehicle routing problems
Scheduling applications
Robot Trajectory Generation
Comments