2 zufällige Objekte gewichtet auswählen

Für Fragen zur Programmiersprache auf welcher Lazarus aufbaut
Antworten
Komoluna
Beiträge: 565
Registriert: So 26. Aug 2012, 09:03
OS, Lazarus, FPC: Windows(10), Linux(Arch)
CPU-Target: 64Bit

2 zufällige Objekte gewichtet auswählen

Beitrag von Komoluna »

Liebes Forum,

der Titel ist vielleicht ein wenig verwirrend, also hier mein Problem:

Ich habe ein unsortiertes Array mit Objekten, die alle eine Wichtung haben:

Code: Alles auswählen

Objekt = class
  Wichtung: Single;
end;
 
var MyArray: array of Objekt;

nun möchte ich zufällig aus meinem Array 2 (verschiedene) dieser Objekte auswählen, deren Auswahlwahrscheinlichkeit ihrer Wichtung entspricht:

Code: Alles auswählen

P(Auswahl) = W / (W(0)+W(1)+...+W(n))
.
Leider habe ich jedoch keine Ahnung, wie man das realisieren könnte.

Habt ihr Vorschläge, wie man da rangehen kann?
(Ich möchte keinen fertigen Code, sondern Konzepte/Ideen)

MFG

Komoluna

P.S.: Ich brauche diese Auswahl für einen Genetischen Algorithmus, wo 2 Objekte nach ihrem Fittnesswert ausgewählt und gekreuzt werden.
Programmer: A device to convert coffee into software.

Rekursion: siehe Rekursion.

Michl
Beiträge: 2505
Registriert: Di 19. Jun 2012, 12:54

Re: 2 zufällige Objekte gewichtet auswählen

Beitrag von Michl »

Wenn ich dich richtig verstanden habe:

Falls du z.B. 10 Faktoren hast, hätten alle Faktoren zusammen eine Summe. Diese entspricht zusammen 100% Wichtung (ob du das in Proztent, Promille, 1 oder sonstwie rechnest, ist dir überlassen).

In Prozent:

Hätte der Faktor 1 eine Wichtung von 5%, Faktor 2 von 7%, Faktor 3 von 16% etc. (zusammen 100%) würde bei einer Zufallszahl von 0 bis 99 jeder Treffer einem Faktor entsprechend seiner Wichtung genommen werden:
Faktor 1: 5% -> Zufallsbereich (0..4)
Faktor 2: 7% -> Zufallsbereich (5..11)
Faktor 3: 16% -> Zufallsbereich (12..27)
...

Code: Alles auswählen

type
  TLiveSelection = (lsMoney, lsChilds, lsTime);
  TLive = Array[0..1] of TLiveSelection; 

Komoluna
Beiträge: 565
Registriert: So 26. Aug 2012, 09:03
OS, Lazarus, FPC: Windows(10), Linux(Arch)
CPU-Target: 64Bit

Re: 2 zufällige Objekte gewichtet auswählen

Beitrag von Komoluna »

erstmal danke für die Antwort.

So weit war ich auch schon. Es scheitert bisher an der Evaluierung, welches Objekt zu Zufallszahl X gehört.
Ich habe dann ja einen Zahlenstrahl, wo die Objekte von verschieden großen Abschnitten repräsentiert werden.
Ich kriegs nur noch nicht gebacken rauszufinden, in welchem Abschnitt sich die zufällig gewählte Zahl befindet.

MFG

Komoluna
Programmer: A device to convert coffee into software.

Rekursion: siehe Rekursion.

Scotty
Beiträge: 768
Registriert: Mo 4. Mai 2009, 13:24
OS, Lazarus, FPC: Arch Linux, Lazarus 1.3 r44426M FPC 2.6.4
CPU-Target: x86_64-linux-qt/gtk2
Kontaktdaten:

Re: 2 zufällige Objekte gewichtet auswählen

Beitrag von Scotty »

Bei einer Zufallsauswahl erzeugt man am besten zuerst eine Liste von Werten und zieht dann im Ablauf nacheinander einzelne Werte und löscht diese entweder oder geht die Liste systematisch durch.

Ansonsten ist diese Seite vielleicht von Interesse für dich: http://wiki.freepascal.org/Generating_Random_Numbers

Horst_h
Beiträge: 72
Registriert: Mi 20. Mär 2013, 08:57

Re: 2 zufällige Objekte gewichtet auswählen

Beitrag von Horst_h »

Hallo,

michl hat das doch schon richtig angedeutet.Du musst nur noch eine Summenwahrscheinlichkeit berechnen { und diese auf 0..1 skalieren, EDIT muss man nicht, sondern die maximale Summe merken } , dann kannst Du mit binärer Suche finden.
Ich habe mal eine Code-Schnipsel für Freepascal gepinselt.

Code: Alles auswählen

const
  oBcnt = 1024*1024;
type
  tWiIdx    = 0..oBcnt-1;
  tSumWiIdx = 0..oBcnt;
  tWicht = array[tWiIdx] of double;
  tSumWi = array[tSumWiIdx] of double;
var
  Wichtungen : tWicht;
  SumWi      : tSumWi;
 
procedure InitWicht(var WI : tWicht);inline;
var
  i : NativeInt;
begin
  For i in tWiIdx do
    Wi[i] := random;
end;
 
function InitSumWi(var WI : tWicht;var SWi: tSumWi):double;
var
  i : NativeInt;
  SumWi: double;
begin
  SWi[0] := 0.0;
  SumWi := 0.0;
  For i in tWiIdx do
  Begin
    SumWi := Sumwi+WI[i];
    SWi[i+1]:= Sumwi;
  end;
  InitSumWi:= Sumwi;
end;
 
function FindObj(x :double;var SWi: tSumWi):tWiIdx;
// Gibt den Index auf das passende Objekt zurueck
var
  l,m,u: NativeUint;
Begin
  l := Low(tSumWi);
  u := High(tSumWi);
  m := (l+u) DIV 2;
  repeat
    if (x>=SWi[m]) then
      l := m
    else
      u := m;
    m := (l+u) DIV 2;
  until (m=l) OR (m=u);
  IF x-SWi[m]< 0.0 then
    Writeln(m,'Fehler',SWi[m]:10:7,x:12:10);
  FindObj:= m;
end;
 
var
  MaxSumwi,x: double;
  i: NativeInt;
Begin
  randomize;
  InitWicht(Wichtungen);
  MaxSumwi:= InitSumWi(Wichtungen,SumWi);
  For i := 1 to 1000000 do
    FindObj(MaxSumwi*Random,SumWi);
 
  x := 0.0000*MaxSumwi;
  i :=  FindObj(x,SumWi);
  writeln(x:12:4,i:8,SumWI[i]:12:4,SumWI[i+1]:12:4);
 
  x := 0.5*MaxSumwi;
  i :=  FindObj(x,SumWi);
  writeln(x:12:4,i:8,SumWI[i]:12:4,SumWI[i+1]:12:4);
 
  x :=  MaxSumwi;
  i :=  FindObj(x,SumWi);
  writeln(x:12:4,i:8,SumWI[i]:12:4,SumWI[i+1]:12:4);
end.

Mit der Ausgabe:

Code: Alles auswählen

 time ./test
      0.0000       0      0.0000      0.6751
 261993.2758  524240 261992.5269 261993.4640
 523986.5516 1048575 523986.5322 523986.5516
real  0m0.445s
 

Die 1'000'000 Suchen sind also recht fix.Ich habe keine 8 MB Level 2 oder gar 3 Cache.Für eine Suche werden bei 2^20 Elementen auch immer 20 Schritte gebraucht.
Wie man jetzt aber verhindern will, dass nicht zweimal das selbe gewählt werden kann, ist dann aber viel aufwendiger.


Gruß Horst

Antworten