如何将终止条件添加到背包问题以及如何显示图表？

Question

我是Python的新手，我有这个背包问题，那里有项目及其体重。用户将插入其优先级（低中级）。然后，GA将运行以找到最大化优先点的最佳背包列表，而不会超过最大重量（30kg）。

我做了大多数遗传操作员，除了终止条件（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[i])


# 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[i] == 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()

Answer 1

如果我将您的主要循环更改为此，它似乎可以正常工作：

def main():
    population = create_initial_population(POP_SIZE)
    fit = []
    for generation in range(GENERATIONS):
        #print("Generation %d with %d" % (generation+1, len(population)))
        population = sorted(
            population, key=lambda x: compute_fitness(x), reverse=True)

        # First item in population has best fitness.
        fit.append( compute_fitness(population[0] ) )
        population = creating_new_generation(population)
    print(
        f"The Best items for the customer backpacking:{(genome_to_items(population[0],items.items()))}")
    print("Maximum fitness: " + str(max(fit)))
    plt.plot(fit)
    plt.ylabel('Fitness')
    plt.xlabel('Generations')
    plt.show()