Entwickler-Ecke

Algorithmen, Optimierung und Assembler - Optimierung Rucksackproblem


Pr0g3r - Do 20.05.10 14:44
Titel: Optimierung Rucksackproblem
Hallo Leute,

Wir schreiben eine Projektarbeit über das Rucksackproblem. Wir suchen aber neben den evolutiönären und den dynamischen Algorithmus noch weitere Optimierungen. Kann mir jemand evtl einen link schicken oder das ganze gleich posten?
Bin für jede hilfe dankbar


Moderiert von user profile iconNarses: Topic aus Sonstiges (Delphi) verschoben am Do 20.05.2010 um 15:56


bummi - Do 20.05.10 14:49

http://de.wikipedia.org/wiki/Rucksackproblem


Pr0g3r - Do 20.05.10 14:51

wie oben beschrieben, haben wir das dynamische schon ... -.-


Gausi - Do 20.05.10 14:55

Hallo und :welcome: in der Entwickler-Ecke,

Mir stellt sich dann erstmal die Frage: Gibt es überhaupt noch andere "Optimierungen" dafür? Muss das unbedingt optimal gelöst werden, oder könnt ihr auch Näherungsverfahren (Greedy) besprechen und zeigen, dass ein Greedy-Ansatz (nicht?) beliebig schlecht sein kann?


Pr0g3r - Do 20.05.10 15:00

Ich weiß nicht, ob es noch Optimierungen gibt. Greedyverfahren sind auch ok, das Evolutionsverfahren gibt ja auch nicht immer die exakte Lösung aus.
Am Ende wollen wir ein Paar Verfahren vergleichen und dann gucken, welches am schnellsten und besten ist.


Hidden - Do 20.05.10 18:16

hi :)

Sehr ergiebig, ist auch oftmals die Betrachtung der Englischen [http://en.wikipedia.org/wiki/Knapsack_problem] und Deutschen Wikipedia: Während die Deutsche sehr genau und kurz ist, ist die Englische oftmals etwas umfangreicher.

lg,


Pr0g3r - Do 20.05.10 19:50

"George Dantzig proposed (1957) a greedy approximation algorithm to solve the unbounded knapsack problem. His version sorts the items in decreasing order of value per unit of weight, vi / wi. It then proceeds to insert them into the sack, starting with as many copies as possible of the first kind of item until there is no longer space in the sack for more. Provided that there is an unlimited supply of each kind of item, if m is the maximum value of items that fit into the sack, then the greedy algorithm is guaranteed to achieve at least a value of m / 2. However, for the bounded problem, where the supply of each kind of item is limited, the algorithm may be far from optimal."

Bedeutet das jetzt, dass er für jedes Element das Verhältnis wert zu Masse berechnet hat und dann solange die mit dem besten Verhältnis in den Sack gestopft hat, bis er voll ist?


Kha - Do 20.05.10 19:57

Exakt :) .


Pr0g3r - Do 20.05.10 20:01

Ich hab es mal programmiert, es funktioniert tatsächlich ganz gut. Hat bei 1.000.000 ELementen mit einer Gewichtsbeschränkung von 2.000.000 1.998.999 rausbekommen.
Gibt es noch andere Methoden?


Horst_H - Fr 21.05.10 12:12

Hallo,

und was heißt das:
Zitat:
mit einer Gewichtsbeschränkung von 2.000.000 1.998.999 rausbekommen.

Waren die übrig geblienbenen Elemente jetzt alle schwerer als 2.000.000-1.998.999=1001 kg?
Sonst hätte mindestens eins noch Platz gehabt.

Gruß Horst
Ok, negativer Wert wäre noch eine Möglichkeit, stände aber bestimmt nicht auf der Liste


gfoidl - Fr 21.05.10 12:57

Hallo,

Zitat:
Wir suchen aber neben den evolutiönären und den dynamischen Algorithmus noch weitere Optimierungen.

Simulated Annealing [http://www.mycsharp.de/wbb2/thread.php?threadid=78641] könnte auch dafür verwendet werden. Und somit auch alle verwandten wie der Sintflutalgorithmus, etc.


mfG Gü


Hidden - Fr 21.05.10 13:30

Oder negative Masse :D Da würde der Algo sogar einen kolossalen Fehler machen =D


Pr0g3r - Fr 21.05.10 14:46

Danke erstmal für eure Hilfe :D

user profile iconHorst_H hat folgendes geschrieben Zum zitierten Posting springen:
Hallo,

und was heißt das:
Zitat:
mit einer Gewichtsbeschränkung von 2.000.000 1.998.999 rausbekommen.

Waren die übrig geblienbenen Elemente jetzt alle schwerer als 2.000.000-1.998.999=1001 kg?


Damir war gemeint, dass das Tragelimit bei 2.000.000 lag und der Algorithmus hat 1.998.999 rausbekommen. Ich habe die Liste in einer For-Schleife mit Array[Schleifenvariable].wert = Schleifenvariable. VOn da her war kein Element mit 1001 kg mehr frei. Daswegen finde ich, dass das für eine Nährungslösung eigentlich gar nicht schlecht ist.
Laut wikipedia [http://de.wikipedia.org/wiki/Schwellenakzeptanz]ist der Sinnflutalgo genauer als das simulierte abkühlen.
Der ist so beschrieben:

"
Wähle einen anfänglichen Schwellwert T > 0
Wähle einen Schwellwertfaktor TF (0 < TF < 1)
Wähle eine Zahl von Probierschritten Zmax
Wähle eine anfängliche Konfiguration C
Referenzlösung C_ref := C
Wiederhole bis Abbruchbedingung erfüllt
Wiederhole Zmax mal
Wähle neue Konfiguration C' (ausgehend von C)
Falls Qualität(C´) > Qualität(C_ref)
C_ref := C´
dQ := Qualität(C') - Qualität(C)
Falls dQ > -T
C := C'
T := T * TF
Gib C_ref aus
"

Was ich noch nicht verstehe ist, wie man am Anfang Zmax festlegt. :gruebel:


gfoidl - Fr 21.05.10 15:29

Hallo,

Zitat:
Laut wikipedia ist der Sinnflutalgo genauer als das simulierte abkühlen.

Das kommt schon sehr auf die Wahl der Parameter an. Nur weil in Wiki steht:
Zitat:
Experimente der Erfinder deuten außerdem darauf hin, dass die Schwellenakzeptanz unter vergleichbaren Bedingungen häufig qualitativ bessere Lösungen liefert als die simulierte Abkühlung.
heißt das noch nichts. Die Erfinder werden ja auch nicht ihrer Erfinden den Nachzug geben :lol:

Zmax ist eben so ein Parameter der festgelegt werden muss. Die korrekte Wahl kann nur durch Probieren ermittelt werden.


mfG Gü


Pr0g3r - Fr 21.05.10 15:31

und wie probiert man das aus?


gfoidl - Fr 21.05.10 15:49

user profile iconPr0g3r hat folgendes geschrieben Zum zitierten Posting springen:
und wie probiert man das aus?


  1. nimm eine Zahl
  2. führe den Algorithmus aus
  3. ist das Ergebnis zufriedenstellend? Falls ja Ende des Probierens, falls nein gehe zu Punkt 1


SCNR :D


mfG Gü


Pr0g3r - Fr 21.05.10 15:52

mmh :|
gibt es da nichts eleganteres, womit man am Anfang berechnen kann, wie viele Durchläufe man ca braucht?


gfoidl - Fr 21.05.10 17:03

Hallo,

das wäre super - aber das gibts bei keinem heuristischen Algorithmus. (Sonst wäre diese ja fast überflüssig wenn die Anzahl der Iterationen bekannt ist).

Du kannst aber in der Literatur für Empfehlungen o.ä. suchen.

mfG Gü


Pr0g3r - Fr 21.05.10 17:17

Ich hab mal geguckt, aber leider nichts gefunden :cry:
vielleicht 2^irgendwas? (ist es ja meistens :wink: )


Hidden - Fr 21.05.10 17:39

Hi :)

Dabei lässt sich sicherlich - unter Annahme zufälliger Gegenstände - ein Erwartungswert angeben. Dieser kann aber durch die vermutlich relativ starke Streuung auch sehr nutzlos ausfallen.

Erfahrungsgemäß ist der Rechenaufwand für die nächsthöhere Anzahl von Iterationen dabei aber so viel höher, dass selbst die vorherige Berechnung aller kleinerer Iterationsstufen noch nicht zu inem merklichen Anstieg der Rechenzeit führt.
So auch beim Schach, wo die Anzahl der vorausberechneten Halbzüge zwar stufenweise erhöht wird, aber für jede weitere Stufe alle vorherigen Berechnungen komplett neu durchgeführt werden.
Ob das bei deinem Algo so ist, hängt vom Anstieg der Rechenzeit mit der Iterationsanzahl ab. Für Schach ist das proportional zum Verhältnis von Blättern zu Knoten, und es existieren in einem Baum [http://de.wikipedia.org/wiki/Baum_%28Graphentheorie%29] sehr viel mehr Blätter als Knoten.

lg,


Pr0g3r - Di 25.05.10 16:25

Könnte ich die schleife nicht endlos laufen lassen und Zmax einfach ignorieren/rauslassen?


Hidden - Di 25.05.10 16:58

Hi :)

Du könntest mit einem Timer zur Anschauung die Genauigkeit(also ZMax) immer weiter schrittweise erhöhen.

Wenn du die Optimierungslösung aber für irgendwas anwenden willst, musst du wohl oder übel irgendwann aufhören :lol: Du kannst dein Geld schließlich auch nicht einfach immer weiter anlegen, nur weil es immer mehr wird :nixweiss:

lg,


Pr0g3r - Di 25.05.10 17:13

Kann ich nicht in der Abbruchsbedingung festlegen, wann er aus der Schleife raus soll?


Hidden - Mi 26.05.10 01:53

Hi :)

Das Ganze soll ja in nachvollziehbar kleinen Schritten ablaufen, daher dachte ich an einen Timer. Die Anzahl der Berechnungen pro Sekunde könnte ja dann exponentiell bis polynormal zunehmen.

Eine Schleife muss in jedem Fall in regelmäßigen Abständen die Prozedur Application.ProcessMessages; enthalten, sonst reagiert das Anwendungsfenster nicht mehr.

Meine Lösung:

Delphi-Quelltext
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:
22:
23:
24:
25:
26:
27:
28:
29:
30:
31:
32:
33:
34:
35:
36:
37:
38:
39:
40:
41:
42:
43:
44:
45:
46:
47:
48:
49:
50:
type
  TForm1 = class (TForm)
    BtnStart: TButton;
    BtnAbort: TButton;
    TmrCalc: TTimer;
    procedure BtnStartClick(Sender: TObject);
    procedure BtnAbortClick(Sender: TObject);
    procedure TmrCalcTimer(Sender: TObject);
  private
    FStartzeit: TTime;
    FIterationsPerSecond: Integer;
    FIterationsTodo: Extended;
    procedure ContinueCalculation;
  {..}
  end;

implementation

{..}

procedure TForm1.BtnStartClick(Sender: TObject);
begin
  BtnStart.Hide;
  FStartzeit := Now;
  TmrCalc.Enabled := true;
  BtnAbort.Show;
end;

procedure TForm1.BtnAbortClick(Sender: TObject);
begin
  BtnAbort.Hide;
  TmrCalc.Enabled := false;
  BtnStart.Show;
end;

procedure TForm1.TmrCalcTimer(Sender: TObject);
const MaxItarations = Sqrt(MaxInt);
begin
  FIterationsPerSecond := Sqr(Second(Now - FStartzeit));
  FIterationsTodo := FIterationsTodo + FIterationsPerSecond * TmrCalc.Interval / 1000;
  if IterationsTodo > MaxIterations then begin
    FIterationsTodo := 0;
    FStartzeit := Now;  //Neustart, Rechnung zu schnell geworden.
  end;
  while FIterationsTodo > 0 do begin
    ContinueCalculation;
    FIterationsTodo := FIterationsTodo - 1;
    Application.ProcessMessages;
  end;
end;


Thorsten83 - Mi 26.05.10 10:55

Naja, der Fall dass du gaaaanz viele Items hast ist ja auch relativ easy zu lösen ;)

Das DP kommt dabei aber auch schon längst an seine Grenzen, da der Speicherbedarf ja bei O(OPT(I)*n) liegt...

Habt ihr euch mal einen FPTAS angeguckt?

Ansonsten kann man auch über Branch&Bound rangehen...


Pr0g3r - Mi 26.05.10 11:13

Hi,
Ich zieh mir FPTAS mal rein.
Noch mal zu dem Sinnflutalgorithmus:
Das mit dem Zmax klappt jetzt einigermaßen, aber ich habe zu
Wähle neue Konfiguration C' (ausgehend von C)
Bis jetzt habe ich immer mit einem Greedy oder vom Evolutionsalgorithmus die neue Konfiguration gewählt.
Gibt es noch andere, schönere Sachen für die neue Konfiguration?


Thorsten83 - Mi 26.05.10 11:34

Hmm randomisiert C' wählen mit ||C-C'||_1 = 1?

Irgendwann ist dann ja der "Wasserpegel" so weit gestiegen, dass du in einem lokalen Maximum hängen bleibst,
also könnte man abbrechen wenn <c, C'> <= W für alle C' mit ||C-C'||=1 ist...

Btw. c ist hierbei der Nutzenvektor... ;)

edit:
Nochmal zum Greedy...
(Hoffe mal, dass das noch nicht geschrieben wurde ;))
Im beschränkten Fall kann der beliebig schlecht werden, z.B. bei folgender Instanz:
Der Rucksack hat eine Kapazität von 1, du hast ein Item mit Profit und Gewicht epsilon und beliebig viele Items mit
Gewicht 1-epsilon/2 und Profit 1-epsilon

Das höchste Profit/Gewicht-Verhältnis hat dann das kleine Item, und dazu passt kein anderes mehr...
Für epsilon -> 0 geht dann auch der Profit gegen 0, obwohl 1 möglich wäre...


Pr0g3r - Do 27.05.10 13:55

FPTAS bedeutet ja einfach nur Nährungsverfahren. Nach denen suchen wir ja für unser Projekt.
Das Sinnflutverfahren funktioniert jetzt endlich ... :)

Das Greedy-Verfahren ist max 50% schlechter als die optimale Lösung. Also sch****.

Kann mir mal bitte wer die Sache mit dem Ameisenalgorithmus erklären, weil im web habe ich keine vernünftige Erklätung gefunden...

//edit: Ich habe das Prinzip zwar verstanden, weiss aber nicht wie ich das auf das Rucksackproblem anwenden soll