Hill_climbing_with_exploitation.py

# -*- coding: utf-8 -*-
"""
Created on Wed Sep 25 14:09:39 2019

@author: Rennan Valadares

The problem: I would like to implement a hill climbing algorithm with an exploitation vision,
that could achieve the global maxima.
The main goal is to maximize the number of bits 1, into binary numbers between 0 and 15.

"""
from random import randint

#create a dictionary of numbers between min_number and max_number
def make_dict(min_number, max_number, list = [], decision_variables = { }):
    for i in range(min_number,max_number+1):
        list.append(i)
        decision_variables = {"Numbers":list }
    return decision_variables



#function for random the first number
def build_solution(encoding, decision_variables):
    max = encoding[-1]
    min = encoding[0]
    i = randint(min, max) # << generate a random number
    return i

#function for returning the fitness of the solution
def objective_function(solution, decision_variables = {}):
    fitness = 0
    binary_rep = dec2bin(solution)
    if solution == 0:
        fitness = 0
    else:
        for digit in binary_rep:
            if digit == 0:
                fitness = 0
            else:
                fitness += int(digit) #fitness = fitnedd + digit
    return fitness




#function for checking if the solution is inside the search space
def is_admissible(solution):
    min = 0
    max = 15
    return (solution >= min and solution <= max)

#function for getting the neighbours
def get_neighbours(solution, decision_variables):
    numbers = decision_variables["Numbers"]
    neig = []
    if solution == numbers[0]:
        neig.append(solution + 1)
    elif solution == numbers[-1]:
        neig.append(solution-1)
    else:
        neig.append(solution - 1)
        neig.append(solution + 1)
    return neig


# dec2bin transforms the number into binary
def dec2bin(n):
    b = ''
    while n != 0:
        b = b + str(n % 2)
        n = int(n / 2)
    x = b[::-1]
    if len(x) == 4:
        return x
    elif len(x) == 3:
        return "0" + x
    elif len(x) == 2:
        return "00" + x
    elif len(x) == 1:
        return "000" + x

#transform binary to decimal
def binary_to_decimal( solution ):
    solution_str = ''

    for digit in solution:
        solution_str += str(digit)

    i = int(solution_str, 2)

    return i


#fuction for searching the key in a dict from the value
def search(term, dic):
    list = []
    for k, v in dic.items():
        if term == v:
            list.append(k)


#flip 1 random bit on each neighbour
def change_bits(binary_list):
    string_list = []
    exploited_neig = []

    for b in binary_list:
        start = 0
        end = 1
        this_string = []
        for i in b:
            this_string.append(b[start:end])
            start += 1
            end += 1
        string_list.append(this_string)


    for b in string_list:
        nr = randint(0,len(b)-1)
        if b[nr] == "0":
           b[nr] = "1"
        elif b[nr] == "1":
            b[nr] = "0"
        else:
            raise(SystemExit(b[nr], "is diferent than 1 or 0"))

    for item in string_list:
        ns = ""
        for i in item:
            ns += i
        exploited_neig.append(ns)
    return exploited_neig

def exploitation(neighbours = []):
    new_neighbours = []
    new_binary_neighbours = []
    binary = []
    for neighbour in neighbours:
        if neighbour == 0:
            binary.append("0000")
        else:
            binary.append(str(dec2bin(neighbour)))

    new_binary_neighbours = change_bits(binary)
    for i in new_binary_neighbours:
        new_neighbours.append(binary_to_decimal(i))
    return new_neighbours




#split the dictionare intro 2 lists compare with exploited values returning
#a list with the 2 best neighbours
def compare_fitness(neig_fitness, exploit_neig_fitness):
    n_fitness = []
    e_fitness = []
    n_solution = []
    e_solution = []
    new_neig = []

    for solution, fitness in neig_fitness.items():
        n_fitness.append(fitness)
        n_solution.append(solution)

    for solution, fitness in exploit_neig_fitness.items():
        e_fitness.append(fitness)
        e_solution.append(solution)

    new_neig = compare_lists(n_solution, e_solution, n_fitness,e_fitness)
    return new_neig



#compare 2 lists and return the max value, rangemax is the index number of itens that
#you want to compare
def compare_lists(n_solution, e_solution, n_fitness, e_fitness):

    new_list = []
    len_list = []
    len_list.append(len(n_solution))
    len_list.append(len(e_solution))
    len_list.append(len(n_fitness))
    len_list.append(len(e_fitness))

    for i in range(0, min(len_list)):
        if n_fitness[i] > e_fitness[i]:
            new_list.append(n_solution[i])
        else:
            new_list.append(e_solution[i])
    return new_list


#run the hill climbing algorithm
def hill_climbing(encoding, iterations):
    decision_variables = make_dict(0,15)
    first_solution = randint(encoding[0], encoding[-1])
    first_fitness = 0
    best_fitness = 0
    best_solution = first_solution
    list_of_solutions = []


    #Test if the solution is in the Search space
    if first_solution == 0:
        best_fitness = 0
        best_solution = 0
    elif is_admissible(first_solution):
        first_fitness = objective_function(first_solution)
        best_fitness = first_fitness
        best_solution = first_solution
        list_of_solutions.append(first_solution)
    else:
        raise SystemExit(first_solution, "is out of the search space.")


    #Loop of iterations that you set on the parameters
    for i in range(0,iterations):
        neighbours = []
        neighbour_fitness = {}
        better_neig_fitness = 0
        better_neig_solution = 0
        exploit_neighbours = []
        exploit_neighbours_fitness = {}
        best_neighbours = []
        best_neightbours_fitness = {}


        #populate neightbours
        for i in get_neighbours(best_solution, decision_variables):
            neighbours.append(i)

        #populate exploit neightbours
        exploit_neighbours = exploitation(neighbours)


        #populate neightbours fitness
        for neighbour in neighbours:
            neighbour_fitness.update({neighbour:objective_function(neighbour)})

        #populate exploit_neightbours_fitness to compare with neighbours fitness
        for neighbour in exploit_neighbours:
            exploit_neighbours_fitness.update({neighbour:objective_function(neighbour)})

        #compare neighbours x exploited neighbours and return the best list
        best_neighbours = compare_fitness(neighbour_fitness, exploit_neighbours_fitness)

        #populate the best neighbours fitness dictionary
        for neighbour in best_neighbours:
            best_neightbours_fitness.update({neighbour:objective_function(neighbour)})




        #check if the solution was already used and
        #test which neighbour has the best fitness
        for solution, fitness in best_neightbours_fitness.items():
            if solution in list_of_solutions:
                continue
            if fitness>=better_neig_fitness:
                better_neig_fitness = fitness
                better_neig_solution = solution



        #put on global var (memory) the best result found in this iteration
        if better_neig_fitness >= best_fitness:
            best_solution = better_neig_solution
            best_fitness = better_neig_fitness
            list_of_solutions.append(best_solution)

    print("Number",first_solution, "was the first solution random selected and its fitness was", first_fitness)
    print("Number",best_solution, "is now the best Solution and its fitness is", best_fitness)
    for i in range(0,len(list_of_solutions)):
        x = i +1
        print(str(x)+ "º", "solution was:", list_of_solutions[i])


#Right now the algorithm can't suport numbers bigger than 15 but soon i will improve to accept any number.
encoding = [0, 15]
hill_climbing(encoding, 10)