multi-objectives_optimized_graph.py

import array
import random

from deap import algorithms
from deap import base
from deap import creator
from deap import tools
import networkx as nx
import math
import drawG

def graph2bin(n, min_edge, max_edge):
    G = nx.gnm_random_graph(n, random.randint(min_edge, max_edge))
    return (int(G.has_edge(i, j)) for i in range(n-1) for j in range(i+1, n))

def bin2graph(ind):
    G = nx.Graph()
    n = int(math.floor(1 + math.sqrt(1 + 8 * len(ind))/2))
    c = 0
    for i in range(n-1):
        for j in range(i+1, n):
            if ind[c] == 1:
                G.add_edge(i, j)
            c += 1
    return G

def evaluate(ind):
    G = bin2graph(ind)
    try:
        avg_short_path =  nx.average_shortest_path_length(G)
    except nx.NetworkXError:
        # Graph is not connected.
        avg_short_path = len(ind) 
    return nx.density(G), avg_short_path, nx.average_clustering(G),

creator.create("FitnessMax", base.Fitness, weights=(-1.0,-1.0,1.0,))
creator.create("Individual", array.array, typecode='b', fitness=creator.FitnessMax)

toolbox = base.Toolbox()

# Structure initializers
toolbox.register("graph", graph2bin, n=100, min_edge=1, max_edge=2000)
toolbox.register("individual", tools.initIterate, creator.Individual, toolbox.graph)
toolbox.register("population", tools.initRepeat, list, toolbox.individual)
toolbox.register("evaluate", evaluate)
toolbox.register("mate", tools.cxTwoPoints)
toolbox.register("mutate", tools.mutFlipBit, indpb=0.05)
toolbox.register("select", tools.selNSGA2)

def main():
    random.seed(64)
    NGEN = 50
    MU = 50
    LAMBDA = 100
    CXPB = 0.7
    MUTPB = 0.2
    
    pop = toolbox.population(n=MU)
    hof = tools.ParetoFront()
    stats = tools.Statistics(lambda ind: ind.fitness.values)
    stats.register("avg", tools.mean)
    stats.register("std", tools.std)
    stats.register("min", min)
    stats.register("max", max)
    
    algorithms.eaMuPlusLambda(pop, toolbox, MU, LAMBDA, CXPB, MUTPB, NGEN, stats,
                              halloffame=hof)
    
    return pop, stats, hof

if __name__ == "__main__":
    [pop, stats, hof]=main()
    
    for ind in hof:
        print ind
        G = bin2graph(ind)
        drawG.drawG(G)
        print len(G.nodes()),len(G.edges())