Numerisk olinjär optimering i realtid

[Tottish]

Hej!

Bakgrund:
Har suttit länge och väl nu och arbetat med ett projekt. Det rör sig om ett PC program som ska:
1. Hämta in lite in-data från en PIC via RS232
2. Utföra en matematisk, olinjär optimering (en numerisk lösning) med dessa
3. Plotta ut resultatet på ett linjediagram
Detta skall ske med så hög uppdateringsfrekvens som möjligt. Säg minst 5Hz.

Har efter mycket om och men lyckats skriva ett sådant program för VBA/Excel (under XP/Win7) bara för att kunna konstatera att frekvensen knappast går över 0,7Hz på den Dualcore Atom som det hela ska köras på.
Jag har efter vissa fruktlösa försök att optimera programmet/processor-användandet beslutat att börja om med något som inte är så "klumpigt"/resurskrävande som Excel.

För den numeriska optimeringen har jag använt Excels vanliga "Solver" ("Problemlösaren" på svenska versionen) och det funkar bra men går inte fort. Detta verkar dock vara det största problemet, att hitta en vettig solver som inte kostar $1000+ och kan anropas lite smidigt från något programmeringsspråk.

Då jag grävt ännu djupare så kommer jag fram till att man bör kunna använda Octave (opensource MATLAB-klon) som lär ha stöd för att kunna anropas men det känns lite overkill och kanske går denna lösning inte mycket snabbare än Excel? Ett plus vore väl att man sannolikt skulle kunna köra från en Linux-miljö vilket kanske skulle snabba upp en del.

Fråga:
Det var mina tankar. Det jag skulle vilja veta är hur ni skulle ha löst denna uppgift. Jag räknar som sagt med att få börja om från grunden så alla förslag välkomnas. Om någon har någon bra optimeringsmodul på lager så får man naturligtvis tipsa om den också.

Tack för ordet, ha en fin eftermiddag!
/Tottish

[SvenW]

Eftersom optimeringproblemet är ofullständigt presenterat är det omöjligt att säga huruvuda Octave klarar av det eller inte.
Octave är annars ett väl fungerande program och klarar av mycket.
Jag skulle försökt med det i första hand. Annars kan man prova skriva ett program i Python eller Perl, och om det inte går får man gå vidare till C eller C++ eller liknande. Man kan också skriva tillägg i C till Octave, Python och Perl, men det är kanske överkurs.
För plottning brukar jag använda Gnuplot, som för övrigt också används av Octave.
Excel använder jag sällan, mitt intryck är att det är mer till för ekonomer och inte för ingenjörer.

[Tottish]

Tack för svaret SvenW!
Jag är faktiskt inte säker på hur jag fullständigt skall formulera problemet då jag inte är så insatt i den biten. Det var inte jag som skrev själva inmatningen till lösningsmodulen från början.
Tror att det får bli ett försök med Octave då. Alternativa lösningar välkomnas naturligtvis ändå.

Här är koden som styr Solver.

Kod: Markera allt

    Sheets("Solver").Select
    SolverOk SetCell:="$C$26", MaxMinVal:=3, ValueOf:="0", ByChange:="$C$18:$C$25"
    SolverOptions MaxTime:=100, Iterations:=500, Precision:=0.0000001, AssumeLinear _
        :=False, StepThru:=False, Estimates:=1, Derivatives:=2, SearchOption:=1, _
        IntTolerance:=5, Scaling:=False, Convergence:=0.001, AssumeNonNeg:=False
    SolverOk SetCell:="$C$26", MaxMinVal:=3, ValueOf:="0", ByChange:="$C$18:$C$25"
    SolverSolve True
    Sheets("Calculator").Select

MVH
/Tottish

[strombom]

Har du tittat noga på parametrarna?
Iterations:=500
Precision:=0.0000001

[Tottish]

Iterationerna är maxantalet om inte den angivna konvergensen uppnåtts innan dess.
Precisionen verkar vara för de enskilda beräkningarna och det verkar inte påverka lösningstiden nämnvärt. Inte mätbart i mitt fall. (Har provat ner till 0.01, ingen skillnad)

MVH
/Tottish

[Tottish]

Hallå!
Framgångsbeskrivning:
Nu har jag faktiskt lyckats koda en fungerande solver till Octave och som jag hoppades så gör den på ca0.05s det som Excel gör på nästan en hel sekund. Vet inte om man kan få det ännu bättre om man kör i en Linux-miljö?

Hur som helst så är det nu dags att gå vidare i projektet och jag tänkte därför börja med att se om det finns någon möjlighet att plotta ut grafen (med realtidsuppdateringar) direkt från Octave. Har kikat på och provat med GnuPlot men jag tycker det känns för segt. Är dock inte så insatt så det kanske finns något sätt att få det att flyta på bättre.

Min fråga är i alla fall:
Har någon plottat i realtid (helst typ 10Hz) direkt från Octave med tillfredsställande resultat? Inget flimmer och sådant...

Går detta i stöpet så känns det som att det får bli en C++ lösning då det verkar gå att skriva Octave-script direkt i C-koden (om man includar octave.h) vilket jag tänker borde generera minst fördröjning.
Tanken är att rådata till solvern slutligen ska hämtas in från en mikrokontroller, så någon form av program som förser Octave-scriptet med variabelvärden behövs ändå. Tänkte bara att det skulle vara skönt om man kunde släppa datahanteringen (i C/C++ programmet) efter att man skickat vidare till scriptet... Speciellt då jag inte kan koda C.

Any takers? (C++ lösningar välkomnas också...)
MVH
/Tottish

[SvenW]

Jag gjorde följande test i Octave (Linux, Pentium P4 2800MHz):

Kod: Markera allt

grid on;
for i = 1:50
x = (1:500) + i ;
s = sin(pi*x/50);
plot(s);
pause(0.1); 
endfor

Den ger en rullande sinuskurva med 500 punkter som uppdateras med ca 10 Hz.
Det blir en lite hackande gång, men inte särskilt störande.

[Tottish]

Tack SvenW!
Tyvärr så ger samma kod ett hackigt och något flimmrigt resultat på min quadCore i7 under Win7 och det finns risk för att slutprodukten måste kunna köras under windows.

Stort tack för att du tog dig tid! Sneglar lite på en Qt/C++ baserad lösning istället. Verkar kunna gå att få Qt-apps att köras riktigt mjukt och fint...

MVH
/Tottish

[SvenW]

Tror at Qt använder vad man kallar dubbelbuffring. Man plottar på en 'pixmap' och låter sedan X-servern, eller vad vad den heter i Windows, överföra hela pixmappen till skärmen på en gång, synkront med skärmens uppdatering. Då blir det helt flimmerfritt.
Gtk använder också detta, och det gör väl de flesta moderna program.
Jag gör samma sak i mina program Hec och det Xlib-baserade Xhec, och där kan man flytta/scrolla sina schemasymboler helt flimmerfritt.

[swesysmgr]

Jag har inte skrivit någon VBA-kod att tala om på fem år men jag tyckte era siffror verkade väldigt märkligt slöa så jag skrev ett litet test i Excel (2007).

Jag kan inte Octave så jag har gissat vad Svens kod innebär, om det blev fel så korrigera gärna.

Dim data(1 To 500) As Double

...

For i = 1 To 50
For x = 1 To 500
d = Sin(pi * (x + i) / 50)
data(x) = d
Next x
(plotta kurva)

För slingan på 50 beräkningar med plottning fick jag tiderna:
Tid: 52 ms
Tid: 54 ms
Tid: 50 ms
Tid: 51 ms
Tid: 34 ms
Tid: 48 ms
Tid: 50 ms
Tid: 50 ms

Lägger jag in timern i varje snurrsteg av de 50 blir det:
Tid: 14 ms
Tid: 1 ms
Tid: 1 ms
Tid: 1 ms
Tid: 1 ms
Tid: 2 ms
Tid: 1 ms
Tid: 1 ms
Tid: 1 ms
Tid: 1 ms
Tid: 0 ms
Tid: 3 ms
Tid: 1 ms
Tid: 1 ms
Tid: 1 ms
Tid: 1 ms
Tid: 1 ms
Tid: 1 ms
Tid: 2 ms
Tid: 1 ms
Tid: 1 ms
Tid: 2 ms
Tid: 1 ms
Tid: 0 ms
Tid: 1 ms
Tid: 1 ms
Tid: 2 ms
Tid: 1 ms

osv.

Man får alltså steppa i koden för att kunna se uppdateringarna men att köra grejer med 10Hz i excel ska inte vara några som helst problem men man får skriva VBA kod som gör det.

Att döma av hur solverkoden ovan ser ut så är det inte ett program utan någon som använt makroinspelaren och klickat sig igenom momenten. Den är mest till för om du vill koppla ett repetitivt moment till en snabbknapp men brukar göra väldigt ineffektiv kod eftersom den skall kunna ändras enkelt av personer som inte kan programmera.

Minns inte exakt hur solvern fungerade men det var väl att man skriver in en formel + målvärde och anger några fria variabler? Lite mer info om optimeringsproblemet vore uppskattat så går det nog att göra ett realistiskt test.

Testmaskin: Intel E8500 C2D CPU, GMA grafik, Vista64

[Tottish]

Hmm, intressant.
Vill först bara säga att jag uttryckt mig oklart angående tiden (och sin-kurvan har jag inte testat alls i Excel). Det är inte själva uträkningen som tar typ en sekund utan. Uträkning + uppdatering av OWC11-diagram i en userform.

Angående problemet så tror jag det är enklast om jag skriver ut octave-koden då jag inte riktigt vet hur jag ska kunna få med allt från Excel utan att det blir super-rörigt.

Kod: Markera allt

function obj = phi (x)
  obj = sumsq(g(x));             
endfunction
%*******************************
function r = g (x) 
        r = [ a_std*x(1)^4 + b_*x(1) + c_std + d_*x(2); 
        e_std*x(2)^4 + f_*x(2) + g_std + d_*x(1);
	a_std*x(3)^4+b_*x(3)+c_std+d_*x(4);
	e_pre*x(4)^4+f_*x(4)+g_pre+d_*x(3);
        a_pre*x(5)^4+b_*x(5)+c_pre+d_*x(6);
        e_std*x(6)^4+f_*x(6)+g_std+d_*x(5);
        a_pre*x(7)^4+b_*x(7)+c_pre+d_*x(8);
        e_pre*x(8)^4+f_*x(8)+g_pre+d_*x(7)];

endfunction

Det är alltså phi(x) som vi söker att minimera. I enlighet med g(x). Det är alltså åtta variabler (där alla har startvärde 300) och polynomerna är av den fjärde ordningen.
Varabelvärdena för e_std, g_std, d_ osv. fås efter enklare aritmetiska operationer utförda på cirka tio "rå-indata".

Angående: "10Hz i excel ska inte vara några som helst problem"
Kanske inte men jag har då inte lyckats få ett linjediagram att uppdateras flimmerfritt i ett eget fönster (userform) med den frekvensen på en DualCore Atom. Inte om man emellan måste göra ändringar i spreadsheetet. Möjligt att det går men jag har då missat något viktigt i så fall för jag är inte i närheten vare sig med eller utan solver.

Hur som helst så har jag gått över till att lösa det hela i Qt/C++ istället då det känns som en betydligt stabilare/snabbare väg att gå. Dyker säkerligen upp en tråd om det snart också då jag är tämligen orutinerad i att kompliera C-program och ska på något vis få C-koden att exekvera ett m-script för Octave eller också använda något bibliotek för olinjär numerisk lösning. Kommer sannolikt behöva hjälp med detta.
Hoppas ingen kommer hata mig för att jag ställer noob-frågor om C++ programmering.

Ha en fin helg allesammans!
/Tottish