Befintliga studier har påvisat att genetiska algoritmer presterar bättre om de ges en bra startpopulation. I denna rapport presenteras en lokal sökalgoritm för att skapa en population med fokus på ”vehicle routing”-problem. Algoritmen använder sig av heuristik i en blandning av simulated annealing och tabu search för att skapa individerna till populationen. Utvärderingar av algoritmen på ett praktiskt problem visar att den ger en bra start jämfört med en slumpmässig startpopulation, vilket är vanligt att använda. Resultaten av utvärderingen visar också att algoritmen ger bäst resultat vid mer komplexa problem, medan den har mindre effekt om problemet är enklare.   Nyckelord: Simulated annealing, Tabu search, Genetiska algoritmer , ”vehicle routing”-problem.

The rising power demands and cost motivates us to explore low power solutions in electronics. In nanometer Complementary Metal Oxide Semiconductor (CMOS) processes with low threshold voltages and thin gate oxides, subthreshold leakage power dominates total power of a circuit. As technology scales, Negative Bias Temperature Instability (NBTI) emerged as a major limiting reliability mechanism. It causes a threshold voltage shift which, over time, results in circuit performance degradation. Hence, leakage power and NBTI degradation are two key challenges in deep sub micron regime. In this dissertation, interval arithmetic based interval propagation technique is introduced as an effective leakage optimization technique in high level circuits with little overhead. The concept of self similarity from fractal theory is adopted for the first time in VLSI research to handle large design space. Though there are some leakage and NBTI co-optimization techniques in literature, our vector cycling approach combined with a back tracking algorithm have achieved better results for ISCAS85 benchmarks. We did not find any previous research works on NBTI optimization of finite state machines (FSMs). The optimization techniques of NBTI optimization in FSMs is introduced in this dissertation as well and substantial NBTI optimization is reported. Input vector control has been shown to be an effective technique to minimize subthreshold leakage. Applying appropriate minimum leakage vector (MLV) to each register transfer level (RTL) module instance results in a low leakage state with significant area overhead. For each module, via Monte Carlo simulation, we identify a set of MLV intervals such that maximum leakage is within (say) 10% of the lowest leakage points. As the module bit width increases, exhaustive simulation to find the low leakage vector is not feasible. Further, we need to search the entire input space uniformly to obtain as many low leakage intervals as possible. Based on empirical observations, we observed self similarity in the leakage distribution of adder/multiplier modules when input space is partitioned into smaller cells. This property enables uniform search of low leakage vectors in the entire input space. Also, the time taken for characterization increases linearly with the module size. Hence, this technique is scalable to higher bit width modules with acceptable characterization time. We can reduce area overhead (in some cases to 0) by choosing Primary Input (PI) MLVs such that resultant inputs to internal nodes are also MLVs. Otherwise, control points can be inserted. Based on interval arithmetic, given a DFG, we propose a heuristic with several variations for PI MLV identification with minimal control points. Experimental results for DSP filters simulated in 16nm technology demonstrated leakage savings of 93.8% with no area overhead, compared to existing work. Input vector control can also be adopted to reduce NBTI degradation as well as leakage in CMOS circuits. In the prior work, it is shown that minimum leakage vector of a circuit is not necessarily NBTI friendly. In order to achieve NBTI and leakage co-optimization, we propose an input vector cycling technique which applies different sub-optimal low leakage vectors to primary inputs at regular intervals. A co-optimal input vector for a given circuit is obtained by using simulated annealing (SA) technique. For a given input vector, a set of critical path PMOS transistors are under stress. A second input vector is obtained using a back tracking algorithm such that most of the critical path PMOS transistors are put in recovery mode. When a co-optimized input vector is assigned to primary input, critical path nodes under stress with high delay contribution are set to recovery. Logic 1 is back propagated from the nodes to the primary inputs to obtain the second input vector. These two vectors are alternated at regular time intervals. The total stress is evenly distributed among transistor sets of two vectors, as the intersection of the two sets is minimized. Hence, the overall stress on critical path transistors is alleviated, thereby reducing the NBTI delay degradation. For ISCAS85 benchmarks, an average of 5.3% improvement is achieved in performance degradation at 3.3% leakage overhead with NBTI-leakage co-optimization with a back tracking algorithm compared to solely using co-optimization. A 10.5% average NBTI improvement is obtained when compared to circuit with minimum leakage input vector for 18% average leakage overhead. Also, an average NBTI improvement of 2.13% is obtained with 6.77% leakage improvement when compared to circuit with minimum NBTI vector. Vector cycling is shown to be more effective in mitigating NBTI over input vector control. Several works in the literature have proposed optimal state encoding techniques for delay, leakage, and dynamic power optimization. In this work, we propose, for the first time, NBTI optimization based on state code optimization. We propose a SA based state code assignment algorithm, resulting in minimization of NBTI degradation in the synthesized circuit. A PMOS transistor when switched ON for a long period of time, will lead to delay degradation due to NBTI. Therefore, in combinational circuits, an NBTI friendly input vector that stresses the least number of PMOS transistors on the critical path can be applied. For sequential circuits, the state code can significantly influence the ON/OFF mode of PMOS transistors in the controller implementation. Therefore, we propose to focus on state encoding. As the problem is computational intractable, we will focus on encoding states with high state probability. The following SA moves are employed: (a) code swap; and (b) code modification by flipping bits. Experiments with LGSYNTH93 benchmarks resulted in 18.6% improvement in NBTI degradation on average with area and power improvements of 5.5% and 4.6% respectively.

Magister Scientiae - MSc / An electrolytic cell was designed and constructed for the preparation of TiO2 nanotubes. Conditions of anodic oxidation were established to reproducibly prepare TiO2 nanotubes of average length 35-50 μm vertically orientated relative to the plain of a pure titanium metal sheet. A non-aqueous solution of ethylene glycol containing small percentage of ammonium fluoride was used as the electrolyte with an applied voltage of 60 V. The morphology and dimensions of the nanotube arrays were studied by scanning (SEM) and transmission (TEM) electron microscopy. The effect of calcination under different conditions of temperature and atmosphere (nitrogen, argon and air) were assessed by both X-ray diffraction (XRD) and cyclic voltammetry (CV). Cyclic voltammetry studies were made possible by construction of a specially designed titanium electrode upon which the nanotubes were prepared. CV studies established a positive correlation between crystallinity and conductivity of the nanotubes. Doping of the nanotubes with nitrogen and carbon was established by elemental analysis, X-ray photoelectron spectroscopy (XPS) and Rutherford back scattering (RBS). The effect of nonmetal doping on the band gap of the TiO2 nanotubes was investigated by diffuse reflectance spectroscopy (DRS). / South Africa

Context: This study has been conducted in the area of train rescheduling. One of the most common types of disturbance scenarios are trains which have deviated from their originally planned arrival or departure times. This type of disturbance is of today handled manually by the train dispatcher, which in some cases can be cumbersome and overwhelmingly complex to solve. Therefore, there is an essential need for a train re-scheduling decision support system. Objectives: The aim of the study is to determine if parallel adaptations of simulated annealing(SA), and tabu search(TS) are able to find high quality solutions for the train re-scheduling problem. The study also aims to compare the two proposed meta-heuristics in order to determine the more adequate algorithm for the given problem. Methods: To answer the research question sequential and parallel versions of the algorithms were implemented. Further the research methodology of choice was experiment, were the meta-heuristics are evaluated based on 10 disturbance scenarios. Results: Parallel simulated annealing(PSA) is overall the better performing algorithm, as it is able to reduce the total delay by 585 seconds more than parallel tabu search(PTS) for the 10 disturbance scenarios. However, PTS is able to solve more conflicts per millisecond than PTS, when compared to their sequential versions. Conclusions: We conclude that both the parallel versions perform better than their sequential versions. Further, PSA is clearly able to outperform PTS in terms of minimizing the accumulated delay. One observation is that the parallel versions are not reaching their max efficiency per thread, this is assumed to be caused by the RAM. For future work we propose further investigation of why we are not reaching the max efficiency per thread, and further improvement of algorithm settings.

No description available.

L'utilisation des fibres SiC Tyranno SA3 (TSA3) et Hi Nicalon S (HNS) pour le renforcement de composites céramiques dédiées aux applications nucléaires impose l'étude de leur stabilité microstructurale et de leur comportement mécanique sous irradiation. La cinétique d'amorphisation des fibres a été étudiée et comparée à celle d'un matériau modèle, 6H-SiC monocristallin, sans que des différences significatives puissent être observées. La dose seuil d'amorphisation totale a été évaluée à ~0,4 dpa à température ambiante et aucune amorphisation complète n'a pas être obtenue pour des températures d'irradiation supérieures à 200 ºC. Les échantillons amorphes ont ensuite été recuits thermiquement ce qui a conduit, pour des températures élevées, à leur recristallisation mais également à une fissuration et une délamination de la zone irradiée. Ce processus d'endommagement était activé thermiquement avec une énergie d'activation de 1,05 eV. En ce qui concerne le comportement mécanique, le fluage d'irradiation des fibres TSA3 a été étudié en utilisant une machine de traction in situ implantée sur deux plateformes d'irradiation aux ions. On montre que sous irradiation ces fibres se déforment en fonction du temps avec des chargements thermique et mécanique où le fluage thermique est négligeable. Cette déformation est plus élevée pour les faibles températures d'irradiation en raison d'un couplage entre le gonflement et le fluage d'irradiation. Pour des températures voisines de 1000 ºC, le gonflement devient négligeable ce qui permet l'étude spécifique du fluage d'irradiation dont la vitesse de déformation présente une dépendance linéaire au flux d'ions. / The use of Tyranno SA3 (TSA3) and Hi Nicalon S (HNS) SiC fibers as reinforcement for ceramic composites for nuclear applications requires the characterization of its structural stability and mechanical behavior under irradiation. Ion-amorphization kinetics of these fibers have been studied and compared to the model material, i.e. 6H-SiC single crystals, with no significant differences. For all samples, full amorphization threshold dose yields ~0.4 dpa at room temperature and complete amorphization was not achieved for irradiation temperatures over 200 ºC. Successively, ion-amorphized samples have been thermally annealed. It is reported that thermal annealing at high temperatures not only induces the recrystallization of the ion-amorphized samples but also causes cracking and delamination. Cracking is reported to be a thermally driven phenomenon characterized by activation energy of 1.05 eV. Regarding the mechanical irradiation behavior, irradiation creep of TSA3 fibers has been investigated using a tensile device dedicated to in situ tests coupled to two different ion-irradiation lines. It is reported that ion-irradiation (12 MeV C4+ and 92 MeV Xe23+) induces a time-dependent strain under loads where thermal creep is negligible. In addition, irradiation strain is reported to be higher at low irradiation temperatures due to a coupling between irradiation swelling and irradiation creep. At temperatures near 1000 ºC, irradiation swelling is minimized hence allowing the characterization of the irradiation creep. Irradiation creep rate is characterized by a linear correlation between the ion flux and the strain rate and square root dependence with the applied load.

Seit 2002 kam ein neues Interesse an Germanium als Material für CMOS-Bauelemente auf, angetrieben durch die höhere Beweglichkeit der Ladungsträger im Vergleich zu Silizium. Für die Herstellung von Germanium MOSFETs bestehen allerdings noch einige Herausforderungen. Speziell die Problematik der hohen n-Dotierung für die Source- und Draingebiete der PMOS-Transistoren hat sich dabei als potentieller Roadblocker herauskristallisiert. Die geringe Aktivierung und die hohe Diffusivität der Donatoren in Germanium stellen ein Problem für die Herstellung von CMOS-Schaltkreisen aus Germanium dar. Als ursächlich dafür wurden Vakanzen identifiziert (Bracht et.al.). Um das Diffusions- und das Aktivierungsverhalten von Arsen und Phosphor in Germanium zu untersuchen, wurden p-Typ Germaniumwafer durch Ionenimplantation mit beiden Spezies dotiert und anschließend durch Rapid-Thermal-Annealing und/ oder Flash-Lamp-Annealing ausgeheilt. Zusätzlich wurden Experimente mit kodotierten und P-dotierten Proben mit verringerter Schichtkonzentration durchgeführt. Untersuchungen mit Rutherford-Backscattering-Spektroskopie und Transmissions-Elektronen-Mikroskopie werden durchgeführt, um die strukturellen Eigenschaften der Proben infolge der Implantation und der Ausheilung festzustellen. Mittels Sekundärionen-Massen-Spektroskopie wird die Dotandenkonzentration bestimmt. Es folgen elektrische Messungen des Schichtwiderstandes bei Raumtemperatur und in geeigneten Fällen bei Temperaturen unterhalb 10K. An ausgewählten Proben werden Hallmessungen durchgeführt. Die Gesamtheit der Analyseverfahren ermöglicht eine Analyse des Rückwachsverhaltens, der Diffusion und der elektrischen Aktivierung der Dotanden unter den verschiedenen Implantations- und Ausheilbedingungen. Die nach verschiedenen Methoden bestimmten Größen wie die Ladungsträgerkonzentration und -mobilität werden betrachtet und im Hinblick auf die Parameter der Probenpräparation analysiert und mit der Literatur verglichen. Abschließend werden mögliche Mechanismen zur Deaktivierung von Donatoren in Germanium erörtert.

La reconstruction phylogénétique est considérée comme un élément central de divers domaines comme l’écologie, la biologie et la physiologie moléculaire pour lesquels les relations généalogiques entre séquences d’espèces ou de gènes, représentées sous forme d’arbres, peuvent apporter des éclairages significatifs à la compréhension de phénomènes biologiques. Le problème de Maximum de Parcimonie est une approche importante pour résoudre la reconstruction phylogénétique en se basant sur un critère d’optimalité pour lequel l’arbre comprenant le moins de mutations est préféré. Dans cette thèse nous proposons différentes méthodes pour s’attaquer à la nature combinatoire de ce problème NP-complet. Premièrement, nous présentons un algorithme de Recuit Simulé compétitif qui nous a permis de trouver des solutions de meilleure qualité pour un ensemble de problèmes. Deuxièmement, nous proposons une nouvelle technique de Path-Relinking qui semble intéressante pour comparer des arbres mais pas pour trouver des solutions de meilleure qualité. Troisièmement, nous donnons le code d’une implantation sur GPU de la fonction objectif dont l’intérêt est de réduire le temps d’exécution de la recherche pour des instances dont la longueur des séquences est importante. Finalement, nous introduisons un prédicteur capable d’estimer le score optimum pour un vaste ensemble d’instances avec une très grande précision. / Phylogenetic reconstruction is considered a central underpinning of diverse fields like ecology, molecular biology and physiology where genealogical relationships of species or gene sequences represented as trees can provide the most meaningful insights into biology. Maximum Parsimony (MP) is an important approach to solve the phylogenetic reconstruction based on an optimality criterion under which the tree that minimizes the total number of genetic transformations is preferred. In this thesis we propose different methods to cope with the combinatorial nature of this NP-complete problem. First we present a competitive Simulated Annealing algorithm which helped us find trees of better parsimony score than the ones that were known for a set of instances. Second, we propose a Path-Relinking technique that appears to be suitable for tree comparison but not for finding trees of better quality. Third, we give a GPU implementation of the objective function of the problem that can reduce the runtime for instances that have an important number of residues per taxon. Finally, we introduce a predictor that is able to estimate the best parsimony score of a huge set of instances with a high accuracy.

High-quality platelet single crystals of Tl₂Ba₂CuO₆±δ (Tl-2201) have been grown using a novel time-varying encapsulation scheme, minimizing the thallium oxide loss that has plagued other attempts and reducing cation substitution. This encapsulation scheme allows the melt to be decanted from the crystals, a step previously impossible, and the remaining cation substitution is homogenized via a high-temperature anneal. Oxygen annealing schemes were developed to produce sharp superconducting transitions from 5 to 85 K without damaging the crystals. The crystals' high homogeneity and high degree of crystalline perfection are further evidenced by narrow rocking curves; the crystals are comparable to YSZ-grown YBa₂Cu₃O₆₊δ by both metrics. Electron probe microanalysis (EPMA) ascertained the crystals' composition to be Tl₁.₉₂₀₍₂₎Ba₁.₉₆₍₂₎Cu₁.₀₈₀₍₂₎O₆₊δ; X-ray diffraction found the composition of a Tc = 75 K crystal to be Tl₁.₉₁₄₍₁₄₎Ba₂Cu₁.₀₈₆₍₁₄₎O₆.₀₇₍₅₎, in excellent agreement. X-ray refinement of the crystal structure found the crystals orthorhombic at most dopings, and their structure to be in general agreement with previous powder data. Cation-substituted Tl-2201 can be orthorhombic, orthorhombic crystals can be prepared, and these superconduct, all new results. X-ray diffraction also found evidence of an as yet unidentified commensurate superlattice modulation. The Tl-2201 crystals' electronic structure were studied by X-ray absorption and emission spectroscopies (XAS/XES). The Zhang-Rice singlet band gains less intensity on overdoping than expected, suggesting a breakdown of the Zhang-Rice singlet approximation, and one thallium oxide band does not disperse as expected. The spectra correspond very closely with LDA band structure calculations, and do not exhibit the upper Hubbard bands arising from strong correlations seen in other cuprates. The spectra are noteworthy for their unprecedented (in the high-Tc cuprates) simplicity. The startling degree to which the electronic structure can be explained bodes well for future research in the cuprates. The overdoped cuprates, and Tl-2201 in particular, may offer a unique opportunity for understanding in an otherwise highly confusing family of materials. / Science, Faculty of / Physics and Astronomy, Department of / Graduate

As a first project, collision-induced dissociation experiments were carried out using electrospray ionisation mass spectrometry on gas phase complexes involving different poly(methylmetacrylate) oligomers with three amino acids: glycine, leucine, and phenylalanine. After acquiring breakdown diagrams, RRKM modeling was used to fit the experimental data in order to obtain the 0 K activation energy and the entropy of activation. These thermodynamic data were then used to understand the competing dissociation channels observed (except for gas phase complexes involving glycine that had only one dissociation channel). Molecular dynamics simulated annealing calculations were carried on the gas phase complexes to understand further the energetic and entropic effects involved as well as the 3D conformation of these complexes. Valuable insight information was found on the 3D conformations, on a qualitative level. Using rotational constants and vibrational harmonic frequencies, it was possible to evaluate the entropy variation between the experimentally observed competing channels. Reasonable agreement was found between the experimental and theoretical variations of entropies. Finally, the proton affinity of poly(methylmetacrylate) oligomers is being discussed. Even though no absolute values for the proton affinity were found, the experimental and computational results help to understand the variation that accompanies the oligomers length. The second project presents the development an efficient and reproducible screening method for identifying low molecular weight compounds that bind to amyloid beta peptides (Abeta) peptides using electrospray ionization mass spectrometry (ESI-MS). Low molecular weight (LMW) compounds capable of interacting with soluble Abeta may be able to modulate/inhibit the Abeta aggregation process and serve as potential disease-modifying agents for Alzheimer’s disease. The present approach was used to rank the binding affinity of a library of compounds to Abeta1-40 peptide. The results obtained show that low molecular weight compounds bind similarly to Abeta1-42, Abeta1-40, as well as Abeta1-28 peptides and they underline the critical role of Abeta peptide charge motif in binding at physiological pH. Finally, some elements of structure-activity relationship (SAR) involved in the binding affinity of homotaurine to soluble Abeta peptides are discussed. As a third project, the gas phase binding of small molecules to the Abeta1-40 peptide generated by electrospray ionization has been explored with collision-induced dissociation mass spectrometry and kinetic rate theory. This project presents a simple procedure used to theoretically model the experimental breakdown diagrams for the Abeta1-40 peptide complexed with a series of aminosulfonate small molecules, namely homotaurine, 3-cyclohexylamino-2-hydroxy-1-propanesulfonic acid (CAPSO), 3-(1,3,4,9-tetrahydro-2H-beta-carbolin-2-yl) propane-1-sulfonic acid, 3-(1,3,4,9-tetrahydro-2H-beta-carbolin-2-yl)butane-1-sulfonic acid, and 3-(cyclohexylamino) propane-1-sulfonic acid. An alternative method employing an extrapolation procedure for the microcanonical rate constant, k(E), is also discussed.