[Alg] Plannings algoritme

[UltimateB]

Ik moet voor mijn stage onder andere een planning laten genereren voor de plaatsing van artiesten binnen een tal bungalow parken.

Mijn vraag is eigenlijk of iemand hier nog wat goede boeken hierover weet die mij isschien een stap in de goede richting zouden helpen. Ik ben op dit moment een brute-force aanpak aan het proberen maar ik denk dat deze methode wat tekort gaat schieten op het moment dat er wijzigingen binnen de planning komen.

Nu heb ik mij laten vertelen door mijn docent software ontwikkeling dat er mensen zijn waarvan hun levenswerk is het maken van een planningsalchoritme dus ik begin ook ee beetje te twijfelen of dit überhaupt tot de mogelijkheden zou kunnen behoren. Daarintegen zullen zij wel een algeeen planningsalchoritme zoeken en niet iets waarvan de grenzen zo duidelijk zijn aangegeven.

Even ter informatie. Zaken die beperkend zijn binnen de planning zijn: aantal speeldagen, aantal km afgelegd, aantal breakshifts (dagen met 1-2 uur pauze ertussen), max 6 dagen aan een gesloten werken. Optredens en breakshifts zo evenredig mogelijk verdelen tussen de bands, niet een band 2x op zelfdse park binnen een midweek of weekeind. Daarnaast zijn er nog een aantal specifieke beperkingen die allen bij bepaalde parken gelden.

Maar mijn vraag blijft dus eigenlijk waar / welke docuentatie ik hierover kan vinden in bijvoorbeeld de bibliotheek, ik heb namelijk hard gezocht op google en kon hier niks over vinden, kan ook verkeerd gezocht hebben natuurlijk, maar heb er wel al aardig wat tijd aan besteedt.

[RickN]

Laat je niet direct ontmoedigen door je docent. Dit soort optimalisatie problemen zijn leuk en een leuk uitdaging, ook voor de wat mindere goden.

Kijk, als je b.v. een best-in-class VLSI layouter wilt bouwen moet je van goeie huizen komen, maar voor problemen van normale mensen/ondernemingen voldoet een standaard aanpak, eventueel met een beetje opleuking vaak ook al hoor.

Er is erg veel over geschreven, maar een leuk overzicht van beschikbare technieken staat in b.v.:

"Local Search in Combinatorial Optimization" door (edited by) Emile Aarts en Jan Karel Lenstra.

Succes.

[UltimateB]

Ok, ik heb dus zowiso al een redelijke werkend gedeelte voor die brute force, dan krijg ik alleen wel wat ehrm, moeilijkheidjes op het moment dat ik een gedeelte ga maken voor het wijzigen van de planning. Ik zal het boek dat je zuggereerde even opzoeken, kijken wat ik daarmee zal kunnen.

P.S. andere suggesties blijven welkom.

[Feyd-Rautha]

Kan je bepalen wanneer een bepaalde plaatsing van toeristen binnen een bungalow goed is, of eerder slecht is.

Zo ja, dan moet je eens kijken naar de volgende algoritmes (op internet is er wel heel wat over te vinden)

* Genetische Algoritmen
* Simulated Annealing
* Hill-climbing

Dat zijn namelijk allemaal algorithmes die lokale zoekproblemen oplossingen en VEEL PERFORMANTER zijn dan een gewone brute-force

in het boek: AI, A modern Approach staat er wel het een en ander over in.

[UltimateB]

Klein detail, het gaat om de plaatsing van artiesten binnen de parken.

Maar bedankt voor de tip.

edit1:
Maar inderrdaad, als ik op dit moment 5000 omgelijkheden wil laten genereren en daar dan een controle op uitoefen wat speeldagen aangaat duurt dit al een minuut of 7 op mijn 750 celeron. Nu is deze code wel heel grof nog maarjah, een alchoritme zou inderdaad veel efficienter zijn.

edit2:
Ik kon net bij een documentje die precies die 3 dingen in 1 noemt, een presentatie omtrend proggen in c ofzo... wel funny.

offtopic:
Ik doe net alttab en got staat op mijn 2e beeldscherm, nu zie ik in het sprekers scherm van powerpoint GoT int klein ;] Wist ik nie...

http://www.xs4all.nl/~remcodb/apart.jpg

[ Voor 92% gewijzigd door UltimateB op 16-01-2004 16:23 ]

[Verwijderd]

Russel en Norvig hebben een boek geschreven waar een heel groot aantal ai problemen worden behandeld waaronder ook allerlei zoekproblemen van best depth first, tot local beam search tot genetische algoritme.
Titel ben ik even kwijt

Je kan ook even googlen naar constrain statisfaction problems dat is namelijk de algemene naam hiervoor.

[ Voor 20% gewijzigd door Verwijderd op 16-01-2004 18:09 ]

[Feyd-Rautha]

zie mijn vorige post voor de titel

AI, A modern Approach

[UltimateB]

lol

Mja, ik heb dus een beetje rond gesnuffeld en ga maandag even naar Univesiteit leiden, geloof dat ze daaro ook iets van infomatica ofzo hebben... ff in de bib kijken

[Opi]

Feyd-Rautha schreef op 16 januari 2004 @ 15:55:
Kan je bepalen wanneer een bepaalde plaatsing van toeristen binnen een bungalow goed is, of eerder slecht is.

Zo ja, dan moet je eens kijken naar de volgende algoritmes (op internet is er wel heel wat over te vinden)

* Genetische Algoritmen
* Simulated Annealing
* Hill-climbing

Dat zijn namelijk allemaal algorithmes die lokale zoekproblemen oplossingen en VEEL PERFORMANTER zijn dan een gewone brute-force

in het boek: AI, A modern Approach staat er wel het een en ander over in.

Ik denk dat intelligente methoden als deze niet noodzakelijk zijn. Wellicht kan de TS kijken naar dynamic programming of een methode waarvan de naam mij helaas ontschoten is, maar die de NS (geen woord ) ook gebruikt.

[Glimi]

Genetische algoritmes zijn leuk, echter houdt er wel rekening mee dat ze vaak een benadering van het optimum geven (bijv GA kan blijven steken op een lokaal optimum). Als dat niet uitmaakt, zijn AI algoritmes zeker een leuk idee.

Is dat niet mogelijk, dan krijg je het heel erg moeilijk denk ik. Ik kan me namelijk bij dit probleem voorstellen dat het een soort van knapsack algoritme is, waar je een maximaal aantal artiesten kan plaatsen wat je waarde is en je beperkingen je gewicht.
Kan je echter cuts daarop maken, dan kan ik me voorstellen dat Dynamisch programmeren of Backtracking mogelijke opties zijn

Het ligt allemaal een beetje aan wat de grenzen van je opties zijn zeg maar

[Opi]

Glimi schreef op 16 januari 2004 @ 20:46:
Genetische algoritmes zijn leuk, echter houdt er wel rekening mee dat ze vaak een benadering van het optimum geven (bijv GA kan blijven steken op een lokaal optimum). Als dat niet uitmaakt, zijn AI algoritmes zeker een leuk idee.

Ik meende dat GAs als een van de weinige AI methoden juist wel globaal werkte en daartoe wel in staat was een globaal optimum te vinden.

[Glimi]

OpifexMaximus schreef op 16 januari 2004 @ 20:50:
Ik meende dat GAs als een van de weinige AI methoden juist wel globaal werkte en daartoe wel in staat was een globaal optimum te vinden.

Je populatie zal steeds meer op elkaar gaan lijken doordat sterken telkens overblijven en gekopieerd worden. Doordat alleen deze gemuteerd worden en deze mutaties minimaal zijn, kan het zijn dat een optimum welke bij een hele intensieve mutatie zit, kan het ervoor zorgen dat deze mutatie niet gemaakt wordt.

Dit is echter allemaal afhankelijk van welk selection gebruikt wordt.

edit:
Maar GA is in staat een globaal optimum vinden, maar _kan_ blijven steken

[ Voor 7% gewijzigd door Glimi op 16-01-2004 21:03 ]

[Opi]

Glimi schreef op 16 januari 2004 @ 21:00:

edit:
Maar GA is in staat een globaal optimum vinden, maar _kan_ blijven steken

Hmmm, moet ik me er toch eens iets meer in gaan verdiepen, want elke AI-methode is in principe in staat een globaal optimum te vinden, alhoewel de agent in een lokaal optimum kan blijven steken.

[ Voor 9% gewijzigd door Opi op 16-01-2004 21:40 ]

[H!GHGuY]

ik snap de opdracht zelf eigenlijk niet helemaal...

moet je de uurplanning maken??? de plaatsing (waar ze logeren) of wat???
want dan zou'k niet snappen wat hun plaatsing op een park te maken heeft met de breakshifts, afgelegde km's enz??)

kun je niet werken met weging???
geef alles een wegingscoefficient en leg de beperkingen vast.
probeer dan de PC dit tegelijk zo efficient mogelijk te laten doen...
test paar keer uit en als het dan nog niet ideaal is, dan kun je misschien er nog een
optimalisatie algoritme op loslaten... als je dan bvb GA erop zou loslaten dan weet je zeker dat je al redelijk dicht bij een oplossing zit...

[UltimateB]

OpifexMaximus schreef op 16 januari 2004 @ 20:02:
[...]

Ik denk dat intelligente methoden als deze niet noodzakelijk zijn. Wellicht kan de TS kijken naar dynamic programming of een methode waarvan de naam mij helaas ontschoten is, maar die de NS (geen woord ) ook gebruikt.

Kan je ajb iets beter uitleggen wat je hiermee bedoeld? Dynamisch programeren? Ik begrijp je punt niet helemaal.

HIGHGuY schreef op 16 januari 2004 @ 21:50:
ik snap de opdracht zelf eigenlijk niet helemaal...

moet je de uurplanning maken??? de plaatsing (waar ze logeren) of wat???
want dan zou'k niet snappen wat hun plaatsing op een park te maken heeft met de breakshifts, afgelegde km's enz??)

kun je niet werken met weging???
geef alles een wegingscoefficient en leg de beperkingen vast.
probeer dan de PC dit tegelijk zo efficient mogelijk te laten doen...
test paar keer uit en als het dan nog niet ideaal is, dan kun je misschien er nog een
optimalisatie algoritme op loslaten... als je dan bvb GA erop zou loslaten dan weet je zeker dat je al redelijk dicht bij een oplossing zit...

Het gaat om een planning van artiesten die op een park spelen.

Het moet schaalbaar zijn maar op dit moment omvat het:

13 parken (komen er binnen 2 maanden 4 bij), 9 artiesten (groepen, zal meer worden n.a.v. meer parken), de parken zin onderverdeeld in 3 'pouls'. Artiesten blijven zoveel mogelijk binnen hun poul ivm reis kilometers. Andere punten zijn: Aantal breakshifts (uitleg zie boven, mogen max 2 per week hebben in de regel), elke 7 dagen 1 dag vrij (redelijk makkelijk te controleren d.m.v. een window), max 1 keer per periode dat de gasten in het park zijn (1 midweek, 1 weekend zijn de meest gebruikte weekdelen), planning moet er komen voor elk steeds 4 weken (ivm werkvergunning voor nederland mogen ze maar 4 weken hier blijven).

De planning moet dus ten eerste gegenereerd worden, het is zo dat elke 4 weken de door de bungalow parken aangeven tijden kunnen veranderen, daarbij kunnen ze bijvoorbeeld zelf artiesten regelen voor bepaalde tijden. Dit heeft als gevolg dat de planning erg flezibel moet zijn.

Waar mijn eerste conclusie op uitkwam is dat ik dmv een random planning genereren (5000x ofzo) de beste eruit kan pikken.

Eventuele veranderingen (ben ik nu achter) zouden dan misschien het beste bekeken kunnen worden d.m.v. een GA omdat het niet reeel is om de planning voor 90 orocent te veranderen als de artiesten al gesettled zijn op een bepaald park.

Iets minder belangrijk is denk ik het feit dat ik het in php aan het schrijven ben, maarjah ik vermeld het toch even ;]

Oplossing op dit moment is dat ik werk met gigantische arrays met daarin de uitkomtst van de random generaties, daarop laat ik dan de voorwaarden los. Daaruit komt dan een 'beste' oplossing.

Ik wil alleen een kijken of het misschien beter kan d.m.v. een algoritme, maarjah, ik ben er onderhand dus ook al achter dat er geen waterdichte methode is.

Ik hoop dat dit het een beetje duidelijker maakt.

P.S. 7 bier op en drink nooit. Even wat moeiljik om goed na te denken.

[ Voor 76% gewijzigd door UltimateB op 17-01-2004 01:40 . Reden: ff 2e qoute copy pasten ]

[Macros]

Je moet eens kijken naar een (randomized) greedy algoritme (met locale optimalisatie). Dat is redelijk snel, efficient en simpel.

Wat je gewoon doet, je deelt een band in op zijn meest beste plek, dan pak je de volgende en die deel je in zo goed mogelijk totdat je alle bands hebt ingedeeld.
De laatste bands die je indeelt zullen niet zo optimaal zijn, dus dan moet je gaan schuiven. Dat noemen ze local optimization. Je probeerd dan het globale probleem op te lossen door een locaal voordeel na te streven. Dus probeer 2 bands te switchen of een band op te schuiven of iets dergelijks.
Als je op een gegeven moment geen optimalisatie meer kan vinden omdat door iets te schuiven ofzo het altijd slechter wordt en het globale probleem is nog niet afdoende opgelost, dan herstart je het algoritme alleen dan deel je de bands anders in maar op dezelfde methode. (Je deelt ze in random volgorde in)

[H!GHGuY]

hmm nu snap ik het probleem al wat beter...

waar ik meteen aan denk:
eerst en vooral maak je door middel van een genetisch algoritme of een ander naar keuze
de kortste route door alle parken.
dan kun je de bands die manueel vastgelegd worden erin stoppen, en zo die kortste route laten afleggen... (en zo hun planning opbouwen)
daarna kun je opvullen met de andere artiesten, rekening houdend met de andere voorwaarden, terwijl ze ook die kortste route zoveel mogelijk afleggen.

misschien wat moeilijker:
genereer eerst opnieuw de kortste route, en genereer dan telkens tussen 2 parken de kortste omweg VIA een ander park. en probeer dan op dezelfde manier zoals hierboven verder te werken: dit kan misschien handig zijn om breakshifts enz in rekening te houden
bvb:
park 1 en park3 liggen op kortste afstand, park2 is kortste omweg tussen 1 en 3
groep 1 speelt in park1
groep 2 in park3
groep 2 neemt breakshift/dagje vrij in park3
en daarom gaat groep 1 in park2 spelen voor ze dan hun trip verder zetten naar park3, terwijl groep 2 in park4 gaat spelen.

[chris]

OpifexMaximus schreef op 16 januari 2004 @ 21:39:
[...]

Hmmm, moet ik me er toch eens iets meer in gaan verdiepen, want elke AI-methode is in principe in staat een globaal optimum te vinden, alhoewel de agent in een lokaal optimum kan blijven steken.

Door middel van cross-over (recombinatie) en mutatie kan je ontsnappen aan lokale minima. Hierover is genoeg literatuur te vinden. Dit hoort volgens mij ook bij een standaard-implementatie.

Voor mensen (topicstarter?) die nieuwsgierig zijn waar dit toch allemaal over gaat: EC FAQ. Ik weet alleen niet zeker of het wel een goede oplossing is voor de topicstarter, aangezien je óf niet weet waar je mee bezig bent, óf je eerst helemaal moet inlezen (wat waarschijnlijk wel veel tijd kost). Maar als je die tijd hebt, is het zeker de moeite waard!

[UltimateB]

HIGHGuY schreef op 17 januari 2004 @ 14:07:
hmm nu snap ik het probleem al wat beter...

knip.

Mja, maar belangrijkste punt zijn speeldagen aangezien ze altijd voor 24 dagen betaald worden ongeacht hun werkelijke dagen.

Dag genetisch alchoritme lijkt me wel erg goed voor wijzigingen verwerken. Maandag heb ik ff een studiedag, ff kijken of ik ergens kan komen.

[chris]

Ultimateb schreef op 17 januari 2004 @ 15:27:
[...]
Dag genetisch alchoritme lijkt me wel erg goed voor wijzigingen verwerken. Maandag heb ik ff een studiedag, ff kijken of ik ergens kan komen.

Ehm, dat is natuurlijk niet alleen om wijzigingen te verwerken. Het is een heel algemeen algoritme, wat b.v. planningsproblemen op een optimale manier kan oplossen, in weinig tijd

[UltimateB]

Mja, maandag ga ik klooien.

[Verwijderd]

Ook goed bruikbaar is Simulated Annealing zoals al genoemd was, daarmee blijf je ook niet snel in lokale minima steken.

[Opi]

Ultimateb schreef op 17 januari 2004 @ 01:28:
Kan je ajb iets beter uitleggen wat je hiermee bedoeld? Dynamisch programeren? Ik begrijp je punt niet helemaal.

Dynamisch programmeren is gebaseerd op Markov beslissings processen in welke de ruimte van mogelijken middels acties verbonden is. Ik begin nu te twijfelen of deze methode te gebruiken is omdat er verschillende typen zijn zoals 'afstand' waarmee ik zo snel niet weet hoe je die kunt gebruiken. Anderzijds zou dit geen problemen op moeten leveren als het met GAs mogelijk is.

Graag zou ik op de hoogte gehouden willen worden van je werk.

[RickN]

chris schreef op 17 januari 2004 @ 15:35:
[...]


Het is een heel algemeen algoritme, wat b.v. planningsproblemen op een optimale manier kan oplossen, in weinig tijd

Correctie, het kan in korte tijd een benadering geven voor een optimaliserings probleem, die in veel gevallen verrasend dicht bij het optimum blijkt te liggen.

Geen enkele heuristische zoekmethode garandeert een optimaal resultaat en zal dat in de meeste gevallen ook niet geven.

[UltimateB]

Dicht bij optimaal is goed genoeg. Het zal het bedrijf heeeeel veel tijd / zorgen schelen en misschien is het nog beter dan dat er met de hand uit komt ;]

[Verwijderd]

RickN schreef op 17 januari 2004 @ 18:15:
[...]


Geen enkele heuristische zoekmethode garandeert een optimaal resultaat en zal dat in de meeste gevallen ook niet geven.

a*, best-first en nog vele andere garanderen een optimaal resultaat en zijn toch echt heuristisch

[RickN]

Verwijderd schreef op 17 januari 2004 @ 19:29:
[...]


a*, best-first en nog vele andere garanderen een optimaal resultaat en zijn toch echt heuristisch

Om misverstanden te voorkomen had ik wellicht beter over Local Search heuristieken kunnen spreken. Maar dat is wat meestal wordt verstaan onder heuristische zoekmethoden, zeker in een NP context.

[Glimi]

chris schreef op 17 januari 2004 @ 14:17:
Door middel van cross-over (recombinatie) en mutatie kan je ontsnappen aan lokale minima. Hierover is genoeg literatuur te vinden. Dit hoort volgens mij ook bij een standaard-implementatie.

Het is niet ondenkelijk dat je populatie steeds dichter bij elkaar komt te liggen, dat is zelfs het doel van GA. Verder kun je je mutatie alleen miniem nemen, omdat je anders te veel wijzigt in je pool, waardoor je je optimalisatie wegmuteerd.
In je stukken die je aanhaalt, zie ik daar niet veel over terugkomen.

[Verwijderd]

Probeer is gewoon een plannings-optimalisatie-probleem aan te pakken binnen EXCELL. Dit is vrij eenvoudig en hoef je niet al dat moeilijke geprogrammeer te doen. Zekers met een aantal plugins, die je zo van het net kunt halen. Anders heb ik ze wel voor je... Ben je met een half uurtje klaar..


Anton

http://web.eur.nl/fbk/dep/dep6/members/fielmich
Erasmus Universiteit Rotterdam

[Verwijderd]

Hoi ultimateb,

Stuur nog ff een reactie ben je mail kwijt heb spullen voor je.

Anton

[alienfruit]

Ik heb nog wel een roosterprogramma liggen ergens :):)

[curry684]

Verwijderd schreef op 29 januari 2004 @ 11:25:
Hoi ultimateb,

Stuur nog ff een reactie ben je mail kwijt heb spullen voor je.

Anton

pssst z'n ICQ en MSN staan gewoon in z'n profile hoor, en naar een MSN-id kun je ook mailen meestal )

[Tomatoman]

Je moet absoluut het volgende boek eens uit de bieb vissen (al was het maar om je literatuurlijst aan te vullen ):

Lawrence, Pasternack: Applied Management Science, A Computer-Integrated Approach for Decision Making, John Wiley & Sons Inc, 1998. ISBN 0-471-13776-6.

Ik neem een belangrijke definitie uit het boek over:

Management science is the scientific approach to executive decision making, which consists of

• The art of mathematical modeling of complex situations
• The science of the development of solution techniques used to solve these models
• The ability to effectively communicate the results to the decision maker.

Het boek zit vol met bedrijfseconomische voorbeelden, zoals de inzet van wachters bij een tolplein. Gedurende de hele dag varieert het verwachte aantal auto's dat bij het tolplein aankomt, zodat de personele bezetting van de tolpoortjes idealiter ook varieert. Helaas lukt dat niet, want iemand moet altijd een dienst van 8 uur draaien en dan een tijdje vrij zijn. Onnodig veel mensen inzetten kost natuurlijk veel geld, terwijl je enorme files krijgt als er niemand zit (en dat is niet toegestaan). In het boek worden methodes aangereikt om de optimale inzet van tolwachters te berekenen.

Alsjeblieft, hier is je documentatie

[UltimateB]

Nou jongens, het is allemaal niet meer nodig. Het is me gelukt om mijn stage te verknallen. Te vaak te laat gekomen...

Blijft wel interessant, dus ik zal nog eens rondkijken hiervoor, maar direct proberen/implementeren zit er niet in

[djluc]

Ultimateb schreef op 29 januari 2004 @ 17:39:
Nou jongens, het is allemaal niet meer nodig. Het is me gelukt om mijn stage te verknallen. Te vaak te laat gekomen...

Blijft wel interessant, dus ik zal nog eens rondkijken hiervoor, maar direct proberen/implementeren zit er niet in

Dat is wel balen, al is het dan toch nog je eigen schuld. Het is in ieders geval leuke materie om eens te proberen, misschien doe je het wel zo goed dat je het leuk kunt verkopen! In ieders geval veel succes

[Verwijderd]

ach als je ook op je volgende stage moeite hebt met uit je bed komen, en je hebt wel het planningsgrapje onder de knie, dan kun je daar tenminste indruk mee maken bij je stagebegeleider. Bedenk dat alle studenten moeite hebben met uit bed komen dus daar ben je niet uniek mee. Nu nog studenten die laat uit hun bed komen en iets kunnen. Daar zijn er veel minder van....


Anton

[Verwijderd]

curry684 schreef op 29 januari 2004 @ 12:25:
[...]

<small>pssst z'n ICQ en MSN staan gewoon in z'n profile hoor, en naar een MSN-id kun je ook mailen meestal )</small>

Nope msn gaat bij mij niet werken en icq al helemaal niet. Waarom niet, nou omdat ik die progjes niet gebruik.

Anton