Hackl, R. ; Morgenstern, Ingo
Alternative Links zum Volltext:DOI
| Dokumentenart: | Artikel |
|---|
| Titel eines Journals oder einer Zeitschrift: | International Journal of Modern Physics C (ijmpc) |
|---|
| Verlag: | World Scientific Publishing |
|---|
| Band: | 8 |
|---|
| Nummer des Zeitschriftenheftes oder des Kapitels: | 5 |
|---|
| Seitenbereich: | S. 1103-1117 |
|---|
| Datum: | Oktober 1997 |
|---|
| Institutionen: | Physik > Institut für Theoretische Physik > Professor Morgenstern |
|---|
| Identifikationsnummer: | | Wert | Typ |
|---|
| 10.1142/S0129183197000977 | DOI |
|
|---|
| Stichwörter / Keywords: | Optimization; Genetic Algorithms; Traveling Salesman; NP-Complete Problems |
|---|
| Dewey-Dezimal-Klassifikation: | 500 Naturwissenschaften und Mathematik > 530 Physik |
|---|
| Status: | Veröffentlicht |
|---|
| Begutachtet: | Unbekannt / Keine Angabe |
|---|
| An der Universität Regensburg entstanden: | Unbekannt / Keine Angabe |
|---|
| Dokumenten-ID: | 16262 |
|---|
Zusammenfassung
In this article we consider the optimization of np-complete problems with a genetic algorithm. For "real word" problems we regard it to be sufficient to get close to the optimal solution without any guarantee of ever hitting it. Our algorithm was tested on two problem classes: the traveling salesman problem and the product ordering problem; the first is a standard problem, the latter a problem we ...
Zusammenfassung
In this article we consider the optimization of np-complete problems with a genetic algorithm. For "real word" problems we regard it to be sufficient to get close to the optimal solution without any guarantee of ever hitting it. Our algorithm was tested on two problem classes: the traveling salesman problem and the product ordering problem; the first is a standard problem, the latter a problem we were confronted with in a practical application. For all investigated problem instances we found very good solutions (<0.2% above optimum) in each run and even the global optimum in some runs on a Pentium/100 MHz-PC. For one instance of the TSP problem we could verify that the time spent to find the optimum follows a logarithmic normal distribution.
Altmetric