/** KnapsackApplet.java * J Scott Cameron * This applet allows the user to manipulate a knapsack object * and use a Genetic Algorithm to find the optimal solution*/ import javax.swing.*; import java.awt.*; import java.applet.*; import Knapsack.*; import GeneticAlgorithm.*; import GaGraph.*; import java.util.*; import java.awt.event.*; import java.io.*; public class KnapsackApplet extends JApplet implements ActionListener,ItemListener{ private Knapsack knapsack;/* Knapsack for user to manipulate */ private GeneticAlgorithm ga;/* Genetic Algorith for user to control*/ /*Swing Components*/ private JButton addItem; private JButton addRandItem; private JButton deleteItem; private JTextField itemWeight; private JTextField itemValue; private JTextField sackCapacity; private JList dataList,dataList2 ; private Vector gaHistory; private Vector gaAvgHistory; private int numItems; private JButton findBest; private JLabel bestDetScore; private JLabel bestDetGen; private JLabel genesChecked; private JLabel lNumItems; private JLabel bestGAScore; private JLabel bestGAGen; private JLabel generationsAdvanced; private JButton resetGA; private JButton nextGen; private JButton manyGens; private JTextField numGens; private JTextField popSize; private JCheckBox mutation; private JCheckBox crossover; private JTextField mutationRate; private Genotype bestGA;/*best GA found*/ private int generation;/* current generation */ private GaGraph graph;/* graph of GA values */ private Random random; /* bools to control behavior of GA */ private boolean crossoverBool = true; private boolean mutationBool = true; // This is a hack to avoid an ugly error message in 1.1. public KnapsackApplet() { getRootPane().putClientProperty("defeatSystemEventQueueCheck", Boolean.TRUE); } public void init() { /* sets Look and Feel to classic Swing look */ try { UIManager.setLookAndFeel( UIManager.getCrossPlatformLookAndFeelClassName()); } catch (Exception e) { } numItems = 0; random = new Random(); /* initializes Knapsack to a capacity of 200 */ knapsack = new Knapsack(200); /* creates 18 random objects as possible items */ for(int i=0;i<18;i++) { knapsack.addItem((Math.abs(random.nextInt())+1)%50, (Math.abs(random.nextInt())+1)%50); numItems++; } /*initialize Swing components*/ JTabbedPane tp = new JTabbedPane(); tp.setBorder(BorderFactory.createMatteBorder(1,1,2,2,Color.black)); getContentPane().add(tp, BorderLayout.CENTER); tp.addTab("Knapsack Definition",designPanel()); tp.addTab("Find Best Knapsack (naive)",detPanel()); tp.addTab("Use Genetic Algorithm",gaPanel()); } /*interprests messages when buttons are pressed and *calls the appropriate method*/ public void actionPerformed(ActionEvent evt) { JButton theItem = (JButton) evt.getSource(); if (theItem == addItem) addPressed(); else if (theItem == addRandItem) addRandPressed(); else if (theItem ==deleteItem) deletePressed(); else if (theItem == findBest) findBestPressed(); else if (theItem == resetGA) resetGAPressed(); else if (theItem == nextGen) nextGenPressed(); else if (theItem == manyGens) manyGensPressed(); } /*listens for changes in the crossover and mutation *checkboxes and updates the associated bools appropriately*/ public void itemStateChanged(ItemEvent p1) { JCheckBox theItem = (JCheckBox) p1.getItemSelectable(); if(theItem == mutation) { if(p1.getStateChange() == ItemEvent.DESELECTED) {mutationBool = false; } else {mutationBool = true; } } else if(theItem ==crossover) { if(p1.getStateChange() ==ItemEvent.DESELECTED) {crossoverBool = false; } else {crossoverBool = true; } } } /* resets the Genetic Algorithm with current parameters */ public void resetGAPressed() { knapsack.setCapacity( (new Integer(sackCapacity.getText())).intValue()); /* initializes Genetic Algorithm using the information * currently entered in the applet */ ga = new GeneticAlgorithm(knapsack.possibleItems(), (new Integer(popSize.getText())).intValue(), crossoverBool,mutationBool, (new Double(mutationRate.getText())).doubleValue(), knapsack,"testFitness"); /* initializes the GA's population */ ga.initPopulation(); /* evaluates the population */ ga.evaluatePopulation(); /* resets the vectors used with the graph */ gaHistory = new Vector(); gaAvgHistory = new Vector(); /* resets the bestGA */ bestGA = ga.best(); /* adds the bestGA to the graph */ gaHistory.add(bestGA); /* add the current average to the graph */ gaAvgHistory.add(new Double(ga.avg())); /* sets the generation to 0 */ generation = 0; /* update swing fields concerning GA performance */ StringWriter sw = new StringWriter(); sw.write("Best GA Genotype Found: "); sw.write(bestGA.toString()); bestGAGen.setText(sw.toString()); sw= new StringWriter(); sw.write("Best GA Score: "); sw.write((new Integer(bestGA.getRating())).toString()); bestGAScore.setText(sw.toString()); sw= new StringWriter(); sw.write("Generations Advanced: "); sw.write((new Integer(generation)).toString()); generationsAdvanced.setText(sw.toString()); /* update the graph */ graph.updateGraph(gaHistory,gaAvgHistory); } /* advances the GA by a single generation */ public void nextGenPressed() { /* regenerate and evaluate GA population*/ generation++; ga.regeneratePopulation(); ga.evaluatePopulation(); /* update graph*/ gaHistory.add(ga.best()); gaAvgHistory.add(new Double(ga.avg())); bestGA = ga.best(); graph.updateGraph(gaHistory,gaAvgHistory); /* update display with GA performance */ StringWriter sw = new StringWriter(); sw.write("Best GA Genotype Found: "); sw.write(bestGA.toString()); bestGAGen.setText(sw.toString()); sw= new StringWriter(); sw.write("Best GA Score: "); sw.write((new Integer(bestGA.getRating())).toString()); bestGAScore.setText(sw.toString()); sw= new StringWriter(); sw.write("Generations Advanced: "); sw.write((new Integer(generation)).toString()); generationsAdvanced.setText(sw.toString()); } /* advances the GA by a multiple generations */ public void manyGensPressed() { /*find out how many generations to advance GA */ int gens = (new Integer(numGens.getText())).intValue(); /*regenerate, evaluate GA and update appropriate Vectors*/ for(int i=0;i=0;i--) { knapsack.removeItem(indices[i]); } /*update Swing components and reset GA to reflect change*/ dataList.setListData(knapsack.getItems()); dataList2.setListData(knapsack.getItems()); resetGAPressed(); } /* use a naive algorithm to find the best possible knapsack*/ public void findBestPressed() { knapsack.setCapacity( (new Integer( sackCapacity.getText())).intValue()); StringWriter sw= new StringWriter(); /* the number of possible knapsacks is larger than 23 * don't compute optimal knapsakc, it will take far too * long */ if(knapsack.getItems().size() <= 23) { /* get best knapsack */ boolean best[] = knapsack.findOptimized(); /* update Swing display with info */ int itemsInSack = 0; sw.write("Best Score: "); sw.write((new Integer(knapsack.testFitness(best))).toString()); bestDetScore.setText(sw.toString()); sw= new StringWriter(); sw.write("Best Genotype: "); for(int i=0;i