Kabeldragningsoptimering!! Algoritmförslag sökes!

[DiyJohn]

Vet ej om detta är rätt kategori att posta i men det hela handlar ju i grunden om elektronik!

Jag satte mig och funderade på hur kabeldragningsoptimering skulle fungera om man skulle få börja från grunden. Jag har kommit en bit i funderingarna och har nu stypt!

Problemet och förutsättningar är förenklade jämfört med verkligheten!:

*Det finns kraftverk som producerar energi, dessa enheter har en position och en given mängd överskottsenergi beroende på storlek på kraftverk.
*Det finns också städer som förbrukar energi, dessa enheter har en position och förbrukar en given mängd energi beroende på storleken på staden.
*Till sist finns det kablar som överför energi, dessa enheter kopplar ihop städer med städer och städer med kraftverk. Kablarna finns i en begränsad variation tjocklekar, tjockare kablar kan överföra mer energi men kostar per distansenhet också mer.

Problemet: minimera kabelkostnaden när alla städer får tillräckligt med energi!

Ex.
Städer ligger placerade på olika platser i ett koordinatsystem, låt säga att det är 8 städer i varierande storlek. I samma koordinatsystem ligger två kraftverk på två olika platser. Kablage av tre olika tjocklekar ska nu koppla ihop städerna och kraftverken för att tillfredställa alla städer till minsta möjliga kostnad. Priset på kablaget är inte nödvändigtvis proportionellt med dess kapacitet.

Min approach:
Allt detta i Matlab:
Jag gör en lista med alla byggnader, d.v.s. de 8 städerna och de två kraftverken. Alltså en 10 enheter lång lista med producenter och förbrukare.
En 10x10 tabell skapas som motsvarar föregående lista där varje cell motsvarar en möjlig kabelväg från och till alla byggnader. I dessa celler sätter jag* in värden, 0 till 3, som motsvarar tjockleken på kablarna. Om 0 så finns där ingen kabelväg.

jag*: Jag använder en genetisk algoritm som beräknar de bästa (billigaste) alternativen.

När jag kopplar in optimeringalgoritmen, den genetiska, bör jag kontrollera att alla städer är tilllfredställda. Detta gör jag enligt följande: jag tar den första byggnaden i listan och kollar i tabellen vilka den är kopplad till. Sedan flaggar jag dessa och lägger ihop deras totala energi-förbrukning/produktion med den första. Detta är nu deras gemensamma energi. Sedan går jag till nästa flaggade byggnad och kollar om den är kopplad till någon oflaggad. Om så är fallet flaggas dom och adderas till den gemensamma energin. Annars går turen till nästa flaggade byggnad. Om alla flaggade byggnader haft sin tur och det fortfarande finns oflaggade "fria" byggnader startas en ny gemensam energi utifrån den första oflaggade i listan och dess kontakter. O.S.V.
Om alla byggnader nu har en positiv energi är alla städer tillfredställda, förutsatt att kraftverken producerar mer än städerna drar.

Denna kontroll är som ni ser inte alls särskilt smidig och jag undrar nu!!: Har någon ett bättre förslag? Om jag ens gjort mig förstådd!

Tack /John

[idiotdea]

Det skulle vara bra med lite mer information. Är förbrukninen/produktionen vid varje "enhet" konstant och definierad?

Ett litet problem är att även om kablarna tillåter att tillräckligt med energi överförs till en förbrukare, betyder det inte att det i praktiken går att överföra tillräckligt med energi (effekt) dit. Tänk dig ett enkelt exempel: ett kraftverk och två städer, där första staden är kopplad till kraftverket med en (t.ex.) 12 MW kabel och kopplad till andra staden med en 10 MW kabel. Andra staden är inte kopplat till någonting annat än första staden. Städerna förbrukar båda 10 MW. Då räcker det endast 2 MW till den andra staden. Eller har jag missat någonting?

Själv skulle jag nog ha försökt mig på en MILP-formulering (mixed integer linear programming) till detta problem. Fast det är klart, blir "världen" stor så kommer väggen så småningom emot med en sådan. Å andra sidan får man antagligen också konvergensproblem med en genetisk algoritm

Men lite mera information skulle hur som helst vara bra.

[Nerre]

Det är väl nästan samma typ av problem som "handelsresandens problem"?

[DiyJohn]

idiotdea: Du har rätt i dedär med att kablarna måste kunna försörja flera städer i serie. Den första kabeln efter kraftverket bör vara tjockare än de senare. Som svar på din fråga: förbrukningen/produktionen är konstant och definierad. Jag ska ta en titt på MILP!

Nerre: Skillnaden mellan detta problem och handelsresandens är att i vårat problem "reser" vi bara enkelväg och ykorsningar utgör inte nödvändigtvis omväg. I handels. ligger alla enheterna i serie medan de i vårt problem kan vara parallella!

[Icecap]

Exakt samma problematik som när man ska bygga vägar: hur får man kortaste vägar och bäst täckning.

Efter vad jag har sett har många givit upp i detta men det finns en lösning som jag såg med vägarna (så det i Illuderat Vetenskap):
Man skruvar pinnar fast i en plastskiva, pinnarna representerar de viktiga knutpunkter. Sedan doppar man rubbet ner i såpvatten och lyfter upp lite så att "såpbubblorna" fördelar sig varpå man tar kort på denna fördelning. "Bubblorna" vill ha kortast längd och om t.ex. en väg ska delas upp till 2 ställen placeras delningspunktet "automatisk" rätt.

Jag skulle tro att det borde gå att iterera fram en lämplig delning men när det blir fler punkter kommer denna iterering att bli mycket komplex och sannolikt ha fler lösningar.

[v-g]

Pinsamt nog går detta att lösa med såpbubblor om man nu får till det så visar de automatiskt bästa vägen

Vet iaf att det går med tre punkter.

Tyvärr tror jag inte att detta hjälper dig

[xxargs]

Det där kan man nog analysera med en spice-simulator, som är just byggd för att räkna på elektriska kretsar som problemet egentligen handlar om.

glöm inte att räkna på kablarnas förluster beroende på distans mellan städerna - kan ge ganska obehagliga förlustvärden som ökar snabbt i slutet (exponentiellt med distansen) när ledningarna börja bli lite långa...

Även elström mår bäst av att vara närproducerat...

[Icecap]

Det går inte att räkna fram mest optimal kabeldragning med en spice-simulator! Den kan dock räkna ihop resultatet.

[xxargs]

nu har jag inte studerat problemet i detalj, men en del kommersiella spicesimulator har via sina skal har möjlighet att numeriskt prova sig fram - montecarlo-tester tex. för att se verkan av komponentspridningar är kanske användbar - även olika typer av RF-simulatorer typ Ansoft har olika former av optimeringsverktyg för att prova sig fram tills uppnådd villkor - det har jag använt av mig när man skall optimera fram kabelängder för att kombinera filter mm. - ok man kanske inte hittar den mest optimala lösningen - men i tekniksammanhang så handlar det oftast om att hitta tillräckligt _bra_ lösning.

[SvenW]

Är inte det här ett fall för Dijkstras Algoritm?

[DiyJohn]

SvenW: Tack för tipset men det verkar som att Dijkstras algoritm är till för att hitta billigaste vägen från A till B, inte hitta billigaste sättet att koppla ihop alla enheter med varandra!

Sedan vill jag gärna påpeka att såpbubbel-lösningen troligtvis löser problemet med den kortaste kabeldragningen men man måste ju också väga in att det krävs olika tjocklekar på kablarna och detta kan inte såpbubblor hantera.

[Icecap]

Så sant så men när man vet hur man drar och längder är resten relativt enkelt att räkna ut detta.

Men efter att ha läst lite mer noga är det ju en fast uppgift utan delningspunkter, alltså en orealistisk skoluppgift varför alt detta med bubblor osv är överkurs.

[DiyJohn]

Icecap: Tack för synpunkter. Som jag skrev i ett tidigare inlägg: kostnaden för kabeln är inte nödvändigtvis proportionell mot kapaciteten. ex. om tjockare kablar kostar mycket mer så skulle det finnas en större benägenhet att dra fler kablar istället för få tjocka!! Då funkar det inte att dra kortaste vägen och sedan bestämma tjocklek. + Detta är ingen skoluppgift, det är sånthär jag odlar i huvudet på fritiden... Jag vet, ärkenörd!

[idiotdea]

Men algoritmen du har kan du väl få problem av just den typen jag nämnde tidigare. Du borde alltså också veta hur mycket energi som överförs genom varje ledning.

Jag tycker att du är på helt rätt väg med en genetisk algoritm. Den självklara (men inte nödvändigtvis bästa) kromosomstrukturen är en (triangulär) matris där varje element är ett heltal mellan 0 och 3 som beskriver kabelstorleken mellan platsena definierade av raden och kolumnen. Nackdelen är att den strukturen tillåter ogiltiga lösningar, vilka alltså måste sorteras ut någonstans, t.ex. i fitness-funktionen. Detta är ofta problematiskt och tidskrävande.

Som sagt skulle jag antagligen själv ha försökt mig på en MILP-formulering. För de som inte vet hur det fungerar kan jag snabbt förklara.

MILP-crash-course:
Man har kontinuerliga (helt vanliga) men kan också ha heltalsvariabler. Det man ofta börjar med är att definiera en objektfunktion som man antingen vill minimera eller maximera. I det här fallet skulle det vara summan av kostnaden för varje installerad kabel. Sedan lägger man till bivillkor, som kan vara antingen olikhetsvillkor eller likhetsvillkor. Dessa "begränsar" lösningen, eller med andra ord ser till att den faktiskt är en möjligt lösning. I denna problemställning strävar objektfunktionen till att minimera kabelkostnaden, vilket i princip betyder att välja så små kablar som möjligt. Bivillkoren används för att se till att varje konsument får tillräckligt med energi.

Det finns program som löser dessa problem, t.ex. lp-solve är ett gratisprogram som fungerar okej med mindre problem. Lösningstiden för detta problem växer dock snabbt beroende på problemstorleken (antalet städer). Det fina med denna metod är att när en lösning har hittats, är den garanterat den bästa lösningen till problemet. Sådana garantier finns generellt inte med genetiska algoritmer.

Om det verkar intressant kan jag lösa en (ännu mindre) variant av ditt problem, bara för att visa hur det fungerar...

[AndLi]

Jag var ju tvungen att leka lite

http://www.andli.com/cable/main.php

Tanken var att negativa tal skulle beskriva förbrukare och positiva skulle vara generatorerna...
Går bara igenom alla enheter och försöker hitta närmaste, detta leder ju till öar.

Frågan är hur man smartast kopplar ihop öarna, att dra alla direkt till generatorn ger ju ganska långa men inte så kraftiga ledningar.. Jag är nig mest inne på att försöka hålla allt så kort som möjligt just nu. Då behöver jag nog märka ut förbrukare som har belastning och sen försöka hitta kortaste vägen mellan en som har och inte har...

edit: Nu kommer nog inte min ISP bli så glad på mig....