Solve multi-objectives optimization of graph metrics with DEAP

[Rodolphe Coulon]

[this message was posted on Stack overflow before I found out about the mailing list. I hope this is OK]

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:
4. Select the best graphs
5. Crossover
6. Mutate (add or remove edges randomly?)
7. Go to 3.

Now, I usually use Python with networkx for my little graph experiments. Could 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.

[Félix-Antoine Fortin]

Hi Rodolphe,

No problem with your answer being both here and on StackOverflow. Just make sure to update your question on SO once you are satisfied with the answers here. Out of curiosity, how did you find out about DEAP and the mailing-list?

As for the problem at hand, it could easily be optimized with DEAP. I will quickly brainstorm on how you could implement a solution. Once you are familiar with DEAP, feel free to ask me to elaborate. In the following, I suppose your graph is simple (no weights, undirected, no loops, and a maximum of one edge between two vertices). 

Your individual could be represented be a classic binary string. Each bit would indicate wether 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, at first, 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 eaMuPlusLambda. For both multi-objective selection and eaMuPlusLambda 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.

If you have more questions or need more details, feel free to ask.

Regards,

Félix-Antoine

[Rodolphe Coulon]

Hey Félix,

This is already so useful, thank you so much! It's really good news DEAP can help me with this problem. I heard of it on stack overflow, actually, while looking for a GA library for Python.

As far as the graph goes, it will be a little bit more complicated than that later on (I actually need to assign categories to vertices), but a simple graph will be a great start.

Thanks again for your very clear explanations, I'll try it first thing tomorrow, will do my best through each step, and might (*will*, most likely) come back with more questions.

Cheers!

Rodolphe

[Rodolphe Coulon]

Ok, my first steps in DEAP:

 

import random

from deap import algorithms

from deap import base

from deap import creator

from deap import tools

import networkx as nx

import random

import math

"""Creates a binary string from a random graph"""

def graph2bin():

G=nx.gnm_random_graph(100,random.randint(1,2000))

ind = ""

for i in G.nodes():

for j in G.nodes():

if j > i:

if G.has_edge(i,j):

ind += '1'

else:

ind += '0'

return ind

 

"""Evaluate function"""

def evaluate(individual):

G = bin2graph(individual)

return nx.density(G), nx.average_shortest_path_length(G), nx.average_clustering(G)

"""Fitness class"""

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

"""Individual class"""

creator.create("Individual", str, fitness=creator.Fitness) # put graph2bin() instead of list?

ind = creator.Individual(graph2bin())

print(ind)

This is the very beginning, but I'm already not sure what to take from OneMax, and what to take from Knapsack. In one word: what's next? :)

Thanks Félix-Antoine!

[Félix-Antoine Fortin]

Hi Rodolphe,

A quick reminder, if you wish to share code with us, and I encourage you to do so, please use a code sharing web service. I have a strong preference for GitHub gist: https://gist.github.com/. Color syntaxing is a blessing when debuging code. gist also has the advantage of supporting versioning. You can therefore updated your code even after posting.

Regarding your individual representation, I recommend you to use a list of one and zeros as in the OneMax example. Python string are not mutable and won't work with DEAP crossover and mutation operators. In your graph2bin function, simply replace ind = "" by ind = [], and append 1 and 0 (the numbers not the characters) to the list instead of using +=.

The first step consists in reading the basic tutorials. I recommend you to go through these two, if you have not already :

http://deap.gel.ulaval.ca/doc/dev/tutorials/basic/part1.html

http://deap.gel.ulaval.ca/doc/dev/tutorials/basic/part2.html

The next step is then to create a toolbox and register the operators. Essentially, you will need the toolbox of OneMax, and the main function of Knapsack. You will need to change the select function registered in the onemax toolbox by the one registered in the knapsack toolbox.

Regards,

Félix-Antoine

--
You received this message because you are subscribed to the Google Groups "deap-users" group.
To unsubscribe from this group and stop receiving emails from it, send an email to deap-users+...@googlegroups.com.
For more options, visit https://groups.google.com/groups/opt_out.

[Rodolphe Coulon]

Alright,

I've tried implementing your advices, Félix-Antoine, and I think it's starting to work. I'm not all the way there, I need, for instance, to change the individuals generator. I'm using toolbox.register("attr_bool", random.randint, 0, 1) from the example, which works, but I'd like to try using my graph2bin() function instead of simply random.randint. I guess I haven't quite understood how a toolbox.register really works.

I need more practice...

I've got this, so far, and I *think*, My graph is being optimized, a bit...

https://gist.github.com/rodolpheg/7832866

A little more work and I can answer the question I put on SO.

Thank you so much for your quick help! Cheers!

[Félix-Antoine Fortin]

Hi Rodolphe,

Excellent news. I have forked your code and made the required adjustments to use your graph2bin function.

https://gist.github.com/cmd-ntrf/7848947

In order to replace the call to random.randint, you simply have to register your graph2bin function in the toolbox and use the initIterate function, instead of initRepeat.

http://deap.gel.ulaval.ca/doc/default/api/tools.html#deap.tools.initIterate

Finally, note that at the end of the evolution, you will not only get a single solution, but a set of solutions along a Pareto front. Each solution will correspond to a compromise for each value of objective. Therefore, you should not only check the first individual in the hall-of-fame, but all individuals. I have added a for-loop in my fork.

Regards,

Félix-Antoine

[Rodolphe Coulon]

Fantastic, I'll check the fork now. Now I need to try and publish something decent and cite DEAP, at least :)

Cheers!