UM ALGORITMO BASEADO EM LATE ACCEPTANCE HILL-CLIMBING PARA SOLUÇÃO DO PROBLEMA DE LAYOUT LINEAR DE CIRCUITOS

Abstract

Este trabalho tem seu foco em um problema de layout linear de circuitos, o Cutwidth Problem. Neste problema há um conjunto de componentes de um circuito que comunicam-se por meio de ligações previamente definidas. O objetivo é sequenciar esses componentes em um layout linear de forma a minimizar a
quantidade de ligações que passam entre cada par de componentes da sequência. Para resolvê-lo, propõe-se neste trabalho um algoritmo heurístico baseado na metaheurística Late Acceptance Hill-Climbing (LAHC), a qual parte de uma solução inicial aleatória e faz o uso de uma estrutura de memória para explorar o espaço de soluções. A vantagem desse algoritmo sobre outros métodos baseados em metaheurísticas é que o LAHC tem apenas dois parâmetros para serem calibrados, o tamanho da memória que guarda o valor das últimas soluções geradas e o critério de parada. O algoritmo foi testado e comparado com outros quatro algoritmos da literatura. Os resultados computacionais preliminares mostram que o método é competitivo com os melhores algoritmos da literatura, tendo como vantagem sua simplicidade.