![\"Schematische](\"https:\/\/industry-science.com\/wp-content\/uploads\/2024\/03\/Berger_IM-23-1_Bild-1-1024x647.jpg\")
Evolution\u00e4re Algorithmen (EA)<\/h2>\n\n
F\u00fcr evolution\u00e4re Algorithmen ist der entscheidende Punkt die Wahl der entsprechenden Komponenten (Kodierung, Selektion, Rekombination und Mutation). Sie alle m\u00fcssen zueinander passen und gleichzeitig zur Problemstellung (Zielfunktion und Suchraum). [1] gibt eine gut verst\u00e4ndliche Einf\u00fchrung in die Thematik.<\/p>\n\n
Ist die Zielfunktion der Optimierung unbekannt oder nur kostenintensiv zu berechnen (beispielsweise durch Experimente oder das L\u00f6sen komplexer Gleichungen), k\u00f6nnen approximierte Zielfunktionen gute Dienste leisten. Hierf\u00fcr werden zun\u00e4chst in einer Vorbereitungsphase Trainingsdaten gesammelt und dann wird mithilfe eines geeigneten Verfahrens des maschinellen Lernens, z. B. neuronale Netze, die Zielfunktion gesch\u00e4tzt. Im Optimierungsprozess kann dann diese Sch\u00e4tzung verwendet werden, die kosteng\u00fcnstiger ist.<\/p>\n\n
Nat\u00fcrlich hat die Nutzung der gesch\u00e4tzten Funktion ihre Nachteile, insbesondere in Bereichen des Suchraums, f\u00fcr die die Sch\u00e4tzung weniger gut gelingt. Hier gibt es allerdings Techniken wie zum Beispiel die Einbeziehung der Verteilung der Trainingsdaten, sodass der negative Einfluss der Sch\u00e4tzung auf den Erfolg der Optimierung m\u00f6glichst geringgehalten wird. Diese Notwendigkeit erfordert eine Form der Kodierung, die es erm\u00f6glicht, diese gesch\u00e4tzte Zielfunktion anzuwenden. Einen \u00dcberblick \u00fcber die Thematik der approximierten Fitnessfunktionen findet sich in [2].<\/p>\n\n
Sei in K\u00fcrze ein Standardbeispiel betrachtet (zum besseren Verst\u00e4ndnis): Dieser Fall ist eine Kostenfunktion, die minimiert werden soll mit f\u00fcnf Eingabevariablen, die alle numerisch sind. Hier ist eine Kodierung sinnig, die die Identit\u00e4t darstellt, d. h. ein L\u00f6sungskandidat wird als Tupel seiner Werte dargestellt (x1, x2, x3, x4, x5). Als \u00adRekombination lie\u00dfe sich gut ein Operator w\u00e4hlen, der zuf\u00e4llig einen auf der Verbindungslinie beider Eltern liegenden Punkt w\u00e4hlt.<\/p>\n\n
Soll der Suchraum explorativ erforscht werden, so k\u00f6nnen dies \u201eau\u00dferhalb\u201c der Eltern liegende Punkte sein, soll der Suchraum feingranular erforscht werden, lie\u00dfe sich der Operator auf die innenliegenden Punkte beschr\u00e4nken. Ein Mutationsoperator in diesem Fall k\u00f6nnte die Addition eines Vielfachen der Standardabweichung der zur Mutation ausgew\u00e4hlten Variable sein (Bild 1). Die Wahl der Operatoren und ihrer Auspr\u00e4gung (Parameterwahl) ist entscheidend f\u00fcr die F\u00e4higkeit des Algorithmus, lokale Optima zu verlassen, um das globale Optimum zu erreichen.<\/p>\n\n
Der folgende Abschnitt erl\u00e4utert die Herkunft und Herausforderung von repetitiven Prozessen, d.h. Prozessen, die aus sich wiederholenden Grundprozessen bestehen, die die zugrunde liegende Forschung motiviert haben.<\/p>\n\n
Repetitive Prozesse<\/h2>\n\n
Prozesse sind ein essenzieller Bestandteil vieler Unternehmungen. Sie kommen in der Logistik vor, in der Herstellung, in der Forschung – auch die Wertsch\u00f6pfungskette selbst ist ein Prozess. Entsprechend h\u00e4ufig geht es eigentlich um eine Optimierung des gesamten Prozesses und nicht nur einzelner Parameter innerhalb dieses Prozesses. In der Methode \u201eFarbige Zust\u00e4nde\u201c [3, 4] beispielsweise lag ein besonderes Augenmerk auf dem Prozess der W\u00e4rmebehandlung von Konstruktionswerkstoffen.<\/p>\n\n
Es galt diesen dahingehend zu optimieren, dass der resultierende Konstruktionswerkstoff genau die Eigenschaften besa\u00df, die durch ein vorher spezifiziertes Anforderungsprofil vorgegeben waren. Diese Eigenschaften waren beispielweise die H\u00e4rte des resultierenden Werkstoffs, die Druckfestigkeit, die Zugfestigkeit und andere Werkstoffeigenschaften.<\/p>\n\n
Eine typische W\u00e4rmebehandlung besteht aus einer starken Erw\u00e4rmung (auch Austenitisierung genannt) und nach einem Abschrecken einer nachgelagerten (meist) schw\u00e4cheren Erw\u00e4rmung, die auch als Anlassen bezeichnet wird (bzw. Verg\u00fcten, wenn die Temperatur signifikant h\u00f6her ist) (Bild 2 f\u00fcr eine schematische Darstellung). Allerdings gibt es auch St\u00e4hle, die einen dritten Erw\u00e4rmungsschritt ben\u00f6tigen, um die gew\u00fcnschten Eigenschaften zu erhalten.<\/p>\n\n
![\"Wärmebehandlungsprozesse](\"https:\/\/industry-science.com\/wp-content\/uploads\/2024\/03\/Berger_IM-23-1_Bild-2-1024x703.jpg\")
Auf der Suche nach neuartigen Konstruktionswerkstoffen ist es prinzipiell auch nicht ausgeschlossen, dass irgendwann weitere dieser Erw\u00e4rmungszyklen hinzukommen. Prinzipiell handelt es sich also um einen repetitiven Prozess, der im Prinzip beliebig oft wiederholt werden kann mit potenziell ver\u00e4nderlichen Parametern. Dasselbe gedankliche Prinzip lie\u00dfe sich auf viele Prozesse \u00fcbertragen, die in einer variablen Anzahl wiederholt werden k\u00f6nnen und dabei in ihren einzelnen Parametern unterschiedliche Werte annehmen k\u00f6nnen.<\/p>\n<\/div>\n<\/div>\n\n
Soll \u00fcber diese Prozesse nun eine Optimierung stattfinden und insbesondere die Variabilit\u00e4t in der Anzahl der potenziell modifizierten Wiederholungen beibehalten werden, so tritt automatisch die Herausforderung zu Tage, dass diese Prozesse in irgendeiner Form f\u00fcr den evolution\u00e4ren Algorithmus passend kodiert werden m\u00fcssen. Eine schlichte Variante w\u00e4re die Form (im Fall der W\u00e4rmebehandlungsprozesse), die Eckpunkte auf dem Temperaturdiagramm zu kodieren, in schlichter abwechselnder Folge der x- und y-Werte.<\/p>\n\n
Dies hat jedoch den Nachteil, dass die Rekombination und Mutation des evolution\u00e4ren Algorithmus nicht nur realit\u00e4tsferne, sondern schlicht nicht darstellbare Prozesse erzeugen w\u00fcrden. Nicht mal mehr der Anspruch einer Temperatur-Zeit-Kurve w\u00e4re in dem Sinne zu halten, insbesondere weil keine Ordnung auf den x-Werten (f\u00fcr die Zeit) eingehalten werden k\u00f6nnte. Dies gilt in dieser Form auch f\u00fcr andere zu kodierende Prozesse.<\/p>\n\n
Durch die hierarchische Struktur der Prozesse \u2212 ein Satz an Parametern geh\u00f6rt zu einem Prozess, mehrere unterschiedliche Instanzen dieser Prozesse werden wiederholt \u2212 und die gleichzeitig bisher eindimensionale Struktur der Kodierung f\u00fcr evolution\u00e4re Algorithmen entsteht stets die Problematik, dass durch die Mutation und Rekombination die Grundstruktur der Prozesse zerst\u00f6rt werden k\u00f6nnte.<\/p>\n\n
Kodierung von repetitiven Prozessen<\/h2>\n\n
Wie kann nun mit diesen repetitiven Prozessen in Bezug auf die Kodierung f\u00fcr evolution\u00e4re Algorithmen umgegangen werden? Auch und insbesondere im Hinblick auf die Tatsache, dass die zugeh\u00f6rige Fitnessfunktion m\u00f6glicherweise durch maschinelles Lernen approximiert werden muss? Im vorigen Absatz hat sich bereits angedeutet, dass die eindimensionale Struktur der Kodierung problematisch ist, sowie die Anpassung der Operatoren auf die Kodierung, damit diese stets valide (nicht sinnvolle, aber valide) Prozesse herstellen.<\/p>\n\n
Die L\u00f6sung ist der Gang in die Zweidimensionalit\u00e4t und die Aufl\u00f6sung der alten Logik: Ein Chromosom f\u00fcr eine Dimension. Eine Folge repetitiver Prozesse wird nun als Tupel seiner Grundprozesse dargestellt. Das hei\u00dft, ein einzelnes Chromosom stellt nun nicht mehr eine Dimension des Suchraums dar, sondern einen Grundprozess. Was in der Folge die Frage aufwirft, wie ein solcher (einzelner) Grundprozess (siehe einen Erw\u00e4rmungsvorgang im Beispiel) dazustellen ist. Hier wurde sich f\u00fcr die Markierung der charakteristischen Punkte des Erw\u00e4rmungsprozesses entschieden \u2212 im Kontext des Projekts \u2212 d. h. es werden die Starttemperatur, Erw\u00e4rmungsdauer, Zieltemperatur, Haltedauer, Abk\u00fchldauer und Endtemperatur eines Prozesses kodiert.<\/p>\n\n
Bild 3 zeigt hier schematisch, wie diese Kodierung beispielhaft f\u00fcr die Temperaturkurve aus Bild 2 anzunehmen ist. Die Kodierung des zugrundeliegenden Prozesses jedoch ist grunds\u00e4tzlich an die jeweilige Dom\u00e4ne anzupassen. Hier k\u00f6nnten auch R\u00fcstzeiten, Produktionszeiten und Lagerzeiten stehen, bevor der Prozess an einer weiteren Station wiederholt wird (mehrere Produktionsvorg\u00e4nge an einem Produkt). Die Variabilit\u00e4t der Anzahl der Repetitionen der Prozesse kann durch die Einf\u00fchrung einer Maximalzahl geregelt werden. Diese ist so zu w\u00e4hlen, dass mehr als diese Wiederholungen entweder technisch nicht m\u00f6glich oder in anderer Form realistisch nicht sinnig w\u00e4ren. Dann wird in der Kodierung stets diese Anzahl an Chromosomen freigehalten. Durch Mutation und Rekombination k\u00f6nnen sich Prozesse dann verl\u00e4ngern und verk\u00fcrzen.<\/p>\n\n Die Rekombination und Mutation hat nun zwei Aufgaben \u2212 zum einen die Modifikation der einzelnen Prozesse, zum anderen die Verk\u00fcrzung oder Verl\u00e4ngerung der gesamten Folge von Prozessen. Die Rekombination nimmt zwei Grundprozesse als Eingabe und produziert zwei Grundprozesse nach dem oben erkl\u00e4rten Prinzip: Es werden zuf\u00e4llig Parameter der Grundprozesse ausgew\u00e4hlt, bspw. Erw\u00e4rmungsdauer und Endtemperatur. F\u00fcr diese werden dann jeweils zwei Punkte auf der sie verbindenden Linie gew\u00e4hlt.<\/p>\n\n Jeder Grundprozess enth\u00e4lt so eine neue Kombination der Parameter Erw\u00e4rmungsdauer und Endtemperatur. So ist sichergestellt, dass beide resultierenden Grundprozesse auch valide Prozesse sind und die gesamte Prozessfolge somit ebenfalls. F\u00fcr die Mutation eines Grundprozesses werden zuf\u00e4llig Parameter des Prozesses gew\u00e4hlt, die passend zum obigen Beispiel dann entsprechend einer einstellbaren Standardabweichung modifiziert werden.<\/p>\n\n Tats\u00e4chlich \u00e4ndern sich Rekombination und Mutation kaum, sie verschieben sich nur von der Ebene des Genotyps, indem Chromosome rekombiniert und mutiert wurden auf die Ebene des Chromosoms, auf der nun Parameter rekombiniert und modifiziert werden. Die Mutation kann so auch Prozesse verl\u00e4ngern: Wird ein Grundprozess (also ein Chromosom) zur Modifikation ausgew\u00e4hlt, der noch keine Parameter hat (bzw. diese alle bei 0 liegen), kann durch die Mutation einzelner Parameter wie oben beschrieben ein tats\u00e4chlicher Grundprozess erzeugt und somit die Prozessfolge verl\u00e4ngert werden.<\/p>\n\n Die Form dieser Kodierung hat zus\u00e4tzlich einen entscheidenden Vorteil f\u00fcr den Nutzen des maschinellen Lernens in Bezug auf die Fitnessfunktion. In einer eindimensionalen Darstellung w\u00e4re es notwendig, Trainingsdaten f\u00fcr beliebige L\u00e4ngen der Prozessfolgen sowie Grundprozesse zu erheben, um eine Fitnessfunktion approximieren zu k\u00f6nnen. Betrachtet man die Grundprozesse als zeitliche Dimensionen, so k\u00f6nnen sie als Operation auf dem aktuellen Zustand des Systems (im Fall der W\u00e4rmebehandlung, des Konstruktionswerkstoffs) verstanden werden. Das bedeutet, dass zur Berechnung der Fitness eines L\u00f6sungskandidaten nicht der gesamte Prozess auf einmal auf den urspr\u00fcnglichen Zustand angewendet wird, sondern die Teilprozesse St\u00fcck f\u00fcr St\u00fcck.<\/p>\n\n Im realen Verfahren wird der Gesamtprozess durchgef\u00fchrt, aber die Berechnung findet nur Schritt f\u00fcr Schritt statt. Eine Prozessfolge w\u00fcrde so St\u00fcck f\u00fcr St\u00fcck auf den aktuellen Systemzustand angewandt und nach Ermittlung des letzten Zustands, die Fitness desselbigen gesch\u00e4tzt. Diese Technik erm\u00f6glicht es, den Suchraum f\u00fcr die Trainingsdaten zu verringern. Nun m\u00fcssen nur unterschiedliche Prozesse auf unterschiedlichen Grundzust\u00e4nden des Systems als Trainingsdaten aufgefasst werden, da pro Abbildung nur ein Prozess auf einen gegebenen Zustand abgebildet wird.<\/p>\n\n Auf das motivierende Problem angewandt f\u00fchrte dies bereits bei 80 unterschiedlichen eingestellten Zust\u00e4nden zu einer guten Erfolgsquote bei der Suche nach W\u00e4rmebehandlungsprozessen, die genau die Zust\u00e4nde im Konstruktionswerkstoff einstellten, die gew\u00fcnscht waren [5].<\/p>\n\n Alles in allem hat die Erweiterung des Kodierungskonzepts auf zwei Dimensionen es erm\u00f6glicht, Prozessfolgen schl\u00fcssig darzustellen und insbesondere sicherzustellen, dass die Konzepte des evolution\u00e4ren Algorithmus w\u00e4hrend der Optimierung ihre F\u00e4higkeiten entfalten k\u00f6nnen. Zus\u00e4tzlich erm\u00f6glicht diese Form der Darstellung ein dateneffizientes maschinelles Lernen, was insbesondere bei experimentell oder in realer Umgebung erhobenen Trainingsdaten von Vorteil ist.<\/p>\n\n Die Forschung zu diesem Beitrag wurde durch das Projekt \u201eFarbige Zust\u00e4nde\u201c (SFB1232), das von der Deutschen Forschungsgemeinschaft gef\u00f6rdert wurde, inspiriert.<\/em><\/p>\n![\"Schematische](\"https:\/\/industry-science.com\/wp-content\/uploads\/2024\/03\/Berger_IM-23-1_Bild-3-1024x222.jpg\")
Bibliography <\/h2>[1] Weicker, K.: Evolution\u00e4re Algorithmen. Berlin Heidelberg 2015.\r
[2] Jin, Y.: Surrogate-assisted evolutionary computation: Recent advances and future challenges. In: Swarm and Evolutionary Computation 1 (2011) 2, S. 61-70. https:\/\/ doi.org\/10.1016\/j.swevo.2011. 05.001.\r
[3] Ellendt, N.; M\u00e4dler, L.: High-Throughput Exploration of Evolutionary Structural Materials. In: HTM Journal of Heat Treatment and Materials 73 (2018), S. 3-12. 10.3139\/105.110345.\r
[4] Drechsler, R.; Eggersgl\u00fc\u00df, S.; Ellendt, N.; Huhn, S.; M\u00e4dler, L.: Exploring superior structural materials using multi-objective optimization and formal techniques 2016. In: Sixth International Symposium on Embedded Computing and System Design (ISED), Patna, India, (2016), S. 13-17, doi: 10.1109\/ ISED.2016.7977046.\r
[5] Ellendt, N. u. a.: Experimental Methods to Enable High-Throughput Characterisation of New Structural Materials. In: JOM (2021).<\/div>Your downloads<\/h2>