Please use this identifier to cite or link to this item: https://repositorio.ufpb.br/jspui/handle/123456789/13109
metadata.dc.type: Dissertação
Title: Uma abordagem heurística para o single-finger keyboard layout problem
metadata.dc.creator: Herthel, Ana Beatriz Fernandes
metadata.dc.contributor.advisor1: Subramanian, Anand
metadata.dc.description.resumo: A popularização de dispositivos móveis e outros aparelhos com teclados virtuais utilizados com um dedo revela o fato de que o layout QWERTY, desenvolvido originalmente para uso com os dez dedos das mãos, não atende às necessidades dos usuários. O problema associado ao desenvolvimento de um layout de teclado para um dedo é denominado SK-QAP e foi formalmente apresentado na literatura como uma variante do Quadratic Assignment Problem (QAP), um problema clássico de otimização conhecido por sua dificuldade de resolução. Uma revisão da literatura foi conduzida para reunir trabalhos relacionados ao desenvolvimento de teclados para um dedo e para n dedos que empregassem métodos vinculados à Pesquisa Operacional. Este trabalho utiliza uma abordagem heurística para resolver o SK-QAP através de um algoritmo Iterated Local Search (ILS), chamado ILS-SKQAP. Três estruturas de vizinhança foram incorporadas à fase de busca local do algoritmo. Duas delas (contour filling e pairwise-exchange) já utilizadas na resolução do SK-QAP, enquanto que a estrutura two pairs swap foi adaptada, neste trabalho, de uma vizinhança do QAP. Além disso, dois mecanismos de perturbação foram desenvolvidos para o ILS-SKQAP: ejection chain e multiple pairwise-exchange. O ILS-SKQAP foi usado na resolução das 24 instâncias existentes do SK-QAP para os idiomas inglês, francês, italiano e espanhol, obtendo resultados altamente competitivos em termos de qualidade das soluções encontradas e tempos computacionais. Ademais, seis novas instâncias foram desenvolvidas para a língua portuguesa e resolvidas pelo algoritmo.
Abstract: The popularization of mobile devices and other equipments with virtual singlefinger keyboards unveils the fact that the QWERTY layout, originally developed for typing with all ten fingers, is not suited for the users’ needs. The problem associated with the design of a single-finger keyboard layout is denoted SK-QAP and it was formally introduced in the literature as a variation of the Quadratic Assignment Problem (QAP), a classical and challenging optimization problem. A literature review was conducted to gather related work regarding single-finger and n finger keyboard layouts’ design that employ an Operations Research-based methodology. This work proposes a heuristic approach to solve the SK-QAP by means of an Iterated Local Search (ILS) algorithm, called ILS-SKQAP. Three neighborhood structures were incorporated in the local search fase of the algorithm. Two of them (contour filling and pairwise-exchange) were previously applied to solve the SK-QAP, whereas two pairs swap was adapted, in this work, from a QAP neighborhood. Furthermore, two perturbation mechanisms were developed for the ILS-SKQAP: ejection chain and multiple pairwise-exchange. ILS-SKQAP was used to solve the 24 existing instances for English, French, Italian and Spanish languages with highly competitive results both in terms of solution quality and CPU time. Moreover, a set of six instances for the Portuguese language was developed and solved by the algorithm.
Keywords: Single-finger
Layout
Teclado
Quadratic assignment problem
Iterated local search
Keyboard
metadata.dc.subject.cnpq: CNPQ::ENGENHARIAS::ENGENHARIA DE PRODUCAO
metadata.dc.language: por
metadata.dc.publisher.country: Brasil
Publisher: Universidade Federal da Paraíba
metadata.dc.publisher.initials: UFPB
metadata.dc.publisher.department: Engenharia de Produção
metadata.dc.publisher.program: Programa de Pós-Graduação em Engenharia de Produção
metadata.dc.rights: Acesso Aberto
Attribution-NoDerivs 3.0 Brazil
metadata.dc.rights.uri: http://creativecommons.org/licenses/by-nd/3.0/br/
URI: https://repositorio.ufpb.br/jspui/handle/123456789/13109
Issue Date: 14-Mar-2018
Appears in Collections:Centro de Tecnologia (CT) - Programa de Pós-Graduação em Engenharia de Produção

Files in This Item:
File Description SizeFormat 
Arquivototal.pdfArquivo total2,41 MBAdobe PDFView/Open


This item is licensed under a Creative Commons License Creative Commons