Alberi Creator. Mantener viva -- python campo con performance campo con game campo con genetic-algorithm camp codereview Relacionados El problema

Alberi creator. Keepalive


5
vote

problema

Español

Esta publicación es un seguimiento de seguimiento a Este post y su seguimiento . < / p>

En esos dos puestos, logramos acelerar la solución de un rompecabezas Alberi, y para crear un rompecabezas de una sola región.

El código completo en lo sucesivo se puede usar para crear rompecabezas multi-árbol por región.

Uso de DFS Tuve poca oportunidad de encontrar un rompecabezas válido, así que tuve que recurrir a un algoritmo genético más exótico.

La primera clase es la implementación general del algoritmo genético (bueno, la más simple de las implementaciones):

  """Genetic algorithm simplicistic and generic implementation. """  import random  class GeneticAlgorithm(object):     """Genetic algorithm iteration cycle.      The aim is to find an individual with the lowest fitness value     by evolving a population of such individuals.      Each individual is tested against a target value to evaluate its fitness      For each evolution loop part of the best are kept for the next cycle     (retain parameter for evolve method), part of the individuals are kept     indipendently from their fitness (random_select parameter), then these     individuals are mutated according to a mutation rate (mutate paramter),     the rest of the new population is made up crossing randomly picked     individuals.     """     def __init__(self, individual, fitness, mutate, crossover):         """Initializes the evolution functions from the problem factory.          Required argument:         individual -- function to generate a new individual. The function can             take a fixed number of parameters to initialize the individual.             This parameters are to be passed to the population method. The             return argument should be a mutable (see mutate).         fitness -- function to score an individual. An individual and the             target will be passed to the function. The target is set by the             evolve method. The function must return a numeric type.         mutate -- function to mutate in-place an individual. The function will             take a mutable as argument         crossover -- function to create a new individual using the genetic             code of the two individuals passed as argument. The return argument             should be a mutable.         """         self.individual = individual         self.fitness = fitness         self.mutate_individual = mutate         self.crossover_individuals = crossover      def population(self, count, *args):         """Create a number of individuals (i.e. a population).          Required argument:         count -- number of individuals to be created         *args -- parameters to be passed to the individual generation function         """         return [self.individual(*args) for _ in range(count)]      def grade(self, pop, target):         """Find average fitness for a population.         """         summed = sum(self.fitness(x, target) for x in pop)         return summed / (len(pop) * 1.0)      def evolve(self, pop, target, retain=0.2, random_select=0.1, mutate=0.2):         """Genetic algorithm evolution loop.          Required argument:         pop --- count of the elements of the population         target -- target value to obtain          Optional arguments:         retain -- Number of elements whith the lowest fitness to keep at             each iteration         random_select -- Rate of selection of elements whithout fitness             filtering         mutate -- Rate of mutation of elements         """         graded = [(self.fitness(x, target), x) for x in pop]         graded = [x[1] for x in sorted(graded)]         retain_length = int(len(graded) * retain)         parents = graded[:retain_length]         # randomly add other individuals to         # promote genetic diversity         for individual in graded[retain_length:]:             if random_select > random.random():                 parents.append(individual)         # mutate some individuals         for individual in parents:             if mutate > random.random():                 self.mutate_individual(individual)         # crossover parents to create children         parents_length = len(parents)         desired_length = len(pop) - parents_length         children = []         while len(children) < desired_length:             male = random.randint(0, parents_length-1)             female = random.randint(0, parents_length-1)             if male != female:                 male = parents[male]                 female = parents[female]                 child = self.crossover_individuals(male, female)                 children.append(child)         parents.extend(children)         return parents   

La clase __init__ toma como argumento Las funciones necesarias para generar un individuo, evalúan su aptitud con un objetivo, mutan (en su lugar) un individuo y cruce dos individuos para hacer un tercero.

Los métodos expuestos son population , que crea que las personas iniciales se evolucionarán, 99887776655443333 , se utiliza para evaluar la aptitud global de una población y 9988777665544334 < / Código>, el núcleo del algoritmo, que crece la población.

Las funciones que di a la clase GeneticAlgorithm son creadas por la siguiente clase:

  """Fill the empty cells of an Alberi puzzle using a genetic algorithm """ from AlberiCover import Alberi from GeneticAlgorithm import GeneticAlgorithm import random  class AlberiGeneticFactory(object):     """Creates the functions needed for the evolution of the GA     """     def __init__(self, m, n, per_row=2, per_column=2, per_region=2):         """Initializes the factory parameters.          Required argument:         n -- Number of rows         m -- Number of columns          Optional arguments:         per_row -- Number of trees per row. (Default: 2.)         per_column -- Number of trees per column. (Default: 2.)         per_region -- Number of trees per region. (Default: 2.)          """          self.m = m         self.n = n         self.size = size = m * n         self.per_row = per_row         self.per_column = per_column         self.per_region = per_region          neighbour = []         for idx in range(size):             row, col = divmod(idx, m)             neighbour.append(                 [endr * n + col for endr in range(row - 1, row + 2)                     if 0 <= endr < m and endr != row] +                 [row * n + endc for endc in range(col - 1, col + 2)                     if 0 <= endc < n and endc != col]             )         self.neighbour = neighbour      def individual_function(self):         """Returns the function to create an Alberi puzzle.         """         REGIONLESS = Alberi.REGIONLESS         ORL = ord(REGIONLESS)         neighbour = self.neighbour          def individual(puzzle):             """ Take a puzzle and makes a single mutation to it.              The mutation is made on a whitespace, labeling it with the letter             of a neighbouring field.              Required argument:             puzzle -- The puzzle to mutate, in the form of a string of n*m                 letters indicating the regions. The whitespace ' ' can be                 used as a placeholder for a cell with no region assigned.             """             neighbour_field = [                 set(puzzle[idx] for idx in lst if puzzle[idx] != REGIONLESS)                 for lst in neighbour]             options = filter(lambda item: len(item[1])>0, enumerate(neighbour_field))             random.shuffle(options)              mypuzzle = bytearray(puzzle)             for option, vals in options:                 if mypuzzle[option] != ORL:                     continue                 mypuzzle[option] = random.sample(vals, 1)[0]                 break             return mypuzzle          return individual      def fitness_function(self):         """Returns the function to evaluate the fitness an Alberi puzzle.         """         m = self.m         n = self.n         size = self.size         per_row = self.per_row         per_column = self.per_column         per_region = self.per_region          REGIONLESS = Alberi.REGIONLESS          memo_fitness={}         def fitness(individual, target):             """ Take a partial puzzle and scores it.              The score is equal to the count of empty cells if the puzzle has             but one solution. The score defaults to size if the puzzle has             more than one solution.              The result is memoized, so it can speed up the scoring in case             of duplicate individuals.              Required argument:             individual -- The puzzle to score, in the form of a string of n*m                 letters indicating the regions. The whitespace ' ' can be                 used as a placeholder for a cell with no region assigned.             target -- unused. Here for compatibility with the GA             """             puzzle = str(individual)             out = memo_fitness.get(puzzle)             if out:                 return out             print(puzzle)             try:                 asolver = Alberi(puzzle, m, n, per_row, per_column, per_region)                 sols = [x for _, x in zip(xrange(2), asolver)]                 out = puzzle.count(REGIONLESS) if len(sols) == 1 else size             except ValueError:                 out = size             memo_fitness[puzzle] = out             return out          return fitness      def mutate_function(self):         """Returns the function to mutate an Alberi puzzle.         """         m = self.m         n = self.n         size = self.size         per_row = self.per_row         per_column = self.per_column         per_region = self.per_region         neighbour = self.neighbour          ORL = ord(Alberi.REGIONLESS)          def mutate_individual(individual):             """ Take a puzzle and makes a single mutation to it.              The mutation is made in-place.              If the mutation is made on a whitespace, this labels it with             the letter of a neighbouring field.             If the mutation is made on a labeled cell, this verifies that             the remaining cells still form a singly-connected region.              Required argument:             individual -- The puzzle to mutate, in the form of a string of n*m                 letters indicating the regions. The whitespace ' ' can be                 used as a placeholder for a cell with no region assigned.             """             neighbour_field = [                 set(individual[idx] for idx in lst if individual[idx] != ORL)                 for lst in neighbour]             options = filter(                 lambda item: len(item[1]) > 0,                 enumerate(neighbour_field))             random.shuffle(options)              for option, vals in options:                 if individual[option] == ORL:                     individual[option] = random.sample(vals, 1)[0]                     break                  vals.difference_update([individual[option]])                 if len(vals) == 0:                     continue                  # Tests if removing the element option from the region with                 # its letter leaves a simply connected region. First make                 # the region array with all the indexes of the cells with the                 # letter at the index option (but without option), then do a                 # BFS algorithm to assign a value (weight) to each cell (in                 # this case is the minimum Manhattan distance from the first                 # cell in the array). If every cell has been labeled with a                 # value than the region is simply connected                 region = [idx for idx, v in enumerate(individual)                     if v == individual[option] and idx != option]                 if len(region)==0:                     continue                 home = region.pop()                 weights = [size+1] * len(region)                 curlist = [home]                 curval = 0                 while len(curlist) > 0:                     newlist = []                     newval = curval + 1                     for list_idx in curlist:                         for cell in neighbour[list_idx]:                             try:                                 idx = region.index(cell)                                 if weights[idx] > newval:                                     weights[idx] = newval                                     newlist.append(cell)                             except:                                 pass                     curlist = newlist                     curval = newval                  if all(w <= size for w in weights):                     individual[option] = random.sample(vals, 1)[0]                 else:                     continue                 break          return mutate_individual      def crossover_function(self):         """Returns the function to crossover two puzzles.         """          def crossover_individuals(male, female):             """ Returns a new puzzle made crossing the puzzles given as input.              The result is simply the first half of the male input joined to             the last half of the female input.              Required argument:             male, female -- The puzzles to crossover, in the form of a                 string of n*m letters indicating the regions. The whitespace                 ' ' can be used as a placeholder for a cell with no region                 assigned.             """             half = len(male) / 2             child = male[:half] + female[half:]             return child          return crossover_individuals   

Los individuos se crean a partir de un rompecabezas de inicio modificando una de las celdas 9988776665544337 . La condición física de cada individuo es el recuento de celdas REGIONLESS , si el rompecabezas tiene una solución, de la contratación, el 9988777665544339 del rompecabezas. La mutación se realiza cambiando una célula a una de las etiquetas de su vecino (se realiza un cheque para controlar que las regiones siempre están completamente conectadas). El cruce simplemente baraja la primera mitad de un rompecabezas con los restantes de la otra (esto es peligroso porque no se hace ningún control sobre la validez del nuevo rompecabezas).

La clase principal de solver es lo mismo de la de la última publicación. Acabo de agregar un parámetro aleatorio al constructor para crear fácilmente rompecabezas aleatorios.

  __init__0  

El módulo __init__1 es donde las piezas se pegan hacia abajo.

  __init__2  

En este módulo se definen dos iteradores: 99887776655443313 y __init__4 .

El primero toma las soluciones de un rompecabezas de unión y crecer regiones alrededor de esas células, manteniendo una sola solución para el rompecabezas.

El segundo toma las regiones del primero y toma grupos de regiones para hacer súper regiones que acomodan más que un árbol.

Este paso se necesita solo para agrupar soluciones, de hecho, en la función 99887766655443315 , solo mantenemos una tira de celdas que conectan las soluciones del esquema original. < / p>

Ahora (deberíamos) tener un rompecabezas de una sola solución-múltiple por región, con muchos agujeros en el interior.

Aquí se transforma el algoritmo genético: alimentamos este rompecabezas como la semilla para los individuos y deja que la población evolucione.

Todo lo que describí se implementa en la función 99887766655443316 , que solo toma las características del rompecabezas y (con suerte) sale un rompecabezas completo.

¡Todo está bien, dices? Bueno, el tiempo para un esquema de 12 por 12 como el de la primera publicación es de aproximadamente 24 horas. El número de rompecabezas probados para encontrarlo no es tan grande: en una de las pruebas medí 6935 tentativos (después de la memorización de la condición física), por lo que el cuello de botella sigue siendo el solucionador de rompecabezas. Tal vez se pueda hacer un cambio al exacto para resolver más de un rompecabezas al mismo tiempo, tal vez aceptar un cambio de topología después de que se encuentre una solución ... pero esta sería una tarea realmente difícil.

Otros problemas son

  • A veces, la creación del vector de la solución de inicio es demasiado larga (tal vez el parámetro aleatorio no sea tan bueno para __init__7 );
  • A veces el __init__8 la recursión parece entrar en un bucle durmiendo (necesitamos algo de eurísta para la tarea).

Cualquier sugerencia es muy bienvenida ... exprime su cerebro y déjame saberlo!

ps. Debo acreditar Will Larson para su implementación de algoritmo genético . Lo siento por el retraso, pero perdí el enlace de origen.

Original en ingles

This post is a follow-follow-up to this post and its follow-up.

In those two posts we managed to speed-up the solution of an Alberi puzzle, and to create a one-tree-per-region puzzle.

The complete code hereafter can be used to create multi-tree-per-region puzzles.

Using DFS I had little chance to find a valid puzzle, so I had to resort to a more exotic genetic algorithm.

The first class is the general genetic algorithm impementation (well the simplest of implementations):

"""Genetic algorithm simplicistic and generic implementation. """  import random  class GeneticAlgorithm(object):     """Genetic algorithm iteration cycle.      The aim is to find an individual with the lowest fitness value     by evolving a population of such individuals.      Each individual is tested against a target value to evaluate its fitness      For each evolution loop part of the best are kept for the next cycle     (retain parameter for evolve method), part of the individuals are kept     indipendently from their fitness (random_select parameter), then these     individuals are mutated according to a mutation rate (mutate paramter),     the rest of the new population is made up crossing randomly picked     individuals.     """     def __init__(self, individual, fitness, mutate, crossover):         """Initializes the evolution functions from the problem factory.          Required argument:         individual -- function to generate a new individual. The function can             take a fixed number of parameters to initialize the individual.             This parameters are to be passed to the population method. The             return argument should be a mutable (see mutate).         fitness -- function to score an individual. An individual and the             target will be passed to the function. The target is set by the             evolve method. The function must return a numeric type.         mutate -- function to mutate in-place an individual. The function will             take a mutable as argument         crossover -- function to create a new individual using the genetic             code of the two individuals passed as argument. The return argument             should be a mutable.         """         self.individual = individual         self.fitness = fitness         self.mutate_individual = mutate         self.crossover_individuals = crossover      def population(self, count, *args):         """Create a number of individuals (i.e. a population).          Required argument:         count -- number of individuals to be created         *args -- parameters to be passed to the individual generation function         """         return [self.individual(*args) for _ in range(count)]      def grade(self, pop, target):         """Find average fitness for a population.         """         summed = sum(self.fitness(x, target) for x in pop)         return summed / (len(pop) * 1.0)      def evolve(self, pop, target, retain=0.2, random_select=0.1, mutate=0.2):         """Genetic algorithm evolution loop.          Required argument:         pop --- count of the elements of the population         target -- target value to obtain          Optional arguments:         retain -- Number of elements whith the lowest fitness to keep at             each iteration         random_select -- Rate of selection of elements whithout fitness             filtering         mutate -- Rate of mutation of elements         """         graded = [(self.fitness(x, target), x) for x in pop]         graded = [x[1] for x in sorted(graded)]         retain_length = int(len(graded) * retain)         parents = graded[:retain_length]         # randomly add other individuals to         # promote genetic diversity         for individual in graded[retain_length:]:             if random_select > random.random():                 parents.append(individual)         # mutate some individuals         for individual in parents:             if mutate > random.random():                 self.mutate_individual(individual)         # crossover parents to create children         parents_length = len(parents)         desired_length = len(pop) - parents_length         children = []         while len(children) < desired_length:             male = random.randint(0, parents_length-1)             female = random.randint(0, parents_length-1)             if male != female:                 male = parents[male]                 female = parents[female]                 child = self.crossover_individuals(male, female)                 children.append(child)         parents.extend(children)         return parents 

The class __init__ takes as argument the functions needed to generate an individual, evaluate its fitness against a target, mutate (in place) an individual and crossover two individual to make a third one.

The methods exposed are population, which creates the initial individuals to be evolved, grade, used to evaluate the global fitness of a population, and evolve, the core of the algorithm, that grows-up the population.

The functions I gave to the GeneticAlgorithm class are created by the following class:

"""Fill the empty cells of an Alberi puzzle using a genetic algorithm """ from AlberiCover import Alberi from GeneticAlgorithm import GeneticAlgorithm import random  class AlberiGeneticFactory(object):     """Creates the functions needed for the evolution of the GA     """     def __init__(self, m, n, per_row=2, per_column=2, per_region=2):         """Initializes the factory parameters.          Required argument:         n -- Number of rows         m -- Number of columns          Optional arguments:         per_row -- Number of trees per row. (Default: 2.)         per_column -- Number of trees per column. (Default: 2.)         per_region -- Number of trees per region. (Default: 2.)          """          self.m = m         self.n = n         self.size = size = m * n         self.per_row = per_row         self.per_column = per_column         self.per_region = per_region          neighbour = []         for idx in range(size):             row, col = divmod(idx, m)             neighbour.append(                 [endr * n + col for endr in range(row - 1, row + 2)                     if 0 <= endr < m and endr != row] +                 [row * n + endc for endc in range(col - 1, col + 2)                     if 0 <= endc < n and endc != col]             )         self.neighbour = neighbour      def individual_function(self):         """Returns the function to create an Alberi puzzle.         """         REGIONLESS = Alberi.REGIONLESS         ORL = ord(REGIONLESS)         neighbour = self.neighbour          def individual(puzzle):             """ Take a puzzle and makes a single mutation to it.              The mutation is made on a whitespace, labeling it with the letter             of a neighbouring field.              Required argument:             puzzle -- The puzzle to mutate, in the form of a string of n*m                 letters indicating the regions. The whitespace ' ' can be                 used as a placeholder for a cell with no region assigned.             """             neighbour_field = [                 set(puzzle[idx] for idx in lst if puzzle[idx] != REGIONLESS)                 for lst in neighbour]             options = filter(lambda item: len(item[1])>0, enumerate(neighbour_field))             random.shuffle(options)              mypuzzle = bytearray(puzzle)             for option, vals in options:                 if mypuzzle[option] != ORL:                     continue                 mypuzzle[option] = random.sample(vals, 1)[0]                 break             return mypuzzle          return individual      def fitness_function(self):         """Returns the function to evaluate the fitness an Alberi puzzle.         """         m = self.m         n = self.n         size = self.size         per_row = self.per_row         per_column = self.per_column         per_region = self.per_region          REGIONLESS = Alberi.REGIONLESS          memo_fitness={}         def fitness(individual, target):             """ Take a partial puzzle and scores it.              The score is equal to the count of empty cells if the puzzle has             but one solution. The score defaults to size if the puzzle has             more than one solution.              The result is memoized, so it can speed up the scoring in case             of duplicate individuals.              Required argument:             individual -- The puzzle to score, in the form of a string of n*m                 letters indicating the regions. The whitespace ' ' can be                 used as a placeholder for a cell with no region assigned.             target -- unused. Here for compatibility with the GA             """             puzzle = str(individual)             out = memo_fitness.get(puzzle)             if out:                 return out             print(puzzle)             try:                 asolver = Alberi(puzzle, m, n, per_row, per_column, per_region)                 sols = [x for _, x in zip(xrange(2), asolver)]                 out = puzzle.count(REGIONLESS) if len(sols) == 1 else size             except ValueError:                 out = size             memo_fitness[puzzle] = out             return out          return fitness      def mutate_function(self):         """Returns the function to mutate an Alberi puzzle.         """         m = self.m         n = self.n         size = self.size         per_row = self.per_row         per_column = self.per_column         per_region = self.per_region         neighbour = self.neighbour          ORL = ord(Alberi.REGIONLESS)          def mutate_individual(individual):             """ Take a puzzle and makes a single mutation to it.              The mutation is made in-place.              If the mutation is made on a whitespace, this labels it with             the letter of a neighbouring field.             If the mutation is made on a labeled cell, this verifies that             the remaining cells still form a singly-connected region.              Required argument:             individual -- The puzzle to mutate, in the form of a string of n*m                 letters indicating the regions. The whitespace ' ' can be                 used as a placeholder for a cell with no region assigned.             """             neighbour_field = [                 set(individual[idx] for idx in lst if individual[idx] != ORL)                 for lst in neighbour]             options = filter(                 lambda item: len(item[1]) > 0,                 enumerate(neighbour_field))             random.shuffle(options)              for option, vals in options:                 if individual[option] == ORL:                     individual[option] = random.sample(vals, 1)[0]                     break                  vals.difference_update([individual[option]])                 if len(vals) == 0:                     continue                  # Tests if removing the element option from the region with                 # its letter leaves a simply connected region. First make                 # the region array with all the indexes of the cells with the                 # letter at the index option (but without option), then do a                 # BFS algorithm to assign a value (weight) to each cell (in                 # this case is the minimum Manhattan distance from the first                 # cell in the array). If every cell has been labeled with a                 # value than the region is simply connected                 region = [idx for idx, v in enumerate(individual)                     if v == individual[option] and idx != option]                 if len(region)==0:                     continue                 home = region.pop()                 weights = [size+1] * len(region)                 curlist = [home]                 curval = 0                 while len(curlist) > 0:                     newlist = []                     newval = curval + 1                     for list_idx in curlist:                         for cell in neighbour[list_idx]:                             try:                                 idx = region.index(cell)                                 if weights[idx] > newval:                                     weights[idx] = newval                                     newlist.append(cell)                             except:                                 pass                     curlist = newlist                     curval = newval                  if all(w <= size for w in weights):                     individual[option] = random.sample(vals, 1)[0]                 else:                     continue                 break          return mutate_individual      def crossover_function(self):         """Returns the function to crossover two puzzles.         """          def crossover_individuals(male, female):             """ Returns a new puzzle made crossing the puzzles given as input.              The result is simply the first half of the male input joined to             the last half of the female input.              Required argument:             male, female -- The puzzles to crossover, in the form of a                 string of n*m letters indicating the regions. The whitespace                 ' ' can be used as a placeholder for a cell with no region                 assigned.             """             half = len(male) / 2             child = male[:half] + female[half:]             return child          return crossover_individuals 

The individuals are created from a starting puzzle by modifying one of the REGIONLESS cells. The fitness of each individual is the count of REGIONLESS cells, if the puzzle has one solution, else the size of the puzzle. The mutation is made by changing a cell to one of its neighbours' label (a check is made to control that the regions are always completely connected). The crossover simply shuffles the first half of a puzzle with the remaining of the other (this is dangerous because no check is made on the validity of the new puzzle).

The main solver class is about the same of the one in the last post. I just added a random parameter to the constructor to easily create random puzzles.

"""Solver for an Alberi puzzle using exact cover """ from collections import Iterator from itertools import product from ExactCoverExt import ExactCover  class Alberi(Iterator):     """An iterator that yields the solutions to an Alberi problem.      >>> puzzle = '''     ... aabbbccccccc     ... accccccdddee     ... accfcfdddgee     ... afffffddggee     ... aafffdddggee     ... afffddddgggg     ... hffffdiijjjj     ... hffffiiikkkk     ... hhhfiiiiiklk     ... hhhffiilllll     ... hhhffiilllll     ... hhhfffilllll     ... '''     >>> asolver = Alberi(*Alberi.multiline_to_solver_params(puzzle))     >>> print(asolver.decode_solution(next(asolver)))     >>> quit()     aaBbBccccccc     acccccCdddeE     acCfcfdddGee     AfffffDdggee     aafffdddGgEe     AfffDdddgggg     hffffdiiJjJj     hffFfIiikkkk     hhhfiiiiiKlK     hHhffiiLllll     hhhFfIilllll     hHhfffiLllll      """     REGIONLESS = ' '     VOID = '.'      def __init__(self, puzzle, m, n, per_row=2, per_column=2, per_region=2, random=False):         """Construct an Alberi instance.          Required argument:         puzzle -- The puzzle to solve, in the form of a string of n*m             letters indicating the regions. The whitespace ' ' can be used             as a placeholder for a cell with no region assigned. The             period '.' can be used to force an empty cell in the solution.         n -- Number of rows         m -- Number of columns          Optional arguments:         per_row -- Number of trees per row. (Default: 2.)         per_column -- Number of trees per column. (Default: 2.)         per_region -- Number of trees per region. (Default: 2.)         random -- True to make a random scheme          """         self.m = m         self.n = n         self.puzzle = puzzle         REGIONLESS = Alberi.REGIONLESS         VOID = Alberi.VOID          regions = set(self.puzzle).difference(REGIONLESS + VOID)         trees = m * per_column         if trees != n * per_row or (                 trees != len(regions) * per_region and len(regions) > 0):             raise ValueError("Bad puzzle instance. '" + puzzle + "'")         def constraints():             for x, y in product(range(m), range(n)):                 cell_at_xy = self.puzzle[self.rc2idx(y, x)]                 if cell_at_xy != VOID:                     yield (y, x), [                         ('row', y), ('column', x)                     ] + ([('region', cell_at_xy)]                         if cell_at_xy != REGIONLESS else []                     ) + [                         ('neighbour', p, q)                         for p, q in product(range(x, x+2), range(y, y+2))                         if 0 <= p < m and 0 <= q < n                     ]         def counts():             for x in range(m):                 yield ('column', x), per_column             for y in range(n):                 yield ('row', y), per_row             for r in regions:                 yield ('region', r), per_region         self.solver = ExactCover(dict(constraints()),                                  counts=dict(counts()),                                  satisfy=dict(counts()),                                  random=random)      @staticmethod     def multiline_to_solver_params(puzzle):         """Construct the set of parameters to call the Alberi constructor.          Required argument:         puzzle -- The puzzle to solve, in the form of a string of n             words, each word consisting of m letters indicating the             regions.          Returns:         puzzle -- A single line representetion of the input         m -- Number of columns         n -- Number of rows         """         puzzle = puzzle.split()         m = len(puzzle[0])         n = len(puzzle)         puzzle = ''.join(puzzle)         return (puzzle, m, n)      def rc2idx(self, row, col):         """Return the index of the cell at (row, col)."""         return row * self.m + col      def decode_solution(self, solution):         """Decode an Alberi solution and return it as a string."""         grid = [             list(self.puzzle[(r*self.m):((r+1)*self.m)])             for r in xrange(self.n)         ]         for y, x in solution:             grid[y][x] = grid[y][x].upper()         return '\n'.join(''.join(row) for row in grid)      def solution_to_string(self, solution):         """Build a single line string for an Alberi solution."""         CELL_OCCUPIED = '*'         CELL_EMPTY = '|'          out = bytearray(CELL_EMPTY * (self.m * self.n))         for y, x in solution:             out[self.rc2idx(y, x)] = CELL_OCCUPIED         return str(out)      def render_board(self, puzzle=None, solution=None):         """Draw a board for the Alberi problem.          Optional arguments:         puzzle -- If defined overrides self.puzzle (without changing it).         solution -- If defined the 'trees' are drawn inside the board.         """         CELL_OCCUPIED = '*'         CELL_EMPTY = ' '          m = self.m         n = self.n         if puzzle is None:             puzzle = self.puzzle         lines = [             puzzle[(r * m):((r + 1) * m)]             for r in xrange(n)         ]         hdiff = [             [                 '|' if p[0] != p[1] else ' '                 for p in zip(line[:-1], line[1:])             ] + ['|']             for line in lines         ]         vdiff = [             [                 '---' if lines[r][c] != lines[r+1][c] else '   '                 for c in xrange(m)             ]             for r in xrange(n-1)         ]         vdiff.append(['---' for c in xrange(m)])         if solution is not None:             grid = [                 list(CELL_EMPTY * self.m)                 for r in xrange(self.n)             ]             for y, x in solution:                 grid[y][x] = CELL_OCCUPIED             lines = [''.join(row) for row in grid]         out = '+' + '---+' * m         for r in xrange(n):             out += '\n|' + ''.join([                 ' {0} {1}'.format(q[0], q[1])                 for q in zip(lines[r], hdiff[r])             ])             out += '\n+' + ''.join([                 '{0}+'.format(q)                 for q in vdiff[r]             ])          return out      def __next__(self):         return next(self.solver)      next = __next__             # for compatibility with Python 2 

The AlberiMaker module is where the pieces are glued toghether.

"""Find an Alberi puzzle using a genetic algorithm """ from AlberiCover import Alberi from random import sample from string import ascii_letters from collections import defaultdict from GeneticAlgorithm import GeneticAlgorithm from AlberiGenetic import AlberiGeneticFactory from itertools import islice, combinations  def one_per_region_creator(m, n, per_row, per_column, origsol):     """Creates a single solution Alberi scheme growing regions around the     trees positioned in the coordinates at origsol.      Required argument:     n -- Number of rows     m -- Number of columns     per_row -- Number of trees per row.     per_column -- Number of trees per column.     origsol -- Coordinates of the trees.     """     size = m * n     REGIONLESS = Alberi.REGIONLESS     ORL = ord(REGIONLESS)     OVOID = ord(Alberi.VOID)      # Assigns a letter to each tree in the original solution     puzzle = bytearray(REGIONLESS * size)     asolver = Alberi(str(puzzle), m, n, per_row, per_column, per_region=1)     for coords, letter in zip(origsol, ascii_letters):         y, x = coords         puzzle[asolver.rc2idx(y, x)] = letter      # Just a debug output to verify that the solution did not change     print(str(puzzle))     asolver = Alberi(str(puzzle), m, n, per_row, per_column, per_region=1)     print(asolver.solution_to_string(next(asolver)))      # An array of neighbour's positions, to speed up calculations     neighbour = []     for idx in range(size):         row, col = divmod(idx, m)         neighbour.append(             [endr * n + col for endr in range(row - 1, row + 2)                 if 0 <= endr < m and endr != row] +             [row * n + endc for endc in range(col - 1, col + 2)                 if 0 <= endc < n and endc != col]         )      def recurse(puzzle):         """Backtracking function. Assigns a letter to an empty cell,         neighbouring a cell with a letter assigned, and verify that the         new scheme has only one solution         """         # Makes a set of neighbours for each empty cell in the puzzle         neighbour_field = [             set(puzzle[idx] for idx in lst             if puzzle[idx] != ORL and puzzle[idx] != OVOID)             for lst in neighbour]          # Sort the list of the neighbours placing first the cells with few         # neighbouring fields and then removes the cells without neighbours         best_list = sorted(enumerate(neighbour_field), key=lambda j: len(j[1]))         best_list = filter(lambda item: len(item[1]) > 0, best_list)          mypuzzle = puzzle[:]         for item in best_list:             best = item[0]             if mypuzzle[best] != ORL:                 continue             vals = item[1]             for v in vals:                 mypuzzle[best] = v                 asolver = Alberi(                     str(mypuzzle), m, n, per_row, per_column, per_region=1                 )                 sols = list(islice(asolver, None, 2))                 if len(sols) == 1:                     print(str(mypuzzle))                     if mypuzzle.count(REGIONLESS) == 0:                         yield mypuzzle                     else:                         for rec_puzzle in recurse(mypuzzle):                             yield rec_puzzle             mypuzzle[best] = REGIONLESS      for scheme in recurse(puzzle):         print(asolver.render_board(puzzle=str(scheme)))         yield scheme   def region_factory(m, n, per_row, per_column, per_region, scheme):     """Joins two or more regions of a one-tree-per-region scheme, and     returns a scheme with per_region trees per region.      The returned scheme usually have more than one solution.      Required argument:     n -- Number of rows     m -- Number of columns     per_row -- Number of trees per row.     per_column -- Number of trees per column.     per_region -- Number of trees per region.     scheme -- Initial scheme. Must be a one-tree-per-region scheme.     """     if per_region == 1:         yield scheme         return      region_count = m * per_row / per_region     size = m * n      # A dictionary with the region identifier as key and a set of neighbouring     # regions' identifiers as value     neighbour_region = defaultdict(set)     for idx, v in enumerate(scheme):         row, col = divmod(idx, m)         for endr in range(row - 1, row + 2):             if 0 <= endr < m and endr != row:                 p = scheme[endr * n + col]                 if p == v or p == ord(Alberi.VOID):                     continue                 neighbour_region[v].add(p)         for endc in range(col - 1, col + 2):             if 0 <= endc < n and endc != col:                 p = scheme[row * n + endc]                 if p == v:                     continue                 neighbour_region[v].add(p)      def validate_connectivity(myneighbour):         """Tests if the graph described in myneighbour is completely connected.         First make the region array with all the indexes of the cells         uncovered. Then do a BFS algorithm to assign a value (weight) to         each cell (in this case is the minimum Manhattan distance from the         first cell in the array). If every cell has been labeled with a         value than the graph is completely connected         """         region = myneighbour.keys()         if len(region)==0:             return True         home = region[0]         weights = [size+1] * len(region)         weights[region.index(home)] = 0         curlist = [home]         curval = 0         while len(curlist) > 0:             newlist = []             newval = curval + 1             for key in curlist:                 for item in myneighbour[key]:                     try:                         idx = region.index(item)                         if weights[idx] > newval:                             weights[idx] = newval                             newlist.append(item)                     except ValueError:                         pass             curlist = newlist             curval = newval          if any(item>size for item in weights):             return False         return True      def region_select_recurse(neighbour_region, selection, depth):         """Depth first search for the groups of regions.         Selects one of the remaining items in the list of neighbours of the         last item selected.         """         neighbour_idx = [             k for k, q in neighbour_region.iteritems()             if len(q.intersection(selection))>0 and not k in selection]         myneighbour = {             k: q             for k, q in neighbour_region.iteritems()             if k != selection[-1]         }          best_list = sorted(neighbour_idx, key=lambda j: len(myneighbour[j].difference(selection)))          for v in best_list:             if depth == 1:                 yield selection + (v,)                 return              if len(myneighbour[v]) == 0:                 continue              for p in region_select_recurse(myneighbour, selection + (v,), depth - 1):                 yield p      def super_region_recurse(neighbour_region, super_regions):         """Backtracking function. For each region take some element in the         set of neighbouring regions and mark these items as a super-region         """         best_list = sorted(             neighbour_region,             key=lambda j: len(neighbour_region[j]))          for v in best_list:             no_group = True             if len(neighbour_region[v]) == 0:                 return             for p in region_select_recurse(neighbour_region, (v,), per_region - 1):                 no_group = False                 myneighbour = {                     k: q.difference(p)                     for k, q in neighbour_region.iteritems() if k != v and k not in p                 }                  if not validate_connectivity(myneighbour):                     continue                  mysuper_regions = super_regions + [p]                 if len(mysuper_regions) == region_count:                     yield mysuper_regions                 else:                     for out in super_region_recurse(myneighbour, mysuper_regions):                         yield out             if no_group:                 return      for super_region in super_region_recurse(neighbour_region, []):         translator = bytearray(256)         for c, l in zip(super_region, ascii_letters):             for v in c:                 translator[v] = l         translator[ord(Alberi.VOID)] = Alberi.VOID         scheme2 = scheme.translate(translator)          print(str(scheme2))         yield scheme2   def reduce_scheme(m, n, per_row, per_column, per_region, scheme3, origsol):     """Blanks as much cell as is possible in a region keeping the trees     in origsol connected by a strip of cells.      The returned scheme usually have more than one solution.      Required argument:     n -- Number of rows     m -- Number of columns     per_row -- Number of trees per row.     per_column -- Number of trees per column.     per_region -- Number of trees per region.     scheme3 -- Initial scheme. Must be a one-tree-per-region scheme.     origsol -- Positions of the trees.     """     if per_region == 1:         for idx in range(len(scheme3)):             if divmod(idx, m) not in origsol:                 scheme3[idx] = Alberi.REGIONLESS         return      size = m * n     for letter in set(scheme3):         region = [divmod(idx, m) for idx, value in enumerate(scheme3) if value == letter]         pivots = set(region).intersection(origsol)          # Uses Dijkstra algorithm to find the best path between the cells.         # home is the first of the trees, weights is a list of the distances         # from home, origin is the previous cell in the best path. curlist         # holds the array of the cells to test in the next iteration.         home = pivots.pop()         weights = [size+1] * len(region)         origin = [None] * len(region)         weights[region.index(home)] = 0         curlist = [home]         curval = 0         while any(weights[region.index(pivot)] > size for pivot in pivots):             newlist = []             newval = curval + 1             for r, c in curlist:                 for cell in [(r + 1, c), (r - 1, c), (r, c + 1), (r, c - 1)]:                     try:                         idx = region.index(cell)                         if weights[idx] > newval:                             weights[idx] = newval                             origin[idx] = (r, c)                             newlist.append(cell)                     except ValueError:                         pass             curlist = newlist             curval = newval          path = set()         for pivot in pivots:             path.add(pivot)             while origin[region.index(pivot)]:                 pivot = origin[region.index(pivot)]                 path.add(pivot)          for idx, l in enumerate(scheme3):             if l == letter:                 cell = divmod(idx, m)                 if cell in path:                     continue                 scheme3[idx] = Alberi.REGIONLESS   def make_it(m, n, per_row, per_column, per_region):     """Creates a single solution Alberi scheme.      This function find the solution using the following sub-steps:     * Create a solution vector with the desired trees per row and column.     * Create a single-tree-per-region puzzle around these solutions.     * Group the regions of this puzzle to have super-regions with enough       trees per region.     * Leave only a strip of cells joining the solution cells to ensure having       a single solution puzzle. The remaining cells become REGIONLESS.     * Evolve this scheme decreasing the number of REGIONLESS cells while       mantaining a single solution for the result.     * When the scheme has no more REGIONLESS cells, return it.      Required argument:     n -- Number of rows     m -- Number of columns     per_row -- Number of trees per row.     per_column -- Number of trees per column.     per_region -- Number of trees per region.     """     size = m * n      alberiGeneticFactory = AlberiGeneticFactory(         m, n,         per_row, per_column, per_region)      alberiGenetic = GeneticAlgorithm(         alberiGeneticFactory.individual_function(),         alberiGeneticFactory.fitness_function(),         alberiGeneticFactory.mutate_function(),         alberiGeneticFactory.crossover_function())      target = 0     p_count = 40      asolver = Alberi('a' * size, m, n, per_row, per_column, m * per_row, True)     origsol = next(asolver)     one_per_region = one_per_region_creator(m, n, per_row, per_column, origsol)      for scheme in one_per_region:         for scheme3 in region_factory(m, n, per_row, per_column, per_region, scheme):             str_scheme = str(scheme3)             print(asolver.render_board(puzzle=str_scheme, solution=origsol))             reduce_scheme(m, n, per_row, per_column, per_region, scheme3, origsol)             print(str(scheme3))             lst = [idx for idx, cell in enumerate(scheme3) if cell != ord(Alberi.REGIONLESS)]             print(asolver.render_board(puzzle=str_scheme, solution=[divmod(idx, m) for idx in lst]))              p = alberiGenetic.population(p_count, str(scheme3))             fitness_history = [alberiGenetic.grade(p, target),]             while alberiGenetic.fitness(p[0], target) > 0:                 p = alberiGenetic.evolve(p, target)                 population_grade = alberiGenetic.grade(p, target)                 fitness_history.append(population_grade)                 print('{0} {1} {2}'.format(str(p[0]), p[0].count(' '), population_grade))                 if population_grade == size:                     break             else:                 return str(p[0])   if __name__ == '__main__':     m = n = 9     per_row = 2     per_column = 2     per_region = 2      asolver = Alberi('a' * (m * n), m, n, per_row, per_column, m * per_row)     puzzle = make_it(m, n, per_row, per_column, per_region)     print(asolver.render_board(puzzle=puzzle)) 

In this module two iterators are defined: one_per_region and region_factory.

The first one takes the solutions of a regionless puzzle and grow regions around those cells, keeping a single solution for the puzzle.

The second one takes the regions from the former and take groups of regions to make super-regions that will accomodate more than a tree.

This step is needed only to group solutions, in fact, in the reduce_scheme function, we keep only a strip of cells connecting the solutions of the original scheme.

Now we (should) have a single-solution-multi-tree-per-region puzzle, with many holes inside.

Here it cames the genetic algorithm: we feed this puzzle as the seed for the individuals and let the population evolve.

Everything I described is implemented in the make_it function, that takes only the carachteristics of the puzzle and (hopefully) outputs a complete puzzle.

Everything is fine you say? Well, the time for a 12 by 12 scheme like the one in the first post is about 24 hours. The number of puzzles tested to find it is not so large: in one of the tests I measured 6935 tentatives (after memoization of the fitness), so the bottleneck is still the puzzle solver. Maybe a change can be made to the ExactCover to solve more than one puzzle at the same time, maybe accepting a topology change after a solution is found... but this would be a really hard task.

Other problems are

  • sometimes, the creation of the starting solution vector is too long (maybe the random parameter is not so good for ExactCover);
  • sometimes the region_factory recursion seem to get into a neverending loop (we need some euristic for the task).

Any suggestions are very welcome... squeeze your brains and let me know!!

PS. I must credit Will Larson for his genetic algorithm implementation. Sorry for the delay but I lost the source link.

           

Lista de respuestas

2
 
vote

Su código se ve bien, bien organizado y bien documentado.

Aquí hay algunos detalles que probablemente podría mejorar (no he leído todo el código).

División de flotador

Supongo summed / (len(pop) * 1.0) es solo una forma hacky de obtener una división de flotadores. La División Float es el comportamiento predeterminado en Python 3 (use // para división de enteros).

Por lo tanto, una forma probablemente más clara de tener lo que desea es usar: from __future__ import division .

Ordenar con la tecla

El siguiente código es bastante confuso:

      graded = [(self.fitness(x, target), x) for x in pop]     graded = [x[1] for x in sorted(graded)]   

Supongo que está tratando de obtener elementos de pop ordenado por su forma física al construir tuplas, ordenándolos y luego recuperar el elemento inicial de la tupla.

Buena nueva, la sorted La función tiene un parámetro key para hacer exactamente esto.

  graded = sorted(pop, key=lambda e: fitness(e, target))   

(esto no se prueba)

intente excepto pase

Esta pieza de código

                          try:                             whatever                         except:                             pass   

me dio escalofríos.

Debe (casi) Siempre especifique el tipo de excepción que está tratando de atrapar. Además, generalmente no hay una buena razón para pass en la captura de excepciones. Más información sobre esto: ¿Por qué "excepto: Pase" una mala práctica de programación? , la más diabólica Python Antipattern .

documentación constante

Su función DOCSTRINGS Use tanto el modo imperativo ("Hacer algo") y el modo declarativo ("hace algo").

Como una nota lateral, pep 257 sugiere:

El Docstring es una frase que termina en un período. Prescribe la función o el efecto del método como un comando ("Haz esto", "devuelve eso"), no como una descripción; p.ej. No escriba "Devuelve el PathName ...".

(y creo que 99887766555443310 intenta detectar esto ).

bucle sobre una cuadrícula

  //1  

parece un poco antinatural. Conoces las dos dimensiones de una cuadrícula y quieres iterar a todas las células. La forma natural (pero verbosa) de hacerlo es probablemente tener 2 bucles anidados, pero está utilizando algún truco matemático para tener un simple bucle.

Es posible que le gustaría saber que //2 ofrece una solución a este problema exacto: //3 .

funciona así:

  //4  
 

Your code looks good, well organised and well documented.

Here are a few details that you could probably improve (I haven't read the whole code).

float division

I assume summed / (len(pop) * 1.0) is just a hacky way to get a float division. Float division is the default behavior in Python 3 (you use // for integer division).

Thus, a probably clearer way to have what you want is to use : from __future__ import division .

Sort with key

The following code is quite confusing :

    graded = [(self.fitness(x, target), x) for x in pop]     graded = [x[1] for x in sorted(graded)] 

I guess you are trying to get elements from pop sorted by their fitness by constructing tuples, sorting them and then retrieving the initial element from the tuple.

Good new, the sorted function has a parameter key to do exactly this.

graded = sorted(pop, key=lambda e: fitness(e, target)) 

(This is not tested)

Try except pass

This piece of code

                        try:                             whatever                         except:                             pass 

gave me shivers.

You should (almost) always specify the type of Exception you are trying to catch. Also, there is usually no good reason to pass on exception catching. More about this : Why is xe2x80x9cexcept: passxe2x80x9d a bad programming practice?, The Most Diabolical Python Antipattern .

Consistent documentation

Your function docstrings use both imperative mode ("do something") and declarative mode ("does something").

As a side-note, PEP 257 suggests :

The docstring is a phrase ending in a period. It prescribes the function or method's effect as a command ("Do this", "Return that"), not as a description; e.g. don't write "Returns the pathname ...".

(And I think that pep257 tries to detect this).

Looping over a grid

    self.m = m     self.n = n     self.size = size = m * n      for idx in range(size):         row, col = divmod(idx, m)         ... 

Seems a bit unnatural. You know the two dimensions of a grid and you want to iterate over all cells. The natural (yet verbose) way to do so is probably to have 2 nested loops but you are using some mathematical trick in order to have a simple loop.

You might like to know that itertools offers a solution to this exact problem : itertools.product.

It works like this :

>>> n, m = 2, 3 >>> [divmod(i, m) for i in range(n*m)] [(0, 0), (0, 1), (0, 2), (1, 0), (1, 1), (1, 2)] >>> list(itertools.product(range(n), range(m))) [(0, 0), (0, 1), (0, 2), (1, 0), (1, 1), (1, 2)] 
 
 
     
     

Relacionados problema

18  Algoritmo genético para proyectos de algoritmos inteligentes  ( Genetic algorithm for clever algorithms project ) 
Escribí un montón de código de rubí para un proyecto de libro que acabo de terminar. Una crítica es que es un código fino, pero no es muy "rubí como". Estoy d...

2  Funciones de cruce y mutación para algoritmo genético  ( Crossover and mutation functions for genetic algorithm ) 
Estoy escribiendo un algoritmo de descifrado usando GA con crossover y mutación. Mi rendimiento es (muy) pobre, a menudo se estanca temprano o convergente a l...

3  Vendedor ambulante problema Algoritmo genético  ( Traveling salesman problem genetic algorithm ) 
Esta es mi opinión sobre este problema. No quiero determinar las distancias, no es adecuado para la aplicación para la aplicación. Lo usaré en Shool para dete...

11  Algoritmo genético para "Hello World"  ( Genetic algorithm for hello world ) 
He escrito una implementación de Erlang del algoritmo genético para un programa "Hello World" como se describe aquí . Esta es mi primera vez que escriba cu...

2  La matriz hash realiza la eliminación gaussiana  ( Hash matrix performs gaussian elimination ) 
Esta es la matriz de hash que usé para procesar la matriz para mi algoritmo cuadrático de tamiz. Puede encontrar el código completo en aquí (es java 7 ), p...

5  Algoritmo genético en Python que parcelas su evolución  ( Genetic algorithm in python that plots its evolution ) 
Después de programar en Haskell por un tiempo, he adjuntado a un estilo funcional. Esto es claramente evidente en el código para mi algoritmo genético. ¿Pod...

7  Algoritmo genético para N-Queens es muy lento  ( Genetic algorithm for n queens is very slow ) 
Uso del algoritmo genético para resolver el problema N-Queens donde n = 22. Mi programa es funcional y es capaz de resolver problemas de N-Queen hasta donde n...

9  Algoritmo genético para resolver un rompecabezas  ( Genetic algorithm for solving a puzzle ) 
editar. versión 2 . Estoy trabajando en un algoritmo genético para resolver un pequeño "rompecabezas". Dado un archivo de texto con N Filas con 4 int...

20  Algoritmo genético para "Hello World"  ( Genetic algorithm for hello world ) 
Este programa utiliza un algoritmo genético para obtener la cadena "Hello, World!" . Se puede resumir de la siguiente manera: Crear una población inicial ...

1  Etapa final del algoritmo genético  ( Genetic algorithm final stage ) 
He escrito el código para un algoritmo genético y tiene la función de cruce, la función de mutación, la función del selector de padres y una función para tran...




© 2022 respuesta.top Reservados todos los derechos. Centro de preguntas y respuestas reservados todos los derechos