My assignment is to use local search heuristics to solve the Multidimensional multiple-choice knapsack problem, but to do so I first need to find a feasible solution to start with.
Here is an example problem with what I tried so far.
Problem
L1 L2 L3
RESOUCES : 8 8 8
GROUPS:
G1:
11.0 3 2 2
12.0 1 1 3
G2:
20.0 1 1 3
5.0 2 3 2
G3:
10.0 2 2 3
30.0 1 1 3
Sorting strategies
To find a starting feasible solution for my local search I decided to ignore maximization of gains and just try to fit the resources requirements.
I decided to sort the choices (strategies) in each group by comparing their "distance" from the multidimensional space origin, thus calculating SQRT(R1^2 + R2^2 + ... + RN^2). I felt like this was a keen solution as it somehow privileged those choices with resouce usages closer to each other (e.g. R1:2 R2:2 R3:2 < R1:1 R2:2 R3:3) even if the total sum is the same.
Doing so and selecting the best choice from each group proved sufficent to find a feasible solution for many[30] different benchmark problems, but of course I knew it was just luck. So I came up with the problem presented above which sorts like this:
L1 L2 L3
RESOUCES : 8 8 8
GROUPS:
G1:
12.0 1 1 3 < select this
11.0 3 2 2
G2:
20.0 1 1 3 < select this
5.0 2 3 2
G3:
30.0 1 1 3 < select this
10.0 2 2 3
And it is not feasible because the resources consmption is R1:3, R2:3, R3:9.
The easy solution is to pick one of the second best choices in group 1 or 2, so I'll need some kind of iteration (local search[?]) to find the starting feasible solution for my local search solution.
Here are the options I came up with
Option 1: iterate choices
I tried to find a way to iterate all the choices with a specific order, something like
G1 G2 G3
1 1 1
2 1 1
1 2 1
1 1 2
2 2 1
...
believeng that feasible solutions won't be that far away from the unfeasible one I start with and thus the number of iterations will keep quite low.
Does this make any sense? If yes, how can I iterate the choices (grouped combinations) of each group keeping "as near as possibile" to the previous iteration?
Option 2: Change the comparation term
I tried to think how to find a better variable to sort the choices on. I thought at a measure of how "precious" a resource is based on supply and demand, so that an higer demand of a more precious resource will push you down the list, but this didn't help at all.
Also I thought there probably isn't gonna be such a comparsion variable which assures me a feasible solution at first strike.
I there such a variable? If not, is there a better sorting criteria anyways?
Option 3: implement any known sub-optimal fast solving algorithm
Unfortunately I could not find any of such algorithms online. Any suggestion?
EDIT
NOTE: I updated the previous description using labels L1 L2 L3 for the problem resource limits in place of R1 R2 R3 which now indicate the resource requirements of each strategy (choice)
Fallowing the input by @J Trana, I decided to go and try a genetic algorithm for the problem setup.
This seemed quite fitting to the problem structure as each Group is a Gene, each Solution is a Chromosome and each Strategy is an Allele.
I also modified the distance expression to fit better with heterogeneous resource limits, so now the distance is : SUM(Rn/Ln) which should give a lower distance (i.e. higher priority) to those strategies with lower resource requirement portions.
Since this part is intended only for solving initialization, I chose the fallowing genetic functions:
Fitness
// if solution is feasible, that's just enough, it has the greatest fitness possible
if(solution.isFeasibleInProblem()) return Integer.MAX_VALUE;
ArrayList<Integer> consumptions = new ArrayList<Integer>();
for(Integer limit : problem.resourceLimits){
consumptions.add(0);
}
// add the resources consumptions from each group
for(Group g : genes){
for(int i = 0; i < g.currentSelectedSolution.resourceRequirements.size(); i++){
consumptions.set(i, consumptions.get(i) + g.currentSelectedSolution.resourceRequirements.get(i));
}
}
ArrayList<Double> subFitnesses = new ArrayList<Double>();
// each subFitness is the ratio between the total limit and the actual consumption
// this way if the consumption is < limit subFitness is greater than 1 (rises the fitness), else it is less than 1 and lowers the fitness
for(int j = 0; j < consumptions.size(); j++){
double subFitness = problem.limits.get(j) / consumptions.get(j);
subFitnesses.add(subFitness);
}
double fitness = 1;
for(Double sF : subFitnesses){
fitness *= sF;
}
return fitness;
So resource requirements lesser than the limit rise the fitness, where requirements greater than the limit lower the fitness.
Mutation
For the mutation function I found that feasible solutions contain strategies with smaller distance and considering solutions far down in the ordered distance list slows the evolution because most of the time those mutations have negative effects.
public void mutate(int strategyIndex, double mutationIntensity){
// if there's no choice, don't mutate
if(this.strategies.size() <= 1) return;
... here I'd need something that keeps in the first positions of the list
but eventually, with higher mutation intensities, goes to greater indexes...
selectStrategy(newStrategyIndex);
}
The above solution works very well for most of the benchmarks, but there are 2 of them, having a lot of choices per group and a lot of resources per choice, that simply won't find a feasible solution.
How could I implement the mutation algorithm so that those 2 benchmarks convert to a feasible solution? Is there any improvement I can put in my fitness function or in the strategy ordering to speed up the solving path?
