1

UNA NUOVA RAPPRESENTAZIONE SEMANTICA CON GLI ALGORI TMI GENETICI PER LA PROGETTAZIONE AUTOMATIZZATA DI FILT RI

ANALOGICI CON VINCOLI REALIZZATIVI: L’ALGORITMO CAMBRIANO

Francesco Napoli

Dottore in Ingegneria Elettronica Laureato presso l’Università degli Studi Roma Tre

ganimede55@hotmail.com Introduzione L’avvento degli elaboratori elettronici ha probabilmente rappresentato la svolta più rivoluzionaria nella storia della scienza e della tecnologia. Questa rivoluzione ancora in corso sta accrescendo enormemente la capacità dell’uomo di controllare la natura e di predirne il comportamento in forme che sarebbero state a malapena immaginabili soltanto mezzo secolo fa. Per molti, il coronamento di questa rivoluzione sarà la creazione di una nuova forma di intelligenza artificiale e addirittura di nuove forme di vita artificiale.

I concetti di selezione naturale e di adattamento introdotti dalla teoria dell’evoluzione di Charles Darwin sono stati rielaborati in epoca moderna, anche grazie ad una migliore comprensione del processo evoluzionistico su base genetica, da un numeroso gruppo di informatici durante gli anni Cinquanta e Sessanta dello scorso secolo, come strumento per l’ottimizzazione applicata a diverse problematiche.

Negli anni Novanta si sono svolti dei lavori pionieristici nella sintesi dei circuiti elettrici, estendendo l’utilizzo di tali tecniche informatiche non solo alla ottimizzazione delle configurazioni circuitali, ma anche alla sintesi della loro topologia, i cui recenti sviluppi hanno dato vita alla Elettronica Evolutiva.

La progettazione dei circuiti analogici, comparata alla progettazione dei circuiti digitali, è caratterizzata da un più alto livello di complessità progettuale e l’implementazione richiede molta più esperienza ed intuizione da parte del progettista. Infatti non esistono regole ben definite a cui attenersi nella progettazione dei circuiti analogici, come invece accade nel mondo digitale. Usualmente il filter design analogico viene realizzato da progettisti esperti. Negli ultimi anni si sono studiati diversi metodi al fine di automatizzare questo processo, tra cui anche il ricorso ad euristiche evolutive.

Il progetto di un filtro analogico è costituito da due fasi principali: 1. Creazione della topologia della rete. 2. Determinazione della tipologia e dei valori per i componenti che la formano.

Entrambi questi fattori devono concorrere al rispetto delle specifiche di progetto richieste. Anche se la grande maggioranza dei moderni circuiti integrati usa la tecnologia digitale, la

circuiteria analogica è sempre necessaria per implementare l’interfaccia dei dispositivi con il mondo esterno, che è analogico.

Quindi la complessità di questo tipo di progettazione, insieme con il relativo scarso numero di esperti, motiva la ricerca in questo campo. L’Algoritmo Cambriano Il presente lavoro si colloca nel campo della Elettronica Evolutiva applicata alla progettazione di circuiti analogici, più precisamente alla sintesi ottimizzata di filtri analogici passivi e attivi. In merito è stato sviluppato un innovativo algoritmo, chiamato “Algoritmo Cambriano”, che automatizza l’intera fase progettuale, interessando sia la sintesi della configurazione circuitale

2

sia il dimensionamento dei componenti di un circuito, al fine di ottenere un’utile ed innovativa metodologia nelle procedure di progettazione assistita al calcolatore (CAD).

L’implementazione dell’algoritmo è stata effettuata seguendo il paradigma di programmazione orientato agli oggetti. Infatti l’algoritmo modella la realtà di interesse come un insieme di oggetti software che interagiscono tra di loro. Ogni cromosoma all’interno del processo evolutivo è un singolo circuito modellato come un oggetto software contraddistinto dalla propria codifica genetica, la quale è stata implementata in modo innovativo utilizzando un approccio semantico, attraverso un originale metalinguaggio simbolico, dotato di una propria sintassi.

Grazie a tale codifica si è potuto descrivere nel dettaglio ogni aspetto della sintesi di un circuito, permettendo al processo evolutivo di selezionare, tramite una misura di idoneità (fitness), gli individui portatori delle migliori informazioni genetiche, al fine di ottenere delle popolazioni evolute di circuiti in grado di soddisfare le specifiche di progetto desiderate: guadagno desiderato, larghezza di banda, attenuazione di banda passante, attenuazione di banda oscura; tenendo anche conto di numerosi vincoli realizzativi: numero massimo di componenti (attivi e passivi) da impiegare, numero massimo di nodi per limitare le dimensioni circuitali, utilizzo dei soli valori nominali appartenenti alla serie commerciale E-24 per i resistori e i condensatori, utilizzo di modelli (forniti dalle case costruttrici) di componenti attivi reali per i transistor e gli amplificatori operazionali impiegati.

Il linguaggio di programmazione utilizzato è il linguaggio orientato agli oggetti Java della Sun Microsystems. L’euristica adottata nel presente lavoro si avvale degli Algoritmi Genetici.

Inoltre si è provveduto ad interfacciare l’algoritmo con il simulatore SPICE al fine di risolvere nel dominio della frequenza i circuiti selezionati dal processo evolutivo, rendendo così possibile il calcolo della fitness dei circuiti automaticamente sintetizzati.

Infatti l’algoritmo dà una descrizione ad alto livello del problema di sintesi, demandando la risoluzione materiale dei circuiti al simulatore, e così riuscendo a descrivere il problema qui affrontato, tramite la modellizzazione ad oggetti, in modo chiaro ed intuitivo. La Generazione Automatica dei Circuiti e dei Componenti Il punto di partenza per il processo di sviluppo dei circuiti consiste in un semplice circuito di partenza, chiamato embrione, e da una struttura fissa di test, fissa nel senso che non è modificabile dal processo evolutivo, che fornisce il segnale di input al circuito che si sta evolvendo, il riferimento a massa e permette il prelievo del segnale di output su un carico prefissato. Infatti il circuito elettrico selezionato dal processo evolutivo che soddisferà le specifiche progettuali del problema considerato sarà ottenuto come evoluzione di un tale semplice circuito iniziale, l’embrione, il quale corrisponde ad un cromosoma della popolazione iniziale generato casualmente. Inoltre grazie alla struttura fissa, siamo in grado di vedere il circuito che si sviluppa come una rete due porte, dove alla prima porta forniamo il segnale di input tramite un generatore di segnale e alla seconda porta viene prelevato il segnale di output su un carico che può per esempio rappresentare lo stadio di ingresso di un dispositivo per il quale stiamo filtrando il segnale. Sono stati utilizzati due tipi di strutture di test, una per la sintesi dei filtri passivi ed una per la sintesi dei filtri attivi. Esse differiscono in quanto la seconda struttura è specializzata per la sintesi di circuiti attivi in quanto già fornisce all’embrione una resistenza di feedback e una impedenza più alta verso massa. Inoltre il guadagno massimo che il circuito può realizzare viene fissato dal rapporto RFEEDBACK/RSOURCE, rapporto tra la resistenza di feedback e la resistenza in ingresso al circuito che si sta sintetizzando (vedi Figura 1).

3

Figura 1 – Embrione e struttura fissa di test per i filtri passivi (a sinistra) e per i filtri attiv i (a destra)

Inoltre questa schematizzazione trova in SPICE una diretta corrispondenza

implementativa poiché l’embrione e il circuito che se ne svilupperà sono considerati, grazie all’istruzione .SUBCKT, come sottocircuiti di un semplice circuito di test che è esattamente la struttura fissa di test qui appena presentata.

Esempio di netlist con struttura fissa di test per la sintesi di filtri passivi (STRUTTURA FISSA DI TEST) e sottocircuito embrionale (CIRCUIT) utilizzando l’istruzione .SUBCKT:

*SOTTOCIRCUITO: .SUBCKT CIRCUIT 1 2 3 <= R1 1 0 1.0E+3 L2 1 2 6.6E-6 R3 2 3 1.0E+4 C4 3 0 1.3E-8 .ENDS

*STRUTTURA FISSA DI TEST: X1 1 2 0 CIRCUIT: <= RIN 1 10 1K RLOAD 2 0 100K V 10 0 AC 10 -90 .AC DEC 10 10 10E+8 .OPTIONS LIMPTS=1000000 .PRINT AC VM(2) VM(10) .END

Inoltre, come precedentemente detto, l’Algoritmo Cambriano modella la realtà d’interesse ad oggetti, per cui ogni circuito e ogni componente sono oggetti istanza. Un oggetto di tipo Circuiti, istanza della classe omonima, è un cromosoma per l’Algoritmo Genetico. In accordo con la codifica adottata, ogni oggetto cromosoma ha un proprio DNA che è una matrice quadrata di stringhe alfanumeriche. Tale scelta è stata implementata nella classe Circuiti utilizzando una particolare variabile d’istanza che è un array bidimensionale di stringhe, String dna[][], variabile che viene opportunamente inizializzata al momento della costruzione dell’oggetto da parte del relativo costruttore nella classe considerata. I componenti, a seconda se sono attivi o passivi, sono oggetti istanza delle classi Componenti.class e ComponentiAttivi.class. Un oggetto di tipo Componenti, istanza della classe omonima, è un oggetto software che modellizza un componente passivo che viene istanziato nel momento in cui bisogna inserire un componente in un circuito. Un oggetto Componenti è caratterizzato dal tipo e dal valore del componente che rappresenta, i quali attributi sono generati casualmente nel momento in

4

cui si istanzia l’oggetto. Una volta che il componente è stato generato, questo è semplicemente capace di fornire il proprio valore, codificato nel metalinguaggio simbolico proprio dell’algoritmo, al processo che lo ha invocato e una volta fatto questo diventa inaccessibile e viene rimosso dalla memoria tramite garbage collection. I componenti passivi modellizabili dalla classe Componenti sono ovviamente tre: i resistori, i condensatori e gli induttori. Inoltre considerando che i valori nominali realmente disponibili per i componenti non sono ovviamente infiniti, tutti i valori assunti dai resistori e dai condensatori sono stati prelevati da un file di dati contenente i valori normalizzati della serie commerciale E-24, serie costituita da 24 valori distinti a due cifre significative e caratterizzata da una tolleranza del 5%. Invece per gli induttori, non esistendo una analoga standardizzazione, si sono generati i valori normalizzati del tutto casualmente, avendo però cura di avere sempre due cifre significative, ovvero di avere valori con lo stesso livello di incertezza della serie E-24. Per quanto riguarda la scelta dell’ordine di grandezza dei valori dei componenti, si sono considerate le analisi fatte da J. Koza [2] nell’ambito della sintesi dei circuiti tramite Programmazione Genetica, le quali analisi, dopo un attento esame di una grande quantità di progetti, hanno mostrato che gli ordini di grandezza per i valori dei componenti comunemente utilizzati nei circuiti sembrava avere un range di 5 ordini di grandezza che per le resistenze era centrato intorno a un 1kΩ , per le capacità era centrato intorno a 1nF e per le induttanze era centrato intorno a 1Hµ . Tutto questo è stato fatto nell’intento di rendere la modellizazzione circuitale il più possibile realistica e quindi il più possibile suscettibile di immediata realizzazione con componenti discreti. Un oggetto di tipo ComponentiAttivi, istanza della classe omonima, è un oggetto software che modellizza un componente attivo e viene istanziato nel momento in cui bisogna inserire un componente attivo in un circuito. Un oggetto ComponentiAttivi è caratterizzato dal tipo e dal valore del componente che rappresenta, i quali attributi sono generati nel momento in cui si istanzia l’oggetto. Una volta che il componente è stato generato, questo è semplicemente capace di fornire il proprio valore, codificato nel metalinguaggio simbolico, al processo che lo ha invocato e una volta fatto questo diventa inaccessibile e viene rimosso dalla memoria tramite garbage collection. I componenti attivi modellizabili dalla classe Componenti sono due: i transistor (sia i BJT che i MOS) e gli amplificatori operazionali. I relativi modelli (forniti dalle case costruttrici), che possono tener conto sia della tecnologia usata sia di vari comportamenti non ideali dei dispositivi utilizzati, sono inseriti automaticamente nel file di input per il simulatore SPICE. La Codifica dei Cromosomi Come per tutti i metodi di ricerca, la rappresentazione delle soluzioni candidate è il punto di partenza fondamentale per garantire il successo dell’euristica. Fin dall’inizio è sembrato evidente che una codifica binaria sarebbe stata del tutto innaturale e gratuitamente complessa per poter descrivere con precisione la problematica d’interesse. Quindi nell’intento di adottare una codifica che fosse la più immediata e naturale possibile nella descrizione di un circuito la cui topologia e dimensione si ignora del tutto a priori, si è deciso di adottare una descrizione matriciale innovativa.

L’idea di base è quindi quella di considerare i cromosomi come matrici quadrate, i cui elementi, i geni, codificano nel dettaglio la natura del collegamento tra due nodi. In questo modo la topologia della rete è codificata dalla struttura e dalla dimensione della matrice, che corrisponde al numero dei nodi della rete, mentre la natura e la dimensione dei componenti è codificata dai singoli geni.

Per poter descrivere con il maggior dettaglio possibile la natura dei componenti e il tipo di interconnessione tra i nodi, si sono codificate le informazioni genetiche sotto forma di stringhe alfanumeriche, le quali vengono generate automaticamente all’interno dell’algoritmo,

5

rispettando una particolare sintassi di un metalinguaggio simbolico appositamente inventato. Quindi i cromosomi sono codificati come matrici quadrate di stringhe alfanumeriche.

La rappresentazione adottata è innovativa in quanto è a lunghezza variabile sia a livello cromosomico che genetico: a livello cromosomico poiché le dimensioni delle matrici possono essere qualsiasi come allo stesso modo può esserlo il numero di nodi di una generica rete elettrica; a livello genetico poiché i geni possono avere una lunghezza qualsiasi, essendo in genere arbitraria la natura e il numero dei componenti che possono interconnettere due nodi qualsiasi di una rete elettrica.

In questo modo si è potuto superare un’importante limitazione presente nella codifica puramente numerica adottata in precedenti lavori, superando i limiti riscontrati nella codifica matriciale che utilizza la matrice di adiacenza per descrivere le interconnessioni di un circuito. Infatti in queste precedenti rappresentazioni risultava impossibile codificare in tali matrici numeriche anche la natura delle interconnessioni, sopratutto le informazioni per i componenti a tre terminali che costituiscono i componenti attivi di un circuito elettronico, imponendo agli sviluppatori di codificare tali informazioni in separati array di dati, limite che ora è stato superato grazie alla nuova codifica alfanumerica qui adottata, rendendo così codificabile in una singola struttura matriciale più facilmente gestibile anche le informazioni di interconnessione degli elementi, sia attivi che passivi, di un circuito.

In questo modo si è potuta ridurre notevolmente la generazione di circuiti non simulabili, potendosi ora controllare, grazie all’utilizzo di un’unica struttura matriciale, la corretta sintesi dei circuiti in modo semplice e diretto tramite operatori matriciali di controllo sviluppati “ad hoc”. In questo modo, non solo nella sintesi dei filtri passivi ma anche di quelli attivi, si sfruttano pienamente i ben noti vantaggi dell’utilizzo della codifica matriciale tramite l’uso della matrice di adiacenza per ridurre il numero di circuiti non simulabili [6]. Il Metalinguaggio Simbolico Al fine di ordinare l’informazione di tipo genetico all’interno dei cromosomi e di semplificarne la gestione automatizzata da parte degli operatori genetici è stato introdotto nel presente algoritmo un metalinguaggio simbolico, caratterizzato da una propria sintassi, rendendo quindi capace l’Algoritmo Genetico di poter “scrivere” e gestire in modo semplice le informazioni genetiche necessarie durante l’intero processo evolutivo.

Si presenta un esempio di cromosoma la cui informazione genetica è codificata nel metalinguaggio simbolico:

Figura 2 – Un esempio di cromosoma

Prima di tutto si distinguono due tipi principali di informazioni genetiche: quelle nodali e quelle di interconnessione.

Le informazioni genetiche di tipo nodale sono quelle relative ad un solo nodo della rete e spazialmente sono quelle collocate sulla diagonale principale della struttura matriciale del cromosoma. Qui se ne dà un esempio per illustrarne la sintassi: G*A004401+*Q000211D*FOUT. Come si può notare la sintassi è dotata prima di tutto di un operatore di concatenazione delle stringhe alfanumeriche, ovvero l’operatore “*”. Ciò serve per far distinguere automaticamente al software due stringhe alfanumeriche consecutive. La lettera G sta per “Ground” e significa che il nodo a cui si riferisce tale informazione genetica si trova al potenziale di massa. Questa informazione, quando presente, si deve trovare per

6

sintassi sempre in prima posizione nella stringa alfanumerica considerata. La stringa “A004401+” sta ad indicare che al nodo considerato è connesso il morsetto non invertente, “+”, di un amplificatore operazionale, contraddistinto dalla lettera iniziale “A” e dal numero di serie 4401. Analogamente avviene per la stringa “Q000211D” che sta ad indicare che al nodo considerato è connesso il terminale di drain, “D”, di un transistor ad effetto di campo (FET), contraddistinto dalla lettera iniziale “Q” e dal numero di serie 211. Si può notare che il formato relativo a tali informazioni permette di distinguere, nei vari circuiti modellizzati nel presente algoritmo, fino a 1.000.000 di differenti transistor e amplificatori operazionali per ogni esecuzione. Infine la stringa “FOUT” sta ad indicare che quel nodo è collegato ad uno dei tre nodi della struttura circuitale fissa sopra presentata – “F” sta per fisso – e precisamente che è il nodo da cui si preleva il segnale di uscita, “OUT”. Gli altri due nodi della struttura fissa vengono quindi analogamente denominati nel seguente modo: “FINN” e “FGRD”. Inoltre questa informazione genetica si trova sempre in ultima posizione nella stringa alfanumerica considerata. Questi punti “fissi” sono sempre presenti in tutti i circuiti generati, poiché permettono l’interconnessione del circuito che si sta sviluppando con il segnale di ingresso (FINN), con l’uscita (FOUT) e con il riferimento a massa (FGRD). Data quindi la loro importanza si sono sviluppati numerosi metodi di controllo per assicurare che tale tipo di informazione sia presente in modo corretto in ogni cromosoma, compito peraltro notevolmente facilitato dalla struttura matriciale. Infine se non vi è nessuna informazione per il nodo considerato, tale situazione è descritta semplicemente con uno zero, “0”.

Le informazioni genetiche di interconnessione sono invece quelle relative ad una coppia di nodi e come dice il nome descrivono la natura del collegamento tra tali nodi all’interno della rete elettrica. Qui se ne dà un esempio per illustrarne la sintassi: C5.6E-1+L8.4E#1/R8.2E#3+R3.3E#4. Come si può notare la sintassi è dotata prima di tutto di due operatori di concatenazione delle stringhe alfanumeriche, ovvero dell’operatore “+” e dell’operatore “/” che rappresentano rispettivamente l’operazione di messa in serie e di messa in parallelo dei componenti. Le lettere “C”, “R” e “L” stanno evidentemente ad indicare la natura del componente passivo considerato (con il corrispondente ovvio significato), e i numeri successivi stanno ad indicare il loro valore nominale in notazione scientifica. Si osserva che qui il simbolo “#” è stato scelto per indicare il segno positivo dell’esponente della relativa potenza di 10 (E), non potendosi utilizzare il simbolo “+” qui già utilizzato e quindi di conseguenza sovraccarico. Quindi la precedente stringa sta ad indicare che tra i due nodi considerati sono presenti due rami paralleli costituiti, uno, da una serie di un condensatore e di un induttore e, l’altro, dalla serie di due resistori. Infine, se non esiste alcun collegamento tra i due nodi considerati, tale situazione è descritta con un semplice zero, “0”.

Come si vede in Figura 2 il cromosoma è una matrice simmetrica di stringhe alfanumeriche, che sono i geni di tale cromosoma, le quali rispettano la sintassi del metalinguaggio. Le informazioni di tipo nodale si trovano sulla diagonale principale e le informazioni di interconnessione si trovano in tutte le altre posizioni. Si può pensare a tale matrice come una mappatura di una rete elettrica dove ogni indice di riga e ogni indice di colonna stanno a rappresentare i nodi della rete elettrica. Ovviamente, essendo simmetrica la matrice, ogni collegamento si può leggere in due modi differenti ed in verso opposto: nodo numero 1 – nodo numero 2, nodo numero 2 – nodo numero 1. L’informazione nella matrice risulta in effetti ridondante, ma si può osservare che la ridondanza strutturale di tale metodo di codifica è in realtà vantaggiosa perché fornisce una struttura cromosomica che ci permette di gestire delle informazioni nodali aggiuntive localizzate spazialmente sulla diagonale principale.

7

L’Algoritmo Genetico L’Algoritmo Genetico lavora con una popolazione di 50 cromosomi, ognuno dei quali rappresenta un circuito secondo la codifica sopra illustrata. Sono stati utilizzati, a seconda del problema affrontato, due metodi di selezione: il metodo della roulette, con selezione proporzionale alla fitness, e il metodo della selezione a torneo. Inoltre ogni nuova generazione è ottenuta dalla precedente con un tasso fisso di clonazione, pari al 10%, e il restante 90% degli individui è ottenuto tramite crossover a punto singolo. Inoltre grazie alla grande capacità espressiva del metalinguaggio qui introdotto è stato possibile sviluppare ben 17 tipi differenti di mutazioni, ciò nell’intento di rendere possibile ogni tipo di configurazione circuitale.

Prima di tutto si distinguono due tipi principali di mutazioni: le mutazioni geniche che agiscono solo sulle informazioni genetiche all’interno dei cromosomi e le mutazioni cromosomiche che invece agiscono su tutta la struttura cromosomica. Per ogni tipo di mutazione il tasso di mutazione è stato fissato al 5%.

Le mutazioni di tipo genico sono: • Serie: crea una mutazione di tipo serie che inserisce un componente passivo,

generato casualmente dalla classe Componenti, in serie ai componenti già presenti, codificati nel gene selezionato. Qui si fa notare la precisione di tale mutazione in quanto se tra due nodi esistono più rami in parallelo, essa è in grado di discriminare i differenti rami paralleli inserendo un nuovo componente in serie su un singolo ramo selezionato a caso.

• EliminaSerie: crea una mutazione, antisimmetrica a quella precedente, che elimina nel gene selezionato un componente in serie. Anche questa mutazione, come la sua corrispondente, è in grado di discriminare tra più rami in parallelo ed inoltre su ciascun ramo può discriminare tra più operatori di serie.

• Parallelo: crea una mutazione che inserisce un componente passivo, generato casualmente dalla classe Componenti, in parallelo ai collegamenti già presenti, codificati nel gene selezionato.

• EliminaParallelo: crea una mutazione, antisimmetrica a quella precedente, che elimina nel gene selezionato un ramo parallelo. Anche questa mutazione è in grado di discriminare tra più rami paralleli.

• Ground: crea una mutazione mettendo un nodo a massa. Ovviamente questa mutazione può agire solo sulle informazioni geniche di tipo nodale, ovvero solo sui geni presenti sulla diagonale principale della struttura matriciale del cromosoma.

• CancelGround: crea una mutazione, antisimmetrica a quella precedente, che elimina il collegamento a massa di un nodo.

• CreaCollegamento: crea un nuovo collegamento tra due nodi non direttamente collegati. Con probabilità del 50% può scegliere se collegare questi due nodi con un corto circuito o con un componente generato casualmente.

• EliminaCollegamento: crea una mutazione, antisimmetrica a quella precedente, che elimina un collegamento esistente tra due nodi.

• SpostaCollegamento: crea una mutazione che sposta il collegamento codificato nel gene selezionato in un’altra posizione del cromosoma.

• MutaValore: muta solo il valore numerico di un componente scelto a caso tra tutti i componenti codificati nel gene selezionato.

• MutaComponente: muta sia il valore numerico sia il tipo di componente per un elemento scelto a caso tra tutti i componenti codificati nel gene selezionato.

• AddComponenteAttivo: crea una mutazione che aggiunge un componente attivo fra tre nodi selezionati a caso, potendo quindi inserire sia transistor che amplificatori

8

operazionali, a seconda del tipo di configurazione circuitale e a seconda della tecnologia che si sta utilizzando.

• Move: crea una mutazione spostando un terminale di un elemento attivo da un nodo ad un altro nodo. Ovviamente questa mutazione, come quella precedente, riguarda solamente le informazioni geniche di tipo nodale, ovvero solo quelle codificate nei geni che si trovano sulla diagonale principale della struttura matriciale del cromosoma.

• Sdoppia: crea una mutazione nel collegamento tra due nodi sdoppiando il collegamento. Questa mutazione vuole introdurre nella configurazione circuitale strutture ripetitive e simmetriche come spesso si osservano sia in natura sia negli schemi elettrici.

• FlipConnections: crea una mutazione scambiando le informazioni genetiche relative a due nodi scelti casualmente nella struttura matriciale del cromosoma. Anche questa mutazione agisce solo su geni di tipo nodale.

Le mutazioni di tipo cromosomico sono invece: • AggiungiNodo: crea una mutazione che aumenta di un’unità il numero dei nodi,

aggiungendone uno in una posizione casuale, modificando in questo modo la topologia del circuito elettronico (Figura 3).

• EliminaNodo: crea una mutazione che diminuisce di un’unità il numero dei nodi, eliminandone uno scelto casualmente, modificando in questo modo la topologia del circuito elettronico.

Infine, a scopo illustrativo, si dà un esempio di mutazione genica, mostrando l’azione della mutazione “Serie” su un gene: C9.1E-1/C1.0E-2+R6.2E-2 => C9.1E-1+R3.3E#4/C1.0E-2+R6.2E-2. Come si può vedere tale mutazione, agendo su un gene che codifica, secondo il metalinguaggio simbolico, la connessione tra due nodi del circuito (costituita da due rami paralleli di cui uno costituito da un solo condensatore, C9.1E-1, e il secondo dalla serie di un condensatore e un resistore, C1.0E-2+R6.2E-2), aggiunge un resistore con resistenza R di valore 3.3*10^4 in serie al condensatore C9.1E-1 sul primo ramo parallelo.

Figura 3 – Un esempio di applicazione della mutazione AggiungiNodo

Inoltre, data la struttura matriciale dei cromosomi, l’operatore di crossover sfrutta tale struttura per realizzare l’incrocio dell’informazione genetica dei due individui genitori. L’idea di base è quella di implementare un incrocio a punto singolo che tenga conto anche del fatto che i cromosomi sono a lunghezza variabile. Dati due cromosomi genitori, il primo costituito da una matrice nxn e il secondo da una matrice mxm, si sceglie casualmente un numero g che soddisfi la seguente relazione: g ≤ min(n,m). Quindi si prende dal primo individuo la parte della matrice con gli indici di riga e colonna minori o uguali a tale numero g, mentre si prende dal secondo individuo la parte di matrice con gli indici di riga e colonna strettamente maggiori del numero g, parte complementare alla sottomatrice proveniente dal primo individuo. La dimensione della matrice rappresentativa dell’individuo ottenuto per incrocio avrà quindi la

9

dimensione m della seconda matrice, risultando perciò importante l’ordine di selezione, sempre casuale, dei due cromosomi genitori. Quanto detto è illustrato in Figura 4.

Figura 4 – Un esempio di crossover con g = 2

Applicazioni e Risultati In fase sperimentale l’Algoritmo Cambriano è stato applicato alla sintesi di filtri analogici. In una prima fase si è provveduto ad applicare l’algoritmo a dei casi preliminari più semplici, ovvero alla sintesi di filtri passivi, per poi estendere tale applicazione anche al caso più complesso della sintesi dei filtri attivi. Sono stati scelti i filtri passa basso poiché quasi ogni altro tipo di filtri può essere ottenuto da essi, per esempio tramite una trasformazione passa basso-passa alto. Inoltre, siccome non è possibile realizzare un filtro ideale, nel calcolo della fitness si sono considerate accettabili delle deviazioni dal comportamento ideale, deviazioni la cui entità è stabilita dalle specifiche di progetto considerate. In generale la fitness è calcolata con la seguente formula:

F [ ( ( ), ) ( )]i i ii

W d f f d f= ⋅∑

dove i

f è la frequenza i-esima, ( )id f è il valore assoluto della differenza tra il valore del

guadagno desiderato e il valore del guadagno calcolato dal simulatore (errore) alla frequenza

if e ( ( ), )

i iW d f f è il peso degli addendi della sommatoria calcolato in funzione di ( )id f e

di i

f .

Ovviamente in questo modo, come pure si verifica nella Genetic Programming di J. Koza, a valori alti di fitness corrisponde una bassa idoneità, mentre ad una bassa fitness corrisponde un’alta idoneità, quindi l’Algoritmo Cambriano andrà alla ricerca dei minimi di tale funzione.

La scelta dei pesi è la questione più delicata nell’uso di questa formula, scelta che può essere suggerita solo da prove sperimentali. Dopo numerose simulazioni si sono considerati i seguenti pesi relativamente ai punti calcolati in banda passante:

• W = 0 se ( )id f ≤ r

• W = 1 se r < ( )id f ≤ d

• W =10 se ( )id f > d

In banda oscura: • W = 0 se ( )id f ≤ ABS

• W = 1 se ABS < ( )id f ≤ h

• W =10 se ( )id f > h

Dove r ≤ ABP è l’ampiezza di ripple considerata accettabile in banda passante e ABP l’attenuazione di banda passante; ABS è l’attenuazione di banda oscura desiderata; d è una deviazione dal guadagno desiderato in banda passante (generalmente unitario), il cui valore viene fissato nelle singole applicazioni, dipendendo ovviamente dall’ampiezza di ripple considerata accettabile; h è una deviazione dal guadagno desiderato in banda oscura

10

(guadagno nullo), il cui valore viene fissato nelle singole applicazioni, dipendendo ovviamente dalla attenuazione di banda oscura desiderata.

Mentre in banda di transizione il peso W è sempre nullo, ovvero non si calcola la fitness in tale banda.

I vantaggi di tale funzione di fitness sono i seguenti: • Non penalizza i valori ideali o ritenuti accettabili • Penalizza leggermente le deviazioni inaccettabili di piccola entità • Penalizza pesantemente le deviazioni inaccettabili di maggiore entità

Ovviamente la definizione di ciò che è considerato accettabile o non accettabile dipenderà dalle specifiche di progetto richieste e dalla natura del particolare problema progettuale considerato.

Infine la generazione automatica dei circuiti, nonostante i numerosi controlli resi possibili dalla codifica adottata, può dar sempre vita a dei circuiti che non possono essere simulati da SPICE. Inoltre durante le simulazioni si possono avere errori di underflow e overflow. In tutti questi casi il simulatore SPICE non effettua alcuna simulazione e lancia un messaggio di errore. Tali configurazioni circuitali vengono considerate non simulabili, i messaggi di errore vengono catturati e a questi circuiti viene assegnata una fitness molto alta così da favorirne l’estinzione nel processo evolutivo. Sintesi di un Filtro Passivo Ellittico Come prima applicazione dell’Algoritmo Cambriano si è scelto di sintetizzare un filtro passivo passa basso equivalente ad un filtro ellittico del 5° ordine, filtro già presentato da J. Koza [1]. Si sono quindi imposte le seguenti specifiche: frequenza di banda passante pari a 1kHz, frequenza di banda oscura pari a 2kHz, guadagno in banda passante pari a 1, attenuazione di banda passante ABP = 0.26 dB, ripple = 30mV, guadagno in banda oscura nullo, attenuazione di banda oscura ABS = 60 dB. Inoltre al fine di realizzare un circuito competitivo con i circuiti derivanti dalla progettazione umana, considerando che un filtro passa basso ellittico della stessa complessità è realizzabile con un circuito che impiega 4 nodi e 7 componenti reattivi, si sono imposti i seguenti vincoli realizzativi: un numero massimo di nodi pari a 5, un numero massimo di componenti (solo L e C) pari a 10 (il numero minimo di componenti per connettere n nodi è n(n-1)/2, quindi per n=5 è 10). Come precedentemente detto, sono stati utilizzati i valori normalizzati della serie commerciale E-24 per le capacità dei condensatori. Inoltre per limitare le dimensioni circuitali, ovvero per limitare il numero dei nodi e il numero dei componenti, si è moltiplicata la fitness per una penalty function p(n) che è unitaria per un numero n di nodi o di componenti molto inferiore al numero massimo nmax impostato e cresce all’avvicinarsi di n a nmax, finché diventa sufficientemente grande appena n diventa maggiore di nmax: p(n) = max1 n na −+ , dove a è una costante, tipicamente pari a 8.

Figura 5 – Schema circuitale del filtro passa basso ellittico del 5° ordine e relativo andamento del modulo

della funzione di trasferimento

11

La fitness dei circuiti generati automaticamente è calcolata tramite un’analisi in frequenza effettuata automaticamente con SPICE in un range di frequenze che va da 100mHz a 100MHz, con una risoluzione di 30 punti per decade. Nelle simulazioni si è utilizzato un generatore sinusoidale in ingresso di ampiezza pari a 10V e la seguente struttura di test: RSOURCE di 1kΩ e un carico resistivo RLOAD di 100kΩ . Infine la selezione è stata implementata con il metodo della roulette; è stato impostato un numero di 50 cromosomi per generazione e il tasso di mutazione è stato fissato al 5%.

Il miglior risultato su 10 esecuzioni ha raggiunto una fitness pari a 0.0, quindi si è sintetizzato un circuito che soddisfa al 100% le specifiche progettuali richieste. Il circuito è stato raggiunto in 1433 generazioni, dopo aver valutato 71650 circuiti, con una percentuale totale di errori e di circuiti insimulabili pari a 0.3%, rammentando che tale percentuale è principalmente dovuta ad errori di overflow e underflow del simulatore. Il circuito così ottenuto impiega 4 nodi e 9 componenti reattivi, quindi utilizza solo 2 componenti in più rispetto ai circuiti realizzabili con le tradizionali tecniche matematiche di sintesi. Si deve inoltre rammentare che tale apparente inefficienza è in realtà il pregio del presente algoritmo, in quanto i valori sintetizzati non richiedono approssimazioni ai valori nominali dei componenti reali, cosa che comunemente avviene in fase realizzativa di un progetto. Infatti l’Algoritmo Cambriano lavora direttamente con i valori nominali realmente disponibili, per cui il circuito automaticamente sintetizzato è direttamente realizzabile con componenti discreti reperibili in commercio. Inoltre confrontando lo schema circuitale del filtro automaticamente sintetizzato con le topologie ottenibili con le tecniche tradizionali di progettazione, si nota che tale topologia è innovativa.

0 1 2 3 4 5 6 70

2000

4000

6000

8000

10000

12000

14000

Generazioni

Fitn

ess

Miglior Fitness Individuale

Best Individual Fitness

Figura 6 – Andamenti, a sinistra, della miglior fitness individuale e, a destra, del modulo in decibel della

funzione di trasferimento del filtro passivo passa basso ellittico del 5° ordine

Infine, dal punto di vista computazionale, il presente risultato risulta molto più efficiente dell’analogo risultato ottenuto da J. Koza con la Programmazione Genetica [1], il quale ha sintetizzato il medesimo filtro con le stesse specifiche qui considerate, ma solo dopo aver valutato milioni di circuiti, ottenendo una configurazione (25 componenti e 7 nodi) molto più complessa di quella sintetizzabile con le convenzionali tecniche di progettazione, quindi realizzando un circuito di non elevato interesse ingegneristico, ed inoltre utilizzando per i componenti valori puramente matematici. Anche per quanto riguarda la percentuale di circuiti insimulabili, l’Algoritmo Cambriano risulta molto efficiente, anche se confrontato con altri lavori che utilizzano gli Algoritmi Genetici [4], [6]. Sintesi di Filtri Attivi con Amplificatori Operazio nali Come seconda applicazione dell’algoritmo si è scelto di sintetizzare un filtro attivo equivalente ad un filtro passa basso ellittico del 5° ordine. L’elemento attivo qui impiegato è il ben noto amplificatore operazionale UA741, di cui si è utilizzato il macromodello SPICE fornito direttamente dalla Texas Instruments.

12

Si sono quindi imposte le seguenti specifiche: frequenza di banda passante pari a 1kHz, frequenza di banda oscura pari a 3.2kHz, guadagno in banda passante unitario, attenuazione di banda passante ABP = 0.9 dB, ripple = 100mV, guadagno in banda oscura nullo, attenuazione di banda oscura ABS = 60 dB.

Diversamente dal caso precedente, i componenti passivi ora utilizzati sono solo resistori e condensatori, i cui valori sono sempre presi dalla serie commerciale E-24. Inoltre si sono imposti i seguenti vincoli realizzativi: un numero massimo di nodi pari a 20, un numero massimo di componenti (solo R e C) pari a 20, un numero massimo di operazionali da impiegare pari a 3.

Infine oltre alle penalty function sopra presentate, ora si utilizza anche una penalty function per il numero di operazionali impiegati, sempre della forma p(n) = max1 n na −+ .

La fitness dei circuiti generati automaticamente è calcolata tramite un’analisi in frequenza per piccolo segnale effettuata automaticamente con SPICE in un range di frequenze che va da 100mHz a 100MHz, con una risoluzione di 10 punti per decade. Nelle simulazioni si è utilizzato un generatore sinusoidale di ampiezza di 100mV e la seguente struttura fissa di test: RSOURCE di 1kΩ , RFEEDBACK di 1kΩ in modo tale che il guadagno massimo raggiungibile sia unitario, RGROUND pari a 1kΩ e un carico resistivo RLOAD di 100kΩ . Infine la selezione è stata implementata con il metodo della roulette; è stato impostato un numero di 50 cromosomi per generazione e il tasso di mutazione è stato fissato al 5%.

Figura 7 – Schema circuitale del filtro attivo ellittico del 5° ordine e relativo andamento del modulo della

funzione di trasferimento

Il miglior risultato su 10 esecuzioni ha raggiunto una fitness pari a 0.0, quindi è un filtro che soddisfa al 100% le specifiche progettuali richieste. Il circuito è stato raggiunto in 200 generazioni, dopo aver valutato 10000 circuiti; la percentuale totale di errori e di circuiti insimulabili è molto bassa, pari solo al 6‰. Esso presenta 8 nodi e utilizza 13 componenti passivi e 2 operazionali.

0 0.5 1 1.5 2 2.5 3 3.5 4 4.5 50

50

100

150

200

250

Miglior Fitness Individuale

Generazioni

Fitn

ess

Best Individual Fitness

Figura 8 - Andamenti, a sinistra, della miglior fitness individuale e, a destra, del modulo in decibel della

funzione di trasferimento del filtro attivo passa basso ellittico del 5° ordine

13

Inoltre in Figura 9 si presenta brevemente il risultato della sintesi di un filtro passa basso attivo con alto guadagno, 60 dB, frequenza di banda passante pari a 1kHz, frequenza di banda oscura pari a 10kHz, attenuazione di banda passante ABP = 0 dB, ripple = 0 (filtro tipo Butterworth), guadagno in banda oscura nullo, attenuazione di banda oscura ABS = 10 dB. La fitness raggiunta è pari a 0.0 ed è stata raggiunta in 100 generazioni; la percentuale totale di errori e di circuiti insimulabili è pari al 2%. Diversamente dal caso precedente si è utilizzato il metodo di selezione a torneo. Il filtro sintetizzato presenta 10 nodi, utilizza 16 componenti passivi e 3 operazionali.

-5 0 5 10 15 200

100

200

300

400

500

600

700

800

900

100060 dB Transfer Function

Frequenza

Gai

n

Gain

0 0.5 1 1.5 2 2.5 3 3.5 4 4.5 5

0

0.2

0.4

0.6

0.8

1

1.2

1.4

1.6

1.8

2x 10

5

Generazioni

Fitn

ess

Miglior Fitness Individuale

Best Individual Fitness

Figura 9 – A sinistra diagramma del modulo della funzione di trasferimento e a destra andamento della

miglior fitness individuale per il filtro con 60 dB di guadagno

Sintesi di Filtri Attivi in Tecnologia FET Come terza applicazione dell’algoritmo si è scelto di sintetizzare un filtro attivo equivalente ad un filtro passa basso ellittico del 3° ordine in grado di fornire in banda passante un guadagno di 20 dB. L’elemento attivo qui impiegato è un transistor NMOS, precisamente lo ZETEX ZVN3306A, il cui modello SPICE è stato fornito direttamente dalla casa costruttrice ZETEX. Quindi si è proceduto nella scelta del punto di lavoro del dispositivo, in modo da non avere problemi di linearità con il segnale, dimensionando di conseguenza la relativa rete di polarizzazione a quattro resistori. Il punto di lavoro scelto si trova ovviamente in zona di saturazione e corrisponde a una tensione di Drain-Source pari a 6V, a una corrente di Drain pari a 300mA e a una tensione di Gate-Source pari a 4.5V. In Figura 10 è visualizzato tale punto di lavoro.

Figura 10 – Rete di polarizzazione a quattro resistori (a sinistra); caratteristica di uscita e retta di carico

dello ZETEX ZVN3306A (a destra)

Si sono quindi imposte le seguenti specifiche: frequenza di banda passante pari a 10kHz, frequenza di banda oscura pari a 100kHz, guadagno in banda passante pari a 20 dB, attenuazione di banda passante ABP = 0.2 dB, ripple = 0.2V, guadagno in banda oscura nullo, attenuazione di banda oscura ABS = 20 dB.

14

Come nel caso precedente i componenti passivi utilizzati sono solo resistori e condensatori, i cui valori sono sempre presi dalla serie commerciale E-24. Inoltre si sono imposti i seguenti vincoli realizzativi: un numero massimo di nodi pari a 20, un numero massimo di componenti (solo R e C) pari a 20, un numero massimo di transistor da impiegare pari a 8.

Infine anche in questo caso si utilizza una penalty function per il numero di transistor impiegati.

Figura 11 – Schema circuitale del filtro attivo ellittico del 3° ordine (a sinistra) e relativo andamento del

modulo della funzione di trasferimento (a destra)

La fitness dei circuiti generati automaticamente è calcolata tramite un’analisi in frequenza per piccolo segnale effettuata automaticamente con SPICE in un range di frequenze che va da 10Hz a 100MHz, con una risoluzione di 10 punti per decade. Nelle simulazioni si è utilizzato un generatore sinusoidale di ampiezza di 100mV con la seguente struttura fissa di test: RSOURCE di 1kΩ , RFEEDBACK di 10kΩ in modo tale che il guadagno massimo raggiungibile sia pari a 10, RGROUND pari a 1kΩ e un carico resistivo RLOAD di 100kΩ . Infine in questa applicazione si è utilizzato il metodo di selezione a torneo; è stato impostato un numero di 50 cromosomi per generazione e il tasso di mutazione è stato fissato al 5%.

0 1 2 3 4 5 6 70

500

1000

1500

2000

2500

3000Miglior Fitness Individuale

Generazioni

Fitn

ess

Best Individual Fitness

Figura 12 – Andamenti, a sinistra, della miglior fitness individuale e, a destra, del modulo in decibel della

funzione di trasferimento del filtro attivo passa basso ellittico del 3° ordine

Il miglior risultato su 10 esecuzioni ha raggiunto una fitness pari a 3.3. Il circuito è stato raggiunto in 1379 generazioni, dopo aver valutato 68950 circuiti; in questa esecuzione non si sono avuti né errori né circuiti insimulabili. Esso presenta 11 nodi e utilizza 18 componenti passivi e 3 transistor NMOS.

Conclusioni I risultati sperimentali hanno positivamente confermato il grande potenziale dell’Algoritmo Cambriano, mostrando chiaramente di essere in grado di automatizzare l’intera fase progettuale e, grazie alla codifica adottata, di poter abbattere notevolmente la percentuale dei circuiti insimulabili. Inoltre l’algoritmo ha dimostrato di poter produrre filtri con topologie

15

innovative, utilizzando sempre un numero limitato di componenti e raggiungendo risultati competitivi con quelli prodotti dalla progettazione umana. Infine l’algoritmo è risultato computazionalmente più efficiente di altre metodologie come la Programmazione Genetica e fortemente competitivo con analoghi precedenti lavori che impiegano gli Algoritmi Genetici.

In conclusione è possibile riassumere il problema principale affrontato dal presente algoritmo guardando il problema computazionale qui affrontato come un problema di ricerca: dato uno spazio di ricerca costituito da tutte le possibili differenti topologie, dalle più bizzarre a quelle più comuni utilizzate dal progettista umano, l’Algoritmo Cambriano ha dimostrato sperimentalmente di poter campionare molto efficientemente questo enorme spazio di ricerca e di poter trovare un circuito elettronico ottimizzato che soddisfi alle specifiche di progetto richieste.

Riferimenti bibliografici [1] Koza, Bennett, Andre, Keane and Dunlap (1997), “Automated Synthesis of Analog Electrical

Circuits by Means of Genetic Programming”, IEEE Transactions on Evolutionary Computation, Vol. 1, pp. 109-128.

[2] Koza, Bennett, Andre, Keane (1999), “Genetic Programming III”, Ed. Morgan Kaufmann. [3] James B. Grimbleby (2000), “Automatic Analogue Circuit Synthesis Using Genetic Algorithms”,

IEEE Proc.-Circuits Devices Syst., Vol 147, pp. 319-323. [4] C. Goh, Y. Li (2001), “GA Automated Design and Synthesis of Analog Circuits with Practical

Constraints”, IEEE Proc. of the 2001 Congress on Evolutionary Computation, pp. 170-177. [5] A. Mesquita (2002), “Adjacency Matrix Representation in Evoluzionary Circuit Synthesis”,

Proceedings of the VII Brazilian Symposium on Neural Networks, IEEE Computer Society. [6] F. A. Salazar, A. Mesquita (2000), “Synthesis of Analog Circuits Using Evolutionary Hardware”,

IEEE 2000. [7] Koza, Kane, Streeter (2003), “L’evoluzione delle invenzioni”, Le Scienze, N. 145, pp.

36-43. [8] James B. Grimbleby (1995), “Automatic Analogue Network Synthesis using Genetic

Algorithms”, in Proceedings of the First IEE/IEEE International Conference on Genetic Algorithms in Engineering Systems (GALESIAS), pp. 53-58.

[9] Louis and Rawlins (1991), “Designer genetic algorithms: genetic algorithms in structure design”, ICGA-91, in Proc. of the Fourth International Conference on Genetic Algorithms, Belew, R.K., Booker, L.B. and Kauffman, M., Eds., pp. 53.

[10] J. Lohn, S. Colombano (1999), “A Circuit Representation Technique for Automated Circuit Design”, IEEE 1999.

[11] Chua, Desoer e Kuh (1987), “Linear and Nonlinear Circuits”, Ed. McGraw Hill. [12] G. Biondo, E. Sacchi (1996), “Manuale di Elettronica e Telecomunicazioni”, Ed. Hoepli. [13] Richard C. Jaeger (1998), “Microelettronica”, Ed. McGraw Hill. [14] Nils J. Nilsson (2002), “Intelligenza Artificiale”, Apogeo. [15] Melanie Mitchell (1998), “Introduzione agli algoritmi genetici”, Ed. Apogeo Scientifica. [16] J. R. Koza (1992), “Genetic Programming”, Ed. MIT Press. [17] J. R. Koza (1994), “Genetic Programming II”, Ed. MIT Press. [18] Koza, Keane, Streeter, Mydlowec, Yu, Lanza (2003), “Genetic Programming IV”, Ed.

Springer. [19] Z. Michalewicz, D. Fogel (2004), “How to Solve It: Modern Heuristics”, Ed. Springer. [20] Zebulum, Pacheco, Vellasco (2002), “Evolutionary Electronics”, Ed. CRC Press. [21] Bruce Eckel (2002), “Thinking in Java”, Ed. Apogeo. [22] Charles Darwin(1982), “Sull’Origine delle Specie per Elezione Naturale”, Ed. Zanichelli. [23] Maynard Smith (2005), “La teoria dell’evoluzione”, Ed. Newton & Compton Editori.