Ответ 1

Обзор

Хотя вы явно отметили evolutionary-algorithm, я бы предложил вам взглянуть на набор алгоритмов, подстроенных под названием Approximate Dynamic Programming (ADP). По-моему, хорошая вступительная книга - это Уоррен Б. Пауэлл. Он содержит много таких проблем с распределением ресурсов, а также несколько других практически важных материалов, которые часто подпадают под название Optimal Control (например: управление транспортной компанией, имеющей несколько тысяч грузовиков).

Одно из преимуществ ADP заключается в прямом применении эволюционных алгоритмов, имитации-отжиге и т.д., так это то, что он не представляет собой специфический алгоритм, а скорее представляет собой структуру для моделирования зависимых от времени марковских решений. В этих рамках можно свободно использовать множество подходящих алгоритмов.

Для применения ADP одним ключом является правильное математическое моделирование данной проблемы. Центральное значение имеет система state системы, actions, которую можно взять в определенном состоянии, а также cost, требуемые этими действиями, и которые нужно минимизировать - ваши затраты здесь указаны продолжительностью тест. Учитывая, что построена подходящая модель, задача состоит в том, чтобы (приблизительно) решить уравнение Беллмана, для которого существует несколько алгоритмов.

В следующем примере я приведу пример того, как можно продолжить здесь. Это, естественно, не готовая к использованию модель, так как это может занять довольно много времени - на самом деле я думаю, что это была бы прекрасная проблема для мастеров или даже кандидатской диссертации. Тем не менее, я постараюсь сделать его исчерпывающим на первом этапе, так что позже можно ввести приближения.

Моделирование состояния отдельной батареи

Сначала мы собираемся создать грубую модель для одной батареи. Здесь полезно, чтобы ваша проблема была столь же детерминированной, как вы описали, т.е. Что здесь нет стохастических компонентов (например, что все длительности фиксированы, а не случайным образом выведены из некоторого статистического распределения).

• Одиночное состояние: Как вы писали, одна батарея задается состоянием

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

  Я добавил 0% и 0m для удобства, хотя они, возможно, действительно не нужны здесь.

  Обратите внимание, что здесь я уже сделал большое упрощение, так как, например, может быть и "Плата за обслуживание" 79%. Предположение, которое оправдывает это, следующее: после того, как вы впервые запустите свой эксперимент (или снова заново), все батареи находятся в состоянии {UNKNOWN,UNKNOWN}. Затем, согласно вашему описанию, первым нужно сделать, чтобы выполнить полную перезарядку, которая устанавливает все в состояние {100%,0m} (и которое стоит 2,5h). Отсюда происходит только квалифицированное изменение состояния - разрядка выполняется только для конкретных SoC и перечитывается только на 100% (это я предположил на основе вашего описания). Обратите внимание, что это становится сложнее в более естественной стохастической структуре, где, например, батареи SoC не настолько хорошо себя ведут.

• Действия и затраты: для конкретных состояний с одной батареей, один из них связан с набором допустимых действий (плюс их соответствующие затраты). Пусть они собираются в следующем:

  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 здесь означает следующее допустимое состояние, тогда как C(SoC, SoC-1) означает "время перехода от SoC к SoC-1, например, от 75% до 50%. На ваш ход здесь, чтобы проверить эту таблицу, соответствует ли она ваша модель. Если нет, вам нужно исправить или расширить ее.

  Обратите внимание, что я сделал еще одно упрощение, разрешив только переход к следующему допустимому состоянию SoC-1 (например, от 75% до 50%). Это разумно, так как стоимость считается дополнительной. Например, когда вы переходите от 75% до 25%, это занимает то же время, что и при первом переходе на 50%, а затем на 25%.

  Кроме того, все действия RECHARGE и DISCHARGE возможны только в рабочие часы, которые не были учтены в приведенной выше таблице (но которые должны быть включены позже в модель).

Объедините приведенное выше с моделью полной системы

Теперь предположим, что у вас есть аккумуляторы N, зарядные устройства M и разрядники K (где мы можем предположить M<=N и K<=N), все из которых идентичны. Далее, скажем, цель состоит в том, чтобы выполнить каждый тест только один раз.

• Состояние теста:Состояние испытания Test представляет собой вектор размерности 4*7 0 и 1, содержащий информацию о том, был ли уже выполнен конкретный тест. Заметим, что это соответствует 2^28 возможным состояниям, поэтому определенно нужно ввести здесь приближение.

• Состояние нескольких батарей: Общее состояние всех батарей B является декартовым продуктом состояния с одной батареей, то есть находится в пространстве {SoC,Relax}^N. Это означает просто, что нужно учитывать состояния N с одной батареей.

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

  Опять же, размер этого пространства будет очень большим для умеренных чисел N.

• Время в офисе: Кроме того, нам нужно включить время суток T. Выполняя это точно, каждый заканчивается несколькими 24*60m / 5m = 288 возможными пятиминутными слотами.

• Действия с несколькими батареями: Аналогично, действия с несколькими батареями даются с помощью N -мерного декартова произведения одномерных действий. RECHARGE и DISCHARGE возможно только для T в часы offcie, и если доступно достаточное количество Re- и Dischargers (сумма всех RECHARGE/DISCHARGE не должна превышать M/K),

Подводя итог, полное состояние S определяется комбинацией

S = {Test, T, B}

Размер пространства состояний около 2^28 * (6*9)^N * 288, который быстро становится огромным.

Кроме того, для каждого состояния существует соответствующий набор допустимых действий, которые должны быть понятны к настоящему времени.

Итак, теперь, когда модель системы была указана более или менее (исправьте ее при необходимости!), мы можем продолжить, пытаясь ее решить.

Уравнение Беллмана

Уравнение Беллмана является центральным уравнением (приближенного) динамического программирования. Для приятного ознакомления посмотрите на книгу Саттона и Барто, которая свободно доступна в сети.

Идея довольно проста: для каждого возможного состояния введите функцию значения V(S), которая сообщит вам, насколько она хороша в состоянии S. Эта функция значения в принципе содержит время, необходимое для завершения тестов, как только вы в состоянии S. Чтобы определить это значение для задачи с конечным горизонтом как таковой, оно начинается с конечного состояния и повторяется до начала - то есть, по крайней мере, если размер проблемы позволяет это. Но давайте сделаем это схематически в следующем и посмотрим:

конечное состояние - это тот, где Test содержит только те, т.е. все теги 28 выполнены. Установите V(S)=0 для всех этих состояний (независимо от T и состояния с несколькими батареями), поскольку вам не нужно больше времени.

На один шаг назад. Теперь рассмотрим все состояния, в которых Test имеет только 27 единиц и один нуль, т.е. один тест еще нужно выполнить. Для каждого возможного состояния с несколькими аккумуляторами B и временной точки T можно автоматически определить самую быструю альтернативу. Установите V(S), равную этой стоимости.

Еще один шаг назад. Далее рассматриваются все состояния, в которых Test имеет только 26 единиц и два нуля (еще два теста еще предстоит сделать). Теперь для каждого возможного состояния с несколькими батареями B и временной точки T выбирается действие a, например, чтобы минимизировать стоимость действия плюс значение состояния, к которому ведет действие. В терминах вам нужно выбрать a, чтобы свести к минимуму C(a) + V(S'), где a ведет от S до S'. Если вы нашли это действие, установите состояние равным V(S) = C(a) + V(S').

И так далее. Это делается для всех возможных состояний и сохраняет каждое оптимальное значение V(S), полученное таким образом - для небольшого количества батарей N это может быть практически осуществимо на практике.

Как только вы будете готовы к этому, вы получите оптимальное действие в каждом состоянии. Для этого, если он находится в состоянии S, следует тот же рецепт, что и выше, и всегда выбирает действие a, которое минимизирует C(a) + V(S'). Это также можно сделать только один раз, когда будет сохранено лучшее действие для каждого состояния.

И тогда вы закончили - вы полностью решили свою проблему. Или скажите, по крайней мере, теоретически, потому что на практике размер проблемы требует слишком больших усилий и хранения для выполнения вышеуказанной обратной рекурсии и хранения ее в таблице (для указанной выше проблемы я бы сказал, что этот режим начинается, когда N~3 и больше). Поэтому необходимо ввести приближения.

Аппроксимация

При использовании приближений, вообще говоря, жертвует "оптимальным решением" для "хорошо работающего решения". Поскольку это можно сделать несколькими способами, здесь начинается искусство. Или, чтобы привести Пауэлл, глава 15.7: "Успешный алгоритм ADP для важного проблемного класса, по нашему мнению, патентованное изобретение ". В связи с этим я буду только набросать некоторые возможные шаги, которые можно сделать здесь.

• Один класс методов аппроксимации, называемый агрегацией, использует упрощенную модель переменной состояния. Например, вместо включения времени T в 5m кусках в переменной состояния (288 состояний) можно использовать 1h куски или даже логическое значение, которое указывает, является ли это время работы. Или вы можете использовать 5m куски только во время работы в офисе плюс одно состояние вне офиса. И так далее... много возможностей. Здесь всегда получается меньшее табличное представление

• В другом классе методов аппроксимации используется параметризованное представление функции значений, например, линейная регрессионная модель или нейронная сеть. В приведенной выше схеме итераций функции значения не сохраняются в таблице, но они скорее используются в качестве входных данных для соответствия параметрам. Это заменяет часто огромное табличное представление гораздо меньшим количеством параметров, но недостатком является то, что процедура подгонки обычно более сложна. (Заметим, что на этом этапе естественным образом можно применять эволюционные алгоритмы).

• В другом методе используются базовые функции, которые захватывают важные состояния системы. Например, в игре tic-tac-toe вам не нужны все возможные игровые состояния, но достаточные базовые состояния, которые указывают, кто занимает центр и занятое количество ребер.

• Затем вместо того, чтобы пытаться выполнить полную итерацию по всем состояниям, можно использовать методы Монте-Карло для случайного изучения многих, но не всех возможных состояний. Это тем эффективнее, что существуют лучшие эвристики, которые позволяют алгоритму исследовать значимые состояния.

Для других идей, а также их практического применения обратитесь к книгам, упомянутым выше.

Хорошо, это стало длинным, но я надеюсь, что это поможет дать вам некоторое представление о одном возможном подходе. Я бы предложил вам разработать небольшую модель, используя только одну батарею, скажем, и попытаться реализовать вышеупомянутую обратную итерацию самостоятельно. Кроме того, в обеих цитированных книгах вы найдете несколько проблем с игрушками, где вы можете ознакомиться с такими проблемами. Удачи с батареями!

Ответ 2

Поскольку это StackOverflow, и поскольку вы собираетесь потратить fkn 500 своих едва заработанных очков, и, поскольку меня это очень интересует сам, я написал вам примерный код, который реализует рецепт, который я представил несколько дней назад, Хотя это и есть модель игрушек, которая решается там, она содержит большинство проблем вашей исходной проблемы и, при условии достаточной мощности компьютера, может быть легко расширена для решения последней проблемы.

Проблема модели

Рассмотрим следующую модельную задачу:

• N=2, M=2 Зарядные устройства, K=1 Разрядник.

• Время T продолжается в течение 6 часов: 0:00, 6:00, 12:00, 18:00. Часы работы все кроме 0:00 в ночное время.

• Состояние батареи:

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

  Батареи изначально находятся в состоянии {0%,0h}, то есть незаряжены в начале тестовой проводимости (Relax не имеет значения, поскольку в любом случае необходимо сначала перезарядить).

• Доступные действия:

  • Relax: ничего не делать. Увеличивает Relax на 6 часов.
  • RECHARGE: увеличивает SoC до следующего состояния и устанавливает Relax в 0h.
  • MEASURE: уменьшает SoC до предыдущего состояния, а также устанавливает Relax в 0h.

  Каждое действие "стоит" 6 часов.

  Обратите внимание, что MEASURE ведет себя почти идентично тому, что вы назвали DISCHARGE. В частности, если MEASURE применяется к состоянию батареи, которое не является тестовым, это просто РАЗГРУЗКА. Однако, и это единственное отличие, когда MEASURE применяется к одному из тестовых случаев, также обновляется состояние Test.

• Батареи необходимо измерять один раз для каждого состояния {SoC,Relax} в {{50%,6h},{100%,6h},{50%,24h},{100%,24h}}. Это делает вектор Test размерности четыре, содержащий либо нули, либо единицы.

После ознакомления с приведенной ниже реализацией вы можете легко изменить все эти варианты.

Описание модели

Я собираюсь использовать описание системы, как показано в моем предыдущем ответе. В частности, состояние системы задается многовекторным

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

На самом деле это не лучшая переменная состояния (переменная состояния должна всегда быть как можно более компактной). Например, не учитывается симметрия батарей. В "реалистичных" моделях проблемы, как этого следует избегать, когда это возможно.

Кроме того, я упростил все, предположив, что все происходит во временных шагах 6 часов. При этом можно просто увеличить переменную T на 6 часов после каждого действия. Если бы были действия продолжительностью, скажем, 12 часов, нужно было бы добавить дополнительные переменные к переменной состояния, которая указывает, заблокирована ли батарея и когда она будет снова доступна. Не говорить, если будет действие, которое длилось бы 5 часов, например. Итак, вы видите, что время рассматривается здесь довольно основательно.

Реализация

Я использовал С++ для реализации, и надеюсь, вам это понравится. Сам код уже довольно длинный, но я попытался прокомментировать его хотя бы немного. Вот основные варианты реализации:

• Во-первых, в отношении основных элементов: более элементарные задаются enum такими, как

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

  Целые числа также хорошо работали бы, но, я думаю, это становится легче читать с использованием перечислений. Для этих перечислений я также предоставил operator<< для вывода экрана, а также operator++ и operator-- для увеличения/уменьшения состояния. Два последних оператора - это функциональные шаблоны, принимающие любое перечисление (- по крайней мере, если оно содержит состояние END_OF_LIST).

• Более сложные элементы, такие как состояния и действия, являются классами. В частности, класс State содержит много логики: он способен определить, разрешено ли задание через его член

  bool isActionAllowed(Action const&) const
  

  Далее он может дать вам следующее состояние для данного действия через

  State nextState(Action const&) const
  

  Эти функции являются центральными в следующей итерации значений.

• Существует класс BatteryCharger, который выполняет фактический алгоритм динамического программирования. Он содержит контейнер std::map<State,int> для хранения значения данного состояния (помните, что здесь значение - это просто время, необходимое для завершения, которое, естественно, должно быть минимизировано). Для того, чтобы map работал, существует также operator< сравнение двух переменных State.

• Наконец, несколько слов в Value Iterationсхема. В вышеприведенном ответе я написал, что можно сделать это путем обратной итерации. Это правда, но это может стать довольно сложным, потому что вам нужно найти путь назад, чтобы охватить все возможные состояния (и в лучшем случае только один раз). Хотя это было бы возможно здесь, можно также просто перебрать все состояния произвольным образом. Однако это нужно сделать итеративно, потому что в противном случае вы будете использовать значения состояния, которые вы еще не оптимизировали. Итерация здесь заканчивается, когда все значения сходятся.

  Подробнее об итерации значений см. снова книга Саттона и Барто.

код

Вот код. Он не особенно хорошо написан (- global variables и т.д.), Но он работает и может быть легко расширен:

#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;
}

Ниже приведена DEMO.

Результаты

С помощью приведенного выше кода вы получите следующие результаты, напечатанные на экране:

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

Видно, что итерация значений сходится после 8 итераций. На моем ПК и в Visual Studio в режиме Release это занимает примерно полсекунды. Таким образом, вы можете смело сделать проблему более подробной и по-прежнему ожидать приемлемого точного ответа.

В приведенных ниже строках приведен пример оптимизированного процесса тестирования. Здесь начальное состояние {(0,0,0,0),6:00 h,(P0,H0)(P0,H0)}, т.е. Полный тест запускается в 6 утра с неиспользуемыми батареями (P0 здесь означает 0%, 6:00 h означает 6am или немецкий "6:00 Uhr" ). Следующий столбец дает вам оптимизированное действие {RELAX,RECHARGE} (что приводит к состоянию в следующей строке). Число в третьем столбце - это время (в единицах 6 часов), которое по-прежнему требуется для завершения тестов. Для этого примерного случая требуется в общей сложности 60 часов.

Вот вы, проблема модели решена. Чтобы проверить разные начальные состояния (все они были оптимизированы!), Просто измените следующие строки в main:

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

И теперь, получайте удовольствие! В лучшем случае вы сообщаете нам, как вы это делали и насколько успешно.