**Fishy Operations**, and kindly contributed to R-bloggers)

Genetic algorithm is a search heuristic. GAs can generate a vast number of possible model solutions and use these to evolve towards an approximation of the best solution of the model. Hereby it mimics evolution in nature.

GA generates a population, the individuals in this population (often
called chromosomes) have a given state. Once the population is
generated, the state of these individuals is evaluated and graded on
their value. The best individuals are then taken and crossed-over - in
order to hopefully generate 'better' offspring - to form the new
population. In some cases the best individuals in the population are
preserved in order to guarantee 'good individuals' in the new generation
(this is called *elitism*).

The GA site by Marek Obitko has a great tutorial for people with no previous knowledge on the subject.

To explain the example I will use my version of the Knapsack problem.

You are going to spend a month in the wilderness. You’re taking a backpack with you, however, the maximum weight it can carry is 20 kilograms. You have a number of survival items available, each with its own number of “survival points”. You’re objective is to maximize the number of survival points.

The following table shows the items you can choose from.

item | survivalpoints | weight |
---|---|---|

pocketknife | 10.00 | 1.00 |

beans | 20.00 | 5.00 |

potatoes | 15.00 | 10.00 |

onions | 2.00 | 1.00 |

sleeping bag | 30.00 | 7.00 |

rope | 10.00 | 5.00 |

compass | 30.00 | 1.00 |

Let's define the dataset and weight constraint;

```
library(genalg)
library(ggplot2)
dataset <- data.frame(item = c("pocketknife", "beans", "potatoes",
"onions", "sleeping bag", "rope", "compass"), survivalpoints = c(10, 20,
15, 2, 30, 10, 30), weight = c(1, 5, 10, 1, 7, 5, 1))
weightlimit <- 20
```

Before creating the model we have to set-up an evaluation function. The evaluation function will evaluate the different individuals (chromosomes) of the population on the value of their gene configuration.

An individual can for example have the following gene configuration:
**1001100**.

Each number in this binary string represents whether or not to take an item with you. A value of 1 refers to putting the specific item in the knapsack while a 0 refers to leave the item at home. Given the example gene configuration we would take the following items;

```
chromosome = c(1, 0, 0, 1, 1, 0, 0)
dataset[chromosome == 1, ]
## item survivalpoints weight
## 1 pocketknife 10 1
## 4 onions 2 1
## 5 sleeping bag 30 7
```

We can check to what amount of surivival points this configuration sums up.

```
cat(chromosome %*% dataset$survivalpoints)
```

```
## 42
```

Above we gave a value to the gene configuration of a given chromosome. This is exactly what the evaluation function does.

The *genalg* algorithm tries to optimize towards the minimum value.
Therefore, the value is calculated as above and multiplied with -1. A
configuration which leads to exceeding the weight constraint returns a
value of 0 (a higher value can also be given).

We define the evaluation function as follows.

```
evalFunc <- function(x) {
current_solution_survivalpoints <- x %*% dataset$survivalpoints
current_solution_weight <- x %*% dataset$weight
if (current_solution_weight > weightlimit)
return(0) else return(-current_solution_survivalpoints)
}
```

Next, we choose the number of iterations, design and run the model.

```
iter = 100
GAmodel <- rbga.bin(size = 7, popSize = 200, iters = iter, mutationChance = 0.01,
elitism = T, evalFunc = evalFunc)
cat(summary.rbga(GAmodel))
```

```
## GA Settings
## Type = binary chromosome
## Population size = 200
## Number of Generations = 100
## Elitism = TRUE
## Mutation Chance = 0.01
##
## Search Domain
## Var 1 = [,]
## Var 0 = [,]
##
## GA Results
## Best Solution : 1 1 0 1 1 1 1
```

The best solution is found to be **1101111**. This leads us to take the
following items with us on our trip into the wild.

```
solution = c(1, 1, 0, 1, 1, 1, 1)
dataset[solution == 1, ]
## item survivalpoints weight
## 1 pocketknife 10 1
## 2 beans 20 5
## 4 onions 2 1
## 5 sleeping bag 30 7
## 6 rope 10 5
## 7 compass 30 1
```

This in turn gives us the total number of survival points.

```
# solution vs available
cat(paste(solution %*% dataset$survivalpoints, "/", sum(dataset$survivalpoints)))
```

```
## 102 / 117
```

Let's visualize how the model evolves.

```
animate_plot <- function(x) {
for (i in seq(1, iter)) {
temp <- data.frame(Generation = c(seq(1, i), seq(1, i)), Variable = c(rep("mean",
i), rep("best", i)), Survivalpoints = c(-GAmodel$mean[1:i], -GAmodel$best[1:i]))
pl <- ggplot(temp, aes(x = Generation, y = Survivalpoints, group = Variable,
colour = Variable)) + geom_line() + scale_x_continuous(limits = c(0,
iter)) + scale_y_continuous(limits = c(0, 110)) + geom_hline(y = max(temp$Survivalpoints),
lty = 2) + annotate("text", x = 1, y = max(temp$Survivalpoints) +
2, hjust = 0, size = 3, color = "black", label = paste("Best solution:",
max(temp$Survivalpoints))) + scale_colour_brewer(palette = "Set1") +
opts(title = "Evolution Knapsack optimization model")
print(pl)
}
}
# in order to save the animation
library(animation)
saveMovie(animate_plot(), interval = 0.1, outdir = getwd())
```

The x-axis denotes the different generations. The blue line shows the mean solution of the entire population of that generation, while the red line shows the best solution of that generation. As you can see, it takes the model only a few generations to hit the best solution, after that it is just a matter of time until the mean of the population of subsequent generations evolves towards the best solution.

For more information on genetic algorithms, check out:

- Wikipedia
- Introduction by Marek Obitko
- A Field Guide to Genetic Programming
- A Genetic Algorithm Tutorial

**leave a comment**for the author, please follow the link and comment on his blog:

**Fishy Operations**.

R-bloggers.com offers

**daily e-mail updates**about R news and tutorials on topics such as: visualization (ggplot2, Boxplots, maps, animation), programming (RStudio, Sweave, LaTeX, SQL, Eclipse, git, hadoop, Web Scraping) statistics (regression, PCA, time series, trading) and more...