[Matlab / abstract] Kies 1 combinatie uit alle mogelijke

[NickThissen]

Ik heb (in Matlab) een vector / array van 32 integers tussen de 1-100, bijvoorbeeld:
2, 3, 5, 8, 9, 15, ..., 89, 93, 97

Uit deze 32 getallen zou ik nu graag een subset van 20 getallen willen kiezen. Bijvoorbeeld:
2, 5, 9, ..., 97

Deze 20 getallen gebruik ik als input voor een algoritme dat een waarde uitspuugt, en die waarde wil ik optimalizeren.

Met Matlab kan ik in theorie alle mogelijke combinaties van 20 getallen berekenen via "nchoosek", maar dit zijn ongeveer 225 miljoen mogelijke combinaties: 32! / ( (32-20)! * 20!) = 225,792,840. Matlab kan me niet eens alle combinaties laten zien, laat staan dat ik ze allemaal zou kunnen proberen.

Wat ik nu wil doen is even "in gedachten" het lijstje met alle mogelijke combinaties genereren. Ook al is dit praktisch onmogelijk, je zou in gedachten het lijstje kunnen maken op een bepaalde volgorde (bijv de volgorde die Matlab via nchoosek aanhoudt). Nu wil ik een van deze combinaties uit deze lijst kiezen, met een bepaalde index (bijvoorbeeld in het midden, index 112896420. Op deze combinatie kan ik nu mijn algoritme loslaten, en daarna kan ik een nieuwe combinatie in de buurt van de vorige kiezen, bijvoorbeeld index 112896425 (5 combinaties verderop). En zo verder. Het idee van het "in de buurt kiezen" is dat ik niet zomaar combinaties at random ga kiezen (dit zou via 'randperm' kunnen denk ik), maar ik wil in de buurt van de optimale oplossing blijven en controle hebben over welke combinatie ik gebruik.


Een voorbeeldje met meer praktische waarden: stel ik heb 5 getallen (1 - 5) waaruit ik er 2 wil kiezen. De 10 mogelijke combinaties zijn dan "nchoosek(1:5,2)":
1: [1 2]
2: [1 3]
3: [1 4]
4: [1 5]
5: [2 3]
6: [2 4]
7: [2 5]
8: [3 4]
9: [3 5]
10: [4 5]

Nu kies ik "combinatie 5": [2 3]. Daarna wil ik een combinatie in de buurt pakken, bijv combinatie 7: [2 5], of combinatie 4: [1 5]. Het punt is: ik wil niet een random combinatie kiezen, maar ik wil controle hebben over welke combinatie. Als ik dus 8 keer achter elkaar combinatie 5 kies, dan krijg ik 8 keer dezelfde: [2 3], en niet 8 keer iets anders.


Is dit uberhaupt wiskundig mogelijk zonder alle mogelijke combinaties te genereren (wat dus niet praktisch is)? Zo ja, is er een manier waarop dit eenvoudig te implementeren is, of is er al een implementatie die ik niet kan vinden?

Ik gebruik momenteel Matlab maar een algemeen algoritme zou wellicht ook te implementeren zijn als het niet al te lastig is.

[MSteverink]

Stel dat je 3 uit 4 getallen zou trekken. Dan heb je de combinaties
1,2,3
1,2,4
1,3,4
2,3,4

Maar: je weet uit eerder onderzoek dat de combinatie 3,4 sowieso suboptimale resultaten gaat opleveren. Dan hoef je alleen nog maar
1,2,3 en
1,2,4
te optimaliseren.

Samengevat, kun je uit die reeks van 225mljn combinaties al combinaties uitsluiten, en zijn dat er zoveel dat dat zoden aan de dijk zet?

[NickThissen]

Nee, ik kan niet voorspellen of een combinatie optimale resultaten gaat opleveren of niet zonder de berekening daadwerkelijk te doen. De enige manier waarop ik de lijst zou kunnen verkleinen is door een random subset te pakken (met kans dat ik de beste al weg gooi).

Naast mijn huidige "optimalisatie" algoritme wat ik in gedachten heb (lijkt een beetje op simulated annealing denk ik) heb ik wel plannen om het op een fatsoenlijke manier te doen, bijv met een genetisch algoritme, echter zou ik graag iets eenvoudigers willen proberen voordat ik aan zo'n project begin.

Mocht het echt een enorm moeilijke opgave zijn om een bepaalde combinatie uit te kiezen dan geef ik het op en doe ik het anders, maar iets zegt me dat het wel mogelijk moet zijn.


Toevallig vind ik net dit script:
https://se.mathworks.com/...hange/7147-permn-v--n--k-

Dit lijkt bijna te doen wat ik wil, namelijk n permutaties uit een vector v, waarbij ik dan ook nog de index van de permutatie kan geven (k). Dit werkt en hiermee kan ik steeds een permutatie krijgen (ipv ze allemaal te berekenen), echter gaat het hier om permutaties en niet combinaties. Hij geeft dus ook permutaties terug waarbij hetzelfde getal meerdere keren voorkomt. Bijvoorbeeld voor permn(1:5, 2) is de eerste permutatie [1, 1], en de eerste combinatie (die ik wil) [1, 2]. Er mogen dus geen dubbele getallen in.

Nu zeg je natuurlijk "dan gooi je toch alle permutaties met duplicates eruit", maar dat kan dus niet omdat het er te veel zijn om ze allemaal te berekenen...

Ik begrijp het algoritme in dit script niet genoeg om te snappen of het aangepast kan worden, of dat er wellicht een compleet andere berekening nodig is...

[ Voor 4% gewijzigd door NickThissen op 16-02-2018 14:27 ]

[Skyaero]

Als je de Statistics toolbox hebt, kun je datasample gebruiken

code:

myArray = [ 1 , 2 ,3 ,5, 88, 99];
nDraw = 20;
y = datasample(myArray, nDraw,'Replace',false);

[NickThissen]

Skyaero schreef op vrijdag 16 februari 2018 @ 14:43:
Als je de Statistics toolbox hebt, kun je datasample gebruiken

code:

myArray = [ 1 , 2 ,3 ,5, 88, 99];
nDraw = 20;
y = datasample(myArray, nDraw,'Replace',false);

Nee hoor... Of mis ik iets? Datasample geeft een random sample. Als ik 3 keer datasample aanroep krijg ik 3 keer verschillende samples.

Ik wil een bepaalde combinatie uit alle mogelijke combinaties kiezen. Stel dat er 1000 combinaties zijn, dan wil ik bijvoorbeeld combinatie 283 kiezen, specifiek die ene combinatie (waarbij de 1000 mogelijke combinaties op een of andere manier gesorteerd zijn, maakt verder niet uit op welke manier als het maar steeds hetzelfde is).

Hoe kies ik in het geval van 'datasample' welke combinatie ik pak?

[donzz]

NickThissen schreef op vrijdag 16 februari 2018 @ 13:35:
Een voorbeeldje met meer praktische waarden: stel ik heb 5 getallen (1 - 5) waaruit ik er 2 wil kiezen. De 10 mogelijke combinaties zijn dan "nchoosek(1:5,2)":
1: \[1 2]
2: \[1 3]
3: \[1 4]
4: \[1 5]
5: \[2 3]
6: \[2 4]
7: \[2 5]
8: \[3 4]
9: \[3 5]
10: \[4 5]

Je wil dus van aan de hand van een index de bijbehorende combinatie bepalen.
Je kan uitrekenen hoeveel combinaties er zijn met 1, dat is namelijk selecteer 1 en voor de volgende getallen: 'kies er 1 uit de getallen 2 tot 5' = 4 combinaties. Is je index kleiner dan dat getal, dan zit 1 in de combinatie die je zoekt, en kan je dezelfde truuk toepassen voor elk volgend getal. Is je index groter dan dat getal, dan ga je verder bij 'kies er 2 uit de getallen 2 tot 5', etc.

[kunnen]

Simpele manier als beginpunt voor de optimalisatie zelf:
Wikipedia: Genetic algorithm

[ Voor 16% gewijzigd door kunnen op 20-02-2018 20:53 ]

[Morrar]

Volgens mij hangt alles af van de optimalisatie die je wilt doen en hoe je de waarde berekend. Als je dat goed kunt uitleggen kun je makkelijker op zoek gaan naar de beste combinatie. Je voorbeeld lijkt uit te gaan van lineaire verbanden.

Je zou bijvoorbeeld 100 (of 1000 of meer) willekeurige combinaties van getallen kunnen pakken en voor deze combinaties de uitkomstwaarde kunnen berekenen. Met bv een lineair regressie model kun je dan per positie het verband met de uitkomstwaarde berekenen.

De uitkomst kan bijvoorbeeld laten zien dat getal op positie 1 zo laag mogelijk moet zijn, want elke punt extra op positie 1 verlaagt de uitkomstwaarde met 1.4. Het getal op positie 2 moet juist zo hoog mogelijk zijn, want elke punt minder verlaagt uitkomstwaarde met 2.4 etc. Dit zijn gewoon de beta gewichten uit de regressie.

Vervolgens kun je de optimale combinatie makkelijk vinden met deze beta gewichten. Grootse positieve beta gewicht geef je het grootste getal uit de reeks van 32. Het grootste negatieve beta gewicht geef je het kleinste getal uit de reeks etc.

[ Voor 8% gewijzigd door Morrar op 20-02-2018 22:28 ]

[Janoz]

Waarom zou de volgorde die nchoosek geeft garanties geven dat 'dichtbijzijnde' permutaties een vergelijkbare score opleveren? Misschien kun je je beter focussen op een methode om een semi random dichtbijzijnde permutatie te genereren uit een (of meerdere) bestaande permutatie. Dan kun je gewoon een genetisch algoritme toepassen voor het zoeken naar de beste oplossing. Je moet dan alleen wel even in de gaten houden dat je niet in een lokaal optimum blijft hangen.