Faculté des sciences et techniques de l'ingénieur STI, Section de microtechnique, Institut d'ingénierie des systèmes I2S (Laboratoire de systèmes intelligents LIS)

Evolutionary synthesis of analog networks

Mattiussi, Claudio ; Floreano, Dario (Dir.)

Thèse sciences Ecole polytechnique fédérale de Lausanne EPFL : 2005 ; no 3199.

Ajouter à la liste personnelle
    Summary
    The significant increase in the available computational power that took place in recent decades has been accompanied by a growing interest in the application of the evolutionary approach to the synthesis of many kinds of systems and, in particular, to the synthesis of systems like analog electronic circuits, neural networks, and, more generally, autonomous systems, for which no satisfying systematic and general design methodology has been found to date. Despite some interesting results in the evolutionary synthesis of these kinds of systems, the endowment of an artificial evolutionary process with the potential for an appreciable increase of complexity of the systems thus generated appears still an open issue. In this thesis the problem of the evolutionary growth of complexity is addressed taking as starting point the insights contained in the published material reporting the unfinished work done in the late 1940s and early 1950s by John von Neumann on the theory of self-reproducing automata. The evolutionary complexity-growth conditions suggested in that work are complemented here with a series of auxiliary conditions inspired by what has been discovered since then relatively to the structure of biological systems, with a particular emphasis on the workings of genetic regulatory networks seen as the most elementary, full-fledged level of organization of existing living organisms. In this perspective, the first chapter is devoted to the formulation of the problem of the evolutionary growth of complexity, going from the description of von Neumann's complexity-growth conditions to the specification of a set of auxiliary complexity-growth conditions derived from the analysis of the operation of genetic regulatory networks. This leads to the definition of a particular structure for the kind of systems that will be evolved and to the specification of the genetic representation for them. A system with the required structure — for which the name analog network is suggested — corresponds to a collection of devices whose terminals are connected by links characterized by a scalar value of interaction strength. One of the specificities of the evolutionary system defined in this thesis is the way these values of interaction strength are determined. This is done by associating with each device terminal of the evolving analog network a sequence of characters extracted from the sequences that constitute the genome representing the network, and by defining a map from pairs of sequences of characters to values of interaction strength. Whereas the first chapter gives general prescriptions for the definition of an evolutionary system endowed with the desired complexity-growth potential, the second chapter is devoted to the specification of all the details of an actual implementation of those prescriptions. In this chapter the structure of the genome and of the corresponding genetic operators are defined. A technique for the genetic encoding of the devices constituting the analog network is described, along with a way to implement the map that specifies the interaction between the devices of the evolved system, and between them and the devices constituting the external environment of the evolved system. The proposed implementation of the interaction map is based on the local alignment of sequences of characters. It is shown how the parameters defining the local alignment can be chosen, and what strategies can be adopted to prevent the proliferation of unwanted interactions. The third chapter is devoted to the application of the evolutionary system defined in the second chapter to problems aimed at assessing the suitability in an evolutionary context of the local alignment technique and to problems aimed at assessing the evolutionary potential of the complete evolutionary system when applied to the synthesis of analog networks. Finally, the fourth chapter briefly considers some further questions that are relevant to the proposed approach but could not be addressed in the context of this thesis. A series of appendixes is devoted to some complementary issues: the definition of a measure of diversity for an evolutionary population employing the genetic description introduced in this thesis; the choice of the quantizer for the values of interaction strength between the devices constituting the evolved analog network; the modifications required to use the analog electronic circuit simulator SPICE as a simulation engine for an evolutionary or an optimization process.
    Riassunto
    Riassunto Il notevole aumento della potenza di calcolo disponibile verificatosi negli ultimi decenni è coinciso con un crescente interesse per l'impiego di metodologie evolutive per la sintesi di svariati tipi di sistemi, in particolare per la sintesi di strutture quali i circuiti elettronici analogici, le reti neurali e, più in generale, i sistemi autonomi, per i quali non sono state sviluppate finora delle tecniche di progettazione sufficientemente generali e sistematiche. Sebbene l'approccio evolutivo applicato alla sintesi di sistemi di questo tipo abbia prodotto risultati indubbiamente interessanti, il problema costituito dalla definizione di un processo di evoluzione artificiale in grado di dar luogo a un significativo aumento della complessità dei sistemi così generati appare tuttora aperto. Questa tesi affronta il problema della crescita evolutiva della complessità prendendo come punto di partenza le intuizioni contenute nei resoconti delle ricerche svolte (ma rimaste incompiute) verso la fine degli anni '40 e l'inizio degli anni '50 del secolo scorso da John von Neumann nel campo della logica degli automi e della loro auto-riproduzione. Le condizioni per la realizzazione della crescita evolutiva della complessità stabilite da von Neumann vengono qui integrate da una serie di condizioni ausiliarie dettate da quanto si è scoperto nel frattempo in merito alla struttura dei sistemi biologici in generale e al funzionamento delle reti di regolazione genetica in particolare. L'attenzione speciale dedicata a queste ultime è motivata dal loro status di più semplice struttura che possa essere considerata a pieno titolo un livello di organizzazione degli organismi viventi esistenti. In quest'ottica, il primo capitolo è dedicato alla formulazione del problema della crescita evolutiva della complessità, partendo dalla descrizione delle condizioni suggerite da von Neumann per giungere alla definizione delle condizioni ausiliare ispirate dall'analisi del funzionamento delle reti di regolazione genetica. Questa analisi conduce alla definizione del tipo di struttura che dovranno possedere i sistemi oggetto del processo evolutivo e alla specificazione della relativa rappresentazione genetica. Un sistema dotato del tipo di struttura richiesto — per il quale si suggerisce il nome di rete analogica — corrisponde a una collezione di dispositivi i cui terminali sono collegati da connessioni caratterizzate da un valore scalare che definisce l'intensità dell'interazione da esse istituito. Una delle peculiarità del sistema evolutivo definito in questa tesi è la modalità di assegnazione dell'intensità di queste interazioni. Essa si basa sull'uso di sequenze di caratteri estratte dalla collezione di sequenze che costituisce il genoma della rete analogica soggetta a evoluzione e associate ai terminali dei dispositivi della rete stessa. Una funzione opportunamente definita si occupa di associare ad ogni coppia di sequenze il valore dell'intensità dell'interazione corrispondente. Se il primo capitolo si limita a dare una serie di indicazioni generali per la definizione di un sistema evolutivo dotato di potenzialità di crescita evolutiva della complessità, il secondo specifica tutti i dettagli di una implementazione di un sistema evolutivo corrispondente a quelle indicazioni. Questo capitolo definisce dunque innanzitutto la struttura del genoma e degli operatori genetici corrispondenti. Vengono poi definite la codifica genetica per i dispositivi che costituiscono la rete analogica e una possibile realizzazione della funzione che determina l'intensità dell'interazione tra dispositivi del sistema evoluto e tra questi e i dispositivi che costituiscono l'ambiente esterno del sistema evoluto. La realizzazione della funzione in questione si basa sull'allineamento locale di sequenze di caratteri. Vengono descritte le modalità di scelta dei parametri dell'allineamento locale e alcune strategie che permettono di evitare la proliferazione delle interazioni indesiderate. Il terzo capitolo è dedicato alla descrizione dei risultati dell'applicazione del sistema evolutivo definito nel secondo capitolo ad una serie di problemi aventi lo scopo di verificare l'adeguatezza della tecnica di allineamento locale delle sequenze a un ambito evolutivo e le potenzialità del sistema evolutivo completo applicato a problemi effettivi di sintesi di reti analogiche. Infine, il quarto capitolo si occupa brevemente di alcuni ulteriori temi attinenti alle tematiche trattate nella tesi. Una serie di appendici è dedicata ad argomenti complementari: la definizione di una misura di diversità per una popolazione soggetta a evoluzione che impieghi la rappresentazione genetica introdotta in questa tesi; la scelta del tipo di quantizzazione dei valori di intensità dell'interazione tra dispositivi che costituiscono la rete analogica soggetta a evoluzione; le modifiche che è necessario apportare al simulatore di circuiti elettronici analogici SPICE al fine di poterlo utilizzare come motore di simulazione nell'ambito di un processo evolutivo o di ottimizzazione.