🚛 ⛹🏼 👄 Elegir el equipo para un juego persa usando genética / evolución en Python 🥌 🌭 👩🏽‍🌾

¿Cómo elegir el mejor equipo en tu juego favorito? Por supuesto, puedes clasificar banalmente todas sus combinaciones posibles (por ejemplo, para el ladrón de World of Warcraft) y encontrar la mejor. Sin magia ni aprendizaje automático. Pero, ¿es posible lograr este resultado no "de frente", sino con la ayuda de algoritmos genéticos, sin probar cada combinación? ¿Es interesante saber cómo los ladrones se reproducen y evolucionan? Vamos.

imagen

Este artículo es una profundización del tema anterior , que ya describe los detalles de la implementación del personaje y el impacto del equipo.

Propósito: mostrar a los interesados cómo crear una población virtual de agentes de juego por su cuenta, unirlos, implementar un algoritmo genético simple (con mutaciones) y visualizar todo esto usando HTML, CSS y Javascript.

Lo que necesita:

1. Python 3 + instale el módulo matplotlib ; IDE (tengo PyCharm);
2. si desea editar una plantilla de informe interactivo, una comprensión básica de HTML, CSS, JavaScript (jQuery).

PASO 1 - establece una meta, trata con OOP

Entonces, el objetivo final de nuestra codificación es hacer posible obtener el mejor atuendo con una simulación de genética / evolución / selección natural. Y tenga la oportunidad de trazar visualmente este camino.

Convertimos nuestro objetivo en tareas específicas:

pensar e implementar el mecanismo genético a nivel individual (los "genes" del ladrón deberían afectar directamente la elección del equipo)
implementar los mecanismos del nacimiento de descendientes, la transferencia de genes a ellos, así como mutaciones menores aleatorias, para garantizar la variabilidad y la posibilidad misma de encontrar el mejor
para darse cuenta de la "competencia" genética, la selección de genes (para unir a sus portadores, de modo que el resultado de la colisión derrote a los genes "malos" y genere los "buenos")
reúne todo en un sistema coherente en el que los ladrones pueden evolucionar en luchadores ideales
para recopilar y visualizar datos para que haya algo que admirar (de lo contrario, ¡es interesante!)
evaluar la utilidad de estas actividades

Aquí OOP nos ayudará, crearemos 4 clases fundamentales:

imagen

PASO 2 - agudizando la clase Rogue para la cría

acordar los términos en la orilla

En este artículo me separaré de los términos "gen" (en el código - gen ) y "genotipo" (en el código - genotipo ). También habrá "mutaciones" (en el código: mutación , mutación ), lo que implica un cambio en uno o más genes de su significado. La reproducción ocurrirá simplemente "incipiendo" al descendiente del progenitor, por lo que no habrá cruces ni otras complicaciones similares. El genotipo del ladrón es una lista de 7 números que son sus genes:

imagen

Entonces, la clase Rogue está creciendo significativamente en comparación con la última vez .

1)El ladrón recibe los genes de una de las formas posibles (se generó el primer día o se heredó del "padre" con o sin una mutación). Los métodos generate_random_genes , mutate_genes , mutate_gene son responsables de esto :

codificar métodos de formación de genes

    #     ():
    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. Los genes (genotipo) determinan qué equipo usa ladrón (inmediatamente al momento del ~~nacimiento del~~ objeto de inicialización). Para hacer esto, el método apply_genes se llama :

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. El equipo determinará el valor final de la "calificación" del ladrón. Para ello, el calculate_rate será llamado método , que calcula la esperanza matemática de los daños:

calcular_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 calificación del ladrón será el factor determinante que conduzca a la reproducción o muerte vergonzosa. Para esto, se introducen los conceptos de "victoria" (método embody_win ) y "derrota" (método embody_defeat ):

embody_win y 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 + ' ...')

Bueno, el constructor de la clase se ha rediseñado en consecuencia para que esta cadena de "genes - equipamiento - calificación" funcione:

Constructor de clase pícaro

    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()

Para resumir esta lógica de clase con una imagen:

imagen

ETAPA 3 - Población, estadísticas y clases de desafío

La clase de población solo se necesita para tres cosas:

crear una población a partir del número especificado de ladrones con genes aleatorios y parámetros biológicos que siempre se mantendrán sin cambios ( wins_to_reproduce - cuántas victorias necesita un ladrón para la reproducción, derrats_to_die - cuántas derrotas harán morir a un individuo);
"Reset" de la población, es decir cuando finaliza el último día de la Etapa actual, todos los ladrones se destruyen y se crean ladrones con los mejores genotipos (consulte el método de recarga );
almacenar algunos datos de población para estadísticas.

población de clase

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 clase Stats realiza dos tareas principales:

recopilación de datos durante la simulación (por ejemplo, indicadores de cada día: el número de ladrones vivos, el número de genotipos únicos, etc.)
( matplotlib, HTML-, ).

Mirando hacia el futuro, muestro cómo se verá este informe:

imagen

el código de plantilla HTML para el informe está disponible en el github .

La clase de estadísticas también se ve mejor en el github (de lo contrario, dañará muchas líneas aquí).

La clase Challenger es responsable de simular colisiones entre ladrones seleccionados al azar. Todos los días, el método se llama perform_battles , que se forma a partir de ladrones vivos que se enfrentan en duelo y los confronta con un método perform_battle , y eventualmente para cada ladrón se produce cualquiera de los métodos embody_win , cualquier método embody_defeat. Por cierto, si resulta que se ha producido un empate (los genotipos y, por lo tanto, las calificaciones de los ladrones son las mismas), entonces divergen sin consecuencias:

retador de clase

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 !  !')

Bueno, ahora pasamos al cuerpo del programa, que une todas las partes mencionadas del código. Primero vienen las constantes que determinan los parámetros clave de la simulación: el número de etapas, días en una etapa, el número inicial de ladrones en una población, etc. Luego vienen las constantes auxiliares para la depuración. Y los desafíos en sí mismos:

código para ejecutar la simulación

# :
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__".')

Al final de la simulación, se genera un archivo con el nombre de tipo "informe 2020-04-25_10-33-54.html" en la carpeta del programa. Más información al respecto en la siguiente parte del artículo.

PASO 4: visualice los datos

Para más explicaciones utilizaré este conjunto de equipos:

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)

Aquí están las posibles combinaciones de 192 conjuntos (3 * 2 * 2 * 2 * 2 * 2 * 2). En consecuencia, habrá 192 posibles genotipos .

La idea principal de la visualización : representar todo el espacio de posibles genotipos como un campo rectangular, donde cada cuadrado representa un genotipo separado. Un algoritmo simple encuentra dos divisores medios del número 192, estos son 16 y 12:

El código para este algoritmo del constructor de la clase 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)

Obtenemos un área de 16x12:

imagen

este código genera una lista de posibles genotipos:

        #    :
        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)

Por lo tanto, los cuadrados en el campo representan los genotipos en este orden:

imagen

esta es una característica importante, porque, por ejemplo, los genotipos que contienen el "gen de la espada fuerte" ( esquina azul ) están en la parte superior del campo, y los que también contienen el "gen de la daga fuerte" ( esquina azul ): ocupa una región aún más alta: por lo

imagen

tanto, el genotipo más fuerte ( 0-0-0-0-0-0-0-0 ) está en la esquina superior izquierda y el más débil ( 2-1-1-1- 1-1-1 ) - en el contrario. Esto nos ayudará a observar la dinámica de la situación, porque sabremos que durante la simulación, el "grupo de genes dominante" debería cambiar a la esquina superior izquierda del campo:

imagen

Ahora ejecute la simulación con los siguientes parámetros:

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

Es decir, 8 ladrones al principio, se crean <div> -contenedores con campos (en lo sucesivo, diapositivas ) para cada día, 5 etapas de 40 días cada una. Como resultado, obtenemos dos juegos de diapositivas de 200 piezas cada una: " prevalencia de genotipos " (colores azul-verde) y " victoria de genotipos " (colores rojo y verde). La saturación de color de los cuadrados depende de los valores.

Abrimos el informe HTML generado y vemos esta imagen para el primer y décimo día:

imagen

Entonces, el primer día, se generaron 8 ladrones, sus cuadrados arrojarán una sombra hasta el final de la simulación. Además, vemos que comenzaron a pelear, lo que significa que aparecen las primeras victorias, lo que lleva a la reproducción. La reproducción con alta probabilidad está asociada con mutaciones, por lo que hay más cuadrados coloreados.

Echa un vistazo en los próximos días. En el día 44, apareció el genotipo " 0-0-0-0-0-0-0-0 " (ver detrás de la flecha azul). En el día 59, ya avanzó en victorias (ver detrás de la flecha roja).

imagen

En el día 137 se puede ver que " 0-0-0-0-0-0-0-0 " fue derrotado por la cantidad de apariciones en la población (ver detrás de la flecha azul). Y en la diapositiva del último día tuvo una sombra dorada, ya que ocupó el primer lugar en términos de número de victorias.

imagen

Como puede ver, de hecho, la selección natural desplaza el "acervo genético" de la población hacia la izquierda y hacia arriba, es decir, hacia un equipo más fuerte. Los genotipos de " abajo a la derecha " son más débiles que los de " arriba a la izquierda ", por lo tanto, desaparecen tan pronto como aparecen (el rojo indica que no hay victorias).Esto se ve más claramente en b sobreen una escala mayor:

imagen

Bueno, el veredicto en el informe es correcto: el genotipo ganador es 0-0-0-0-0-0-0-0 : los

imagen

gráficos obtenidos con matplotlib ayudarán a evaluar más a fondo lo que está sucediendo:

1. el gráfico de “ población viva ” muestra la dinámica cambios en el número de ladrones que viven simultáneamente;
2. el gráfico de " nacido todo " está casi siempre en línea recta, si no comienza a jugar con parámetros demográficos:

imagen

3. el gráfico de " diversidad de genotipos ": generalmente un crecimiento rápido al principio, luego se ralentiza y se acerca gradualmente al máximo;
4. horario " dinámica del sorteo"- muestra cómo el número de sorteos cambia con el tiempo (estas son peleas cuando dos genotipos idénticos chocan en una pelea sin sentido):

imagen

sucede que una población" se estanca "cuando los ladrones con los mismos genotipos permanecen en ella (los gráficos muestran: un fuerte aumento en el número de sorteos, inmutabilidad (en términos de población y el número de genotipos únicos) el

estancamiento de la población significa que el cálculo y el dibujo de diapositivas en vano para reducir los períodos de estancamiento, es necesario reducir el valor MAX_DAYS_AT_STAGE constante, y se verá que la congestión ha disminuido, y en algunos lugares desapareció por completo:

imagen

PASO 5: experimente grandes espacios de genotipo

Ahora intentemos ejecutar la simulación para el conjunto de equipos personalizados evolution_equipment_ discutidos en el último artículo con parámetros ligeramente diferentes. Aquí, el valor POSSIBLE_BIRTH_QUANTITIES = [1, 2] significa que con el acto de reproducción con una probabilidad del 50%, nacerán 1 o 2 descendientes. Esto mejorará la dinámica de lo que está sucediendo:

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

Aquí, el patrón de distribución de los genotipos en las diapositivas será diferente, porque el equipo más significativo para el resultado general ("La espada del maestro") se encuentra ahora en "otros lugares". La visualización de este conjunto de equipos ya se caracteriza por la aparición de una serie de "focos de poder" en diferentes lugares donde la potencia del equipo es mayor que en las "áreas" vecinas.

imagen

Por cierto, este algoritmo determinó inequívocamente el conjunto superior de equipos ( 3-3-0-0-0-0-0-1 ), que coincide con el determinado por el algoritmo combinatorio del artículo anterior :

imagen

Y, finalmente, realicé la prueba para el conjunto extendido , que da 18432 combinaciones:

con tales parámetros

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 general, puede seguir divirtiéndose con esto, pero la tendencia no cambia: durante la simulación, los genotipos comienzan a acumularse rápidamente en estos mismos "centros de poder". Y el genotipo dominante está en uno de los "focos" más llamativos.

PASO 6 - ¿Tiene sentido todo?

Si pasamos ahora al lado práctico de la pregunta, debemos entender si este algoritmo genético puede encontrar la respuesta correcta a costa de menos peleas que una simple búsqueda combinatoria de todos los genotipos. Respuesta: sí, capaz . Prueba debajo del corte:

prueba de la efectividad del algoritmo genético

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% .

.

PD Es posible obtener la respuesta correcta incluso con ROGUES_AT_BEGIN = 2 y POSSIBLE_BIRTH_QUANTITIES = [1] . Esto parece sorprendente, porque la población nunca supera los 2 ladrones. Como uno pierde, el otro gana, el primero muere y el segundo da a luz a un descendiente. Y el padre comienza a competir con este descendiente. El descendiente es más fuerte o más débil. Y de esta manera, la despiadada rueda de selección se mueve entre el padre y su descendiente hasta que llega a un punto mejor (que puede lograr en el tiempo asignado, por lo que no siempre es el mejor).

Resumen

El problema se resuelve utilizando algoritmos genéticos.
«» .
, , ( calculate_rate Rogue, ).
Por supuesto, en este programa aún puede experimentar y experimentar, mejorando la eficiencia. Por ejemplo, en algún momento, comience a "prohibir" obviamente la pérdida de genotipos, sin permitir que sus dueños peleen o aparezcan. Por lo tanto, el embudo de "líderes" se reducirá, donde deben determinar exactamente quién es el "más fuerte" entre ellos.

Publiqué todo el código del proyecto en el github .

Estimada comunidad, me complacerá recibir comentarios sobre este tema.

Elegir el equipo para un juego persa usando genética / evolución en Python