Algorithmus um Iterationsschritte zu verringern

[Dennis89]

Guten Morgen zusammen,

ich weiß dass es Algorithmen gibt, die eine gesuchte Zahl nicht strikt von 0 an suchen, sondern den Bereich der möglichen Zahlen unterteilen und sich erst in großen Schritten annähern. So etwas suche ich gerade, werde aber nicht so wirklich fündig.

Mein Problem ist ich habe berechne drei Werte "x", "y" und "z". "x" und "y" sind von "p1" anbhängig, "y" auch noch von "p2" und "z" auch von "p2". Mein Ziel ist `x == y == z` und dazu ändere ich iterative "p1" und "p2" um definierte Schritte bis die Differenz für mich akzeptabel ist. Das dauert allerdings und ich würde das gerne optimieren.

Könnt ihr mir sagen, nach was ich eigentlich suche? Also Schlagwörter bzw. wie die Algorithmen heißen, die hier in Frage kommen?


Grüße und Danke
Dennis

[grubenfox]

Binäre Suche

[Sirius3]

Ich denke, es geht eher um einen Least-Square-Fit: https://docs.scipy.org/doc/scipy/refere ... astsq.html mit dem Ziel (x-y)**2 + (x-z)**2 zu minimieren.

[Dennis89]

Danke für die Antworten. Die von Sirius3 sah ich erst nach dem ich schon mit der Binäre-Suche angefangen hatte und hatte bis jetzt noch nicht genügend Zeit, den Vorschlag richtig zu verstehen.

Die Binär-Suche habe ich einfach mal so umgesetzt:

Code: Alles auswählen

#!/usr/bin/env python

VALUES = list(range(50))
SEARCH_VALUE = 21


# Just a placeholder for the production code
calculate = lambda x: x + 1

def main():
    values = VALUES
    while True:
        lower, upper = values[:len(values) // 2], values[len(values) // 2:]
        result_lower = calculate(lower[-1])
        result_upper = calculate(upper[0])
        if abs(result_lower - SEARCH_VALUE) < abs(result_upper - SEARCH_VALUE):
            if result_lower == SEARCH_VALUE:
                print(f"Finish lower list; {result_lower}")
                return
            elif result_upper == SEARCH_VALUE:
                print(f"Finish upper list; {result_upper}")
                return
            values = lower
        else:
            values = upper


if __name__ == "__main__":
    main()

Erst mal als Minimalbeispiel, das ich den Überblick behalte. Schwer tue ich mir mit den Namen. `lower`, `upper`, etc. Etwas besseres fiel mir nicht ein und daher denke ich, dass das wie so oft, noch optimierbar ist?
Erst im nächsten Schritt will ich dass dann ausbauen und eine vereinfachte Berechnung einbauen, damit ich meinen benötigten Vergleich `x == y == z` einbauen kann.

Grüße
Dennis

[nezzcarth]

Wenn ich dich richtig verstehe, muss die Lösung nicht perfekt, sondern nur gut genug sein. Da bieten sich dann auch heuristische Verfahren an. Ich würde ja erst einmal gucken, wie gut das Ergebnis wird, wenn du p1 und p2 N-mal zufällig auswürfelst (in dem Wertebereich, der Sinn ergibt für das Problem in N abhänging davon, wie lange die Berechnung dauert) und dann das beste Pärchen raussuchst. Optional kann man dann aus dem Teilergebnis noch versuchen, mit z.B. Hill Climbing o.Ä. mehr herauszuquetschen. Das kann in simplen Fällen schon helfen. Ansonsten gibt es auch noch komplexere Verfahren.

[Dennis89]

Danke für die Antwort. Ja genau, ich lasse eine bestimmte Differenz zwischen den Werten zu.
Das mit den zufälligen Zahlen könnte doch auch nach hinten los gehen? Also was die Laufzeit angeht bzw. es kann bei wiederholten Rechendurchgängen zu merkbaren Abweichungen kommen oder stelle ich mir das zu extrem vor?

Grüße
Dennis

[__blackjack__]

@Dennis89 Warum teilst Du da in `lower` und `upper` auf und kopierst `values` in neue Listen? Normalerweise macht man das alles nur mit Indexwerten und kopiert die Originaldaten nicht. Wenn kein Wert gefunden wird ist das übrigens eine Endlosschleife.

Grundsätzlich gibt's die binäre Suche übrigens schon im `bisect`-Modul in der Standardbibliothek.

In diesem Thema gibt's binäre Suche in klassischem BASIC und FORTRAN: viewtopic.php?t=58769

[Dennis89]

Danke für die Antwort.

`lower` und `upper` weil ich es übersichtlicher fand und `values` weil ich den Name brauchte und die Ursprungsliste als Konstante behalten wollte. Würde vermutlich alles wegfallen, wenn ich, wie vorgeschlagen, nur mit Indexwerten arbeite.
`bisect` schaue ich mir gerne an, scheitere aber gerade die Binärsuche an sich in meine ursprüngliche Rechnung einzubauen. Ich habe den Code, in den ich die Suche einbauen will so weit wie möglich vereinfacht und die Namenswahl ist so, weil ich nicht unbedingt will, das man da irgendwelche Rückschlüsse ziehen kann.

Code: Alles auswählen

#!/usr/bin/env python
from itertools import pairwise
from math import pi
from time import process_time

from icecream import ic

START_VALUES = list(map(int, [45e5, 70e5, 91e5, 500e5]))
ITEMS = [50, 40, 35]

POSSIBLE_VALUES = list(range(min(START_VALUES), max(START_VALUES)))
CONSTANTS = [pi * item**2 / 4 * 0.13 * 530 * 60 for item in ITEMS]

MAX_DIFFERENCE = 0.1
VALUE_CHANGING = 1000


def get_result(value, constant):
    return 0.9317 * value / 1 * constant


def main():
    start = process_time()
    stage_values = START_VALUES
    results = []
    value_changing = VALUE_CHANGING
    while True:
        for (in_value, out_value), constant in zip(pairwise(stage_values), CONSTANTS):
            # NOTE: out_value will be used in production code
            results.append(get_result(in_value, constant))
        no_difference = True
        for stage, (first, second) in enumerate(pairwise(results), 1):
            flow_difference = first - second
            ic(flow_difference)
            if abs(flow_difference) > MAX_DIFFERENCE:
                no_difference = False
                if flow_difference >= 0:
                    stage_values[stage] += value_changing
                else:
                    value_changing /= 2
                    stage_values[stage] -= value_changing
        if no_difference:
            ic(process_time() - start)
            return
        else:
            results = []


if __name__ == "__main__":
    main()

Auch hier `value_changing` um die Konstante zu behalten.
Der läuft zwar recht zügig durch, aber im originalen braucht der ca. 40 Sekunden, da da noch mehr berechnet wird.
Von den `stage_values` werden jeweils die mittleren zwei geändert, da die Einfluss auf das Ergebnis haben. Bei meinen Versuchen die Suche einzubauen benötige ich Flags die mir sagen ob die `lower` oder `upper` Liste benutzt wurde und noch ne Schleife um alles und ich verlor schon beim schreiben den Überlick. Sprich es wäre schön, wenn ihr mich da etwas unterstützen könnt. Gerne bezogen auf Python und nicht unbedingt BASIC oder FORTRAN

Ist die Binäre-Suche überhaupt das Richtige hier?


Danke und Grüße
Dennis

[grubenfox]

Naja, 'Binaärsuche' war mein erster Gedanke als ich im Halbschlaf diesne Satz gelesen hatte:

ich weiß dass es Algorithmen gibt, die eine gesuchte Zahl nicht strikt von 0 an suchen, sondern den Bereich der möglichen Zahlen unterteilen und sich erst in großen Schritten annähern.

Aber wenn man sich den Rest der Aufgabenstellung anschaut, dann ist das wohl ein Optimierungs-Problem. Zu Optimierungsverfahren verweise ich da lieber auf die obensthenden Beiträge von Sirius3 und nezzcarth.

[Sirius3]

@Dennsi89: warum versuchst Du etwas selbst zu implementieren, was es schon längst fertig gibt?

Code: Alles auswählen

from math import pi
import scipy.optimize

START_VALUES = [45e5, 70e5, 91e5]
ITEMS = [50, 40, 35]
CONSTANTS = [pi * item**2 / 4 * 0.13 * 530 * 60 for item in ITEMS]

def merit_function(values):
    results = 0.9317 * values * CONSTANTS
    return results - results.mean()

results, _ = scipy.optimize.leastsq(merit_function, START_VALUES)
print(results)