Sorting Networks

Optimal Network Generation

  1from deap_er import creator
  2from deap_er import tools
  3from deap_er import base
  4import random
  5import numpy
  6
  7
  8random.seed(1234)  # disables randomization
  9
 10INPUTS = 6
 11NGEN = 100
 12CX_PROB = 0.5
 13MUT_PROB = 0.2
 14ADD_PROB = 0.01
 15DEL_PROB = 0.01
 16
 17
 18def eval_network(individual, dimension):
 19    network = tools.SortingNetwork(dimension, individual)
 20    return network.evaluate(), network.length, network.depth
 21
 22
 23def gen_wire(dimension):
 24    wire1 = random.randrange(dimension)
 25    wire2 = random.randrange(dimension)
 26    return wire1, wire2
 27
 28
 29def gen_network(dimension, min_size, max_size):
 30    size = random.randint(min_size, max_size)
 31    network = [gen_wire(dimension) for _ in range(size)]
 32    return network
 33
 34
 35def mut_wire(individual, dimension, mut_prob):
 36    for index, elem in enumerate(individual):
 37        if random.random() < mut_prob:
 38            individual[index] = gen_wire(dimension)
 39
 40
 41def mut_add_wire(individual, dimension):
 42    index = random.randint(0, len(individual))
 43    individual.insert(index, gen_wire(dimension))
 44
 45
 46def mut_del_wire(individual):
 47    index = random.randrange(len(individual))
 48    del individual[index]
 49
 50
 51def setup():
 52    creator.create("FitnessMin", base.Fitness, weights=(-1.0, -1.0, -1.0))
 53    creator.create("Individual", list, fitness=creator.FitnessMin)
 54
 55    toolbox = base.Toolbox()
 56    toolbox.register("network", gen_network, dimension=INPUTS, min_size=9, max_size=12)
 57    toolbox.register("individual", tools.init_iterate, creator.Individual, toolbox.network)
 58    toolbox.register("population", tools.init_repeat, list, toolbox.individual)
 59
 60    toolbox.register("evaluate", eval_network, dimension=INPUTS)
 61    toolbox.register("mate", tools.cx_two_point)
 62    toolbox.register("mutate", mut_wire, dimension=INPUTS, mut_prob=0.05)
 63    toolbox.register("addwire", mut_add_wire, dimension=INPUTS)
 64    toolbox.register("delwire", mut_del_wire)
 65    toolbox.register("select", tools.sel_nsga_2)
 66
 67    stats = tools.Statistics(lambda ind: ind.fitness.values)
 68    stats.register("avg", numpy.mean, axis=0)
 69    stats.register("std", numpy.std, axis=0)
 70    stats.register("min", numpy.min, axis=0)
 71    stats.register("max", numpy.max, axis=0)
 72
 73    logbook = tools.Logbook()
 74    logbook.header = "gen", "evals", "std", "min", "avg", "max"
 75
 76    return toolbox, stats, logbook
 77
 78
 79def print_results(best_network):
 80    print('\nBest sorting network schematic:')
 81    print(best_network.draw())
 82    print(f'\nEvolution converged correctly.')
 83
 84
 85def main():
 86    toolbox, stats, logbook = setup()
 87    population = toolbox.population(size=300)
 88    hof = tools.ParetoFront()
 89
 90    def log_stats(ngen=0):
 91        hof.update(population)
 92        record = stats.compile(population)
 93        logbook.record(gen=ngen, evals=len(population), **record)
 94        print(logbook.stream)
 95
 96    fitness = toolbox.map(toolbox.evaluate, population)
 97    for ind, fit in zip(population, fitness):
 98        ind.fitness.values = fit
 99
100    log_stats()
101
102    for generation in range(1, NGEN):
103        offspring = [toolbox.clone(ind) for ind in population]
104
105        for ind1, ind2 in zip(offspring[::2], offspring[1::2]):
106            if random.random() < CX_PROB:
107                toolbox.mate(ind1, ind2)
108                del ind1.fitness.values
109                del ind2.fitness.values
110
111        for ind in offspring:
112            if random.random() < MUT_PROB:
113                toolbox.mutate(ind)
114                del ind.fitness.values
115            if random.random() < ADD_PROB:
116                toolbox.addwire(ind)
117                del ind.fitness.values
118            if random.random() < DEL_PROB:
119                toolbox.delwire(ind)
120                del ind.fitness.values
121
122        invalid_ind = [ind for ind in offspring if not ind.fitness.is_valid()]
123        fitness = toolbox.map(toolbox.evaluate, invalid_ind)
124        for ind, fit in zip(invalid_ind, fitness):
125            ind.fitness.values = fit
126
127        population = toolbox.select(population+offspring, len(offspring))
128
129        log_stats(generation)
130
131    best_network = tools.SortingNetwork(INPUTS, hof[0])
132    print_results(best_network)
133
134
135if __name__ == "__main__":
136    main()

Hillis Cooperative Co-Evolution

  1from deap_er import creator
  2from deap_er import tools
  3from deap_er import base
  4import random
  5import numpy
  6
  7
  8random.seed(1234)  # disables randomization
  9
 10INPUTS = 12
 11MAXGEN = 100
 12H_CX_PROB, H_MUT_PROB = 0.6, 0.3
 13P_CX_PROB, P_MUT_PROB = 0.6, 0.3
 14
 15
 16def gen_wire(dimension):
 17    wire1 = random.randrange(dimension)
 18    wire2 = random.randrange(dimension)
 19    return wire1, wire2
 20
 21
 22def gen_network(dimension, min_size, max_size):
 23    size = random.randint(min_size, max_size)
 24    network = [gen_wire(dimension) for _ in range(size)]
 25    return network
 26
 27
 28def eval_network(host, parasite, dimension):
 29    network = tools.SortingNetwork(dimension, host)
 30    return network.evaluate(parasite),  # The comma is essential here.
 31
 32
 33def mut_network(individual, dimension, mutpb, addpb, delpb, indpb):
 34    if random.random() < mutpb:
 35        for index, elem in enumerate(individual):
 36            if random.random() < indpb:
 37                individual[index] = gen_wire(dimension)
 38    if random.random() < addpb:
 39        index = random.randint(0, len(individual))
 40        individual.insert(index, gen_wire(dimension))
 41    if random.random() < delpb:
 42        index = random.randrange(len(individual))
 43        del individual[index]
 44    return individual,  # The comma is essential here.
 45
 46
 47def clone_network(individual):
 48    clone = individual.__class__(individual)
 49    clone.fitness.values = individual.fitness.values
 50    return clone
 51
 52
 53def gen_parasite(dimension):
 54    return [random.choice((0, 1)) for _ in range(dimension)]
 55
 56
 57def mut_parasite(individual, mut_prob):
 58    for i in individual:
 59        if random.random() < mut_prob:
 60            tools.mut_flip_bit(i, mut_prob)
 61    return individual,  # The comma is essential here.
 62
 63
 64def clone_parasite(individual):
 65    clone = individual.__class__(list(seq) for seq in individual)
 66    clone.fitness.values = individual.fitness.values
 67    return clone
 68
 69
 70def setup():
 71    creator.create("FitnessMax", base.Fitness, weights=(1.0,))
 72    creator.create("FitnessMin", base.Fitness, weights=(-1.0,))
 73    creator.create("Host", list, fitness=creator.FitnessMin)
 74    creator.create("Parasite", list, fitness=creator.FitnessMax)
 75
 76    h_toolbox = base.Toolbox()
 77    h_toolbox.register("host", gen_network, dimension=INPUTS, min_size=9, max_size=12)
 78    h_toolbox.register("individual", tools.init_iterate, creator.Host, h_toolbox.host)
 79    h_toolbox.register("population", tools.init_repeat, list, h_toolbox.individual)
 80    h_toolbox.register("evaluate", eval_network, dimension=INPUTS)
 81    h_toolbox.register("mate", tools.cx_two_point)
 82    h_toolbox.register("mutate", mut_network, dimension=INPUTS, mutpb=0.2, addpb=0.01, delpb=0.01, indpb=0.05)
 83    h_toolbox.register("select", tools.sel_tournament, contestants=3)
 84    h_toolbox.register("clone", clone_network)
 85
 86    p_toolbox = base.Toolbox()
 87    p_toolbox.register("parasite", gen_parasite, dimension=INPUTS)
 88    p_toolbox.register("individual", tools.init_repeat, creator.Parasite, p_toolbox.parasite, 20)
 89    p_toolbox.register("population", tools.init_repeat, list, p_toolbox.individual)
 90    p_toolbox.register("mate", tools.cx_two_point)
 91    p_toolbox.register("mutate", mut_parasite, mut_prob=0.05)
 92    p_toolbox.register("select", tools.sel_tournament, contestants=3)
 93    p_toolbox.register("clone", clone_parasite)
 94
 95    stats = tools.Statistics(lambda ind: ind.fitness.values)
 96    stats.register("avg", numpy.mean)
 97    stats.register("std", numpy.std)
 98    stats.register("min", numpy.min)
 99    stats.register("max", numpy.max)
100
101    logbook = tools.Logbook()
102    logbook.header = "gen", "evals", "std", "min", "avg", "max"
103
104    return h_toolbox, p_toolbox, stats, logbook
105
106
107def print_results(best_network):
108    print('\nBest sorting network schematic:')
109    print(best_network.draw())
110    print(f'\nEvolution converged correctly.')
111
112
113def main():
114    h_toolbox, p_toolbox, stats, logbook = setup()
115    hof = tools.HallOfFame(1)
116
117    def evaluate_fitness():
118        fits = h_toolbox.map(h_toolbox.evaluate, hosts, parasites)
119        for host, parasite, fit in zip(hosts, parasites, fits):
120            host.fitness.values = parasite.fitness.values = fit
121
122    def log_stats(ngen=0):
123        hof.update(hosts)
124        record = stats.compile(hosts)
125        logbook.record(gen=ngen, evals=len(hosts), **record)
126        print(logbook.stream)
127
128    hosts = h_toolbox.population(size=300)
129    parasites = p_toolbox.population(size=300)
130
131    evaluate_fitness()
132    log_stats()
133
134    for gen in range(1, MAXGEN):
135        hosts = h_toolbox.select(hosts, len(hosts))
136        parasites = p_toolbox.select(parasites, len(parasites))
137
138        hosts = tools.var_and(h_toolbox, hosts, H_CX_PROB, H_MUT_PROB)
139        parasites = tools.var_and(p_toolbox, parasites, P_CX_PROB, P_MUT_PROB)
140
141        evaluate_fitness()
142        log_stats(gen)
143
144    best_network = tools.SortingNetwork(INPUTS, hof[0])
145    print_results(best_network)
146
147
148if __name__ == "__main__":
149    main()