Я создал генетический алгоритм, чтобы решить проблему просмотра шоу, в каком порядке максимизировать прибыль, используя код, вдохновленный Kie Codes, следуя коду в этом видео https://www.youtube.com/watch?v=nhT56blfRpE
К сожалению, я не могу заставить часть поколений работать, и это приводит к тому, что в результате получается 0 поколений, хотя он создал решение, которое каждый раз отличается в прогоне. Переменные, которые у меня есть, — это имя, физическая форма и вес, которые переводятся в название шоу, его рейтинг и количество серий. Что касается генерации, то часть кода не будет работать, она также не будет учитывать время, необходимое программе для создания оптимального решения.
from random import choices, randint, randrange, random #allows for a random creations to be made
from typing import List, Callable, Tuple #allows to use list functions and callable
from collections import namedtuple #allows the use for named tuple
import time #allows for time to be used
from functools import partial #allows for partial to be used
Genome=List[int]
Population=List[Genome]
FitnessFunc=Callable[[Genome],int] #puts the fitness with the genome
PopulateFunc=Callable[[], Population]#gives out new solutions
SelectionFunc=Callable[[Population, FitnessFunc], Tuple[Genome,Genome]] #takes the population and fitness to make select for a new solution
CrossoverFunc=Callable[[Genome, Genome], Tuple[Genome,Genome]]#takes two genomes and produces two genomes
MutationFunc=Callable[[Genome], Genome]#takes a genome and sometimes produces a new genome
PrinterFunc=Callable[[Population, int, FitnessFunc], None]
#puts the functions into perameters
Thing=namedtuple('Thing',['name','value','weight'])#gives a structure for the list below
things=[
Thing('Seishun Buta Yarou wa Bunny Girl Senpai no Yume wo Minai (TV)',8.38,13),
Thing('Bakemonogatari',8.36,15),
Thing('Kodomo no Jikan (TV)',6.82,12),
Thing('Tsuki ga Kirei',8.18,12),
Thing('Tokyo Ravens',7.53,24),
Thing('Kono Subarashii Sekai ni Shukufuku wo!',8.15,10),
Thing('Shingeki no Kyojin S4',9.2,12),
Thing('Dr Stone S2',8.33,11),
Thing('The Promised Neverland',8.11,11),
Thing('Re:Zero',8.7,12),
Thing('Toradora!',8.24,25),
Thing('Sousei no Onmyouji',7.33,50),
Thing('Rurouni Kenshin: Meiji Kenkaku Romantan',8.31,94),
Thing('Fullmetal Alchemist: Brotherhood',9.2,64),
Thing('Steins;Gate',9.11,24),
Thing('Boku no Pico',4.31,3)
]
def generate_genome(length: int) -> Genome:
return choices([0,1], k=length)
#creates a random genome
##genome
def generate_population(size: int, genome_length: int) -> Population:
return [generate_genome(genome_length)for _ in range(size)]
#generates a list of genomes
##population
def fitness(genome: Genome, things: things, weight_limit: int) -> int:
if len(genome)!=len(things):#checks if the two are the same length
raise ValueError("genome and things must be of the same length")
weight=0
value=0
for i, thing in enumerate (things):
if genome[i]==1:
weight+=thing.weight
value+=thing.value #adds the weight values and fitness values
if weight>weight_limit: #checks if the genome is under the weight limit
return 0
return value
#fitness function
def selection_pair(population: Population, fitness_func: FitnessFunc) -> Population:
return choices(
population=population,
weights=[fitness_func(genome) for genome in population],
k=2 #draw twice (two parents)
)
#selection function
def single_point_crossover(a: Genome,b: Genome) -> Tuple[Genome,Genome]:
if len(a)!=len(b):
raise ValueError("Genomes a and b must be of same length")
#checks the size of the genomes that was selected
#the genomes have to be the same in length or it will not work
length=len(a)
if length<2:#checks the length as they would have to be at least 2 or else you are unable to cut them in half
return a,b
p=randint(1, length-1)#randomly takes parts of the two genomes
return a[0:p]+b[p:],b[0:p]+a[p:]#and then creates them
#crossover function
def mutation(genome: Genome, num: int=1, probability: float=0.5) -> Genome:
for _ in range(num):
index=randrange(len(genome))#if the number made is higher than the probability it is left alone
genome[index]=genome[index] if random() > probability else abs(genome[index]-1)#makes the absolute value so that it is either 1 or 0
#people hatee this one but why ^^
return genome
#mutation function
def run_evolution(
populate_func: PopulateFunc,
fitness_func: FitnessFunc,#for these two it populates with variables
fitness_limit: int,#if the fitness limit is reached then the program is done
selection_func: SelectionFunc=selection_pair,
crossover_func: CrossoverFunc=single_point_crossover,
mutation_func: MutationFunc=mutation,# initialises the above three
generation_limit: int=100 #limits on how much is made
) -> Tuple[Population, int]:
population=populate_func()#populates with random genomes
for generations in range(generation_limit):
population=sorted(
population,
key=lambda genome: fitness_func(genome),
reverse=True
#sorts the fitness of the genomes so that the higher number is at the start
)
if fitness_func(population[0])>=fitness_limit:
break
#if the fitness limit is reached then the program ends (breaks)
next_generation=population[0:2]#gets the top two genomes for the next generation
for j in range(int(len(population)/2)-1):
parents=selection_func(population, fitness_func) #gets the top two to be made as parents
offspring_a, offspring_b=crossover_func(parents[0], parents[1]) #puts the genomes into seprate variables
offspring_a=mutation_func(offspring_a)
offspring_b=mutation_func(offspring_b)#creates a mutation for both genomes randomly
next_generation+=[offspring_a, offspring_b]
#creates the next genomes and puts them into population
population=next_generation
population=sorted(
population,
key=lambda genome: fitness_func(genome),
reverse=True
#sorts the fitness of the genomes so that the higher number is at the start
)
return population, generations
#evolutionary main loop
def genome_to_things(genome: Genome, things: things) -> things:
result=[]
for i, thing in enumerate(things):
if genome[i]==1:
result+=[thing.name]
return result
#collects the best solutions so that it may be printied out for later
start=time.time()
population, generations=run_evolution(
populate_func=partial(
generate_population, size=10, genome_length=len(things)
),
fitness_func=partial(
fitness, things=things, weight_limit=94
),
fitness_limit=10,
generation_limit=100
)
end=time.time()
#runs the program
print(f"number of generations: {generations}")
print(f"time: {end-start}s")
print(f"best solution: {genome_to_things(population[0], things)}")
#prints results
