Как добавить условие завершения к задаче о рюкзаке и как показать график? ⇐ Python

[Anonymous]

Я новичок в Python, у меня проблема с рюкзаком, где есть предметы и их вес. Пользователь укажет свой приоритет (низкий-средний-высокий). А затем GA запустится, чтобы найти лучший список рюкзаков, который максимизирует приоритетные точки, не превышая максимальный вес (30 кг).
Я выполнил большинство генетических операторов, за исключением того, что условие завершения (после 20000 поколений или когда приспособленность достигает 1) не сработало, и график (график) производительности GA не отображается.
Код:
import matplotlib.pyplot as plt
import random
import time
from unittest import result

# Data (search space)
items = {
'Sleeping bag': 10,
'Rope': 3,
'Pocket Knife': 2,
'Torch': 5,
'Water Bottle': 9,
'Glucose': 8,
'First aid supplies': 6,
'Rain jacket': 3,
'Personal Locator Beacon': 2
}

Genome = list[int]
# Number of items
ITEMS_COUNT = len(items)

# # Number of points for the multi point crossover entered by the user. Default is 3
N_POINT = 3

# # Number of individulas in the population filled with some permutation of 0s and 1s entered by the user. Default is 50
POP_SIZE = 20

# # Elitisim for selection. Default is True
ELITISM = True

# # Number of generations entered by the user. Default is 200
GENERATIONS = 200

# # Crossover probability enterd by the user. Default is 0.1
CROSSOVER_PROBABILTY = 0.1

# # Mutate probability entered by the user. Defaulst is 0.05
MUTATION_PROBABITLY = 0.05

# Priorities
itemsPriorities = {'low': 5, 'medium': 10, 'high': 15}

# User input
def user_input():
print('Welcome to Smart Hiker Backpacking!')
print('Input your priority for items based on the priority legend: ')
print('Low \t Medium \t High')
print()
print('Choose your priority for these items below: ')
print('-'*50) # design: ------
for item, _ in items.items(): # Print items
print(item)
print('-'*50) # design: ------

prio_l = []

# Ask user to enter a priority for every item
# Goes through and displays every item in the data (search space)
for item in items:
prio_input = str(input(f"What is your priority for {item}? "))
while prio_input.lower() not in itemsPriorities.keys(): # convert entered data by the user to lower case

# Asks the user again to enter a correct choice (low, medium, high), regardless of the capitalization
prio_input = str(input('Please enter low, medium or high: '))
else:
prio_l.append(itemsPriorities[prio_input.lower()])
return prio_l

priority_list = user_input()

# Print the item name and its entered priority
print('-'*50) # design: ------
for i, j in enumerate(items):
print(j, 'has a priority of: ', priority_list)

# Assume the population size is 20
pop_size = 20

# generate initial population

def create_initial_population(amount):
#global pop_size
return [generate_genome() for i in range(0, amount)]
# generate genome

def generate_genome():
return [random.randint(0, 1) for x in range(0, len(items))]

print('-'*50) # design: ------
#print("Population:\n", create_initial_population(POP_SIZE))

# Compute fitness function

def compute_fitness(target):
total_points = 0
total_weight = 0
index = 0

# Sum of priority points and weight
for i in target:
if index >= len(items):
break
if (i == 1):
total_points += priority_list[index]
total_weight += list(items.values())[index]
index += 1

# Cheking to fit
if total_weight > 30:
return 0
else:
return total_points

def get_total_points(pop):
total_points = 0
for target in pop:
total_points += compute_fitness(target)
return total_points

# mutating a point on a solution
def mutate(target):
r = random.randint(0, len(target)-1)
if target[r] == 1:
target[r] = 0
else:
target[r] = 1

# selecting parents by using roulette wheel selection

def roulette_wheel_selection(pop, parent_number):
parents = []
total_points = get_total_points(pop)
current_value = 0
# spining the wheel and select parent based on rate of value and total_points
for spin in range(0, parent_number):
spin_value = random.randint(0, total_points)
for target in pop:
current_value += compute_fitness(target)
if current_value >= spin_value:
# print "SPIN!!! ,%s, TOTAL VALUE / SPIN VALUE : %s/%s, fit: %s" % (str(target),str(total_points), str(spin_value) , fitness(target))
parents.append(target)
pop.remove(target)
total_points = get_total_points(pop)
break
# print("-------------------------------------------------------------------------")
return parents

# n-point crossover by using two solution to generate their child

def crossover(father, mother):
# deciding the lines to split the solution
genes_points = [0]
genes_points += sorted(random.sample(range(2, ITEMS_COUNT), N_POINT))
genes_points += [ITEMS_COUNT]
child = []
# creating a new child by using father and mother data
for count in range(0, N_POINT+1):
start = genes_points[count]
end = genes_points[count+1]
# chosing which part of father or mother
if count % 2 == 0:
child += father[start:end]
else:
child += mother[start:end]
return child

# generating a new generation by mutation and crossover

def creating_new_generation(pop):
# selection with roulette_wheel_selection
new_generation = []
parents = []

if ELITISM:
parents = pop[int(0): int(POP_SIZE/5)]
else:
parents = roulette_wheel_selection(pop, (POP_SIZE/5))

parents_length = len(parents)
new_generation.extend(parents[:])
# mutating selected parents
for p in parents:
if MUTATION_PROBABITLY > random.random():
mutate(p)
children = []
desired_length = POP_SIZE - parents_length
# creating new children by using parents
while len(children) < desired_length:
# crossover cheking
if CROSSOVER_PROBABILTY > random.random():
# selecting two parents randomly
father_and_mother = random.sample(range(0, parents_length-1), 2)
father = parents[father_and_mother[0]]
mother = parents[father_and_mother[1]]
# crossover selected two parents to create a new child
child = crossover(father[:], mother[:])
else:
# or cloning a parent randomly
child = parents[random.randint(0, parents_length-1)][:]
# checking to mutate the new child
if MUTATION_PROBABITLY > random.random():
mutate(child)
children.append(child[:])
new_generation.extend(children[:])
return new_generation

def genome_to_string(genome) -> str:
return "".join(map(str, genome))

def genome_to_items(genome, ITEMS):
result = []
for i, itm in enumerate(ITEMS):
if genome == 1:
result += [itm]
return result

def main():
#start_time = time.time()
population = create_initial_population(POP_SIZE)
max_fit = 0
for generation in range(1, GENERATIONS+1):
plt.plot(generation, max_fit)
plt.ylabel('Fitness')
plt.xlabel('Generations')
plt.show()
#print("Generation %d with %d" % (generation, len(population)))
population = sorted(
population, key=lambda x: compute_fitness(x), reverse=True)

for i in population:
# print "%s, fit: %s" % (str(i), fitness(i))
if compute_fitness(i) > max_fit:
max_fit = compute_fitness(i)

population = creating_new_generation(population)
# for item in items:
# print(item)
#elapsed_time = time.time() - start_time
#print( "Best: %s (%f)" % (genome_to_string(population[0]), compute_fitness(population[0])))
print(
f"The Best items for the customer backpacking:{(genome_to_items(population[0],items.items()))}")
print("Maximum fitness: " + str(max_fit))
#print ("Time : " + str(elapsed_time) + " seconds")

main()


Подробнее здесь: https://stackoverflow.com/questions/722 ... -the-graph