Skip to main content

Resultados relacionados

Resultados totales (Incluyendo duplicados): 7
Encontrada(s) 1 página(s)

Zaguán. Repositorio Digital de la Universidad de Zaragoza
Publication Artículo científico (JournalArticle)

µG2-ELM: an upgraded implementation of µ G-ELM

  • Lacruz, B.
  • Lahoz, D.
  • Mateo, P. M.
µG-ELM is a multiobjective evolutionary algorithm which looks for the best (in terms of the MSE) and most compact artificial neural network using the ELM methodology. In this work we present the µG2-ELM, an upgraded version of µG-ELM, previously presented by the authors. The upgrading is based on three key elements: a specifically designed approach for the initialization of the weights of the initial artificial neural networks, the introduction of a re-sowing process when selecting the population to be evolved and a change of the process used to modify the weights of the artificial neural networks. To test our proposal we consider several state-of-the-art Extreme Learning Machine (ELM) algorithms and we confront them using a wide and well-known set of continuous, regression and classification problems. From the conducted experiments it is proved that the µG2-ELM shows a better general performance than the previous version and also than other competitors. Therefore, we can guess that the combination of evolutionary algorithms with the ELM methodology is a promising subject of study since both together allow for the design of better training algorithms for artificial neural networks.
Zaguán. Repositorio Digital de la Universidad de Zaragoza
Publication Artículo científico (JournalArticle)

The energy-constrained quickest path problem

  • Calvete, Herminia I.
  • Pozo, Lourdes del
  • Iranzo, José A.
This paper addresses a variant of the quickest path problem in which each arc has an additional parameter associated to it representing the energy consumed during the transmission along the arc while each node is endowed with a limited power to transmit messages. The aim of the energy-constrained quickest path problem is to obtain a quickest path whose nodes are able to support the transmission of a message of a known size. After introducing the problem and proving the main theoretical results, a polynomial algorithm is proposed to solve the problem based on computing shortest paths in a sequence of subnetworks of the original network. In the second part of the paper, the bi-objective variant of this problem is considered in which the objectives are the transmission time and the total energy used. An exact algorithm is proposed to find a complete set of efficient paths. The computational experiments carried out show the performance of both algorithms.
Zaguán. Repositorio Digital de la Universidad de Zaragoza
Publication Artículo científico (JournalArticle)

Polynomially solvable cases of the bipartite traveling salesman problem

  • García, A.
  • Tejel, J.
Given two sets, R and B, consisting of n cities each, in the bipartite traveling salesman problem one looks for the shortest way of visiting alternately the cities of R and B, returning to the city of origin. This problem is known to be NP-hard for arbitrary sets R and B. In this paper we provide an O(n6) algorithm to solve the bipartite traveling salesman problem if the quadrangle property holds. In particular, this algorithm can be applied to solve in O(n6) time the bipartite traveling salesman problem in the following cases: S=R¿B is a convex point set in the plane, S=R¿B is the set of vertices of a simple polygon and V=R¿B is the set of vertices of a circular graph. For this last case, we also describe another algorithm which runs in O(n2) time.
Zaguán. Repositorio Digital de la Universidad de Zaragoza
Publication Artículo científico (JournalArticle)

Graph-based solution batch management for Multi-Objective Evolutionary Algorithms

  • Mateo, P.M.
  • Alberto, I.
In Alberto and Mateo [2], 2004, a graph-based structure used for manipulating populations of Multi-Objective Evolutionary Algorithms in a more efficient way than the structures existing at that point was defined. In this paper, an improvement of such tool is presented. It consists of the simultaneous insertion of a set of solutions (solution batch), instead of a single one, into the created graph structure. Furthermore, two experiments devoted to comparing the behavior of the new algorithms with the original version from Alberto and Mateo [2] and with a well-known non-dominated sorting algorithm are carried out. The first shows how the new version outperforms the original one in time and number of Pareto comparisons. The second experiment shows a reduction in the time needed in all the cases and an important reduction in the number of Pareto comparisons when inserting chains of dominated solutions. From these experiments it is verified that, in general, the new proposals save computational time and, in the majority of the cases, the number of Pareto comparisons carried out for the insertion. In addition, when the new proposals outperform the others, they increase their gain over them as the size of the population and/or the size of the batch increases. The new tool can also be used, for example, in parallel genetic algorithms such as the ones based on islands, to carry out the migrations of the solutions.
Zaguán. Repositorio Digital de la Universidad de Zaragoza
Publication Artículo científico (JournalArticle)

Colored ray configurations

  • Fabila-Monroy, R.
  • García, A.
  • Hurtado, F.
  • Jaume, R.
  • Pérez-Lantero, P.
  • Saumell, M.
  • Silveira, R.I.
  • Tejel, J.
  • Urrutia, J.
We study the cyclic color sequences induced at infinity by colored rays with apices being a given balanced finite bichromatic point set. We first study the case in which the rays are required to be pairwise disjoint. We derive a lower bound on the number of color sequences that can be realized from any such fixed point set and examine color sequences that can be realized regardless of the point set, exhibiting negative examples as well. We also provide a tight upper bound on the number of configurations that can be realized from a point set, and point sets for which there are asymptotically less configurations than that number. In addition, we provide algorithms to decide whether a color sequence is realizable from a given point set in a line or in general position. We address afterwards the variant of the problem where the rays are allowed to intersect. We prove that for some configurations and point sets, the number of ray crossings must be T(n2) and study then configurations that can be realized by rays that pairwise cross. We show that there are point sets for which the number of configurations that can be realized by pairwise-crossing rays is asymptotically smaller than the number of configurations realizable by pairwise-disjoint rays. We provide also point sets from which any configuration can be realized by pairwise-crossing rays and show that there is no configuration that can be realized by pairwise-crossing rays from every point set.
Zaguán. Repositorio Digital de la Universidad de Zaragoza
Publication Artículo científico (JournalArticle)

On Hamiltonian alternating cycles and paths

  • Claverol, Mercè
  • García, Alfredo
  • Garijo, Delia
  • Seara, Carlos
  • Tejel, Javier
We undertake a study on computing Hamiltonian alternating cycles and paths on bicolored point sets. This has been an intensively studied problem, not always with a solution, when the paths and cycles are also required to be plane. In this paper, we relax the constraint on the cycles and paths from being plane to being 1-plane, and deal with the same type of questions as those for the plane case, obtaining a remarkable variety of results. For point sets in general position, our main result is that it is always possible to obtain a 1-plane Hamiltonian alternating cycle. When the point set is in convex position, we prove that every Hamiltonian alternating cycle with minimum number of crossings is 1-plane, and provide O(n) and O(n2) time algorithms for computing, respectively, Hamiltonian alternating cycles and paths with minimum number of crossings.
Zaguán. Repositorio Digital de la Universidad de Zaragoza
Publication Artículo científico (JournalArticle)

Dealing with residual energy when transmitting data in energy-constrained capacitated networks

  • Calvete, H.I.
  • del-Pozo, L.
  • Iranzo, J.A.
This paper addresses several problems relating to the energy available after the transmission of a given amount of data in a capacitated network. The arcs have an associated parameter representing the energy consumed during the transmission along the arc and the nodes have limited power to transmit data. In the first part of the paper, we consider the problem of designing a path which maximizes the minimum of the residual energy remaining at the nodes. After formulating the problem and proving the main theoretical results, a polynomial time algorithm is proposed based on computing maxmin paths in a sequence of non-capacitated networks. In the second part of the paper, the problem of obtaining a quickest path in this context is analyzed. First, the bi-objective variant of this problem is considered in which we aim to minimize the transmission time and to maximize the minimum residual energy. An exact polynomial time algorithm is proposed to find a minimal complete set of efficient solutions which amounts to solving shortest path problems. Second, the problem of computing an energy-constrained quickest path which guarantees at least a given residual energy at the nodes is reformulated as a variant of the energy-constrained quickest path problem. The algorithms are tested on a set of benchmark problems providing the optimal solution or the Pareto front within reasonable computing times.