Hybrid Variable Neighborhood HyperHeuristics for Exam Timetabling Problems

This paper presents our work on analysing the high level search within a graph based hyperheuristic. The graph based hyperheuristic solves the problem at a higher level by searching through permutations of graph heuristics rather than the actual solutions. The heuristic permutations are then used to construct the solutions. Variable Neighborhood Search, Steepest Descent, Iterated Local Search and Tabu Search are compared. An analysis of their performance within the high level search space of heuristics is also carried out. Experimental results on benchmark exam timetabling problems demonstrate the simplicity and efficiency of this hyperheuristic approach. They also indicate that the choice of the high level search methodology is not crucial and the high level search should explore the heuristic search space as widely as possible within a limited searching time. This simple and general graph based hyperheuristic may be applied to a range of timetabling and optimisation problems.

Nurse Rostering with Genetic Algorithms

In recent years genetic algorithms have emerged as a useful tool for the heuristic solution of complex discrete optimisation problems. In particular there has been considerable interest in their use in tackling problems arising in the areas of scheduling and timetabling. However, the classical genetic algorithm paradigm is not well equipped to handle constraints and successful implementations usually require some sort of modification to enable the search to exploit problem specific knowledge in order to overcome this shortcoming. This paper is concerned with the development of a family of genetic algorithms for the solution of a nurse rostering problem at a major UK hospital. The hospital is made up of wards of up to 30 nurses. Each ward has its own group of nurses whose shifts have to be scheduled on a weekly basis. In addition to fulfilling the minimum demand for staff over three daily shifts, nurses’ wishes and qualifications have to be taken into account. The schedules must also be seen to be fair, in that unpopular shifts have to be spread evenly amongst all nurses, and other restrictions, such as team nursing and special conditions for senior staff, have to be satisfied. The basis of the family of genetic algorithms is a classical genetic algorithm consisting of n-point crossover, single-bit mutation and a rank-based selection. The solution space consists of all schedules in which each nurse works the required number of shifts, but the remaining constraints, both hard and soft, are relaxed and penalised in the fitness function. The talk will start with a detailed description of the problem and the initial implementation and will go on to highlight the shortcomings of such an approach, in terms of the key element of balancing feasibility, i.e. covering the demand and work regulations, and quality, as measured by the nurses’ preferences. A series of experiments involving parameter adaptation, niching, intelligent weights, delta coding, local hill climbing, migration and special selection rules will then be outlined and it will be shown how a series of these enhancements were able to eradicate these difficulties. Results based on several months’ real data will be used to measure the impact of each modification, and to show that the final algorithm is able to compete with a tabu search approach currently employed at the hospital. The talk will conclude with some observations as to the overall quality of this approach to this and similar problems.

An Indirect Genetic Algorithm for a Nurse Scheduling Problem

This paper describes a Genetic Algorithms approach to a manpower-scheduling problem arising at a major UK hospital. Although Genetic Algorithms have been successfully used for similar problems in the past, they always had to overcome the limitations of the classical Genetic Algorithms paradigm in handling the conflict between objectives and constraints. The approach taken here is to use an indirect coding based on permutations of the nurses, and a heuristic decoder that builds schedules from these permutations. Computational experiments based on 52 weeks of live data are used to evaluate three different decoders with varying levels of intelligence, and four well-known crossover operators. Results are further enhanced by introducing a hybrid crossover operator and by making use of simple bounds to reduce the size of the solution space. The results reveal that the proposed algorithm is able to find high quality solutions and is both faster and more flexible than a recently published Tabu Search approach.

Boosting the performance of metaheuristics for the MinLA problem using a more discriminating evaluation function

International audience

Path relinking for the fixed spectrum frequency assignment problem

International audience

Ordonnancement des opérations dans une unité d’extrusion

Les travaux de ce mémoire traitent du problème d’ordonnancement et d’optimisation de la production dans un environnement de plusieurs machines en présence de contraintes sur les ressources matérielles dans une usine d’extrusion plastique. La minimisation de la somme pondérée des retards est le critère économique autour duquel s’articule cette étude car il représente un critère très important pour le respect des délais. Dans ce mémoire, nous proposons une approche exacte via une formulation mathématique capable des donner des solutions optimales et une approche heuristique qui repose sur deux méthodes de construction de solution sérielle et parallèle et un ensemble de méthodes de recherche dans le voisinage (recuit-simulé, recherche avec tabous, GRASP et algorithme génétique) avec cinq variantes de voisinages. Pour être en totale conformité avec la réalité de l’industrie du plastique, nous avons pris en considération certaines caractéristiques très fréquentes telles que les temps de changement d’outils sur les machines lorsqu’un ordre de fabrication succède à un autre sur une machine donnée. La disponibilité des extrudeuses et des matrices d’extrusion représente le goulot d’étranglement dans ce problème d’ordonnancement. Des séries d’expérimentations basées sur des problèmes tests ont été effectuées pour évaluer la qualité de la solution obtenue avec les différents algorithmes proposés. L’analyse des résultats a démontré que les méthodes de construction de solution ne sont pas suffisantes pour assurer de bons résultats et que les méthodes de recherche dans le voisinage donnent des solutions de très bonne qualité. Le choix du voisinage est important pour raffiner la qualité de la solution obtenue. Mots-clés : ordonnancement, optimisation, extrusion, formulation mathématique, heuristique, recuit-simulé, recherche avec tabous, GRASP, algorithme génétique

Network assimilation methodology and sectorization of water distribution systems by graph mining and optimization algorithm

Water Distribution Networks (WDNs) play a vital importance rule in communities, ensuring well-being band supporting economic growth and productivity. The need for greater investment requires design choices will impact on the efficiency of management in the coming decades. This thesis proposes an algorithmic approach to address two related problems:(i) identify the fundamental asset of large WDNs in terms of main infrastructure;(ii) sectorize large WDNs into isolated sectors in order to respect the minimum service to be guaranteed to users. Two methodologies have been developed to meet these objectives and subsequently they were integrated to guarantee an overall process which allows to optimize the sectorized configuration of WDN taking into account the needs to integrated in a global vision the two problems (i) and (ii). With regards to the problem (i), the methodology developed introduces the concept of primary network to give an answer with a dual approach, of connecting main nodes of WDN in terms of hydraulic infrastructures (reservoirs, tanks, pumps stations) and identifying hypothetical paths with the minimal energy losses. This primary network thus identified can be used as an initial basis to design the sectors. The sectorization problem (ii) has been faced using optimization techniques by the development of a new dedicated Tabu Search algorithm able to deal with real case studies of WDNs. For this reason, three new large WDNs models have been developed in order to test the capabilities of the algorithm on different and complex real cases. The developed methodology also allows to automatically identify the deficient parts of the primary network and dynamically includes new edges in order to support a sectorized configuration of the WDN. The application of the overall algorithm to the new real case studies and to others from literature has given applicable solutions even in specific complex situations.

BIOMedical search engine framework: lightweight and customized implementation of domain-specific biomedical search engines

The Smart Drug Search is publicly accessible at http://sing.ei.uvigo.es/sds/. The BIOMedical Search Engine Framework is freely available for non-commercial use at https://github.com/agjacome/biomsef

Antigenic community between Schistosoma mansoni and Biomphalaria glabrata: on the search of candidate antigens for vaccines

We have previously confirmed the presence of common antigens between Schistosoma mansoni and its vector, Biomphalaria glabrata. Cross-reactive antigens may be important as possible candidates for vaccine and diagnosis of schistosomiasis. Sera from outbred mice immunized with a soluble Biomphalaria glabrata antigen (SBgA) of non-infected B. glabrata snails recognized molecules of SBgA itself and S. mansoni AWA by Western blot. Recognition of several molecules of the SBgA were inhibited by pre-incubation with AWA (16, 30, 36, 60 and 155 kDa). The only specific molecule of AWA, inhibited by SBgA, was a 120 kDa protein. In order to determine which epitopes of SBgA were glycoproteins, the antigen was treated with sodium metaperiodate and compared with non-treated antigen. Molecules of 140, 60 and 24 kDa in the SBgA appear to be glycoproteins. Possible protective effects of the SBgA were evaluated immunizing outbred mice in two different experiments using Freund's Adjuvant. In the first one (12 mice/group), we obtained a significant level of protection (46%) in the total worm load, with a high variability in worm recovery. In the second experiment (22 mice/group), no significant protection was observed, neither in worm load nor in egg production per female. Our results suggest that SBgA constitutes a rich source of candidate antigens for diagnosis and prophylactic studies.

Combinatorial peptide library-based identification of peptide ligands for tumor-reactive cytolytic T lymphocytes of unknown specificity.

A novel approach for the identification of tumor antigen-derived sequences recognized by CD8(+) cytolytic T lymphocytes (CTL) consists in using synthetic combinatorial peptide libraries. Here we have screened a library composed of 3.1 x 10(11) nonapeptides arranged in a positional scanning format, in a cytotoxicity assay, to search the antigen recognized by melanoma-reactive CTL of unknown specificity. The results of this analysis enabled the identification of several optimal peptide ligands, as most of the individual nonapeptides deduced from the primary screening were efficiently recognized by the CTL. The results of the library screening were also analyzed with a mathematical approach based on a model of independent and additive contribution of individual amino acids to antigen recognition. This biometrical data analysis enabled the retrieval, in public databases, of the native antigenic peptide SSX-2(41-49), whose sequence is highly homologous to the ones deduced from the library screening, among the ones with the highest stimulatory score. These results underline the high predictive value of positional scanning synthetic combinatorial peptide library analysis and encourage its use for the identification of CTL ligands.

A heuristic method for reactive power planning

An approach for solving reactive power planning problems is presented, which is based on binary search techniques and the use of a special heuristic to obtain a discrete solution. Two versions were developed, one to run on conventional (sequential) computers and the other to run on a distributed memory (hypercube) machine. This latter parallel processing version employs an asynchronous programming model. Once the set of candidate buses has been defined, the program gives the location and size of the reactive sources needed(if any) in keeping with operating and security constraints.

Brazilian foreign policy in the Cardoso era: The search for autonomy through integration

The Fernando Henrique Cardoso administration attempted to replace a reactive foreign policy agenda dominated by a logic of autonomy through distance with a proactive international agenda guided by a logic of autonomy through integration. In adopting this agenda, the administration maintained that Brazil would be able to confront its problems and secure more control over its future if it actively contributed to elaborating the norms and guidelines of the administration of the global order. Because of structural weaknesses, however, this policy of integration, adherence, and participation was not adequately accompanied by positions entailing practical responsibilities - responsibilities that would have prepared both government and civil society for a higher profile in the post - cold-war era. In the end, the gains achieved during Cardoso's tenure failed to alter Brazil's international standing in any significant way. © 2007 Latin American Perspectives.

Identification of protein targets of nevirapine reactive metabolites using click chemistry and mass spectrometry-based differential proteomics

Abstract : Adverse drug reactions (ADRs) are undesirable effects caused after administration of a single dose or prolonged administration of drug or result from the combination of two or more drugs. Idiosyncratic drug reaction (IDR) is an adverse reaction that does not occur in most patients treated with a drug and does not involve the therapeutic effect of the drug. IDRs are unpredictable and often life-threatening. Idiosyncratic reaction is dependent on drug chemical characteristics or individual immunological response. IDRs are a major problem for drug development because they are usually not detected during clinical trials. In this study we focused on IDRs of Nevirapine (NVP), which is a non-nucleoside reverse transcriptase inhibitor used for the treatment of Human Immunodeficiency Virus (HIV) infections. The use of NVP is limited by a relatively high incidence of skin rash. NVP also causes a rash in female Brown Norway (BN) rats, which we use as animal model for this study. Our hypothesis is that idiosyncratic skin reactions associated with NVP treatment are due to post-translational modifications of proteins (e.g., glutathionylation) detectable by MS. The main objective of this study was to identify the proteins that are targeted by a reactive metabolite of Nevirapine in the skin. The specific objectives derived from the general objective were as follow: 1) To implement the click chemistry approach to detect proteins modified by a reactive NVP-Alkyne (NVP-ALK) metabolite. The purpose of using NVP-ALK was to couple it with Biotin using cycloaddition Click Chemistry reaction. 2) To detect protein modification using Western blotting and Mass Spectrometry techniques, which is important to understand the mechanism of NVP induced toxicity. 3) To identify the proteins using MASCOT search engine for protein identification, by comparing obtained spectrum from Mass Spectrometry with theoretical spectrum to find a matching peptide sequence. 4) To test if the drug or drug metabolites can cause harmful effects, as the induction of oxidative stress in cells (via protein glutathionylation). Oxidative stress causes cell damage that mediates signals, which likely induces the immune response. The results showed that Nevirapine is metabolized to a reactive metabolite, which causes protein modification. The extracted protein from the treated BN rats matched 10% of keratin, which implies that keratin was the protein targeted by the NVP-ALK.

Reactive clusters on a membrane

We investigate the reaction dynamics of diffusive molecules with immobile binding partners. The fixed reactants build clusters that comprise just a few tens of molecules, which leads to small cluster sizes. These molecules participate in the reaction only if they are activated. The dynamics of activation is mapped to a time-dependent size of an active region within the cluster. We focus on the deterministic description of the dynamics of a single cluster. The spatial setup accounts for one of the most important determinants of the dynamics of a cluster, i.e. diffusional transport of reaction partners toward or away from the active region of the cluster. We provide numerical and analytical evidence that diffusion influences decisively the dynamic regimes of the reactions. The application of our methods to intracellular Ca²⁺ dynamics shows that large local concentrations saturate the Ca²⁺ feedback to the channel state control. That eliminates oscillations depending on this feedback.