Navegando por Autor "Haddad, Matheus Nohra"
Agora exibindo 1 - 5 de 5
Resultados por página
Opções de Ordenação
Item Algoritmo aco rank based aprimorado para uso na seleção de variáveis em modelos de classificação.(2023) Delamora, Roberto Alexandre; Coelho, Bruno Nazário; Sabino, Jodelson Aguilar; Coelho, Bruno Nazário; Sabino, Jodelson Aguilar; Souza, Marcone Jamilson Freitas; Haddad, Matheus NohraSeleção de atributos é um processo onde se busca o melhor subconjunto de variáveis em um determinado conjunto de dados. Em um mundo em que as decisões são cada vez mais baseadas em dados, torna-se essencial o uso de ferramentas que realizem, de forma mais eficiente, essa seleção de variáveis, visando melhorar o desempenho final dos modelos. Neste trabalho, é utilizado como referência o algoritmo pertencente à meta-heurística de otimização por colônia de formigas (ACO), originalmente criado para tratar o problema do Caixeiro Viajante (TSP), e são introduzidas melhorias para adequá-lo à tarefa de seleção de variáveis. O novo algoritmo proposto utiliza métodos Filter-Wrapper em sua estrutura e uma função de aptidão criada especificamente para refinar a seleção de soluções. Esta abordagem foi avaliada em conjuntos de dados do repositório de aprendizado de máquina UCI e os resultados foram comparados com outro algoritmo recentemente publicado que é considerado referência na seleção de variáveis usando ACO. O algoritmo proposto apresentou ganhos importantes no desempenho, superando o algoritmo de comparação na maioria dos casos estudados.Item Algoritmos heurísticos híbridos para o problema de sequenciamento em máquinas paralelas não-relacionadas com tempos de preparação dependentes da sequência.(Programa de Pós-Graduação em Ciência da Computação. Departamento de Ciência da Computação, Instituto de Ciências Exatas e Biológicas, Universidade Federal de Ouro Preto., 2012) Haddad, Matheus Nohra; Souza, Marcone Jamilson FreitasEste trabalho aborda o problema de sequenciamento em máquinas paralelas não- relacionadas com tempos de preparação dependentes da sequência, dó inglês Unre- lated Parallel Machine Scheduling Problem with Sequence Dependent Setup Times, ou apenas UPMSPST. Neste problema há um conjunto de tarefas e máquinas e a cada tarefa está associado um tempo de processamento, que é diferente para cada máquina. Dadas duas tarefas, também existe um tempo de preparação dependente da sequência de lase da máquina utilizada. O objetivo considerado neste problema é minimizar o tempo máximo de conclusão do sequenciamento, o chamado makes pan. OUPMSPST é muito encontrado no âmbito industrial e pertence à classe NP- difícil. Visando a sua resolução, são propostos três algoritmos heurísticos híbridos. O primeiro, nomeado VP, combina os procedimentos heurísticos Iterated Local Search (ILS), Variable Neighborhood Descent (VND)e Path Relinking(PR). O segundo, nomeado GIVP, difere do primeiro pelo fato de gerar a solução inicial pela fase de construção Greedy Randomized AdaptiveS earch Procedure(GRASP), e não por um procedimento guloso. O terceiro algoritmo, nomeado GIVMP, diferedos outros em três estratégias: a fase PR utiliza a estratégia mix edrelinking ao invés de backward relinking, as vizinhanças que formam o VND são usada sem ordem aleatória a cada chamada e não em ordem previamente de nida; por m,o GIVMP inclui um módulo de busca local feita pelo resolvedor CPLEX12.1 de programação matemática. Este resolvedor é aplicado apenas à máquina gargalo do problema e utiliza um modelo de programação inteira mista base a dono problemado Caixeiro Viajante Assimétrico. Para explorar o espaço de soluções são utilizados movimentos de inserção e troca de tarefas entre máquinas. Para testar os algoritmos foram utilizados dois conjuntos de problemas-teste da literatura. Inicialmente eles foram comparados entre si em um conjunto reduzido de instâncias ,tendo- severi cado a superioridade do algoritmo GIVMP. Em seguida, este algoritmo foi compara do com outros seis da literatura, sendo dois no primeiro conjunto de problemas- teste e outros quatro no Segundo. No primeiro conjunto veri cou-se a superiorida de absoluta do GIVMP sobre os dois algoritmos genéticos da literatura, tendo-se encontra do desvios percentuais relativos médios menores e novas melhores soluções.No segundo conjunto de problemas-teste vericou-se que o GIVMP tem desempenho inferior a um dos algoritmos, mas superior em relação aos outros três. Observa-se,no entanto,que neste segundo conjunto de problemas, não foram disponibilizados os desvios percentuais relativos médios dos algoritmos, mas apenas os desvios dos melhores valores encontrados,impedindo uma comparação de robustez dos algoritmos.Item Algoritmos para o problema de sequenciamento de tarefas em máquinas paralelas idênticas.(2020) Ribeiro, Klevison Daniel de Oliveira; Souza, Marcone Jamilson Freitas; Cota, Luciano Perdigão; Souza, Marcone Jamilson Freitas; Cota, Luciano Perdigão; Guimarães, Frederico Gadelha; Ribeiro, Roberto Gomes; Haddad, Matheus NohraEste trabalho trata do Problema de Sequenciamento de Tarefas em Máquinas Paralelas Idênticas objetivando minimizar o makespan e o custo total de energia (TEC). Neste problema busca-se alocar um grupo de tarefas a um conjunto de máquinas disponíveis de forma a se reduzir os custos de operação. Tal classe de problemas tem sido amplamente estudada atualmente, dada a grande busca pela eficiência energética e a otimização dos processos de produção. Além disso, a investigação de tal problema se justifica por ele pertencer à classe NP-difícil. Para solucioná-lo, foi ajustado um modelo bi-objetivo da literatura para uma abordagem mono-objetiva por soma ponderada. Também foram adaptados dois algoritmos baseados na meta-heurística Iterated Local Search (ILS): o primeiro, referido como ILS apenas, é uma versão clássica do método proposto na literatura. Já o segundo, é uma versão aperfeiçoada, denominada Smart Iterated Local Search, ou apenas SILS. Nessa versão adaptada, a dinâmica de perturbação é alterada em relação ao algoritmo clássico, permitindo um melhor desempenho da busca local incorporada ao método. Enquanto no ILS clássico o nível de perturbação é alterado sempre que não ocorre melhora na solução, no SILS são realizadas novas tentativas de melhoria em um mesmo nível de perturbação. Tal modificação foi realizada partindo da hipótese de que o aumento de nível da perturbação pode ser precipitado, visto que se trata de um movimento aleatório e que o vizinho gerado por este movimento pode não ter sido bom para a continuidade da busca. Os dois algoritmos implementados têm o mesmo método de busca local, o Randomized Variable Neighborhood Search (RVND). Para testar os algoritmos foram utilizadas instâncias da literatura de pequeno e grande porte. Ambos os algoritmos foram calibrados pelo software Irace. Os resultados dos algoritmos foram comparados entre si e também com os do otimizador CPLEX. Com base nos resultados, verificou-se que o SILS se mostrou mais eficiente do que o ILS clássico com relação à capacidade de encontrar melhores soluções.Item A general variable neighborhood search approach for the resolution of the Eternity II Puzzle.(2010) Coelho, Igor Machado; Coelho, Bruno Nazário; Coelho, Vitor Nazário; Haddad, Matheus Nohra; Souza, Marcone Jamilson Freitas; Ochi, Luiz SatoruItem Large neighborhood-based metaheuristic and branch-and-price for the pickup and delivery problem with split loads.(2018) Haddad, Matheus Nohra; Pinto, Rafael Martinelli; Vidal, Thibaut Victor Gaston; Martins, Simone de Lima; Ochi, Luiz Satoru; Souza, Marcone Jamilson Freitas; Hartl, RichardWe consider the multi-vehicle one-to-one pickup and delivery problem with split loads, a NP-hard problem linked with a variety of applications for bulk product transportation, bike-sharing systems and inventory re-balancing. This problem is notoriously difficult due to the interaction of two challenging vehicle routing attributes, “pickups and deliveries” and “split deliveries”. This possibly leads to optimal solutions of a size that grows exponentially with the instance size, containing multiple visits per customer pair, even in the same route. To solve this problem, we propose an iterated local search metaheuristic as well as a branch-and-price algorithm. The core of the metaheuristic consists of a new large neighborhood search, which reduces the problem of finding the best insertion combination of a pickup and delivery pair into a route (with possible splits) to a resource-constrained shortest path and knapsack problem. Similarly, the branch-and-price algorithm uses sophisticated labeling techniques, route relaxations, pre-processing and branching rules for an efficient resolution. Our computational experiments on classical single-vehicle instances demonstrate the excellent performance of the metaheuristic, which produces new best known solutions for 92 out of 93 test instances, and outperforms all previous algorithms. Experimental results on new multi-vehicle instances with distance constraints are also reported. The branch-and-price algorithm produces optimal solutions for instances with up to 20 pickup-and-delivery pairs, and very accurate solutions are found by the metaheuristic.