Erst durch diese Problemstellung wurde mir bewusst, dass es genetische Algorithmen gibt und wofür man sie nutzen kann.
    Die Abdeckung von Arealen mit W-Lan ist ein altbekanntes Problem. Wo stelle ich meine Repeater auf? Wann wird das Signal zu schlecht um sinnvoll arbeiten zu können? Und wie halte ich trotz hervorragender Abdeckung die Strahlung so gering wie möglich. Diese Problematik (nicht mit W-Lan, sondern mit anderen Quellen) lösen wir gerade für einen unserer Kunden.

    Erste Schritte zur Verständnis des Problems

    Auf einer flachen Ebene können wir uns das alles sehr entspannt vorstellen. Jeder Sender hat eine gewisse Sendeleistung. Um eine optimale Abdeckung zu gewährleisten muss die größtmögliche Fläche mit so wenig wie möglich Sendequellen abgedeckt sein. Erschwerend kommt hinzu, dass diese Sender selbstverständlich weder freischwebend noch an jedem Objekt angebracht werden können. In dieser Visualisierung können Sender nur an den schwarzen Linien im Inneren angebracht werden.

    Darstellung einer zufälligen Senderverteilung durch den Algorithmus
    2 durch den Algorithmus generierte zufällige Verteilungen

    Sehr schnell sieht man an diesen beiden Beispielen, dass die linke Version für unser geschildertes Vorhaben deutlich performanter ist. Das ist mit dem bloßen Auge klar erkennbar.

    Sicherlich könnte jeder von uns diese Verteilung selbst erzeugen ohne dabei höhere Mathematik bemühen zu müssen. Spannender, und deutlich komplexer, wird es wenn wir den dreidimensionalen Raum betrachten.

    Eine dreidimensionale Ansicht mitsamt einer Lösung des Algorithmus

    Hier muss ich mich geschlagen geben. Und das hier ist ein recht „simples“ Gebäude. Sie sehen hier 3 Stockwerke (die gelben Elemente stellen den Bereich in jedem Stockwerk dar an dem Sender platziert werden dürfen) Um hier mit Sicherheit sagen zu können wo die besten Plätze für die Sender sind bedarf es meiner Meinung nun entweder höherer Mathematik oder stundenlangem „trial and error“. Mit genetischen Algorithmen ist es uns gelungen dieser Problematik habhaft zu werden.

    Wie funktioniert dieser Algorithmus?

    Kurz und knapp zusammengefasst geht unser Algorithmus wie folgt vor: er generiert zu Beginn eine riesige „Population“. Als Population bezeichnen wir in diesem Kontext eine Ansammlung möglicher Lösungen der gestellten Aufgabe. Auf Basis festgelegter Kriterien bewertet er diese Lösungen (wir sprechen hierbei im weiteren Verlauf von Individuen) mit einem Punktemodell. So entscheidet er welche Individuen am besten gelungen sind. Hierbei gibt es keine Bewertung ob etwas gut oder schlecht ist, sondern lediglich wie er im Vergleich zur restlichen Population abschneidet.

    Die besten Individuen werden nun zufällig miteinander kombiniert und durch „Mutation“ verändert. Die so entstandenen Individuen (man könnte Kinder sagen) werden nach den selben Kriterien bewertet. Schneiden Sie besser als ihre Eltern ab werden sie für die Erzeugung weiterer Generationen genutzt. Sind sie schlechter bewertet wird mit den Eltern weiter verfahren.

    Dieses Prozedere wird beliebig oft wiederholt. In diesem Zusammenhang bedeutet „beliebig oft“, dass eine bestimmte Anzahl vorgegeben werden muss. Da der Algorithmus keine „richtige Lösung“ kennt, kann er auch nicht sagen wann seine Verteilung optimal ist. Aus diesem Grund muss man ihm eine Menge an Generationen nennen nach der er aufhören soll.

    Warum handelt es sich hier nicht um „reinforcement Learning“?

    Hier ein Auszug aus Wikipedia zur Definition von „bestärkendem Lernen“ Bestärkendes Lernen oder verstärkendes Lernen (englisch reinforcement learning) steht für eine Reihe von Methoden des maschinellen Lernens, bei denen ein Agent selbständig eine Strategie erlernt, um erhaltene Belohnungen zu maximieren. Dabei wird dem Agenten nicht vorgezeigt, welche Aktion in welcher Situation die beste ist, sondern er erhält zu bestimmten Zeitpunkten eine Belohnung, die auch negativ sein kann. Anhand dieser Belohnungen approximiert er eine Nutzenfunktion, die beschreibt, welchen Wert ein bestimmter Zustand oder Aktion hat.

    Wir kennen das Ergebnis von reinforcement Learning aus den Medien. „Alpha go zero“ schlug den besten „Go“ Spieler der Welt. (falls Sie mehr hierzu wissen wollen finden sie einen sehr informatives Video hier: https://www.youtube.com/watch?v=MgowR4pq3e8 )
    Im Prinzip werden die selben Verfahren genutzt. Der Algorithmus macht einen Zug (sei es bei Go oder mit der Platzierung eines Senders) und erhält für das Ergebnis Punkte. Bekommt er viele Punkte war es ein guter Zug, bei wenigen war es keiner. Allerdings gibt es nebst kleineren Unterschieden auch einen gewaltigen. Ein durch reinforcement Learning trainiertes Neuronales Netz behält sein Wissen. Es muss bei einem neuen Spiel nicht wieder bei Null anfangen. Unser Algorithmus beginnt, da er kein neuronales Netz zugrunde liegen hat, jedes mal wieder von vorne. Das ist in diesem Fall allerdings auch sinnvoll und gewollt.

    Daher handelt es sich bei diesem Projekt nicht um „machine learning“, denn der Algorithmus lernt nicht durch seine vorherigen Arbeiten dazu. Es ist aber sehr wohl künstliche Intelligenz, da er ein Problem selbstständig löst.

    Pin It on Pinterest