Re: [Neo] Alternative Layout-Berechnung
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
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
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
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
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.
[Neo] Alternative Layout-Berechnung
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
