mbelmadani
commented
6 years ago Hi @Arttii
The good news is that you should be able to do it just by modifying knapsack.py You shouldn't have to modify the multiobjective algorithm for different problems (MOEA/D in moead.py in this case.) Note that DEAP, the framework used here to provide the evolutionary computing functionality, has other multiobjective algorithms that you can use (SPEA2,NSGA-II). Knapsack.py is a modified version from the version borrowed from the DEAP project examples, see https://github.com/DEAP/deap/blob/4db155fb3c4fe1678f8d7cd03a638248a1a2f447/examples/ga/knapsack.py and http://deap.readthedocs.io/en/master/examples/ga_knapsack.html).
Also note that this depends heavily on DEAP so have a look at the documentation: http://deap.readthedocs.io/en/master/index.html and some examples, and the deap-users user group https://groups.google.com/forum/#!forum/deap-users .
I can describe how I imagine the solution would work, though it might not be optimal. You need to do the following modifications:
1) Update the population individual representation to a multiple-knapsack version:
The current representation is a list of items which can grow/shrink in length. The individuals are lists of elements attr_item (line 104, a random value relating to an item number), representing a single knapsack solution. You need to have a representation that keeps track of which values in the individual belongs to which knapsack. One way to do it would be to change attr_item to be a knapsack instead of an item (essentially, attr_knapsack.) And instead of random.randrange, the function would return a a knapsack of attr_items.
Also, you'll need to adjust either crossovers or mutations, because then the current crossover methods would only switch a elements of knapsacks, assuming they're sets. I imagine that wouldn't work with your new representation. You could edit mutate (mutSet) to do mutation within knapsacks, and let crossover just shuffle knapsacks arounds without worrying about the values of the knapsacks; I can't tell at this stage if that would converge well towards good solutions, but you likely need at least one operator to edit elements in your knapsacks. I'm not sure the method is the best way to do, but I would start with something simple to at least show it works. Later you could get fancy and use multiple operators that edit either the knapsacks themselves of the list of knapsack combination. Also consider if you will be making those fixed length or let them vary.
2) An evaluation function compatible with your new representation: currently there's both a 2-objective and 3-objective version of the problem. The 2-objective version computes knapsack weight and value (profit), and the 3-objective one also computes the sum of differences between consecutive items. This is just something I just made up quickly to be able to test 3-objectives with minimal changes.
You will need to edit evalKnapsack to compute the objectives based on the new individual type representing multiple knapsacks. Currently it just iterates over the list and sums the weights/profits for each item. Instead you should process each knapsack individually and check that they don't fail the weight constraint or number of item limits (line 51). That will also vary depending if you have equal size knapsacks or a list of capacities your knapsacks have to respect.
For your choice of objectives, what you need to do is compute values that represent your solution fitnesses appropriately in the context of multiple knapsacks. Looking at the description of the multiple knapsack problem (https://en.wikipedia.org/wiki/List_of_knapsack_problems), the goal is to maximize profit across all knapsacks (this is my interpretation, I'm not recently familiar with the problem, so don't take my word for it ;)), so sum of knapsacks profits would be a maximizing objective.
The second objective in the provided 2-objective function minimizes the weight. That's not something that's required by the algorithm, the constraint just wants the knapsack to be under capacity. But minimizing the weight will likely provide you more diverse solution and help evolution because it would try to find the smallest possible weights while trying to get the best possible fitness in other metrics as well (so, the lowest weight with the highest profit.) Low-weight solutions may not be be most profitable solutions, but they control against overweighted solutions by giving incentive to keep the knapsacks light. You'll have to decide what "weight" means across knapsacks, and maybe experiment with different variants (e.g. return only the maximum of all knapsacks, or the average, the median etc. and see which one provide better solutions. Just pick the easiest one for now). This objective should be minimized.
Finally, set which objectives are maximizing or mimizing by setting the weight vector of 1.0 and -1.0 as done at like 90 in knapsack.py. (E.g. Maximizing, minimizing, maximizing would be creator.create("Fitness", base.Fitness, weights=(1.0, -1.0, 1.0)) ). I would start with only these two objective for now before trying anything else fancy. Personally, I've often had better luck using 2 very relevant objectives than 3 less clearly defined ones, but don't quote me on this.
That's essentially it I think. If you're still interested, I would start with that and see if you can get a basic version working. Then there will likely be improvements to do in the individual representations, crossover/mutate methods, and choice of objectives. If you get it working, feel free to submit a pull request to the repository to have the multiple-knapsack version as an example, that would be cool!
Arttii
Hi,
I am quite new to the field, but I was wondering do you have any suggestion on extending this to a Multi-Knapsack scenario? Where we need to fill M knapsacks and maximize the overall fitness. Would this fit the method in a good way?
Thanks