Evolutionary Algorithms

FIRST_POPULATION_SIZE = 93123;
N = 10

def generate_random_population():
   population = []
   for i in range(FIRST_POPULATION_SIZE):
       X = []

       # --- YOUR CODE HERE
       X = [randint(0, 1) for i in range(N)]

       X = [i for i in range(N)]
       random_shuffle(X)
       # --- YOUR CODE ENDS HERE

       population.append(X)

   return population


# This doesn't account for permutations
def order_crossover(X, Y):
    N = len(X)
    a = randint(0, N - 2)
    b = randint(0, N - 2)
    if a > b:
        swap(a, b)

    C1 = X, C2 = Y
    for i in range(a, b+1):
         swap(C1[i], C2[i])

        return C1, C2


# Crossover over permutations
def order_crossover(X, Y):
    N = len(X)
    a = randint(0, N - 2)
    b = randint(0, N - 2)
    if a > b:
        swap(a, b)

    C1 = [], C2 = []
    for i in range(a, b + 1):
         C1.append(X[i])
         C2.append(Y[i])

    U = [], V = []
    for i in range(b, N + a):
         if Y[i%N] not in C1:
             U.append(Y[i%N])

    for i in range(b, N + a):
         if X[i%N] not in C2:
             V.append(X[i%N])

    C1 = (C1 + U)[a:] + (C1 + U)[:a]
    C2 = (C2 + V)[a:] + (C2 + V)[:a]
    return C1, C2



def algo():
    population = generate_random_population()
    for epoch in range(E):
        # SELECTION

        # KRIZENJE

        # MUTACIJA

        # ZAMENA NA CHILDS AND PARENTS

        # GOAL?



def h(X):
    # calculate the strength of X


def goal(X):
   for gene in X:
      if gene == 0:
         return false
   return true


LIMIT_SIZE = 312875

def algo():
    population = generate_random_population()
    for epoch in range(E):
        selected_parents = selection(population)
        children = merge(selected_parents)
        children = map(mutate, children)
        population = children + population[:0.03 * len(population)]
        population = population[:LIMIT_SIZE]
        for child in children:
            if goal(child):
                return child





## KRIZENJE

def kpoint_crossover(X, Y, K):
   N = len(X)
   points = [randint(0, N - 1) for i in range(K)]
   points = sorted(points)
   if K % 2 == 1:
      points.append(N)

   for i in range(0, K, 2):
       for j in range(points[i], points[i+1]):
           swap(X[j], Y[j])

   return X, Y


def uniform_crossover(X, Y, P):
    for i in range(0, N - 1):
        if randfloat(0, 1) < P:
            swap(X[i], Y[i])

     return X, Y



## MUTACIJA

# probability for mutation to happen
Pm = 0.03

def mutate(child):
    if randfloat(0, 1) <= Pm:
        u = randint(0, N - 1)
        child[u] = 1 - child[u]
    return child

## MUTACII ZA PERMUTACII

def mutate_swap(child):
    if randfloat(0, 1) <= Pm:
       u = randint(0, N - 1)
       v = randint(0, N - 1)
       swap(child[u], child[v])
    return child

def mutate_insertion(child):
    if randfloat(0, 1) <= Pm:
       u = randint(0, N - 1)
       v = randint(0, N - 2)
       t = child[u]
       child.pop(u)
       return child[:(v-1)] + [t] + child[v:]
    return child

def mutate_reverse(child):
    if randfloat(0, 1) <= Pm:
        u = randint(0, N - 1)
        v = randint(0, N - 1)
        if u > v:
           swap(u, v)

        return child[:u] + list(reverse(child[u:v])) + child[v:]
    return child





## MERGE

def merge(population):
    children = []
    for i in range(0, len(population), 2):
        C1, C2 = crossover(population[i], population[i+1])
        children.append(C1, C2)

    return children


## SELEKCII

def proportional_selection(population):
    sumG = sum([h(X) for X in population])

    result = []
    for X in population:
        if randfloat(0, 1) <= h(X) / sumG
            result.append(X)

    return result

def linear_selection(population):
    population.sort(lamdba x: h(x))

    g = [0 for i in range(len(population))]
    for i in range(population):
        g[i] = 2 - PS + 2 * (PS-1) * (i - 1) / (n - 1)

    result = []
    for i in range(len(population)):
        if randfloat(0, 1) <= g[i] / sum(g)
            result.append(population[i])

    return result


def stochastic_selection(population, K):
    START = randfloat(0, 1 / K)

    for i .... len(pop)
         g[i] = h(population[i])

    for i ..... len(pop)
          g[i] = g[i] / sum(g)

    result = []
    for p in range(K):
         i = 0
         while sum(g[:i]) < (START + p / K):
             i++
         result.append(population[i])

    return result


def tournament_selection(population, K, NEW_POPULATION_SIZE):
    result = []
    for i in range(NEW_POPULATION_SIZE):
        random_choice = random.choices(population, K)
        random_choice.sort(lambda x: -h(x))

        # take only the best
        result.append(random_choice[0])

    return result