I have an ArrayList of items (each item with weight and profit):
ArrayList itemList: [{Weight: 3, Profit: 10}, {Weight: 15, Profit: 50}, {Weight: 7, Profit: 25}, {Weight: 6, Profit: 15}, {Weight: 4, Profit: 10}]
Then I have a random bitStrings representing which items to be taken given maximum weight to be taken is 20 (capacity = 20).
Let's say the initial random bits obtain is [1,1,0,0,0] which means Item 1 and Item 2 are taken which give:
TotalWeight = 3 + 15 = 18 [<= capacity]
Then I have a random bit to be flipped (if the bit is 1 -> 0, and if the bit selected to flip is 0 -> 1). Let's say the order to flip the bits is [3,2,1,4,0].
So firstly, the bit at index 3 will be flipped and count the total weight like this:
[1,1,0,0,0] --> [1,1,0,1,0]
Hence, the new bitstring after bit[3] flip: [1,1,0,1,0].
Then count the total weight again:
Total Weight of new bitstring = 3 + 15 + 6 = 24 [> capacity]
So the total exceeds capacity and I want the new bitstring to assign back to the previous bitstring before it is flip:
[1,1,0,1,0] --> return back to previous state: [1,1,0,0,0].
After return back to state: [1,1,0,0,0] the next bit will be flip from the order just now [3,2,1,4,0] but now I have to flip the bit at index 2 according to the order from left to right. This becomes:
From [1,1,0,0,0] --> flip bit[2]:
[1,1,0,0,0] --> [1,1,1,0,0]
Then do the same calculate weight etc.
if the total still exceeds it will return back to previous state but if it does not exceeds it will add the new solution to a new ArrayList.
I have done some codings on it but my problems are to get back to the previous state and at adding the accepted bit strings to ArrayList improve. It stores the latest updated solution only and the other accepted solutions is being replaced as shown in the output I obtain.
This is my codes: '
public class KnapsackHC {
public static void main (String[] args){
int n = 5, capacity = 20, pointer, toFlip;
//Item items = new Item();
ArrayList<Item> itemList = new ArrayList<Item>();
ArrayList<Integer> solution = new ArrayList<Integer>();
ArrayList<Integer> currentSolution = new ArrayList<Integer>();
ArrayList<Integer> flipOrder = new ArrayList<Integer>();
ArrayList<ArrayList<Integer>> improve = new ArrayList<ArrayList<Integer>>();
//ArrayList<Integer> temp = new ArrayList<Integer>();
itemList = getProblem();
solution = initialSolution(n);
currentSolution = solution;
flipOrder = randomFlipOrder(n);
System.out.println("List of Items: " + itemList);
System.out.println("Initial solution: " + solution);
System.out.println("Current solution: " + currentSolution);
System.out.println("Random order: " + flipOrder);
for (int i = 0; i < flipOrder.size(); i++){
int totalWeight = 0, totalProfit = 0;
pointer = flipOrder.get(i);
toFlip = solution.get(pointer);
for (int j = 0; j < solution.size(); j++){
if (solution.get(j) == 1){
totalWeight += itemList.get(j).getWeight();
totalProfit += itemList.get(j).getProfit();
}
}
System.out.println();
System.out.println("Updated Solution: " + currentSolution);
System.out.println("Total Weight Solution " + (i+1) + " : " + totalWeight + " | Total Profit Solution " + (i+1) + " : " + totalProfit);
if (totalWeight <= capacity){
System.out.println("----------NOT EXCEED-----------");
currentSolution = solution;
System.out.println("currentSolution BEFORE FLIP: " + currentSolution);
improve.add(currentSolution);
System.out.println("Improve: " + improve);
if (toFlip == 1){
solution.set(pointer, 0);
}
else if (toFlip == 0){
solution.set(pointer, 1);
}
System.out.println("solution AFTER FLIP from Random Order [" + flipOrder.get(i) + "] : " + solution);
currentSolution = solution;
//solution = new ArrayList<Integer>();
System.out.println("--------------------------------");
}
else{
System.out.println("----------EXCEED!!!!------------");
//currentSolution = solution;
System.out.println("currentSolution BEFORE FLIP {return back to previous state}: " + currentSolution);
if (toFlip == 1){
solution.set(pointer, 0);
}
else if (toFlip == 0){
solution.set(pointer, 1);
}
System.out.println("solution AFTER FLIP from Random Order [" + flipOrder.get(i) + "] : " + solution);
System.out.println("--------------------------------");
}
}
}
/*
public static ArrayList<Integer> calcFitness(ArrayList<Integer> currentSolution, ArrayList<Integer> solution, ArrayList<Item> itemList, int capacity){
System.out.println("\nAfter Flip: " + solution);
System.out.println("Current Solution: " + currentSolution);
int totalWeight = 0;
int totalProfit = 0;
for (int i = 0; i < solution.size(); i++){
if (solution.get(i) == 1){
totalWeight += itemList.get(i).getWeight();
totalProfit += itemList.get(i).getProfit();
}
}
System.out.println("Total Weight: " + totalWeight + " || Total Profit: " + totalProfit);
if (totalWeight <= capacity){
currentSolution = solution;
System.out.println("Solution change: " + currentSolution);
System.out.println();
return solution;
}
else{
System.out.println("Solution NO change: " + currentSolution);
System.out.println();
return currentSolution;
}
}*/
public static ArrayList<Item> getProblem(){
ArrayList<Item> itemsArr = new ArrayList<Item>();
try {
BufferedReader in = new BufferedReader( new FileReader("knapsack_problem_5.txt" ) );
int i = 0;
String str;
while ( (str = in.readLine() )!= null ) {
String[] item = str.split( "," );
//System.out.print("Weight #" + i + " : " + Integer.parseInt(item[0]));
//System.out.print("Profit #" + i + " : " + Integer.parseInt(item[1]));
int weight = Integer.parseInt(item[0]);
int profit = Integer.parseInt(item[1]);
itemsArr.add(i,new Item(weight,profit));
i++;
}
in.close();
} catch ( IOException ex ) {
System.err.println( "Error: Can't open the file for reading." );
}
return itemsArr;
}
//generate initial solution(bits) randomly
public static ArrayList<Integer> initialSolution(int length){
Random r = new Random();
ArrayList<Integer> solution = new ArrayList<Integer>(length);
// generate some random boolean values
boolean[] booleans = new boolean[length];
for (int i = 0; i < booleans.length; i++) {
booleans[i] = r.nextBoolean();
}
for (boolean b : booleans) {
if (b == true){
solution.add(1);
}
else{
solution.add(0);
}
}
return solution;
}
public static ArrayList<Integer> randomFlipOrder(int length){
ArrayList<Integer> order = new ArrayList<Integer>();
Random r = new Random();
for (int i = 0; i < length; i++){
order.add(i);
}
Collections.shuffle(order);
return order;
}
}
'
My textfile consists the following (weight, profit):
3,10
15,50
7,25
6,15
4,10
My output obtained (the initial bit strings and random order to flip bit will be randomly generated):
List of Items: [{Weight: 3, Profit: 10}, {Weight: 15, Profit: 50}, {Weight: 7, Profit: 25}, {Weight: 6, Profit: 15}, {Weight: 4, Profit: 10}]
Initial solution: [1, 0, 0, 1, 0]
Current solution: [1, 0, 0, 1, 0]
Random order: [2, 4, 0, 1, 3]
Updated Solution: [1, 0, 0, 1, 0]
Total Weight Solution 1 : 9 | Total Profit Solution 1 : 25
----------NOT EXCEED-----------
currentSolution BEFORE FLIP: [1, 0, 0, 1, 0]
Improve: [[1, 0, 0, 1, 0]]
solution AFTER FLIP from Random Order [2] : [1, 0, 1, 1, 0]
Updated Solution: [1, 0, 1, 1, 0]
Total Weight Solution 2 : 16 | Total Profit Solution 2 : 50
----------NOT EXCEED-----------
currentSolution BEFORE FLIP: [1, 0, 1, 1, 0]
Improve: [[1, 0, 1, 1, 0], [1, 0, 1, 1, 0]] It doesn't store the previous accepted solution but replace it with new one
solution AFTER FLIP from Random Order [4] : [1, 0, 1, 1, 1]
Updated Solution: [1, 0, 1, 1, 1]
Total Weight Solution 3 : 20 | Total Profit Solution 3 : 60
----------NOT EXCEED-----------
currentSolution BEFORE FLIP: [1, 0, 1, 1, 1]
Improve: [[1, 0, 1, 1, 1], [1, 0, 1, 1, 1], [1, 0, 1, 1, 1]]
solution AFTER FLIP from Random Order [0] : [0, 0, 1, 1, 1]
Updated Solution: [0, 0, 1, 1, 1]
Total Weight Solution 4 : 17 | Total Profit Solution 4 : 50
----------NOT EXCEED-----------
currentSolution BEFORE FLIP: [0, 0, 1, 1, 1]
Improve: [[0, 0, 1, 1, 1], [0, 0, 1, 1, 1], [0, 0, 1, 1, 1], [0, 0, 1, 1, 1]]
solution AFTER FLIP from Random Order [1] : [0, 1, 1, 1, 1]
Updated Solution: [0, 1, 1, 1, 1]
Total Weight Solution 5 : 32 | Total Profit Solution 5 : 100
----------EXCEED!!!!------------
currentSolution BEFORE FLIP {return back to previous state}: [0, 1, 1, 1, 1] ==> This should return back to [0,0,1,1,1] where the capacity is not exceeded
solution AFTER FLIP from Random Order [3] : [0, 1, 1, 0, 1] ==> this should be flipped from [0,0,1,1,1] and bcomes -> [0,0,1,0,1]
And lastly, once it has becomes [0,0,1,0,1] it should display the total weight again and display but it's not displaying.
I'm not sure where are the mistakes. Please help. Thank you.
Aucun commentaire:
Enregistrer un commentaire