Tutorial: Solving your own problems with EasyGA - danielwilczak101/EasyGA GitHub Wiki

Below is a complete tutorial on how to use EasyGA to solve your own problems. Further customization is discussed in the rest of the wiki.

In this tutorial, we will learn how to

1. use EasyGA's data structure.
2. encode a problem into a fitness function.
3. select methods appropriate for the problem.
4. run the GA and show the results.

Problem Statement

The below tutorial uses the assignment problem:

There is a collection of tasks that need to be completed and a collection of workers that can complete tasks. The amount of tasks and workers are the same. However, tasks may be more expensive to assign to some workers than others, and each worker can complete at most one task. Find which task should be assigned to each worker so that the least amount of cost is incurred.

Data Structure

from EasyGA import GA

# create ga to run example
ga = GA()
# initialize population
ga.evolve(1)

# show the population
print(ga.population)
# show the best chromosome
print(ga.population[0])
# show its first gene
print(ga.population[0][0])
# show that gene's value
print(ga.population[0][0].value)

Genetic algorithms use array-like data structures. The GA contains a population, which is a list of chromosomes, and each chromosome is a list of genes. Each gene contains a .value attribute, which may be numeric, string, or otherwise, depending on the nature of your problem.

Looping over the data

from EasyGA import GA

# create ga to run example
ga = GA()
# initialize population
ga.evolve(1)
# get the best chromosome
chromosome = ga.population[0]

# loop over the chromosome
for gene in chromosome:
    print(gene)

# loop over gene values
for value in chromosome.gene_value_iter:
    print(value)

Populations and chromosomes may also be looped over. Chromosomes additionally have the .gene_value_iter and .gene_value_list properties, which allow direct looping over their genes' values.

Initializing chromosomes

import random
from EasyGA import GA


# Inherit the GA class to modify its methods
class Assignment_Problem_GA(GA):

    # initialize the ga with the costs matrix
    def __init__(ga, costs):
        super().__init__()
        ga.costs = costs

    # initialize a random chromosome
    def chromosome_impl(ga):
        # shuffle tasks around
        chromosome = list(range(len(ga.costs)))
        random.shuffle(chromosome)
        return chromosome

When the GA needs to create new chromosomes, the chromosome_impl method is called. A list of values should be returned to create the new chromosome. In the above example, a random shuffle is used to assign tasks to workers randomly.

Fitness Functions

import random
from EasyGA import GA


class Assignment_Problem_GA(GA):

    def __init__(ga, costs):
        super().__init__()
        ga.costs = costs
        # our goal is to minimize the costs
        ga.target_fitness_type = 'min'

    def chromosome_impl(ga):
        chromosome = list(range(len(ga.costs)))
        random.shuffle(chromosome)
        return chromosome

    # the "value" of a chromosome is the total costs
    def fitness_function_impl(ga, chromosome):
        total_cost = 0
        # for each worker, get the cost of their task
        for task_costs, task_chosen in zip(ga.costs, chromosome.gene_value_iter):
            total_cost += task_costs[task_chosen]
        return total_cost


# costs for worker 1 are [1, 2, 3] for each task
costs = [[1, 2, 3],
         [3, 4, 7],
         [8, 1, 3]]

# create the genetic algorithm
ga = Assignment_Problem_GA(costs)

To measure how good a chromosome is, a fitness function is called. In our Assignment Problem GA, we loop over each worker, getting the cost of the task they're assigned to. The total of these costs is the fitness of the chromosome.

Since we want to find the minimum cost, ga.target_fitness_type is set to 'min' in the __init__. If we wanted the maximum cost instead, we could set ga.target_fitness_type to 'max' instead.

Making Appropriate Methods

import random
from EasyGA import GA


class Assignment_Problem_GA(GA):

    def __init__(ga, costs):
        super().__init__()
        ga.costs = costs
        ga.target_fitness_type = 'min'

    def chromosome_impl(ga):
        chromosome = list(range(len(ga.costs)))
        random.shuffle(chromosome)
        return chromosome

    def fitness_function_impl(ga, chromosome):
        total_cost = 0
        for task_costs, task_chosen in zip(ga.costs, chromosome.gene_value_iter):
            total_cost += task_costs[task_chosen]
        return total_cost

    # we don't need to combine chromosomes
    def crossover_individual_impl(ga, parent1, parent2):
        pass

    # randomly swap assigned tasks between two workers
    def mutation_individual_impl(ga, chromosome):
        chromosome.fitness = None
        index1, index2 = random.sample(range(len(chromosome)), 2)
        chromosome[index1], chromosome[index2] = chromosome[index2], chromosome[index1]


costs = [[1, 2, 3],
         [3, 4, 7],
         [8, 1, 3]]

ga = Assignment_Problem_GA(costs)

Not all GA methods are appropriate for our specific problem. For example, we have to keep in mind that every task is assigned to only one worker. The methods related to chromosome modifications are the crossover_individual_impl and mutation_individual_impl methods.

The crossover_individual_impl is for combining two chromosomes. This doesn't make much sense for our problem, so we do nothing.

The mutation_individual_impl is for changing a chromosome. In the above example, we randomly swap two tasks.

Running the GA and Showing Results

ga.evolve()
ga.print_best_chromosome()

To run the ga, we use ga.evolve(). To show the results, we use ga.print_best_chromosome(). The results are:

Best Chromosome         : [2][0][1]
Best Fitness            : 7

Looking back at the costs, we can see our end result was:

costs = [[1, 2, 3],  # last task costs $3
         [3, 4, 7],  # first task costs $3
         [8, 1, 3]]  # second task costs $1

And this is indeed the solution to our problem!