🤲🏻 👨🏻 🧑🏿‍🤝‍🧑🏼 Choisir l'équipement pour un jeu persan utilisant la génétique / évolution en Python 🤚 🎙️ 🛷

Comment choisir le meilleur équipement de votre jeu préféré? Bien sûr, vous pouvez trier banalement toutes ses combinaisons possibles (par exemple, pour le voleur de World of Warcraft) et trouver le meilleur. Sans magie ni apprentissage automatique. Mais est-il possible d'atteindre ce résultat non pas «de front», mais à l'aide d'algorithmes génétiques, sans essayer chaque combinaison? Il est intéressant de savoir comment les voleurs se reproduisent et évoluent? Aller.

Cet article est un approfondissement du sujet précédent , qui décrit déjà les détails de la mise en œuvre du personnage et l'impact de l'équipement.

Objectif: montrer aux intéressés comment créer eux-mêmes une population virtuelle d'agents de jeu, les regrouper, implémenter un algorithme génétique simple (avec des mutations) et visualiser tout cela en utilisant HTML, CSS et Javascript.

Ce dont vous avez besoin:

1. Python 3 + installez le module matplotlib ; IDE (j'ai PyCharm);
2. si vous souhaitez modifier un modèle de rapport interactif, alors une compréhension de base de HTML, CSS, JavaScript (jQuery).

ÉTAPE 1 - fixer un objectif, traiter avec la POO

Ainsi, le but ultime de notre codage est de permettre d'obtenir la meilleure tenue avec une simulation génétique / évolution / sélection naturelle. Et obtenez l'opportunité de tracer visuellement ce chemin.

Nous transformons notre objectif en tâches spécifiques:

réfléchir et mettre en œuvre le mécanisme génétique au niveau individuel (les «gènes» du voleur devraient affecter directement le choix de l'équipement)
mettre en œuvre les mécanismes de la naissance des descendants, le transfert des gènes à eux, ainsi que les mutations mineures aléatoires, pour assurer la variabilité et la possibilité même de trouver le meilleur
pour réaliser la «compétition» génétique, la sélection des gènes (pour rapprocher leurs porteurs, afin que le résultat de la collision renverse les «mauvais» gènes et élève les «bons»)
tout assembler dans un système cohérent dans lequel les voleurs peuvent évoluer en combattants idéaux
pour collecter et visualiser des données pour qu'il y ait quelque chose à admirer (sinon c'est intéressant!)
évaluer l'utilité de ces activités

Ici la POO va nous aider, nous allons créer 4 classes fondamentales:

ÉTAPE 2 - affiner la classe Rogue pour l'élevage

convenir des conditions sur le rivage

Dans cet article, je me séparerai des termes «gène» (dans le code - gène ) et «génotype» (dans le code - génotype ). Il y aura également des «mutations» (dans le code - mutation , mutation ), impliquant un changement dans un ou plusieurs gènes de leur signification. La reproduction se fera simplement en «bourgeonnant» le descendant du parent, il n'y aura donc pas de croisement et d'autres complications similaires. Le génotype du voleur est une liste de 7 nombres , qui sont ses gènes:

Ainsi, la classe Rogue se développe considérablement par rapport à la dernière fois .

1.Le voleur obtient les gènes de l'une des manières possibles (a été généré dès le premier jour ou hérité du «parent» avec ou sans mutation). Les méthodes generate_random_genes , mutate_genes , mutate_gene sont responsables de ceci :

coder les méthodes de formation de gènes

    #     ():
    def generate_random_genes(self):
        dbg = DBG_rogue_generate_random_genes

        self.my_genes[0] = randrange(0, len(RIGHT_HANDS))    # <--   :
        self.my_genes[1] = randrange(0, len(LEFT_HANDS))     # <--   :
        self.my_genes[2] = randrange(0, len(GLOVES))         # <--  :
        self.my_genes[3] = randrange(0, len(HEADS))          # <--  :
        self.my_genes[4] = randrange(0, len(CHESTS))         # <--  :
        self.my_genes[5] = randrange(0, len(PANTS))          # <--  :
        self.my_genes[6] = randrange(0, len(BOOTS))          # <--  :

        if dbg:  #  :
            print('\nf "generate_random_genes":' + '\n\tgenes generated:\n\t', end='')
            print(self.my_genes)


    #      :
    def mutate_genes(self, parent_genes):
        dbg = DBG_rogue_mutate_genes

        #     :
        self.my_genes = parent_genes.copy()

        #    :
        event_mutation = randint(1, 10)

        #     ,    :
        if event_mutation == 10:
            if dbg:  #  :
                print('\nf "mutate_genes"   :' + '\n\t  \n\told genes: ', end='')
                print(parent_genes)
                print('\tnew genes: ', end='')
                print(self.my_genes)
            return 0

        #    :
        else:
            #  ""  =  ,   :
            mutation_volume = randint(0, 30)
            mutation_iters = 1
            if 22 <= mutation_volume <= 28:
                mutation_iters = 2
            elif 29 <= mutation_volume <= 30:
                mutation_iters = 3

            if dbg:  #  :
                print('\nf "mutate_genes" :' + '\n\t : ' + str(mutation_iters))

            #  ,   :
            genes_available = [0, 1, 2, 3, 4, 5, 6]

            #   :
            genes_mutated = []

            current_iter = 0
            while current_iter < mutation_iters:
                if dbg:  #  :
                    print('\tw1')

                #     :
                gene_with_forced_mutation = choice(genes_available)

                #      :
                if gene_with_forced_mutation not in genes_mutated:
                    self.mutate_gene(gene_with_forced_mutation)
                    genes_mutated.append(gene_with_forced_mutation)
                    current_iter += 1
                    if dbg:  #  :
                        print('\tcurrent_iter =', current_iter)
                else:
                    if dbg:  #  :
                        print('\telse, because ' + str(gene_with_forced_mutation) + ' already in genes_mutated')

        if dbg:  #  :
            genes_mutated_str = ''
            if len(genes_mutated) > 1:
                for x in genes_mutated:
                    genes_mutated_str += str(x) + ', '
            else:
                genes_mutated_str = str(genes_mutated[0])
            print('\nf "mutate_genes" :' + '\n\told genes: ', end='')
            print(parent_genes)
            print('\tgenes_mutated: ' + genes_mutated_str)
            print('\tnew genes: ', end='')
            print(self.my_genes)


    #     ,      :
    def mutate_gene(self, gene_id):
        dbg = DBG_rogue_mutate_gene

        current_value = self.my_genes[gene_id]
        new_value = current_value

        if dbg:  #  :
            print('\nf "mutate_gene":' + '\n\tgene_id: ' + str(gene_id) + '\n\told gene value: ' + str(current_value))

        tries = 0
        while new_value == current_value:
            if dbg and tries > 0:  #  :
                print('\tw2, because ' + str(new_value) + ' = ' + str(current_value) )
            new_value = randrange(0, len(LINKS_TO_EQUIP_DICTS[gene_id]))
            self.my_genes[gene_id] = new_value
            tries += 1

        if dbg:  #  :
            print('\tnew gene value: ' + str(new_value) + '\n\ttries: ' + str(tries))

2. Les gènes (génotype) déterminent quel voleur d'usure (immédiatement à l' objet d'initialisation à la ~~naissance~~ ). Pour ce faire, la méthode apply_genes est appelée :

apply_genes

    # ""  ()     :
    def apply_genes(self):
        dbg = DBG_rogue_apply_genes

        pointer = 0
        for item_id in self.my_genes:
            self.wear_item(pointer, item_id, LINKS_TO_EQUIP_DICTS[pointer])
            pointer += 1

        if dbg:  #  :
            print('\nf "apply_genes":' + '\n\t.')
            print(self)

3. L' équipement déterminera la valeur finale de la «cote» du voleur. Pour ce faire, la méthode Calculate_rate sera appelée , qui calcule l'attente mathématique des dommages:

Calculate_rate

    #     :
    def calculate_rate(self):
        dbg = DBG_rogue_calculate_rate

        #   :
        p_hit = self.stat_hit / 100

        #      :
        p_glancing = self.stat_glancing_percent / 100
        not_p_glancing = 1 - self.stat_glancing_percent / 100

        #      :
        p_crit = self.stat_crit / 100
        not_p_crit = 1 - self.stat_crit / 100

        #   :
        expectation_modificator = p_hit * (p_glancing * 0.7 + not_p_glancing * (p_crit * 2 + not_p_crit))

        #      :
        expectation_damage = expectation_modificator * self.stat_attackpower
        expectation_damage = round(expectation_damage, 3)

        if dbg:
            print('\t  =', expectation_modificator)
            print('\t  =', expectation_damage)

        return expectation_damage

4. La cote du voleur sera le facteur déterminant menant à la reproduction ou à la mort honteuse. Pour cela, les concepts de «victoire» (méthode embody_win ) et de «défaite» (méthode embody_defeat ) sont introduits :

embody_win et embody_defeat

    #    :
    def embody_win(self):
        dbg = DBG_rogue_embody_win

        self.my_wins += 1
        stats.genes_add_win(self.my_genes)

        #    :
        if self.my_wins % population.wins_to_reproduce == 0:

            #    :
            total_borns = choice(population.possible_birth_quantities)
            if dbg:
                print('  ' + str(total_borns))

            for x in range(0, total_borns):
                if dbg:
                    print(self.name + '  ...')

                #  -:
                new_rogue = Rogue(self.my_genes, self.my_generation, from_parent=True)
                ROGUES_LIST.append(new_rogue)

            Population.day_of_last_changes = current_day

        #         :
        if self.my_wins > Population.record_max_wins:
            Population.record_max_wins = self.my_wins
            Population.max_winner_name = self.name
            Population.max_winner_genes = self.my_genes


    #    :
    def embody_defeat(self):
        dbg = DBG_rogue_embody_defeat

        self.my_defeats += 1

        #    :
        if self.my_defeats == population.defeats_to_die:
            self.alive = False
            Population.how_many_rogues_alive -= 1
            Population.day_of_last_changes = current_day

            if dbg:
                print(self.name + ' ...')

Eh bien, le constructeur de la classe a été repensé en conséquence pour faire fonctionner cette chaîne «gènes - équipement - évaluation»:

Constructeur de classe voyous

    def __init__(self, genes_list_inherited, parent_generation, from_parent=True, genes_can_mutate=True):

        #    ,    id  :
        # 0 -  , 1 -  , 2 - , 3 - , 4 - , 5 - , 6 - 
        self.equipment_slots = [0] * 7

        #    ,      :
        self.equipment_names = [''] * 7

        #    ( -     ):
        self.basic_stat_agility = 50
        self.basic_stat_power = 40
        self.basic_stat_hit = 80
        self.basic_stat_crit = 20
        self.basic_stat_mastery = 0

        #     :
        self.set_stats_without_equip()

        #  :
        Population.how_many_rogues += 1
        Population.how_many_rogues_alive += 1

        #  :
        self.my_generation = parent_generation + 1
        if self.my_generation > Population.generations:
            Population.generations = self.my_generation

        # "" :
        self.name = '"' + str(Population.how_many_rogues) + '-,   ' + str(parent_generation + 1) + '"'

        #  :
        self.alive = True

        #    :
        self.my_wins = 0
        self.my_defeats = 0

        #   :
        self.my_genes = [0] * 7

        if genes_can_mutate:
            #      ,     :
            if from_parent:
                self.mutate_genes(genes_list_inherited)
            else:
                self.generate_random_genes()
        else:
            self.my_genes = genes_list_inherited

        #     :
        stats.genes_add_presence(self.my_genes, self.my_generation)

        #     :
        self.apply_genes()

Pour résumer cette logique de classe avec une image:

ÉTAPE 3 - Population, statistiques et classes de défi

La classe Population n'est nécessaire que pour trois choses:

créer une population à partir du nombre spécifié de voleurs avec des gènes aléatoires et des paramètres biologiques qui seront toujours inchangés ( wins_to_reproduce - combien de victoires un voleur doit gagner pour la reproduction, defeats_to_die - combien de défaites feront mourir un individu);
"Reset" de la population, c'est-à-dire à la fin du dernier jour de l'étape actuelle, tous les voleurs sont détruits et les voleurs avec les meilleurs génotypes sont créés (voir la méthode de rechargement );
stocker certaines données démographiques pour les statistiques.

population de classe

class Population():
    """     ."""

    how_many_rogues = 0 # <--   
    how_many_rogues_alive = 0 # <--   
    how_many_battles = 0 # <--  
    how_many_ties = 0 # <--  
    generations = 0 # <--  
    day_of_last_changes = 0  # <--       
    max_days_without_changes = 0  # <--    

    #        ,      :
    record_max_wins = 0
    max_winner_name = 'none'
    max_winner_genes = 'none'


    #       :
    def __init__(self, total, possible_birth_quantities, wins_to_reproduce, defeats_to_die):

        #   :
        self.initial_size = total

        #   ,        :
        self.wins_to_reproduce = wins_to_reproduce
        self.defeats_to_die = defeats_to_die
        self.possible_birth_quantities = possible_birth_quantities

        while total > 0:

            #   ,  " "    ,     :
            new_rogue = Rogue('', 0, from_parent=False)

            #   :
            ROGUES_LIST.append(new_rogue)

            total -= 1


    #     :
    def __str__(self):
        text = ':\n'
        text += ': ' + str(Population.generations) + '\n'
        text += ' : ' + str(Population.how_many_rogues) + '\n'
        text += ' : ' + str(Population.how_many_rogues_alive) + '\n'
        text += ' : ' + str(Population.record_max_wins) + '\n'
        text += ' : ' + str(Population.max_winner_name) + '\n'
        text += ' : ' + str(Population.max_winner_genes) + '\n'
        return text


    #  ,    how_many_to_save     :
    def reload(self, how_many_to_save):

        #  - :
        Population.how_many_rogues_alive = 0

        # ""   :
        for x in ROGUES_LIST:
            x.alive = False

        #        :
        list_genotypes_top = stats.get_ordered_list_from_dict(LIST_FOR_DICTS_GENOTYPES[current_stage], inner_index=2)

        #      :
        for x in range(0, how_many_to_save):

            #      :
            genotype_in_str = list_genotypes_top[x][0]
            genotype_in_list = []
            for char in genotype_in_str:
                if char != '-':
                    genotype_in_list.append( int(char) )

            #   ,      ,     :
            new_rogue = Rogue(genotype_in_list, 0, from_parent=True, genes_can_mutate=False)

            #   :
            ROGUES_LIST.append(new_rogue)

La classe Stats effectue deux tâches principales:

collecte de données pendant la simulation (par exemple, les indicateurs de chaque jour: le nombre de voleurs vivants, le nombre de génotypes uniques, etc.)
( matplotlib, HTML-, ).

Pour l'avenir, je montre à quoi ressemblera ce rapport:

Le code de modèle HTML pour le rapport est disponible sur le github .

La classe Stats est également mieux vue sur le github (sinon cela blessera beaucoup de lignes ici).

La classe Challenger est chargée de simuler les collisions entre des voleurs sélectionnés au hasard. Chaque jour, la méthode est appelée perform_battles , qui se forme à partir d'une paire de duels de voleurs vivants et les confronte à une méthode perform_battle , et finalement pour chaque voleur est causée soit la méthode embody_win , toute méthode embody_defeat. Soit dit en passant, s'il s'avère qu'un tirage au sort a eu lieu (les génotypes, et donc les notes des voleurs sont les mêmes), alors ils divergent sans conséquences:

challenger de classe

class Challenger():
    """      ."""

    #   :
    def perform_battles(self):
        dbg = DBG_challenger_perform_battles

        #    :
        rogues_alive = []
        for x in ROGUES_LIST:
            if x.alive:
                rogues_alive.append(x)

        #  :
        shuffle(rogues_alive)

        #       :
        pairs_total = int(len(rogues_alive) // 2)

        if dbg:
            print('pairs_total =', pairs_total)

        #       :
        counter = 0
        pointer = 0
        while counter < pairs_total:
            a_1 = rogues_alive[pointer]
            a_2 = rogues_alive[pointer + 1]
            self.perform_battle(a_1, a_2)
            counter += 1
            pointer += 2


    #     :
    def perform_battle(self, rogue_1, rogue_2):
        dbg = DBG_challenger_perform_battle

        if dbg:
            print('\n  :', rogue_1.name, '', rogue_2.name)

        #     (        ):
        rating_1 = rogue_1.calculate_rate()
        rating_2 = rogue_2.calculate_rate()

        #  :
        Population.how_many_battles += 1

        if dbg:
            print('\t :', rating_1, '', rating_2, '.')

        #      :
        if rating_1 > rating_2:
            rogue_1.embody_win()
            rogue_2.embody_defeat()
        elif rating_1 < rating_2:
            rogue_1.embody_defeat()
            rogue_2.embody_win()
        else:
            Population.how_many_ties += 1
            if dbg:
                print('\t !  !')

Eh bien, nous passons maintenant au corps du programme, qui relie toutes les parties mentionnées du code. Viennent d'abord les constantes qui déterminent les paramètres clés de la simulation: le nombre d'étapes, les jours dans une étape, le nombre initial de voleurs dans une population, etc. Viennent ensuite les constantes auxiliaires pour le débogage. Et les défis eux-mêmes:

code pour exécuter la simulation

# :
MAX_STAGES = 8 # <--      
MAX_DAYS_AT_STAGE = 20 # <--        
SLIDING_FREQUENCY = 10 # <--     HTML-    (1 =   , 10 =   10 )
ROGUES_AT_BEGIN = 10 # <--    (  )
WINS_TO_REPRODUCE = 2 # <--     ,  
DEFEATS_TO_DIE = 2 # <--      
POSSIBLE_BIRTH_QUANTITIES = [1] # <--   ,       , :
# [1, 2] ,   50%-    1,  1 
# [1, 1, 2] ,   66%-   1 

HTML_GSQUARE_SIDE = 10 # <--   ,     
HTML_GSQUARE_MARGIN = 3 # <--   ,     

#     :
LINKS_TO_EQUIP_DICTS = [RIGHT_HANDS, LEFT_HANDS, GLOVES, HEADS, CHESTS, PANTS, BOOTS]

#         (    ):
LIST_FOR_DICTS_GENOTYPES = [{}] * MAX_STAGES

#        :
DICT_UNIQUE_GENOTYPES = {}

#      :
DICT_DAYS = {}

# ,       -  :
ROGUES_LIST = list()

#       (     )
current_stage = 0

#     "" (    /):
DBG_rogue_mutate_genes = False
DBG_rogue_generate_random_genes = False
DBG_rogue_apply_genes = False
DBG_rogue_calculate_rate = False
DBG_rogue_mutate_gene = False
DBG_rogue_embody_win = False
DBG_rogue_embody_defeat = False
DBG_rogue_wear_item = False
DBG_challenger_perform_battles = False
DBG_challenger_perform_battle = False
DBG_days_report = False  # <--     



# :
if __name__ == '__main__':

    #  :
    time_begin = time()

    #        :
    max_days_for_current_stage = 0
    current_day = 1
    while current_stage < MAX_STAGES:

        #    :
        if current_stage == 0:

            #   :
            stats = Stats()

            #          ,      :
            population = Population(ROGUES_AT_BEGIN, POSSIBLE_BIRTH_QUANTITIES, wins_to_reproduce=WINS_TO_REPRODUCE, defeats_to_die=DEFEATS_TO_DIE)

            #     :
            challenger = Challenger()

            # "" :
            print(population)

        #        :
        max_days_for_current_stage += MAX_DAYS_AT_STAGE

        # /      (1  = 1    (*) )
        # * -     -    , -           
        while current_day <= max_days_for_current_stage:
            print('st ' + str(current_stage) + ', day ' + str(current_day))
            if DBG_days_report:
                print('\n\n/DAY', current_day)

            #   :
            challenger.perform_battles()

            if DBG_days_report:
                print('\n', current_day, '.')
                print(population)

            #    :
            stats.add_new_day(current_day)

            #        :
            if current_day - Population.day_of_last_changes > Population.max_days_without_changes:
                Population.max_days_without_changes = current_day - Population.day_of_last_changes

            #    SLIDING_FREQUENCY  (     )     :
            if current_day % SLIDING_FREQUENCY == 0 or current_day == 1 or current_day == MAX_DAYS_AT_STAGE * MAX_STAGES:
                stats.draw_genes_distribution(current_day)

            #    SLIDING_FREQUENCY  (     )     :
            if current_day % SLIDING_FREQUENCY == 0 or current_day == 1 or current_day == MAX_DAYS_AT_STAGE * MAX_STAGES:
                stats.draw_genes_wins(current_day)

            current_day += 1

        #      ,  ,     -  :
        if current_stage < MAX_STAGES - 1:
            population.reload(ROGUES_AT_BEGIN)

        current_stage += 1


    #      ,      LIST_FOR_DICTS_GENOTYPES:
    current_stage -= 1

    #   :
    print('\n:')
    print(DICT_DAYS)

    #       :
    stats.draw_and_put_line_chart_to_file(DICT_DAYS, 1, ' ', '', '', 'charts/chart_population_demography.png')

    #       -  :
    stats.draw_and_put_line_chart_to_file(DICT_DAYS, 0, ' ', '', '', 'charts/chart_population_total.png')

    #      :
    stats.draw_and_put_line_chart_to_file(DICT_DAYS, 2, ' ', '', ' ', 'charts/chart_genotypes_variety.png')

    #      (=   ):
    stats.draw_and_put_line_chart_to_file(DICT_DAYS, 3, ' ', '', '', 'charts/chart_genotypes_ties.png')

    #   HTML   :
    stats.create_index_html()

    #   :
    time_session = time() - time_begin
    duration_info = '  : ' + str(round(time_session, 2)) + ' .'
    print('\n' + duration_info)

else:
    print('__name__ is not "__main__".')

À la fin de la simulation, un fichier avec un nom de type «report 2020-04-25_10-33-54.html» est généré dans le dossier du programme. Plus d'informations à ce sujet dans la prochaine partie de l'article.

ÉTAPE 4 - visualiser les données

Pour plus d'explications, j'utiliserai cet ensemble d'équipements:

evolution_equipment_obvious_strong.py

#       .
#    ,     :
# 0 - , 1 - , 2 - , 3 - , 4 - , 5 - , 6 - 

EQUIPMENT_COLLECTION = 'obvious_strong'

RIGHT_HANDS = dict()
RIGHT_HANDS[1] = (' ', 5000, 0, 0, 0, 0, 0)
RIGHT_HANDS[2] = (' ', 800, 0, 0, 0, 0, 0)
RIGHT_HANDS[3] = (' ', 20, 0, 0, 0, 0, 0)

LEFT_HANDS = dict()
LEFT_HANDS[1] = (' ', 4000, 0, 0, 0, 0, 0)
LEFT_HANDS[2] = (' ', 10, 0, 0, 0, 0, 0)

GLOVES = dict()
GLOVES[1] = (' ', 300, 0, 0, 0, 0, 0)
GLOVES[2] = (' ', 1, 0, 0, 0, 0, 0)

HEADS = dict()
HEADS[1] = (' ', 300, 0, 0, 0, 0, 0)
HEADS[2] = (' ', 1, 0, 0, 0, 0, 0)

CHESTS = dict()
CHESTS[1] = (' ', 300, 0, 0, 0, 0, 0)
CHESTS[2] = (' ', 1, 0, 0, 0, 0, 0)

PANTS = dict()
PANTS[1] = (' ', 300, 0, 0, 0, 0, 0)
PANTS[2] = (' ', 1, 0, 0, 0, 0, 0)

BOOTS = dict()
BOOTS[1] = (' ', 300, 0, 0, 0, 0, 0)
BOOTS[2] = (' ', 1, 0, 0, 0, 0, 0)

Voici les combinaisons possibles de 192 ensembles (3 * 2 * 2 * 2 * 2 * 2 * 2). En conséquence, il y aura 192 génotypes possibles .

L'idée principale de la visualisation : représenter tout l'espace des génotypes possibles comme un champ rectangulaire, où chaque carré représente un génotype distinct. Un algorithme simple trouve deux diviseurs moyens du nombre 192, ce sont 16 et 12:

le code de cet algorithme du constructeur de la classe Stats

        #      - :
        list_divisors = list()
        current_number = int(self.genotypes_total // 2)
        while current_number >= 2:
            if self.genotypes_total % current_number == 0:
                list_divisors.append(current_number)
            current_number -= 1
        print('list_divisors:', list_divisors)

        #        :
        somewhere_in_the_middle = len(list_divisors) // 2

        #     :
        side_1 = list_divisors[somewhere_in_the_middle]
        side_2 = self.genotypes_total / side_1

        # ,   ,     ""  :
        self.side_x = int(side_1 if side_1 >= side_2 else side_2)
        self.side_y = int(self.genotypes_total / self.side_x)
        print('side_x =', self.side_x, 'side_y =', self.side_y)

On obtient une zone 16x12:

Une liste de génotypes possibles est générée par ce code:

        #    :
        self.list_of_possible_genotypes = list()

        #      :
        for g1 in RIGHT_HANDS:
            #      :
            for g2 in LEFT_HANDS:
                #   :
                for g3 in GLOVES:
                    #   :
                    for g4 in HEADS:
                        #   :
                        for g5 in CHESTS:
                            #   :
                            for g6 in PANTS:
                                #   :
                                for g7 in BOOTS:
                                    current_genotype = str(g1-1)+'-'+str(g2-1)+'-'+str(g3-1)+'-'+str(g4-1)+'-'+str(g5-1)+'-'+str(g6-1)+'-'+str(g7-1)
                                    self.list_of_possible_genotypes.append(current_genotype)

Par conséquent, les carrés sur le terrain représentent les génotypes dans cet ordre:

c'est une caractéristique importante, car, par exemple, les génotypes qui contiennent le «gène de l'épée forte» ( coin bleu ) sont dans la partie supérieure du champ, et ceux qui contiennent également le «gène de la dague forte» ( coin bleu ) - occupent une région encore plus élevée:

Ainsi, le génotype le plus fort ( 0-0-0-0-0-0-0-0-0 ) est dans le coin supérieur gauche, et le plus faible ( 2-1-1-1- 1-1-1 ) - à l'opposé. Cela nous aidera à observer la dynamique de la situation, car nous saurons que pendant la simulation, le «pool génétique dominant» devrait se déplacer vers le coin supérieur gauche du champ:

Maintenant, exécutez la simulation avec les paramètres suivants:

MAX_STAGES = 5
MAX_DAYS_AT_STAGE = 40
SLIDING_FREQUENCY = 1
ROGUES_AT_BEGIN = 8
WINS_TO_REPRODUCE = 2
DEFEATS_TO_DIE = 2
POSSIBLE_BIRTH_QUANTITIES = [1]

HTML_GSQUARE_SIDE = 16
HTML_GSQUARE_MARGIN = 3

Autrement dit, 8 voleurs au début, des conteneurs <div> avec des champs (appelés ci-après des diapositives ) sont créés pour chaque jour, 5 étapes de 40 jours chacune. En conséquence, nous obtenons deux séries de diapositives de 200 pièces chacune: " prévalence des génotypes " (couleurs bleu-vert) et " victoire des génotypes " (couleurs rouge et verte). La saturation des couleurs des carrés dépend des valeurs.

Nous ouvrons le rapport HTML généré et voyons cette image pour les 1er et 10e jours:

Ainsi, le premier jour, 8 voleurs ont été générés, leurs carrés projetteront une ombre jusqu'à la fin de la simulation. De plus, nous voyons qu'ils ont commencé à se battre, ce qui signifie que les premières victoires apparaissent, conduisant à la reproduction. Une reproduction à forte probabilité est associée à des mutations, il y a donc plus de carrés colorés.

Jetez un œil dans les jours suivants. Le 44ème jour, le génotype " 0-0-0-0-0-0-0-0-0 " est apparu (voir derrière la flèche bleue). Le 59e jour, il avait déjà pris les devants (voir derrière la flèche rouge).

Au 137ème jour, on peut voir que " 0-0-0-0-0-0-0-0-0 " a été battu en tête par le nombre d'apparitions dans la population (voir derrière la flèche bleue). Et sur la diapositive du dernier jour, il avait une ombre dorée, puisqu'il détenait la première place en termes de nombre de victoires.

Comme vous pouvez le voir, en effet, la sélection naturelle déplace le «pool génétique» de la population vers la gauche et vers le haut, c'est-à-dire vers un équipement plus solide. Les génotypes «en bas à droite » sont plus faibles que ceux «en haut à gauche », ils disparaissent donc dès leur apparition (le rouge indique aucune victoire).Cela se voit plus clairement sur b à proposà plus grande échelle:

Eh bien, le verdict dans le rapport est correct: le génotype gagnant est 0-0-0-0-0-0-0-0-0 : Les

graphiques obtenus avec matplotlib aideront à mieux évaluer ce qui se passe:

1. le graphique « population en direct » montre la dynamique changements dans le nombre de voleurs vivant simultanément;
2. le graphique de " born all " est principalement proche d'une ligne droite, si vous ne commencez pas à jouer avec les paramètres démographiques:

3. le graphique de " diversité des génotypes " - généralement une croissance rapide au début, puis ralentit, s'approchant progressivement du maximum;
4. calendrier " dessiner la dynamique"- montre comment le nombre de tirages change au fil du temps (ce sont des combats lorsque deux génotypes identiques entrent en collision dans un combat sans signification):

il arrive qu'une population" stagne "lorsque des voleurs avec les mêmes génotypes y restent (les graphiques montrent: une forte augmentation du nombre de dessine, immuabilité.en termes de population et de nombre de génotypes uniques) la

stagnation de la population signifie que le calcul et le dessin glissent en vain pour réduire les périodes de stagnation, il faut réduire la valeur MAX_DAYS_AT_STAGE constante, et on verra que la congestion a diminué, et dans certains endroits complètement disparu:

ÉTAPE 5 - découvrez de grands espaces de génotypes

Essayons maintenant d'exécuter la simulation de l' ensemble d'équipements evolution_equipment_custom discuté dans le dernier article avec des paramètres légèrement différents. Ici, la valeur POSSIBLE_BIRTH_QUANTITIES = [1, 2] signifie qu'avec l'acte de reproduction avec une probabilité de 50%, 1 ou 2 descendants apparaîtront . Cela améliorera la dynamique de ce qui se passe:

MAX_STAGES = 20
MAX_DAYS_AT_STAGE = 50
SLIDING_FREQUENCY = 10
ROGUES_AT_BEGIN = 8 
WINS_TO_REPRODUCE = 2
DEFEATS_TO_DIE = 2
POSSIBLE_BIRTH_QUANTITIES = [1, 2]

HTML_GSQUARE_SIDE = 10
HTML_GSQUARE_MARGIN = 3

Ici, le schéma de distribution des génotypes sur les diapositives sera différent, car l'équipement le plus important pour le résultat global («l'épée du maître») est maintenant dans «d'autres endroits». La visualisation de cet ensemble d'équipements se caractérise déjà par l'apparition d'un certain nombre de «foyers de puissance» à différents endroits où la puissance des équipements est plus élevée que dans les «zones» voisines.

Soit dit en passant, cet algorithme a indubitablement déterminé l'ensemble supérieur d'équipement ( 3-3-0-0-0-0-0-1 ), qui correspond à celui déterminé par l'algorithme combinatoire de l' article précédent :

Et, enfin, j'ai exécuté le test pour l' ensemble étendu , qui donne 18432 combinaisons:

avec de tels paramètres

MAX_STAGES = 30
MAX_DAYS_AT_STAGE = 50
SLIDING_FREQUENCY = 100
ROGUES_AT_BEGIN = 20
WINS_TO_REPRODUCE = 2
DEFEATS_TO_DIE = 2
POSSIBLE_BIRTH_QUANTITIES = [1, 2]

HTML_GSQUARE_SIDE = 4
HTML_GSQUARE_MARGIN = 1

En général, vous pouvez continuer à jouer avec cela, mais la tendance reste inchangée: lors de la simulation, les génotypes commencent assez rapidement à s'accumuler dans ces mêmes «centres de pouvoir». Et le génotype dominant se trouve dans l'un des «foyers» les plus frappants.

ÉTAPE 6 - Est-ce que tout cela a du sens?

Si nous passons maintenant au côté pratique de la question, nous devons comprendre si cet algorithme génétique est capable de trouver la bonne réponse au prix de moins de combats qu'une simple recherche combinatoire de tous les génotypes. Réponse: oui, capable . Preuve sous la coupe:

preuve de l'efficacité de l'algorithme génétique

1728 .

, .. 1728 .

, 1728 . «» — 2 ( ). , , 1728 / 2 = 864. .

:

MAX_STAGES = 8
MAX_DAYS_AT_STAGE = 20
SLIDING_FREQUENCY = 10
ROGUES_AT_BEGIN = 10
WINS_TO_REPRODUCE = 2
DEFEATS_TO_DIE = 2
POSSIBLE_BIRTH_QUANTITIES = [1]

HTML_GSQUARE_SIDE = 10
HTML_GSQUARE_MARGIN = 3

, 3-3-0-0-0-0-1:

, 3-3-0-0-0-0-1 547 . 87 (), 16% .

.

PS Il est possible d'obtenir la bonne réponse même avec ROGUES_AT_BEGIN = 2 et POSSIBLE_BIRTH_QUANTITIES = [1] . Cela semble surprenant, car la population ne dépasse jamais 2 voleurs. Parce que l'un perd, l'autre gagne, le premier meurt et le second donne naissance à un descendant. Et le parent commence à rivaliser avec ce descendant. Le descendant est soit plus fort soit plus faible. Et donc la roue de sélection impitoyable se déplace entre le parent et son descendant jusqu'à ce qu'il arrive à un meilleur point (qu'il peut atteindre dans le temps imparti, donc ce n'est pas toujours le meilleur).

Sommaire

Le problème est résolu en utilisant des algorithmes génétiques.
«» .
, , ( calculate_rate Rogue, ).
Bien sûr, sur ce programme, vous pouvez toujours expérimenter et expérimenter, améliorant ainsi l'efficacité. Par exemple, à un moment donné, commencez à «interdire» évidemment la perte de génotypes, ne permettant pas à leurs propriétaires de se battre ou même d'apparaître. Ainsi, l'entonnoir des «dirigeants» se rétrécira, où ils devront déterminer exactement qui est «le plus fort» entre eux.

J'ai posté tout le code du projet sur le github .

Chère communauté, je serai heureux de recevoir des commentaires sur ce sujet.

Choisir l'équipement pour un jeu persan utilisant la génétique / évolution en Python