Constraint Problems - danielwilczak101/EasyGA GitHub Wiki

Some mathematical problems, such as linear programs, quadratic programs, and similar constraint-type problems may be solved using EasyGA.

Example:

Minimize the objective function:

x^3 + xy

over the values of x and y that satisfy the inequalities:

x^2 + y^2 < 10

x^2 + 3xy - y^2 > 5

0 < x < 10

0 < y < 10

Such a problem may be solved using a modification of the Big M method by adding the errors (how badly the inequalities are satisfied) to the objective function but massively scaled up so that the GA will first attempt to remove the errors from the problem before solving further.

import EasyGA
import random
import math
import numpy as np
import matplotlib.pyplot as plt

# Create the Genetic algorithm
ga = EasyGA.GA()

# Create 25 chromosomes each with 10 genes and 200 generations
ga.population_size = 100
ga.chromosome_length = 2
ga.generation_goal = 150
ga.chromosome_mutation_rate = 0.25

# Create random genes from 0 to 10
ga.gene_impl = lambda: random.uniform(0, 10)


# Solve quadratic program:
# Minimize:
#     x^3 + xy
# Subject to:
#     x^2 + y^2 < 10
#     x^2 + 3xy - y^2 > 5
#     0 < x < 10
#     0 < y < 10

def fitness_function_impl(chromosome):
    # Unpack x and y from chromosome
    x, y = [gene.value for gene in chromosome.gene_list]

    # Collect errors
    error_list = [
        x**2+y**2-10,
        5-x**2-3*x*y+y**2,
    ]

    # Objective function plus very large errors
    return x**3+x*y + 1e50*sum(max(error, 0)**2 for error in error_list)

ga.fitness_function_impl = fitness_function_impl
ga.target_fitness_type = 'min'


# Cross genes by choosing random floats between the genes
ga.crossover_individual_impl = EasyGA.Crossover_Methods.Individual.Arithmetic.average

# Solve and plot
plt.figure(figsize = [6, 6])

# Plot first constraint
Theta = np.linspace(0, 0.5*math.pi, num = 100)
R = [math.sqrt(10)]*100
X = [
    r*math.cos(theta)
    for r, theta
    in zip(R, Theta)
]
Y = [
    r*math.sin(theta)
    for r, theta
    in zip(R, Theta)
]
plt.plot(X, Y)

# Plot second constraint
Theta = np.linspace(0, 0.4*math.pi, num = 100)
R = [math.sqrt(max(5/(math.cos(theta)**2+3*math.cos(theta)*math.sin(theta)-math.sin(theta)**2), 0))
     for theta
     in Theta
]
X = [
    r*math.cos(theta)
    for r, theta
    in zip(R, Theta)
]
Y = [
    r*math.sin(theta)
    for r, theta
    in zip(R, Theta)
]

plt.plot(X, Y)

# Plot GA's best, 5th best, and 10th best points from each generation
X = []
Y = []

while ga.active():
    ga.evolve_generation()
    for i in (0, 5, 10):
        x, y = (gene.value for gene in ga.population[i])
        X.append(x)
        Y.append(y)

ga.print_population()

plt.scatter(X, Y)
plt.xlabel('x')
plt.ylabel('y')
plt.title('Plot of points found by GA.')
plt.show()

The blue curve represents the line x^2 + y^2 = 10 while the orange curve represents the line x^2 + 3xy - y^2 = 5. A scatter plot of the best, 5th best, and 10th best points from each generation are shown below. Initially it can be seen that the results are generally scattered but eventually converge to the solution near the border of the orange curve.