Re: [Neo] Alternative Layout-Berechnung

2011-04-22 Diskussionsfäden Marco Antoni

Hallo Liste und Joke,

Am 18.04.2011, 10:11 Uhr, schrieb Joke de Buhr j...@seiken.de:

 natürlich nicht auf anhieb verstanden.


Hoffe, nach mehrmaligem Durchlesen war es dann doch verständlich.

  Aber mal anders gefragt: Du meintest du hättest da schon ein  
ähnliches Programm vorliegen. a) Welche

 Programmiersprache b) hast du es mal modifiziert c) kann man etwas
 betrachten?



Das Programm ist in C++ geschrieben, allerdings ist der Code nicht sehr  
schön. Es vertauscht Spalten einer Matrix per Backtracking, um die  
Diagonale mit 1en zu füllen. Es gibt nur Einträge mit 1 und 0.
Zu modifizieren sind also die zulässigen Werte für Einträge und das  
Renormieren nach dem Vertauschen. Die Laufzeit ist recht gut, nur das  
initiale Sortieren läuft über bidirektionales Bubblesort (bei 1000*1000  
experimentell O(10s), also vernachlässigbar gegenüber der restlichen  
Laufzeit).


Ein Hinweis, wie man gewichtete Optimierungsprobleme sehr gut Lösen  
kann.

Es gibt da ein Programm namens lpsolve [1]. Ich weiß nicht, ob es jetzt
gerade mit dem bestehenden Gedankengang weiterhilft, generell ließe sich
lpsolve allerdings für hier einsetzen. Das fällt in den Bereich Linear
Programming.

  [1] http://lpsolve.sourceforge.net/


Das klingt sehr interessant. Schau ich mir die Tage mal an.

Gruß, Marco8



Re: [Neo] Alternative Layout-Berechnung

2011-04-18 Diskussionsfäden Joke de Buhr
On Monday 18 April 2011 02:45:31 Michael Gattinger wrote:
 Da dir bisher keiner geantwortet hat mache ich das mal gerne:
 Ich hab mir deinen Text mal bis zur hälfte durchgelesen und habs
 natürlich nicht auf anhieb verstanden. Aber mal anders gefragt: Du
 meintest du hättest da schon ein ähnliches Programm vorliegen. a) Welche
 Programmiersprache b) hast du es mal modifiziert c) kann man etwas
 betrachten?
 
 Kannst dich ja sonst mal bei mir melden.
 
 Am 19.03.2011 18:49, schrieb Marco Antoni:
  Hi Leute,
  
  wie schon im Chat vorgestellt, habe ich mir eine Methode zur
  Berechnung der besten Layouts zu gegebenen Kriterien und Gewichten als
  Alternative zu Arnes genetischem Algorithmus überlegt.
  Eine Zusammenfassung findet ihr unter
  http://dl.dropbox.com/u/837165/neo/layoutberechnung und im Chat habe
  ich folgendes dazu geschrieben:
  
  Die größte Schwierigkeit sehe ich darin, die Funktion und die Matrix
  als Funktion der Konstanten zu bestimmen. Zur Lösung der numerischen
  Matrix habe ich vor einiger Zeit ein Programm geschrieben, das ein
  ähnliches Problem ungefähr wie im ersten vorgeschlagenen Algorithmus
  löst und nur wenig modifiziert werden muss (aber sicher stark
  optimiert werden kann). Dieses Programm spuckt die ersten Lösungen
  einer 1000*1000-Matrix nach wenigen Sekunden aus. Die perfekte Lösung
  ist natürlich nie garantiert dabei, aber durch die Konstruktion kommen
  gleich zu Beginn sehr gute Lösungen raus und nach kurzer Zeit
  (Größenordnung wenige Minuten) ist die sicher beste gefunden.
  Das Problem hier ist einerseits rechenaufwendiger (zumindest mit
  meinen Algorithmen durch die andauernde Normierung), andererseits nur
  32*32 groß statt 1000*1000 … imho ist das machbar :-)
  
  Diskussion und Realisierungshilfe (wie löst man ein Gleichungssystem
  mit 1000 Gleichungen? Software?) erwünscht.

Ein Hinweis, wie man gewichtete Optimierungsprobleme sehr gut Lösen kann. Es 
gibt da ein Programm namens lpsolve [1]. Ich weiß nicht, ob es jetzt gerade 
mit dem bestehenden Gedankengang weiterhilft, generell ließe sich lpsolve 
allerdings für hier einsetzen. Das fällt in den Bereich Linear Programming.


  [1] http://lpsolve.sourceforge.net/


  Grüße, Marco8

Viele Grüße
Joke


signature.asc
Description: This is a digitally signed message part.


Re: [Neo] Alternative Layout-Berechnung

2011-04-18 Diskussionsfäden Joke de Buhr
On Monday 18 April 2011 09:56:37 you wrote:
 On Monday 18 April 2011 02:45:31 Michael Gattinger wrote:
  Da dir bisher keiner geantwortet hat mache ich das mal gerne:
  Ich hab mir deinen Text mal bis zur hälfte durchgelesen und habs
  natürlich nicht auf anhieb verstanden. Aber mal anders gefragt: Du
  meintest du hättest da schon ein ähnliches Programm vorliegen. a) Welche
  Programmiersprache b) hast du es mal modifiziert c) kann man etwas
  betrachten?
  
  Kannst dich ja sonst mal bei mir melden.
  
  Am 19.03.2011 18:49, schrieb Marco Antoni:
   Hi Leute,
   
   wie schon im Chat vorgestellt, habe ich mir eine Methode zur
   Berechnung der besten Layouts zu gegebenen Kriterien und Gewichten als
   Alternative zu Arnes genetischem Algorithmus überlegt.
   Eine Zusammenfassung findet ihr unter
   http://dl.dropbox.com/u/837165/neo/layoutberechnung und im Chat habe
   ich folgendes dazu geschrieben:
   
   Die größte Schwierigkeit sehe ich darin, die Funktion und die Matrix
   als Funktion der Konstanten zu bestimmen. Zur Lösung der numerischen
   Matrix habe ich vor einiger Zeit ein Programm geschrieben, das ein
   ähnliches Problem ungefähr wie im ersten vorgeschlagenen Algorithmus
   löst und nur wenig modifiziert werden muss (aber sicher stark
   optimiert werden kann). Dieses Programm spuckt die ersten Lösungen
   einer 1000*1000-Matrix nach wenigen Sekunden aus. Die perfekte Lösung
   ist natürlich nie garantiert dabei, aber durch die Konstruktion kommen
   gleich zu Beginn sehr gute Lösungen raus und nach kurzer Zeit
   (Größenordnung wenige Minuten) ist die sicher beste gefunden.
   Das Problem hier ist einerseits rechenaufwendiger (zumindest mit
   meinen Algorithmen durch die andauernde Normierung), andererseits nur
   32*32 groß statt 1000*1000 … imho ist das machbar :-)
   
   Diskussion und Realisierungshilfe (wie löst man ein Gleichungssystem
   mit 1000 Gleichungen? Software?) erwünscht.
 
 Ein Hinweis, wie man gewichtete Optimierungsprobleme sehr gut Lösen kann.
 Es gibt da ein Programm namens lpsolve [1]. Ich weiß nicht, ob es jetzt
 gerade mit dem bestehenden Gedankengang weiterhilft, generell ließe sich
 lpsolve allerdings für hier einsetzen. Das fällt in den Bereich Linear
 Programming.
 
   [1] http://lpsolve.sourceforge.net/
 

Vielleicht noch ein sehr kurzes Beispiel zu lpsolve:

Man gibt eine Zielsetzung an, wie etwa

  max: a + b;

Anschließend folgen und-verknüpfte Regeln wie:

  a = 5;
  a  2;
  b = 10;
  b = 3;

Man lässt dann alles durch lpsolve laufen und erhält eine optimale Belegung 
der Variablen geliefert, welche das Gleichungssystem erfüllen. Für eine 
komplette Tastaturbelegung werden die Gleichungssysteme entsprechend größer 
und komplexer, jedoch ist lpsolve hier sehr gut, da es zum Modelchecking 
verwendet wird.


   Grüße, Marco8
 
 Viele Grüße
 Joke

Viele Grüße
Joke


signature.asc
Description: This is a digitally signed message part.


Re: [Neo] Alternative Layout-Berechnung

2011-04-17 Diskussionsfäden Michael Gattinger

Da dir bisher keiner geantwortet hat mache ich das mal gerne:
Ich hab mir deinen Text mal bis zur hälfte durchgelesen und habs 
natürlich nicht auf anhieb verstanden. Aber mal anders gefragt: Du 
meintest du hättest da schon ein ähnliches Programm vorliegen. a) Welche 
Programmiersprache b) hast du es mal modifiziert c) kann man etwas 
betrachten?


Kannst dich ja sonst mal bei mir melden.

Am 19.03.2011 18:49, schrieb Marco Antoni:

Hi Leute,

wie schon im Chat vorgestellt, habe ich mir eine Methode zur 
Berechnung der besten Layouts zu gegebenen Kriterien und Gewichten als 
Alternative zu Arnes genetischem Algorithmus überlegt.
Eine Zusammenfassung findet ihr unter 
http://dl.dropbox.com/u/837165/neo/layoutberechnung und im Chat habe 
ich folgendes dazu geschrieben:


Die größte Schwierigkeit sehe ich darin, die Funktion und die Matrix 
als Funktion der Konstanten zu bestimmen. Zur Lösung der numerischen 
Matrix habe ich vor einiger Zeit ein Programm geschrieben, das ein 
ähnliches Problem ungefähr wie im ersten vorgeschlagenen Algorithmus 
löst und nur wenig modifiziert werden muss (aber sicher stark 
optimiert werden kann). Dieses Programm spuckt die ersten Lösungen 
einer 1000*1000-Matrix nach wenigen Sekunden aus. Die perfekte Lösung 
ist natürlich nie garantiert dabei, aber durch die Konstruktion kommen 
gleich zu Beginn sehr gute Lösungen raus und nach kurzer Zeit 
(Größenordnung wenige Minuten) ist die sicher beste gefunden.
Das Problem hier ist einerseits rechenaufwendiger (zumindest mit 
meinen Algorithmen durch die andauernde Normierung), andererseits nur 
32*32 groß statt 1000*1000 … imho ist das machbar :-)


Diskussion und Realisierungshilfe (wie löst man ein Gleichungssystem 
mit 1000 Gleichungen? Software?) erwünscht.


Grüße, Marco8







Re: [Neo] Alternative Layout-Berechnung

2011-04-17 Diskussionsfäden Arne Babenhauserheide
Ach verdammt, stimmt… ich sollte immer eine explizite Todo-Liste führen…

On Monday 18 April 2011 02:45:31 Michael Gattinger wrote:
 Da dir bisher keiner geantwortet hat mache ich das mal gerne:
 Am 19.03.2011 18:49, schrieb Marco Antoni:
  Diskussion und Realisierungshilfe (wie löst man ein Gleichungssystem
  mit 1000 Gleichungen? Software?) erwünscht.

Die Frage, die ich eigentlich schon im März stellen wollte: Geht das den
Gradienten nach (danach klang der Text für mich), oder prüft es wirklich jede
Möglichkeit (wenn auch erst nur ungenau)?

Liebe Grüße,
Arne

signature.asc
Description: This is a digitally signed message part.