Fli*_*lip 16 algorithm search genetic-algorithm evolutionary-algorithm
我正在寻找一种合适的算法来解决时间调度问题.首先,我将概述问题本身,然后在第二部分,我将给出我正在考虑解决方案的方向.我正在尝试解决这个问题,因为我对这些问题感兴趣,并且因为同样的问题可以在以后用更多的变量和更大的设置来解决.
我想对电池进行一些测试,以了解它们在连接到负载时的响应方式.并在尽可能短的时间内完成所有测试.这里的两个重要变量是:
总组合:一个电池4 x 7 = 28
测试应该进行的顺序如下:充电到100%,放电到所需的SoC,放松,放电到新的SoC测量
示例:我们希望看到电池在放电达到2小时的同时从75%放电到50%时的反应
电池现在可以再次放松,并从50%到25%开始测量.它不必再次充电至100%.
现在我将概述一些可能发生的情况以及在这种情况下必须采取的措施.
可以使用已执行的测试来初始化问题(这很重要,因为我们可能希望在中途重新安排).如果电池具有已知状态(SoC /松弛),我们可以使用它.如果SoC未知,那么电池必须充电.如果放松未知但SoC已知,那么电池必须放松至少24小时.
将电池放入充电器必须手动完成.将电池留在充电器中不是问题.充电大约需要2.5小时.每个电池都有自己的专用充电器,但将来我们可能会有更多的电池充电器,因此算法需要能够采用不同数量的充电器.
放松可以简单地通过不将电池连接到任何东西来完成,因此它不需要任何特殊设备.在松弛时间段开始之前,必须对电池施加压力(=连接到放电器).我们不确定压力期将持续多长时间,但我们假设将电池放电1%所需的时间就足够了.99%将成为我们可以准确确定放松时间的第一个SoC.
目前只有一个放电器,但算法应该能够采用不同数量的放电器.将电池放入放电器必须手动完成(也取出).但是,如果将电池放入放电器,则无需立即将电池放电.可以将时间设置为在特定时间开始.当排出足够的能量时,放电器可以自动停止.可以从查找表估计放电时间的估计.这不是线性的,因此75%至50%不必花费相同的时间,从25%到0%.查找相当准确(2.5小时差异大约5分钟).
如果取出所有放电器,电池可以等待,但是等待放电器会增加放松时间.因此,如果弛豫时间高于必须执行的测量所需的弛豫时间,则它必须放电到较低的电荷水平并再次松弛,或者必须再次充电.
如果安全地取出所有充电器,电池可以等待,这里没有任何惩罚/劣势,除此之外没有时间等待.
必须手动完成的事情只能在办公时间(星期一至星期五8:30-17:00)完成.因此,例如将电池放入放电器必须手动完成.然后在夜晚的设定时间(电池放松后),可以在计时器上启动放电器,然后第二天早上到达办公室时,电池可以放入充电器.
我不确定我是否正在考虑正确的方向,因为我还没有工作解决方案.所以部件中的任何东西都可能是错误的..
任务序列很重要,因为不同的序列可能会引入比另一个序列更多或更少的等待时间.因此,对于只有一个28次测试的电池,这将是28的排列!这是一个相当大的数字.因此,对问题空间的详尽搜索是不可行的.我所知道的唯一可以在这些问题上给出相当好结果的算法是遗传算法.虽然有所有的限制和可能性,我不能只使用经典的遗传算法.我读过一些(研究)论文,最终对排列Flowshop调度问题(PFSP)的描述产生了最多的共鸣(各种来源).虽然提到扩展作业车间调度问题(EJSSP)在这里也非常有趣.
我看到的最大问题是办公时间限制.如果不是因为调度可能类似于仅将块拟合到时隙中(即使插槽具有动态大小).我不确定处理这种约束的最佳方法是什么.要么我可以将机器(放电器)建模为两个独立的机器,每个机器在不同时刻都是活动的,或者我可以引入假工作,以便机器不能被正常工作带走.
这只是在这一点上的猜测,因为我缺乏经验.我更像是一个务实的程序员,而不是一个学者,我真的很难弄清楚哪些算法适合哪些,以及注意事项是什么.我很高兴做到实施,但现在我仍然坚持:
dav*_*igh 10
虽然您已明确标记evolutionary-algorithm,但我建议您查看一组以近似动态规划(ADP)命名的算法.在我看来,一本好的介绍性书籍是沃伦·鲍威尔(Warren B. Powell).它包含许多这样的资源分配问题,以及其他一些实际相关的东西,这些东西通常以最优控制的名义(例如:控制拥有数千辆卡车的货运公司).
ADP直接应用进化算法,模拟退火等的一个优点是它没有提供特定的算法,而是一个用于建模时间依赖的马尔可夫决策问题的框架.在这些框架内,人们可以自由地使用各种适当的算法.
为了应用ADP,一个关键是给定问题的正确数学建模.最重要的是state系统,actions人们可以采取一个给定的状态,以及cost这些行动需要和哪个人想要最小化 - 这里的成本由测试的持续时间给出.给定一个已经构建了适当的模型,然后该任务将(近似地)求解Bellman方程,其中存在若干算法.
在下文中,我将举例说明如何进行此处.这自然不是一个随时可用的模型,因为这可能需要相当长的时间来构建 - 实际上我认为这对于大师甚至是博士论文来说都是一个很好的问题.但是,我会尝试在第一步中保持详尽无遗,以便稍后可以引入近似值.
首先,我们将为单个电池设置一个粗略的模型.在这里,您的问题与您所描述的一样具有确定性是有帮助的,即此处没有随机分量(例如,所有持续时间都是固定的,而不是从某些统计分布中随机抽取).
单一状态:正如您所写,一个电池由一个州提供
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为0s 的向量,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于在工作时间以及是否有足够的再充电和放电(全部RECHARGE/ DISCHARGE不得超过M/ 的总和K).
总而言之,完整的状态S由组合给出
S = {Test, T, B}
国家空间的维度2^28 * (6*9)^N * 288很快就会变得庞大.
此外,对于每个州,存在相应的一组允许的动作,这些动作现在应该是清楚的.
所以现在已经或多或少地指定了系统的模型(如果需要,请更正它!),我们可以继续尝试解决它.
Bellman方程是(近似)动态规划的中心方程.有一个很好的介绍,请看一下Sutton和Barto的书,它可以在网上免费获得.
它的想法很简单:对于每个可能的状态,引入一个值函数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算法是一项可获得专利的发明".因此,我将只绘制一些可以在这里完成的步骤.
一类称为聚合的近似方法使用状态变量的简化模型.例如,不是在状态变量(288个状态)中T以5m块的形式包括时间,而是可以使用1h块或甚至布尔值来指示它是否是办公时间.或者,您5m只能在办公时间加一个州外出时间使用块.等等......很多可能性.这里总是得到一个较小的表格表示
另一类近似方法使用值函数的参数化表示,比如线性回归模型或神经网络.在上面的迭代方案中,值函数不存储在表中,而是用作输入以适合参数.这个通过更少数量的参数替换了通常巨大的表格表示,但缺点是拟合过程通常更复杂.(注意,在这一步骤中,可以自然地应用进化算法).
在另一种方法中,使用捕获系统重要状态的基函数.例如,在井字游戏中,您不需要所有可能的游戏状态,但是指示谁占据中心和占用边数的基础状态就足够了.
接下来,可以使用蒙特卡罗方法随机探索许多但不是所有可能的状态,而不是尝试对所有状态执行完整迭代.这是更有效的,更好的启发式存在,让算法探索有意义的状态.
有关其他想法及其实际应用,请参阅上述书籍.
好吧,这变得冗长但我希望有助于你了解一种可能的方法.我建议你只使用一个电池设计一个小型模型,然后尝试自己实现上面的反向迭代.或者,在所引用的两本书中,您会发现几个玩具问题,您可以熟悉这些问题.祝电池好运!