neural - tensorflow python

¿Hay una mejor manera de adivinar posibles variables desconocidas sin fuerza bruta que lo que estoy haciendo? ¿Aprendizaje automático?

Question

Esta pregunta ya tiene una respuesta aquí:

• ¿Cómo abordar un algoritmo de juego de adivinación de números (con un giro)? 5 respuestas

Tengo un juego con las siguientes reglas:

• A un usuario se le dan precios de la fruta y tiene la oportunidad de comprar o vender artículos en su cesta de fruta cada vez.

• El usuario no puede realizar más de un 10% de cambio total en su cesta en un solo turno.

• Los precios de las frutas cambian todos los días y cuando se multiplican por las cantidades de artículos en la canasta de frutas, el valor total de la canasta cambia en relación con los cambios en los precios de las frutas todos los días también.
• El programa solo recibe el precio actual de todas las frutas y el valor actual de la canasta (precio actual de las cantidades de fruta * para todos los artículos de la canasta).
• Sobre la base de estos 2 insumos (todos los precios de la fruta y el valor total de la canasta), el programa trata de adivinar qué artículos hay en la canasta.
• Una cesta no puede contener más de 100 artículos, pero las ranuras pueden estar vacías
• El jugador puede jugar varios turnos.

Mi objetivo es adivinar con precisión lo más barato posible computacionalmente (lea: sin fuerza bruta) y escalar si hay miles de nuevos frutos.

Estoy luchando para encontrar una respuesta, pero en mi mente, no es difícil. Si tengo la siguiente tabla. Pude estudiar el día 1 y obtener los siguientes datos:

Apple   1
Pears   2
Oranges 3

Basket Value = 217

Puedo hacer una parte posterior del cálculo de la servilleta y asumir que los pesos en la canasta son: 0 manzana, 83 peras y 17 naranjas que equivalen a un valor de canasta de 217.

Al día siguiente, los valores de las frutas y la cesta cambian. A (manzana = 2, pera 3, naranjas 5) con un valor de cesta de 348. Cuando tomo mis pesos supuestos (0,83,17) obtengo un valor total de 334, ¡no es correcto! Ejecutando esto por mi guión, veo que la coincidencia más cercana es 0 manzanas, 76 peras, 24 naranjas, que a pesar de ser igual a 348 cuando el% de cambio factorizado es un 38%, ¡no es posible!

Sé que puedo forzar completamente esta fuerza bruta, pero si tengo 1000 frutas, no se escalará. No saltar en cualquier carro, pero ¿algo como una red neuronal puede descartar rápidamente lo poco probable, así que calculo grandes volúmenes de datos? Creo que tienen que ser una forma más escalable / rápida que la fuerza bruta pura. ¿O hay algún otro tipo de solución que pueda obtener el resultado?

Aquí están los datos sin procesar (recuerde que el programa solo puede ver los precios y el valor total de la cesta):

Aquí hay un código de fuerza bruta (Gracias @paul Hankin por un ejemplo más limpio que el mío):

def possibilities(value, prices):
    for i in range(0, value+1, prices[0]):
        for j in range(0, value+1-i, prices[1]):
            k = value - i - j
            if k % prices[2] == 0:
                yield i//prices[0], j//prices[1], k//prices[2]

def merge_totals(last, this, r):
    ok = []
    for t in this:
        for l in last:
            f = int(sum(l) * r)
            if all(l[i] -f <= t[i] <= l[i] + f for i in range(len(l))):
                ok.append(t)
                break
    return ok

days = [
    (217, (1, 2, 3)),
    (348, (2, 3, 5)),
    (251, (1, 2, 4)),
]

ps = None
for i, d in enumerate(days):
    new_ps = list(possibilities(*d))
    if ps is None:
        ps = new_ps
    ps = merge_totals(ps, new_ps, 0.10)

    print(''Day %d'' % (i+1))
    for p in ps:
        print(''Day %d,'' % (i+1), ''apples: %s, pears: %s, oranges: %s'' % p)
    print

Actualización - la información hasta ahora es impresionante. ¿Tiene sentido dividir el problema en dos problemas? Uno es generar las posibilidades, mientras que el otro es encontrar la relación entre las posibilidades (no más de un 10% de cambio diario). Al descartar posibilidades, ¿no se podría usar eso para ayudar solo a generar posibilidades posibles, para empezar? No estoy seguro de que el enfoque sea todavía, pero sí siento que ambos problemas son diferentes pero están estrechamente relacionados. ¿Tus pensamientos?

Actualización 2 : hay muchas preguntas sobre el% de cambio. Este es el volumen total de artículos en la cesta que puede cambiar. Para usar el ejemplo del juego, Imagine dice la tienda: puedes vender / devolver / comprar frutas, pero no pueden ser más del 10% de tu última factura. Entonces, aunque el cambio en los precios de la fruta puede causar cambios en el valor de su canasta, el usuario no puede realizar ninguna acción que pueda impactarlo en más del 10%. Por lo tanto, si el valor era 100, pueden hacer cambios para crear hasta 110 pero no más.

Answer 1

Enfoque de programación lineal integral

Esto se configura de forma natural como un Programa Integer de múltiples pasos, con las tenencias en {manzanas, peras, naranjas} del paso anterior, teniendo en cuenta el cálculo del cambio relativo en las tenencias que debe restringirse. No hay una noción de óptimo aquí, pero podemos convertir la restricción de "rotación" en un objetivo y ver qué sucede.

Las soluciones proporcionadas mejoran las de su gráfico anterior y son mínimas en el sentido de cambio total en las tenencias de la cesta.

Comentarios -

• No sé cómo calculó la columna "% de cambio" en su tabla. ¿Un cambio del Día 1 al Día 2 de 20 manzanas a 21 manzanas es un cambio de 4.76%?

• En todos los días, su participación total en frutas es exactamente 100. Existe una restricción de que la suma de las existencias es <= 100. No hay infracción, solo quiero confirmar.

Podemos configurarlo como un programa lineal de enteros, utilizando la rutina de optimización de enteros de ortools . No he usado un solucionador de ILP durante mucho tiempo, y creo que este es un poco escamoso (el indicador del solucionador.OPTIMA nunca parece ser cierto, incluso para los problemas con los juguetes. Además, el solucionador LP ortools no logra encontrar un óptimo solución en los casos en que scipy.linprog funciona sin problemas

h1,d = holdings in apples (number of apples) at end of day d
h2,d = holdings in pears at end of day d
h3,d = holdings in oranges at end of day d

Daré dos propuestas aquí, una que minimiza la norma l1 del error absoluto, la otra la norma l0 .

La solución l1 encuentra el mínimo de abs(h1,(d+1) - h1,d)/h1 + ... + abs(h3,(d+1) - h3,d)/h3) , esperando que la restricción que cada cambio relativo en las tenencias es inferior al 10% si la suma del cambio relativo en las tenencias se minimiza.

Lo único que impide que esto sea un programa lineal (aparte del requisito de enteros) es la función objetivo no lineal. No hay problema, podemos introducir variables de holgura y hacer que todo sea lineal. Para la formulación l1 , se introducen 6 variables de holgura adicionales, 2 por fruta y 6 restricciones de desigualdad adicionales. Para la formulación l0 , se introduce 1 variable de holgura y 6 restricciones de desigualdad adicionales.

Este es un proceso de dos pasos, por ejemplo, reemplazando | apples_new - apples_old | / | apples_old | con la variable | e |, y agregando restricciones de desigualdad para garantizar que e mide lo que nos gustaría. Entonces reemplazamos | e | con (e + - e-), cada uno de e +, e-> 0. Se puede mostrar que uno de e +, e- será 0, y que (e + + e-) es el valor absoluto de e. De esa forma, el par (e +, e-) puede representar un número positivo o negativo. Cosas estándar, pero eso agrega un montón de variables y restricciones. Puedo explicar esto con un poco más de detalle si es necesario.

import numpy as np
from ortools.linear_solver import pywraplp


def fruit_basket_l1_ortools():

    UPPER_BOUND = 1000

    prices = [[2,3,5],
              [1,2,4],
              [1,2,3]]

    holdings = [20,43,37]

    values = [348, 251, 213]

    for day in range(len(values)):

        solver = pywraplp.Solver(''ILPSolver'',
                                  pywraplp.Solver.BOP_INTEGER_PROGRAMMING)
        # solver = pywraplp.Solver(''ILPSolver'',
        #                          pywraplp.Solver.CLP_LINEAR_PROGRAMMING)


        c = ([1,1] * 3) + [0,0,0]

        price = prices[day]
        value = values[day]

        A_eq = [[ 0,  0, 0,  0, 0,  0, price[0], price[1], price[2]]]

        b_eq = [value]

        A_ub = [[-1*holdings[0], 1*holdings[0],              0,             0,              0,              0,  1.0,    0,    0],
                [-1*holdings[0], 1*holdings[0],              0,             0,              0,              0, -1.0,    0,    0],
                [             0,             0, -1*holdings[1], 1*holdings[1],              0,              0,    0,  1.0,    0],
                [             0,             0, -1*holdings[1], 1*holdings[1],              0,              0,    0, -1.0,    0],
                [             0,             0,              0,              0, -1*holdings[2], 1*holdings[2],    0,    0,  1.0],
                [             0,             0,              0,              0, -1*holdings[2], 1*holdings[2],    0,    0, -1.0]]

        b_ub = [1*holdings[0], -1*holdings[0], 1*holdings[1], -1*holdings[1], 1*holdings[2], -1*holdings[2]]

        num_vars             = len(c)
        num_ineq_constraints = len(A_ub)
        num_eq_constraints   = len(A_eq)                

        data = [[]] * num_vars

        data[0]  = solver.IntVar(           0, UPPER_BOUND, ''e1_p'')
        data[1]  = solver.IntVar(           0, UPPER_BOUND, ''e1_n'')
        data[2]  = solver.IntVar(           0, UPPER_BOUND, ''e2_p'')
        data[3]  = solver.IntVar(           0, UPPER_BOUND, ''e2_n'')
        data[4]  = solver.IntVar(           0, UPPER_BOUND, ''e3_p'')
        data[5]  = solver.IntVar(           0, UPPER_BOUND, ''e3_n'')
        data[6]  = solver.IntVar(           0, UPPER_BOUND, ''x1'')
        data[7]  = solver.IntVar(           0, UPPER_BOUND, ''x2'')
        data[8]  = solver.IntVar(           0, UPPER_BOUND, ''x3'')

        constraints = [0] * (len(A_ub) + len(b_eq))

        # Inequality constraints
        for i in range(0,num_ineq_constraints):
            constraints[i] = solver.Constraint(-solver.infinity(), b_ub[i])
            for j in range(0,num_vars):
                constraints[i].SetCoefficient(data[j], A_ub[i][j])

        # Equality constraints
        for i in range(num_ineq_constraints, num_ineq_constraints+num_eq_constraints):
            constraints[i] = solver.Constraint(b_eq[i-num_ineq_constraints], b_eq[i-num_ineq_constraints])
            for j in range(0,num_vars):
                constraints[i].SetCoefficient(data[j], A_eq[i-num_ineq_constraints][j])

        # Objective function
        objective = solver.Objective()
        for i in range(0,num_vars):
            objective.SetCoefficient(data[i], c[i])

        # Set up as minization problem
        objective.SetMinimization()

        # Solve it
        result_status = solver.Solve()

        solution_set = [data[i].solution_value() for i in range(len(data))]

        print(''DAY: {}''.format(day+1))
        print(''======'')
        print(''SOLUTION FEASIBLE: {}''.format(solver.FEASIBLE))
        print(''SOLUTION OPTIMAL:  {}''.format(solver.OPTIMAL))
        print(''VALUE OF BASKET:   {}''.format(np.dot(A_eq[0], solution_set)))
        print(''SOLUTION   (apples,pears,oranges): {!r}''.format(solution_set[-3:]))
        print(''PCT CHANGE (apples,pears,oranges): {!r}/n/n''.format([round(100*(x-y)/y,2) for x,y in zip(solution_set[-3:], holdings)]))

        # Update holdings for the next day
        holdings = solution_set[-3:]

Una sola carrera da:

DAY: 1
======
SOLUTION FEASIBLE: 1
SOLUTION OPTIMAL:  0
VALUE OF BASKET:   348.0
SOLUTION   (apples,pears,oranges): [20.0, 41.0, 37.0]
PCT CHANGE (apples,pears,oranges): [0.0, -4.65, 0.0]


DAY: 2
======
SOLUTION FEASIBLE: 1
SOLUTION OPTIMAL:  0
VALUE OF BASKET:   251.0
SOLUTION   (apples,pears,oranges): [21.0, 41.0, 37.0]
PCT CHANGE (apples,pears,oranges): [5.0, 0.0, 0.0]


DAY: 3
======
SOLUTION FEASIBLE: 1
SOLUTION OPTIMAL:  0
VALUE OF BASKET:   213.0
SOLUTION   (apples,pears,oranges): [20.0, 41.0, 37.0]
PCT CHANGE (apples,pears,oranges): [-4.76, 0.0, 0.0]

También se presenta la formulación l0 :

def fruit_basket_l0_ortools():

    UPPER_BOUND = 1000

    prices = [[2,3,5],
              [1,2,4],
              [1,2,3]]

    holdings = [20,43,37]

    values = [348, 251, 213]

    for day in range(len(values)):

        solver = pywraplp.Solver(''ILPSolver'',
                                  pywraplp.Solver.BOP_INTEGER_PROGRAMMING)
        # solver = pywraplp.Solver(''ILPSolver'',
        #                          pywraplp.Solver.CLP_LINEAR_PROGRAMMING)

        c = [1, 0, 0, 0]

        price = prices[day]
        value = values[day]

        A_eq = [[0, price[0], price[1], price[2]]]

        b_eq = [value]

        A_ub = [[-1*holdings[0],  1.0,    0,    0],
                [-1*holdings[0], -1.0,    0,    0],
                [-1*holdings[1],    0,  1.0,    0],
                [-1*holdings[1],    0, -1.0,    0],
                [-1*holdings[2],    0,    0,  1.0],
                [-1*holdings[2],    0,    0, -1.0]]


        b_ub = [holdings[0], -1*holdings[0], holdings[1], -1*holdings[1], holdings[2], -1*holdings[2]]


        num_vars             = len(c)
        num_ineq_constraints = len(A_ub)
        num_eq_constraints   = len(A_eq)                

        data = [[]] * num_vars

        data[0]  = solver.IntVar(-UPPER_BOUND, UPPER_BOUND, ''e'' )
        data[1]  = solver.IntVar(           0, UPPER_BOUND, ''x1'')
        data[2]  = solver.IntVar(           0, UPPER_BOUND, ''x2'')
        data[3]  = solver.IntVar(           0, UPPER_BOUND, ''x3'')

        constraints = [0] * (len(A_ub) + len(b_eq))

        # Inequality constraints
        for i in range(0,num_ineq_constraints):
            constraints[i] = solver.Constraint(-solver.infinity(), b_ub[i])
            for j in range(0,num_vars):
                constraints[i].SetCoefficient(data[j], A_ub[i][j])

        # Equality constraints
        for i in range(num_ineq_constraints, num_ineq_constraints+num_eq_constraints):
            constraints[i] = solver.Constraint(int(b_eq[i-num_ineq_constraints]), b_eq[i-num_ineq_constraints])
            for j in range(0,num_vars):
                constraints[i].SetCoefficient(data[j], A_eq[i-num_ineq_constraints][j])

        # Objective function
        objective = solver.Objective()
        for i in range(0,num_vars):
            objective.SetCoefficient(data[i], c[i])

        # Set up as minization problem
        objective.SetMinimization()

        # Solve it
        result_status = solver.Solve()

        solution_set = [data[i].solution_value() for i in range(len(data))]

        print(''DAY: {}''.format(day+1))
        print(''======'')
        print(''SOLUTION FEASIBLE: {}''.format(solver.FEASIBLE))
        print(''SOLUTION OPTIMAL:  {}''.format(solver.OPTIMAL))
        print(''VALUE OF BASKET:   {}''.format(np.dot(A_eq[0], solution_set)))
        print(''SOLUTION   (apples,pears,oranges): {!r}''.format(solution_set[-3:]))
        print(''PCT CHANGE (apples,pears,oranges): {!r}/n/n''.format([round(100*(x-y)/y,2) for x,y in zip(solution_set[-3:], holdings)]))

        # Update holdings for the next day
        holdings = solution_set[-3:]

Una sola carrera de esto da

DAY: 1
======
SOLUTION FEASIBLE: 1
SOLUTION OPTIMAL:  0
VALUE OF BASKET:   348.0
SOLUTION   (apples,pears,oranges): [33.0, 79.0, 9.0]
PCT CHANGE (apples,pears,oranges): [65.0, 83.72, -75.68]


DAY: 2
======
SOLUTION FEASIBLE: 1
SOLUTION OPTIMAL:  0
VALUE OF BASKET:   251.0
SOLUTION   (apples,pears,oranges): [49.0, 83.0, 9.0]
PCT CHANGE (apples,pears,oranges): [48.48, 5.06, 0.0]


DAY: 3
======
SOLUTION FEASIBLE: 1
SOLUTION OPTIMAL:  0
VALUE OF BASKET:   213.0
SOLUTION   (apples,pears,oranges): [51.0, 63.0, 12.0]
PCT CHANGE (apples,pears,oranges): [4.08, -24.1, 33.33]

Resumen

La formulación l1 da resultados más sensibles, menor rotación, mucho menor. Sin embargo, la comprobación de optimalidad falla en todas las ejecuciones, lo cual es preocupante. Incluí también un solucionador lineal y eso falla el control de factibilidad de alguna manera, no sé por qué. La gente de Google proporciona muy poca documentación para la liberación de ortools, y la mayor parte es para la liberación de C ++. Pero la formulación l1 puede ser una solución a su problema, que puede escalar. En general, ILP es NP-completo, y lo más probable es su problema.

Además, ¿existe una solución el día 2? ¿Cómo define el% de cambio para que lo haga en su gráfico anterior? Si supiera que podría volver a plantear las desigualdades anteriores y tendríamos la solución general.

Answer 2

Problema de encuadre

Este problema puede ser descrito como un problema de optimización combinatoria . Está intentando encontrar un objeto óptimo (una combinación de artículos de fruta) de un conjunto finito de objetos (todas las combinaciones posibles de artículos de fruta). Con la analogía y las transformaciones adecuadas, podemos reducir este problema de la canasta de frutas al problema de mochila bien conocido y ampliamente estudiado (desde 1897).

Resolver esta clase de problemas de optimización es NP-hard . El problema de decisión de responder "¿Podemos encontrar una combinación de artículos de fruta con un valor de X?" es NP-complete . Ya que desea tener en cuenta el peor de los casos cuando tiene miles de artículos de fruta, lo mejor es usar una metaheuristic , como el cálculo evolutivo .

Solución propuesta

La computación evolutiva es una familia de metaheurísticas de inspiración biológica. Trabajan revisando y mezclando (evolucionando) las soluciones candidatas más adecuadas basadas en una función de aptitud y descartando las menos adecuadas en muchas iteraciones. Cuanto mayor sea la idoneidad de una solución, es más probable que reproduzca soluciones similares y sobreviva a la siguiente generación (iteración). Eventualmente, se encuentra una solución óptima local o global.

Estos métodos proporcionan un compromiso necesario cuando el espacio de búsqueda es demasiado grande para cubrir con las soluciones matemáticas tradicionales de forma cerrada. Debido a la naturaleza estocástica de estos algoritmos, diferentes ejecuciones de los algoritmos pueden llevar a diferentes óptimos locales, y no hay garantía de que se encuentre el óptimo global. Las probabilidades son buenas en nuestro caso, ya que tenemos varias soluciones válidas.

Ejemplo

Usemos el marco de algoritmos evolutivos distribuidos en Python (DEAP) y adaptemos su ejemplo de problema de Knapsack a nuestro problema. En el código a continuación aplicamos una fuerte penalización para canastas con más de 100 artículos. Esto reducirá severamente su condición física y los sacará del grupo de la población en una o dos generaciones. Hay otras formas de manejar las restricciones que también son válidas.

#    This file is part of DEAP.
#
#    DEAP is free software: you can redistribute it and/or modify
#    it under the terms of the GNU Lesser General Public License as
#    published by the Free Software Foundation, either version 3 of
#    the License, or (at your option) any later version.
#
#    DEAP is distributed in the hope that it will be useful,
#    but WITHOUT ANY WARRANTY; without even the implied warranty of
#    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
#    GNU Lesser General Public License for more details.
#
#    You should have received a copy of the GNU Lesser General Public
#    License along with DEAP. If not, see <http://www.gnu.org/licenses/>.

import random

import numpy as np

from deap import algorithms
from deap import base
from deap import creator
from deap import tools

IND_INIT_SIZE = 5 # Calls to `individual` function
MAX_ITEM = 100   # Max 100 fruit items in basket
NBR_ITEMS = 50   # Start with 50 items in basket
FRUIT_TYPES = 10 # Number of fruit types (apples, bananas, ...)

# Generate a dictionary of random fruit prices.
fruit_price = {i: random.randint(1, 5)  for i in range(FRUIT_TYPES)}

# Create fruit items dictionary.  The key is item ID, and the 
# value is a (weight, price) tuple.  Weight is always 1 here.
items = {}
# Create random items and store them in the items'' dictionary.
for i in range(NBR_ITEMS):
    items[i] = (1, fruit_price[i])

# Create fitness function and an individual (solution candidate)
# A solution candidate in our case is a collection of fruit items.
creator.create("Fitness", base.Fitness, weights=(-1.0, 1.0))
creator.create("Individual", set, fitness=creator.Fitness)

toolbox = base.Toolbox()

# Randomly initialize the population (a set of candidate solutions)
toolbox.register("attr_item", random.randrange, NBR_ITEMS)
toolbox.register("individual", tools.initRepeat, creator.Individual, 
toolbox.attr_item, IND_INIT_SIZE)


def evalBasket(individual):
    """Evaluate the value of the basket and
    apply constraints penalty.
    """
    value = 0 # Total value of the basket
    for item in individual:
        value += items[item][1]

    # Heavily penalize baskets with 100+ items
    if len(individual) > MAX_ITEM:
        return 10000, 0
    return len(individual), value  # (items in basket, value of basket)


def cxSet(ind1, ind2):
    """Apply a crossover operation on input sets.
    The first child is the intersection of the two sets,
    the second child is the difference of the two sets.
    This is one way to evolve new candidate solutions from
    existing ones.  Think of it as parents mixing their genes
    to produce a child.
    """
    temp = set(ind1)                # Used in order to keep type
    ind1 &= ind2                    # Intersection (inplace)
    ind2 ^= temp                    # Symmetric Difference (inplace)
    return ind1, ind2


def mutSet(individual):
    """Mutation that pops or add an element.
    In nature, gene mutations help offspring express new traits
    not found in their ancestors.  That could be beneficial or 
    harmful.  Survival of the fittest at play here.
    """
    if random.random() < 0.5:  # 50% chance of mutation
        if len(individual) > 0:
            individual.remove(random.choice(sorted(tuple(individual))))
    else:
        individual.add(random.randrange(NBR_ITEMS))
    return individual,

# Register evaluation, mating, mutation and selection functions
# so the framework can use them to run the simulation.
toolbox.register("evaluate", evalKnapsack)
toolbox.register("mate", cxSet)
toolbox.register("mutate", mutSet)
toolbox.register("select", tools.selNSGA2)


def main():
    random.seed(64)
    NGEN = 50
    MU = 50
    LAMBDA = 100
    CXPB = 0.7
    MUTPB = 0.2

    pop = toolbox.population(n=MU)  # Initial population size
    hof = tools.ParetoFront()    # Using Pareto front to rank fitness

    # Keep track of population fitness stats which should 
    # improve over generations (iterations).
    stats = tools.Statistics(lambda ind: ind.fitness.values)
    stats.register("avg", numpy.mean, axis=0)
    stats.register("std", numpy.std, axis=0)
    stats.register("min", numpy.min, axis=0)
    stats.register("max", numpy.max, axis=0)

    algorithms.eaMuPlusLambda(pop, toolbox, MU,LAMBDA,/
                              CXPB, MUTPB, NGEN, stats,/
                              halloffame=hof)
    return pop, stats, hof


if __name__ == "__main__":
    main()   

Answer 3

Me parece que su enfoque es razonable, pero si depende del tamaño de los números en el juego real. Aquí hay una implementación completa que es mucho más eficiente que la suya (pero aún tiene mucho margen de mejora). Mantiene una lista de posibilidades para el día anterior y, luego, filtra las cantidades del día actual a aquellas que se encuentran dentro del 5% de alguna posibilidad del día anterior, y las imprime por día.

def possibilities(value, prices):
    for i in range(0, value+1, prices[0]):
        for j in range(0, value+1-i, prices[1]):
            k = value - i - j
            if k % prices[2] == 0:
                yield i//prices[0], j//prices[1], k//prices[2]

def merge_totals(last, this, r):
    ok = []
    for t in this:
        for l in last:
            f = int(sum(l) * r)
            if all(l[i] -f <= t[i] <= l[i] + f for i in range(len(l))):
                ok.append(t)
                break
    return ok

days = [
    (26, (1, 2, 3)),
    (51, (2, 3, 4)),
    (61, (2, 4, 5)),
]

ps = None
for i, d in enumerate(days):
    new_ps = list(possibilities(*d))
    if ps is None:
        ps = new_ps
    ps = merge_totals(ps, new_ps, 0.05)

    print(''Day %d'' % (i+1))
    for p in ps:
        print(''apples: %s, pears: %s, oranges: %s'' % p)
    print

Answer 4

No es una respuesta, sino un intento de hacer que la información sobre lo que se supone que significa "% de cambio" (suma de cambio en el recuento de cada elemento calculado al revés ) sea más accesible para los no creyentes en montones de píxeles:

| Day 1 ! Day 2 change ! Day 3 change ! Day 4 change |$/1| # | $ !$/1| # | % | $ !$/1| # | % | $ !$/1| # | % | $ Apples | 1 | 20 | 20 ! 2 | 21 | 4.76 | 42 ! 1 | 21 | 0 | 21 ! 1 | 22 | 4.55 | 22 Pears | 2 | 43 | 86 ! 3 | 42 | 2.38 | 126 ! 2 | 43 | 2.33 | 86 ! 2 | 43 | 0 | 86 Oranges| 3 | 37 | 111 ! 5 | 36 | 2.78 | 180 ! 4 | 36 | 0 | 144 ! 3 | 35 | 2.86 | 105 Total | 100 | 217 ! 100 | 9.92 | 348 ! 100 | 2.33 | 251 ! 100 | 7.40 | 213

Answer 5

Odio decepcionarte, pero realmente no creo que una red neuronal ayude en absoluto para este problema, y ​​en mi opinión, la mejor respuesta a tu pregunta es el consejo "no pierdas el tiempo probando redes neuronales".

Una regla de oro fácil para decidir si las redes neuronales son o no aplicables es pensar, "¿puede un humano adulto promedio resolver este problema razonablemente bien en unos pocos segundos?" Para problemas como "qué hay en esta imagen", "responder a esta pregunta" o "transcribir este clip de audio", la respuesta es sí . Pero para tu problema, la respuesta es un no definitivo.

Las redes neuronales tienen limitaciones, y una de ellas es que no resuelven bien los problemas altamente lógicos. Esto se debe a que las respuestas generalmente no son "suaves". Si toma una imagen y cambia ligeramente unos pocos píxeles, el contenido de la imagen sigue siendo el mismo. Si toma un clip de audio e inserta unos pocos milisegundos de ruido, es probable que una red neuronal aún pueda averiguar lo que se dice. Pero en su problema, cambie el "valor total de la canasta" de un solo día en solo 1 unidad, y sus respuestas cambiarán drásticamente.

Parece que la única forma de resolver su problema es con un enfoque algorítmico "clásico". Como se indica actualmente, puede que no haya ningún algoritmo mejor que la fuerza bruta, y puede que no sea posible descartar mucho. Por ejemplo, ¿qué pasa si todos los días tiene la propiedad de que todas las frutas tienen el mismo precio? El recuento de cada fruta puede variar, siempre que el número total de frutas sea fijo, por lo que la cantidad de posibilidades es todavía exponencial en la cantidad de frutas. Si su objetivo es "producir una lista de posibilidades", entonces ningún algoritmo puede ser mejor que el tiempo exponencial, ya que esta lista puede ser exponencialmente grande en algunos casos.

Es interesante que parte de su problema se pueda reducir a un programa lineal entero (ILP). Considere un solo día, donde se le da el total de la canasta B y el costo de cada fruta c_i , para i=1 hasta i=n (si n es el número total de frutas distintas). Digamos que los precios son altos, por lo que no es obvio que pueda "llenar" la canasta con frutas de costo unitario. Puede ser difícil en esta situación encontrar una sola solución. Formulado como un ILP, esto es equivalente a encontrar valores enteros de x_i tal que:

sum_i (x_i*c_i) = x_1*c_1 + x_2*c_2 + ... + x_n*c_n = B

y x_i >= 0 para todos 1 <= i <= n (no puede tener frutos negativos), y sum_i x_i <= 100 (puede tener como máximo 100 frutos).

La buena noticia es que existen solucionadores de ILP decentes: solo puede entregar las fórmulas anteriores y el solucionador hará todo lo posible para encontrar una solución única. Incluso puede agregar una "función objetivo" que el solucionador maximizará o minimizará: minimizar sum_i x_i tiene el efecto de minimizar el número total de frutas en la canasta. La mala noticia es que la ILP está completa en NP, por lo que casi no hay esperanza de encontrar una solución eficiente para un gran número de frutas (lo que equivale al número de variables x_i ).

Creo que el mejor enfoque es probar el enfoque ILP, pero también introducir algunas restricciones más en el escenario. Por ejemplo, ¿qué pasaría si todas las frutas tuvieran un costo de número primo diferente? Esto tiene la buena propiedad de que si encuentra una solución, puede enumerar un montón de otras soluciones relacionadas. Si una manzana cuesta m y una naranja cuesta n , donde m y n son primos relativos, entonces puede "intercambiar" n*x manzanas por m*x naranjas sin cambiar el total de la canasta, por cualquier entero x>0 (siempre que tienes suficientes manzanas y naranjas para empezar). Si elige que todas las frutas tengan diferentes costos de números primos, entonces todos los costos serán relativamente primos por pares. Creo que este enfoque dará como resultado relativamente pocas soluciones para un día determinado.

También puede considerar otras restricciones, como "no puede haber más de 5 frutas de un solo tipo en la canasta" (agregue la restricción x_i <= 5 ), o "puede haber como máximo 5 clases distintas de frutas en la cesta "(pero esto es más difícil de codificar como una restricción ILP). Agregar este tipo de restricciones facilitará que el solucionador de ILP encuentre una solución.

Por supuesto, la discusión anterior se enfoca en un solo día, y usted tiene datos de varios días. Si la parte más difícil del problema es encontrar una solución para cualquier día (lo que sucede si sus precios son altos), entonces usar un solucionador de ILP le dará un gran impulso. Si las soluciones son fáciles de encontrar (lo que sucede si tiene una fruta de muy bajo costo que puede "llenar" su canasta), y la parte más difícil del problema es encontrar soluciones que sean "consistentes" en varios días, luego El enfoque ILP podría no ser el mejor ajuste, y en general este problema parece mucho más difícil de razonar.

Edición: y como se menciona en los comentarios, para algunas interpretaciones de la restricción de "10% de cambio", incluso puede codificar todo el problema de varios días como un ILP.

Answer 6

Tienes un problema lógico en enteros, no un problema de representación . Las redes neuronales son relevantes para problemas con representaciones complejas (por ejemplo, imágenes con píxeles, objetos en diferentes formas y colores, a veces ocultos, etc.), ya que crean su propio conjunto de características (descriptores) y mipmaps; también son una buena combinación de problemas relacionados con reales, no con enteros; y por último, como están hoy, no tratan realmente con el razonamiento y la lógica, o eventualmente con lógica simple como una pequeña sucesión de if/else o switch pero realmente no tenemos control sobre eso.

Lo que veo está más cerca de un problema criptográfico con restricciones (10% de cambio, máximo 100 artículos).

Solución para todos los conjuntos de frutas.

Hay una manera de llegar a todas las soluciones muy rápidamente. Comenzamos por factorizar en primos el total, luego encontramos pocas soluciones a través de la fuerza bruta. Desde allí podemos cambiar el conjunto de frutas con igual total. Por ejemplo, intercambiamos 1 naranja por 1 manzana y 1 pera con precios = (1,2,3). De esta manera podemos navegar a través de soluciones sin tener que pasar por la fuerza bruta.

Algoritmo (s): factoriza en números primos el total, luego los divide en dos o más grupos; tomemos 2 grupos: sea A un multiplicador común y B sea el otro (s). Luego puedes agregar tus frutas para alcanzar el total de B.

Ejemplos:

Día 1: Manzana = 1, Peras = 2, Naranjas = 3, Valor de la canasta = 217

Día 2: Manzana = 2, Peras = 3, Naranjas = 5, Valor de la canasta = 348

• 217 factoriza en [7, 31], seleccionamos 31 como A (multiplicador común), luego digamos 7 = 3 * 2 + 1 (2 naranja, 0 pera, 1 manzana), obtuviste una respuesta: 62 naranjas, 0 peras , 31 manzanas. 62 + 31 <100: válido.

• 348 factoriza en [2, 2, 3, 29], tiene varias formas de agrupar sus factores y multiplicar sus frutos dentro de este. El multiplicador puede ser 29, (o 2 * 29, etc.), luego escoges tus frutos para alcanzar 12. Digamos que 12 = 2 * 2 + 3 + 5. Tienes (2 manzanas, 1 pera, 1 naranja) * 29, pero son más de 100 artículos. Puede fusionar recursivamente 1 manzana y 1 pera en 1 naranja hasta que esté por debajo de 100 artículos, o puede ir directamente con la solución con un mínimo de artículos: (2 naranjas, 1 manzana) * 29 = (58 naranjas, 29 manzanas) . Y por ultimo:

  - 87 <100 válidos;

  - el cambio es (-4 naranjas, -2 manzanas), 6/93 = 6.45% <10% de cambio: válido.

Código

Observación: no hay implementación de la variación del 10%.

Nota: no implementé el proceso de "intercambio de fruta" que permite la "navegación de la solución"

Ejecute con python -O solution.py para optimizar y eliminar los mensajes de depuración.

def prime_factors(n):
    i = 2
    factors = []
    while i * i <= n:
        if n % i:
            i += 1
        else:
            n //= i
            factors.append(i)
    if n > 1:
        factors.append(n)
    return factors

def possibilities(value, prices):
    for i in range(0, value + 1, prices[0]):
        for j in range(0, value + 1-i, prices[1]):
            k = value - i - j
            if k % prices[2] == 0:
                yield i//prices[0], j//prices[1], k//prices[2]

days = [
    (217, (1, 2, 3)),
    (348, (2, 3, 5)),
    (251, (1, 2, 4)),
    (213, (1, 2, 3)),
]

for set in days:
    total = set[0]
    (priceApple, pricePear, priceOrange) = set[1]

    factors = prime_factors(total)
    if __debug__:
        print(str(total) + " -> " + str(factors))

    # remove small article to help factorize (odd helper)
    evenHelper = False
    if len(factors) == 1 :
        evenHelper = True
        t1 = total - priceApple
        factors = prime_factors(t1)
        if __debug__:
            print(str(total) + " --> " + str(factors))

    # merge factors on left
    while factors[0] < priceOrange :
        factors = [factors[0] * factors[1]] + factors[2:]
        if __debug__:
            print("merging: " + str(factors))

    # merge factors on right
    if len(factors) > 2:
        multiplier = 1
        for f in factors[1:]:
            multiplier *= f
        factors = [factors[0]] + [multiplier]

    (smallTotal, multiplier) = factors
    if __debug__:
        print("final factors: " + str(smallTotal) + " (small total) , " + str(multiplier) + " (multiplier)")

    # solutions satisfying #<100
    smallMax = 100 / multiplier
    solutions = [o for o in possibilities(smallTotal, set[1]) if sum(o) < smallMax ]
    for solution in solutions:
        (a,p,o) = [i * multiplier for i in solution]

        # if we used it, we need to add back the odd helper to reach the actual solution
        if evenHelper:
            a += 1

        print(str(a) + " apple(s), " + str(p) + " pear(s), " + str(o) + " orange(s)")


    # separating solutions
    print()

Programé el programa con un total de 10037 con precios (5, 8, 17) y un máximo de 500 artículos: se trata de 2 ms (en i7 6700k). El proceso de "navegación de la solución" es muy simple y no debería agregar un tiempo significativo.

Puede haber una heurística para ir día a día sin tener que hacer el proceso de validación de factorización + navegación +. Lo pensare.

Answer 7

Sé que es un poco tarde, pero pensé que era un problema interesante y que también podría agregar mis dos centavos.

Mi código:

import math

prices = [1, 2, 3]
basketVal = 217
maxFruits = 100
numFruits = len(prices)


## Get the possible baskets
def getPossibleBaskets(maxFruits, numFruits, basketVal, prices):

    possBaskets = []
    for i in range(101):
        for j in range(101):
            for k in range(101):

              if i + j + k > 100:
                  pass
              else:

                  possibleBasketVal = 0
                  for m in range(numFruits):
                      possibleBasketVal += (prices[m] * [i, j, k][m])

                      if possibleBasketVal > basketVal:
                          break

                  if possibleBasketVal == basketVal:
                      possBaskets.append([i, j, k])

    return possBaskets


firstDayBaskets = getPossibleBaskets(maxFruits, numFruits, basketVal, prices)
## Compare the baskets for percentage change and filter out the values
while True:

    prices = list(map(int, input("New Prices:/t").split()))
    basketVal = int(input("New Basket Value:/t"))
    maxFruits = int(input("Max Fruits:/t"))
    numFruits = len(prices)

    secondDayBaskets = getPossibleBaskets(maxFruits, numFruits, basketVal, prices)

    possBaskets = []
    for basket in firstDayBaskets:
        for newBasket in secondDayBaskets:
            if newBasket not in possBaskets:
                percentChange = 0
                for n in range(numFruits):
                    percentChange += (abs(basket[n] - newBasket[n]) / 100)
                if percentChange <= 10:
                    possBaskets.append(newBasket)

    firstDayBaskets = possBaskets
    secondDayBaskets = []

    print(firstDayBaskets)

Supongo que esto podría llamarse una solución de fuerza bruta, pero definitivamente funciona. Todos los días, se imprimirán las posibles configuraciones de la cesta.