Untitled

Funder

Organizational Unit

Publications

A hybrid shuffled frog-leaping algorithm for the university examination timetabling problem

Publication . Leite, Nuno; Melicio, Fernando; Rosa, Agostinho C.

The problem of examination timetabling is studied in this work. We propose a hybrid solution heuristic based on the Shuffled Frog-Leaping Algorithm (SFLA) for minimising the conflicts in the students's exams. The hybrid algorithm, named Hybrid SFLA (HSFLA), improves a population of frogs (solutions) by iteratively optimising each memeplex, and then shuffling the memeplexes in order to distribute the best performing frogs by the memeplexes. In each iteration the frogs are improved based on three operators: crossover and mutation operators, and a local search operator based on the Simulated Annealing metaheuristic. For the mutation and local search, we use two well known neighbourhood structures. The performance of the proposed method is evaluated on the 13 instances of the Toronto datasets from the literature. Computational results show that the HSFLA is competitive with state-of-the-art methods, obtaining the best results on average in seven of the 13 instances.

2016Conference object

Restricted access

On the analytical solutions of the Hindmarsh-Rose neuronal model

Publication . Duarte, Jorge; Januário, Cristina; Martins, Nuno

In this article we analytically solve the Hindmarsh-Rose model (Proc R Soc Lond B221:87-102, 1984) by means of a technique developed for strongly nonlinear problems-the step homotopy analysis method. This analytical algorithm, based on a modification of the standard homotopy analysis method, allows us to obtain a one-parameter family of explicit series solutions for the studied neuronal model. The Hindmarsh-Rose system represents a paradigmatic example of models developed to qualitatively reproduce the electrical activity of cell membranes. By using the homotopy solutions, we investigate the dynamical effect of two chosen biologically meaningful bifurcation parameters: the injected current I and the parameter r, representing the ratio of time scales between spiking (fast dynamics) and resting (slow dynamics). The auxiliary parameter involved in the analytical method provides us with an elegant way to ensure convergent series solutions of the neuronal model. Our analytical results are found to be in excellent agreement with the numerical simulations.

2015-11Journal article

Restricted access

Spectral invariants of periodic nonautonomous discrete dynamical systems

Publication . Alves, João Ferreira; Málek, Michal; Silva, Luís

For an interval map, the poles of the Artin-Mazur zeta function provide topological invariants which are closely connected to topological entropy. It is known that for a time-periodic nonautonomous dynamical system F with period p, the p-th power [zeta(F) (z)](p) of its zeta function is meromorphic in the unit disk. Unlike in the autonomous case, where the zeta function zeta(f)(z) only has poles in the unit disk, in the p-periodic nonautonomous case [zeta(F)(z)](p) may have zeros. In this paper we introduce the concept of spectral invariants of p-periodic nonautonomous discrete dynamical systems and study the role played by the zeros of [zeta(F)(z)](p) in this context. As we will see, these zeros play an important role in the spectral classification of these systems.

2015-10-01Journal article

Restricted access

A fast simulated annealing algorithm for the examination timetabling problem

Publication . Leite, Nuno; Melicio, Fernando; Rosa, Agostinho

The timetabling problem involves the scheduling of a set of entities (e.g., lectures, exams, vehicles, or people) to a set of resources in a limited number of time slots, while satisfying a set of constraints. In this paper, a new variant of the simulated annealing (SA) algorithm, named FastSA, is proposed for solving the examination timetabling problem. In the FastSA's acceptance criterion, each exam selected for scheduling is only moved (and the associated move is evaluated) if that exam had any accepted moves in the immediately preceding temperature bin. Ten temperature bins were formed, ensuring that an equal number of evaluations is performed by the FastSA, in each bin. It was observed empirically that if an exam had zero accepted movements in the preceding temperature bin, it is likely to have few or zero accepted movements in the future, as it is becoming crystallised. Hence, the moves of all exams that are fixed along the way are not evaluated no more, yielding a lower number of evaluations compared to the reference algorithm, the standard SA. A saturation degree-based heuristic, coupled with Conflict-Based Statistics in order to avoid any exam assignment looping effect, is used to construct the initial solution. The proposed FastSA and the standard SA approaches were tested on the 2nd International Timetabling Competition (ITC 2007) benchmark set. Compared to the SA, the FastSA uses 17% less evaluations, on average, and a maximum of 41% less evaluations on one instance. In terms of solution cost, the FastSA is competitive with the SA algorithm attaining the best average fitness value in four out of twelve instances, while requiring less time to execute. In terms of average comparison with the state-of-the-art approaches, the FastSA improves on one out of twelve instances, and ranks third among the five best algorithms. The article's main impact comprises the points: (i) proposal of a new algorithm (FastSA) which is able to attain a reduced computation time (and number of evaluations computed) compared to the standard SA, (ii) demonstration of the FastSA capabilities on a NP-Complete timetabling problem, (iii) comparison with state-of-the-art approaches where the FastSA is able to improve the best known result on a benchmark instance. Due to the variety of problems solved by expert and intelligent systems using SA-based algorithms, we believe that the proposed approach will open new research paths with the creation of new algorithms that explore the space in a more efficient way.

2019-05-15Journal article

Restricted access

A cellular memetic algorithm for the examination timetabling problem

Publication . Leite, Nuno; Fernandes, Carlos M.; Melicio, Fernando; Rosa, Agostinho

The timetabling problem involves the scheduling of a set of entities (e.g., lectures, exams, vehicles, or people) to a given set of resources in a limited number of time slots, while satisfying a set of constraints. In this paper, a cellular memetic algorithm is proposed for solving the examination timetabling problem. Cellular evolutionary algorithms are population-based metaheuristics. They differ from non-cellular algorithms in that the population is organised in a cellular structure, providing for a smooth actualisation of the populations that contributes to improving the population diversity. The proposed cellular evolutionary algorithm is hybridised with the threshold acceptance local search metaheuristic. The implemented algorithm uses feasible genetic recombination and local search operators, thus limiting the exploration to the feasible solution space. The effect of the threshold acceptance used in the hybrid algorithm for the examination timetabling problem is studied. It is shown that a low threshold decreasing rate is needed in order to rearrange the most difficult exams in better periods, allowing for the easy set of exams to be placed in good periods as well. The approach was tested on the public Toronto and ITC 2007 benchmark sets. The proposed hybrid is able to attain four and three new upper bounds for the Toronto and ITC 2007 benchmark sets, respectively.

2018-06Journal article

Restricted access