Brazil

Hyper-heuristics (HHs) are algorithms suitable for designing heuristics. HHs perform the search divided in two levels: they look for heuristic components in the high level and the heuristic is used, in the low level, to solve a set of instances of one or more problems. Different from offline HHs, hyper-heuristics with dynamic learning select or generate heuristics during the search. This paper proposes a hyper-heuristic associated with a dynamic learning strategy for selecting Iterated Greedy (IG) components. The proposal is capable of selecting appropriate values for six IG components: local search, perturbation, destruction size, neighborhood size, destruction position and local search focus. The proposed HH is tested with six dynamic adaptation strategies: random, e-greedy, probability matching, multi-armed bandit, LinUCB, and Thompson Sampling (TS). The hyper-parameters of each strategy are tuned by irace. As a testbed, we use several instances with four different sizes (20, 50, 100 and 200 jobs) of three different formulations of flowshop problems (permutation, no-wait, no-idle), two distinct objectives (makespan, flowtime), and four processing time distributions (uniform, exponential and job or machine correlated). The results show that different strategies are most suitable for adapting different IG components, TS performs quite well for all components and, except for local search, using adaptation is always beneficial when compared with the IG running with standard parameters.

BRACIS 2021

Dynamic Learning in Hyper-Heuristics to Solve Flowshop Problems

flowshop variants

adaptive components

iterated greedy algorithm

hyper-heuristic

**BRACIS** originated from the combination of the two most important scientific events in Brazil in Artificial Intelligence (AI) and Computational Intelligence (CI): the Brazilian Symposium on Artificial Intelligence – **SBIA** (22 editions), and the Brazilian Symposium on Neural Networks – **SBRN** (13 editions). **ENIAC** is a national forum for researchers, practitioners, educators and students to present and discuss innovations, trends, experiences, developments and work in progress in the fields of Artificial and Computational Intelligence. **STIL** is the bi-annual Language Technology event.
All events are supported by the Brazilian Computer Society – Special Interest Groups: **CE-IA**, **CE-IC** and **CE-PLN**.

To access the 10th Brazilian Conference on Intelligent Systems (**BRACIS**), you need to register for the conference.  Please visit the Conference official site to register

[Register now](http://c4ai.inova.usp.br/bracis2021/)

Register now

BRACIS originated from the combination of the two most important scientific events in Brazil in Artificial Intelligence (AI) and Computational Intelligence (CI): the Brazilian Symposium on Artificial Intelligence – SBIA (22 editions), and the Brazilian Symposium on Neural Networks – SBRN (13 editions). 
ENIAC is a national forum for researchers, practitioners, educators and students to present and discuss innovations, trends, experiences, developments and work in progress in the fields of Artificial and Computational Intelligence. 
STIL is the bi-annual Language Technology event.
All events are supported by the Brazilian Computer Society – Special Interest Groups: CE-IA, CE-IC and CE-PLN

technical paper

Task-oriented dialogue systems are very important due to their wide range of applications. In particular, those tasks that involve multiple domains have gained increasing attention in recent years, as the actual tasks performed by virtual assistants often span multiple domains. In this work, we propose the Divide-and-Conquer Distributed Architecture with Slot Sharing Mechanism (DCDA-S2M) system, which includes not only a distributed system aimed at managing dialogues through the pipeline architecture, but also a slot sharing mechanism that allows the system to obtain information during a conversation in one domain and reuse it in another domain, in order to avoid redundant interactions and make the dialogue more efficient. Results show that the distributed architecture outperforms the centralized one by 21.51% and that the slot sharing mechanism improves the system performance both in the success rate and in the number of turns during the dialogue, demonstrating that it can prevent the agent from requesting redundant information.

Slot Sharing Mechanism in Multi-Domain Dialogue Systems

The recent progress in Reinforcement Learning applications to Resource Management presents MDPs without a deeper analysis of the impacts of design decisions on agent performance. In this paper, we compare and contrast four different MDP formulations, discussing their computational requirements and impacts on agent performance by means of an empirical analysis. We conclude by showing that, when used with Multi-Layer Perceptrons, image-like formulations are more helpful when shorter jobs dominate in the data set, while compact formulations are more helpful when longer jobs are used, and when transfer learning is desired as well.

On the impact of MDP design for Reinforcement Learning agents in Resource Management

The coronavirus disease (COVID-19) pandemic has brought significant challenges worldwide through the consequences of increasing demand for the Intensive Care Unit (ICU) resources. This work presents the Multi-Agent System for Glycemic Control (MAS4GC) to assist health professionals leading with critical patients in the ICU. More specifically, the MAS4GC manages patients’ blood glucose through glycemic predictions, treatment, and monitoring recommendations to health professionals. Prediction models are applied to monitor patients’ blood glucose allowing health professionals to carry out preventive treatments. The glycemic control is included in the FAST HUG mnemonic to remember the key issues in the supportive care of critically ill patients. The MAS4GC methodological development process is presented with Tropos modeling, architectural design, and implementation with the PADE framework. Agents’ inference mechanisms are based on production rules defined by intensive care physician specialists applying their knowledge to indicate treatments for patients. Two experiments using patients with synthetic data were conducted to evaluate the results of the MAS4GC: (1) the prediction model achieved 90\% accuracy in blood glucose predictions for the next 4 hours, (2) 84\% similarity of treatment recommendations compared to a human specialist, and 78\% in recommendations for monitoring glycemic of critical patients.

MAS4GC: Multi-Agent System for Glycemic Control of Intensive Care Unit Patients

Stochastic Value Gradient (SVG) methods underlie many recent achievements of model-based Reinforcement Learning agents in continuous state-action spaces. Despite their practical significance, many algorithm design choices still lack rigorous theoretical or empirical justification. In this work, we analyze one such design choice: the gradient estimator formula. We conduct our analysis on randomized Linear Quadratic Gaussian environments, allowing us to empirically assess gradient estimation quality relative to the actual SVG. Our results justify a widely used gradient estimator by showing it induces a favorable bias-variance tradeoff, which could explain the lower sample complexity of recent SVG methods.

Gradient Estimation in Model-Based Reinforcement Learning: a Study on Linear Quadratic Environments

Argumentation-based persuasive negotiation is a form of negotiation dialogue in which agents, with different interests and goals, exchange proposals that are supported by rhetorical arguments such as threats, rewards, or appeals. Besides rhetorical arguments, additional kinds of illocutions may also be exchanged during the dialogue, for instance, agents may ask for explanations, give explanations, or attack (or contradict) previous arguments. This paper presents a formal protocol for argumentation-based persuasive negotiation dialogues in which a proponent agent tries to persuade his opponent to perform a given action and the opponent tries to maintain his position. The protocol is modelled as a dialogue game (i.e. the interactions between the proponent and the opponent are governed by a set of rules) and the outcome of the dialogue is determined by applying an argumentation semantics. We prove the soundness and completeness of our proposal and illustrate the proposed protocol by using an example.

A Protocol for Argumentation-based Persuasive Negotiation Dialogues

Bed allocation in hospitals is a critical and important problem, and it has become even more important since last year because of the COVID-19 pandemic. In this paper, we present an approach based on intelligent-agent technologies to assist hospital staff in charge of bed allocation. As part of this work, we developed a web-based simulation of a hospital bed allocation system integrated with a chatbot for interaction with the user. As a core component in our approach, an intelligent agent uses the feedback of a plan validator to check if there are any flaws in a user-made allocation, communicating any detected problems to the user using natural language through the chatbot. Thus, our resulting application not only validates bed allocation plans but also interacts with hospital professionals using natural language communication, including giving explainable suggestions of better alternative allocations. We evaluated our approach with professionals responsible for bed allocation in two local hospitals and a doctor who provides consultancy to another local hospital. The version of the system reported in this paper addresses all the suggestions made by the specialists who evaluated its previous version.

A Conversational Agent to Support Hospital Bed Allocation

The Quadratic Assignment Problem (QAP) can be subdivided into different versions, being present in several real-world applications. In this work, it is used a version that considers many objectives. QAP is an NP-hard problem, so approximate algorithms are used to address it. This work analyzes a Hyper-Heuristic (HH) that selects genetic operators to be applied during the evolutionary process. HH is based on the NSGA-III framework and on the Thompson Sampling approach. Our main contribution is the analysis of the use of a many objective algorithm using HH for QAP, as this problem was still under-explored in the context of many objective optimization. Furthermore, we analyze the behavior of operators forward the changes related to HH (TS). The proposal was tested considering 42 instances with 5, 7 and 10 objectives. The results, interpreted using the Friedman statistical test, were satisfactory when compared to the original algorithm (without HH), as well as when compared to algorithms in the literature: MOEA/DD, MOEA/D, SPEA2, NSGA-II and MOEA/D-DRA.

Hyper-Heuristic based NSGA-III for the Many-Objective Quadratic Assignment Problem

Particle Swarm Optimization (PSO) algorithms are swarm intelligence methods that are effective in solving optimization problems. However, current techniques have some drawbacks: the particles of some PSO implementations are sensible to their input hyper-parameters, lack direction diversity in their movement, have rotational variance, and might prematurely converge due to rapid swarm diversity loss. This article addresses these issues by introducing Rotationally Invariant Attractive and Repulsive eXpanded PSO (RI-AR-XPSO) and Rotationally Invariant Semi-Autonomous eXpanded PSO (RI-SAXPSO) as improvements of Rotationally Invariant Semi-Autonomous PSO (RI-SAPSO) and eXpanded PSO (XPSO). Their swarm behavior was evaluated with classic functions in the literature and their accuracy was tested with the Congress on Evolutionary Computation (CEC) 2017 optimization problems, in whose results a statistical significance test was applied. The results obtained attest that strategies such as diversity control, automatic hyper-parameter adjustment, directional diversity, and rotational invariance improve performance without accuracy loss when adequately implemented.

Improving particle swarm optimization with self-adaptive parameters, rotational invariance, and diversity control.

This paper presents a novel Multiobjective Genetic Algorithm, named Modied Non-Dominated Sorting Genetic Algorithm Distance Oriented (MNSGA-DO), which aims to adjust the NSGA-DO selection operator to improve its diversity when applied to continuous multiobjective optimization problems. In order to validate this new Genetic Algorithm, we carried out a performance comparison among it and the genetic algorithms NSGA-II and NSGA-DO, regarding continuous multiobjective optimization problems. To this aim, a set of standard benchmark problems, the so-called ZDT functions, was applied considering the quality indicators Generational Distance, Inverted Generational Distance and Hypervolume as well as a time evaluation. The results demonstrate that MNSGA-DO overcomes NSGA-II and NSGA-DO in almost all benchmarks, obtaining more accurate solutions and diversity.

A Modified NSGA-DO for Solving Multiobjective Optimization Problems

General and adaptive strategies have been a highly pursued goal of the optimization community, due to the domain-dependent set of configurations (operators and parameters) that is usually required for achieving high quality solutions. This work investigates a Deep Q-Network (DQN) selection strategy under an online selection Hyper-Heuristic algorithm and compares it with two state-of-the-art Multi-Armed Bandit (MAB) approaches. We conducted the experiments on all six problem domains from the HyFlex Framework. With our definition of state representation and reward scheme, the DQN was able to quickly identify the good and bad operators, which resulted on better performance than the MAB strategies on the problem instances that a more exploitative behavior deemed advantageous.


Premium content

Dynamic Learning in Hyper-Heuristics to Solve Flowshop Problems

Downloads

Next from BRACIS 2021

Slot Sharing Mechanism in Multi-Domain Dialogue Systems

Similar lecture

Online selection of heuristic operators with Deep Q-Netowrk: a study on the HyFlex Framework

Stay up to date with the latest Underline news!

PRESENTATIONS

CONFERENCES

COMPANY

RESOURCES