Solve multi-objectives optimization of a graph in Python

user_1208142 0
Viewed 4216

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.

genetic-algorithm python
2 Answers

I suggest the excellent pyevolve library https://github.com/perone/Pyevolve. This will do most of the work for you, you will only have to define the fitness function and your representation nodes/functions. You can specify the crossover and mutation rate as well.

user_30587850
Related