UM ALGORITMO BASEADO EM LATE ACCEPTANCE HILL-CLIMBING PARA SOLUÇÃO DO PROBLEMA DE LAYOUT LINEAR DE CIRCUITOS
Guilherme Murta Miranda1; Jonatas Batista Costa das Chagas1; Marcone Jamilson Freitas Souza1
1 Universidade Federal de Ouro Preto
Baixar PDF doi:10.20906/CPS/CBA2018-1207
Resumo
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.
Palavras-chave: Layout linear de circuitos; Metaheuristicas; Otimização; Late Acceptance Hill-Climbing