TY - CONF AB - In practise, it is often desirable to provide the decision-maker with a rich set of diverse solutions of decent quality instead of just a single solution. In this paper we study evolutionary diversity optimization for the knapsack problem (KP). Our goal is to evolve a population of solutions that all have a profit of at least (1 - {$ϵ$}) {$\cdot$} OPT, where OPT is the value of an optimal solution. Furthermore, they should differ in structure with respect to an entropy-based diversity measure. To this end we propose a simple ({$\mu$} + 1)-EA with initial approximate solutions calculated by a well-known FPTAS for the KP. We investigate the effect of different standard mutation operators and introduce biased mutation and crossover which puts strong probability on flipping bits of low and/or high frequency within the population. An experimental study on different instances and settings shows that the proposed mutation operators in most cases perform slightly inferior in the long term, but show strong benefits if the number of function evaluations is severely limited. AU - Bossek, Jakob AU - Neumann, Aneta AU - Neumann, Frank ID - 48853 KW - evolutionary algorithms KW - evolutionary diversity optimization KW - knapsack problem KW - tailored operators SN - 978-1-4503-8350-9 T2 - Proceedings of the Genetic and Evolutionary Computation Conference TI - Breeding Diverse Packings for the Knapsack Problem by Means of Diversity-Tailored Evolutionary Algorithms ER - TY - CONF AB - In the area of evolutionary computation the calculation of diverse sets of high-quality solutions to a given optimization problem has gained momentum in recent years under the term evolutionary diversity optimization. Theoretical insights into the working principles of baseline evolutionary algorithms for diversity optimization are still rare. In this paper we study the well-known Minimum Spanning Tree problem (MST) in the context of diversity optimization where population diversity is measured by the sum of pairwise edge overlaps. Theoretical results provide insights into the fitness landscape of the MST diversity optimization problem pointing out that even for a population of {$\mu$} = 2 fitness plateaus (of constant length) can be reached, but nevertheless diverse sets can be calculated in polynomial time. We supplement our theoretical results with a series of experiments for the unconstrained and constraint case where all solutions need to fulfill a minimal quality threshold. Our results show that a simple ({$\mu$} + 1)-EA can effectively compute a diversified population of spanning trees of high quality. AU - Bossek, Jakob AU - Neumann, Frank ID - 48860 KW - evolutionary algorithms KW - evolutionary diversity optimization KW - minimum spanning tree KW - runtime analysis SN - 978-1-4503-8350-9 T2 - Proceedings of the Genetic and Evolutionary Computation Conference TI - Evolutionary Diversity Optimization and the Minimum Spanning Tree Problem ER - TY - JOUR AB - We contribute to the theoretical understanding of randomized search heuristics for dynamic problems. We consider the classical vertex coloring problem on graphs and investigate the dynamic setting where edges are added to the current graph. We then analyze the expected time for randomized search heuristics to recompute high quality solutions. The (1+1) Evolutionary Algorithm and RLS operate in a setting where the number of colors is bounded and we are minimizing the number of conflicts. Iterated local search algorithms use an unbounded color palette and aim to use the smallest colors and, consequently, the smallest number of colors. We identify classes of bipartite graphs where reoptimization is as hard as or even harder than optimization from scratch, i.e., starting with a random initialization. Even adding a single edge can lead to hard symmetry problems. However, graph classes that are hard for one algorithm turn out to be easy for others. In most cases our bounds show that reoptimization is faster than optimizing from scratch. We further show that tailoring mutation operators to parts of the graph where changes have occurred can significantly reduce the expected reoptimization time. In most settings the expected reoptimization time for such tailored algorithms is linear in the number of added edges. However, tailored algorithms cannot prevent exponential times in settings where the original algorithm is inefficient. AU - Bossek, Jakob AU - Neumann, Frank AU - Peng, Pan AU - Sudholt, Dirk ID - 48854 IS - 10 JF - Algorithmica KW - Dynamic optimization KW - Evolutionary algorithms KW - Running time analysis SN - 0178-4617 TI - Time Complexity Analysis of Randomized Search Heuristics for the Dynamic Graph Coloring Problem VL - 83 ER - TY - CONF AB - Modern services comprise interconnected components, e.g., microservices in a service mesh, that can scale and run on multiple nodes across the network on demand. To process incoming traffic, service components have to be instantiated and traffic assigned to these instances, taking capacities and changing demands into account. This challenge is usually solved with custom approaches designed by experts. While this typically works well for the considered scenario, the models often rely on unrealistic assumptions or on knowledge that is not available in practice (e.g., a priori knowledge). We propose a novel deep reinforcement learning approach that learns how to best coordinate services and is geared towards realistic assumptions. It interacts with the network and relies on available, possibly delayed monitoring information. Rather than defining a complex model or an algorithm how to achieve an objective, our model-free approach adapts to various objectives and traffic patterns. An agent is trained offline without expert knowledge and then applied online with minimal overhead. Compared to a state-of-the-art heuristic, it significantly improves flow throughput and overall network utility on real-world network topologies and traffic traces. It also learns to optimize different objectives, generalizes to scenarios with unseen, stochastic traffic patterns, and scales to large real-world networks. AU - Schneider, Stefan Balthasar AU - Manzoor, Adnan AU - Qarawlus, Haydar AU - Schellenberg, Rafael AU - Karl, Holger AU - Khalili, Ramin AU - Hecker, Artur ID - 19609 KW - self-driving networks KW - self-learning KW - network coordination KW - service coordination KW - reinforcement learning KW - deep learning KW - nfv T2 - IEEE International Conference on Network and Service Management (CNSM) TI - Self-Driving Network and Service Coordination Using Deep Reinforcement Learning ER - TY - GEN AB - The aim to reduce pollutant emission has led to a trend towards lightweight construction in car body development during the last years. As a consequence of the resulting need for multi-material design, mechanical joining technologies become increasingly important. Mechanical joining allows for the combination of dissimilar materials, while thermic joining techniques reach their limits. Self-piercing riveting enables the joining of dissimilar materials by using semi-tubular rivets as mechanical fasteners. The rivet production, however, is costly and time-consuming, as the rivets generally have to be hardened, tempered and coated after forming, in order to achieve an adequate strength and corrosion resistance. A promising approach to improve the efficiency of the rivet manufacturing is the use of high-strength high nitrogen steel as rivet material because these additional process steps would not be necessary anymore. As a result of the comparatively high nitrogen content, such steels have various beneficial properties like higher strength, good ductility and improved corrosion resistance. By cold bulk forming of high nitrogen steels high-strength parts can be manufactured due to the strengthening which is caused by the high strain hardening. However, high tool loads thereby have to be expected and are a major challenge during the production process. Consequently, there is a need for appropriate forming strategies. This paper presents key aspects concerning the process design for the manufacturing of semi-tubular self-piercing rivets made of high-strength steel. The aim is to produce the rivets in several forming stages without intermediate heat treatment between the single stages. Due to the high strain hardening of the material, a two stage forming concept will be investigated. Cup-backward extrusion is chosen as the first process step in order to form the rivet shank without forming the rivet foot. Thus, the strain hardening effects in the area of the rivet foot are minimized and the tool loads during the following process step can be reduced. During the second and final forming stage the detailed geometry of the rivet foot and the rivet head is formed. In this context, the effect of different variations, for example concerning the final geometry of the rivet foot, on the tool load is investigated using multistage numerical analysis. Furthermore, the influence of the process temperature on occurring stresses is analysed. Based on the results of the investigations, an adequate forming strategy and a tool concept for the manufacturing of semi-tubular self-piercing rivets made of high-strength steel are presented. ED - Kuball, Clara-Maria ED - Uhe, Benedikt ED - Meschut, Gerson ED - Merklein, Marion ID - 19976 KW - high nitrogen steel KW - self-piercing riveting KW - joining by forming KW - bulk forming KW - tool design TI - Process design for the forming of semi-tubular self-piercing rivets made of high nitrogen steel VL - 50 ER - TY - CONF AB - We consider a natural extension to the metric uncapacitated Facility Location Problem (FLP) in which requests ask for different commodities out of a finite set \( S \) of commodities. Ravi and Sinha (SODA 2004) introduced the model as the \emph{Multi-Commodity Facility Location Problem} (MFLP) and considered it an offline optimization problem. The model itself is similar to the FLP: i.e., requests are located at points of a finite metric space and the task of an algorithm is to construct facilities and assign requests to facilities while minimizing the construction cost and the sum over all assignment distances. In addition, requests and facilities are heterogeneous; they request or offer multiple commodities out of $S$. A request has to be connected to a set of facilities jointly offering the commodities demanded by it. In comparison to the FLP, an algorithm has to decide not only if and where to place facilities, but also which commodities to offer at each. To the best of our knowledge we are the first to study the problem in its online variant in which requests, their positions and their commodities are not known beforehand but revealed over time. We present results regarding the competitive ratio. On the one hand, we show that heterogeneity influences the competitive ratio by developing a lower bound on the competitive ratio for any randomized online algorithm of \( \Omega ( \sqrt{|S|} + \frac{\log n}{\log \log n} ) \) that already holds for simple line metrics. Here, \( n \) is the number of requests. On the other side, we establish a deterministic \( \mathcal{O}(\sqrt{|S|} \cdot \log n) \)-competitive algorithm and a randomized \( \mathcal{O}(\sqrt{|S|} \cdot \frac{\log n}{\log \log n} ) \)-competitive algorithm. Further, we show that when considering a more special class of cost functions for the construction cost of a facility, the competitive ratio decreases given by our deterministic algorithm depending on the function. AU - Castenow, Jannik AU - Feldkord, Björn AU - Knollmann, Till AU - Malatyali, Manuel AU - Meyer auf der Heide, Friedhelm ID - 17370 KW - Online Multi-Commodity Facility Location KW - Competitive Ratio KW - Online Optimization KW - Facility Location Problem SN - 9781450369350 T2 - Proceedings of the 32nd ACM Symposium on Parallelism in Algorithms and Architectures TI - The Online Multi-Commodity Facility Location Problem ER - TY - JOUR AU - Otroshi, Mortaza AU - Rossel, Moritz AU - Meschut, Gerson ID - 20143 JF - Journal of Advanced Joining Processes KW - Self-pierce riveting KW - Ductile fracture KW - Damage modeling KW - GISSMO damage model TI - Stress state dependent damage modeling of self-pierce riveting process simulation using GISSMO damage model VL - 1 ER - TY - JOUR AB - Im Artikel werden drei verschiedene Lernzugänge (kom-petenzorientiertes, ästhetisches und biographisches Lernen) vorgestellt und aus theoretischer Perspektive deren motivierender Gehalt für selbstreguliertes Lernen in Praxisphasen des Lehramtsstudiumsherausgearbeitet. Als theoretische Grund-lage dient die Selbstbestimmungstheorie als zentrale motivationale Theorie zur Erklärung selbstbestimmten Handelns. AU - Caruso, Carina AU - Adammek, Christine AU - Bonanati, Sabrina AU - Wiescholek, Sybille ID - 35298 IS - 1 JF - Herausforderung Lehrer*innenbildung - Zeitschrift Zur Konzeption, Gestaltung Und Diskussion KW - ästhetische Forschung KW - Biographiearbeit KW - Praxissemester KW - Professionalisierung KW - selbstreguliertes Lernen KW - Motivation / aesthetic research KW - biographical work KW - long-term internship KW - profes-sionalization KW - self-regulated learning KW - motivation SN - 2625-0675 TI - Motivierende Lernzugänge als Ausgangspunkt der Professionalisierung angehender Lehrer_innen VL - 3 ER - TY - JOUR AB - Helhmoltz–Kirchhoff equations of motions of vortices of an incompressible fluid in the plane define a dynamics with singularities and this leads to a Zermelo navigation problem describing the ship travel in such a field where the control is the heading angle. Considering one vortex, we define a time minimization problem which can be analyzed with the technics of geometric optimal control combined with numerical simulations, the geometric frame being the extension of Randers metrics in the punctured plane, with rotational symmetry. Candidates as minimizers are parameterized thanks to the Pontryagin Maximum Principle as extremal solutions of a Hamiltonian vector field. We analyze the time minimal solution to transfer the ship between two points where during the transfer the ship can be either in a strong current region in the vicinity of the vortex or in a weak current region. The analysis is based on a micro-local classification of the extremals using mainly the integrability properties of the dynamics due to the rotational symmetry. The discussion is complex and related to the existence of an isolated extremal (Reeb) circle due to the vortex singularity. The explicit computation of cut points where the extremal curves cease to be optimal is given and the spheres are described in the case where at the initial point the current is weak. AU - Bonnard, Bernard AU - Cots, Olivier AU - Wembe Moafo, Boris Edgar ID - 33866 JF - ESAIM: Control, Optimisation and Calculus of Variations KW - Computational Mathematics KW - Control and Optimization KW - Control and Systems Engineering SN - 1292-8119 TI - A Zermelo navigation problem with a vortex singularity VL - 27 ER - TY - GEN AB - Due to the trend towards lightweight design in car body development mechanical joining technologies become increasingly important. These techniques allow for the joining of dissimilar materials and thus enable multi-material design, while thermic joining methods reach their limits. Semi-tubular self-piercing riveting is an important mechanical joining technology. The rivet production, however, is costly and time-consuming, as the process consists of several process steps including the heat treatment and coating of the rivets in order to achieve an adequate strength and corrosion resistance. The use of high nitrogen steel as rivet material leads to the possibility of reducing process steps and hence increasing the efficiency of the process. However, the high tool loads being expected due to the high strain hardening of the material are a major challenge during the rivet production. Thus, there is a need for appropriate forming strategies, such as the manufacturing of the rivets at elevated temperatures. Prior investigations led to the conclusion that forming already at 200 °C results in a distinct reduction of the yield strength. To create a deeper understanding of the forming behaviour of high nitrogen steel at elevated temperatures, compression tests were conducted in a temperature range between room temperature and 200 °C. The determined true stress – true strain curves are the basis for the further process and tool design of the rivet production. Another key factor for the rivet manufacturing at elevated temperatures is the influence of the process temperature on the tribological conditions. For this reason, ring compression tests at room temperature and 200 °C are carried out. The friction factors are determined on the basis of calibration curves resulting from the numerical analysis of the ring compression process. The investigations indicate that the friction factor at 200 °C is significantly higher compared to room temperature. This essential fact has to be taken into account for the process and tool design for the rivet production using high nitrogen steel. ED - Kuball, Clara-Maria ED - Jung, R ED - Uhe, Benedikt ED - Meschut, Gerson ED - Merklein, Marion ID - 19974 KW - High nitrogen steel KW - Self-piercing riveting KW - Joining by forming KW - Bulk forming KW - Strain hardening TI - Influence of the process temperature on the forming behaviour and the friction during bulk forming of high nitrogen steel VL - 1 ER -