Your email was sent successfully. Check your inbox.

An error occurred while sending the email. Please try again.

Proceed reservation?

Export
  • 1
    Electronic Resource
    Electronic Resource
    Springer
    OR spectrum 17 (1995), S. 125-137 
    ISSN: 1436-6304
    Keywords: Heuristics ; integer programming ; genetic algorithms ; scatter search ; Scatter search (gestreute Suche) ; genetische Algorithmen ; Sternpfade ; Projektion
    Source: Springer Online Journal Archives 1860-2000
    Topics: Mathematics , Economics
    Description / Table of Contents: Zusammenfassung Scatter Search (gestreute Suche) und genetische Algorithmen weisen eine Anzahl einander komplementärer Eigenschaften auf. Trotz verschiedenen Ursprungs haben sich in den letzten Jahren, insbesondere auch aufgrund zahlreicher Modifikationen genetischer Verfahren, zunehmend mehr Gemeinsamkeiten herausgeschält, die in erster Linie auch durch die Übertragung von Scatter Search Features in genetische Algorithmen entstanden. Einige grundlegende Aspekte von Scatter Search sind bisher jedoch in genetischen Algorithmen — im engeren Sinne — nicht berücksichtigt. Es zeigt sich, daß mittels Scatter Search Kombinationen von Lösungen generiert werden können, deren Eigenschaften entscheidend die kombinatorische Struktur der zugrundeliegenden Optimierungsprobleme widerspiegeln. Im Falle binärer Optimierungsprobleme werden durch Projektionen Lösungen zu sog. Sternpfaden (star-paths) kombiniert, von denen aus jeweils optimale Lösungen erzeugt werden können. Mögliche Ergänzungen durch Schnittebenen zur Exploration des Lösungsraumes legen nahe, der Kombination von Lösungen (vgl. etwa die Rekombination bei genetischen Algorithmen) zur Erzeugung problemspezifischen Wissens mehr Aufmerksamkeit zu schenken als bisher.
    Notes: Abstract Scatter search and genetic algorithms have originated from somewhat different traditions and perspectives, yet exhibit features that are strongly complementary. Links between the approaches have increased in recent years as variants of genetic algorithms have been introduced that embody themes in closer harmony with those of scatter search. Some researchers are now beginning to take advantage of these connections by identifying additional ways to incorporate elements of scatter search into genetic algorithm approaches. There remain aspects of the scatter approach that have not been exploited in conjunction with genetic algorithms, yet that provide ways to achieve goals that are basic to the genetic algorithm design. Part of the gap in implementing hybrids of these procedures may derive from relying too literally on the genetic metaphor, which in its narrower interpretation does not readily accommodate the strategic elements underlying scatter search. The theme of this paper is to show there are benefits to be gained by going beyond a perspective constrained too tightly by the connotations of the term “genetic”. We show that the scatter search framework directly leads to processes for combining solutions that exhibit special properties for exploiting combinatorial optimization problems. In the setting of zero-one integer programming, we identify a mapping that gives new ways to create combined solutions, producing constructions calledstar-paths for exploring the zero-one solution space. Star-path trajectories have the special property of lying within regions assured to include optimal solutions. They also can be exploited in association with both cutting plane and extreme point solution approaches. These outcomes motivate a deeper look into current conceptions of appropriate ways to combine solutions, and disclose there are more powerful methods to derive information from these combinations than those traditionally applied.
    Type of Medium: Electronic Resource
    Signatur Availability
    BibTip Others were also interested in ...
  • 2
    Electronic Resource
    Electronic Resource
    Springer
    OR spectrum 17 (1995), S. 149-158 
    ISSN: 1436-6304
    Keywords: Heuristics ; applications ; relaxations ; discrete location ; integer programming ; Heuristiken ; Anwendungen ; Relaxationen ; diskrete Standortplanung ; ganzzahlige Programmierung
    Source: Springer Online Journal Archives 1860-2000
    Topics: Mathematics , Economics
    Description / Table of Contents: Zusammenfassung Das Problem der Plazierung von Dämpfern für große flexible Gerüststrukturen im Raum besteht darin,p Gerüstteile der Struktur durch aktive (oder passive) Dämpfer zu ersetzen, so daß die modale Dämpfungsrate für alle signifikanten Vibrationsformen maximiert wird. Ist eine Spannungsmatrix gegeben, bei der die Zeilen den Modi und die Spalten den Gerüstteilen entsprechen, so besteht ein äquivalentes Problem darin, eine Menge vonp Spalten so zu bestimmen, daß die kleinste Zeilensumme über diep-Spalten maximiert wird. Für den Fall passiver Dämpfer wird eine Erweiterung des Modells angegeben, die als Entscheidungsvariablen die Frequenzen der maximalen Verrückung enthält. Als Formulierungen ergeben sich gemischt-ganzzahlige (0/1) LP-Probleme. Wir vergleichen das Verhalten von Tabu Search, Simulated Annealing sowie einem Branch & Bound-Verfahren für das Problem an einem im Labor entwickelten Testmodell, dem NASA Langley Controls-Structures Interact Phase I Evolutionary Model (10 Modi und 1507 Gerüstteile). Unsere Ergebnisse zeigen, daß sich Tabu Search mit Startlösungen gemäß einer LP-Relaxation sowohl hinsichtlich der Lösungsgüte als auch bezüglich der Rechenzeit als am günstigsten erweist.
    Notes: Abstract The damper placement problem for large flexible space truss structures is to determine thep truss members of the structure to replace with active (or passive) dampers so that the modal damping ratio is as large as possible for all significant modes of vibration. Equivalently, given a strain energy matrix with rows indexed on the modes and columns indexed on the truss members we seek to find a set ofp columns such that the smallest row sum, over thep columns, is maximized. An extension of this model is formulated for the passive damper case. This formulation includes the frequency of maximum displacement as a decision variable for each passive damper. Each formulation can be written as a mixed 0/1 integer linear program. We compare the performance of tabu search and simulated annealing for the damper placement problem on a laboratory test article, the NASA Langley Controls-Structures Interaction Phase I Evolutionary Model (10 modes and 1507 truss members). Tabu search, coupled with the starting solution generated by rounding the solution to a linear programming relaxation, is shown to provide the highest quality solutions in the shortest amount of computing time.
    Type of Medium: Electronic Resource
    Signatur Availability
    BibTip Others were also interested in ...
  • 3
    Electronic Resource
    Electronic Resource
    Springer
    OR spectrum 20 (1998), S. 229-235 
    ISSN: 1436-6304
    Keywords: Scheduling ; Heuristics ; Two-machine flow-shop ; Buffer ; Tabu Search ; Maschinenbelegungsplanung ; Heuristiken ; Zwei-Maschinen-Flow-Shop ; Zwischenlager ; Tabu-Search
    Source: Springer Online Journal Archives 1860-2000
    Topics: Mathematics , Economics
    Description / Table of Contents: Zusammenfassung In dieser Arbeit wird eine Heuristik zur Ermittlung der minimalen Gesamtdurchlaufzeit in einem Zwei-Maschinen-Flow-Shop-Problem mit begrenzter Zwischenlagerkapazität vorgestellt. Solche Maschinenbelegungs-planungsprobleme werden häufig zur Modellierung von Justin-Time und Flexiblen Fertigungssytemen eingesetzt. Der Algorithmus basiert auf dem Tabu-Search-Verfahren mit eingeschränkter Nachbarschaft, beschleunigter Suche und Rücksprungtechnik auf der Suchtrajektorie. Aufgrund einiger spezieller Eigenschaften liefert das vorgestellte Verfahren in kurzer Zeit Lösungsqualitäten nahe dem Optimum.
    Notes: Abstract Problems with “blocking” (limited intermediate storage space) are used frequently for modelling and scheduling just-in-time and flexible manufacturing systems. In this paper, an approximation algorithm is presented for the problem of finding the minimum makespan in a two-machine permutation flow-shop scheduling problem with the mediating buffer of finite capacity. The algorithm is based on the tabu search approach supported by the reduced neighborhood, search accelerator and technique of back jumps on the search trajectory. Due to some special properties, the proposed algorithm provides makespans very close to optimal in a short time. It has been shown that this algorithm outperforms all known approximation algorithms for the problem stated.
    Type of Medium: Electronic Resource
    Signatur Availability
    BibTip Others were also interested in ...
  • 4
    Electronic Resource
    Electronic Resource
    Springer
    OR spectrum 17 (1995), S. 67-86 
    ISSN: 1436-6304
    Keywords: Heuristic algorithms ; local search ; reactive tabu search ; N-K model ; multi-knapsack problem ; Heuristics ; local search ; reactive tabu search ; N-K Modell ; Multiknapsack Problem
    Source: Springer Online Journal Archives 1860-2000
    Topics: Mathematics , Economics
    Description / Table of Contents: Zusammenfassung Diese Arbeit entwickelt eine Variante der sogenannten „Reactive Tabu Search“ Methode (RTS), die auch für Optimierungsprobleme mit Nebenbedingungen geeignet ist. Das Verhalten dieser RTS Variante wird anhand einer Reihe von kombinatorischen Optimierungsproblemen mit und ohne Nebenbedingungen ausgetestet. Die Benchmark besteht aus einigen Beispielen des N-K Modells und des Multiknapsack Problems mit verschiedenen Größen und Schwierigkeitsstufen, die mit portablen Zufallszahlgeneratoren definiert werden. Ein Vergleich zwischen der Leistung der RTS Variante und der Leistung von Repeated Local Minima Search, Simulated Annealing, genetischen Algorithmen und neuronalen Netzen wird durchgeführt. Anschließend werden die Auswirkungen verschiedener Hashingschemata und eines ‚aspiration‘ Kriteriums im RTS Algorithmus untersucht.
    Notes: Abstract The purpose of this work is that of presenting a version of the Reactive Tabu Search method (RTS) that is suitable for constrained problems, and that of testing RTS on a series of constrained and unconstrained Combinatorial Optimization tasks. The benchmark suite consists of many instances of the N-K model and of the Multiknapsack problem with various sizes and difficulties, defined with portable random number generators. The performance of RTS is compared with that of Repeated Local Minima Search, Simulated Annealing, Genetic Algorithms, and Neural Networks. In addition, the effects of differenthashing schemes and of the presence of a simple “aspiration” criterion in the RTS algorithm are investigated.
    Type of Medium: Electronic Resource
    Signatur Availability
    BibTip Others were also interested in ...
Close ⊗
This website uses cookies and the analysis tool Matomo. More information can be found here...