Demonstration of using a genetic algorithm to find a potentially optimum combination of projects where the sum of costs is at or less than a defined total cost.

genetic_algo_projects.py

"""
author:      Bill Thaman
description: Uses a genetic algorithm, with selective pressure, to find the optimal combination
             of projects where the sum of costs is less than or equal to a total. Inspired by the knapsack problem.
"""
from random import randint, random
from operator import add
from functools import reduce
import roulette
import project
import most_common_funcs as mcf
import matplotlib.pyplot as plt


def individual(projects):
    """Create a member of the population."""
    return [p.get_random_alternative_list() for p in projects]


def population(count, projects):
    """
    Create a number of individuals (i.e. a population).

    count: the number of individuals in the population
    length: the number of values per individual
    """
    return [individual(projects) for x in range(count)]


def fitness(individual, projects, max_cost):
    """
    Determine the fitness of an individual. Higher is better.
    maximum weight specified
    individual: the individual to evaluate
    """
    cost = 0
    revenue = 0
    for n, p in enumerate(individual):
        ind_cost = sum([i*j for i, j in zip(p, projects[n].cost)])
        ind_revenue = sum([i*j for i, j in zip(p, projects[n].revenue)])
        cost += ind_cost
        revenue += ind_revenue
    # revenue = revenue if cost <= max_cost else 0
    revenue = (revenue + (max_cost - cost)) if cost <= max_cost else 0
    return revenue


def grade(pop, projects, max_cost):
    """Find average fitness for a population."""
    summed = reduce(add, (fitness(x, projects, max_cost) for x in pop))
    return summed / len(pop)


def evolve(pop, projects, max_cost, retain=0.25, random_select=0.0, mutate=0.1, sp=1.35):
    retain_length = int(len(pop)*retain)
    fitness_unsorted = [fitness(x, projects, max_cost) for x in pop]
    parents = roulette.get_parents_ranked(pop, fitness_unsorted, retain_length, sp)
    # randomly add other individuals to promote genetic diversity
    for individual in pop:
        if random_select > random():
            parents.append(individual)
    # mutate some individuals
    for individual in parents:
        if mutate > random():
            random_project_index = randint(0, len(individual)-1)
            random_project = projects[random_project_index]
            random_project.set_alternatives(individual[random_project_index])
            individual[random_project_index] = random_project.get_mutation()
    # crossover parents to create children
    parents_length = len(parents)
    desired_length = len(pop) - parents_length
    children = []
    while len(children) < desired_length:
        male = randint(0, parents_length-1)
        female = randint(0, parents_length-1)
        if male != female:
            male = parents[male]
            female = parents[female]
            half = int(len(male) / 2)
            child = male[:half] + female[half:]
            children.append(child)
    parents.extend(children)
    return parents


if __name__ == '__main__':
    try:
        items = ['Project A', 'Project B', 'Project C', 'Project D', 'Project E', 'Project F']
        p_count = 75
        max_generations = 150000
        max_cost = 17
        selective_pressure = 1.35
        p1 = project.Project(cost=[1, 2, 3.1], revenue=[5.2, 6, 8])
        p2 = project.Project(cost=[2, 3, 3.9], revenue=[8.5, 7, 12])
        p3 = project.Project(cost=[1.3, 2.8], revenue=[3.4, 5.7])
        p4 = project.Project(cost=[0.9, 3, 4.1], revenue=[4.7, 9.5, 11.9])
        p5 = project.Project(cost=[2.1, 3.8, 4.2, 3.1], revenue=[6.4, 9.3, 10, 8.8])
        p6 = project.Project(cost=[3.8, 4.5, 5.6], revenue=[13.3, 15.7, 17.1])
        projects = [p1, p2, p3, p4, p5, p6]
        p = population(p_count, projects)
        fitness_history = [grade(p, projects, max_cost)]
        max_grade = fitness_history[0]
        print(round(max_grade, 2))
        grade_counter = 0
        last_iter = 0
        for i in range(max_generations):
            p = evolve(p, projects, max_cost, sp=selective_pressure)
            g = grade(p, projects, max_cost)
            fitness_history.append(g)
            # termination condition check
            if i - last_iter > 10000 or grade_counter >= 40:
                break
            if g == max_grade:
                grade_counter += 1
                print(i, round(g, 2))
            elif g > max_grade:
                max_grade = g
                full_list = [(i, j) for i, j in zip(mcf.most_common_unhashable(p), items)]
                last_iter = i
                print(i, round(g, 2))
        # print/plot output
        print('\n')
        print(i + 1, max_grade, grade_counter)
        print(full_list)
        total_cost = 0
        for k, p in enumerate(full_list):
            projects[k].set_alternatives(p[0])
            total_cost += projects[k].get_cost()
            print(p[1] + ': Alternative ' + str(p[0].index(1) + 1))
        print('\nTotal Cost: ' + str(round(total_cost, 2)))
        plt.plot(fitness_history)
        plt.ylabel = 'Fitness'
        plt.grid(True)
        plt.show()
    except Exception as e:
        print(e)

most_common_funcs.py

from collections import Counter
import itertools
import operator


def most_common(lst):
    data = Counter(lst)
    return max(lst, key=data.get)


def most_common_unhashable(L):
    # get an iterable of (item, iterable) pairs
    SL = sorted((x, i) for i, x in enumerate(L))
    # print 'SL:', SL
    groups = itertools.groupby(SL, key=operator.itemgetter(0))
    # auxiliary function to get "quality" for an item

    def _auxfun(g):
        item, iterable = g
        count = 0
        min_index = len(L)
        for _, where in iterable:
            count += 1
            min_index = min(min_index, where)
        # print 'item %r, count %r, minind %r' % (item, count, min_index)
        return count, -min_index
    # pick the highest-count/earliest item
    return max(groups, key=_auxfun)[0]

if __name__ == '__main__':
    lst = [[0, 0, 1], [1, 1, 1], [0, 1, 0], [1, 1, 1], [0, 0, 1], [1, 1, 1]]
    lcommon = most_common_unhashable(lst)
    print(lcommon)