/* Genetic Knapsack Problem Solver
(c) 1998 by J. L. Pe
Java 1.0 source code follows */
import java.applet.Applet;
import java.awt.*;
import java.util.*;
public class Gks extends Applet implements Runnable
{
int numSpoints;
int cycleNumber = 0;
int delay = 400;
int[] sizes = {3, 121, 345, 34, 67, 380, 223, 169, 10, 12, 56, 22, 52, 499, 419, 442, 99, 7, 29, 30, 144, 26, 2, 676, 147, 8, 188, 16};
// packet sizes
int[] distances; // distances of solutions from knapsack capacity
int[] extremes;
int[] zero;
int[] temp;
int[][] delta; // used to initialize solutions array
int numSizes;
int winner;
int knapsackLimit;
double matingThreshold;
Solution[] solutions;
Solution topScorer;
Rectangle r;
int w, h;
TextArea ta, sizesTextArea;
Choice choice;
Panel masterPanel, sizesPanel, limitPanel, buttonPanel;
Label sizesLabel, limitLabel, solutionLabel, choiceLabel;
TextField limitTextField, solutionTextField;
Button enterButton, startButton, aboutButton;
boolean startFlag = true;
Thread paintThread;
Font f = new Font("Serif", Font.PLAIN, 10);
StringTokenizer st;
String sizesString, limitString, solutionString;
int sumUp(int[] addends)
{
int sum = 0;
for (int i = 0; i < addends.length; i++)
{
sum += addends[i];
}
return sum;
}
int distance(Solution s) // measures distance from knapsack limit, i.e., "fitness"
{
return knapsackLimit - sumUp(s.genes);
}
boolean isValidSolution(int[] candidate)
{
if (sumUp(candidate) <= knapsackLimit)
{
return true;
}else
{
return false;
}
}
int[] getExtremes(int[] distances)
{
int result[] = new int[4]; // return min distance, index of minimizer solution, max distance, index of maximizer solution
int min = 9000000;
int max = -9000000;
int minimizer = 0;
int maximizer = 0;
for (int i = 0; i < distances.length; i++)
{
if (distances[i] < min)
{
min = distances[i];
minimizer = i;
}
if (distances[i] > max)
{
max = distances[i];
maximizer = i;
}
}
result[0] = min;
result[1] = minimizer;
result[2] = max;
result[3] = maximizer;
return result;
}
int getDifferentNumber(int value1, int value2, int maxValue) // gets a random integer different from values 1, 2 from range 0 to maxValue, or returns 0 if none
{
int randint = 0, residue = 0, result = 0;
randint = (int)(maxValue * Math.random());
for (int i = randint; i < randint + maxValue; i++)
{
residue = randint % maxValue;
if ((i != value1) && (i != value2))
{
result = residue;
break;
}
}
return result;
}
void initSolutions()
{
int i = 0;
delta = new int[numSpoints][numSizes];
for (i = 0; i < numSpoints; i++)
{
delta[i][i] = sizes[i];
} // entries of delta initialized to 0 in declaration
solutions = new Solution[numSpoints];
distances = new int[numSpoints];
for (i = 0; i < numSpoints; i++)
{
solutions[i] = new Solution(delta[i]);
distances[i] = distance(solutions[i]);
}
zero = new int[numSizes]; // entries initialized to 0 by compiler
topScorer = new Solution(zero);
winner = 0;
}
public void init()
{
setLayout(new BorderLayout());
setBackground(Color.white);
setForeground(Color.black);
setFont(f);
r = bounds();
w = r.width;
h = r.height;
numSpoints = 16;
numSizes = sizes.length;
knapsackLimit = 2000;
matingThreshold = .3;
initSolutions();
extremes = new int[4];
temp = new int[numSizes];
masterPanel = new Panel();
masterPanel.setLayout(new BorderLayout());
masterPanel.setBackground(Color.lightGray);
masterPanel.setForeground(Color.black);
sizesPanel = new Panel();
sizesLabel = new Label("Enter packet sizes: ", Label.CENTER);
sizesPanel.add(sizesLabel);
sizesTextArea = new TextArea(2, 90);
sizesTextArea.setText("3 121 345 34 67 380 223 169 10 12 56 22 52 499 419 442 99 7 29 30 144 26 2 676 147 8 188 16");
sizesPanel.add(sizesTextArea);
masterPanel.add(sizesPanel, "Center");
limitPanel = new Panel();
choiceLabel = new Label(" Evolution rate:");
limitPanel.add(choiceLabel);
choice = new Choice();
choice.setBackground(Color.white);
choice.addItem("Moderate");
choice.addItem("Low");
choice.addItem("High");
limitPanel.add(choice);
limitLabel = new Label("Enter knapsack size: ", Label.CENTER);
limitPanel.add(limitLabel);
limitTextField = new TextField(8);
limitTextField.setText("2000");
limitPanel.add(limitTextField);
solutionLabel = new Label("Enter number of solutions: ", Label.CENTER);
limitPanel.add(solutionLabel);
solutionTextField = new TextField(8);
solutionTextField.setText("" + numSpoints);
limitPanel.add(solutionTextField);
masterPanel.add(limitPanel, "North");
buttonPanel = new Panel();
aboutButton = new Button("About");
buttonPanel.add(aboutButton);
enterButton = new Button("ENTER");
buttonPanel.add(enterButton);
startButton = new Button("START/Pause");
buttonPanel.add(startButton);
masterPanel.add(buttonPanel, "South");
add(masterPanel, "South");
ta = new TextArea(100, 100);
add(ta, "Center");
paintThread = new Thread(this);
paintThread.start();
}
public void run()
{
int minimizer = 0, maximizer = 0;
int i = 0, mate = 0, mutant = 0;
double determinant = 0;
StringBuffer answer;
while(true)
{
try
{
Thread.sleep(delay);
}
catch(InterruptedException iexp){}
cycleNumber++;
// mate if determinant is larger than matingThreshold
determinant = Math.random();
if (determinant > matingThreshold)
{
// get the fittest and least fit solutions
extremes = getExtremes(distances);
minimizer = extremes[1];
maximizer = extremes[3];
// mate randomly selected non-extreme solution with minimizer,
// and replace maximizer by offspring, if valid solution was obtained
for (i = 0; i < numSizes; i++)
{
temp[i] = (solutions[maximizer]).genes[i];
}
mate = getDifferentNumber(minimizer, maximizer, numSpoints);
(solutions[minimizer]).mate(solutions[mate], solutions[maximizer]);
if (!(isValidSolution((solutions[maximizer]).genes)))
{
for (i = 0; i < numSizes; i++)
{
(solutions[maximizer]).genes[i] = temp[i];
}
}else
{
//update distances array
distances[maximizer] = distance(solutions[maximizer]);
}
}
// mutate a random solution
mutant = (int)(numSpoints * Math.random());
if (mutant == numSpoints)
{
mutant--;
}
solutions[mutant].mutate(sizes, knapsackLimit);
// update distances array
distances[mutant] = distance(solutions[mutant]);
// now get the fittest solution after possible mating and mutation cycles
extremes = getExtremes(distances);
minimizer = extremes[1];
winner = minimizer;
// if necessary, update topScorer
if (distance(solutions[winner]) < distance(topScorer))
{
for (i = 0; i < numSizes; i++)
{
(topScorer.genes)[i] = ((solutions[winner]).genes)[i];
}
}
answer = new StringBuffer("");
answer.append(" Knapsack capacity = ");
answer.append(knapsackLimit);
answer.append("; ");
answer.append(numSizes);
answer.append(" packet sizes:");
answer.append("\n");
for (i = 0; i < numSizes; i++)
{
(answer.append(" ")).append(sizes[i]);
}
answer.append("\n");
(answer.append("Current optimal fit = ")).append(sumUp(topScorer.genes));
(answer.append(" / ")).appen
Gks.zip_GKS_genetic knapsack_knapsack c_visual c
版权申诉
185 浏览量
2022-09-22
20:12:55
上传
评论
收藏 4KB ZIP 举报
JonSco
- 粉丝: 76
- 资源: 1万+