# Untitled

unknown
plain_text
2 months ago
4.2 kB
2
Indexable
Never
```import random

IdealBag = [(25, 300, 1000)]
population = 500  # population size
pc = 0.9 # crossover probability
pm = 0.6  # mutation probability
knapsack = []
generations = 100

# Generates a bag in the form of (a, b, c)
def generateBag():
Weight = random.randint(0, 100)
profit = random.randint(0, 100)
Size = random.randint(0, 10000)
return Weight, profit, Size

# Performs crossover between two parents
def crossover(parent1, parent2):
# Choose a crossover point (random index to split the bag tuple)
crossover_point = random.randint(0, 2)  # 0 for weight, 1 for profit, 2 for size

# Create offspring by combining genetic material of parents at the crossover point
child1 = parent1[:crossover_point] + parent2[crossover_point:]
child2 = parent2[:crossover_point] + parent1[crossover_point:]

return child1, child2

# Calculates fitness score of an individual bag
def fitness(bag, ideal_bag):
weight_diff = abs(bag[0] - ideal_bag[0][0])
profit_diff = abs(bag[1] - ideal_bag[0][1])
size_diff = abs(bag[2] - ideal_bag[0][2])
total_diff = weight_diff + profit_diff + size_diff
return 1 / (1 + total_diff)  # Return fitness score

# Performs mutation on two children
def mutation(child1, child2):
mutated_child1 = list(child1)
mutated_child2 = list(child2)

# Randomly select an attribute to mutate
attribute_index = random.randint(0, 2)  # 0 for weight, 1 for profit, 2 for size

# Mutate the selected attribute by adding a small random value
mutation_amount = random.randint(-10, 10)  # Adjust mutation range as needed
mutated_child1[attribute_index] += mutation_amount
mutated_child2[attribute_index] += mutation_amount

# Ensure attribute values stay within valid range
mutated_child1[attribute_index] = max(0, mutated_child1[attribute_index])
mutated_child2[attribute_index] = max(0, mutated_child2[attribute_index])

return tuple(mutated_child1), tuple(mutated_child2)

# Generate initial population
individuals = [generateBag() for _ in range(population)]  # creates a list of each (a,b,c)

best_fitness = 0
best_individual = None

# Evolution loop over generations
for generation in range(generations):
fitness_scores = [fitness(individual, IdealBag) for individual in individuals]

# Update best fitness and best individual for the generation
max_fitness = max(fitness_scores)
max_index = fitness_scores.index(max_fitness)
if max_fitness > best_fitness:
best_fitness = max_fitness
best_individual = individuals[max_index]

# Print generation number, best individual, and its fitness
print(f"Generation: {generation + 1}, Best Individual: {best_individual}, Fitness: {best_fitness}")

# Check for perfect match
if best_fitness >= 0.98:
print(f"Perfect match found in generation {generation + 1}!")
print(f"Best Individual: {best_individual}, Fitness: {best_fitness}")
break

# Sort individuals based on fitness scores
sorted_individuals = [individual for _, individual in sorted(zip(fitness_scores, individuals), reverse=True)]

# Keep the top population fittest individuals
individuals = sorted_individuals[:population]

# Apply crossover and mutation to create new individuals
new_individuals = []
for _ in range(population):
parent1 = random.choice(individuals)
parent2 = random.choice(individuals)

# Apply crossover based on the crossover probability (pc)
if random.random() < pc:
child1, child2 = crossover(parent1, parent2)
else:
child1, child2 = parent1, parent2

# Apply mutation based on the mutation probability (pm)
if random.random() < pm:
child1, child2 = mutation(child1, child2)

new_individuals.append(child1)
new_individuals.append(child2)

# Extend the population with the new individuals
individuals.extend(new_individuals)

else:
print("No perfect match found within specified generations.")
```