Optimització Combinatòria i
Disseny de Xarxes d'Interconnexió
F. Comellas , E.Pallarès
Departament de Matemàtica Aplicada i Telemàtica;
Universitat Politècnica de Catalunya
Butlletí de la Societat Catalana de Ciències.,
Vol.XIV, Num 2 (1994), pp. 221-234.
En els darrers anys s'han considerat tècniques noves d'optimització
amb ordinador que han donat bons resultats en el tractament de problemes
combinatòris complexos. Aquests problemes consisteixen en trobar un
mínim o màxim global d'una funció de cost definida en un conjunt
d'estats (o de solucions possibles). D'entre aquestes tècniques
destaquem les xarxes neuronals, la recuita simulada (simulated annealing) i els algorismes genètics. En aquest article es mostra
la seva aplicabilitat al disseny de xarxes
d'interconnexió i en concret al problema d'obtenir una xarxa
d'interconnexió plana a partir d'una xarxa possiblement no plana. Es fa
èmfasi, en particular, en la recuita simulada, mètode basat en
l'analogia entre les configuracions possibles d'un problema
d'optimització combinatòria i els estats d'un sistema físic del
qual es busca l'estat d'energia mínima. La tècnica s'ha emprat per a
determinar una funció de cost adequada als problemes
d'aplanament. També, a la darrera secció, s'ha comparat
la seva efectivitat en relació als algorismes genètics.
Load:
