Plaseerauskone

Yleinen Fyysikkokiltaan ja fyysikkouteen liittyvä keskustelu
Post Reply
User avatar
Heikki Pulkkinen
Posts: 56
Joined: 09.07.2013 11:26

Plaseerauskone

Post by Heikki Pulkkinen » 05.02.2014 09:05

Moikka

Me tehtiin iltamme kuluksi Miffin kanssa Excel-taulukko, joka osaa tehdä plaseerauksia. Se ei tosin ole siinä vielä kovin hyvä. Liitetiedostossa näkyy, millaisen plaseerauksen kone teki Fuusio 66:lle.

Toimintaperiaate on suunnilleen tämä: Koneella on funktio, joka laskee yksittäisten ihmisten tyytyväisyyden tiettyihin vieruskavereihin. Se ottaa tyytyväisyyksien summan, käyttää sitä optimointialgoritmin tavoitefunktiona ja sen jälkeen luultavasti vaan sekoittaa pakkaa kunnes kaikki ovat kohtuullisen tyytyväisiä.

Mulla on kyllä paljon ideoita, miten tästä vois tehdä paremman. Mutta en usko, että ne kannattaa implementoida Excelillä. Ehkä Matlab olis tähän ongelmaan oikea softa?

Noh, jokatapauksessa haastan teidät tekemään ohjelmia, jotka tekee Fuusio 66:n paremman plaseerauksen.
Attachments
Plaseerauskone.xlsx
(133.9 KiB) Downloaded 219 times
Heikki Pulkkinen
041 437 7542
heikki.j.pulkkinen@gmail.com

Mikael Parmala1
Posts: 15
Joined: 19.10.2013 15:26
Contact:

Re: Plaseerauskone

Post by Mikael Parmala1 » 06.02.2014 18:38

Tässä matlab-koodinpätkiä, joka pyrkii optimoimaan plaseerausta, vieläkään ei ole kovin hyvä mutta pientä kehitystä nopeuden suhteen verrattuna excel-tiedostoon.

Toimintaperiate on samanhenkinen kuin alla mainitussa Heikin funktiossa sillä erolla, että tyytyväisyys lasketaan jokaisen pöydässä istuvan läheisyyteen verrattuna sekä avec otetaan huomioon kertoimella 10, kun muut toiveet kertoimella 1. Tämän lisäksi pöydän toisella puolella olevan henkilön hyötyfunktiota jaetaan puolella, jotta avecit suurella todennäköisyydellä päätyvät vastakksin. Optimointialgoritmi on toteutettu siten, että yksittäisiä henkilöitä heitetään randomilla päittäin ja katsotaan paraniko plaseeraus. Jos plaseeraus parani valitaan uusi plaseeraus pohjaksi ja arvotaan uusi pariskunta vaihdettavaksi.

Zipissä olevat tiedostot ovat iloisen kommentoimattomia, mutta tässä pikaiset kuvaukset tiedostoista.

hyoty.m:
Laskee saavutetun hyödyn tietyllä plaseerausjärjestyksellä. Tämän antamaa arvoa pyritään maksimoimaan.

plaseeraus.m:
Pääfunktio, rakentaa toivelistamatriisin josta hyötyjä aletaan laskea. Tekee sivistyneen alkuarvauksen (Peräkkäin ilmonneet usein samasta seurueesta). Sylkee ulos matriisit A ja B, joista A kertoo kuinka suuren hyödyn kukin sai ja B pöytäjärjestyksen.

test.csv:
Fuusio 66, ilmoittautumisen lievästi parsittu data.

testMain.csv:
Ajaa plaseerausfunktion x kertaa ja tallentaa tulokset.

testi_optimointi.m:
Optimointifunktio, valitsee x kertaa 2 ihmistä, jos saavutetaan hyötyä vaihtamalla nämä kaksi henkilöä päittäin siirretään ne päittäin ja nollataan x:n laskuri. Jos laskuri saavuttaa x:n lopetetaan ajo ja palautetaan saatu pöytäjärjestys.

Selkeitä ongelmia ovat ainakin:
-Optimointi hyvin epämääräistä, riittävän suurella ajomäärällä kuitenkin suurin osa ongelmista pitäisi kadota ja optimaalinen tulos löytyä.
- Ratkaisu(?): optimointialgoritmi, joka ensin pyrkii vaihtamaan suuren joukon ihmisiä keralla päittäin ja tilanteen parantuessa säilyttää uuden pöytäjärjestyksen. Ja kun saavutetaan riittävän hyvä alkuarvaus siirrytään vaihtelemaan yksittäisiä ihmisiä päittäin.

-Ilmoittautuneiden ilmoittautumisten parsiminen, usein ilmoittautumiset ovat hyvin vapaamuotoisesti kirjoitettuja, joten niiden koneellinen lukeminen on hankalaa.
- Ratkaisu(?): Pakotetaan ilmoittautumisvaiheessa ihmisten pöytätoiveet useammille riveille ja tiettyyn formaattiin. Tämän jälkikäteen koneellisesti käsitteleminen on kuitenkin lähes mahdoton ongelma. Voidaan myös hoitaa siten että skriptin käyttäjät itse kirjoittavat toiveet järkevämpään muotoon.

-Useiden pöytien ongelma
- Ratkaisu(?) pöytien yli ei vertailla hyötyä ja annetaan vapaat kädet muodostaa matriisi (N x (M_i x 2)) pöydille, missä N on pöytien määrä ja M_i on pöytien leveys. Optimointi suoritetaan kuitenkin kaikkien pöytien ylitse.


Kaiken kaikkiaan, jos haluaa yksinkertaisen kohteen miten tätä voi lähteä kehittämään niin Optimointialgoritmi ja Parsiminen tarjoavat selkeimmät lähtökohdat tälle.

-Miffi
Attachments
plaseeraus.zip
(4.14 KiB) Downloaded 149 times

User avatar
Heikki Pulkkinen
Posts: 56
Joined: 09.07.2013 11:26

Re: Plaseerauskone

Post by Heikki Pulkkinen » 06.02.2014 21:40

Kerrassaan mielenkiintoinen ratkaisu! Mietin ehkä myöhemmin uusia ratkaisuja tiedossa oleviin puutteisiin. Nyt en kuitenkaan voi kontribuoida muuten kuin ongelmalla:
- Kun kaksi avecia päätyvät toisiaan vastapäätä, kumpaakaan ei voi enää siirtää (paitsi keskenään). Tämä tapahtuu siksi, että mikään muu ei riitä korvaamaan sitä, että menetetään avecien antama 20 yksikön hyöty.
Heikki Pulkkinen
041 437 7542
heikki.j.pulkkinen@gmail.com

Mikael Parmala1
Posts: 15
Joined: 19.10.2013 15:26
Contact:

Re: Plaseerauskone

Post by Mikael Parmala1 » 06.02.2014 21:51

Hmm,

Olet aivan oikeassa. Mahdollinen ratkaisu mainitsemaasi ongelmaan on ensin optimoida yksittäisiä ihmisiä ja tämän jälkeen ottaa uusi kierros, jossa otetaan vastakkaiset ihmiset ja pyritään samanhenkisellä metodilla (tai tylysti yksittäin kaikki läpikäyden) etsimään paras mahdollinen sijainti heille.

Mikael Parmala1
Posts: 15
Joined: 19.10.2013 15:26
Contact:

Re: Plaseerauskone

Post by Mikael Parmala1 » 09.02.2014 03:44

Jälleen pientä kehitystä asian suhteen.

Jaoin funktiot useampaan moduuliin, jotta yksittäisten moduulien muokkaaminen on yksinkertaisempaa.

Tärkein muutos on se, että sen sijaan että olisi yksittäisiä .m tiedostoja, joissa tehdään koko yksittäinen optimointirutiini siirsin kehitetyt optimointirutiinit omiksi funktioikseen. Tämän lisäksi aloin sekoittaa englantia ja suomea, jotta koodi olisi mahdollisimman hankalaa luettavaa.

Nämä optimointifunktiot ovat:

Single_optimization.m
- Arpoo kaksi ihmistä, katsoo saadaanko niiden paikkoja vaihtamalla parannettua lopputulosta

Pairwise_optimization.m
- Arpoo kaksi paria, jotka istuvat toisiaan vastapäätä vaihtaa näiden sijainnit ja tarkistaa paraniko asettelu.

percentage_optimization_low_to_high.m
- Arpoo kaikista ihmisistä x prosenttia ja vaihtaa näiden paikkoja keskenään. Jos tulos paranee tallennetaan uusi tulos. Esim. Jos low = 0.1 ja high = 0.5 ja step = 0.2 arvotaan ensin 10% ihmisistä joiden paikkoja vaihdetaan, sitten 30% ihmisistä joiden paikkoja vaihdetaan ja lopulta 50% ihmisistä joiden paikkoja vaihdetaan.

percentage_optimization_high_to_low.m
- Arpoo kaikista ihmisistä x prosenttia ja vaihtaa näiden paikkoja keskenään. Jos tulos paranee tallennetaan uusi tulos. Esim. Jos low = 0.1 ja high = 0.5 ja step = 0.2. Arvotaan ensin 90% ihmisistä, joiden paikkoja vaihdetaan, sitten 70% ja lopulta 50%.

Kaksi viimeksi mainittuja olivat lieviä pettymyksiä eivätkä toimineen ollenkaan siten kuten olisin toivonut (hitaita ja tehottomia). Säilytin ne kuitenkin tässä sillä niillä voi olla myöhempää käyttöä. Toistaiseksi parhaimmat tulokset ovat tulleet tekemällä kahdella ensimmäisellä funktiolla ajot: Single - Pair - Single

Näiden optimointifunktioiden lisäksi päätin siirtää hyötymatriisin muodostamisen ulos plaseeraus.m filusta omaksi toivematriisi.m funktioksi. Tämä siksi että nyt voi kustomoida halutessaan toivematriisin muokkausta eikä tarvitse muuttaa koko tiedostoa. Tähän otettiin myös vuosikurssit huomioon kun se data nyt sattui olemaan tarjolla.

Muita muutoksia on lähinnä testidataan:
- Edited.csv sisältää uuden csv listan, jossa on parsittu fuusion toiveista lista asioita joita ihmiset olivat etusijalla toivoneet. Tämä siksi että nähdään miten systeemi toimii kun on useampia toteuttamiskelpoisia toiveita.
- Testmain.m ajaa plaseeraus.m tiedoston n kertaa ja tallentaa saadut tulokset. Tämän lisäksi se mittaa kuinka kauan funktion pyörittämiseen meni kaiken kaikkiaan.


Tulevat huomioonotettavat asiat:

Optimointifunktiot:
- Funktio joka tarkastelee lähimmät pisteet jokaiselle tyypille ja töinäisee sitä askeleen verran jos parannusta on saatavissa.

Hyötymatriisi:
- Mies-Nais asettelun aikaansaaminen. Sujunee sillä että antaa jokaiselle miehelle naista kohtaan painokertoimen +0.5 ja naiselle miestä kohtaan +0.5, jolloin automaattinen plaseeraus haluaa asettaa ne vierekkäin. Ongelma on lähinnä, että kummat pistää binäärissä nolliksi ja kummat ykkösiksi.
- Toiveiden parsimisen automatisointi(?). Vaikuttaa huomattavan hankalalta verrattuna siihen että vaan tylysti pistää ihmisen yhtenäistämään toivedatan
- Useampien toiveiden huomioon ottaminen, pitäisi olla kohtuu yksinkertainen, toiveet erotetaan pilkuilla ja ykköstoive saa painokertoimen 1 kakkostoive painokertoimen 1/2 jne.
Attachments
plaseeraus.rar
(4.97 KiB) Downloaded 154 times

Mikael Parmala1
Posts: 15
Joined: 19.10.2013 15:26
Contact:

Re: Plaseerauskone

Post by Mikael Parmala1 » 12.02.2014 20:28

Terve,

Jälleen on käytetty aivan liikaa tunteja tämänkin tekemiseen, mutta nyt on tapahtunut seuraavat asiat.

"Tukee" rinnakkaisajoa, eli tein ensimmäisestä for-loopista parfor-loopin. Tämä sitten varaa niin monta threadia kuin vain käsiinsä saa eli saattaa aiheuttaa jännyyksiä. Koulun windows-koneilla hoitaa workerien varaamisen itsekseen. unix-koneilla pitää ilmoittaa kuinka monta threadia haluaa uhrata tälle antamalla käsky matlabpool(N), missä N on haluttu threadien määrä. Koshilla toimii ainakin N = 2 (Toim. Huom. Älkää ajako tätä koshilla)

Mies-Nais plaseeraus otetaan huomioon Hyöty-funktiossa. Käytännössä jos nainen osuu naisen paikalle tai mies miehen paikalle saa hän hyötyfunktioonsa +10 muiden juttujen lisäksi, jolloin tämä plaseeraus yltää pöytätoiveiden kanssa samalle tasolle kun istutaan vastakkain, mutta muuten tämä ajaa pöytätoiveiden ylitse. Ja tämän takia edited.csv on nykyään edited2.csv, käsin kirjoittelin kuka on nainen ja kuka on mies.

Parittomat sitsit, jos ilmoittautuneita on ei-parillinen määrä ilmestyy mukaan "Empty" kaveri, joka ei anna hyötyä kenellekään eikä saa hyötyä mistään.

Pari uutta optimointifunktiota:

Single_optimization_thermal.m:

Toimii muuten melko samalla tavalla kuin Single_optimization.m, eli arpoo kaksi kaveria ja hyväksyy muutoksen jos siitä seuraa suurempi hyöty kuin aikaisemmasta plaseerauksesta. Mutta tämän lisäksi funktio ei hylkää kaikkia jossa hyöty pienenee vaan hyväksyy todennäköisyydellä exp(Delta(hyöty)/T) nekin. Tällöin funktio pääsee pois lokaaleista minimeistä tietyllä todennäköisyydellä. Kun N kierrosta on ajettu tätä T = T*0.9, jolloin todennäköisyys hyväksyä negatiiviset muutokset pienenee.

Funktion lopetusehtona toimii kun N:stä kierroksesta 10 tai alle muutosta hyväksytään.

Pairwise_optimization_thermal.m:
Sama kuin yllä mutta pareittain Pairwise_optimization.m henkeen, eli valitaan kaksi paria ja vaihdetaan niiden paikkoja ja hyväksytään tietyllä tn:llä.

Toimivat oikein mainiosti ja antavat toistaiseksi parhaimmat tulokset. Ongelmana kuitenkin funktioiden hitaus.


Single_optimization_no_random.m:
Etsii paikallisen maksimin. Tekee hieman höpsösti tämän eli ottaa ensimmäisen tyypin, katsoo kaikki läpi, jos parempi löytyy vaihdetaan päittäin ja aloitetaan taas alusta.
Eli esim. ensin otetaan paikan 1 henkilö verrataan kaikkiin muihin henkilöihin, jos parempaa järjestystä ei löydy, siirrytään paikan 2 henkilöön. Paikan 2 henkilölle tehdään sama vertailu, mutta tällä kertaa löydetään jotain -> vaihdetaan päittäin ja palataan takaisin paikkaan 1. Eli ei etsi maksimia jokaiselle vaan etsii seuraavan joka antaa maksimin.

Pairwise_optimization_no_random.m:
Kuin Single, mutta vertailee pareittain.

Nämä ovat melkoisen huonoja funktioita yksinään sillä löytävät vain lokaalin maksimin, mutta kannattaa ajaa loppuun sillä silloin löytää sen varmasti eikä jää sen ulkopuolelle.


ToDo:
- Useampien toiveiden laskeminen toivematriisiin.
- Siirtyminen käyttäjän määrittämiin eri-pituisiin pöytiin, vaatii hieman mielikuvitusta ja käytännössä täydellisen overhaulin funktioiden toimintaan, mutta toteutettavissa.
- C-koodin vääntäminen koko härpäkkeestä, jolloin optimointi sujuisi nopeammin. (Vasta kun ollaan testattu että toimii matlabilla fiksusti...)
- Nykyisistä funktioista optimaalisimman kombon etsiminen tai uusien kehittäminen.


Joitain muitakin muutoksia saattoi olla, mutta en niitä muista.
Attachments
12_02_2014.rar
(7.3 KiB) Downloaded 147 times

Mikael Parmala1
Posts: 15
Joined: 19.10.2013 15:26
Contact:

Re: Plaseerauskone

Post by Mikael Parmala1 » 13.02.2014 00:10

Ja nyt vehje toimii N:llä eri kokoisella pöydällä ja ilmoittaa, jos kaikki sitseille ilmoittautuneet eivät mahdu näihin pöytiin. (Jonka jälkeen dumppaa viimeiset nimet ja jatkaa ilman niitä)

Ehdin toteuttaa vasta yhden funktion, joka on melko kämäinen yksin ajettuna, mutta näyttää että idea toimii. Useamman pöydän lisääminen lisää mahdollisia lokaaleja maksimeja, joten tämä systeemi on vielä entistä epävarmempi, joten kysyntää paremmille optimointialgoritmeille on.

Nyt toteutettu optimointialgoritmi on Single_optimization.m. Ajoaika .rar:in sisältämillä tiedostoilla kun koshilla käyttää kahta lankaa on noin 60-120 s. (Johtaa typeriin lopputuloksiin ja tämä on tiedossa oleva feature, joka korjataan tulevissa versioissa)

Testaus on hyvin puuttellista, joten ilmoittakaa jos löydätte jotain bugeja tästä koodista.
Attachments
PlaseerausM.rar
(4.2 KiB) Downloaded 176 times

Post Reply