Solve graph optimization for multiple goals in Python

Question

I am trying to find a complex and time-consuming multipurpose optimization on a large-true chart.

Here's the problem: I want to find a graph of n vertices (n is a constant, say 100) and m edges (m may vary), where the set of indicators is optimized:

• Metric A should be as high as possible
• Metric B should be as low as possible
• Metric C should be as high as possible
• Metric D should be as low as possible

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

• Create a set of graphs from n nodes randomly connected to each other using m = random [1,2000] (for example) edges
• Run metrics A, B, C, D on each chart
• Is an optimal solution found (as defined in the problem)?

If so, excellent. If not:

• Choose the best graphics
• Crossover
• Mutate (randomly add or remove faces?)
• Go to 3.

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

I can work out if necessary. Greetings.

Answer 1

Disclaimer: I am one of the developers of DEAP.

. , . n * (n - 1)/2 , n - . , . . gist https://gist.github.com/cmd-ntrf/7816665.

4 , , , :

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

, OneMax. http://deap.gel.ulaval.ca/doc/default/examples/ga_onemax_short.html

, , - NSGA2 SPEA2. , mu + lambda. , mu + lambda, . GA Knapsack. http://deap.gel.ulaval.ca/doc/default/examples/ga_knapsack.html

, , onemax .

Answer 2

pyevolve https://github.com/perone/Pyevolve. , / . .