Skip to content

anonymous /GeneticKnapsackAlgorithm.java
Created

Embed URL

HTTPS clone URL

Subversion checkout URL

You can clone with
or
.
Download ZIP
import java.io.BufferedWriter;
import java.io.File;
import java.io.FileWriter;
import java.io.IOException;
import java.util.ArrayList;
import java.util.Collections;
import java.util.Random;
import java.util.Scanner;
public class GeneticKnapsackAlgorithm {
private static ArrayList<Specimen> genePool;
private static ArrayList<Specimen> childrenPopulation;
//Change these to tweak runtime
private static final int genePoolSize = 50;
private static final int numGenerations = 1000;
private static final int numChildren = 50;
private static int bestPossibleFitness;
private static Random rGen;
private static int numItems;
private static int knapsackWidth;
private static int knapsackLength;
//Prints the most-fit specimen of the genePool to a file
public static void printToFile()
{
Specimen mostFit;
File outFile;
BufferedWriter writer;
mostFit = getMostFit(genePool);
outFile = new File("Most fit Pack-O-Tron Specimen.txt");
try
{
writer = new BufferedWriter(new FileWriter(outFile));
writer.write("Fitness: " + mostFit.getFitness());
writer.newLine();
for(KnapsackObject object : mostFit.getObjectArray())
{
writer.write(object.getWidth() + " " + object.getLength());
writer.newLine();
}
for(int j = 0; j < knapsackLength; j++)
{
for(int i = 0; i < knapsackWidth; i++)
{
writer.write(mostFit.getKnapsack()[i][j] + " ");
}
writer.newLine();
}
writer.close();
} catch (IOException e) {
// Who cares
e.printStackTrace();
}
}
/* Used for testing purposed */
public static void printSpecimenToFile(Specimen specimen)
{
File outFile;
BufferedWriter writer;
outFile = new File("Pack-O-Tron Test Specimen.txt");
try
{
writer = new BufferedWriter(new FileWriter(outFile));
writer.write("Fitness: " + specimen.getFitness());
writer.newLine();
for(KnapsackObject object : specimen.getObjectArray())
{
writer.write(object.getWidth() + " " + object.getLength());
writer.newLine();
}
for(int j = 0; j < knapsackLength; j++)
{
for(int i = 0; i < knapsackWidth; i++)
{
writer.write(specimen.getKnapsack()[i][j] + " ");
}
writer.newLine();
}
writer.close();
} catch (IOException e) {
// Who cares
e.printStackTrace();
}
}
/* Similar to writeToFile(), but prints to console instead */
public static void printResult()
{
Specimen mostFit;
mostFit = getMostFit(genePool);
System.out.println("Fitness: " + mostFit.getFitness());
for(KnapsackObject object : mostFit.getObjectArray())
System.out.println(object.getWidth() + " " + object.getLength());
for(int j = 0; j < mostFit.getKnapsack()[0].length; j++)
{
for(int i = 0; i < mostFit.getKnapsack().length; i++)
{
System.out.printf("%d ", mostFit.getKnapsack()[i][j]);
}
System.out.println();
}
}
/* Returns the most-fit Specimen of some pool
* Used for genePool improvement.
*/
public static Specimen getMostFit(ArrayList<Specimen> pool)
{
Specimen mostFit;
mostFit = pool.get(0);
for(Specimen specimen : pool)
{
if(specimen.getFitness() < mostFit.getFitness())
mostFit = specimen;
}
return mostFit;
}
/* Returns the second-most-fit Specimen of some pool
* Used for genePool improvement.
*/
public static Specimen getSecondMostFit(ArrayList<Specimen> pool)
{
Specimen mostFit;
Specimen secondMostFit;
mostFit = getMostFit(pool);
if(pool.get(0) == mostFit)
secondMostFit = pool.get(1);
else
secondMostFit = pool.get(0);
for(Specimen specimen : pool)
{
if(specimen.getFitness() < secondMostFit.getFitness() && specimen != mostFit)
secondMostFit = specimen;
}
return secondMostFit;
}
/* Returns the least-fit Specimen of some pool
* Used for genePool improvement.
*/
public static Specimen getLeastFit(ArrayList<Specimen> pool)
{
Specimen leastFit;
leastFit = pool.get(0);
for(Specimen specimen : pool)
{
if(specimen.getFitness() > leastFit.getFitness())
leastFit = specimen;
}
return leastFit;
}
/* Returns the second-least-fit Specimen of some pool
* Used for genePool improvement.
*/
public static Specimen getSecondLeastFit(ArrayList<Specimen> pool)
{
Specimen leastFit;
Specimen secondLeastFit;
leastFit = getLeastFit(pool);
if(pool.get(0) == leastFit)
secondLeastFit = pool.get(1);
else
secondLeastFit = pool.get(0);
for(Specimen specimen : pool)
{
if(specimen.getFitness() > secondLeastFit.getFitness() && specimen != leastFit)
secondLeastFit = specimen;
}
return secondLeastFit;
}
/* Initializes the genePool with the array of objects */
public static void initializeGenePool(ArrayList<KnapsackObject> objectArray)
{
genePool = new ArrayList<Specimen>();
bestPossibleFitness = 0;
//The best possible bounding box area is the sum of all of the object's areas. This might not be possible to achieve.
for(KnapsackObject object : objectArray)
bestPossibleFitness += object.getArea();
for(int i = 0; i < genePoolSize; i++)
{
genePool.add(new Specimen(knapsackWidth, knapsackLength, numItems, objectArray, true));
//genePool.get(i).determineFitness() (Now called in constructor)
}
}
/* Creates a new "genome", or ordered list, based off of two parents */
public static Specimen mutateGenome(Specimen parent1, Specimen parent2)
{
Specimen child;
Specimen tempSpecimen;
boolean dominantParent;
KnapsackObject chosenTrait;
int indexOfTrait;
int indexInOtherParent;
ArrayList<KnapsackObject> tempList;
int mutationChance;
dominantParent = rGen.nextBoolean();
mutationChance = rGen.nextInt(100) + 1;
if(dominantParent) //Randomly determines the "dominant" parent
{
tempSpecimen = parent1;
parent1 = parent2;
parent2 = parent1;
}
//Copies a "gene"'s, or KnapsackObject's, position from one parent to another, resulting in a new "genome"
indexOfTrait = rGen.nextInt(numItems);
chosenTrait = parent1.getObjectArray().get(indexOfTrait);
tempList = new ArrayList<KnapsackObject>();
//tempList.addAll(0, parent2.getObjectArray());
tempList = parent2.getObjectArray();
indexInOtherParent = tempList.indexOf(chosenTrait);
tempList.remove(indexInOtherParent);
tempList.add(indexOfTrait, chosenTrait);
//Randomly swaps two object's positions
if(mutationChance % 7 == 0)
{
int randomIndex1;
int randomIndex2;
KnapsackObject object1;
KnapsackObject object2;
randomIndex1 = rGen.nextInt(numItems);
do
{
randomIndex2 = rGen.nextInt(numItems);
} while(randomIndex1 == randomIndex2);
object1 = tempList.get(randomIndex1);
object2 = tempList.get(randomIndex2);
tempList.set(randomIndex1, object2);
tempList.set(randomIndex2, object1);
}
//Randomly reverses the array
if(mutationChance < 15)
{
Collections.reverse(tempList);
}
//Randomly swaps the sides of an object in the array
if(mutationChance % 14 == 0)
{
KnapsackObject tempObject;
int randomIndex;
randomIndex = rGen.nextInt(numItems);
tempObject = tempList.get(randomIndex);
tempObject.swapSides();
tempList.set(randomIndex, tempObject);
}
child = new Specimen(knapsackWidth, knapsackLength, numItems, tempList, false);
return child;
}
/* Generates a pool of children based off of two parents */
public static void generateChildren(Specimen parent1, Specimen parent2)
{
childrenPopulation = new ArrayList<Specimen>(); //Resets the child pool
for(int i = 0; i < numChildren; i++)
childrenPopulation.add(mutateGenome(parent1, parent2));
}
/* Determines whether or not to replace individuals in the genePool with children, based on fitness */
public static boolean compete()
{
boolean returnValue;
Specimen genePoolLeastFit;
Specimen genePoolSecondLeastFit;
Specimen childStrongest;
Specimen childSecondStrongest;
returnValue = false;
genePoolLeastFit = getLeastFit(genePool);
genePoolSecondLeastFit = getSecondLeastFit(genePool);
childStrongest = getMostFit(childrenPopulation);
childSecondStrongest = getSecondMostFit(childrenPopulation);
if(childSecondStrongest.getFitness() < genePoolSecondLeastFit.getFitness()) //If the "weakest" strong child is stronger than the strongest "weak" genePool member, swap both
{
genePool.set(genePool.indexOf(genePoolSecondLeastFit), childSecondStrongest);
genePool.set(genePool.indexOf(genePoolLeastFit), childStrongest);
returnValue = true;
}
//Otherwise, replace the weakest Specimen in the genePool with the strongest child.
else if(childStrongest.getFitness() < genePoolLeastFit.getFitness())
{
genePool.set(genePool.indexOf(genePoolLeastFit), childStrongest);
returnValue = true;
}
return returnValue; //A replacement occured
}
/* Selects two parents and updates the genePool */
public static void evolve()
{
int matingType;
boolean randomChoice;
Specimen parent1;
Specimen parent2;
int parent1Index;
int parent2Index;
matingType = rGen.nextInt(99);
if(matingType < 33) //Two random parents
{
parent1Index = rGen.nextInt(genePool.size());
do
{
parent2Index = rGen.nextInt(genePool.size());
} while(parent1Index == parent2Index);
parent1 = genePool.get(parent1Index);
parent2 = genePool.get(parent2Index);
}
else if(matingType < 67) //Two most fit parents
{
parent1 = getMostFit(genePool);
parent2 = getSecondMostFit(genePool);
}
else //One of the most fit parents and a random parent
{
randomChoice = rGen.nextBoolean();
if(randomChoice)
parent1 = getMostFit(genePool);
else
parent1 = getSecondMostFit(genePool);
parent1Index = genePool.indexOf(parent1);
do
{
parent2Index = rGen.nextInt(genePool.size());
} while(parent1Index == parent2Index);
parent2 = genePool.get(parent2Index);
}
generateChildren(parent1, parent2);
}
/* Genetic "master" function. Call this to start the genetic process */
public static void darwinize()
{
int currentGeneration;
currentGeneration = 0;
printToFile(); //Writes the current-best Specimen to a file
//If the best possible fit has been found, stop. Otherwise, continue until specified number of generations
while((getMostFit(genePool).getFitness() != bestPossibleFitness) && (currentGeneration < numGenerations))
{
currentGeneration++;
System.out.println("Generation " + currentGeneration);
evolve();
if(compete())
{
System.out.println("Generation improved!");
}
}
printToFile(); //Updates the best speciment.
}
/* Used for testing purposes */
public static void testSpecimen(ArrayList<KnapsackObject> objectArray)
{
Specimen sample;
sample = new Specimen(knapsackWidth, knapsackLength, numItems, objectArray, false);
printSpecimenToFile(sample);
}
public static void main(String [] args)
{
Scanner input;
ArrayList<KnapsackObject> objectArray;
String tempInput;
String [] tempInputArray;
input = new Scanner(System.in);
rGen = new Random();
tempInput = input.nextLine();
tempInputArray = tempInput.split(" ");
knapsackWidth = Integer.parseInt(tempInputArray[0]);
knapsackLength = Integer.parseInt(tempInputArray[1]);
numItems = input.nextInt();
objectArray = new ArrayList<KnapsackObject>();
input.nextLine(); //Takes care of trailing /n
for(int i = 0; i < numItems; i++)
{
tempInput = input.nextLine();
tempInputArray = tempInput.split(" ");
objectArray.add(new KnapsackObject(Integer.parseInt(tempInputArray[0]), Integer.parseInt(tempInputArray[1])));
}
//testSpecimen(objectArray); (Testing purposes)
initializeGenePool(objectArray);
darwinize();
}
}
/* Rectangles.
*
*/
public class KnapsackObject {
private int width;
private int length;
private int area;
public KnapsackObject(int width, int length)
{
this.width = width;
this.length = length;
updateArea();
}
public int getWidth()
{
return width;
}
public int getLength()
{
return length;
}
public void setWidth(int width)
{
this.width = width;
updateArea();
}
public void setLength(int length)
{
this.length = length;
updateArea();
}
private void updateArea()
{
area = width * length;
}
public int getArea()
{
return area;
}
public void swapSides()
{
int temp;
temp = width;
width = length;
length = temp;
}
//Initially wanted to implement Comparable. Not needed.
/*
public int compareTo(Object comparator)
{
final int smaller = -1;
final int equal = 0;
final int larger = 1;
if(this == comparator)
return equal;
else if(this.getArea() < ((KnapsackObject) comparator).getArea())
return smaller;
else
return larger;
}
*/
}
/* A Specimen is a knapsack packed with an ordered list of objects using a first-fit algorithm.
*
*/
import java.util.ArrayList;
import java.util.Random;
public class Specimen{
private int [][] knapsack;
private int numItems;
private ArrayList<KnapsackObject> objectArray;
private int fitness;
/* Constructor. Creates a Specimen with a given knapsack size, number of objects, list of objects, and whether or not the object order is random */
public Specimen(int knapsackWidth, int knapsackLength, int numItems, ArrayList<KnapsackObject> objectArray, boolean random)
{
knapsack = new int[knapsackWidth][knapsackLength];
this.numItems = numItems;
//The object order isn't random. Keep the list as-is.
if(!random)
{
this.objectArray = objectArray;
}
//The object order is random. Randomize both the order of the list and the orientation of objects.
else //Randomly sets up objectArray;
{
Random rGen;
boolean swapSides;
int currentPosition;
ArrayList<Integer> usedArrayPositions;
KnapsackObject [] tempArray;
KnapsackObject tempObject;
rGen = new Random();
swapSides = false;
usedArrayPositions = new ArrayList<Integer>();
tempArray = new KnapsackObject[objectArray.size()];
this.objectArray = new ArrayList<KnapsackObject>();
//Randomly orders objects
for(int i = 0; i < numItems; i++)
{
swapSides = rGen.nextBoolean();
do
{
currentPosition = rGen.nextInt(numItems);
} while(usedArrayPositions.contains(currentPosition));
usedArrayPositions.add(currentPosition);
tempObject = objectArray.get(i);
//Randomly orients objects
if(swapSides)
tempObject.swapSides();
tempArray[currentPosition] = tempObject;
}
//Initializes objectArray with this new random ordering
for(int i = 0; i < numItems; i++)
this.objectArray.add(tempArray[i]);
}
//Updates fitness (packs the knapsack)
fitness = 0;
determineFitness();
}
public void print()
{
System.out.println();
for(int j = 0; j < knapsack[0].length; j++)
{
for(int i = 0; i < knapsack.length; i++)
{
System.out.print(knapsack[i][j]+ " ");
}
System.out.println();
}
}
/* Updates the knapsack with an object and it's starting position. Should only be called from tryToFit(), which should only be called from pack() */
private void placeObject(int startX, int startY, int width, int length, int positionInArray)
{
positionInArray++; //Passed the actual index, 0-based. Converts to 1-based.
for(int j = 0; j < length; j++)
{
for(int i = 0; i < width; i++)
{
//System.out.println("Writing " + positionInArray + " to " + i + " " + j);
knapsack[startX + i][startY + j] = positionInArray;
}
}
}
/* Fairly naive approach. Attemps to fit some object in the knapsack in the upper-left-most corner.
* Moves right and then wraps around (x = 0, y++) looking for possible spots to place the item.
*/
private boolean tryToFit(KnapsackObject object, int indexInArray)
{
boolean canFit;
canFit = true;
for(int j = 0; j < knapsack[0].length; j++)
{
for(int i = 0; i < knapsack.length; i++)
{
for(int m = 0; m < object.getLength(); m++)
{
for(int n = 0; n < object.getWidth(); n++)
{
if( (i + n >= knapsack.length) || (j + m >= knapsack[0].length) || (knapsack[i+ n][j + m] != 0)) //If the item won't fit in the xDirection, yDirection, or a space "in the item" is already occupied
canFit = false; //The item can't fit!
//End-of-object check for fit in knapsack
if(m + 1 == object.getLength() && n + 1 == object.getWidth() && canFit) //It fits!
{
placeObject(i, j, object.getWidth(), object.getLength(), indexInArray); //Place the object
return canFit; //Return successful!
}
else if(m + 1 == object.getLength() && n + 1 == object.getWidth() && !canFit) //It doesn't fit. Increment starting position and try again.
canFit = true;
}
}
}
}
//If the code reaches here, the item wasn't able to be placed.
canFit = false; //Not really needed, but the loop exits with canFit = true. Can just return false instead
return canFit;
}
/* Attempts to pack all objects into the knapsack */
public void pack()
{
int indexOfObject;
int numItemsFit;
indexOfObject = 0;
numItemsFit = numItems;
for(KnapsackObject object : objectArray)
{
if(!tryToFit(object, indexOfObject)) //If the item can't be fit using the algorithm, update the numItemsFit
numItemsFit--;
indexOfObject++; //Combination for & for each. Probably bad practice.
}
//If all items were able to fit
if(numItemsFit == numItems)
calculateGoodFitness();
else
calculateBadFitness(numItemsFit);
}
/* Creates an arbitrary *very high* number in relation to Specimen's that managed to fit all objects into the grid. */
public void calculateBadFitness(int numItemsFit)
{
//The more items fit, the "more fit" it is, regardless of object size. This is quick and dirty, can be improved
fitness = knapsack.length * knapsack[0].length * numItemsFit * 1000;
}
/* Finds and sets fitness to minimum bounding box for current assignment, only if all objects are placed */
private void calculateGoodFitness()
{
int width;
int length;
int highestWidth;
int highestLength;
highestWidth = 0;
highestLength = 0;
width = 0;
length = 0;
for(int i = 0; i < knapsack.length; i++)
{
for(int j = 0; j < knapsack[0].length; j++)
{
if(knapsack[i][j] != 0)
length = j + 1;
}
if(length > highestLength)
highestLength = length;
length = 0;
}
for(int j = 0; j < knapsack[0].length; j++)
{
for(int i = 0; i < knapsack.length; i++)
{
if(knapsack[i][j] != 0)
width = i + 1;
}
if(width > highestWidth)
highestWidth = width;
width = 0;
}
fitness = highestWidth * highestLength;
}
//Wrapper for pack()
public void determineFitness()
{
pack();
}
/* Accessors and mutators for private variables */
public int [][] getKnapsack()
{
return knapsack;
}
public ArrayList<KnapsackObject> getObjectArray()
{
return objectArray;
}
public void setObjectArray(ArrayList<KnapsackObject> objectArray)
{
this.objectArray = objectArray;
}
public int getNumItems()
{
return numItems;
}
public int getFitness()
{
return fitness;
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Something went wrong with that request. Please try again.