artificial life

Chapter 5: Genetic Algorithms

5.3 Representation and Evaluation

The first step in creating a genetic algorithm is to determine how a solution can be represented; this will be the template for which the genotypes are randomly generated. In the case of the 0-1 Knapsack problem there are n items that may or may not be placed in the knapsack. A solution is represented by a vector of n bits, if the bit has value of 1 then that item is placed in the knapsack, a value of 0 means the item is left behind.

The next step is to prepare a fitness evaluation for a possible solution. The fitness function of the knapsack problem adds up the weights and values of the population of solutions. If the sum weight of the items is greater than the capacity then a fitness lower than the fitness of the lowest successful knapsack is given, since it is not an acceptable solution to the problem. If the weight constraint is met then the fitness for the solution is equal to the sum of alues of the items in the sack.

Figure 5.1 illustrates the representation and evaluation of a possible 0-1 Knapsack problem. In this case there are 10 different objects, A-J, which can be put into a sack of capacity 100. Each object has its own Weight and Value that are used to evaluate possible solutions. The solutions are encoded in a 10-bit vector, with each bit representing the presence of the respective object. For example, solution (a) is ‘1100100000’, this indicates that items A, B and E are placed in the sack and all others are left out. This gives the sack a Weight of 45 and a Value of 58. Since the sack is well under capacity, the Fitness for this individual is equal to its Value, in this case 58. The figure shows 10 randomly generated bit-vectors. Many of these are unacceptable solutions, as their Weight exceeds the capacity of the knapsack. In these cases the Fitness is set to the capacity Weight (100) minus the Weight of the individual.