More Debate, Please!
“… there are many issues in computing that inspire differing
opinions. We would be better off highlighting the differences
rather than pretending they do not exist”
–Moshe Y. Vardi
In an article entitled “More Debate, Please!”, in the January, 2010 issue of Communications of the ACM, Moshe Y. Vardi, editor-in-chief of Communications, writes:
`Vigorous debate, I believe, exposes all sides of an issue—their strengths and weaknesses. It helps us reach more knowledgeable conclusions. To quote Benjamin Franklin: “When Truth and Error have fair play, the former is always an overmatch for the latter.”’[1]
Vardi goes on to say that as he solicited ideas for the 2008 relaunch of Communications, he was frequently told to keep controversial topics front and center. “Let blood spill over the pages of Communications,” a member of a focus group jokingly urged [1].
In my attempts, to date, to publish my doctoral research—work that ultimately became chapters two and three of my dissertation—in evolutionary computation journals, I found the sentiments expressed by Vardi to be in short supply. The reviewers seemed much more invested in not rocking the boat than in fostering a climate in which prevailing assumptions can be challenged, and alternate ideas expressed transparently. They seemed, in short, to be inured to the poverty of the field’s foundations, and, for the most part, had little tolerance for someone with a bone to pick with the status quo. “Fall in line, or get rejected,” was the overarching message.
One way this unfortunate state of affairs may be addressed is through the institution of a forum like the Point/Counterpoint section introduced to Communications by Vardi in 2008—a forum where the various controversies that mark our field are periodically featured, and the different sides of each controversy given, as Benjamin Franklin put it, fair play. There are several contentious topics in EC. Tapped correctly, many of these topics can be powerful vehicles for learning—not just about the workings of evolutionary algorithms, but, also, about the workings of a vibrant intellectual community. Right now, instead of vigorous, open, ongoing debates in the EC literature, uneasy truces prevail. The community, by and large, steps around the the really big points of contention. Researchers talk past each other to niche audiences. And, if my experience is anything to go by, new lines of criticism, and new modes of analysis are hastily dismissed.
In the absence of a written record of ongoing controversies, new entrants to the field will not have access to the various positions involved. Pressed for time, and confronting the reality of “publish or perish”, most will fall back on the opinions and practices of their advisors. It doesn’t take much to see that in environments like this, opportunities for learning and advancement will frequently be missed.
A forum for open, ongoing, collegial debate would bring awareness, and transparency to the controversies in our field. It would also (one hopes) inculcate a more welcoming attitude toward alternate approaches, conclusions, and critiques.
Two topics for debate: (No points for guessing where my sympathies lie on these issues)
EC Theory and First Hitting Time: Is it problematic that so much contemporary theoretical work in EC focuses on “first hitting time”, i.e., the number of fitness evaluations required to find a global optimum? Do we look at first hitting time only because there currently isn’t a well developed, and generally accepted theoretical framework for examining adaptation (the generation of fitter points over time)? If so, isn’t the study of first hitting time a lot like the proverbial search for one’s house keys under the light of a street lamp just because it happens to be dark in one’s house?
The Building Block Hypothesis: Can the building block hypothesis be reconciled with the widely reported utility of uniform crossover? If yes, how? If no, can we—more to the point, should we—be comfortable with this knowledge given the considerable influence of the building block hypothesis on contemporary evolutionary computation research?
What other topics have been under-addressed in the evolutionary computation literature? Leave a comment with your opinion, or a link to your own blog post.
[1] Moshe Y. Vardi. More debate please!, In Communications of the ACM 53(1):5, 2010
Dissertation Deposition
I deposited my dissertation today.
Click here to see the final version (single spaced for easy reading).
Back to the Future: A Science of Genetic Algorithms
From the preface to my dissertation:
The foundations of most computer engineering disciplines are almost entirely mathematical. There is, for instance, almost no question about the soundness of the foundations of such engineering disciplines as graphics, machine learning, programming languages, and databases. An exception to this general rule is the field of genetic algorithmics, whose foundation includes a significant scientific component.
The existence of a science at the heart of this computer engineering discipline is regarded with nervousness. Science traffics in provisional truth; it requires one to adopt a form of skepticism that is more nuanced, and hence more difficult to master than the radical sort of skepticism that suffices in mathematics and theoretical computer science. Many, therefore, would be happy to see science excised from the foundations of genetic algorithmics. Indeed, over the past decade and a half, much effort seems to have been devoted to turning genetic algorithmics into just another field of computer engineering, one with an entirely mathematical foundation.
Broadening one’s perspective beyond computer engineering, however, one cannot help wondering if much of this effort is not a little misplaced. Read the rest of this entry »
The Fundamental Problem with the Building Block Hypothesis (new manuscript)
Abstract: Skepticism of the building block hypothesis has previously been expressed on account of the weak theoretical foundations of this hypothesis and anomalies in the empirical record of the simple genetic algorithm. In this paper we focus on a more fundamental cause for skepticism—the extraordinary strength of some of the assumptions undergirding the building block hypothesis. As many of these assumptions have been embraced by the designers of so called “competent” genetic algorithms, our critique is relevant to an appraisal of such algorithms. We argue that these assumptions are too strong to be acceptable without additional evidence. We then point out weaknesses in the arguments that have been provided in lieu of such evidence.
New manuscript now at arXiv
My latest manuscript is now posted at arXiv.
The Dubious History of the Building Block Hypothesis
From the introduction of a manuscript that I recently submitted for review
Perceptions of the abilities and limitations of the SGA (and hence the kinds of problems that it can and cannot solve) have been heavily influenced by a theory of adaptation called the building block hypothesis (Goldberg, 1989; Mitchell, 1996; Holland, 1975, 2000). This theory of adaptation has its genesis in the following idea: maybe small groups of closely located co-adaptive alleles propagate within an evolving population of genomes in much the same way that single adaptive alleles do in Fisher’s theories of sexual evolution (Fisher, 1958). Holland called such groups of alleles building blocks. This idea can be taken one step further: maybe small groups of co-adaptive building blocks propagate within an evolving population of genomes in much the same way that single building blocks do. Such groups can be thought of as higher-level building blocks. Pursuing this idea to the fullest extent, maybe Read the rest of this entry »
Critique of the Compositional Paradigm
Adaptation in selecto-recombinative genetic systems is widely believed to occur by the recombination of pre-adapted genetic material. This belief is at the core of the paradigm under which most GA and all EDA research currently occurs. It underlies the construction of several new varieties of genetic algorithms that purportedly work by combining pre-adapted genetic material in some sophisticated way (e.g. cohort GAs, messy GAs, LLGA, ECGA, BOA, hBOA, etc.).
In this paradigm, each post-selection population is thought to harbor “good” genetic material. Recombination operators, and estimation of distribution procedures, are thought drive adaptation by composing this material to produce good or better individuals in the next generation.When adaptation stalls it is thought to be because “good” genetic material is unavailable, or because recombination of this material was not performed effectively.
Let us call this general set of beliefs the Compositional Paradigm. This paradigm draws its support from Holland’s Building Block Hypothesis. Its widespread acceptance in the GA community signals Read the rest of this entry »
