repeticion pueden permutaciones permutacion palabras palabra matematica formar definicion cuantos con combinatoria combinaciones anagramas algorithm search genetic-algorithm evolutionary-algorithm

algorithm - pueden - permutaciones en r



Programación de trabajos de permutación con máquinas disponibles parcialmente (2)

Estoy buscando un algoritmo adecuado para resolver un problema de programación de tiempo. Primero esbozaré el problema en sí, luego en una segunda parte daré la dirección hacia la que estaba pensando para encontrar una solución. Estoy tratando de resolver este problema porque tengo un interés en este tipo de problemas y también porque el mismo tipo de problema se puede resolver más tarde con más variables y una configuración más grande.

problema

Me gustaría hacer algunas pruebas con baterías para ver cómo responden cuando están conectadas a una carga. Y realice estas pruebas en el menor tiempo posible para completar todas las pruebas. Las dos variables importantes aquí son:

  • Estado de carga (SoC) la cantidad de energía que queda en la batería de 100% a 0%. Probaremos el 99%, 75%, 50% y 25% (4 variaciones). (explicado más adelante por qué el 99% y no el 100%). Asumiremos que el SoC perdido cuando la relajación es 0.
  • Relajación de la cantidad de la batería se ha relajado en horas. Sabemos que teóricamente las 24 horas deberían ser suficientes, así que este es el máximo. Probamos diferentes momentos como: 5 minutos, 15 minutos, 30 minutos, 1 hora, 2 horas, 6 horas, 24 horas (7 variaciones).

Combinaciones totales: 4 x 7 = 28 para una batería

El orden en que debe proceder la prueba es el siguiente: cargue al 100%, descargue el SoC deseado, relájese, descargue a un SoC nuevo mientras mide

Ejemplo: queremos ver cómo reacciona la batería mientras se descarga del 75% al ​​50% mientras se relaja durante 2 horas

  1. La batería tiene SoC desconocido (los métodos de medición no son lo suficientemente precisos)
  2. Recargue al 100%
  3. Descargue al 75%
  4. Relájate 2 horas
  5. Descargue mientras mide, pare en 50%

La batería ahora puede relajarse nuevamente y comenzar su medición del 50% al 25%. NO tiene que recargarse al 100% nuevamente.

situaciones / estados

Ahora describiré algunas situaciones que pueden ocurrir y lo que se debe hacer en tal caso.

inicialización

El problema se puede inicializar con pruebas ya realizadas (esto es importante porque es posible que desee reprogramar a la mitad). Si las baterías tienen un estado conocido (SoC / relax) podemos usar eso. Si el SoC es desconocido, entonces la batería debe ser recargada. Si se desconoce la relajación pero se conoce el SoC, la batería debe relajarse durante al menos 24 horas.

recargar

Poner la batería en el recargador debe hacerse manualmente. Dejar la batería en el cargador no es un problema. La recarga demora alrededor de 2.5 horas. Cada batería tiene su propio cargador dedicado, pero en el futuro podríamos tener más baterías que cargadores, por lo que el algoritmo debe poder tomar una cantidad variable de cargadores.

relajación (relax)

La relajación se puede hacer simplemente sin conectar la batería a nada, por lo que no necesita ningún equipo especial. Antes de que pueda comenzar el período de relajación, la batería debe estar bajo tensión (= conectada al descargador). No sabemos con certeza cuánto durará el período de estrés, pero suponemos que bastará con el período de descarga del 1%. El 99% será el primer SoC en el que podamos determinar con precisión el tiempo de relajación.

descarga

Solo hay un descargador en este momento, pero el algoritmo debería poder tomar una cantidad variable de descargadores. Poner la batería en el descargador tiene que hacerse manualmente (también sacarlo). SIN EMBARGO, poner la batería en el descargador no necesariamente descarga la batería de inmediato. Se puede configurar un tiempo para que comience en un momento determinado. Y el descargador puede detenerse automáticamente cuando se haya descargado suficiente energía. Se puede estimar una estimación del tiempo de descarga a partir de una tabla de búsqueda. Esto no es lineal, por lo que el 75% al ​​50% no tiene que tomar la misma cantidad de tiempo que el 25% al ​​0%. La búsqueda es bastante precisa (alrededor de 5 minutos de diferencia en 2,5 horas).

esperando

La batería puede esperar si se toman todos los descargadores, pero esperar un descargador aumenta el tiempo de relajación. Entonces, si el tiempo de relajación es mayor que el tiempo de relajación necesario para las mediciones que deben realizarse, entonces tiene que descargarse a un nivel más bajo de carga y relajarse nuevamente, o tiene que volver a cargarse.
La batería puede esperar si todos los cargadores se toman de forma segura, no hay penalización / desventaja aquí, otros pierden algo de tiempo para tener que esperar.

restricciones

Las cosas que tienen que hacerse manualmente solo se pueden hacer durante el horario de oficina (de lunes a viernes de 8:30 a 17:00). Entonces, por ejemplo, poner la batería en el descargador debe hacerse manualmente. Luego, a una hora determinada de la noche (después de que la batería se haya relajado lo suficiente), el descargador se puede iniciar con un temporizador, y a la mañana siguiente, cuando llegue a la oficina, la batería se puede colocar en el cargador.

pensamientos para una solución

No estoy seguro si estoy pensando en la dirección correcta aquí, porque todavía no tengo la solución de trabajo. Entonces, cualquier cosa en la parte podría estar equivocada.

La secuencia de tareas es importante porque una secuencia diferente puede introducir más o menos tiempo de espera y luego otra secuencia. Entonces, para una sola batería con 28 pruebas, ¡será una permutación de 28! que es un número bastante grande. Por lo tanto, no es posible realizar una búsqueda exhaustiva del espacio problemático. El único tipo de algoritmo que sé que puede dar un resultado bastante bueno en este tipo de problemas es el algoritmo genético. Aunque con todas las limitaciones y posibilidades, no puedo usar un algoritmo genético clásico. He leído algunos artículos (de investigación) y, finalmente, la descripción del problema de programación de Permutation Flowshop (PFSP) fue la que más resonó (varias fuentes). Aunque el mencionado Problema de Programación de Compras Extendidas (EJSSP) aquí también fue interesante.

El mayor problema que veo es la restricción de horas de oficina. Si no fuera por eso, la programación podría ser similar a colocar bloques en ranuras de tiempo (aunque las ranuras serían de tamaño dinámico). No estoy seguro de cuál es la mejor manera de lidiar con esta restricción. O podría modelar las máquinas (descargador) como dos máquinas separadas que están activas en diferentes momentos, o podría introducir trabajos falsos para que las máquinas no puedan ser tomadas por los trabajos normales.

Esto es solo una especulación en este punto, debido a mi falta de experiencia. Soy más un programador pragmático que un académico y tengo un momento realmente difícil para descubrir cuáles de los posibles algoritmos son adecuados y cuáles son las advertencias. Estoy feliz de hacer la implementación, pero ahora mismo estoy atrapado en:

  1. qué algoritmos son adecuados para este tipo de problema?
  2. ¿Cómo establezco las condiciones especiales en los algoritmos?
  3. ¿Cómo puedo hacer una función de cruce / selección / mutación?
  4. ¿Necesito romper este problema en problemas secundarios e incorporar eso en un algoritmo más grande? ¿Qué sub-problemas son óptimos para resolver primero?
  5. ¿Cómo se vería el pseudo código?

Visión de conjunto

Aunque ha etiquetado explícitamente el evolutionary-algorithm , le sugiero que eche un vistazo a un conjunto de algoritmos resumidos bajo el nombre Programación dinámica aproximada (ADP). En mi opinión, un buen libro introductorio es el de Warren B. Powell. Contiene muchos de esos problemas de asignación de recursos, así como otras muchas cosas prácticas que a menudo se conocen con el nombre de Control óptimo (por ejemplo, controlar una empresa de camiones con varios miles de camiones).

Una ventaja que ADP tiene sobre la aplicación directa de algoritmos evolutivos, el recocido simulado, etc., es que no presenta un algoritmo específico, sino más bien un marco para modelar los problemas de decisión de Markov dependientes del tiempo. Dentro de este marco, uno es libre de emplear una variedad de algoritmos apropiados.

Para aplicar ADP, una clave es el modelo matemático correcto del problema dado. De importancia central es el state del sistema, las actions uno puede tomar en un estado determinado, así como el cost que requieren estas acciones y que uno quiere minimizar: sus costos aquí están dados por la duración de la prueba. Dado que uno ha construido un modelo apropiado, la tarea es (aproximadamente) resolver la ecuación de Bellman , para la cual existen varios algoritmos.

A continuación, daré un ejemplo de cómo se puede proceder aquí. Naturalmente, este no es un modelo listo para usar, ya que puede llevar bastante tiempo construirlo. De hecho, creo que este sería un problema excelente para un máster o incluso para una tesis doctoral. Sin embargo, trataré de mantenerlo exhaustivo en un primer paso, de modo que uno pueda introducir aproximaciones más adelante.

Modelando el estado de una sola batería

Primero vamos a configurar un modelo aproximado para una sola batería. Aquí es útil que su problema sea tan determinista como usted describió, es decir, que aquí no hay componentes estocásticos (por ejemplo, que todas las duraciones son fijas y no se extraen al azar de alguna distribución estadística).

  • Estado único: como escribió, una batería está dada por un estado

    S = {SoC, Relax} where SoC /in {UNKNOWN, 0%, 25%, 50%, 75%, 100%} and Relax /in {UNKNOWN, 0m, 5m, 15m, 30m, 1h, 2h, 6h, 24h}

    He agregado 0% y 0m por conveniencia, aunque tal vez no sean realmente necesarios aquí.

    Tenga en cuenta que ya he hecho una gran simplificación aquí, ya que el estado de carga también puede ser del 79% , por ejemplo. La suposición que justifica esto es la siguiente: una vez que comienza su experimento por primera vez (o también de nuevo después de un largo tiempo), todas las baterías están razonablemente en el estado {UNKNOWN,UNKNOWN} . Entonces, de acuerdo con su descripción, lo primero que tiene que hacer es hacer una recarga completa, que establece todo en el estado {100%,0m} (y que cuesta 2,5h ). A partir de aquí, uno solo realiza cambios de estado calificados : la descarga se realiza solo a SoC específicos, y la recarga solo al 100% (esto asumí en función de su descripción). Tenga en cuenta que esto se vuelve más difícil en un marco estocástico más natural, donde, por ejemplo, el SoC las baterías no es tan bueno.

  • Acciones y costos: para estados de batería única específicos, uno ha asociado un conjunto de acciones factibles (más sus costos correspondientes). Vamos a recogerlos en lo siguiente:

    State Possible Actions Cost ------------------------------------------------------------------------------- {UNKNOWN, Relax} -> RECHARGE TO {100%,0m} 2,5h {SoC, 0m} -> RELAX TO {SoC,5m}, 5m {SoC, Relax} -> RECHARGE TO {100%,0m}, 2,5h DISCARGE TO {SoC-1}, C(SoC, SoC-1) DISCHARGE-MEASURE TO {SoC-1}, C(SoC, SoC-1) RELAX TO {SoC, RELAX+1} C(Relax, Relax+1) {SoC, UNKNOWN} -> RECHARGE TO {100%,0m}, 2,5h DISCARGE TO {SOC-1,0m}, C(SoC,SoC-1) RELAX {SoC, 24h} 24h

    SoC-1 representa el siguiente estado factible, mientras que C(SoC, SoC-1) significa "tiempo para pasar de SoC a SoC-1, por ejemplo, de 75% a 50%. Es su turno aquí para consultar esta tabla si se encuentra con su modelo. Si no, debe corregirlo o ampliarlo.

    Tenga en cuenta que he vuelto a hacer una simplificación al permitir solo las transiciones al siguiente estado viable SoC-1 (por ejemplo, de 75% a 50%). Esto es razonable ya que el costo se asume como adicional. Por ejemplo, cuando pasa del 75% al ​​25%, se tarda el mismo tiempo que al principio en 50% y luego en 25%.

    Además, todas las acciones RECHARGE y DISCHARGE son factibles solo en el horario de oficina, lo que no se ha tenido en cuenta en la tabla anterior (pero que se debe incorporar más adelante en el modelo).

Combine lo anterior con un modelo del sistema completo

Ahora supongamos que tiene N baterías, recargadores M y descargadores K (donde podemos suponer que M<=N y K<=N ), todos los cuales son idénticos. Además, digamos que el objetivo es realizar cada prueba solo una vez.

  • Estado de prueba: el estado de prueba La prueba es un vector de dimensión 4*7 de 0 y 1 contiene la información de si ya se realizó una prueba específica. Tenga en cuenta que esto corresponde a 2^28 estados posibles, por lo que uno definitivamente tiene que introducir una aproximación aquí.

  • Estado de batería múltiple: el estado combinado de todas las baterías B es el producto cartesiano del estado de batería única, es decir, está en el espacio {SoC,Relax}^N Eso significa simplemente que uno debe considerar N estados de batería única.

    B={SoC_1, Relax_1}, ..., {SoC_N, Relax_N}

    De nuevo, el tamaño de este espacio va a ser un número muy grande para números moderados N

  • Tiempo de oficina: Además, necesitamos incorporar la hora del día T Al hacerlo exactamente, uno termina con una cantidad de 24*60m / 5m = 288 posibles ranuras de cinco minutos.

  • Acciones de varias baterías: de manera similar, las acciones de baterías múltiples están dadas por un producto cartesiano N -dimensional de las acciones unidimensionales. RECHARGE y DISCHARGE solo es factible para T en el horario laboral y si hay suficientes recargas y descargas disponibles (la suma de todas las RECHARGE / DISCHARGE no debe exceder M / K ).

Resumiendo, el estado completo S viene dado por la combinación

S = {Test, T, B}

La dimensión del espacio de estado es aproximadamente 2^28 * (6*9)^N * 288 que rápidamente se vuelve enorme.

Además, para cada estado hay un conjunto correspondiente de acciones permitidas que deberían estar claras por ahora.

Entonces, ahora que el modelo del sistema se ha especificado más o menos (¡corríjalo si es necesario!), Podemos continuar intentando resolverlo.

La ecuación de Bellman

La ecuación de Bellman es la ecuación central de la programación dinámica (aproximada). Para una buena introducción, eche un vistazo al libro de Sutton y Barto que está disponible gratuitamente en la red.

Su idea es bastante simple: para cada estado posible, introduzca una función de valor V(S) que le indique qué tan bueno es estar en el estado S. Esta función de valor contiene, en principio, el tiempo necesario para finalizar las pruebas una vez que se encuentre en estado S. Para determinar este valor para un problema de horizonte finito como este, uno comienza desde el estado final y recurre hasta el comienzo, es decir, al menos si el tamaño del problema lo permite. Pero hagámoslo esquemáticamente en lo que sigue y veamos:

El estado final es aquel en el que Test contiene solo unos, es decir, se han realizado las 28 pruebas. Configure V(S)=0 para todos estos estados (independientemente de T y del estado de batería múltiple), ya que no necesita más tiempo.

Un paso atrás : ahora considere todos los estados donde Test tiene solo 27 unidades y un cero, es decir, todavía se necesita realizar una prueba. Para cada posible estado de batería múltiple B y punto de tiempo T uno puede detectar automáticamente la alternativa más rápida. Establezca V(S) igual a este costo.

Otro paso atrás : el siguiente considera todos los estados donde Test tiene solo 26 unos y dos ceros (dos pruebas aún por realizar). Ahora, para cada posible estado de batería múltiple B y punto de tiempo T uno elige la acción a para minimizar el costo de la acción más el valor del estado al que conduce la acción. En términos, debe elegir a para minimizar C(a) + V(S'') , donde a lleva de S a S'' . Si encontró esta acción, establezca el estado igual a V(S) = C(a) + V(S'') .

Y así. Uno hace esto para todos los estados posibles y almacena cada valor óptimo V(S) obtenido de esta manera: para un número pequeño de baterías N , esto incluso podría ser factible en la práctica.

Una vez que esté listo con esto, obtendrá la acción óptima en cada estado. Para esto, si uno está en el estado S , uno sigue la misma receta que arriba y siempre elige la acción a que minimiza C(a) + V(S'') . Esto también se puede hacer solo una vez cuando se almacena la mejor acción para cada estado.

Y luego terminaste: resolviste por completo tu problema. O digamos, al menos teóricamente, porque en la práctica el tamaño del problema requiere demasiado esfuerzo y almacenamiento para realizar la recursión anterior y almacenarla en una tabla (para el problema especificado anteriormente, diría que este régimen comienza cuando N~3 y más grande). Por lo tanto, uno necesita introducir aproximaciones.

Aproximaciones

Al usar aproximaciones, en general se sacrifica la "solución óptima" por una "solución que funciona bien". Como esto se puede hacer de varias maneras, aquí es donde comienza el arte. O, para citar a Powell, capítulo 15.7 .: "Un algoritmo exitoso de ADP para una clase de problema importante es, creemos, una invención patentable". Debido a esto, solo bosquejaré algunos pasos posibles que se pueden hacer aquí.

  • Una clase de métodos de aproximación llamada agregación utiliza un modelo simplificado de la variable de estado. Por ejemplo, en lugar de incluir el tiempo T en trozos de 5m en la variable de estado (288 estados), uno puede usar trozos de 1h o incluso un valor booleano que indica si se trata de tiempo de oficina. O puede usar trozos de 5m solo durante el tiempo de oficina más un estado fuera de la oficina. Y así sucesivamente ... muchas posibilidades. Aquí uno siempre gana una representación tabular más pequeña de la

  • Otra clase de métodos de aproximación utiliza una representación parametrizada de la función de valor, por ejemplo, un modelo de regresión lineal o una red neuronal. En el esquema de iteración anterior, las funciones de valor no se almacenan en una tabla, sino que se utilizan como entrada para ajustar los parámetros. Éste reemplaza la representación tabular a menudo enorme por un número mucho más pequeño de parámetros, pero un inconveniente es que el procedimiento de ajuste suele ser más sofisticado. (Tenga en cuenta que en este paso los algoritmos evolutivos se pueden aplicar naturalmente).

  • En otro método, uno usa funciones de base que capturan estados importantes del sistema. Por ejemplo, en un juego de tres en raya, no necesitas todos los estados de juego posibles, pero son suficientes los estados básicos que indican quién ocupa el centro y el número de bordes ocupados.

  • A continuación, en lugar de intentar realizar una iteración completa en todos los estados, se pueden usar los métodos de Monte-Carlo para explorar aleatoriamente muchos, pero no todos, los estados posibles. Esto es tanto más eficiente cuanto mejores heurísticas existen, lo que permite que el algoritmo explore estados significativos.

Para otras ideas, así como su aplicación práctica, consulte los libros mencionados anteriormente.

Ok, eso se hizo largo, pero espero que ayude darles una idea de un posible enfoque. Le sugiero que diseñe un modelo pequeño usando solo una batería, por ejemplo, e intente implementar la iteración hacia atrás anterior por usted mismo. Alternativamente, en los dos libros citados, encontrará varios problemas de juguetes donde puede familiarizarse con este tipo de problemas. Buena suerte con las baterías!

Como esto es , y como vas a gastar fkn 500 de tus puntos apenas ganados, y como estoy muy interesado en esto yo mismo, te escribí un código de ejemplo que implementa la receta que presenté hace unos días. Aunque se trata de un modelo de juguete que se resuelve allí, contiene la mayoría de los problemas de su problema original y, dado el poder computacional suficiente, podría ampliarse fácilmente para resolver el último.

Problema de modelo

Consideremos el siguiente problema modelo:

  • N=2 baterías, M=2 recargas, K=1 descargador.

  • Tiempo T procede en múltiplos de 6 horas: 0:00 , 6:00 , 12:00 , 18:00 . Los horarios de oficina son todos excepto las 0:00 de la noche.

  • Los estados de la batería son:

    • SoC en {0%,50%,100%}
    • Relax en {0h,6h,12h,18h,24h}

    Las baterías están inicialmente en el estado {0%,0h} , es decir, descargadas al comienzo de la conducción de la prueba (Relax no es importante ya que de todos modos uno necesita recargar primero).

  • Las acciones disponibles son:

    • RELAX : no hagas nada. Aumenta el Relax en 6 horas.
    • RECHARGE : aumenta SoC al siguiente estado y establece Relax a 0h .
    • MEASURE : disminuye SoC al estado anterior y también establece Relax en 0h .

    Cada acción "cuesta" 6 horas.

    Tenga en cuenta que MEASURE se comporta de forma casi idéntica a lo que usted llamó DESCARGAR. Particularmente, si MEASURE se aplica a un estado de batería que no es un caso de prueba, es simplemente una DESCARGA. Sin embargo, y esa es la única diferencia, cuando MEASURE se aplica a uno de los casos de prueba también se actualiza el estado de Test .

  • Las baterías deben medirse una vez para cada estado {SoC,Relax} en {{50%,6h},{100%,6h},{50%,24h},{100%,24h}} . Eso hace que un vector de Test de la dimensión cuatro contenga ceros o unos.

Una vez que se haya familiarizado con la implementación a continuación, puede cambiar fácilmente todas estas opciones.

Descripcion del modelo

Voy a usar la descripción del sistema como se presentó en mi respuesta anterior. En particular, el estado del sistema está dado por un multi-vector

{Test, T, {SoC_1,Relax_1}, {SoC_2,Relax_2}}

De hecho, esta no es la mejor variable de estado (una variable de estado siempre debe ser lo más compacta posible). Por ejemplo, no se tiene en cuenta la simetría de las baterías. En los modelos de "realidad dura", problemas como este deben evitarse siempre que sea posible.

Además, simplifiqué las cosas asumiendo que todo sucede en pasos de tiempo de 6 horas. Con esto, simplemente puede aumentar la variable T 6 horas después de cada acción. Si hubiera acciones con una duración de, por ejemplo, 12 horas, habría que agregar más variables a la variable de estado que indiquen si la batería está bloqueada y cuándo estará disponible nuevamente. No hablar si habría una acción que duró 5 horas, por ejemplo. Como puede ver, el tiempo se trata de manera bastante básica aquí.

Implementación

He usado C ++ para la implementación y espero que estés cómodo con eso. El código en sí ya es bastante extenso, pero traté de comentarlo al menos un poco. Aquí están los principales puntos de implementación:

  • Primero, con respecto a los elementos básicos: los más elementales son dados por enum s tales como

    enum struct StateOfCharge { P0=0, P50, P100, END_OF_LIST };

    Los enteros también habrían funcionado bien, pero creo que es más fácil leer usando enumeraciones. Para estas enumeraciones, también proporcioné operator<< para salida de pantalla, así como operator++ y operator-- para aumentar / disminuir el estado. Los dos últimos operadores son plantillas de función que aceptan cualquier enumeración (--al menos si contiene un estado END_OF_LIST ).

  • Los elementos más avanzados como estados y acciones son clases. Particularmente, la clase de State contiene mucha lógica: es capaz de decir si una acción dada está permitida a través de su miembro.

    bool isActionAllowed(Action const&) const

    Además puede darle el siguiente estado para una acción determinada a través de

    State nextState(Action const&) const

    Estas funciones son centrales en la iteración del valor que se describe a continuación.

  • Existe la clase BatteryCharger , que realiza el algoritmo de programación dinámica real. Contiene un contenedor std::map<State,int> para almacenar el valor de un estado dado (recuerde que el valor aquí es simplemente el tiempo requerido para finalizar, que naturalmente se minimizará). Para que el map funcione, también hay un operator< compara dos variables de State .

  • Finalmente, algunas palabras sobre el esquema Value Iteration . En la respuesta anterior, escribí que uno puede hacerlo mediante iteración hacia atrás. Esto es cierto, pero puede ser bastante complicado porque necesita encontrar un camino de regreso de modo que todos los estados posibles estén cubiertos (y en el mejor de los casos solo una vez). Aunque esto sería posible aquí, también se puede simplemente iterar sobre todos los estados de una manera arbitraria. Sin embargo, esto debe hacerse de manera iterativa, porque de lo contrario se recurrirá a valores de estado que aún no se han optimizado. La iteración aquí termina cuando todos los valores se convergen.

    Para más información sobre la iteración de valores, vea nuevamente el libro de Sutton y Barto .

Código

Aquí está el código. No está particularmente bien escrito (--global variables etc.), pero funciona y se puede extender fácilmente:

#include<iostream> #include<array> #include<map> #include<type_traits> #include<algorithm> template<typename T, typename = typename std::enable_if<std::is_enum<T>::value >::type> bool isLast(T const& t) { return t == static_cast<T>(static_cast<int>(T::END_OF_LIST) - 1); } template<typename T, typename = typename std::enable_if<std::is_enum<T>::value >::type> bool isFirst(T const& t) { return t == static_cast<T>(0); } template<typename T, typename = typename std::enable_if<std::is_enum<T>::value >::type> T& operator++(T& t) { if (static_cast<int>(t) < static_cast<int>(T::END_OF_LIST) - 1) { t = static_cast<T>(static_cast<int>(t)+1); } return t; } template<typename T, typename = typename std::enable_if<std::is_enum<T>::value >::type> T operator++(T& t, int) { auto ret = t; ++t; return ret; } template<typename T, typename = typename std::enable_if<std::is_enum<T>::value >::type> T& operator--(T& t) { if (static_cast<int>(t) > 0) { t = static_cast<T>(static_cast<int>(t)-1); } return t; } template<typename T, typename = typename std::enable_if<std::is_enum<T>::value >::type> T operator--(T& t, int) { auto ret = t; --t; return ret; } const int Nbattery = 2; const int Nrecharger = 2; const int Ndischarger = 1; const int Ntest = 4; enum struct StateOfCharge { P0=0, P50, P100, END_OF_LIST }; //screen output std::ostream& operator<<(std::ostream& os, StateOfCharge const& s) { if(s==StateOfCharge::P0) os << "P0"; else if (s==StateOfCharge::P50) os << "P50"; else if (s == StateOfCharge::P100) os << "P100"; return os; } enum struct StateOfRelax { H0=0, H6, H12, H18, H24, END_OF_LIST }; //screen output std::ostream& operator<<(std::ostream& os, StateOfRelax const& s) { if(s==StateOfRelax::H0) os << "H0"; else if (s == StateOfRelax::H6) os << "H6"; else if (s == StateOfRelax::H12) os << "H12"; else if (s == StateOfRelax::H18) os << "H18"; else if (s == StateOfRelax::H24) os << "H24"; return os; } struct SingleBatteryState { //initialize battery as unfilled StateOfCharge SoC; StateOfRelax Relax; SingleBatteryState(StateOfCharge _SoC = static_cast<StateOfCharge>(0), StateOfRelax _Relax = static_cast<StateOfRelax>(0)) : SoC(_SoC) , Relax(_Relax) {} //loop over state bool increase() { //try to increase Relax if (!isLast(Relax)) { ++Relax; return true; } //if not possible, reset Relax else if (!isLast(SoC)) { ++SoC; Relax = static_cast<StateOfRelax>(0); return true; } //no increment possible: reset and return false SoC = static_cast<StateOfCharge>(0); Relax = static_cast<StateOfRelax>(0); return false; } }; std::ostream& operator<<(std::ostream& os, SingleBatteryState const& s) { os << "("<<s.SoC << "," << s.Relax << ")"; return os; } bool operator<(SingleBatteryState const& s1, SingleBatteryState const& s2) { return std::tie(s1.SoC, s1.Relax) < std::tie(s2.SoC, s2.Relax); } bool operator==(SingleBatteryState const& s1, SingleBatteryState const& s2) { return std::tie(s1.SoC, s1.Relax) == std::tie(s2.SoC, s2.Relax); } //here specify which cases you want to have tested std::array<SingleBatteryState, Ntest> TestCases = { SingleBatteryState{ StateOfCharge::P50, StateOfRelax::H6 } , SingleBatteryState{ StateOfCharge::P50, StateOfRelax::H24 } , SingleBatteryState{ StateOfCharge::P100, StateOfRelax::H6 } , SingleBatteryState{ StateOfCharge::P100, StateOfRelax::H24 } }; // for a state s (and action MEASURE), return the entry in the array Test // which has to be set to true int getTestState(SingleBatteryState const& s) { auto it = std::find(std::begin(TestCases), std::end(TestCases), s); if(it==std::end(TestCases)) return -1; else return it - std::begin(TestCases); } enum struct SingleAction { RELAX = 0, RECHARGE, MEASURE, END_OF_LIST }; std::ostream& operator<<(std::ostream& os, SingleAction const& a) { if(a== SingleAction::RELAX) os << "RELAX"; else if (a == SingleAction::RECHARGE) os << "RECHARGE"; else if (a == SingleAction::MEASURE) os << "MEASURE"; return os; } enum struct TimeOfDay { H0 = 0, H6, H12, H18, END_OF_LIST }; //here set office times std::array<TimeOfDay,3> OfficeTime = {TimeOfDay::H6, TimeOfDay::H12, TimeOfDay::H18}; bool isOfficeTime(TimeOfDay t) { return std::find(std::begin(OfficeTime), std::end(OfficeTime),t) != std::end(OfficeTime); } //screen output std::ostream& operator<<(std::ostream& os, TimeOfDay const& s) { if(s==TimeOfDay::H0) os << "0:00 h"; else if (s == TimeOfDay::H6) os << "6:00 h"; else if (s == TimeOfDay::H12) os << "12:00 h"; else if (s == TimeOfDay::H18) os << "18:00 h"; return os; } struct Action { SingleAction& operator[](int i) { return A[i]; } SingleAction const& operator[](int i) const { return A[i]; } std::array<SingleAction, Nbattery> A{}; bool increase() { for (int i = Nbattery - 1; i >= 0; --i) { if (!isLast(A[i])) { ++A[i]; return true; } else { A[i] = static_cast<SingleAction>(0); } } return false; } }; //screen output std::ostream& operator<<(std::ostream& os, Action const& A) { os << "("; for (int i = 0; i < Nbattery-1 ; ++i) { os << A[i] << ","; } os << A[Nbattery-1] << ")"; return os; } struct State { std::array<bool, Ntest> Test{}; TimeOfDay T = TimeOfDay::H0; std::array<SingleBatteryState, Nbattery> B{}; State() { for (int i = 0; i < Ntest; ++i) { Test[i] = true; } } bool isSingleActionAllowed(SingleAction const& a) const { if ( !isOfficeTime(T) && a != SingleAction::RELAX) { return false; } return true; } bool isActionAllowed(Action const& A) const { //check whether single action is allowed for (int i = 0; i < Nbattery; ++i) { if (!isSingleActionAllowed(A[i])) return false; } //check whether enough Rechargers and Dischargers are available int re = 0; int dis = 0; for (int i = 0; i < Nbattery; ++i) { //increase re counter if (A[i] == SingleAction::RECHARGE) { ++re; } //increase dis counter else if (A[i] == SingleAction::MEASURE) { ++dis; } //check whether ressources are exceeded if (re>Nrecharger || dis > Ndischarger) { return false; } } return true; } //loop over state bool increase() { //increase time if (!isLast(T)) { ++T; return true; } else { T = static_cast<TimeOfDay>(0); } //if not possible, try to increase single battery states for (int i = Nbattery-1; i >= 0; --i) { if (B[i].increase()) { return true; } } //if also not possible, try to increase Test state for (int i = Ntest-1; i >=0; --i) { if (Test[i]) { Test[i] = false; return true; } else { Test[i] = true; } } return false; } // given a single action and a single-battery state, calculate the new single-battery state. // it is assumed the action is allowed SingleBatteryState newState(SingleBatteryState s, SingleAction const& a) const { if (a == SingleAction::RELAX) { ++s.Relax; } else if (a == SingleAction::RECHARGE) { ++s.SoC; s.Relax = static_cast<StateOfRelax>(0); } else if (a == SingleAction::MEASURE) { --s.SoC; s.Relax = static_cast<StateOfRelax>(0); } return s; } // calculate new complete state while assuming the action s allowed State newState(Action const& a) const { State ret = *this; //increase time if (isLast(ret.T)) { ret.T = static_cast<TimeOfDay>(0); } else { ret.T++; } //apply single-battery action for (int i = 0; i < Nbattery; ++i) { ret.B[i] = newState(B[i], a[i]); // if measurement is performed, set new Test state. // measurement is only possible if Soc=50% or 100% // and Relax= 6h or 24h if (a[i] == SingleAction::MEASURE && getTestState(B[i]) != -1) { ret.Test[getTestState(B[i])] = true; } } return ret; } int cost(Action const& a) const { if (std::find(std::begin(Test), std::end(Test), false) == std::end(Test)) { return 0; } return 1; } }; //screen output std::ostream& operator<<(std::ostream& os, State const& S) { os << "{("; for (int i = 0; i < Ntest-1; ++i) { os << S.Test[i]<<","; } os << S.Test[Ntest-1] << "),"<<S.T<<","; for (int i = 0; i < Nbattery; ++i) { os << "(" << S.B[i].SoC << "," << S.B[i].Relax<<")"; } os << "}"; return os; } bool operator<(const State& s1, const State& s2) { return std::tie(s1.Test, s1.T, s1.B) < std::tie(s2.Test, s2.T, s2.B); } struct BatteryCharger { bool valueIteration() { // loop over all states with one specified Test state State S; int maxDiff=0; do { int prevValue = V.find(S)->second; int minCost = prevValue; // loop over all actions // and determine the one with minimal cost Action A; do { if (!S.isActionAllowed(A)) { continue; } auto Snew = S.newState(A); int newCost = S.cost(A) + V.find(Snew)->second; if (newCost < minCost) { minCost = newCost; } } while (A.increase()); V[S] = minCost; maxDiff = std::max(maxDiff, std::abs(prevValue - minCost)); } while (S.increase()); //return true if no changes occur return maxDiff!=0; } void showResults() { State S; do { auto Aopt = getOptimalAction(S); auto Snew = S.newState(Aopt); std::cout << S << " " << Aopt << " " << Snew << " " << V[S] << " " << V.find(Snew)->second << std::endl; } while (S.increase()); } Action getOptimalAction(State const& S) const { Action Aopt; Action A; int minCost = std::numeric_limits<int>::max(); do { if (!S.isActionAllowed(A)) { continue; } auto Snew = S.newState(A); int newCost = S.cost(A) + V.find(Snew)->second; if (newCost < minCost) { minCost = newCost; Aopt = A; } } while (A.increase()); return Aopt; } BatteryCharger() { State S; do { int ad = 0; for (int i = 0; i < Ntest; ++i) { if (!S.Test[i]) ad += 100; } V[S] = ad; } while (S.increase()); } std::map<State, int> V; }; int main(int argc, char* argv[]) { BatteryCharger BC; int count = 0; while (BC.valueIteration()) { ++count; }; std::cout << "Value Iteration converged after " << count << " iterations/n"<<std::endl; //start at 6:00 with no tests at all performed State S; S.Test[0] = false; S.Test[1] = false; S.Test[2] = false; S.Test[3] = false; S.T = TimeOfDay::H6; //get sequence of optimal actions auto Aopt = BC.getOptimalAction(S); while (BC.V[S] != 0) { std::cout << S << " " << Aopt << " " << BC.V[S] << std::endl; S = S.newState(Aopt); Aopt = BC.getOptimalAction(S); } std::cout << S << " " << Aopt << " " << BC.V[S] << std::endl; return 0; }

Aquí hay una DEMO para jugar.

Resultados

Con el código anterior, uno obtiene los siguientes resultados impresos en la pantalla:

Value Iteration converged after 8 iterations {(0,0,0,0),6:00 h,(P0,H0)(P0,H0)} (RELAX,RECHARGE) 10 {(0,0,0,0),12:00 h,(P0,H6)(P50,H0)} (RECHARGE,RECHARGE) 9 {(0,0,0,0),18:00 h,(P50,H0)(P100,H0)} (RECHARGE,RELAX) 8 {(0,0,0,0),0:00 h,(P100,H0)(P100,H6)} (RELAX,RELAX) 7 {(0,0,0,0),6:00 h,(P100,H6)(P100,H12)} (MEASURE,RELAX) 6 {(0,0,1,0),12:00 h,(P50,H0)(P100,H18)} (RELAX,RELAX) 5 {(0,0,1,0),18:00 h,(P50,H6)(P100,H24)} (RELAX,MEASURE) 4 {(0,0,1,1),0:00 h,(P50,H12)(P50,H0)} (RELAX,RELAX) 3 {(0,0,1,1),6:00 h,(P50,H18)(P50,H6)} (RELAX,MEASURE) 2 {(1,0,1,1),12:00 h,(P50,H24)(P0,H0)} (MEASURE,RELAX) 1 {(1,1,1,1),18:00 h,(P0,H0)(P0,H6)} (RELAX,RELAX) 0

Uno ve que la iteración del valor converge después de 8 iteraciones. En mi PC y con Visual Studio en modo de lanzamiento, esto toma aproximadamente medio segundo. Por lo tanto, puede hacer que el problema sea más detallado y, a la vez, esperar una respuesta exacta y factible.

En las líneas a continuación, verá un ejemplo de un proceso de prueba optimizado. Aquí, el estado inicial es {(0,0,0,0),6:00 h,(P0,H0)(P0,H0)} , es decir, la prueba completa se inicia a las 6 a.m. con las baterías no utilizadas ( P0 aquí significa 0% , 6:00 h significa 6am o el alemán "6:00 Uhr"). La siguiente columna le da la acción optimizada {RELAX,RECHARGE} (que lleva al estado en la siguiente línea). El número en la tercera columna es el tiempo (en unidades de 6 horas) que aún se requiere para finalizar las pruebas. Para este caso de ejemplo, se requieren un total de 60 horas.

Ahí está, el problema del modelo está resuelto. Para verificar diferentes estados iniciales (¡ todos han sido optimizados!), Simplemente cambie las siguientes líneas en main :

//start at 6:00 with no tests at all performed State S; S.Test = {false,false,false,false}; S.T = TimeOfDay::H6;

Y ahora, ¡diviértete! En el mejor de los casos, nos deja saber cómo procedió y qué tan exitoso fue.