artificial life
Chapter 5: Genetic Algorithms
5.6 0-1 Knapsack Applet
A Java Applet that allows the user to define a 0-1 Knapsack Problem and use a Genetic Algorithm to solve it is implemented as part of this project.
The Genetic Algorithm for the applet was developed independent of anything specific to the 0-1 Knapsack Problem so that the library could be reused to create other Genetic Algorithm solutions.
The applet has three different panels, each of which control a different component of the definition and analysis of the problem. The first panel allows the user to define the capacity of the knapsack and define the possible items to be placed in the knapsack. The second panel allows the user to find the optimal solution to the problem is using a naïve algorithm that simply searches all possible solutions. The third panel allows the user to define the various attributes of the Genetic Algorithm and analyzes the results of the algorithm.
Panel 1
The first panel of the Knapsack Applet allows the user to define the problem. The set of items that can possibly be in the sack is shown in the main list window of the panel. The user can add items to this list or delete items from it. The capacity of the sack is also set on this panel. The applet is initialized with 18 random objects on the list. Descriptions of the specific components of the panel follow:
Main List: A list of all the possible items for the knapsack. Each item has an individual Weight and Value that are used to calculate the item’s suitability in the knapsack.
Item Weight Field: A field for the user to define the weight of any items to be added to the list of possible items.
Item Value Field: A field for the user to define the value of any items to be added to the list of possible items.
Add Item Button: This button allows the user to add an item to the list with the attributes defined in the Item Weight and Item Value Fields.
Add Random Item Button: This button allows the user to add an item to the list with randomly chosen attribute values. The values will be bounded between 0 and the value for the respective attribute field.
Delete Button: This button allows the user to delete selected items from the list. Multiple item deletions are allowed.
Sack Capacity: A field that determines the capacity of the sack to be used in the problem.
Panel 2
The second panel of the Knapsack Applet allows the user to find the optimal solution to the defined problem using a naïve algorithm that searches through the entire search space. If the number of items in the list becomes larger than 23 then the optimal solution is not found, since the search space becomes prohibitively large. The optimal solution is presented in both its genotype representation and as a list with allowed items selected. This is done so that the user can observe the relationship between genotype representation and list that they defined.
Best Genotype: This is the genotype representation of the optimal solution to the defined problem.
Best Score: This is the Fitness value of the best individual found. It is equal to the sum of the values of all the items placed in the knapsack.
Size of the Search Space: The number of possible solutions the algorithm had to search through to ensure the optimal solution was found. This number is equal to 2n where n is the number of possible items to be placed in the sack. This number is calculated even when the optimal solution cannot be found with the brute force technique.
Find Best Configuration Button: This button initializes the naïve algorithm to calculate the optimal solution to the problem. This can take some time to calculate as larger problems are explored, the user is advised to use caution when using this function on slower machines.
Main List: The list of possible items. Those items that the optimal solution allows are highlighted.
Panel 3
The third panel of the Knapsack Applet allows the user to apply a Genetic Algorithm to the problem. The applet allows the user to create a GA that uses Crossover, Mutation or both to generate descendents. The applet shows the user the best score and genotype found and displays a graph showing the progress of the GA.
Reset Genetic Algorithm Button: This button resets the Genetic Algorithm and generates a new random population. The button is used for any changes are made to the state of the Genetic Algorithm; if the definition of the problem is changed on one of the other panels then the algorithm is automatically reset.
Crossover Checkbox: Allows the user to toggle whether or not the algorithm uses crossover in regeneration. The algorithm must be reset for this change to take effect.
Mutation Checkbox: Allows the user to toggle whether or not the algorithm uses mutation in regeneration. The algorithm must be reset for this change to take effect.
Mutation Rate Field: This allows the user to determine how likely a mutation is during regeneration. A value of .01 means that an attribute has a 1/100 likelihood of mutating. The algorithm must be reset for this change to take effect.
Population Size: Allows the user to set the size of the population that the GA creates. Larger populations usually result in finding the optimal solution sooner, but take longer to evaluate and regenerate since there are more individuals. The algorithm must be reset for any changes to take effect.
Advance GA One Generation: This button initializes GA regeneration and evaluation of one generation.
Advance GA Multiple Generations: Allows the user to advance the GA as many generations as indicated in the field to the button’s right.
Best GA Score: Displays the fitness of the best solution found by the GA.
Best Genotype Found: Displays the genotype representation of the best solution found by the GA.
Generations Advanced: Displays the number of generations generated and evaluated.
Main Graph: This graph displays a history of the GA fitness. The graph shows fitness vs. generation. The top (red) points show the fitness of the best solution found in a given generation. The bottom (blue) points show the average fitness of the given generation.
This project is developed in two parts, a generic Genetic Algorithm library and a solution to the Knapsack problem that uses this library.
The GA library is comprised of three .java files:
The Knapsack Solution has four .java files: