A Hybrid Swarm Based Approach in Addressing University Timetabling Problems

This paper is concerned with the application of an automated hybrid approach in addressing the university timetabling problem. The approach described is based on the nature-inspired artificial bee colony (ABC) algorithm. An ABC algorithm is a biologically-inspired optimization approach, which has been widely implemented in solving a range of optimization problems in recent years such as job shop scheduling and machine timetabling problems. Although the approach has proven to be robust across a range of problems, it is acknowledged within the literature that there currently exist a number of inefficiencies regarding the exploration and exploitation abilities. These inefficiencies can often lead to a slow convergence speed within the search process. Hence, this paper introduces a variant of the algorithm which utilizes a global best model inspired from particle swarm optimization to enhance the global exploration ability while hybridizing with the great deluge (GD) algorithm in order to improve the local exploitation ability. Using this approach, an effective balance between exploration and exploitation is attained. In addition, a traditional local search approach is incorporated within the GD algorithm with the aim of further enhancing the performance of the overall hybrid method. To evaluate the performance of the proposed approach, two diverse university timetabling datasets are investigated, i.e., Carter's examination timetabling and Socha course timetabling datasets. It should be noted that both problems have differing complexity and different solution landscapes. Experimental results demonstrate that the proposed method is capable of producing high quality solutions across both these benchmark problems, showing a good degree of generality in the approach. Moreover, the proposed method produces best results on some instances as compared with other approaches presented in the literature.

A new Nawaz–Enscore–Ham-based heuristic for permutation flow-shop problem with bicriteria of makespan and machine idle-time

A new heuristic based on Nawaz–Enscore–Ham (NEH) algorithm is proposed for solving permutation flowshop scheduling problem in this paper. A new priority rule is proposed by accounting for the average, mean absolute deviation, skewness and kurtosis, in order to fully describe the distribution style of processing times. A new tie-breaking rule is also introduced for achieving effective job insertion for the objective of minimizing both makespan and machine idle-time. Statistical tests illustrate better solution quality of the proposed algorithm, comparing to existing benchmark heuristics.

Optimised search heuristics: combining metaheuristics and exact methods to solve scheduling problems

Tese dout., Matemática, Investigação Operacional, Universidade do Algarve, 2009

Open-domain web-based multiple document : question answering for list questions with support for temporal restrictors

Tese de doutoramento, Informática (Ciências da Computação), Universidade de Lisboa, Faculdade de Ciências, 2015

Self-optimization module for scheduling using case-based reasoning

Metaheuristics performance is highly dependent of the respective parameters which need to be tuned. Parameter tuning may allow a larger flexibility and robustness but requires a careful initialization. The process of defining which parameters setting should be used is not obvious. The values for parameters depend mainly on the problem, the instance to be solved, the search time available to spend in solving the problem, and the required quality of solution. This paper presents a learning module proposal for an autonomous parameterization of Metaheuristics, integrated on a Multi-Agent System for the resolution of Dynamic Scheduling problems. The proposed learning module is inspired on Autonomic Computing Self-Optimization concept, defining that systems must continuously and proactively improve their performance. For the learning implementation it is used Case-based Reasoning, which uses previous similar data to solve new cases. In the use of Case-based Reasoning it is assumed that similar cases have similar solutions. After a literature review on topics used, both AutoDynAgents system and Self-Optimization module are described. Finally, a computational study is presented where the proposed module is evaluated, obtained results are compared with previous ones, some conclusions are reached, and some future work is referred. It is expected that this proposal can be a great contribution for the self-parameterization of Metaheuristics and for the resolution of scheduling problems on dynamic environments.

Multi-apprentice learning for meta-heuristics parameter tuning in a multi agent scheduling system

The scheduling problem is considered in complexity theory as a NP-hard combinatorial optimization problem. Meta-heuristics proved to be very useful in the resolution of this class of problems. However, these techniques require parameter tuning which is a very hard task to perform. A Case-based Reasoning module is proposed in order to solve the parameter tuning problem in a Multi-Agent Scheduling System. A computational study is performed in order to evaluate the proposed CBR module performance.

Meta-heuristics tunning using CBR for dynamic scheduling

This paper addresses the problem of Biological Inspired Optimization Techniques (BIT) parameterization, considering the importance of this issue in the design of BIT especially when considering real world situations, subject to external perturbations. A learning module with the objective to permit a Multi-Agent Scheduling System to automatically select a Meta-heuristic and its parameterization to use in the optimization process is proposed. For the learning process, Casebased Reasoning was used, allowing the system to learn from experience, in the resolution of similar problems. Analyzing the obtained results we conclude about the advantages of its use.

Application of different heuristic classes in memory-based and stimulus-based decisions

This paper studies the drivers of heuristic application in different decision types. The study compares differences in frequencies of heuristic classes' such as recognition, one-reason choice and trade-off applied in, respectively, memory-based and stimulus-based choices as well as in high and low involvement decisions. The study has been conducted online among 205 participants from 28 countries.

The essence of a tacit intersection : a heuristic inquiry into nature-based leisure and personal transformation

There are a considerable number of programs and agencies that count on the existence of a unique relationship between nature and human development. In addition, there are significant bodies of literature dedicated to understanding developmentally focused nature-based experiences. This research project was designed to flirther the understanding of this phenomenon. Consequently, the purpose of this research endeavour was to discover the essence ofthe intersection ofpersonal transformation and nature-based leisure, culminating in a rich and detailed account of this otherwise tacit phenomenon. As such, this research built on the assumption of this beneficial intersection of nature and personal transformation and contributes to the understanding ofhow this context is supporting or generating of selfactualization and positive development. Heuristic methods were employed because heuristics is concerned with the quality and essence of an experience, not causal relationships (Moustakas, 1990). Heuristic inquiry begins with the primary researcher and her personal experience and knowledge of the phenomenon. This study also involved four other coresearchers who had also experienced this phenomenon intensely. Co-researchers were found through purposeful and snowball sampling. Rich narrative descriptions of their experiences were gathered through in-depth, semi-structured interviews, and artifact elicitation was employed as a means to get at co-researchers' tacit knowledge. Each coresearcher was interviewed twice (the first interview focused on personal transformation, the second on nature) for approximately four and a half hours in total. Transcripts were read repeatedly to discern patterns that emerged from the study of the narratives and were coded accordingly. Individual narratives were consolidated to create a composite narrative of the experience. Finally, a creative synthesis was developed to represent the essence of this tacit experience. In conclusion the essence of the intersection of nature-based leisure and personal transformation was found to lie in the convergence of the lived experience of authenticity. The physical environment of nature was perceived and experienced to be a space and context of authenticity, leisure experiences were experienced as an engagement of authenticity, and individuals themselves encountered a true or authentic self that emanated from within. The implications of these findings are many, offering suggestions, considerations and implications from reconsidered approaches to environmental education to support for selfdirected human development.

Heuristics for the Critical Node Detection Problem in Large Complex Networks

Complex networks have recently attracted a significant amount of research attention due to their ability to model real world phenomena. One important problem often encountered is to limit diffusive processes spread over the network, for example mitigating pandemic disease or computer virus spread. A number of problem formulations have been proposed that aim to solve such problems based on desired network characteristics, such as maintaining the largest network component after node removal. The recently formulated critical node detection problem aims to remove a small subset of vertices from the network such that the residual network has minimum pairwise connectivity. Unfortunately, the problem is NP-hard and also the number of constraints is cubic in number of vertices, making very large scale problems impossible to solve with traditional mathematical programming techniques. Even many approximation algorithm strategies such as dynamic programming, evolutionary algorithms, etc. all are unusable for networks that contain thousands to millions of vertices. A computationally efficient and simple approach is required in such circumstances, but none currently exist. In this thesis, such an algorithm is proposed. The methodology is based on a depth-first search traversal of the network, and a specially designed ranking function that considers information local to each vertex. Due to the variety of network structures, a number of characteristics must be taken into consideration and combined into a single rank that measures the utility of removing each vertex. Since removing a vertex in sequential fashion impacts the network structure, an efficient post-processing algorithm is also proposed to quickly re-rank vertices. Experiments on a range of common complex network models with varying number of vertices are considered, in addition to real world networks. The proposed algorithm, DFSH, is shown to be highly competitive and often outperforms existing strategies such as Google PageRank for minimizing pairwise connectivity.

Integration of knowledge-based, qualitative and numeric tools for real time dynamic systems supervision

The proposal presented in this thesis is to provide designers of knowledge based supervisory systems of dynamic systems with a framework to facilitate their tasks avoiding interface problems among tools, data flow and management. The approach is thought to be useful to both control and process engineers in assisting their tasks. The use of AI technologies to diagnose and perform control loops and, of course, assist process supervisory tasks such as fault detection and diagnose, are in the scope of this work. Special effort has been put in integration of tools for assisting expert supervisory systems design. With this aim the experience of Computer Aided Control Systems Design (CACSD) frameworks have been analysed and used to design a Computer Aided Supervisory Systems (CASSD) framework. In this sense, some basic facilities are required to be available in this proposed framework: ·

Rich and famous: recognition-based judgment in the Sunday Times rich list

Recognition as a cue to judgment in a novel, multi-option domain (the Sunday Times Rich List) is explored. As in previous studies, participants were found to make use of name recognition as a cue to the presumed wealth of individuals. Names that were recognized were judged to be the richest name from amongst the set presented at above chance levels. This effect persisted across situations in which more than one name was recognized; recognition was used as an inclusion criterion for the sub-set of names to be considered the richest of the set presented. However, when the question was reversed, and a “poorest” judgment was required, use of recognition as an exclusion criterion was observed only when a single name was recognized. Reaction times when making these judgments also show a distinction between “richest” and “poorest” questions with recognition of none of the options taking the longest time to judge in the “richest” question condition and full recognition of all the names presented taking longest to judge in the “poorest” question condition. Implications for decision-making using simple heuristics are discussed.

Heuristic based evolution for the coordination of autonomous vehicles in the absence of speed lanes

The current state of the art in the planning and coordination of autonomous vehicles is based upon the presence of speed lanes. In a traffic scenario where there is a large diversity between vehicles the removal of speed lanes can generate a significantly higher traffic bandwidth. Vehicle navigation in such unorganized traffic is considered. An evolutionary based trajectory planning technique has the advantages of making driving efficient and safe, however it also has to surpass the hurdle of computational cost. In this paper, we propose a real time genetic algorithm with Bezier curves for trajectory planning. The main contribution is the integration of vehicle following and overtaking behaviour for general traffic as heuristics for the coordination between vehicles. The resultant coordination strategy is fast and near-optimal. As the vehicles move, uncertainties may arise which are constantly adapted to, and may even lead to either the cancellation of an overtaking procedure or the initiation of one. Higher level planning is performed by Dijkstra's algorithm which indicates the route to be followed by the vehicle in a road network. Re-planning is carried out when a road blockage or obstacle is detected. Experimental results confirm the success of the algorithm subject to optimal high and low-level planning, re-planning and overtaking.

Using decision-tree to automatically construct learned-heuristics for events classification in sports video

Automatic events classification is an essential requirement for constructing an effective sports video summary. It has become a well-known theory that the high-level semantics in sport video can be “computationally interpreted” based on the occurrences of specific audio and visual features which can be extracted automatically. State-of-the-art solutions for features-based event classification have only relied on either manual-knowledge based heuristics or machine learning. To bridge the gaps, we have successfully combined the two approaches by using learning-based heuristics. The heuristics are constructed automatically using decision tree while manual supervision is only required to check the features and highlight contained in each training segment. Thus, fully automated construction of classification system for sports video events has been achieved. A comprehensive experiment on 10 hours video dataset, with five full-match soccer and five full-match basketball videos, has demonstrated the effectiveness/robustness of our algorithms.