The genotype to phenotype mapping based on the ordered inclusion can result in suboptimal solutions especially when you have an item with a weight that's close to the knapsack capacity and a value that is very high.

In the example, if you change the book's weight to say 395 and value to 10,000, the optimal solution (book+socks=10,050) must include the book. But since it is the last item, the chances of all items before it being '0' is very slim and the book will never get selected.

A better approach might be to order the initial set of items based on a simple & widely known greedy heuristic - the ratio of value to weight.

In: 01-hyperparameter-tuning-grid.py
...
...
from evolutionary_search import EvolutionaryAlgorithmSearchCV

gives the following error:
builtins.ModuleNotFoundError: No module named 'evolutionary_search'

Hi,
I want to solve 3D bin packing(especially container loading), which is a extension of knapsack problem(?), but I don't know how can I do that.
Is there any referrence code for 3d bpp?

thanks.

Any thoughts on applying a greedy heuristic to the TSP problem to create the initial population?

def load_individuals(creator, n):
    individuals = []
    for _ in range(0, n):
        next_city = random.randint(0, tsp.tspSize - 1)
        visited_cities = []
        visited_cities.append(next_city)
        while len(visited_cities) < tsp.tspSize:
            nearest_neighbor, _ = sorted(
                [(city, distance) for (city, distance) in enumerate(tsp.distances[next_city]) if city not in visited_cities],
                key=lambda p: p[1]
            )[0]
            visited_cities.append(nearest_neighbor)
            next_city = nearest_neighbor

        individuals.append(creator(visited_cities))

    return individuals

# create the population creation operator to generate a list of individuals:
toolbox.register("populationCreator",load_individuals, creator.Individual)

This gives a better solution for the initial TSP implementation with algorithms.eaSimple and a faster convergence (under 50 generations) for the elitism.eaSimpleWithElitism implementation

The getRoutes method in the VehicleRoutingProblem has a bug where is fails to detect an empty route if a separator (a vehicle index) is followed by the index of the central depot at the end of the chromosome. Below is an example:

A random Solution for the bayg29 problem with 3 vehicles and depot index of 12
[23, 0, 5, 29, 11, 8, 4, 20, 9, 3, 14, 17, 13, 16, 21, 10, 18, 19, 1, 28, 2, 25, 27, 7, 26, 22, 6, 24, 15, 30, 12]

Notice how the depot index 12 follows the vehicle index 30. In this case `getRoutes` returns
[[23, 0, 5], [11, 8, 4, 20, 9, 3, 14, 17, 13, 16, 21, 10, 18, 19, 1, 28, 2, 25, 27, 7, 26, 22, 6, 24, 15]]

It should return
[[23, 0, 5], [11, 8, 4, 20, 9, 3, 14, 17, 13, 16, 21, 10, 18, 19, 1, 28, 2, 25, 27, 7, 26, 22, 6, 24, 15], []]

I'd be happy to submit PR to fix this along with a fitness function that minimizes total distance (instead of max distance) and also aims to maximize the vehicle utilization of each vehicle (based on distance travelled)

    def getFitnessDistance(self, indices):
        routeDistances = [self.getRouteDistance(route) for route in self.getRoutes(indices)]
        totalDistance = sum(routeDistances)
        avgDistance = totalDistance / self.numOfVehicles
        return totalDistance + sum([abs(avgDistance - dist) for dist in routeDistances])

This fitness function yields better results for both the 3 and 6 vehicle variations of the bayg29 VRP problem.