资源描述：
《rollout algorithms for combinatorial optimizationnew》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、APRIL1997LIDS-P-2386REVISEDJUNE1997ROLLOUTALGORITHMSFORCOMBINATORIALOPTIMIZATION1byDimitriP.Bertsekas,JohnN.Tsitsiklis,andCynaraWu2AbstractWeconsidertheapproximatesolutionofdiscreteoptimizationproblemsusingproceduresthatarecapableofmagnifyingtheeffectivenessofanygivenheuristicalgori
2、thmthroughsequen-tialapplication.Inparticular,weembedtheproblemwithinadynamicprogrammingframework,andweintroduceseveraltypesofrolloutalgorithms,whicharerelatedtonotionsofpolicyiter-ation.Weprovideconditionsguaranteeingthattherolloutalgorithmimprovestheperformanceoftheoriginalheuris
3、ticalgorithm.Themethodisillustratedinthecontextofamachinemain-tenanceandrepairproblem.1ResearchsupportedbyNSFunderGrantDMI-9625489.2Dept.ofElectricalEngineeringandComputerScience,M.I.T.,Cambridge,Mass.,02139.11.Introduction1.INTRODUCTIONWediscusstheapproximatesolutionofbroadclasses
4、ofcombinatorialoptimizationproblemsbyembeddingthemwithinaDynamicProgrammingframework(DPforshort).Thekeyideaistoemployagivenheuristicintheconstructionofanoptimalcost-to-gofunctionapproximation,whichisthenusedinthespiritoftheNeuro-DynamicProgramming/ReinforcementLearningmethodology(N
5、DPforshort;see[BBS95],[BeT96]forbroaddiscussionsofthismethodology).Inthenextsection,wewillintroduceageneralgraphsearchproblemthatwillserveasthecontextofourmethodology.Toillustratetheideasinvolved,however,letusconsiderthefollowingtypeofproblem,whichincludesasspecialcasesproblemssuch
6、asshortestpath,assignment,scheduling,matching,etc.TheproblemischaracterizedbyafinitesetUoffeasiblesolutions,andbyacostfunctiong(u).EachsolutionuhasNcomponents;thatis,ithastheformu=(u1,u2,...,uN),whereNisapositiveinteger.Wewanttofindasolutionu∈Uthatminimizesg(u).Wecanviewtheprecedingp
7、roblemasasequentialdecisionproblem,wherebythecom-ponentsu1,...,uNareselectedone-at-a-time.Ann-tuple(u1,...,un)consistingofthefirstncomponentsofasolutioniscalledann-solution.Weassociaten-solutionswiththenthstageofaDPproblem.Inparticular,forn=1,...,N,thestatesofthenthstageareoftheform
8、(u1,...,un).Theinitialstat
