DE69420134T2 - Hopfield neuronales netzwerk und verfahren zu dessen betrieb - Google Patents

Description

• Die vorliegende Erfindung bezieht sich auf ein verbessertes neuronales Hopfield-Netz. Insbesondere, aber nicht ausschließlich kann das verbesserte neuronale Netz benutzt werden, um die Paketvermittlung in einem Paketvermittlungsnetz zu steuern.
• Bei einem Paketvermittlungsnetz wird die zu übertragende Information digitalisiert und dann in kleine adressierbare Pakete umgewandelt und danach über ein synchrones Netz übermittelt. Es wird erwartet, daß die Breitbandvermittlungssysteme der Zukunft auf die Paketvermittlung [1] zurückgreifen werden, und obgleich allgemein anerkannt wird, daß solche Netze im Asynchronous Transfer Mode (ATM) betrieben werden, gibt es nach wie vor viele Fragen bei der Realisierung der notwendigen Hochgeschwindigkeitspaketvermittlungstechnologien [2, 3]. Insbesondere ist ein wesentliches Merkmal eines solchen Systems die Verfügbarkeit von schnellen Paketvermittlungen, um die individuellen Pakete zuverlässig und schnell an ihre Bestimmungsadressen weiterzuleiten.
• Von einigen Autoren [4] wurde vorgeschlagen, neuronale Netze für die Umsetzung von ATM-Netzsteuerungen einzusetzen. Insbesondere wurde vorgeschlagen, die Techniken neuronaler Netze auf das Vermitteln und Weiterleiten anzuwenden; einen allgemeinen Überblick über dieses Gebiet findet man bei Brown [5].
• In einer neueren Studie untersuchten Ali und Nguyen die Verwendung eines Hopfield-Netzes zum Steuern einer Hochgeschwindigkeitspaketvermittlung [6]. Die Verwendung eines neuronalen Hopfield-Netzes zum Steuern einer Vermittlung wurde zuerst durch Marrakchi und Toudet [7] vorgeschlagen. Obgleich Ali und Nguyen zeigen konnten, daß das dynamische Hopfield-Netz verwendet werden kann, um eine hohe Lösungsgenauigkeit zu erzielen, sind die langen Simulationszeiten noch ein Problem.
• Diese bedeuten wesentliche Einschränkungen in bezug auf die Größe des Vermittlungssystems, das untersucht werden kann. Obgleich der Ansatz von Ali und Nguyen einen bedeutenden Fortschritt brachten, so kam dieser doch zum größten Teil ad hoc zustande und führte zu Vorschlägen für ein Netz, das nicht nur sub-optimal in bezug auf die Verarbeitungsgeschwindigkeit war, sondern auch keine Garantie beinhaltete, daß eine Konvergenz zu einer gültigen Lösung existierte.
• Verschiedene Versuche wurden unternommen, um die Konvergenzgeschwindigkeit zu verbessern, wobei eine Technik darin bestand, die Schwellenwertfunktion der Neuronen in Abhängigkeit von den fortschreitenden Berechnungen zu verändern, um bei der Verarbeitung durch das Netz zum gewünschten Ergebnis zu gelangen. Ein solcher Ansatz wurde von Honeywell [11] gemacht. Ein alternativer Ansatz, den z. B. Foo et al. [15] machten, besteht darin, konstante Vorgaben für bestimmte Neuronen zu verwenden, um Verarbeitungsdringlichkeitsbeziehungen durchzusetzen. Obgleich beide Ansätze unter bestimmten Voraussetzungen hilfreich sein können, lösen sie nicht das zentrale Problem, nämlich zu verhindern, daß die Berechnungen extrem langwierig und schwerfällig und damit langsam werden, was bei großen Netzen mit vielen aktiven Neuronen leicht der Fall sein kann.
• Ein gemeinsames Ziel der Forscher auf dem Gebiet der neuronalen Netze ist es, ein robustes Netz zu entwickeln, das nicht so ohne weiteres in einem lokalen Minimum gefangen wird. Verschiedene Ansätze wurden gemacht, um die Robustheit von Netzen zu verbessern, einschließlich der Verwendung einer Transferfunktion, die sich mit der Zeit auf definierte Art und Weise verändert. Ueda et al. [16] beschreiben die Verwendung einer zeitabhängigen Transferfunktion, die graduell schärfer wird, je weiter die Berechnung fortschreitet. Neelakanta et al. [17] machen einen im wesentlichen ähnlichen Ansatz, der jedoch auf der Analogie zu einer graduell abnehmenden Ausheiltemperatur basiert. Cheung [18] und Ghosh [19] machen an dere Ansätze zum definierten Ändern der Operation von individuellen Neuronen, je weiter die Berechnungen fortschreiten.
• Um den Typ des neuronalen Netzes, der jetzt unter seinem Namen bekannt ist, zu optimieren, schlug zuerst Hopfield vor, eine Energiefunktion für das zu lösende Problem aufzustellen und dann diese Energiefunktion mit dem, was jetzt unter Hopfield-Energiefunktion bekannt ist, zu vergleichen, um die Gewichte und Vorgaben für das Netz zu bestimmen. Ein solches Verfahren ist z. B. in Hopfield [13] und in Chu [14] beschrieben. Die jetzige Anmelderin fand, daß eine Erweiterung dieser Technik überraschenderweise wesentlich mehr Information zur Verfügung stellt, was bei der Optimierung des Netzes von Nutzen sein kann.
• Neuronale Netze wurden unter vielen verschiedenen Umständen eingesetzt, und diese schließen Routing-Systeme und Kreuzschienenvermittlungen ein - siehe beispielsweise Fujitsu [20] und Troudet et al. [12]
• Es ist eine Aufgabe der vorliegenden Erfindung, ein verbessertes neuronales Netz auf der Basis des Hopfield-Modells zu schaffen, das insbesondere für die Verwendung bei Hochgeschwindigkeitspaketvermittlungen gedacht ist (obgleich viele weitere Anwendungen denkbar sind).
• Es ist ein weiteres Ziel, die Ergebnisse von Ali und Nguyen [6] zu verbessern und ein neuronales Netz zu schaffen, das sicher oder so gut wie sicher und schneller zu einer gültigen Lösung konvergiert.
• Es ist ein weiteres Ziel der vorliegenden Erfindung, ein verbessertes allgemeines neuronales Netz auf der Basis des Hopfield-Modells zu schaffen, das in vielen technischen Gebieten anwendbar ist.
• Gemäß einem ersten Aspekt der vorliegenden Erfindung wird ein Verfahren zum Betreiben eines Hopfield-Netzes mit Neuronen mit einer Transferfunktion mit abgestufter Reaktion geschaffen, wobei die Transferfunktion eine 5-förmige Funktion ist, wobei das Verfahren das wiederholte Aktualisieren der neuronalen Ausgänge entsprechend einer Aktualisierungsregel umfaßt, das dadurch gekennzeichnet ist, daß die Transferfunktion wenigstens einen Parameter aufweist, der die Steigung der Transferfunktion bestimmt und der sich zufällig oder pseudozufällig zwischen Iterationen ändert.
• Die Erfindung erstreckt sich auch auf eine Vorrichtung für die Durchführung des Verfahrens und dementsprechend auch auf ein Hopfield-Netz mit Neuronen mit einer Transferfunktion mit einer abgestuften Reaktion, wobei die Transferfunktion eine S-förmige Funktion ist, wobei das Netz eine Vorrichtung zum Aktualisieren der neuronalen Ausgangssignale gemäß einer Aktualisierungsregel umfaßt und gekennzeichnet ist durch eine Vorrichtung zum Variieren eines Parameters, der die Steigung der Transferfunktion vorgibt, und zwar auf zufällige oder pseudozufällige Art zwischen Iterationen.
• Das Verändern der Aktualisierungsregel von Iteration zu Iteration führt zu Rauschen in dem System und ermöglicht es dem Algorithmus, wenigstens einige der nicht-globalen Minima zu vermeiden, in denen er sonst gefangen werden könnte. Dies kann erreicht werden durch zufälliges oder pseudozufälliges Verändern der Konstante (β) einer 5-förmigen Funktion.
• Die bevorzugte Anwendung der vorliegenden Erfindung ist die in einer Telekommunikationsvermittlung, insbesondere in einer Paketvermittlung. Die praktische Realisierung der Vermittlung wird sehr stark von der Anwendung und der Einschränkung der verschiedenen verwendeten Technologien abhängen. Anwendung können VLSI, Optik, Software usw. finden.
• Das neuronale Netz kann entweder als Hardware oder als Software implementiert werden. Es kann ebenso als beides implementiert sein (Hybridware).
• In einer praktischen Ausführungsform wird eine Paketvermittlung vorzugsweise mit einem separaten Queue-Manager zusammenhängen, der vor der Vermittlung sitzt und Prioritätsinformation an das neuronale Netz weitergibt. Bei einem ankommenden Paket, das eine übergroße Verzögerung erleidet (oder bei einem ankommenden Paket, das mit einer hohen Priorität versehen ist) kann der Queue-Manager die Eingangsmatrix des neuronalen Netzes derart modifizieren, daß das gewünschte Sequenzieren berücksichtigt wird. Die Funktion des Queue-Managers kann erreicht werden unter Verwendung konventioneller, neuronaler, genetischer Algorithmen, Fuzzy-Algorithmen oder hybrider Techniken.
• Bei Implementierungen, bei denen die vorliegende Erfindung zum Lösen von Problemen außerhalb der Telekommunikationsvermittlungen verwendet wird, kann es außerdem wünschenswert sein, einen Eingangsmanager zu haben, der vor dem neuronalen Netz sitzt und die Eingangsmatrix gemäß den bekannten Einschränkungen in bezug auf das zu lösende Problem modifiziert. Insbesondere wird der Eingangsmanager das neuronale Netz mit Prioritätsinformationen versorgen, wenn das Netz irgendeine Art von Sequenzierung durchführt.
• Die Erfindung kann in der Praxis auf verschiedene Arten umgesetzt werden, und eine spezielle Ausführungsform wird jetzt als Beispiel beschrieben, um die Verwendung der vorliegenden Erfindung auf dem Gebiet der Hochgeschwindigkeitspaketvermittlung zu erläutern. Die Beschreibung der bevorzugten Ausführungsform bezieht sich auf die beigefügten Zeichnungen, bei denen:
• Fig. 1 schematisch eine Hochgeschwindigkeitspaketvermittlung zeigt,
• Fig. 2 graphisch die S-förmige Funktion für β-Werte von 0,08 und 0,16 zeigt,
• Fig. 3 die Beziehung zwischen neuronalem Netz und dem Queue- Manager darstellt.
• Die spezielle Ausführungsform bezieht sich insbesondere auf ein neuronales Netz zum Betreiben einer Hochgeschwindigkeitspaketvermittlung der Art, wie sie in Fig. 1 gezeigt ist. Diese Figur wurde an eine ähnliche Figur von Ali und Nguyen [6] angepaßt. Der Sinn einer Vermittlung ist es, sicherzustellen, daß die adressierten Pakete innerhalb des Systems schnell an ihr eigentliches Ziel geleitet werden, entlang der für sie jeweils gewünschten Pfade. Eine typische Vermittlung hat mehrere Eingänge und mehrere Ausgänge, wobei die Eingänge die Pakete empfangen, die weitergeleitet werden sollen, und die Ausgänge mit den verschiedenen verfügbaren Pfaden verbunden sind. Damit kann ein ankommendes Paket am Eingang 1 über irgendeinen der Vermittlungsausgänge weitergeleitet werden. Auf ähnliche Art und Weise können Pakete, die an irgendeinem der anderen Eingänge ankommen, zu irgendeinem Ausgang weitergeleitet werden.
• Wie sich aus Fig. 1 ergibt, ist die Vermittlung der vorliegenden Ausführungsform eine n · n-Vermittlung; mit anderen Worten, es gibt n Eingänge und n Ausgänge. Jeder der n Eingänge hat N separate Eingangsschlangen, eine für jeden der Ausgänge. Dementsprechend wird ein bei dem Eingang 1 ankommendes Paket, das an den Ausgang 1 weitergeleitet werden soll, in der ersten Schlange des Eingangs 1 aufgenommen. Andere Pakete bei diesem Eingang, die an den Ausgang 2 weitergeleitet werden sollen, werden in der zweiten Schlange des Eingangs 1 aufgenommen, usw. Es ist klar, daß es insgesamt n² Eingangsschlangen gibt.
• Die Vermittlung arbeitet synchron, und es ist ihre Aufgabe, die Pakete in den Eingangsschlangen so schnell wie möglich zu vermitteln an die gewünschten Ausgänge. Wo die Anfragen nach Übertragung schneller eingehen, als es die Kapazität der Vermittlung verkraftet, muß die Vermittlung die Pakete aus den verschiedenen Eingangsschlangen derart auswählen, daß der Durchsatz maximiert wird. Bei der vorliegenden Ausführungsform ist es ein neuronales Netz, das dieses Optimierungsproblem löst.
• Gemäß dem Verfahren von Ali und Nguyen [6] wird ein neuronales Hopfield-Netz verwendet. Die allgemeine Hopfield-Energiefunktion wird mit der berechneten Energiefunktion verglichen, die den Durchsatz maximiert, um so zu der gewünschten Differentialgleichung zu kommen, die die Lösung des Vermittlungsproblems ist. Die Differentialgleichung beinhaltet undefinierte Konstanten (Optimierungsparameter), die bei Ali und Nguyen mittels Simulation bestimmt wurden.
• Wir beginnen mit der Betrachtung des Hopfield-Grundmodells, und wir gehen dann zu der Betrachtung über, wie dieses verwendet werden kann, um mit dem speziellen Vermittlungsproblem, das wir uns stellen, fertig zu werden.
Neuronales Hopfield-Netz, Grundmodell
• Das in der vorliegenden Ausführungsform verwendete neuronale Netz ist das Hopfield-Modell [8, 9], welches aus einer großen Anzahl von Verarbeitungselementen (neuronalen Zellen) besteht, die über neuronale Gewichte miteinander verbunden sind. Zu jedem Zeitpunkt kann jedes Neuron durch zwei kontinuierliche Variablen beschrieben werden, nämlich den neuronalen Aktivitätspegel xij und den neuronalen Ausgang yij. Diese Variablen hängen über die nichtlineare Verarbeitungsfunktion f wie folgt zusammen:
• yij = f (xij) (1),
• wobei für f angenommen wird, daß es sich um eine nichtlineare monoton steigende Funktion handelt. Diese Funktion wird Aktivierungs-(oder Transfer-)funktion genannt. Die genaue Form von f ist nicht so bedeutsam, und es kann irgendeine geeignete nichtlineare monoton steigende Funktion verwendet werden. In der bevorzugten Ausführungsform ist jedoch f eine S-förmige Funktion
• f (x) = 1/1 + exp (-βx) (2),
• wobei β der Gewinnfaktor ist, der die Steilheit der S-förmigen Funktion wie in Fig. 2 dargestellt steuert.
• Die Hopfield-Gleichung, die die Dynamik eines individuellen Neurons beschreibt, ist gegeben durch
• wobei Tij,kl die Gewichtsmatrix ist, die die Verbindungsstärke zwischen den Neuronen, die mit (ij) und (kl) bezeichnet sind, beschreibt. Iij beschreibt die externe Vorgabe (manchmal auch "externer Vorgabestrom" genannt), welche jedem Neuron zur Verfügung steht.
• Hopfield hat gezeigt, daß für den Fall symmetrischer Verbindungen, d. h. Tij,kl = Tkl,ij, und monoton ansteigende Verarbeitungsfunktionen f das dynamische System (3) eine Lyapunov- (Energie)funktion besitzt, die kontinuierlich mit der Zeit abnimmt. Die Existenz einer solchen Funktion garantiert, daß das System zu einem Gleichgewichtszustand konvergiert. Diese Gleichgewichtszustände werden oft als "Punkt-Attraktoren" bezeichnet.
• Die Hopfield-Energiefunktion hat die folgende Form:
• wobei λij positive Konstanten sind und x' die Variable ist, über die die Integration durchgeführt wird. Diese Gleichung ist abgeleitet in Hopfield [8].
• Man stellt leicht fest, daß mit λij= a für alle ij die Bewegungsgleichung (3) geschrieben werden kann als
• wobei der Punkt die Differenzierung in bezug auf Zeit bedeutet. Aufgrund dieser Beziehung leiten wir die partielle Differentialgleichung
• ab.
• Die Ungleichheit folgt aus der Tatsache, daß die Verarbeitungsfunktion (2) monoton ansteigt. Wenn wir den Term mit dem Integral in (4) fallenlassen (was für Berechnungen dieser Art üblich ist), wird die Zeitableitung der Energiefunktion zu
• Wenn Konvergenz hergestellt werden soll, muß die Gleichung (4) kontinuierlich abnehmen, und es muß daher die rechte Seite der Gleichung 7 kleiner oder gleich 0 sein. Im allgemeinen wäre dies aufgrund des zweiten Terms auf der rechten Seite nicht der Fall. Aber im Grenzwert des großen Gewinns (mit anderen Worten, wenn die Gleichung (2) sich einer Schrittfunktion nähert und β groß ist), wird die Ableitung dfij/dxij zu einer Deltafunktion, und daher strebt (dfij /dxij)xij gegen Null. Dieses führt zu dem in Hopfield [8] diskutierten Ergebnis. Dementsprechend können wir unter der Voraussetzung, daß der Wert β in Gleichung (2) geeignet gewählt wird, sicher sein, daß das System konvergiert und daß im Gleichgewicht keine Ungenauigkeiten verbleiben, weil der Termin mit dem Integral in Gleichung (4) vernachlässigt wurde.
• Es gibt andere Ansätze, um eine Lyapunov-Funktion zu erzeugen, z. B. indem der Zerfall in der dynamischen Gleichung auf Null gesetzt wird. Obgleich dieser Ansatz von Aiyer et al. [10] diskutiert wurde, ist es nicht der bevorzugte Ansatz in der vorliegenden Ausführungsform und wird» daher hier nicht weiter erläutert.
Formulierung des Vermittlungsproblems für die Lösung mit neuronalem Netz
• Wie man sich erinnert, betrifft die Fig. 1 die Lösung eines Optimierungsproblems einer quadratischen Vermittlung der Größe n · n. Es wird das Verfahren von Brown, Ali und Nguyen [5, 6] verwendet, um den Status der Vermittlung zu irgendeinem Zeitpunkt als eine n · n-Binärmatrix zu definieren, die mit y bezeichnet wird. Es sei rij die Zahl der Pakete am Eingang i für den Ausgang j. Der Status jeder Eingangsschlange ist als Anfangsbedingung einem Neuron vorgegeben; so werden für ein n · n-Vermittlungsnetz insgesamt n² Neuronen benötigt. Die ursprünglichen Bedingungen der Neuronen (in anderen Worten der Zustand der Eingangsschlangen) werden dann wiedergegeben durch die Matrix
• wobei
• gilt.
• Mit anderen Worten, rij ist der Einheitswert, wenn eine spezielle Eingangsschlange arbeitet, und ist Null, wenn sie im Leerlauf ist. Bei dieser Formulierung stellen die Zeilen der Matrix y die Eingangsleitungen und die Spalten die Ausgangsleitungen dar. Jedes Indexpaar (ij) definiert einen Verbindungskanal.
• Während jedes Zeitfensters kann nur ein Paket pro Kanal zugelassen werden: mit anderen Worten während jedes Zeitfensters kann höchstens ein Paket zu jedem der Ausgänge geschickt werden und höchstens ein Paket von jedem der Eingänge gewählt werden. Die Aufgabe des neuronalen Netzes ist es, die Eingangsmatrix y zu nehmen und wiederholt zu bearbeiten, um einen Ausgang oder eine Konfigurationsmatrix zu erzeugen, die tatsächlich die Kanalverbindungen herstellt, d. h. die Pakete definiert, die gewählt werden sollen, um den maximalen Durchsatz innerhalb der Vermittlungseinschränkungen zu gewährleisten.
• Unter der Annahme, daß Beschränkungen in bezug auf die Vermittlung bestehen, ist es klar, daß die Ausgangs-(Konfigurations-)matrix höchstens ein nicht-verschwindendes Element in jeder Zeile und ein nicht-verschwindendes Element in jeder Spalte haben kann. Mehr als ein einziges Element in jeder Zeile oder ein einziges Element in jeder Spalte würde bedeuten, daß die Vermittlungseinschränkungen verletzt worden sind, indem die Vermittlung entweder versucht hat, zwei Pakete gleichzeitig von einem einzigen Eingang weiterzuleiten oder zwei Pakete gleichzeitig an einen einzigen Ausgang weiterzuleiten.
• Wenn die Eingangsmatrix mehr als ein nicht-verschwindendes Element in jeder Zeile oder mehr als ein nichtverschwindendes Element in jeder Spalte aufweist, dann gibt es mehr Anfragen nach Verbindungen, als die Vermittlung in dem Zeitfenster bedienen kann. Da nur ein Eingang mit einem Ausgang zu einem gegebenen Zeitpunkt verbunden werden kann, wird der Vermittlungsmechanismus nur eine Anfrage auswählen können und muß den Rest warten lassen.
• Als Beispiel für den Fall, daß Anfragen bestehen, daß jeder der Eingänge für zu übermittelnde Pakete an alle Ausgänge bestehen, hat die Eingangsmatrix y die Form
• Für diese Eingangsgleichung sind die Ausgangs-(Konfigurations-)matrizen, die den Paketfluß durch die Vermittlung maximieren, die folgenden:
• Jede von diesen wird "gültige" Lösung genannt, da sie beide die Vermittlungsbedingungen erfüllen und sie außerdem den Vermittlungsdurchsatz maximieren. Andere Konfigurationsgleichungen wie
• sind nicht gültig. Die erste von diesen befriedigt die Vermittlungsbedingungen, maximiert aber nicht den Durchsatz, da kein Paket von dem ersten Eingang ausgewählt wurde, obgleich es wenigstens ein wartendes Paket gibt. Die zweite Matrix verletzt die Vermittlungsbedingungen, indem sie versucht, zwei Pakete gleichzeitig von dem ersten Eingang auszuwählen und zwei Pakete gleichzeitig zu dem ersten Ausgang abzusenden.
• Manchmal natürlich wird es keine Pakete geben, die an jedem der Eingänge warten, und die Eingangsmatrix y wird nicht voll sein. In diesem Fall wird die Zahl der gültigen Lösungen geringer sein. Um ein Beispiel zu nennen, sei die Eingangsmatrix die folgende:
• Dann sind die gültigen Ausgangsmatrizen
• Man sollte beachten, daß für den Fall, daß eine Zeile oder Spalte der Eingangsmatrix nur Nullen als Einträge hat, die sich ergebende Ausgangs- oder Konfigurationsmatrix in der Nomenklatur, wie wir sie verwenden, nur gültig ist, wenn sie auch nur Nullen in den entsprechenden Zeilen und/oder Spalten aufweist. Andererseits würden Verbindungen durch die Vermittlung hergestellt, obgleich gar keine Anfrage für eine solche Verbindung vorliegt. Die folgende Matrix
• wäre keine gültige Konfigurationsmatrix, obgleich sie den Durchsatz der Vermittlung maximiert und die Vermittlungsbedingungen nicht verletzt, da sie eine Verbindung zwischen der ersten Eingangsleitung und der dritten Ausgangsleitung verbindet, was für kein ankommendes Paket gefordert wurde.
Vermeidung lokaler Minima:
• In jedem System, in dem die Bewegungsgleichungen durch eine kontinuierlich reduzierende Energiefunktion bestimmt sind, besteht das Risiko, daß das System in einem lokalen Minimum der Energiefunktion gefangen wird. Bei der vorliegenden Ausführungsform wäre dies äquivalent zu der Konvergenz zu einer Lösung, die die Vermittlungsbedingungen erfüllt, aber nur ein lokales Maximum für den Vermittlungsdurchsatz darstellt und nicht das globale Maximum. Wenn es kein offensichtliches Verfahren zum Vermeiden der Konvergenz zu einem lokalen Minimum gibt, schlagen wir vor, daß in der Praxis ein gewisses "Rauschen" in das System eingeführt wird, um so weit wie möglich Nebenkonvergenzen zu vermeiden. Dies wird erreicht, indem bei der Berechnung der Lösung durch das neuronale Netz der Wert von β in Gleichung (2) zufällig variiert wird. In der ersten Iteration wird der Wirt von β auf 0,08 gesetzt, und bei den nachfolgenden Iterationen wird der Wert von β zufällig so gewählt, daß er irgendwo im Bereich zwischen 0,08 und 0,16 liegt. β ist natürlich der Gewinnfaktor, der die Steilheit der S-förmigen Funktion wie in Fig. 1 dargestellt bestimmt. Wenn β einen Wert von mehr als 0,08 annimmt (s. Gleichung 21 (c)), kann der maximale Wert des Rauschens als äquivalent zu dem Wert von β angenommen werden.
Eingeprägte Attraktoren:
• Ein Netz für die Verwendung in Vermittlungen wird normalerweise nur wenige Verbindungen haben. Dies ist einfach einzusehen, da der erste Term auf der rechten Seiten von Gleichung (12) nur ungleich Null ist, wenn i = k und j ungleich k ist. Dieses gibt n² · (n - 1) Verbindungen. Der zweite Termin hat gleichermaßen viele nicht-verschwindende Beiträge. Die Verbindungsmatrix (12) definiert daher 2n² · (n - 1) Verbindungen. Dies muß verglichen werden mit der maximal möglichen Zahl von Verbindungen, die ein Netz mit n² Neuronen haben kann: das ist n&sup4; - n².
• Wie vorher bereits erwähnt, ist es wünschenswert, daß die Ausgangsmatrix auch eine entsprechende Zeile oder Spalte mit Nullen hat, wenn die Eingangsmatrix eine Zeile mit Nullen oder eine Spalte mit Nullen hat, da anderenfalls das neuronale Netz Verbindungen herstellt, wo keine gewünscht waren. Die Energiefunktion (11) und die Verbindungsmatrix (12) sind kein Garant dafür, daß dies der Fall ist. Dies folgt aus der Tatsache, daß die Energiefunktion (11) keine Minima annimmt, wenn eine der Zeilen oder Spalten nur verschwindende Einträge aufweist. Um dieses zu vermeiden, schlagen wir vor, daß die Zeilen und Spalten mit Nullen aus der Hopfield-Dynamik ausgekoppelt werden sollten. In der Praxis wurde gefunden, daß beides die Konvergenz der anderen Neuronen verbessert und somit deutliche Steigerungen in bezug auf die erreichbare Geschwindigkeit bedeuten.
• Die Zeilen und Spalten mit Nullen können von der Hopfield- Dynamik auf vielerlei Arten entkoppelt werden. Ein einfacher Mechanismus wäre es, die Zeilen und Spalten mit Nullen in einer der Berechnungen überhaupt nicht zu berücksichtigen. Ein alternatives und bevorzugtes Verfahren besteht darin, alle Neuronen in einer Zeile mit Nullen oder einer Spalte mit Nullen zu einem negativen Attraktor zu zwingen. Was in der Praxis geschieht, ist den Eingang für die Zeilen und Spalten mit Nullen von all den anderen Neuronen zu entkoppeln. Jedoch sind ihre konstanten Ausgänge immer noch gekoppelt. Daher bleiben die gezwungenen Neuronen für alle Zeiten an den negativen Attraktor fixiert, aber ihre Ausgänge werden immer noch beim Rest der Berechnungen berücksichtigt und werden die zeitliche Entwicklung der ungezwungenen Neuronen beeinflussen. Die externen Vorgaben für all die gezwungenen Neuronen werden auf Null gesetzt.
• Wenn der eingeprägte Attraktor x&sub3; genannt wird, um ihn von den positiven und den negativen Attraktor x&sub1; und x&sub2; der Gleichungen (16) und (18) zu unterscheiden, können wir ein Äquivalent zu Gleichung (16) verwenden, um uns eine gewisse Idee von dem zu vermitteln, was der eingeprägte Attraktor sein sollte, um sicherzustellen, daß das jeweilige Neuron immer gegen Null konvergiert. Da A = B und A sehr viel größer als C ist, ergibt sich aus der Gleichung (16) die Näherungsgleichung
• x&sub3; = -2A (22).
Queue-Manager:
• In einer praktischen Ausführungsform der vorliegenden Erfindung mag es notwendig sein, um mit den ankommenden Paketen arbeiten zu können, die überlange Verzögerungen erleiden, bei bestimmten Aufbauten eine spezielle hohe Priorität zu haben oder andere spezielle Sequenzierungsanforderungen zu stellen. In der bevorzugten Ausführungsform gibt es daher einen Queue- Manager, der sich vor dem neuronalen Netz befindet und Prioritätsvermerke oder Vorgaben für den ankommenden Verkehr vergibt. Dieses ist schematisch in Fig. 3 dargestellt.
• Wenn ein ankommendes Paket eine überlange Verzögerung erleidet (oder wenn ein kritisches Paket als mit hoher Priorität behaftet bezeichnet ist), so modifiziert der Queue-Manager die Eingangsmatrix (9), um der gewünschten Sequenzierung Rechnung zu tragen. Wenn der Queue-Manager ein Paket von der Eingangsleitung empfängt, wird er die Zieladresse prüfen, um die geeignete Zielausgangsleitung zu bestimmen. Er wird außerdem die Priorität und/oder Verzögerung des speziellen Pakets bestimmen. Aufgrund der Information, die er gelesen hat, wird er dann die Eingangsmatrix (9) entsprechend aktualisieren, so daß die Ursprungsbedingungen, die das neuronale Netz bearbeitet, sich ändern. Er kann außerdem Attraktoren einführen, entweder positiv oder negativ, oder auf andere Arten gewisse Neuronen von dem Netzwerk abkoppeln, gemäß den gewünschten Prioritäten der individuellen Pakete.
• Die Funktion des Queue-Managers kann unter Verwendung konventioneller, neuronaler, genetischer Algorithmen, Fuzzy-Algorithmen oder Hybridtechniken erzielt werden.
• Eine spezielle Funktion, die durch den Queue-Manager gegeben sein könnte, ist es die Eingangsmatrix (9) anzupassen, um der Tatsache Rechnung zu tragen, daß mehr als ein Paket existiert, das auf eine spezielle Verbindung wartet. Wenn eine große Anzahl von Paketen sich langsam aufbaut, die alle auf eine spezielle Verbindung warten, sollte der Queue-Manager über einen Mechanismus verfügen, um effektiv die Priorität dieser Pakete anzuheben, um sicherzustellen, daß die Schlange nicht unnötig lang wird. Ein alternatives Verfahren zum Erreichen desselben Ergebnisses kann darin bestehen, eine Eingangsanfragenmatrix zu verwenden, in welcher jedes Element nicht nur 0 oder 1 ist, sondern eine ganze Zahl ist, die die Anzahl der Pakete darstellt, die auf eine spezielle Verbindung warten. Je größer die Zahl ist, die auf eine spezielle Verbindung warten, desto größer wäre der ursprüngliche Wert von y gemäß den Gleichungen (1) und (2), und entsprechend wä re eine größere Wahrscheinlichkeit gegeben, daß das spezielle Neuron gegen den Wert 1 konvergiert.
Rechenverfahren:
• Schließlich wenden wir uns dem Rechenverfahren zu, das beim Betrieb des neuronalen Netzes verwendet wird. Das Verfahren ist effektiv das gleiche, unabhängig davon ob das Netz als Hardware oder als Software implementiert ist.
Das Verfahren ist wie folgt:
• 1. Empfange die Eingangsanfragenmatrix, welche Nullen und Einsen in dem einfachsten Fall enthält, wodurch angezeigt wird, welche Verbindungen erforderlich sind und welche nicht.
• 2. Zum Zentrieren der Anfragenmatrix auf Null konvertiere die Nullen in jeweils -2A (negativer Attraktor).
• 3. [Optional] Verwende den Queue-Manager, um irgendwelche geeigneten Verbesserungen an der sich ergebenden Matrix vorzunehmen, z. B. bei bestimmten Anfragen eine höhere Priorität zuzulassen. Eine höhere Priorität wird erreicht durch Ersetzen einer speziellen 1 als Eintrag durch eine höhere Zahl. Zur selben Zeit wird der Queue-Manager irgendeinen eingeprägten negativen Attraktor, der erforderlich sein kann, durch Ändern der entsprechenden Einträge in große negative Zahlen (z. B. -2A), aufstellen, und zu derselben Zeit wird er für derartige Neuronen, die von den anderen entkoppelt werden sollen, (wie oben erläutert) sorgen, bevor die Berechnungen beginnen.
• 4. Die modifizierte Eingangsmatrix wird dann durch eine neuronale Matrix unter Verwendung der Gleichung (2) ersetzt.
• Die Elemente dieser neuronalen Matrix sind yij. Der Parameter β wird zufällig innerhalb des Bereiches 0,08 und 0,16 ge wählt. Bei der ersten Iteration von Schritt 4 wird er auf β = 0,08 gesetzt.
• 5. Iteriere die Differentialgleichung (13a) (die die Parameter A, B und C enthält), um neue Werte für xij zu berechnen. Die Schrittweite Δt kann z. B. 0,2 betragen.
• 6. Gehe zu Schritt 4, es sei denn, das System ist konvergiert, d. h. die yij haben sich gegenüber der letzten Iteration nicht um einen gegebenen Wert verändert. Wenn alle Neuronen konvergiert sind, beende das Verfahren.
Praktische Realisierung:
• Das Netz der vorliegenden Erfindung kann entweder als Hardware oder als Software implementiert werden, oder in einer Kombination aus beiden. Potentielle Hardwaretechnologien beinhalten VLSI, Optik usw. Die Umgebung, in welcher das Netz eingebettet werden soll, spielt natürlich eine Schlüsselrolle bei der Bestimmung des Mediums. Wenn z. B. die Geschwindigkeit von Bedeutung ist, wird eine Hardwareimplementierung vorzuziehen sein, aber dies muß natürlich gegenüber der Tatsache abgewogen werden, daß Hardwareimplementierungen bei großen Vermittlungen außerordentlich kompliziert sind. Eine Spezifizierung für eine Hardwarerealisierung (elektrische Realisierung) eines neuronalen Hopfield-Netzes wurde bereits von Brown [5] veröffentlicht. Die verschiedenen Parameter in dem Hopfield-Modell können auf Werte der verschiedenen elektrischen Komponenten in der Schaltung bezogen werden.
• Man erwartet, daß die vorliegende Erfindung auf sehr vielen unterschiedlichen Gebieten Anwendung findet, und insbesondere bei jedem Problem, bei dem eine Hopfield-Energie berechnet werden kann, und es ist eine Anforderung für eine Eingangsmatrix, daß sie höchstens ein nicht-verschwindendes Element pro Zeile und höchstens ein nicht-verschwindendes Element pro Spalte hat, mit anderen Worten, das Problem ist äquivalent zu dem Problem des Handlungsreisenden. Potentielle Anwendungsgebiete beinhalten Netzwerk- und Service-Management (einschließlich Vermitteln von Leitungen, Kanälen, Karten, Schaltkreisen, Netzen etc.); Überlastungskontrolle, verteilte Computersysteme (einschließlich Lastenausgleich bei Mikroprozessorsystemen, Karten, Schaltkreisen etc.) und dezentralisierte Computersysteme, Arbeitsmanagementsysteme, Finanztransaktionssysteme (bei Banken, Börsen, Geschäften etc.); Verkehrsplanung (Luftlinien, Zügen, Untergrundbahnen, Verschiffung etc.); alternierende Produktionslinien, Reservierung, Speicherung und Frachtsysteme (einschließlich Luftlinien, Lager etc.); allgemeine Planung und Ressourcenverwaltungsprobleme, allgemeine Kanalzuordnungsprobleme, Fluidsteuersysteme (einschließlich Öl, Gas, Chemie etc.); allgemeine Steuersysteme (einschließlich nuklearer Systeme, Fahrzeugsysteme, Luftliniensystemen, Transportsystemen etc.); Systemmanagementsysteme (einschließlich Satelliten, Mobilfunk, Audio etc.); Robotersysteme mit Aufgabenzuweisung; Aufgabenzuweisung im allgemeinen; Echtzeitdatenerfassung und Analysesysteme; Warteschlangenverzögerungsprozeduren.
Der kontinuierliche Fall
• Das vorliegende Ergebnis kann ausgedehnt werden auf den kontinuierlichen Fall, wo die Eingänge für das Netz jeden Wert innerhalb eines gegebenen Bereiches annehmen können, anstatt nur auf 0 und 1 beschränkt zu sein. Eine spezielle Art dies zu tun, wäre es, wie oben beschrieben, als Eingänge jede positive ganze Zahl zu akzeptieren, z. B. eine ganze Zahl, die der Zahl der Pakete entspricht, die in der jeweiligen Warteschlange auf die Vermittlung warten. Alternativ können die Eingänge wirklich kontinuierlich sein (nicht nur abgestuft).
• Die Eingänge können multipliziert werden mit einem Spreizfaktor f, bevor die Netzberechnungen begonnen werden, um den Bereich zu verändern, der durch die Eingangswerte aufgespannt wird. Da die Netzberechnungen nichtlinear sind, kann die Ver änderung des Eingangsbereiches erhebliche Effekte auf die Bearbeitung und die Geschwindigkeit bei der Konvergenz des Netzes haben.
• Bei dem wirklich kontinuierlichen Fall muß die Addition von Rauschen vermieden werden. Eingeprägte Attraktoren können verwendet werden, aber in der Praxis wurde gefunden, daß sie nicht sehr viel Geschwindigkeit zu der Konvergenzgeschwindigkeit des Netzes in vielen Fällen beitragen können.
• Der kontinuierliche Fall kann herangezogen werden für die Durchführung einer Aufgabenzuordnung, in erster Ordnung in einem mehrstufigen Dienstsystem oder einer heterogenen Umgebung, durch Maximieren der Summe der Indikatoren der Geeignetheit von Aufgaben für die gewählten Ressourcen. Das Netz kann ebenso für Aufgabenzuordnungen höherer Ordnung genutzt werden, wenn man berücksichtigt, daß unter anderem Kosten in bezug auf die Kommunikation zwischen den Aufgaben bestehen. Die Anwendungsgebiete umfassen unter anderem Netz- und Dienstleistungsmanagement, verteilte Computersysteme, Systeme für die Arbeitsverwaltung, Finanztransaktionen, Verkehrsplanung, Reservierung, Lagerung, Frachtabwicklung, Datenbanksteuerung, automatisierte Produktion und allgemeines Planen, Steuern oder Probleme bei Zuordnung von Ressourcen.
Referenzen
• [1] A. Pattavini, 'Broadband Switching Systems: First Generation', European Transactions an Telecommunications, Bd. 2, Nr. 1, S. 75, 1991.
• [2] M. Listanti und A. Roveri, 'Integrated Services Digital networks: Broadband Networks', European Transactions an Telecommunications, Bd. 2, Nr. 1, S. 59, 1991.
• [3] CCITT, Draft Recommendation I.150: B-ISDN ATM Aspects, Genf, Januar 1990.
• [4] A. Hiramatsu, 'ATM Communications Network Control by Neural Networks', IEEE Transactions an Neural networks, Bd. 1, Nr. 1, S. 122, März 1990.
• [5] T. X. Brown, 'Neural Networks for Switching from E. C. Posner, Ed.', 'Special Issue an Neural Networks in Communications', IEEE Communications Magazine, S. 72, November 1989; siehe auch A. Maren, C. Hartson und R. Rap, 'Handbook of Neural Computing Applications', Academic Press, London, 1990.
• [6] M. M. Ali und H. T. Nguyen, 'A Neural Network Controller for a High-Speed Packet Switch', Proc. Int. Telecommunications Symposium 1990, S. 493-497.
• [7] A. Marrakchi und T. Troudet, 'A Neural Network Arbitrator for Large Crossbar Packet Switches', in IEEE Transactions an Circuits and Systems, Bd. 36, Nr. 7, S. 1039, 9989.
• [8] J. J. Hopfield, Neurons with graded response have collective computational properties like those of two-state neurons. Proc. Natl. Sci. USA, Bd, 81, S. 3088-3092, Biophysics, Mai 1984.
• [9] A good discussions of Hopfield networks and further references is given in J. Hertz, A. Krogh und R. G. Palmer, 'Introduction to the Theory of Neural Computation', Addison-Wesley, Redwood City, 1991.
• [10] S. V. Aiyer, M. Niranjan und F. Fallside, A Theoretical Investigation into the performance of the Hopfield Model. IEE Transactions on Neural Networks, Bd. 1, Nr. 2, Juni 1990.
• [11] Honeywell Inc. EP-A-0 340 742.
• [12] Troudet et al., IEEE Transactions on Circuits and Systems, Bd. 38, Nr. 1, Januar 1991, New York, US, S. 42- 56.
• [13] J. J. Hopfield, US-A-4 660 166.
• [14] P. P. Chu, IJCNN-91: International Joint Conference on Neural Networks, Bd. 1, 8. Juli 1991, Seattle, USA, S. 141-146.
• [15] Y. S. Foo, IEEE International Conference on Neural Networks, Bd. 2, 24. Juli 1988, Sand Diego, USA, S. 275- 282.
• [16] Ueda et al., IJCNN International Joint Conference on Neural networks, Bd. 4, 7. Juni 1992, Baltimore, USA, S. 624-629.
• [17] Neelakanta et al., Biological Cybernetics, Bd. 65, Nr. 5, September 1991, Heidelberg, Deutschland, S. 331-338.
• [18] Cheung et al., IECON89, 15th Annual Conference of IEEE Industrial Electronics Society, Bd. 1, 6. November 1989, Philadelphia, USA, S. 759-763.
• [19] Ghosh et al., 1993, IEEE International Conference an Neural Networks, Bd. 1, 28. März 1993, San Francisco, USA, S. 359-364.
• [20] Fuijtsui Limited, EP-A-475 233.

Claims (10)

1. Verfahren zum Betreiben eines Hopfield-Netzes mit Neuronen mit einer Transferfunktion mit abgestufter Reaktion, wobei die Transferfunktion eine S-förmige Funktion ist, wobei das Verfahren das wiederholte Aktualisieren der neuronalen Ausgänge entsprechend einer Aktualisierungsregel umfaßt, dadurch gekennzeichnet, daß die Transferfunktion wenigstens einen Parameter aufweist, der die Steigung der Transferfunktion bestimmt und der sich zufällig oder pseudozufällig zwischen Iterationen ändert.

2. Verfahren nach Anspruch 1, bei dem der Parameter eine nicht-monotone Funktion der Iterationsziffer ist.

3. Verfahren nach Anspruch 1 oder 2, bei dem die Transferfunktion definiert ist durch y = f(x), wobei x der neuronale Eingang ist, y der neuronale Ausgang ist und

f(x) = 1/(1 + exp (-βx)),

wobei β der Parameter ist.

4. Verfahren zum Betreiben eines Telekommunikationsschalters unter Verwendung eines Verfahrens zum Betreiben eines Hopfield-Netzes nach einem der vorangehenden Ansprüche.

5. Verfahren zum Betreiben eines Telekommunikationsschalters nach Anspruch 4, bei dem der Schalter ein Paketschalter ist.

6. Ein Hopfield-Netz mit Neuronen mit einer Transferfunktion mit einer abgestuften Reaktion, wobei die Transferfunktion eine 5-förmige Funktion ist, wobei das Netz eine Vorrichtung zum Aktualisieren der neuronalen Ausgangssignale gemäß einer Aktualisierungsregel umfaßt, gekennzeichnet durch eine Vorrichtung zum Variieren eines Parameters, der die Steigung der Transferfunktion vorgibt, auf zufällige oder pseudozufällige Art zwischen Iterationen.

7. Telekommunikationsschalter mit einem Hopfield-Netz nach Anspruch 6.

8. Telekommunikationsschalter nach Anspruch 7 mit einem Queue-Manager, der zum Verbessern der ursprünglichen Bedingungen vor dem Betreiben des neuronalen Netzes in Abhängigkeit von den Prioritäten von Anrufen, die darauf warten, durchgeschaltet zu werden, angepaßt wird.

9. Telekommunikationsschalter nach Anspruch 7 oder 8, bei dem der Schalter ein Paketschalter ist.

10. Telekommunikationsnetz mit einem Schalter nach einem der Ansprüche 7 bis 9.