Entgeltliche Optimierung eines Agent-based models

Wie rufe ich R-Funktionen auf, wie selektiere ich Daten, ich weiß nicht genau ....

Moderatoren: EDi, jogo

Anti
Beiträge: 23
Registriert: Di Nov 06, 2018 10:48 am

Entgeltliche Optimierung eines Agent-based models

Beitrag von Anti » Di Nov 06, 2018 11:13 am

Hallo zusammen,

im Rahmen meiner Diss untersuche ich die Besiedelungsgeschichte Polynesiens. Um mögliche Szenarien gegeneinander abzuwägen, habe ich in R ein agenten-basiertes Modell (ABM) erstellt, welches für 242 geographische Gruppen mit max. 120 x 1.0003^t Individuen über einen Zeitraum von 4500 Jahren Migrationen zwischen den Populationen (diese werden als "Deme" bezeichnet, Singular "Dem" - Referenz für Flow Chart) simuliert.

Das Ganze funktioniert bisher, auch wenn das Modell noch nicht vollständig ist (Flow Chart ist angehängt). Bislang habe ich lediglich den Tod der Individuen sowie die Migration zwischen den Populationen implementiert. Allerdings benötigt die Simulation im ersten Jahr (in dem noch nicht mal alle möglichen Populationen existieren - sie werden erst später mit dem Einsetzen von 14C-Datierungen besiedelt) für einen Durchgang (1 Jahr) etwa 30 Minuten.

Ich möchte daher nachfragen, ob mir Jemand von Euch dabei behilflich sein könnte, die Performanz meines Modells zu steigern (Vektorisierung, Ersetzen von Data Frames durch data.tables, Parallelisierung, etc.). Der Code selbst ist nicht sonderlich groß, das ABM umfaßt aktuell (noch unfertig) gerade < 100 Zeilen. Gerne bezahle ich dafür auch einen Obolus. Sofern Interesse besteht, schreibt mir bitte hier oder eine pm mit Eurer Mailadresse.

Vielen Dank im Voraus!
Anti
Dateianhänge
Flow Chart.pdf
(25.22 KiB) 51-mal heruntergeladen

bigben
Beiträge: 1057
Registriert: Mi Okt 12, 2016 9:09 am

Re: Entgeltliche Optimierung eines Agent-based models

Beitrag von bigben » Di Nov 06, 2018 12:50 pm

Hallo Anti,

vorneweg: Ich bin der falsche, andere hier können das mit dem Beschleunigen viel besser. Ich wollte aber gerne schreiben, dass ich mich freue, dass und wie Du die Arbeit dargestellt hast. Das klingt auch für den fachfremden sehr interessant. Erzählst Du uns noch, was Autosomen sind? Die kannte ich bislang nur aus der Genetik.

Zwei Tipps vielleicht vorab, fallst Du nicht sofort jemanden findest:
1. Ich könnte mir vorstellen, dass Du im Laufe Deines Ablaufs sehr viele Zufallsentscheidungen und Zufallszahlen generierst. Hier kann man viel Zeit sparen, wenn man viele Zufallszahlen gleichzeitig und nicht nacheinander abfragt. Vergleiche mal folgende Kommandos:

Code: Alles auswählen

for(i in 1:1e7) rnorm(1)
rnorm(1e7)
Dafür brauchst Du keine Stoppuhr, das fühlst Du auch so.
2. Kommen in Deinem Code viele for-Schleifen vor? Die willst Du wahrscheinlich durch Vektorisierung los werden. Bedenke, dass sich for-Schleifen oft durch foreach-Schleifen aus dem foreach Package ersetzen lassen und dass sie damit sehr leicht zu parallelisieren sind.

Wenn Du brauchbare Ansprechpartner gefunden hast würde ich Deinen Thread danach gerne für eine Interne Diskussion kapern, ob R für soetwas die richtige Sprache ist, oder ob man das nicht gleich in Julia angehen sollte. Steile These, denn die, die ich anspreche, können das auch in R schnell. Aber würde die Schnelligkeit mit einer compilierten Sprache wie C++ oder Julia nicht viel einfacher kommen, viel weniger Hirnschmalz kosten?

Dir erstmal viel Glück,
Bernhard
---
Programmiere stets so, dass die Maxime Deines Programmierstils Grundlage allgemeiner Gesetzgebung sein könnte

Benutzeravatar
EDi
Beiträge: 887
Registriert: Sa Okt 08, 2016 3:39 pm

Re: Entgeltliche Optimierung eines Agent-based models

Beitrag von EDi » Di Nov 06, 2018 4:50 pm

Aber würde die Schnelligkeit mit einer compilierten Sprache wie C++ oder Julia nicht viel einfacher kommen, viel weniger Hirnschmalz kosten?
Also schneller als netlogo ist R allemal.
Es kommt aber stark drauf an wie man das ibm implementiert. Dazu gibt auch einpaar Beispiele im Netz.

Wenn es nicht zu komplex ist, würde ich in R prototypisieren und dann auf rcpp portieren wenn zu lahm (und der R Code schon optimiert ist).

Oder einfach die Rechenleistung beim cloud-Provider mieten und mir die Kosten fürs refactoring dort investieren.
Bitte immer ein reproduzierbares Minimalbeispiel angeben. Meinungen gehören mir und geben nicht die meines Brötchengebers wieder.

Dieser Beitrag ist lizensiert unter einer CC BY 4.0 Lizenz
Bild.

Anti
Beiträge: 23
Registriert: Di Nov 06, 2018 10:48 am

Re: Entgeltliche Optimierung eines Agent-based models

Beitrag von Anti » Di Nov 06, 2018 6:03 pm

Hi,

vielen lieben Dank für die Antworten und sorry für die späte Rückantwort - war eben ziemlich busy. Natürlich habe ich schon mein Bestes mit dem Vektorisieren getan, muß aber klar zugeben, daß ich hier an meine Grenzen stoße (wegen fehlender Erfahrung mit ABMs). Mein Prototyp geht halt zunächst durch alle möglichen Individuenalter durch und sampled dann zufällig Individuen, die sterben. Da die Migrationswahrscheinlichkeit sowohl von der Migrationshäufigkeit und max. Migrationsweite der Papuaner, der Migrationshäufigkeit der Austronesier, von der Vernetzung (erzeugt mittles Delaunay-Triangulaten) und den Migrationsdistanzen der zum Zeitpunkt t besiedelbaren Deme ausgeht, habe ich hier relativ viele if-Bedingungen und iteriere durch alle Deme durch. Und mit Autosomen sind auch die Autosomen aus der Genetik, also (Gene auf den) Nicht-Geschlechtschromosomen gemeint.

RCPP wäre natürlich auch eine brauchbare Lösung - allerdings habe ich damit bislang noch nicht gearbeitet.

Wenn Ihr noch mehr wissen wollt oder weitere Anregungen habt, bin ich jederzeit offen. Natürlich können Lösungen dann hier auch als exemplarische Fälle zur Diskussion dienen.

Anti
Beiträge: 23
Registriert: Di Nov 06, 2018 10:48 am

Re: Entgeltliche Optimierung eines Agent-based models

Beitrag von Anti » Di Nov 06, 2018 8:53 pm

Anbei nun mein bisher geschriebener R-Code sowie die benötigten Dateien.
  • "admixture rates" enthält geschätzte "Verwandtschafts"-Koeffizienten, die am Ende der 4500 simulierten Zeitschritte mit dem Modell-Output (für einen gegebenen Parameter-Range verglichen werden sollen
  • "history" enthält Informationen über die Besiedelung einzelner Deme bzw. die Ankunftszeit der austronesischen Migranten
  • "migration" ist eine Liste, die für jede Population (Informationen der i-ten Population werden mit migration[ [ i ] ] erhalten) einen "probability"-Wert enthält, mit dessen Hilfe Migranten auf die aufgelisteten Populationen aufgeteilt werden, und eine "normalized distance", welche dazu genutzt wird um Migrationen über lange Wegstrecken für überwiegend papuanische Individuen zu unterbinden (vgl. R-Code "slow boat.R").
Dateianhänge
files.7z
(30.9 KiB) 28-mal heruntergeladen

bigben
Beiträge: 1057
Registriert: Mi Okt 12, 2016 9:09 am

Re: Entgeltliche Optimierung eines Agent-based models

Beitrag von bigben » Mi Nov 07, 2018 9:13 am

EDi hat geschrieben:
Di Nov 06, 2018 4:50 pm
Oder einfach die Rechenleistung beim cloud-Provider mieten und mir die Kosten fürs refactoring dort investieren.
Hallo EDi,

grundsätzlich ein guter Gedanke, aber mal überschlagsweise: Das Modell ist noch nicht fertig, braucht aber 30 Minuten pro Jahr. Simuliert werden sollen 4500 Jahre, also braucht das unfertige Modell schon 94 Tage. Man will ja wahrscheinlich n > 1 mal das Modell laufen lassen und auch wenn ich nicht weiß, welche Beschleunigung man von schnellerer Hardware erwarten darf, würde ich auch erst Versuchen, einen guter R'ler mit der Beschleunigung zu beschäftigen oder eine complilierte Sprache ins Auge zu fassen, bevor ich das mit Rechenpower zu erschlagen versuche. Als compilierte Sprache bevorzugt eine, die Parallelisierung leicht macht. Mit Blick auf letzteres weiß ich nicht, ob C++ da die optimale Wahl ist.

LG,
Bernhard


PS: Ok, ich gebe zu, dass ich auch das Geld lieber bei bei Student oder bei consuli sehen würde, als bei Amazon und Co.
---
Programmiere stets so, dass die Maxime Deines Programmierstils Grundlage allgemeiner Gesetzgebung sein könnte

jogo
Beiträge: 1473
Registriert: Fr Okt 07, 2016 8:25 am

Re: Entgeltliche Optimierung eines Agent-based models

Beitrag von jogo » Mi Nov 07, 2018 9:27 am

Hallo Anti,
Anti hat geschrieben:
Di Nov 06, 2018 6:03 pm
Wenn Ihr noch mehr wissen wollt oder weitere Anregungen habt, bin ich jederzeit offen. Natürlich können Lösungen dann hier auch als exemplarische Fälle zur Diskussion dienen.
ich habe mir das Skript angesehen und habe meine Schwierigkeiten, es zu lesen. Das liegt u.a. an folgenden Eigenheiten:
  • Du verwendest Matrizen auch dort, wo es sich eigentlich um Dataframes handelt.
  • Du verwendest zum Zugriff auf die Spalte stets die Nummer und nicht den Spaltennamen (wenn Du das so machst, bräuchtest Du keine Namen für die Spalten).
  • Auch die Zeilenbereich werden an jeder Stelle im Code fest kodiert; Beispiel: sehr häufig taucht die Zahl 21000 auf. Warum steht nicht am Anfang des Skripts anzahlIrgendwas <- 21000 ?
  • einige Daten liegen getrennt, obwohl sie zusammen gehören, z.B. death.rate und birth.rate in Abhängigkeit vom Alter.
  • Es gibt zwei verschiedene Objekte death.rate: erst eine Matrix, dann einen Vektor.
Der Umfang des Quelltextes ist schon so groß, dass ich es mir nicht recht zutraue, die Datenstrukturen in eine bequeme Form abzuändern.
Hier aber ein Beispiel dafür, wie ich denersten Teil schreiben würde:

Code: Alles auswählen

#death rates #birth rate
#(from Pietrusewsky, M, Douglas, MT, & Ikehara-Quebral, RM (1997) An Assessment of Health and Disease in the Prehistoric Inhabitants of the Mariana Islands. Am. J. Phys. Anthropol. 104: 315 - 342.)
BD <- data.frame(age=0:55, 
        death_rate=c(0.02, 0.035, 0.0476, 0.07, 0.09, 0.1, 0.1032, 0.1032, 0.093, 0.072, 0.05, 0.047, 0.046, 0.0443, 0.048, 0.055, 0.062, 0.064, 0.0648, 0.073, 0.08, 0.09, 0.093, 0.098, 0.123, 0.145, 0.167, 0.18, 0.1965, 0.198, 0.1995, 0.201, 0.202, 0.2036, 0.23, 0.25, 0.268, 0.27, 0.2757, 0.278, 0.28, 0.283, 0.285, 0.286, 0.29, 0.31, 0.37, 0.42, 0.5, 0.62, 0.73, 0.84, 0.89, 0.94, 0.97, 1),
        birth.rate=c(0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0.001, 0.003, 0.01, 0.04, 0.09, 0.13, 0.17, 0.24, 0.27, 0.29, 0.31, 0.31, 0.295, 0.28, 0.265, 0.245, 0.225, 0.205, 0.19, 0.17, 0.15, 0.13, 0.11, 0.09, 0.075, 0.06, 0.045, 0.03, 0.01, 0.007, 0.0055, 0.0035, 0.0025, 0.0024, 0.0022, 0.0015, 0.001, 0.0005, 0.0001, 0, 0, 0, 0, 0)
)
BD$survival   <- with(BD, { s <- cumsum(death_rate); s <- max(s)-s; s <- s/sum(s); c(s[1:55], NA)})
BD$death.rate <- c(0, -diff(BD$survival/BD$survival[1]), 1)
Der nächste Teil sähe so aus:

Code: Alles auswählen

PopulParam <- list(
  asian.fecundities   = c(3, 4, 5, 6, 7),
  papuan.fecundities  = c(3, 4, 5, 6, 7),
  asian.migrations    = c(0.1, 0.2, 0.3, 0.4, 0.5, 0.6, 0.7, 0.8),
  papuan.migrations   = c(0.1, 0.2, 0.3, 0.4, 0.5, 0.6, 0.7, 0.8),
  marriage.weights    = c(0.00, 0.05, 0.10, 0.15, 0.20, 0.25),
  migration.distances = c(0.2, 0.4, 0.6, 0.8, 1.0)
)
runsummary <- expand.grid(PopulParam)
runsummary <- runsummary[rep(1:nrow(runsummary), 100),]
runsummary <- data.frame(runID=1:nrow(runsummary), runsummary, Aauto=NA, Amt=NA, AY=NA)
Der Teil mit der Migration könnte so aussehen:

Code: Alles auswählen

#migration
Subset <- subset(runlist, (t-BirthYear > 11) & is.na(DeathYear) & is.na(partner) & BirthPlace==residence)
Subset <- Sample[sample.int(nrow(Subset)),]
Gruß, Jörg

Anti
Beiträge: 23
Registriert: Di Nov 06, 2018 10:48 am

Re: Entgeltliche Optimierung eines Agent-based models

Beitrag von Anti » Mi Nov 07, 2018 10:15 am

jogo hat geschrieben:
Mi Nov 07, 2018 9:27 am
ich habe mir das Skript angesehen und habe meine Schwierigkeiten, es zu lesen. Das liegt u.a. an folgenden Eigenheiten:
Hi jogo,

vielen Dank für Deine Kritik, die ich natürlich gerne annehme. Ich werde versuchen morgen etwas mehr Ordnung in das Chaos zu bringen. Dann werde ich mich wieder melden.

Beste Grüße
Anti

jogo
Beiträge: 1473
Registriert: Fr Okt 07, 2016 8:25 am

Re: Entgeltliche Optimierung eines Agent-based models

Beitrag von jogo » Mi Nov 07, 2018 10:45 am

Hallo Anti,

ich habe schon die ersten zwei Teile nach meinem Gusto umgestaltet (siehe vorherige Nachricht).
Ab da wird es etwas komplizierter (weitere Datenobjekte, die umgestylt werden sollten, und Verquickung mit den bisherigen), aber das Prinzip der möglichen Vereinfachungen ist ähnlich.

noch eine Anmerkung:
subset() ist eine R-Funktion, die man sich nicht verbauen sollte, indem man eigene Objekte so nennt.

und noch eine:
Du kannst profitieren von der Technik: Indizieren mit logischem Vektor.

Gruß, Jörg

Benutzeravatar
EDi
Beiträge: 887
Registriert: Sa Okt 08, 2016 3:39 pm

Re: Entgeltliche Optimierung eines Agent-based models

Beitrag von EDi » Mi Nov 07, 2018 4:06 pm

bigben hat geschrieben:
Mi Nov 07, 2018 9:13 am
EDi hat geschrieben:
Di Nov 06, 2018 4:50 pm
Oder einfach die Rechenleistung beim cloud-Provider mieten und mir die Kosten fürs refactoring dort investieren.
Hallo EDi,

grundsätzlich ein guter Gedanke, aber mal überschlagsweise: Das Modell ist noch nicht fertig, braucht aber 30 Minuten pro Jahr. Simuliert werden sollen 4500 Jahre, also braucht das unfertige Modell schon 94 Tage. Man will ja wahrscheinlich n > 1 mal das Modell laufen lassen und auch wenn ich nicht weiß, welche Beschleunigung man von schnellerer Hardware erwarten darf, würde ich auch erst Versuchen, einen guter R'ler mit der Beschleunigung zu beschäftigen oder eine complilierte Sprache ins Auge zu fassen, bevor ich das mit Rechenpower zu erschlagen versuche. Als compilierte Sprache bevorzugt eine, die Parallelisierung leicht macht. Mit Blick auf letzteres weiß ich nicht, ob C++ da die optimale Wahl ist.

LG,
Bernhard


PS: Ok, ich gebe zu, dass ich auch das Geld lieber bei bei Student oder bei consuli sehen würde, als bei Amazon und Co.
Agree. Meine Rechnung geht auch nur auf, wenn man einfach parallelsieren kann (z. b. mclapply oder furrr drumrum/als schleife), man faul ist und mit miesem code leben kann. Sicherlich eine hässliche Lösung.
Eine Stunde bei einem consultant kostet vermutlich irgendwas um die 150€.
Ein Stunde amazon aws mit 72 Kernen und 140GB RAM kosten irgendwas um die 3 €. Für 150 € kann ich also 50 Stunden rechnen und hat 3600runs durch.

Was auch billig ist (falls man viel Algebra im code hat): das BLAS auf openblas oder intel mkl wechseln. Gibst für lau und die speedups z. b. bei eigenwertzerlegungen sind im 2stelligen prozentbereich. Unter Linux hat man das ruckzuck eingerichtet.
Bitte immer ein reproduzierbares Minimalbeispiel angeben. Meinungen gehören mir und geben nicht die meines Brötchengebers wieder.

Dieser Beitrag ist lizensiert unter einer CC BY 4.0 Lizenz
Bild.

Antworten