Solve multi-objectives optimization of a graph in Python

Question

I'm trying to find what seems to be a complicated and time-consuming multi-objective optimization on a large-ish graph.

Here's the problem: I want to find a graph of n vertices (n is constant at, say 100) and m edges (m can change) where a set of metrics are optimized:

• Metric A needs to be as high as possible
• Metric B needs to be as low as possible
• Metric C needs to be as high as possible
• Metric D needs to be as low as possible

My best guess is to go with GA. I am not very familiar with genetic algorithms, but I can spend a little time to learn the basics. From what I'm reading so far, I need to go as such:

1. Generate a population of graphs of n nodes randomly connected to each other by m = random[1,2000] (for instance) edges
2. Run the metrics A, B, C, D on each graph
3. Is an optimal solution found (as defined in the problem)?

If yes, perfect. If not:

1. Select the best graphs
2. Crossover
3. Mutate (add or remove edges randomly?)
4. Go to 3.

Now, I usually use Python for my little experiments. Could DEAP (https://code.google.com/p/deap/) help me with this problem? If so, I have many more questions (especially on the crossover and mutate steps), but in short: are the steps (in Python, using DEAP) easy enough to be explain or summarized here?

I can try and elaborate if needed. Cheers.

Answer 1

Disclaimer: I am one of DEAP lead developer.

Your individual could be represented by a binary string. Each bit would indicate whether there is an edge between two vertices. Therefore, your individuals would be composed of n * (n - 1) / 2 bits, where n is the number of vertices. To evaluate your individual, you would simply need to build an adjacency matrix from the individual genotype. For an evaluation function example, see the following gist https://gist.github.com/cmd-ntrf/7816665.

Your fitness would be composed of 4 objectives, and based on what you said regarding minimization and maximization of each objective, the fitness class would be created like this :

creator.create("Fitness", base.Fitness, weights=(1.0, -1.0, 1.0, -1.0)

The crossover and mutation operators could be the same as in the OneMax example. http://deap.gel.ulaval.ca/doc/default/examples/ga_onemax_short.html

However, since you want to do multi-objective, you would need a multi-objective selection operator, either NSGA2 or SPEA2. Finally, the algorithm would have to be mu + lambda. For both multi-objective selection and mu + lambda algorithm usage, see the GA Knapsack example. http://deap.gel.ulaval.ca/doc/default/examples/ga_knapsack.html

So essentially, to get up and running, you only have to merge a part of the onemax example with the knapsack while using the proposed evaluation function.