Moortiii

Genetic Algorithm

Jan 17th, 2021
824
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. import random
  2.  
  3. def calculate_fitness(bits, items, threshold):
  4.     total_cost = 0
  5.     total_weight = 0
  6.  
  7.     #print("Items in fitness check:", items)
  8.  
  9.     for i, bit in enumerate(bits):
  10.         if bit == 1:
  11.             item = items[i]
  12.             total_cost += item[1][0]
  13.             total_weight += item[1][1]
  14.    
  15.     if total_weight <= threshold:
  16.         return total_cost
  17.    
  18.     return 0
  19.  
  20. def perform_selection(items):
  21.     backpack = []
  22.  
  23.     for _ in range(len(items)):
  24.         if random.random() > 0.5:
  25.             backpack.append(1)
  26.         else:
  27.             backpack.append(0)
  28.  
  29.     return backpack
  30.  
  31. def crossover_split(parent_a, parent_b):
  32.     """ Single point crossover split """
  33.     split_index = 3
  34.  
  35.     parent_1, splice_1 = parent_a[:split_index], parent_a[split_index:]
  36.     parent_2, splice_2 = parent_b[:split_index], parent_b[split_index:]
  37.     parent_1.extend(splice_2)
  38.     parent_2.extend(splice_1)
  39.  
  40.     return parent_1, parent_2
  41.  
  42. def mutate(bits):
  43.     """ Mutate by flipping bits pseudo-randomly """
  44.     output = ''
  45.     threshold = 0.9
  46.  
  47.     for bit in bits:
  48.         if random.random() > threshold:
  49.             if bit == 1:
  50.                 output += '0'
  51.             else:
  52.                 output += '1'
  53.         else:
  54.             output += str(bit)
  55.  
  56.     #print("I:", ''.join([str(bit) for bit in bits]))
  57.     #print("O:", output)
  58.     return [int(bit) for bit in output]
  59.  
  60. def generate_population(items, n):
  61.     selections = []
  62.  
  63.     for _ in range(n):
  64.         selections.append(perform_selection(items))
  65.  
  66.     return selections
  67.  
  68. generations = 5
  69. population_size = 10
  70.  
  71. items = {
  72.     0: ("laptop", (500, 2200)),
  73.     1: ("headphones", (150, 160)),
  74.     2: ("coffee mug", (60, 350)),
  75.     3: ("notepad", (40, 333)),
  76.     4: ("water bottle", (30, 192))
  77. }
  78.  
  79. # The initial population is entirely random
  80. population = generate_population(items, 10)
  81.  
  82. # Apply the algorithm
  83. for generation in range(generations):
  84.     print(f"Generation {generation + 1}.")
  85.  
  86.     # calculate the fitness score for each of the members of the population
  87.     fitness_scores = []
  88.  
  89.     for entry in population:
  90.         fitness_scores.append((entry, calculate_fitness(entry, items, 3000)))
  91.  
  92.     best = sorted(fitness_scores, key=lambda xy: xy[1])[::-1]
  93.    
  94.     elitism_count = 2
  95.     elite = best[0:elitism_count]
  96.     next_population = []
  97.  
  98.     for entry in elite:
  99.         bits, score = entry
  100.         next_population.append(bits)
  101.  
  102.     while len(next_population) < population_size:
  103.         index_a = random.randint(0, len(items))
  104.         index_b = random.randint(0, len(items))
  105.  
  106.         while index_b == index_a:
  107.             index_b = random.randint(0, len(items))
  108.  
  109.         results = crossover_split(
  110.             population[index_a], population[index_b])
  111.  
  112.         next_population.extend(results)
  113.  
  114.     print("Next population:", next_population)
  115.     mutated_population = []
  116.  
  117.     for entry in next_population:
  118.         mutation = mutate(entry)
  119.         mutated_population.append(mutation)
  120.  
  121.     population = mutated_population
  122.  
  123. print("Finished.")
RAW Paste Data