DECOM - Artigos publicados em periódicos

Permanent URI for this collection

https://monog.ufop.br/handle/123456789/578

Browse

Now showing 1 - 20 of 301

5th International Conference on Variable Neighborhood Search (ICVNS'17).
(2018) Coelho, Vitor Nazário; Santos, Haroldo Gambini; Coelho, Igor Machado; Penna, Puca Huachi Vaz; Oliveira, Thays Aparecida de; Souza, Marcone Jamilson Freitas; Sifaleras, Angelo
This volume presents selected, peer-reviewed, short papers that were accepted for presentation in the 5th International Conference on Variable Neighborhood Search (ICVNS'17) which was held in Ouro Preto, Brazil, during October 2–4, 2017.
Abordagem exata e heurísticas para o problema de planejamento de ordens de manutenção de longo prazo : um estudo de caso industrial de larga escala.
(2019) Aquino, Roberto Dias; Chagas, Jonatas Batista Costa das; Souza, Marcone Jamilson Freitas
Este trabalho tem seu foco em um problema real de planejamento de manutenção de longo prazo para uma planta de beneficiamento de minério de ferro no Brasil. Este e um problema complexo de programação de ordens de manutenção à preventiva, para o qual é necessário atribuir ordens de manutenção preventiva para as equipes de trabalho disponíveis em um horizonte de 52 semanas. Para resolvê-lo, foi desenvolvido um modelo de programação linear inteira mista, bem como algoritmos metaheurísticos baseados nos métodos Simulated Annealing, Variable Neighborhood Search e Biased Random-Key Genetic Algorithm. O modelo exato serviu para validar os resultados dos algoritmos heurísticos aplicados a instancias de dimensões menores. Os algoritmos metaheurísticos foram capazes de produzir soluções melhores do que aquelas empregadas pela empresa, e em um tempo de execução adequado para a tomada de decisão.
Active contours for overlapping cervical cell segmentation.
(2021) Araujo, Flavio Henrique Duarte de; Silva, Romuere Rodrigues Veloso e; Medeiros, Fátima Nelsizeuma Sombra de; Rocha Neto, Jeová Farias Sales; Oliveira, Paulo Henrique Calaes; Bianchi, Andrea Gomes Campos; Ushizima, Daniela Mayumi
The nuclei and cytoplasm segmentation of cervical cells is a well studied problem. However, the current segmentation algorithms are not robust to clinical practice due to the high computational cost or because they cannot accurately segment cells with high overlapping. In this paper, we propose a method that is capable of segmenting both cytoplasm and nucleus of each individual cell in a clump of overlapping cells. The proposed method consists of three steps: 1) cellular mass segmentation; 2) nucleus segmentation; 3)cytoplasm identification based on an active contour method. We carried out experiments on both synthetic and real cell images. The performance evaluation of the proposed method showed that it was less sensitive to the increase in the number of cells per image and the overlapping ratio against two other existing algorithms. It has also achieved a promising low processing time and, hence, it has the potential to support expert systems for cervical cell recognition.
Adaptive large neighborhood search applied to the design of electronic circuits.
(2018) Santos, Vinícius Gandra Martins; Carvalho, Marco Antonio Moreira de
In this paper, a new algorithm is proposed for solving the Gate Matrix Layout Problem (GMLP). This combinatorial problem is -Hard and aims to determine the physical layout of the components of an electronic circuit in order to minimize the number of tracks required to connect its nets. By reducing the circuit area, it is possible to reduce manufacturing costs and also improve circuit performance. Computer-aided design of such layouts has direct practical applications in engineering and industry, including information technology, industrial processes automation, and consumer goods production. We propose new local search procedures combined in an Adaptive Large Neighborhood Search (ALNS) metaheuristic to generate solutions for the GMLP. To assess the quality of the proposed method, we have considered 1455 real-world and artificial instances from the literature and compared the proposed ALNS with the state-of-the-art method for the GMLP solution. The ALNS performance is robust as it matches 89% of known optimal solutions and also improves the best known results in some instances.
Aggregation Trees for visualization and dimension reduction in many-objective optimization.
(2015) Freitas, Alan Robert Resende de; Fleming, Peter J.; Guimarães, Frederico Gadelha
This paper introduces the concept of Aggregation Trees for the visualization of the results of high-dimensional multi-objective optimization problems, or many-objective problems and as a means of performing dimension reduction. The high dimensionality of manyobjective optimization makes it difficult to represent the relationship between objectives and solutions in such problems and most approaches in the literature are based on the representation of solutions in lower dimensions. The method of Aggregation Trees proposed here is based on an iterative aggregation of objectives that are represented in a tree. The location of conflict is also calculated and represented on the tree. Thus, the tree can represent which objectives and groups of objectives are the most harmonic, what sort of conflict is present between groups of objectives, and which aggregations would be helpful in order to reduce the problem dimension.
Algorithms based on VNS for solving the Single Machine Scheduling Problem with Earliness and Tardiness Penalties.
(2018) Rosa, Bruno Ferreira; Souza, Marcone Jamilson Freitas; Souza, Sergio Ricardo de
This work implements and compares four algorithms based on Variable Neighborhood Search (VNS), named RVNS, GVNSf, GVNSr and GVNSrf, for solving the Single Machine Scheduling Problem with Earliness and Tardiness Penalties (SM-SPETP). Computational experiments showed that the algorithm GVNSf obtained better-quality solutions compared with the other algorithms, including an algorithm found in the literature. The algorithms GVNSr and GVNSrf obtained solutions close to the GVNSf, and outperformed the algorithm of the literature, both with respect to the quality of the solutions and the computational times.
Algorithms for job scheduling problems with distinct time windows and general earliness/tardiness penalties.
(2016) Rosa, Bruno Ferreira; Souza, Marcone Jamilson Freitas; Souza, Sérgio Ricardo de; França Filho, Moacir Felizardo de; Ales, Zacharie; Michelon, Philippe Yves Paul
This paper addresses the single machine scheduling problem with distinct time windows and sequence- dependent setup times. The objective is to minimize the total weighted earliness and tardiness. The prob- lem involves determining the job execution sequence and the starting time for each job in the sequence. An implicit enumeration algorithm denoted IE and a general variable neighborhood search algorithm de- noted GVNS are proposed to determine the job scheduling. IE is an exact algorithm, whereas GVNS is a heuristic algorithm. In order to define the starting times, an O ( n 2 ) idle time insertion algorithm (ITIA) is proposed. IE and GVNS use the ITIA algorithm to determine the starting time for each job. However, the IE algorithm is only valid for instances with sequence-independent setup times, and takes advantage of theoretical results generated for this problem. Computational experiments show that the ITIA algo- rithm is more efficient than the only other equivalent algorithm found in the literature. The IE algorithm allows the optimal solutions of all instances with up to 15 jobs to be determined within a feasible com- putational time. For larger instances, GVNS produces better-quality solutions requiring less computational time compared with the other algorithm from the literature.
Um algoritmo evolutivo híbrido para o problema de recobrimento de rotas com coletas de premios.
(2010) Silva, Matheus de Souza Alves; Mine, Marcio Tadayuki; Ochi, Luiz Satoru; Souza, Marcone Jamilson Freitas
Este artigo propõe um algoritmo evolutivo híbrido para obter soluções aproximadas para o Problema de Recobrimento de Rotas com Coleta de Prêmios (PRRCP). O algoritmo proposto combina estratégias heurísticas baseadas nos procedimentos Busca Local Iterada, Busca em Vizinhança Variável, Reconexão por Caminhos e GENIUS. Resultados computacionais para um conjunto de instancias mostram a eﬁciência e a robustez da heurística proposta.
Algoritmos simulated annealing e GRASP para o planejamento de aulas de um departamento.
(2009) Martins, Alexandre Xavier; Castro, Raphael Reis Mauro de; Souza, Marcone Jamilson Freitas
Este trabalho trata do problema de programação de horários em escolas. Dada sua natureza combinatória, ele é resolvido por meio de dois algoritmos metaeurísticos, um baseado em Simulated Annealing e outro em GRASP. Ambos possuem parâmetros auto-adaptativos, dispensando, assim, a calibragem destes. Para testálos são utilizados dados reais do departamento de uma universidade. São apresentados resultados computacionais, comparando-se as soluções produzidas pelos algoritmos propostos com aquelas geradas manualmente pela instituição de ensino. Os resultados obtidos mostram a eficiência dos métodos desenvolvidos perante as soluções manuais e a superioridade do Simulated Annealing, em comparação com o GRASP para as instâncias tratadas.
An adaptive multi-objective algorithm based on decomposition and large neighborhood search for a green machine scheduling problem.
(2019) Cota, Luciano Perdigão; Guimarães, Frederico Gadelha; Ribeiro, Roberto Gomes; Meneghini, Ivan Reinaldo; Oliveira, Fernando Bernardes de; Souza, Marcone Jamilson Freitas; Siarry, Patrick
Green machine scheduling consists in the allocation of jobs in order to maximize production, in view of the sustainable use of energy. This work addresses the unrelated parallel machine scheduling problem with setup times, with the minimization of the makespan and the total energy consumption. The latter takes into account the power consumption of each machine in different operation modes. We propose multi-objective extensions of the Adaptive Large Neighborhood Search (ALNS) metaheuristic with Learning Automata (LA) to improve the search process and to solve the large scale instances efficiently. ALNS combines ad-hoc destroy and repair (also named removal and insertion) operators and a local search procedure. The LA is used to adapt the selection of insertion and removal operators within the framework of ALNS. Two new algorithms are developed: the MO-ALNS and the MO-ALNS/D. The first algorithm is a direct extension of single objective ALNS by using multi-objective local search. As this method does not offer much control of the diversification of the Pareto front approximation, a second strategy employs the decomposition approach similar to MOEA/D algorithm. The results show that the MO-ALNS/D algorithm has better performance than MO-ALNS and MOEA/D in all indicators. These findings show that the decomposition strategy is beneficial not only for evolutionary algorithms, but it is indeed an efficient way to extend ALNS to multi-objective problems.
An end-to-end deep learning system for hop classification.
(2022) Castro, Pedro Henrique Nascimento; Moreira, Gladston Juliano Prates; Luz, Eduardo José da Silva
Automatic classification of plant species is a very challenging and widely studied problem in the literature. Distinguishing different varieties within the same species is an even more challenging task although less explored. Nevertheless, for some species distinguishing the varieties within the species can be of paramount importance. Hops, a plant widely used in beer production, has over 250 cataloged varieties. Although the varieties have similar appearances, their chemical components, which influence the aroma and flavor of the drink, are quite heterogeneous. Therefore, it is important for producers to distinguish which variety the plant belongs to in a simple manner. In this work, an end-to-end deep learning system is proposed to automate the task of hop classification. Five architectures are proposed and evaluated with an uncontrolled environment dataset that includes 12 varieties of hops on 1592 images, from three different cell phone cameras. The best architecture automatically detects the hop leaves on the image and performs the classification using the information of up to 10 leaves. The method achieved an accuracy of 95.69% with an inference time of 672ms. To reach such figures, state-of-the-art convolutional blocks were explored along with data augmentation techniques. Our results show that the system is robust and has a low computational cost.
An ensemble method for nuclei detection of overlapping cervical cells.
(2021) Diniz, Débora Nasser; Vitor, Rafael Ferreira; Bianchi, Andrea Gomes Campos; Silva, Saul Emanuel Delabrida; Carneiro, Cláudia Martins; Ushizima, Daniela Mayumi; Medeiros, Fátima Nelsizeuma Sombra de; Souza, Marcone Jamilson Freitas
The Pap test is a preventive approach that requires specialized and labor-intensive examination of cytological preparations to track potentially cancerous cells from the internal and external cervix surface. A cytopathologist must analyze many microscopic fields while screening for abnormal cells. Therefore there is hope that a support decision system could assist with clinical diagnosis, for example, by identifying sub-cellular abnormalities, such as changes in the nuclei features. This work proposes an ensemble method for cervical nuclei detection aiming to reduce the workload of cytopathologists. First, a preprocessing phase divides the original image into superpixels, which are input to feature extraction and selection algorithms. The proposed ensemble method combines three classifiers: Decision Tree (DT), Nearest Centroid (NC), and k-Nearest Neighbors (k-NN), which are evaluated against the ISBI’14 Overlapping Cervical Cytology Image Segmentation Challenge dataset. Experiments show that the proposed method is the state-of-the-art algorithm of the literature for recall (0.999) and F1 values (0.993). It produced a recall very close to the optimum value and also kept high precision (0.988).
An ensemble of spatially explicit land-cover model projections : prospects and challenges to retrospectively evaluate deforestation policy.
(2017) Bradley, Andrew V.; Rosa, Isabel Maria Duarte; Brandão Júnior, Amintas; Crema, Stefano; Dobler, Carlos; Moulds, Simon; Ahmed, Sadia E.; Carneiro, Tiago Garcia de Senna; Smith, Matthew J.; Ewers, Robert M.
Ensemble techniques, common in many disciplines, have yet to be fully exploited with spatially explicit projections from land-change models. We trial a land-change model ensemble to assess the impact of policies designed to conserve tropical rainforest at the municipality scale in Brazil, noting the achievements made and challenges ahead. Four spatial model frameworks that were calibrated with the same predictor variables produced 21 counterfactual simulations of the actual landscape. Individual projections with a uniform calibration period gave estimates that between 29 and 68% of the simulated deforestation was saved, but lacked an uncertainty estimate, whilst batch projections from two different model frameworks provided a more dependable mean estimate that 38 and 49% deforestation was prevented with an uncertainty range of 1900 and 1000 km2. The consensus ensembles used agreement between the projections and found that the seven examples with a uniform calibration period produced an error margin of ±435.94 km2 and a prevented forest loss estimate of 50%. Using all 21 projections with diverse calibration periods improved these errors to ±179.26 km2 with a 53% estimate of prevented forest loss. Whilst we achieved a method of combining projections of different frameworks to reduce uncertainty of individual modelling frameworks, demonstrating a control model and accounting for non-linear conditions are challenges that will provide better confidence in this method as an operational tool. Such retrospective evidence could be used to make timely rewards for efforts of governments and municipalities to support tropical forest conservation and help mitigate deforestation.
An extensible real-time visualization pipeline for dynamic spatial modeling.
(2013) Rodrigues, Antônio José da Cunha; Carneiro, Tiago Garcia de Senna; Andrade Neto, Pedro Ribeiro de
This article presents research results of an extensible visualization pipeline for real-time exploratory analysis of spatially explicit simulations. We identify software requirements and discuss the main conceptual and design issues. We propose a protocol for data serialization, a high performance monitoring mechanism, and graphical interfaces for visualization. Performance experiments show that combining multithreading and the Blackboard design pattern reduces the visualization response time by 80%, with no significant increase in memory consumption (less than 7%). The components presented in this article have been integrated in the TerraME modeling platform for simulation of terrestrial systems.
An extensible toolbox for modeling nature-society interactions.
(2013) Carneiro, Tiago Garcia de Senna; Andrade Neto, Pedro Ribeiro de; Câmara, Gilberto; Monteiro, Antônio Miguel Vieira; Pereira, Rodrigo Reis
Modeling interactions between social and natural systems is a hard task. It involves collecting data, building up a conceptual approach, implementing, calibrating, simulating, validating, and possibly repeating these steps again and again. There are different conceptual approaches proposed in the literature to tackle this problem. However, for complex problems it is better to combine different approaches, giving rise to a need for flexible and extensible frameworks for modeling nature-society interactions. In this paper we present TerraME, an open source toolbox that supports multi-paradigm and multi-scale modeling of coupled human-environmental systems. It enables models that combine agent based, cellular automata, system dynamics, and discrete event simulation paradigms. TerraME has a GIS interface for managing real-world geospatial data and uses Lua, an expressive scripting language.
An ILS-based algorithm to solve a large-scale real heterogeneous fleet VRP with multi-trips and docking constraints.
(2016) Coelho, Vitor Nazário; Grasas, A.; Ramalinho, H.; Coelho, Igor Machado; Souza, Marcone Jamilson Freitas; Cruz, Raphael Carlos
Distribution planning is crucial for most companies since goods are rarely produced and consumed at the same place. Distribution costs, inaddition, can be an important component of the final cost of the products. In this paper, westudya VRP variant inspired on a real case of a large distribution company. In particular, we consider a VRP with a heterogeneous fleet of vehicles that a real lowed to perform multipletrips. The problem also includes docking constraints in which some vehicles are unable to serve some particular customers, and a realistic objective function with vehicles’ fixed and distance- based costs and a costper customer visited. We design a trajectory search heuristic called GILS-VND that combines Iterated Local Search (ILS), Greedy Randomized Adaptive Search Procedure (GRASP) and Variable Neighborhood Descent (VND) procedures. This method obtains competitive solutions and improves the company solutions leading to significant savings in transportation costs.
An integer programming approach to the multimode resource-constrained multiproject scheduling problem.
(2016) Toffolo, Túlio Ângelo Machado; Santos, Haroldo Gambini; Carvalho, Marco Antonio Moreira de; Soares, Janniele Aparecida
The project scheduling problem (PSP) is the subject of several studies in computer science, mathematics, and operations research because of the hardness of solving it and its practical importance. This work tackles an extended version of the problem known as the multimode resourceconstrained multiproject scheduling problem. A solution to this problem consists of a schedule of jobs from various projects, so that the job allocations do not exceed the stipulated limits of renewable and nonrenewable resources. To accomplish this, a set of execution modes for the jobs must be chosen, as the jobs’ duration and amount of needed resources vary depending on the mode selected. Finally, the schedule must also consider precedence constraints between jobs. This work proposes heuristic methods based on integer programming to solve the PSP considered in the Multidisciplinary International Scheduling Conference: Theory and Applications (MISTA) 2013 Challenge. The developed solver was ranked third in the competition, being able to find feasible and competitive solutions for all instances and improving best known solutions for some problems.
An intrinsically-typed solution for the list-machine benchmark.
(2022) Feitosa, Samuel da Silva; Ribeiro, Rodrigo Geraldo
Formal models are important tools in the programming language research community. However, such models are full of intricacies and, due to that, they are subject to subtle errors. Such failures motivated the usage of tools to ensure the correctness of these formalisms. One way to eliminate such errors is to encode models in a dependently-typed language in order to ensure its ‘‘correctness-by-construction’’. In this paper, we use this idea to build a verified interpreter for the list-machine benchmark in the Agda programming language, comparing the results with formalizations developed by Appel et al.. We formalize the 14 tasks of the benchmark using roughly 14% of LOC compared to a Twelf solution, and 47% of LOC compared to a Coq solution, even without the use of proof automation. We also describe a solution to the second version of the benchmark and compare it with Appel’s et. al. Coq-based solution.
An iterated local search heuristic for multi-capacity bin packing and machine reassignment problems.
(2013) Masson, Renaud; Vidal, Thibaut Victor Gaston; Michallet, Julien; Penna, Puca Huachi Vaz; Petrucci, Vinicius; Subramanian, Anand; Dubedout, Hugues
This paper proposes an efficient Multi-Start Iterated Local Search for Packing Problems (MS-ILS-PPs) metaheuristic for Multi-Capacity Bin Packing Problems (MCBPP) and Machine Reassignment Problems (MRP). The MCBPP is a generalization of the classical bin-packing problem in which the machine (bin) capacity and task (item) sizes are given by multiple (resource) dimensions. The MRP is a challenging and novel optimization problem, aimed at maximizing the usage of available machines by reallocating tasks/processes among those machines in a cost-efficient manner, while fulfilling several capacity, conflict, and dependency-related constraints. The proposed MS-ILS-PP approach relies on simple neighborhoods as well as problem-tailored shaking procedures. We perform computational experiments on MRP benchmark instances containing between 100 and 50,000 processes. Near-optimum multi-resource allocation and scheduling solutions are obtained while meeting specified processing-time requirements (on the order of minutes). In particular, for 9/28 instances with more than 1000 processes, the gap between the solution value and a lower bound measure is smaller than 0.1%. Our optimization method is also applied to solve classical benchmark instances for the MCBPP, yielding the best known solutions and optimum ones in most cases. In addition, several upper bounds for non-solved problems were improved.
An iterated local search heuristic for the heterogeneous fleet vehicle routing problem.
(2013) Penna, Puca Huachi Vaz; Subramanian, Anand; Ochi, Luiz Satoru
This paper deals with the Heterogeneous Fleet Vehicle Routing Problem (HFVRP). The HFVRP is NP-hard since it is a generalization of the classical Vehicle Routing Problem (VRP), in which clients are served by a heterogeneous fleet of vehicles with distinct capacities and costs. The objective is to design a set of routes in such a way that the sum of the costs is minimized. The proposed algorithm is based on the Iterated Local Search (ILS) metaheuristic which uses a Variable Neighborhood Descent procedure, with a random neighborhood ordering (RVND), in the local search phase. To the best of our knowledge, this is the first ILS approach for the HFVRP. The developed heuristic was tested on well-known benchmark instances involving 20, 50, 75 and 100 customers. These test-problems also include dependent and/or fixed costs according to the vehicle type. The results obtained are quite competitive when compared to other algorithms found in the literature.

Browse

Browsing DECOM - Artigos publicados em periódicos by Title

Results Per Page

Sort Options