Optimierung des Quellcodes

[zwiety]

Ich habe einen Algorithmus für meine Diplomarbeit geschrieben und wollte mal fragen, ob man den noch irgendwie optimieren kann.

Code: Alles auswählen

import math
from itertools import izip
import numpy as np


def erfrage_koordinate():
    return np.array(
        [float(raw_input('{0}. Koordinate: '.format(i + 1))) for i in xrange(2)]
    )



def lex_opt_standort(index, gewichte, standorte):
    a = sum(
        (g[index] * s for g, s in izip(gewichte, standorte)),
        np.zeros(2)
    )
    return a / sum(gewicht[index] for gewicht in gewichte)


def f_i(x, index, gewichte, standorte):
    return sum(
        # g[index] * ((s[0] - x[0])**2) + g[index] * ((s[1] - x[1])**2)
        # ⇒     (factoring)
        # g[index] * ((s[0] - x[0])**2 + (s[1] - x[1])**2)
        # ⇒     (using `numpy`)
        (g[index] * (s - x)**2).sum() for g, s in izip(gewichte, standorte)
    )


def f(x, gewichte, standorte):
    return [f_i(x, i, gewichte, standorte) for i in xrange(2)]

def idealpunkt(xs,gewichte,standorte):
    return [f_i(xs[i],i,gewichte,standorte) for i in xrange(2)]



def U1(Z1, Z2):
    a = Z1
    r = np.array([Z2[i] -Z1[i] for i in xrange(2)])
    return a, r
    


def L1(YI, Z1):
    a = YI
    r = np.array([Z1[i] - YI[i] for i in xrange(2)])
    return a, r



def H(L, Ln, U):
    return max(h(L,U), h(Ln,U), h1(U,L, Ln))


def h(L,U):
    return max(distanz(L[0] + t * L[1], U) for t in  np.linspace(0, 1, num=200))

def h1(U,L, Ln):
    return max(distanz2(U[0] + t * U[1], L, Ln) for t in  np.linspace(0, 1, num=200))



def distanz(p, U):
    d = min(((p - U[0] - t * U[1])**2).sum() for t in np.linspace(0, 1, num=200))
    return math.sqrt(d)
    
def distanz2(p, L, Ln):
    d1 = min(((p - L[0] - t * L[1])**2).sum() for t in np.linspace(0, 1, num=200))
    d2 = min(((p - Ln[0] - t * Ln[1])**2).sum() for t in np.linspace(0, 1, num=200))
    d = min(d1,d2)
    return math.sqrt(d)


def stoppkriterium(L, Ln, U, genauigkeit, Z1, Z2, Liste):
    if genauigkeit < H(L, Ln, U):
        Liste.append([L, Ln, U, Z1, Z2])
        return Liste
    else:
        return 0


def gew_summenproblem(Y1,Y2):
    return np.array([-(Y2[1] - Y1[1]), Y2[0] - Y1[0]])

def neue_gewichte(Y1, Y2, index, gewichte):
    return (gewichte[index] * gew_summenproblem(Y1,Y2)).sum()

def opt_standort(gewichte_neu, standorte):
    a = sum(
        (g * s for g, s in izip(gewichte_neu, standorte)),
        np.zeros(2)
    )
    return a / sum(gewicht for gewicht in gewichte_neu)

def schnittpunkt1(L, U, Y3):
    n1 = U[1][0] * (L[0][1] - Y3[1])
    n2 = U[1][1] * (L[0][0] - Y3[0])
    m1 = L[1][0] * U[1][1]
    m2 = L[1][1] * U[1][0]
    t = (n1 - n2) / (m1 - m2)
    return L[0] + t * L[1]



def improve(Liste, gewichte, standorte, xs, repraesentatives_system, genauigkeit):
    L = Liste[0][0]
    Ln = Liste[0][1]
    U = Liste[0][2]
    Y1 = Liste[0][3]
    Y2 = Liste[0][4]
    Liste.remove(Liste[0])
    gewichte_neu =[neue_gewichte(Y1, Y2, i, gewichte) for i in xrange(len(gewichte))]
    X3 = opt_standort(gewichte_neu, standorte)
    xs = xs.append(X3)
    Y3 = f(X3, gewichte, standorte)
    repraesentatives_system.append(Y3)
    C3 =(gew_summenproblem(Y1,Y2) * f(X3, gewichte, standorte)).sum()
    P1 = schnittpunkt1(L, U, Y3)
    P2 = schnittpunkt1(Ln, U, Y3)
    L = L1(P1, Y1)
    Ln = L1(P1, Y3)
    U = U1(Y1, Y3)
    stoppkriterium(L, Ln, U, genauigkeit, Y1, Y3, Liste)
    L = L1(P2, Y3)
    Ln = L1(P2, Y2)
    U = U1(Y3, Y2)
    stoppkriterium(L, Ln, U, genauigkeit, Y3, Y2, Liste)
    return repraesentatives_system

        
    


def main():
    anzahl_standorte = int(raw_input('Anzahl der existierenden Standorte: '))
    
    standorte = [erfrage_koordinate() for _ in xrange(anzahl_standorte)]
    print 'Die Menge der existierenden Standorte ist: ', standorte
    
    gewichte = [erfrage_koordinate() for _ in xrange(anzahl_standorte)]
    print 'Die Menge der Gewichte ist: ', gewichte

    genauigkeit=float(raw_input('Gewuenschte Genauigkeit: '))
    
    
    xs = [lex_opt_standort(i, gewichte, standorte) for i in xrange(2)]

    repraesentatives_system = [f(x, gewichte, standorte) for x in xs]
    print repraesentatives_system

    Z1 = f(xs[0], gewichte, standorte)

    Z2 = f(xs[1], gewichte, standorte)

    YI = idealpunkt(xs, gewichte, standorte)

    U = U1(Z1, Z2)

    L = L1(YI, Z1)

    Ln = L1(YI, Z2)

    Liste = []

    stoppkriterium(L, Ln, U, genauigkeit, Z1, Z2, Liste)

    while len(Liste) > 0:
        improve(Liste, gewichte, standorte, xs, repraesentatives_system, genauigkeit)
        

    print 'Das repräsentative System ist gegeben durch: Rep= ', repraesentatives_system

 
        
    

if __name__ == '__main__':
    main()

[Dobi]

Was sagt denn der Profiler (http://docs.python.org/library/profile.html), wo die meiste Zeit verbraten wird?

[zwiety]

Die meiste Zeit wird bei stoppkriterium() verbraucht, weil er ja t in np.linspace(0,1,num=200) sucht. ich weis aber nicht wie ich diese Gerade anders definieren könnte. Hat da jemand eine Idee oder einen Tip

[EyDu]

Der einfachste Schritt wäre, wenn du numpy.linspace einmal berechnen würdest und nicht immer und immer wieder.

Sehe ich es richtig, dass du lediglich versuchst den Abstand von zwei Geraden zu bestimmen? Dafür musst du diese aber nicht samplen, das kann man in einer geschlossenen Formel lösen.

[zwiety]

Also ich versuch http://de.wikipedia.org/wiki/Hausdorff-Abstand zu berechnen. Kann ich das dann auch einfacher machen?

ich muss es ja immer und immer wieder machen, weil die Geraden sich in jeder Iteration ändern.

[EyDu]

Für mich sieht es so aus, als würdest du nur die Hausdorff-Distanz nutzen, da du nicht die richtige Lösung kennst:

Code: Alles auswählen

def h(L,U):
    return max(distanz(L[0] + t * L[1], U) for t in  np.linspace(0, 1, num=200))

def distanz(p, U):
    d = min(((p - U[0] - t * U[1])**2).sum() for t in np.linspace(0, 1, num=200))
    return math.sqrt(d)

Soll doch wohl der minimale Abstand zwischen den geraden g = L[0] + a*L[1] und h = U[0] + b*U[1] sein, oder?

[zwiety]

Also in

Code: Alles auswählen

def distanz(p, U):
    d = min(((p - U[0] - t * U[1])**2).sum() for t in np.linspace(0, 1, num=200))
    return math.sqrt(d)

suche ich die minimale Distanz von dem Punkt p der auf L liegt und der geraden U und wähle durch

Code: Alles auswählen

def h(L,U):
    return max(distanz(L[0] + t * L[1], U) for t in  np.linspace(0, 1, num=200))

dann den maximalen Abstand aller minimalen Distanzen aus.

Mit anderen Worten möchte ich das Maximum aller minimalen Distanzen von einem Punkt auf L zu einem Punkt auf U

[EyDu]

Oh, natürlich. Da habe ich das max für ein min gehalten. Für eine Optimierung wäre es dann natürlich noch interessant, warum du num=200 verwendest. Sind hier tatsächlich diskrete Schritte vorgesehen?

[zwiety]

Nein es sind keine diskreten Schritte vorgesehen. Darin hängt ja noch mein Problem, nämlich das ich nicht weis wie ich es sonst programmieren soll.

[EyDu]

Für das Minimum ist der Fall eigentlich ganz einfach: du hast einen Punkt p und eine Gerade g = u + a*v. Dann findest du das Minimum indem du (g - p)^2 = (u+ a*v -p)^2 nach a ableitest, das Ergebnis =0 setzt und anschließend nach a auflöst. Jetzt musst du nur noch testen ob das Minimum im Definitionsbereich liegt. Wenn nicht, dann ist das Minimum entweder die obere oder die untere Grenze des Definitionsbereichs Damit hast du das Problem für die distanz-Funktion gelöst.

Mir erschließt sich allerdings nicht der Sinn der h-Funktion, wenn die Schritte nicht diskret sind. Da du zwei Geradensegmente hast, würde bei deiner aktuellen Implementierung die Lösung von h immer den ersten Punkte auf dem Segment ergeben oder den letzten.

[zwiety]

Also bei der Distanz hast du vollkommen recht gehabt. ich habe das jetzt mittels der Ableitungen geändert. Keine Ahnung wieso ich nicht auf diese Idee gekommen bin .

Das mit der h()-Funktion ist nun auch mein Problem. Ich weis nicht, wie ich das allgemein definieren kann, dass ich die beiden Geraden verwende ohne diskrete Schritte zu wählen. Hast du vielleicht eine Idee, wie man das anders bewältigen könnte?

[EyDu]

Naja, jetzt kommt es ein wenig darauf an, was genau du als Ergebnis haben möchtest. Da die beiden Segmente L und U nun stetig sind, macht das Maximum der minimalen Abstände zwischen diesen beiden Segmenten für mich keinen wirklichen Sinn mehr. Ich sehe eigentlich nur die folgenden Lösungen:

1) Der minimale Abstand zwischen den Segmenten L und U oder
2) der maximale Abstand zwischen den Segmenten L und U oder
3) ich übersehe etwas.

Den Punkt 1) könntest du analog zum minimalen Abstand zwischen Punkt und Gerade bestimmen. Das sind auch nur zwei partielle Ableitungen und ein LGS. Eigentlich brauchst du das auch nicht selber bestimmen, die triviale Arbeit nimmt dir Google auch ab.

Punkt 2) wäre noch einfach zu lösen. Da reicht es, wenn du Anfangs- und Endpunkte aus L mit den Anfangs- und Endpunkten aus U vergleichst. Der maximale Abstand der vier Paare ist gleichzeitig der maixmale Abstand zwischen den Segmenten.

Sebastian