Algoritmos experimentais para o problema biobjetivo da árvore geradora quadrática em adjacência de arestas

The Quadratic Minimum Spanning Tree (QMST) problem is a generalization of the Minimum Spanning Tree problem in which, beyond linear costs associated to each edge, quadratic costs associated to each pair of edges must be considered. The quadratic costs are due to interaction costs between the edges. When interactions occur between adjacent edges only, the problem is named Adjacent Only Quadratic Minimum Spanning Tree (AQMST). Both QMST and AQMST are NP-hard and model a number of real world applications involving infrastructure networks design. Linear and quadratic costs are summed in the mono-objective versions of the problems. However, real world applications often deal with conflicting objectives. In those cases, considering linear and quadratic costs separately is more appropriate and multi-objective optimization provides a more realistic modelling. Exact and heuristic algorithms are investigated in this work for the Bi-objective Adjacent Only Quadratic Spanning Tree Problem. The following techniques are proposed: backtracking, branch-and-bound, Pareto Local Search, Greedy Randomized Adaptive Search Procedure, Simulated Annealing, NSGA-II, Transgenetic Algorithm, Particle Swarm Optimization and a hybridization of the Transgenetic Algorithm with the MOEA-D technique. Pareto compliant quality indicators are used to compare the algorithms on a set of benchmark instances proposed in literature.

Cogestion des ressources naturelles : une approche structurale pour quantifier la contribution des réseaux d'acteurs à la résilience des systèmes socio-écologiques

Alors que les activités anthropiques font basculer de nombreux écosystèmes vers des régimes fonctionnels différents, la résilience des systèmes socio-écologiques devient un problème pressant. Des acteurs locaux, impliqués dans une grande diversité de groupes — allant d’initiatives locales et indépendantes à de grandes institutions formelles — peuvent agir sur ces questions en collaborant au développement, à la promotion ou à l’implantation de pratiques plus en accord avec ce que l’environnement peut fournir. De ces collaborations répétées émergent des réseaux complexes, et il a été montré que la topologie de ces réseaux peut améliorer la résilience des systèmes socio-écologiques (SSÉ) auxquels ils participent. La topologie des réseaux d’acteurs favorisant la résilience de leur SSÉ est caractérisée par une combinaison de plusieurs facteurs : la structure doit être modulaire afin d’aider les différents groupes à développer et proposer des solutions à la fois plus innovantes (en réduisant l’homogénéisation du réseau), et plus proches de leurs intérêts propres ; elle doit être bien connectée et facilement synchronisable afin de faciliter les consensus, d’augmenter le capital social, ainsi que la capacité d’apprentissage ; enfin, elle doit être robuste, afin d’éviter que les deux premières caractéristiques ne souffrent du retrait volontaire ou de la mise à l’écart de certains acteurs. Ces caractéristiques, qui sont relativement intuitives à la fois conceptuellement et dans leur application mathématique, sont souvent employées séparément pour analyser les qualités structurales de réseaux d’acteurs empiriques. Cependant, certaines sont, par nature, incompatibles entre elles. Par exemple, le degré de modularité d’un réseau ne peut pas augmenter au même rythme que sa connectivité, et cette dernière ne peut pas être améliorée tout en améliorant sa robustesse. Cet obstacle rend difficile la création d’une mesure globale, car le niveau auquel le réseau des acteurs contribue à améliorer la résilience du SSÉ ne peut pas être la simple addition des caractéristiques citées, mais plutôt le résultat d’un compromis subtil entre celles-ci. Le travail présenté ici a pour objectifs (1), d’explorer les compromis entre ces caractéristiques ; (2) de proposer une mesure du degré auquel un réseau empirique d’acteurs contribue à la résilience de son SSÉ ; et (3) d’analyser un réseau empirique à la lumière, entre autres, de ces qualités structurales. Cette thèse s’articule autour d’une introduction et de quatre chapitres numérotés de 2 à 5. Le chapitre 2 est une revue de la littérature sur la résilience des SSÉ. Il identifie une série de caractéristiques structurales (ainsi que les mesures de réseaux qui leur correspondent) liées à l’amélioration de la résilience dans les SSÉ. Le chapitre 3 est une étude de cas sur la péninsule d’Eyre, une région rurale d’Australie-Méridionale où l’occupation du sol, ainsi que les changements climatiques, contribuent à l’érosion de la biodiversité. Pour cette étude de cas, des travaux de terrain ont été effectués en 2010 et 2011 durant lesquels une série d’entrevues a permis de créer une liste des acteurs de la cogestion de la biodiversité sur la péninsule. Les données collectées ont été utilisées pour le développement d’un questionnaire en ligne permettant de documenter les interactions entre ces acteurs. Ces deux étapes ont permis la reconstitution d’un réseau pondéré et dirigé de 129 acteurs individuels et 1180 relations. Le chapitre 4 décrit une méthodologie pour mesurer le degré auquel un réseau d’acteurs participe à la résilience du SSÉ dans lequel il est inclus. La méthode s’articule en deux étapes : premièrement, un algorithme d’optimisation (recuit simulé) est utilisé pour fabriquer un archétype semi-aléatoire correspondant à un compromis entre des niveaux élevés de modularité, de connectivité et de robustesse. Deuxièmement, un réseau empirique (comme celui de la péninsule d’Eyre) est comparé au réseau archétypique par le biais d’une mesure de distance structurelle. Plus la distance est courte, et plus le réseau empirique est proche de sa configuration optimale. La cinquième et dernier chapitre est une amélioration de l’algorithme de recuit simulé utilisé dans le chapitre 4. Comme il est d’usage pour ce genre d’algorithmes, le recuit simulé utilisé projetait les dimensions du problème multiobjectif dans une seule dimension (sous la forme d’une moyenne pondérée). Si cette technique donne de très bons résultats ponctuellement, elle n’autorise la production que d’une seule solution parmi la multitude de compromis possibles entre les différents objectifs. Afin de mieux explorer ces compromis, nous proposons un algorithme de recuit simulé multiobjectifs qui, plutôt que d’optimiser une seule solution, optimise une surface multidimensionnelle de solutions. Cette étude, qui se concentre sur la partie sociale des systèmes socio-écologiques, améliore notre compréhension des structures actorielles qui contribuent à la résilience des SSÉ. Elle montre que si certaines caractéristiques profitables à la résilience sont incompatibles (modularité et connectivité, ou — dans une moindre mesure — connectivité et robustesse), d’autres sont plus facilement conciliables (connectivité et synchronisabilité, ou — dans une moindre mesure — modularité et robustesse). Elle fournit également une méthode intuitive pour mesurer quantitativement des réseaux d’acteurs empiriques, et ouvre ainsi la voie vers, par exemple, des comparaisons d’études de cas, ou des suivis — dans le temps — de réseaux d’acteurs. De plus, cette thèse inclut une étude de cas qui fait la lumière sur l’importance de certains groupes institutionnels pour la coordination des collaborations et des échanges de connaissances entre des acteurs aux intérêts potentiellement divergents.

'Artificial Immune Systems: A new Decision Making Paradigm for Operational Research'

Over the last few years, more and more heuristic decision making techniques have been inspired by nature, e.g. evolutionary algorithms, ant colony optimisation and simulated annealing. More recently, a novel computational intelligence technique inspired by immunology has emerged, called Artificial Immune Systems (AIS). This immune system inspired technique has already been useful in solving some computational problems. In this keynote, we will very briefly describe the immune system metaphors that are relevant to AIS. We will then give some illustrative real-world problems suitable for AIS use and show a step-by-step algorithm walkthrough. A comparison of AIS to other well-known algorithms and areas for future work will round this keynote off. It should be noted that as AIS is still a young and evolving field, there is not yet a fixed algorithm template and hence actual implementations might differ somewhat from the examples given here

Investigating a Hybrid Metaheuristic For Job Shop Rescheduling

Previous research has shown that artificial immune systems can be used to produce robust schedules in a manufacturing environment. The main goal is to develop building blocks (antibodies) of partial schedules that can be used to construct backup solutions (antigens) when disturbances occur during production. The building blocks are created based upon underpinning ideas from artificial immune systems and evolved using a genetic algorithm (Phase I). Each partial schedule (antibody) is assigned a fitness value and the best partial schedules are selected to be converted into complete schedules (antigens). We further investigate whether simulated annealing and the great deluge algorithm can improve the results when hybridised with our artificial immune system (Phase II). We use ten fixed solutions as our target and measure how well we cover these specific scenarios.

A New Paradigm for Heuristic Decision Making, Invited Keynote Talk

Over the last few years, more and more heuristic decision making techniques have been inspired by nature, e.g. evolutionary algorithms, ant colony optimisation and simulated annealing. More recently, a novel computational intelligence technique inspired by immunology has emerged, called Artificial Immune Systems (AIS). This immune system inspired technique has already been useful in solving some computational problems. In this keynote, we will very briefly describe the immune system metaphors that are relevant to AIS. We will then give some illustrative real-world problems suitable for AIS use and show a step-by-step algorithm walkthrough. A comparison of AIS to other well-known algorithms and areas for future work will round this keynote off. It should be noted that as AIS is still a young and evolving field, there is not yet a fixed algorithm template and hence actual implementations might differ somewhat from the examples given here.

Cogestion des ressources naturelles : une approche structurale pour quantifier la contribution des réseaux d'acteurs à la résilience des systèmes socio-écologiques

Alors que les activités anthropiques font basculer de nombreux écosystèmes vers des régimes fonctionnels différents, la résilience des systèmes socio-écologiques devient un problème pressant. Des acteurs locaux, impliqués dans une grande diversité de groupes — allant d’initiatives locales et indépendantes à de grandes institutions formelles — peuvent agir sur ces questions en collaborant au développement, à la promotion ou à l’implantation de pratiques plus en accord avec ce que l’environnement peut fournir. De ces collaborations répétées émergent des réseaux complexes, et il a été montré que la topologie de ces réseaux peut améliorer la résilience des systèmes socio-écologiques (SSÉ) auxquels ils participent. La topologie des réseaux d’acteurs favorisant la résilience de leur SSÉ est caractérisée par une combinaison de plusieurs facteurs : la structure doit être modulaire afin d’aider les différents groupes à développer et proposer des solutions à la fois plus innovantes (en réduisant l’homogénéisation du réseau), et plus proches de leurs intérêts propres ; elle doit être bien connectée et facilement synchronisable afin de faciliter les consensus, d’augmenter le capital social, ainsi que la capacité d’apprentissage ; enfin, elle doit être robuste, afin d’éviter que les deux premières caractéristiques ne souffrent du retrait volontaire ou de la mise à l’écart de certains acteurs. Ces caractéristiques, qui sont relativement intuitives à la fois conceptuellement et dans leur application mathématique, sont souvent employées séparément pour analyser les qualités structurales de réseaux d’acteurs empiriques. Cependant, certaines sont, par nature, incompatibles entre elles. Par exemple, le degré de modularité d’un réseau ne peut pas augmenter au même rythme que sa connectivité, et cette dernière ne peut pas être améliorée tout en améliorant sa robustesse. Cet obstacle rend difficile la création d’une mesure globale, car le niveau auquel le réseau des acteurs contribue à améliorer la résilience du SSÉ ne peut pas être la simple addition des caractéristiques citées, mais plutôt le résultat d’un compromis subtil entre celles-ci. Le travail présenté ici a pour objectifs (1), d’explorer les compromis entre ces caractéristiques ; (2) de proposer une mesure du degré auquel un réseau empirique d’acteurs contribue à la résilience de son SSÉ ; et (3) d’analyser un réseau empirique à la lumière, entre autres, de ces qualités structurales. Cette thèse s’articule autour d’une introduction et de quatre chapitres numérotés de 2 à 5. Le chapitre 2 est une revue de la littérature sur la résilience des SSÉ. Il identifie une série de caractéristiques structurales (ainsi que les mesures de réseaux qui leur correspondent) liées à l’amélioration de la résilience dans les SSÉ. Le chapitre 3 est une étude de cas sur la péninsule d’Eyre, une région rurale d’Australie-Méridionale où l’occupation du sol, ainsi que les changements climatiques, contribuent à l’érosion de la biodiversité. Pour cette étude de cas, des travaux de terrain ont été effectués en 2010 et 2011 durant lesquels une série d’entrevues a permis de créer une liste des acteurs de la cogestion de la biodiversité sur la péninsule. Les données collectées ont été utilisées pour le développement d’un questionnaire en ligne permettant de documenter les interactions entre ces acteurs. Ces deux étapes ont permis la reconstitution d’un réseau pondéré et dirigé de 129 acteurs individuels et 1180 relations. Le chapitre 4 décrit une méthodologie pour mesurer le degré auquel un réseau d’acteurs participe à la résilience du SSÉ dans lequel il est inclus. La méthode s’articule en deux étapes : premièrement, un algorithme d’optimisation (recuit simulé) est utilisé pour fabriquer un archétype semi-aléatoire correspondant à un compromis entre des niveaux élevés de modularité, de connectivité et de robustesse. Deuxièmement, un réseau empirique (comme celui de la péninsule d’Eyre) est comparé au réseau archétypique par le biais d’une mesure de distance structurelle. Plus la distance est courte, et plus le réseau empirique est proche de sa configuration optimale. La cinquième et dernier chapitre est une amélioration de l’algorithme de recuit simulé utilisé dans le chapitre 4. Comme il est d’usage pour ce genre d’algorithmes, le recuit simulé utilisé projetait les dimensions du problème multiobjectif dans une seule dimension (sous la forme d’une moyenne pondérée). Si cette technique donne de très bons résultats ponctuellement, elle n’autorise la production que d’une seule solution parmi la multitude de compromis possibles entre les différents objectifs. Afin de mieux explorer ces compromis, nous proposons un algorithme de recuit simulé multiobjectifs qui, plutôt que d’optimiser une seule solution, optimise une surface multidimensionnelle de solutions. Cette étude, qui se concentre sur la partie sociale des systèmes socio-écologiques, améliore notre compréhension des structures actorielles qui contribuent à la résilience des SSÉ. Elle montre que si certaines caractéristiques profitables à la résilience sont incompatibles (modularité et connectivité, ou — dans une moindre mesure — connectivité et robustesse), d’autres sont plus facilement conciliables (connectivité et synchronisabilité, ou — dans une moindre mesure — modularité et robustesse). Elle fournit également une méthode intuitive pour mesurer quantitativement des réseaux d’acteurs empiriques, et ouvre ainsi la voie vers, par exemple, des comparaisons d’études de cas, ou des suivis — dans le temps — de réseaux d’acteurs. De plus, cette thèse inclut une étude de cas qui fait la lumière sur l’importance de certains groupes institutionnels pour la coordination des collaborations et des échanges de connaissances entre des acteurs aux intérêts potentiellement divergents.

Tabu search for the cyclic bandwidth problem

International audience

Vehicle routing and location routing problems with minimum latency: algorithms and models

Latency can be defined as the sum of the arrival times at the customers. Minimum latency problems are specially relevant in applications related to humanitarian logistics. This thesis presents algorithms for solving a family of vehicle routing problems with minimum latency. First the latency location routing problem (LLRP) is considered. It consists of determining the subset of depots to be opened, and the routes that a set of homogeneous capacitated vehicles must perform in order to visit a set of customers such that the sum of the demands of the customers assigned to each vehicle does not exceed the capacity of the vehicle. For solving this problem three metaheuristic algorithms combining simulated annealing and variable neighborhood descent, and an iterated local search (ILS) algorithm, are proposed. Furthermore, the multi-depot cumulative capacitated vehicle routing problem (MDCCVRP) and the multi-depot k-traveling repairman problem (MDk-TRP) are solved with the proposed ILS algorithm. The MDCCVRP is a special case of the LLRP in which all the depots can be opened, and the MDk-TRP is a special case of the MDCCVRP in which the capacity constraints are relaxed. Finally, a LLRP with stochastic travel times is studied. A two-stage stochastic programming model and a variable neighborhood search algorithm are proposed for solving the problem. Furthermore a sampling method is developed for tackling instances with an infinite number of scenarios. Extensive computational experiments show that the proposed methods are effective for solving the problems under study.

Hybrid Algorithms for Routing and Assignment Wavelengths in Optical Networks

This paper presents a strategy for the solution of the WDM optical networks planning. Specifically, the problem of Routing and Wavelength Allocation (RWA) in order to minimize the amount of wavelengths used. In this case, the problem is known as the Min-RWA. Two meta-heuristics (Tabu Search and Simulated Annealing) are applied to take solutions of good quality and high performance. The key point is the degradation of the maximum load on the virtual links in favor of minimization of number of wavelengths used; the objective is to find a good compromise between the metrics of virtual topology (load in Gb/s) and of the physical topology (quantity of wavelengths). The simulations suggest good results when compared to some existing in the literature.

Solution structure of methionine-oxidized amyloid beta-peptide (1-40). Does oxidation affect conformational switching?

The solution structure of A beta(1-40)Met(O), the methionine-oxidized form of amyloid beta-peptide A beta(1-40), has been investigated by CD and NMR spectroscopy. Oxidation of Met35 may have implications in the aetiology of Alzheimer's disease. Circular dichroism experiments showed that whereas A beta(1-40) and A beta(1-40)Met(O) both adopt essentially random coil structures in water (pH 4) at micromolar concentrations, the former aggregates within several days while the latter is stable for at least 7 days under these conditions. This remarkable difference led us to determine the solution structure of A beta(1-40)Met(O) using H-1 NMR spectroscopy. In a water-SDS micelle medium needed to solubilize both peptides at the millimolar concentrations required to measure NMR spectra, chemical shift and NOE data for A beta(1-40)Met(O) strongly suggest the presence of a helical region between residues 16 and 24. This is supported by slow H-D exchange of amide protons in this region and by structure calculations using simulated annealing with the program XPLOR. The remainder of the structure is relatively disordered. Our previously reported NMR data for A beta(1-40) in the same solvent shows that helices are present over residues 15-24 (helix 1) and 28-36 (helix 2), Oxidation of Met35 thus causes a local and selective disruption of helix 2. In addition to this helix-coil rearrangement in aqueous micelles, the CD data show that oxidation inhibits a coil-to-beta-sheet transition in water. These significant structural rearrangements in the C-terminal region of A beta may be important clues to the chemistry and biology of A beta(1-40) and A beta(1-42).

Three-dimensional solution structure of alpha-conotoxin MII by NMR spectroscopy: Effects of solution environment on helicity

alpha-Conotoxin MII, a 16-residue polypeptide from the venom of the piscivorous cone snail Conus magus, is a potent and highly specific blocker of mammalian neuronal nicotinic acetylcholine receptors composed of alpha 3 beta 2 subunits. The role of this receptor type in the modulation of neurotransmitter release and its relevance to the problems of addiction and psychosis emphasize the importance of a structural understanding of the mode of interaction of MII with the alpha 3 beta 2 interface. Here we describe the three-dimensional solution structure of MIT determined using 2D H-1 NMR spectroscopy. Structural restraints consisting of 376 interproton distances inferred from NOEs and 12 dihedral restraints derived from spin-spin coupling constants were used as input for simulated annealing calculations and energy minimization in the program X-PLOR. The final set of 20 structures is exceptionally well-defined with mean pairwise rms differences over the whole molecule of 0.07 Angstrom for the backbone atoms and 0.34 Angstrom for all heavy atoms. MII adopts a compact structure incorporating a central segment of alpha-helix and beta-turns at the N- and C-termini. The molecule is stabilized by two disulfide bonds, which provide cross-links between the N-terminus and both the middle and C-terminus of the structure. The susceptibility of the structure to conformational change was examined using several different solvent conditions. While the global fold of MII remains the same, the structure is stabilized in a more hydrophobic environment provided by the addition of acetonitrile or trifluoroethanol to the aqueous solution. The distribution of amino acid side chains in MII creates distinct hydrophobic and polar patches on its surface that may be important for the specific interaction with the alpha 3 beta 2 neuronal nAChR. A comparison of the structure of MII with other neuronal-specific alpha-conotoxins provides insights into their mode of interaction with these receptors.

Role of the 6-20 disulfide bridge in the structure and activity of epidermal growth factor

Two synthetic analogues of murine epidermal. growth factor, [Abu6, 20] mEGF4-48 (where Abu denotes amino-butyric acid) and [G1, M3, K21, H40] mEGF1-48, have been investigated by NMR spectroscopy. [Abu6, 20] mEGF4-48 was designed to determine the contribution of the 6-20 disulfide bridge to the structure and function of mEGF The overall structure of this analogue was similar to that of native mEGF, indicating that the loss of the 6-20 disulfide bridge did not affect the global fold of the molecule. Significant structural differences were observed near the N-terminus, however, with the direction of the polypeptide chain between residues four and nine being altered such that these residues were now located on the opposite face of the main beta-sheet from their position in native mEGF Thermal denaturation experiments also showed that the structure of [Abu6, 20] mEGF4-48 was less stable than that of mEGF. Removal of this disulfide bridge resulted in a significant loss of both mitogenic activity in Balb/c 3T3 cells and receptor binding on A431 cells compared with native mEGF and mEGF4-48, implying that the structural changes in [Abu6, 20] mEGF4-48, although limited to the N-terminus, were sufficient to interfere with receptor binding. The loss of binding affinity probably arose mainly from steric interactions of the dislocated N-terminal region with part of the receptor binding surface of EGF [G1, M3, K21, H40] mEGF1-48 was also synthesized in order to compare the synthetic polypeptide with the corresponding product of recombinant expression. Its mitogenic activity in Balb/c 3T3 cells was similar to that of native mEGF and analysis of its H-1 chemical shifts suggested that its structure was also very similar to native.

CXTANNEAL: an improved program for estimating solute transport parameters

CXTANNEAL is a program for analysing contaminant transport in soils. The code, written in Fortran 77, is a modified version of CXTFIT, a commonly used package for estimating solute transport parameters in soils. The improvement of the present code is that it includes simulated annealing as the optimization technique for curve fitting. Tests with hypothetical data show that CXTANNEAL performs better than the original code in searching for optimal parameter estimates. To reduce the computational time, a parallel version of CXTANNEAL (CXTANNEAL_P) was also developed. (C) 1999 Elsevier Science Ltd. All rights reserved.

MiAMP1, a novel protein from Macadamia integrifolia adopts a Greek key beta-barrel fold unique amongst plant antimicrobial proteins

MiAMP1 is a recently discovered 76 amino acid residue, highly basic protein from the nut kernel of:Macadamia integrifolia which possesses no sequence homology to any known protein and inhibits the growth of several microbial plant pathogens in vitro while having no effect on mammalian or plant cells. It is considered to be a potentially useful tool for the genetic engineering of disease resistance in transgenic crop plants and for the design of new fungicides. The three-dimensional structure of MiAMP1 was determined through homonuclear and heteronuclear (N-15) 2D NMR spectroscopy and subsequent simulated annealing calculations with the ultimate aim of understanding the structure-activity relationships of the protein. MiAMP1 is made up of eight beta-strands which are arranged in two Greek key motifs. These Greek key motifs associate to form a Greek key beta-barrel. This structure is unique amongst plant antimicrobial proteins and forms a new class which we term the beta-barrelins. Interestingly, the structure of MiAMP1 bears remarkable similarity to a yeast killer toxin from Williopsis mrakii. This toxin acts by inhibiting beta-glucan synthesis and thereby cell wall construction in sensitive strains of yeast. The structural similarity of MiAMP1 and WmKT, which originate from plant and fungal phyla respectively, may reflect a similar mode of action. (C) 1999 Academic Press.

Three-dimensional structure of RK-1: A novel alpha-defensin peptide

NMR spectroscopy and simulated annealing calculations have been used to determine the three-dimensional structure of RK-1, an antimicrobial peptide from rabbit kidney recently discovered from homology screening based on the distinctive physicochemical properties of the corticostatins/defensins. RK-1 consists of 32 residues, including six cysteines arranged into three disulfide bonds. It exhibits antimicrobial activity against Escherichia coli and activates Ca2+ channels in vitro. Through its physicochemical similarity, identical cysteine spacing, and linkage to the corticostatins/defensins, it was presumed to be a member of this family. However, RK-1 lacks both a large number of arginines in the primary sequence and a high overall positive charge, which are characteristic of this family of peptides. The three-dimensional solution structure, determined by NMR, consists of a triple-stranded antiparallel beta -sheet and a series of turns and is similar to the known structures of other alpha -defensins. This has enabled the definitive classification of RK-1 as a member of this family of antimicrobial peptides. Ultracentrifuge measurements confirmed that like rabbit neutrophil defensins, RK-1 is monomeric in solution, in contrast to human neutrophil defensins, which are dimeric.