Die Mathe-Redaktion - 23.08.2019 14:01 - 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!
ListenpunktAnmeldung MPCT Sept.
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 479 Gäste und 14 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: im letzten Monat
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.



  Profil  Quote  Link auf diesen Beitrag Link
VannyFi
Junior Letzter Besuch: im letzten Monat
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.



  Profil  Quote  Link auf diesen Beitrag Link
Diophant
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 18.01.2019
Mitteilungen: 1629
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\)


  Profil  Quote  Link auf diesen Beitrag Link
Kitaktus
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 11.09.2008
Mitteilungen: 5985
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.



  Profil  Quote  Link auf diesen Beitrag Link
hgseib
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 04.04.2019
Mitteilungen: 148
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.



  Profil  Quote  Link auf diesen Beitrag Link
VannyFi hat die Antworten auf ihre/seine Frage gesehen.
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]