Skip to main content
Fachgebiete
Automobil + Motoren Bauwesen + Immobilien Business IT + Informatik Elektrotechnik + Elektronik Energie + Nachhaltigkeit Finance + Banking Management + Führung Marketing + Vertrieb Maschinenbau + Werkstoffe Versicherung + Risiko
DE
EN
Bücher
Zeitschriften
Themenseiten
Organisationspsychologie Projektmanagement Marketing Smart Manufacturing
Weitere Formate
Podcasts Webinare Technik Webinare Wirtschaft Kongresse Veranstaltungskalender Awards
Jetzt Einzelzugang starten
Zugang für Unternehmen
Referenzkunden
SLX-Digitalkonferenz: Zukunftswerkstatt 2024

Mehr Umsatz mit Top-Kontakten

Am 7. Mai erfahren Sie, wie Vertriebsteams Leadgenerierung, Leadnurturing und Leadstrategien effizient steuern können.
Erweiterte Suche
Anmelden
nach oben

2002 | Buch

Genetic Algorithms and Innovation Kapitel lesen Erstes Kapitel lesen

The Design of Innovation

Lessons from and for Competent Genetic Algorithms

verfasst von: David E. Goldberg

Verlag: Springer US

Buchreihe : Genetic Algorithms and Evolutionary Computation

Enthalten in: Professional Book Archive

Einloggen, um Zugang zu erhalten
insite
SUCHEN

Über dieses Buch

7 69 6 A DESIGN APPROACH TO PROBLEM DIFFICULTY 71 1 Design and Problem Difficulty 71 2 Three Misconceptions 72 3 Hard Problems Exist 76 4 The 3-Way Decomposition and Its Core 77 The Core of Intra-BB Difficulty: Deception 5 77 6 The Core of Inter-BB Difficulty: Scaling 83 7 The Core of Extra-BB Difficulty: Noise 88 Crosstalk: All Roads Lead to the Core 8 89 9 From Multimodality to Hierarchy 93 10 Summary 100 7 ENSURING BUILDING BLOCK SUPPLY 101 1 Past Work 101 2 Facetwise Supply Model I: One BB 102 Facetwise Supply Model II: Partition Success 103 3 4 Population Size for BB Supply 104 Summary 5 106 8 ENSURING BUILDING BLOCK GROWTH 109 1 The Schema Theorem: BB Growth Bound 109 2 Schema Growth Somewhat More Generally 111 3 Designing for BB Market Share Growth 112 4 Selection Press ure for Early Success 114 5 Designing for Late in the Day 116 The Schema Theorem Works 6 118 A Demonstration of Selection Stall 7 119 Summary 122 8 9 MAKING TIME FOR BUILDING BLOCKS 125 1 Analysis of Selection Alone: Takeover Time 126 2 Drift: When Selection Chooses for No Reason 129 3 Convergence Times with Multiple BBs 132 4 A Time-Scales Derivation of Critical Locus 142 5 A Little Model of Noise-Induced Run Elongation 143 6 From Alleles to Building Blocks 147 7 Summary 148 10 DECIDING WELL 151 1 Why is Decision Making a Problem? 151

Inhaltsverzeichnis

Frontmatter
Chapter 1. Genetic Algorithms and Innovation
Abstract
Genetic algorithms (GAs) are defined as search procedures based on the mechanics of natural selection and genetics, and we think we know what innovation is—at least in some qualitative sort of way—but what does one have to do with the other? The connection appeared fairly early in my writing on GAs when I used human innovation in my PhD dissertation (Goldberg, 1983) as a metaphor or an intuitive explanation of how such simple mechanisms as those in genetic algorithms might be doing something quite interesting. My aim was to give a plausible explanation of GA power to new readers in an effort to connect with those who might otherwise find the operation of GAs somewhat suspect. I repeated this argument in my earlier book on genetic algorithms (Goldberg, 1989c), and for some readers of that text the argument was temporarily satisfying; for others it was simply maddening, and so the matter has stood. Yet, as my own work on designing increasingly effective genetic algorithms has proceeded, it seemed that the speed and quality of solutions that we were obtaining were far beyond anything I had expected initially. Because of this, and because of my earlier flirtation with innovation, I wondered if perhaps the design of effective GAs was ultimately helping us create first-order computational models of innovation.
David E. Goldberg
Chapter 2. Making Genetic Algorithms Fly
Abstract
The interlocked goals of this book—the design of GAs that work and the discovery of computational models of innovation—force us to ask a pair of methodological questions: How do we design competent, selectorecombinative genetic algorithms—GAs that solve hard problems quickly, reliably, and accurately? How do we build computational models of the processes of cross-fertilizing innovation? If we were to treat these complex questions about abstract topics directly with the intellectual gravity and abstruse prose that they perhaps deserve, there would almost certainly be no readers left at the beginning of chapter 3. But more to the point, it is often useful when trying to do something new to shift the terms of the debate to a domain that is further along in its intellectual development. Thus, here we choose not to examine the question of how we should design GAs directly; rather, we shift to another era and area of human endeavor and examine the historical record of how two of the greatest inventors of the twentieth century came to build and fly that marvelous machine, the airplane. Along the way, we abstract a number of straightforward lessons that will help us in the development of innovating machines such as genetic algorithms.
David E. Goldberg
Chapter 3. Three Tools of Conceptual Engineering
Abstract
The previous chapter argued for a tripartite method of invention or design for genetic algorithms and other innovating machines. The argument was made at a fairly high level, however, invoking some aviation history as empirical evidence, an economy of modeling as rational theory, and a combination of philosophy and history to unmask a cultural bias that resists the adoption of effective design technique. Although these efforts were important to laying the intellectual foundations for what follows, abstract discourse does not show us the way to GAs that work. Here, we examine three tools of the conceptual engineering trade:
1.
design decomposition
 
2.
little models
 
3.
patchquilt integration using dimensional analysis
 
in somewhat more detail with an eye toward application. Where it is advantageous, examples of technique in the realm of material machines will be given followed by a “conceptual machine” example drawn from the design of selectorecombinative genetic algorithms.
David E. Goldberg
Chapter 4. Goals and Elements of GA Design
Abstract
The last chapter was methodological, arguing that the design of effective GAs—the design of complex conceptual machines of all kinds—requires both clarity of aims and the application of an effective design method. In this chapter, we outline the goals of our GA design efforts and consider the elements of an integrated theory of selectorecombinative GA design.
David E. Goldberg
Chapter 5. Building Blocks
Abstract
The metaphor of flight has already been stretched to the breaking point, but we tug at it again to help answer a difficult question: What is the starting point of rational GA design? It is tempting to answer that the moment one has conceived of automata containing chromosomes, genes, and associated hardware together with genetic and selective processing that one is in business, but returning to the example of the Wright brothers and other would-be aviators of the 19th century, the mere conception of powered flight was not enough. Humankind has almost certainly always dreamed of flight and probably has had some notion of the importance of wings to that effort. Thousands of years of recorded history passed without success in flight. No, rational design efforts began when the principles of flight were developed, when the Magnus effect—the ability of circulation around an airfoil to create lift—was understood, and when these principles were associated with airfoils, angle of attack, and the other necessities of flight. Then and only then was a deliberate effort to create powered flight successful.
David E. Goldberg
Chapter 6. A Design Approach to Problem Difficulty
Abstract
The last chapter motivated and expanded upon the notion of a building block to understand the raw material available for genetic search. This chapter builds on these ideas to understand the ways in which a GA might succeed or fail depending upon the type of problem it faces. Our approach is to design bounding adversarial problems that represent different dimensions of problem difficulty. Success in this endeavor will allow us to test different algorithms against a limited number of boundedly difficult problems in such a way that algorithm success against the particular problems ensures success against a large class of problems no harder than the test cases. This adversarial design method contrasts sharply with the common practices of using historical, randomly generated, or ad hoc test functions.
David E. Goldberg
Chapter 7. Ensuring Building Block Supply
Abstract
In chapter 5, we defined what we meant by building blocks and acknowledged their importance. In the last chapter, we looked at search problems through the lens of building blocks and tried to envision various dimensions of problem difficulty from that standpoint. Here it is important to take BBs quite seriously, almost physically, and make sure that the GA is well supplied with a good stock of the building blocks necessary to solve the problem at hand. In this chapter, we consider this supply question in isolation and estimate the size of population necessary to ensure that the raw BBs are present and available for subsequent selection and genetic operation. As it turns out, the supply population requirement is often superseded by the so-called decision-making population size to be taken up in a subsequent chapter. Moreover, more sophisticated equations combine the requirements of supply and decision in a single model. Nonetheless, we examine the supply question in isolation, because the calculations are straightforward, revealing, and easily verified. We start by briefly reviewing prior work in this area and then turn to deriving a facetwise model with some straightforward probabilistic calculation.
David E. Goldberg
Chapter 8. Ensuring Building Block Growth
Abstract
In the previous chapter, we examined estimates of the population size required to ensure that building blocks of the required size are present in the initial population. This chapter develops the theory to permit us to design GAs and choose their parameters to ensure that the market share of the best building blocks grows. We start by reexamining the well-known schema theorem and consider its implications in GA design, both early and late during the life of a run. These considerations help us both qualitatively in choosing appropriate selection operators and quantitatively in setting an appropriate balance between selection pressure and recombination frequency.
David E. Goldberg
Chapter 9. Making Time for Building Blocks
Abstract
The schema theorem provides one important constraint on the design of a genetic algorithm. Certainly, if the building blocks that make up desirable solutions do not grow in market share, there is little hope that recombination mixes them to form good solutions. Having said this, the schema theorem is something of a static condition saying little about the time to substantial convergence, and understanding time is critical for two reasons. Most pragmatically, understanding time is one leg of a three-legged analytical stool of understanding (1) time or run duration, (2) space or population size, and (3) accuracy or solution quality that enables us to start to estimate solution time complexity, and we certainly are most interested in understanding how selectorecombinative GAs scale as problem size or difficulty change. Second, applicable models of time enable us to analyze other key phenomena by appealing to time-scales arguments such as the race alluded to in chapter 3. In this chapter, we examine an array of little models that help us understand how long it takes before populations converge under a variety of assumptions.
David E. Goldberg
Chapter 10. Deciding Well
Abstract
We have identified what we think the GA is processing—building blocks; we have ensured that there is a sufficient initial supply of BBs and that the best ones grow in market share on average; and just now, we have taken the time to understand how long such market share growth takes, but how do we know whether the best building blocks are actually the ones that come to dominate the population? Answering this question is the focus of this chapter. Specifically, building on the identification of the building block decision problem as a problem in statistical decision making (Holland, 1973), we examine a number of little models of BB decision making. Starting with the generation-wise decision model that gave an initial bound on the relation between solution quality and population size, we conclude by presenting a simple, accurate model based on the solution to the gambler’s ruin problem. In the best tradition of little models, this back-of-an-envelope calculation is giving surprisingly accurate estimates of decision quality across a range of population sizes, problem sizes and complexity, and GA operators and selection schemes.
David E. Goldberg
Chapter 11. Mixing, Control Maps, and Genetic Algorithm Success
Abstract
On the face of it, the previous chapter would seem like good news. After all, solution accuracy and reliability were predictably controlled using nothing more than appropriate (sub- or near-linear) population sizing. Moreover, this happy circumstance appeared to occur on both easy and hard problems. But closer scrutiny of the presented results shows that all is not necessarily well. In the last chapter, and in previous works on population sizing, when difficult problems were tested, tight linkage was assumed. That is, alleles contributing to a difficult building block were assumed to be physically close to one another, and crossover operators such as single-point crossover were used to facilitate the necessary exchange of intact building blocks with high probability.
David E. Goldberg
Chapter 12. Design of Competent Genetic Algorithms
Abstract
The good news of the last chapter was that mixing or exchange behavior can be understood in quantitative terms. The bad news was that simple selectorecombinative GAs scale poorly on hard problems, largely the result of their inadequate mixing behavior. of course, this does not say that simple GAs are not useful; nor does it invalidate the success that many have had in using simple GAs to solve problems that are difficult to approach by other means. Moreover, the class of nearly decomposable problems with unknown decomposition is difficult to crack by any computational method. But the results presented in the last chapter do go a long way toward explaining the observed fiddling and twiddling with codings and operators that have long been a staple of practical GA application. It also makes us wonder whether it is possible to design what we have called competent GAs—GAs that solve boundedly difficulty problems quickly, reliably, and accurately without the need for problemspecific codings, operators, or other forms of human intervention.
David E. Goldberg
Epilogue: From Competence to Efficiency and Beyond
Abstract
Twelve chapters ago we embarked on a journey through what has proven to be interesting intellectual territory. Here, we review where we have been and consider some of the research directions made possible by the methods and results reported. A number of these directions have already attracted significant activity, and some are just starting to draw a crowd, but all are put on firmer ground by the results of this volume. In particular we consider (1) the spread of the competence revolution to other forms of genetic and evolutionary computation, (2) the development and use of efficiency-enhancement techniques, (3) closer investigation of GAs as models of innovation, and (4) the prospect for going beyond computational innovation to the computationally creative. Each of these is briefly discussed following a brief summary of the volume.
David E. Goldberg
Backmatter
Metadaten
Titel
The Design of Innovation
verfasst von
David E. Goldberg
Copyright-Jahr
2002
Verlag
Springer US
Electronic ISBN
978-1-4757-3643-4
Print ISBN
978-1-4757-3645-8
DOI
https://doi.org/10.1007/978-1-4757-3643-4