Die Mathe-Redaktion - 17.01.2020 14:55 - Registrieren/Login
Auswahl
ListenpunktHome
ListenpunktAktuell und Interessant ai
ListenpunktArtikelübersicht/-suche
ListenpunktAlle Links / Mathe-Links
ListenpunktFach- & Sachbücher
ListenpunktMitglieder / Karte / Top 15
ListenpunktRegistrieren/Login
ListenpunktArbeitsgruppen
Listenpunkt? im neuen Schwätz
ListenpunktWerde Mathe-Millionär!
ListenpunktAward-Abstimmung ab 1.1.
ListenpunktFormeleditor fedgeo
Schwarzes Brett
Aktion im Forum
Suche
Stichwortsuche in Artikeln und Links von Matheplanet
Suchen im Forum
Suchtipps

Bücher
Englische Bücher
Software
Suchbegriffe:
Mathematik bei amazon
Naturwissenschaft & Technik
In Partnerschaft mit Amazon.de
Kontakt
Mail an Matroid
[Keine Übungsaufgaben!]
Impressum

Bitte beachten Sie unsere Nutzungsbedingungen, die Distanzierung, unsere Datenschutzerklärung und
die Forumregeln.

Sie können Mitglied werden. Mitglieder können den Matheplanet-Newsletter bestellen, der etwa alle 2 Monate erscheint.

Der Newsletter Okt. 2017

Für Mitglieder
Mathematisch für Anfänger
Wer ist Online
Aktuell sind 700 Gäste und 25 Mitglieder online.

Sie können Mitglied werden:
Klick hier.

Über Matheplanet
 
Zum letzten Themenfilter: Themenfilter:
Matroids Matheplanet Forum Index
Moderiert von matroid
Mathematik » Numerik & Optimierung » Angabe des prozentualen Unterschieds zwischen Optimierungsverfahren
Druckversion
Druckversion
Antworten
Antworten
Autor
Universität/Hochschule Angabe des prozentualen Unterschieds zwischen Optimierungsverfahren
VannyFi
Junior Letzter Besuch: vor mehr als 3 Monaten
Dabei seit: 27.08.2018
Mitteilungen: 17
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Themenstart: 2019-07-20


Hallo Leute,

ich würde gerne mehrere Heuristiken mit der opimalen Lösung vergleichen. Es geht um ein Minimierungsproblem und ich hatte ursprünglich vor prozentual anzugeben, um wie viel Prozent die Heursitiken an das Ergebnis des exakte Verfahren, welches das globale Optimum liefert, dran kommt.

Ich dachte daran an folgendes Verhältnis:
\[\frac{Z_{Optimal}}{Z_{Heuristik}}*100\]
Der optimale Zielfunktionswert \(Z_{Optimal}\)wird als 100 % angesehen. Das Problem ist, dass dieser Wert 0 sein kann. Somit würde dieser Quotient stets den Wert 0 anngehmen, egal wie nah die spezielle Heuristik am optimalen Ergebnis ist d.h. ob \(Z_{Heuristik}\) den Wert 100 oder 0.1 annehmen würde, spielt keine Rolle.

Deswegen wollte ich euch mal fragen, ob ihr eine bessere Idee habt, um den Prozentualen Unterschied von verschiedenen Heuristiken mit denen des optimalen Zielfunktionswertes zu vergleichen?

Ich würde mich über jede Antwort sehr freuen.



Wahlurne Für VannyFi bei den Matheplanet-Awards stimmen
  Profil  Quote  Link auf diesen Beitrag Link
VannyFi
Junior Letzter Besuch: vor mehr als 3 Monaten
Dabei seit: 27.08.2018
Mitteilungen: 17
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.1, vom Themenstarter, eingetragen 2019-07-23


Hat niemand eine Idee dazu bzw. war mit demselben Problem konfrontiert?
Ich würde mich sehr über eure Meinung freuen.



Wahlurne Für VannyFi bei den Matheplanet-Awards stimmen
  Profil  Quote  Link auf diesen Beitrag Link
Diophant
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 18.01.2019
Mitteilungen: 2565
Aus: Rosenfeld, BW
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.2, eingetragen 2019-07-23

\(\begingroup\)\( \newcommand{\ba}{\begin{aligned}} \newcommand{\ea}{\end{aligned}} \newcommand{\bpm}{\begin{pmatrix}} \newcommand{\epm}{\end{pmatrix}} \newcommand{\bc}{\begin{cases}} \newcommand{\ec}{\end{cases}}\)
Hallo,

das musst du m.A. nach einfach mit der Differenz machen, also

\[P=\frac{Z_\text{Heuristik}-Z_\text{Optimal}}{Z_\text{Optimal}}\cdot 100\%\]
Und natürlich auf den optimalen Wert beziehen, nicht auf den heuristisch erzielten.

EDIT: sorry, ich hatte mich verlesen. Mein Tipp ist hier nicht praktikabel, aus dem von dir genannten Grund.

Siehe dazu auch die nächste Antwort von Kitaktus.


Gruß, Diophant
\(\endgroup\)


Wahlurne Für Diophant bei den Matheplanet-Awards stimmen
  Profil  Quote  Link auf diesen Beitrag Link
Kitaktus
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 11.09.2008
Mitteilungen: 6132
Aus: Niedersachsen
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.3, eingetragen 2019-07-23


Wenn der optimale Zielfunktionswert 0 sein kann, dann kann man eben keine sinnvollen _relativen_ Abweichungen angeben.

Eine Variante wäre: $\frac{Z_{Durchschnitt}-Z_{Heuristik}}{Z_{Durchschnitt}-Z_{Optimal}}$. Dieser Quotient gibt an, welcher Anteil der Verbesserung zwischen einer durchschnittlichen Lösung hin zum Optimum auch von der Heuristik gefunden wird.
Bei vielen Problemen kann man einen durchschnittlichen Funktionswert leicht bestimmen. Die durchschnittliche Länge einer Rundreise ist bspw. die mittlere Kantenlänge multipliziert mit der Zahl der Knoten auf der Rundreise.

Kleiner Nachteil: Auf die Weise erscheinen(!) Heuristiken teilweise besser als sie sind.
Ist bspw. $Z_{Optimal}=1$, $Z_{Heuristik}=1.1$ und $Z_{Durchschnitt}=5$, so ergibt sich ein Quotient von $0.975$. Also nur 2.5% der durchschnittlichen Verbesserung zwischen einer zufälligen Startlösung und dem Optimum werden von der Heuristik nicht gefunden.
Das wirkt schon anders als die Angabe: Die Lösung der Heuristik war 10% schlechter.
Dabei wird das Ergebnis "2.5%" stark davon beeinflusst, wie schlecht eine durchschnittliche Lösung ist.



Wahlurne Für Kitaktus bei den Matheplanet-Awards stimmen
  Profil  Quote  Link auf diesen Beitrag Link
hgseib
Wenig Aktiv Letzter Besuch: vor mehr als 3 Monaten
Dabei seit: 04.04.2019
Mitteilungen: 172
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.4, eingetragen 2019-07-23


Wenn a der Zielwert ist und bmax der am weitesten davon entfernteste Wert ***, dann kannst du alle anderen dazwischenliegenden Werte bn mit %-Werte berechnen.

*** Das kann auch ein Wert sein, der per definition als der schlechteste Wert angenommen wird.



Wahlurne Für hgseib bei den Matheplanet-Awards stimmen
  Profil  Quote  Link auf diesen Beitrag Link
Folgende Antworten hat der Fragesteller vermutlich noch nicht gesehen.
Er/sie war noch nicht wieder auf dem Matheplaneten
Carmageddon
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 22.12.2009
Mitteilungen: 622
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.5, eingetragen 2019-08-30


Meine Meinung:

Wäre es nicht sinnvoller mit absoluten Werten (Normdifferenz) zu rechnen? Bei großen Werten kann auch eine "kleine" prozentuale Abweichung eine "große" absolute Abweichung bedeuten. Je nachdem wie die tatsächlichen Zahlen aussehen ist auch ein direkter Vergleich (in einer Liste o.ä.) der verschiedenen Heuristiken übersichtlich.

Nebenbei hat sich dein Problem mit der Null auch erledigt.


-----------------
Zitat: "Es gibt einen Beweis aus der Physik: Er ist kurz, er ist elegant... und falsch"



Wahlurne Für Carmageddon bei den Matheplanet-Awards stimmen
  Profil  Quote  Link auf diesen Beitrag Link
Kitaktus
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 11.09.2008
Mitteilungen: 6132
Aus: Niedersachsen
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.6, eingetragen 2019-08-30


Die mathematische Optimierung beschäftigt sich typischerweise nicht mit _einem_ Optimierungsproblem, sondern mit einer ganzen Klasse. Eine typische Frage (aus dem Bereich der Anwender) ist z.B. welche Heuristik wie gut geeignet ist.
Das Heuristik A bei der Instanz x besser war und Heuristik B bei Instanz y, sagt ja allein noch nicht viel aus, man interessiert sich für eine Statistik: "A schneidet im Durchschnitt so gut ab und B so gut."
An der Stelle wird klar, dass man die Zielfunktionswerte irgendwie sinnvoll normieren muss und nicht einfach absolute Beträge verwenden kann(*). Sonst würde eine Testinstanz in der Auswertung plötzlich tausendmal so wichtig, nur weil man die Einheiten von Kilometer in Meter umgewandelt hat.
Hier kommt dann der relative Fehler und seine Verwandten ins Spiel.


(*) Es gibt einige Probleme, z.B. in der Graphentheorie, bei denen auch absolute Größen relevant sind, weil z.B. eine Heuristik "höchstens um 1 daneben liegt". Das sind aber seltene Ausnahmen.



Wahlurne Für Kitaktus bei den Matheplanet-Awards stimmen
  Profil  Quote  Link auf diesen Beitrag Link
Carmageddon
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 22.12.2009
Mitteilungen: 622
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.7, eingetragen 2019-09-04


2019-08-30 12:52 - Kitaktus in Beitrag No. 6 schreibt:
Die mathematische Optimierung beschäftigt sich typischerweise nicht mit _einem_ Optimierungsproblem, sondern mit einer ganzen Klasse. Eine typische Frage (aus dem Bereich der Anwender) ist z.B. welche Heuristik wie gut geeignet ist.

Akzeptiert.

Meiner Meinung nach kann man aus dem Startposting aber herauslesen, dass es sich nur um ein spezielles Minimierungsproblem handelt. In diesem Fall kann man durchaus mit absoluten Zahlen arbeiten.


-----------------
Zitat: "Es gibt einen Beweis aus der Physik: Er ist kurz, er ist elegant... und falsch"



Wahlurne Für Carmageddon bei den Matheplanet-Awards stimmen
  Profil  Quote  Link auf diesen Beitrag Link
Neues Thema [Neues Thema] Antworten [Antworten]    Druckversion [Druckversion]

 


Wechsel in ein anderes Forum:
 Suchen    
 
All logos and trademarks in this site are property of their respective owner. The comments are property of their posters, all the rest © 2001-2019 by Matroids Matheplanet
This web site was made with PHP-Nuke, a web portal system written in PHP. PHP-Nuke is Free Software released under the GNU/GPL license.
Ich distanziere mich von rechtswidrigen oder anstößigen Inhalten, die sich trotz aufmerksamer Prüfung hinter hier verwendeten Links verbergen mögen.
Lesen Sie die Nutzungsbedingungen, die Distanzierung, die Datenschutzerklärung und das Impressum.
[Seitenanfang]