import random

num_items=6#物品數(shù)量
capacity=80#容量大小
weight=[25,15,20,30,20,15]
value=[15,5,10,20,10,10]
pop_size=50#種群大小
num_generations=1000#迭代次數(shù)

#考慮選擇變異有一個(gè)選擇率
selection_rate=0.5
#變異率
mutation_rate=0.01

def swap(t1, t2):
     t1,t2=t2, t1
     return

#初始化種群函數(shù)
def init_population():
    population=[]#種群是一個(gè)數(shù)組,其中有一些染色體
    for i in range(pop_size):
        chromosome=[]
        for j in range(num_items):
            chromosome.append(random.randint(0,1))#隨機(jī)初始化染色體
        population.append(chromosome) #pop_size個(gè)染色體形成一個(gè)種群
    return population

#計(jì)算適應(yīng)度
def fitness(chromosome):
    total_weight=0
    total_value=0
    for i in range(num_items):
        if(chromosome[i]==1):
            total_weight+=weight[i]
            total_value+=value[i]
    if total_weight>capacity:
        return 0
    else :
        return total_value

#選擇函數(shù)
def selection(population):
    population_fitness=[]#組成適應(yīng)度數(shù)組
    for chromosome in population:
        population_fitness.append(fitness(chromosome))
    #下方是根據(jù)適應(yīng)度排序的數(shù)組
    sorted_population=[x for _,x in sorted(zip(population_fitness,population),reverse= True)]
    cutoff=int(selection_rate*len(sorted_population))
    return sorted_population[:cutoff]

#交換函數(shù)
def crossover(parent1,parent2):
    crossover_point=random.randint(0,num_items-1)#0-5之間選擇一個(gè)交叉點(diǎn)
    child1=parent1[:crossover_point]+parent2[crossover_point:]
    child2=parent2[:crossover_point]+parent1[crossover_point:]
    return child1,child2

#變異函數(shù)
def mutation(chromosome):
    #模擬變異的過程,任何時(shí)候都可能變異
    for i in range(num_items):
        if random.random()<mutation_rate:
            j=random.randint(0,num_items-1)
            swap(chromosome[i],chromosome[j])
    return chromosome

#遺傳算法的主函數(shù)
def genetic_algorithm():
    population=init_population()
    for i in range(num_generations):
        selected_population=selection(population)
        offspring_population=[]
        for j in range(pop_size-len(selected_population)):
            #體現(xiàn)選擇的隨機(jī)性
            parent1=random.choice(selected_population)
            parent2=random.choice(selected_population)
            child1,child2=crossover(parent1,parent2)
            child1=mutation(child1)
            child2=mutation(child2)
            offspring_population.append(child1)
            offspring_population.append(child2)
        population=selected_population+offspring_population
        best_chromosome=max(population,key=fitness)
        best_fitness=fitness(best_chromosome)
    print("Best Solution: ",best_chromosome)
    print("Best Fitness : ",best_fitness)

# def __init__():

genetic_algorithm()