[pt] Desde sua introdução, a comunicação móvel sem fio cresceu e se modificou severamente. Seu crescimento acentuado significa que a alocação de diferentes parâmetros para rádios ou estações-base ganhou diversos graus de complexidade. Um parâmetro é o Root Sequence Index (RSI), relacionado com os preâmbulos do Random Access Channel (PRACH), usado para alocar canais de upload entre o equipamento do usuário e a estação rádio-base. A alocação de RSIs próximos a radios ou antenas vizinhas pode causar colisões, que são responsáveis por falhas no estabelecimento do serviço de comunicação e, portanto, degradação no desempenho da rede. Em geral, tais problemas de alocação são modelados como um Problema de Coloração de Grafos, incluindo diversas restrições. Contudo, não há estudos que foquem na alocação de RSI e colisões. O objetivo deste estudo é explorar e comparar modelos exatos e heurísticos para esse problema. Para isso, diversos modelos matemáticos foram elaborados, além de um algoritmo genético de chaves aleatórias viciadas. Os resultados apontam que a utilização de uma estratégia baseada nas relações de vizinhança é eficaz para a obtenção de boas soluções. / [en] Since its introduction, mobile wireless communication has grown and changed substantially. This massive growth leads to different levels of complexity, mainly concerned with the assignment of different parameters to radio or base stations. One parameter is the Root Sequence Index (RSI), related to the Physical Random Access Channel (PRACH) preambles, used to allocate uplink channels between the user equipment and the base station. The assignment of RSIs close-in-range to neighbor antennas may cause collisions, which are responsible for failures on service establishment, and therefore, performance degradation. Such allocation problems can be modeled as Graph Coloring Problems, including several additional constraints. However, few studies focus on RSI allocation and collisions from the optimization perspective. The objective of this study is to develop methods for allocating the RSI, trying to lessen the risk of collision, and obeying other constraints. In this study, both exact and heuristics methods are explored and compared. For this, several mathematical models were made, alongside a biased random key genetic algorithm. The results show that the utilization of an allocation strategy based on neighbor relations is efficient for finding good solutions.

[pt] O Algoritmo Genético de Chaves Aleatórias Enviesadas (BRKGA) é uma metaheurística populacional utilizada na obtenção de soluções ótimas ou quase ótimas para problemas de otimização combinatória. A parametrização do algoritmo é crucial para garantir seu bom desempenho. Os valores dos parâmetros têm uma grande influência em determinar se uma boa solução será encontrada pelo algoritmo e se o processo de busca será eficiente. Uma maneira de resolver esse problema de configuração de parâmetros é por meio da abordagem de parametrização online (ou controle de parâmetros). A parametrização online permite que o algoritmo adapte os valores dos parâmetros de acordo com os diferentes estágios do processo de busca e acumule informações sobre o espaço de soluções nesse processo para usar as informações obtidas em estágios posteriores. Ele também libera o usuário da tarefa de definir as configurações dos parâmetros, resolvendo implicitamente o problema de configuração. Neste trabalho, avaliamos duas estratégias para implementar o controle de parâmetros no BRKGA. Nossa primeira abordagem foi adotar valores de parâmetros aleatórios para cada geração do BRKGA. A segunda abordagem foi incorporar os princípios adotados pelo irace, um método de parametrização do estado da arte, ao BRKGA. Ambas as estratégias foram avaliadas em três problemas clássicos de otimização (Problema de Permutação Flowshop, Problema de Cobertura de Conjuntos e Problema do Caixeiro Viajante) e levaram a resultados competitivos quando comparados ao algoritmo tunado. / [en] The Biased Random-Key Genetic Algorithm (BRKGA) is a populationbased metaheuristic applied to obtain optimal or near-optimal solutions to combinatorial problems. To ensure the good performance of this algorithm (and other metaheuristics in general), defining parameter settings is a crucial step. Parameter values have a great influence on determining whether a good solution will be found by the algorithm and whether the search process will be efficient. One way of tackling the parameter setting problem is through the parameter control (or online tuning) approach. Parameter control allows the algorithm to adapt parameter values according to different stages of the search process and to accumulate information on the fitness landscape during the search to use this information in later stages. It also releases the user from the task of defining parameter settings, implicitly solving the tuning problem. In this work, we evaluate two strategies to implement parameter control in BRKGA. Our first approach was adopting random parameter values for each of BRKGA s generations. The second approach was to introduce the principles adopted by Iterated Race, a state-of-the-art tuning method, to BRKGA. Both strategies were evaluated in three classical optimization problems (Flowshop Permutation Problem, Set Covering Problem, and the Traveling Salesman Problem) and led to competitive results when compared to the tuned algorithm.

Orientador: John Fredy Franco Baquero / Resumo: Nesta dissertação é proposta a aplicação do algoritmo genético de chaves aleatórias viciadas para a solução do problema de reconfiguração de sistemas de distribuição. Esse problema de otimização consiste em encontrar a configuração radial que apresenta perdas mínimas, satisfazendo as restrições topológicas e as restrições operacionais, sendo modelado como um problema de Programação Não Linear Inteira Mista. O método proposto utiliza o algoritmo de Prim na geração de configurações radiais e emprega um algoritmo de fluxo de carga de varredura para avaliar cada proposta de solução. O algoritmo genético de chaves aleatórias viciadas foi desenvolvido na linguagem de programação FORTRAN e foi testado em quatro sistemas de distribuição da literatura especializada (14 barras, 33 barras, 84 barras e 136 barras). Os resultados obtidos da aplicação do algoritmo permitem avaliar o seu desempenho e eficiência em comparação com a melhor solução encontrada na literatura especializada. / Abstract: The application of the biased random-key genetic algorithm for the reconfiguration of distribution systems is proposed in this Dissertation. The problem of reconfiguration in distribution systems consists of finding the radial configuration that presents the minimum losses, satisfying topological and operating constraints and is commonly modeled as a mixed-integer nonlinear programming problem. The proposed method uses the Prim's algorithm to generate radial configurations that are evaluated through a backward/forward sweep power flow method. The biased random-key genetic algorithm used was developed in the programming language FORTRAN and was tested in four systems (14-bus, 33-bus, 84-bus and 136-bus). The obtained results show the performance and efficiency of the proposed method in comparison to the best solution found in the specialized literature. / Mestre

Submitted by Rommel Gregorio Vargas Peralta (rgvp88@gmail.com) on 2018-07-11T22:12:08Z No. of bitstreams: 1 Dissertação Mestrado - Rommel Gregorio Vargas Peralta.pdf: 3543837 bytes, checksum: 233f1b03c9cd16d58a1c981ab331ee0f (MD5) / Approved for entry into archive by Cristina Alexandra de Godoy null (cristina@adm.feis.unesp.br) on 2018-07-12T20:17:35Z (GMT) No. of bitstreams: 1 vargasperalta_rg_me_ilha.pdf: 3732403 bytes, checksum: eb45069beb69cdfd8b2cc75bf47668bf (MD5) / Made available in DSpace on 2018-07-12T20:17:35Z (GMT). No. of bitstreams: 1 vargasperalta_rg_me_ilha.pdf: 3732403 bytes, checksum: eb45069beb69cdfd8b2cc75bf47668bf (MD5) Previous issue date: 2018-04-20 / Coordenação de Aperfeiçoamento de Pessoal de Nível Superior (CAPES) / Nesta dissertação é proposta a aplicação do algoritmo genético de chaves aleatórias viciadas para a solução do problema de reconfiguração de sistemas de distribuição. Esse problema de otimização consiste em encontrar a configuração radial que apresenta perdas mínimas, satisfazendo as restrições topológicas e as restrições operacionais, sendo modelado como um problema de Programação Não Linear Inteira Mista. O método proposto utiliza o algoritmo de Prim na geração de configurações radiais e emprega um algoritmo de fluxo de carga de varredura para avaliar cada proposta de solução. O algoritmo genético de chaves aleatórias viciadas foi desenvolvido na linguagem de programação FORTRAN e foi testado em quatro sistemas de distribuição da literatura especializada (14 barras, 33 barras, 84 barras e 136 barras). Os resultados obtidos da aplicação do algoritmo permitem avaliar o seu desempenho e eficiência em comparação com a melhor solução encontrada na literatura especializada. / The application of the biased random-key genetic algorithm for the reconfiguration of distribution systems is proposed in this Dissertation. The problem of reconfiguration in distribution systems consists of finding the radial configuration that presents the minimum losses, satisfying topological and operating constraints and is commonly modeled as a mixed-integer nonlinear programming problem. The proposed method uses the Prim's algorithm to generate radial configurations that are evaluated through a backward/forward sweep power flow method. The biased random-key genetic algorithm used was developed in the programming language FORTRAN and was tested in four systems (14-bus, 33-bus, 84-bus and 136-bus). The obtained results show the performance and efficiency of the proposed method in comparison to the best solution found in the specialized literature.