is Íslenska en English

Lokaverkefni (Doktors)

Háskóli Íslands > Verkfræði- og náttúruvísindasvið > Doktorsritgerðir - Verkfræði- og náttúruvísindasvið >

Vinsamlegast notið þetta auðkenni þegar þið vitnið til verksins eða tengið í það: http://hdl.handle.net/1946/25337

Titill: 
  • Titill er á ensku ALICE: Analysis & Learning Iterative Consecutive Executions
  • LÍSA: Lærdómur ítrekunarreiknirita og samtakagreining algríma
Námsstig: 
  • Doktors
Efnisorð: 
Útdráttur: 
  • Útdráttur er á ensku

    Over the years there have been many approaches to create dispatching rules for scheduling. Recent past efforts have focused on direct search methods (e.g. genetic programming) or training on data (e.g. supervised learning). The dissertation will examine the latter and give a framework called Analysis & Learning Iterative Consecutive Executions (ALICE) on how to do it effectively.
    Defining training data as {φ(xi(k)),yi(k)} ∈ D (k from 1 to K) the dissertation will show: i) φ(xi(k)) should represent the induced data distribution D. This done by updating the learned model in an active imitation learning fashion; ii) yi is labelled using an expert policy via a solver; iii) data needs to be balanced, as the set is unbalanced w.r.t. the dispatching step k, and iv) to improve upon localised stepwise features φ, it's possible to incorporate (K-k) roll-outs where the learned model can be construed as a deterministic pilot heuristic.
    When querying an expert policy, there is an abundance of valuable information that can be utilised for learning new models. For instance, it's possible to seek out when the scheduling process is most susceptible to failure. Furthermore, generally stepwise optimality (or classification accuracy) implies good end performance, here minimising the final makespan. However, as the impact of suboptimal moves is not fully understood, then the measure needs to be adjusted for its intended trajectory.
    Using these guidelines, it becomes easier to create custom dispatching rules for one's particular application. For this several different distributions of job-shop will be considered.
    Moreover, the machine learning approach is based on preference learning, i.e., which post-decision state is preferable to another. However, that could easily be substituted for other learning methods or applied to other shop-constraints or family of scheduling problems that are based on iteratively applying dispatching rules.

  • Til eru margar aðferðir við að búa til ákvarðanareglur fyrir áætlanagerð. Undanfarið hefur áherslan í fræðunum verið á beina leit (t.d. gentíska bestun) eða gagnaþjálfun, en ein aðferð við það síðarnefnda er stýrður lærdómur.Í ritgerðinni verður sú aðferð skoðuð nánar og sett fram líkan kallað „Lærdómur ítrekunarreiknirita og samtakagreining algríma“ (LÍSA) um hvernig megi framkvæma þessa greiningu á skilvirkan máta.
    Látum þjálfunargögnin vera {φ(xi(k)),yi(k)} ∈ D (k frá 1 til K) og ritgerðin mun sýna i) úrtök φ(xi(k)) þurfa að vera í samræmi við gagnadreifinguna D sem verður unnin úr henni. Þetta er gert með því að uppfæra lærða líkanið með virku námsferli byggðu á eftirlíkingum; ii) yi er merkt með því að nota endurgjöf sérfræðings (gert með bestun); iii) gögnin þurfa að vera í jafnvægi, þar sem gagnasettið er í ójafnvægi með tilliti til skrefs k; einnig iv) til að betrumbæta lýsingu á núverandi stöðu φ, er hægt að nota útspilun fyrir næstu K-k skref, það er að endalokum ákvarðanaferilsins. Þá má túlka lærða líkanið sem fyrirframákveðna útspilunarreglu
    Þegar sérfræðingur er spurður, verður til mikið af gagnlegum upplýsingum sem hægt er að nýta til að læra ný líkön. Til að mynda er hægt að komast að því hvenær í ákvarðanaferlinu er líklegast að mistök eigi sér stað. Yfirleitt gefa háar líkur á því að besta ákvörðun sé tekin (eða þjálfunarnákvæmni) til kynna góða lokaframmistöðu, þ.e. í þessu samhengi að lágmarka heildartíma fyrir allt ákvarðanaferlið. Þar sem afleiðingar rangra ákvarðana eru ekki alltaf þekktar, þá er betra að uppfæra matið með tilliti til ákvarðanatökunnar sjálfrar.
    Með þessari greiningu er einfaldara að búa til sérhæfðar ákvarðanareglur fyrir hverja nýja notkun. Í ritgerðinni verða skoðaðar nokkrar mismunandi tegundir af verkniðurröðun á vélar. Þar að auki verður vélnámið byggt á ákjósanlegri bestun, þar sem gerður er greinarmunur á því hvaða stöður eru betri kostur en aðrar. Ákjósanlegri bestun væri þó hægt að skipta út fyrir aðrar námsaðferðir, hægt væri að bæta við fleiri skorðum á verkefnið eða beita sömu námsaðferð á aðra tegund af verkefnum af svipuðum toga.

Styrktaraðili: 
  • Styrktaraðili er á ensku Doctoral grant from the Research Fund of the University of Iceland
Samþykkt: 
  • 22.6.2016
URI: 
  • http://hdl.handle.net/1946/25337


Skrár
Skráarnafn Stærð AðgangurLýsingSkráartegund 
thesis.pdf6.46 MBOpinnHeildartextiPDFSkoða/Opna