GeneticKnapsackAlgorithm.java

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();
		
		
	}
	
	
}

KnapsackObject.java

/*  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;		
	}
	*/


}

Specimen.java

/* 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;
	}

}