2024-03-28T19:05:43Z
https://seer.ufrgs.br/index.php/rita/oai
oai:seer.ufrgs.br:article/80478
2020-01-11T19:30:12Z
rita:EHSO
driver
Investigation of Archiving Techniques for Evolutionary Multi-objective Optimizers
Medeiros, Hudson Geovane de
Goldbarg, Elizabeth Ferreira Gouvêa
Goldbarg, Marco Cesar
Archiving techniques
Multi-objective evolutionary algorithms
Recycling techniques.
Abstract: The optimization of multi-objective problems from the Pareto dominance viewpoint can lead to huge sets of incomparable solutions. Many heuristic techniques proposed to these problems have to deal with approximation sets that can be limited or not. Usually, a new solution generated by a heuristic is compared with other archived non-dominated solutions generated previously. Many techniques deal with limited size archives, since comparisons within unlimited archives may require significant computational effort. To maintain limited archives, solutions need to be discarded. Several techniques were proposed to deal with the problem of deciding which solutions remain in the archive and which are discarded. Previous investigations showed that those techniques might not prevent deterioration of the archives. In this study, we propose to store discarded solutions in a secondary archive and, periodically, recycle them, bringing them back to the optimization process. Three recycling techniques were investigated for three known methods. The datasets for the experiments consisted of 91 instances of discrete and continuous problems with 2, 3 and 4 objectives. The results showed that the recycling method can benefit the tested optimizers on many problem classes.
Instituto de Informática - Universidade Federal do Rio Grande do Sul
2018-11-19
info:eu-repo/semantics/article
info:eu-repo/semantics/publishedVersion
application/pdf
https://seer.ufrgs.br/index.php/rita/article/view/RITA_Vol25_Nr4_11
10.22456/2175-2745.80478
Revista de Informática Teórica e Aplicada; Vol. 25 No. 4 (2018); 11-27
Revista de Informática Teórica e Aplicada; v. 25 n. 4 (2018); 11-27
2175-2745
0103-4308
eng
https://seer.ufrgs.br/index.php/rita/article/view/RITA_Vol25_Nr4_11/pdf
Copyright (c) 2018 Hudson Geovane de Medeiros, Elizabeth Ferreira Gouvêa Goldbarg, Marco Cesar Goldbarg
oai:seer.ufrgs.br:article/80525
2020-01-11T19:55:01Z
rita:EHSO
driver
Algorithms for the power-p Steiner tree problem in the Euclidean plane
Burt, Christina
Costa, Alysson
Ras, Charl
Steiner tree problem
Power-p
Mixed-integer formulations
Heuristics
We study the problem of constructing minimum power-$p$ Euclidean $k$-Steiner trees in the plane. The problem is to find a tree of minimum cost spanning a set of given terminals where, as opposed to the minimum spanning tree problem, at most $k$ additional nodes (Steiner points) may be introduced anywhere in the plane. The cost of an edge is its length to the power of $p$ (where $p\geq 1$), and the cost of a network is the sum of all edge costs. We propose two heuristics: a ``beaded" minimum spanning tree heuristic; and a heuristic which alternates between minimum spanning tree construction and a local fixed topology minimisation procedure for locating the Steiner points. We show that the performance ratio $\kappa$ of the beaded-MST heuristic satisfies $\sqrt{3}^{p-1}(1+2^{1-p})\leq \kappa\leq 3(2^{p-1})$. We then provide two mixed-integer nonlinear programming formulations for the problem, and extend several important geometric properties into valid inequalities. Finally, we combine the valid inequalities with warm-starting and preprocessing to obtain computational improvements for the $p=2$ case.
Instituto de Informática - Universidade Federal do Rio Grande do Sul
2018-11-19
info:eu-repo/semantics/article
info:eu-repo/semantics/publishedVersion
application/pdf
https://seer.ufrgs.br/index.php/rita/article/view/RITA_Vol25_Nr4_28
10.22456/2175-2745.80525
Revista de Informática Teórica e Aplicada; Vol. 25 No. 4 (2018); 28-42
Revista de Informática Teórica e Aplicada; v. 25 n. 4 (2018); 28-42
2175-2745
0103-4308
eng
https://seer.ufrgs.br/index.php/rita/article/view/RITA_Vol25_Nr4_28/pdf
Copyright (c) 2018 Christina Burt, Alysson Costa, Charl Ras
oai:seer.ufrgs.br:article/80702
2020-01-11T18:42:49Z
rita:EHSO
driver
Extreme Learning Machine combined with a Differential Evolution algorithm for lithology identification
Saporetti, Camila Martins
Duarte, Grasiele Regina
Fonseca, Tales Lima
da Fonseca, Leonardo Goliatt
Pereira, Egberto
Extreme Learning Machines
Differential Evolution
Lithology
Lithology identification, obtained through the analysis of several geophysical properties, has an important role in the process of characterization of oil reservoirs. The identification can be accomplished by direct and indirect methods, but these methods are not always feasible because of the cost or imprecision of the results generated. Consequently, there is a need to automate the procedure of reservoir characterization and, in this context, computational intelligence techniques appear as an alternative to lithology identification. However, to acquire proper performance, usually some parameters should be adjusted and this can become a hard task depending on the complexity of the underlying problem. This paper aims to apply an Extreme Learning Machine (ELM) adjusted with a Differential Evolution (DE) to classify data from the South Provence Basin, using a previously published paper as a baseline reference. The paper contributions include the use of an evolutionary algorithm as a tool for search on the hyperparameters of the ELM. In addition, an activation function recently proposed in the literature is implemented and tested. The computational approach developed here has the potential to assist in petrographic data classification and helps to improve the process of reservoir characterization and the production development planning.
Instituto de Informática - Universidade Federal do Rio Grande do Sul
2018-11-19
info:eu-repo/semantics/article
info:eu-repo/semantics/publishedVersion
application/pdf
https://seer.ufrgs.br/index.php/rita/article/view/RITA_Vol25_Nr4_43
10.22456/2175-2745.80702
Revista de Informática Teórica e Aplicada; Vol. 25 No. 4 (2018); 43-56
Revista de Informática Teórica e Aplicada; v. 25 n. 4 (2018); 43-56
2175-2745
0103-4308
eng
https://seer.ufrgs.br/index.php/rita/article/view/RITA_Vol25_Nr4_43/pdf
Copyright (c) 2018 Camila Martins Saporetti, Grasiele Regina Duarte, Tales Lima Fonseca, Leonardo Goliatt da Fonseca, Egberto Pereira
oai:seer.ufrgs.br:article/80721
2020-01-11T19:03:52Z
rita:EHSO
driver
Exact Algorithms for the Graph Coloring Problem
de Lima, Alane Marie
Carmo, Renato
Graph Theory
Graph Coloring
Exact Algorithms
The graph coloring problem is the problem of partitioning the vertices of a graph into the smallest possible set of independent sets. Since it is a well-known NP-Hard problem, it is of great interest of the computer science finding results over exact algorithms that solve it. The main algorithms of this kind, though, are scattered through the literature. In this paper, we group and contextualize some of these algorithms, which are based in Dynamic Programming, Branch-and-Bound and Integer Linear Programming. The algorithms for the first group are based in the work of Lawler, which searches maximal independent sets on each subset of vertices of a graph as the base of his algorithm. In the second group, the algorithms are based in the work of Brelaz, which adapted the DSATUR procedure to an exact version, and in the work of Zykov, which introduced the definition of Zykov trees. The third group contains the algorithms based in the work of Mehrotra and Trick, which uses the Column Generation method.
Instituto de Informática - Universidade Federal do Rio Grande do Sul
2018-11-19
info:eu-repo/semantics/article
info:eu-repo/semantics/publishedVersion
application/pdf
https://seer.ufrgs.br/index.php/rita/article/view/RITA_Vol25_Nr4_57
10.22456/2175-2745.80721
Revista de Informática Teórica e Aplicada; Vol. 25 No. 4 (2018); 57-73
Revista de Informática Teórica e Aplicada; v. 25 n. 4 (2018); 57-73
2175-2745
0103-4308
eng
https://seer.ufrgs.br/index.php/rita/article/view/RITA_Vol25_Nr4_57/pdf
Copyright (c) 2018 Alane Marie de Lima, Renato Carmo