Re: GA ver. Parallel tempering

On Fri, 15 Sep 2006 02:40:04 +0000, Kent Paul Dolan wrote:
"Lionel B" <me@xxxxxxxxxxx> wrote:

To clarify the point I was making: since both SA and GAs are serial
algorithms when implemented on a serial machine,

No.

My point of view is as follows: I assume that for (non-trivial) search
spaces, the bulk of processing time will be spent in evaluating potential
solutions; that is, I ignore the overhead of the implementation of the
algorithm itself [of course this may not be supportable for search spaces
where evaluation is computationally cheap; I explicitly exclude such
situations].

Thus I take the time spent by an algorithm in evaluating solutions as a
basis for algorithm comparison (which is what this thread is about). It is
with respect to this comparison criterion that I make the claim that "both
SA and GAs are serial algorithms when implemented on a serial machine"
since on a serial machine a GA *is* essentially a serial algorithm, in the
sense that evaluations are of necessity performed serially. I qualify this
with "essentially" because one might, of course, interleave evaluations
(that is, artificially multi-task them). But even in this case, the
processing time for evaluations will be much the same as if evaluations
were performed truly in serial.

You are confusing how the _arithmetic_ is done, serially for both, with
how the _search_ is done, in serial for simulated annealing, in parallel
for genetic algorithms.

/.../

So I really *am* talking about "search" rather than arithmetic. The
"inherent" difference between serial algorithms such as SA, say, and
parallel algorithms such as GAs and parallel tempering is that in the
former we *must* evaluate one potential solution before the next potential
solution may be constructed, while in the latter this may not be
necessary. I don't think we disagree there. My central argument, however,
is that if we are constrained to evaluate solutions serially then this
inherent difference makes *no* difference to comparison of algorithm
efficiency on the basis of total evaluation time.

John H. Holland, parent of genetic algorithms, explained the _inherent_
parallelism of genetic algorithms

I am quite familiar with John Holland's work and I don't believe he
explained any such thing. Let's examine the passage you quote:

The genetic algorithm exploits the
higher-payoff, or "target," regions of the
solution space, because successive generations
of reproduction and crossover produce increasing
numbers of strings in those regions. The
algorithm favors the fittest strings as parents,
and so above-average strings (which fall in
target regions) will have more offspring in the
next generation.

Suppose we encode solutions for SA as strings, in the same way as for
the GA. Then:

The SA algorithm exploits the higher-payoff, or "target" regions of
the solution space, because successive iterations [of preferential
selection of higher fitness "offspring" strings] increase the probability
of sampling strings in those regions. The algorithm favors the fittest
strings as the parent [i.e. the current string], and so an above-average
string (which falls in target regions) will have more offspring [in fact
will have the only offspring] in the next iteration.

Indeed, the number of strings in a given region
increases at a rate proportional to the
statistical estimate of that region's fitness.

SA: Indeed, the probability of sampling a string in a given region
increases at a rate proportional to the statistical estimate of that
region's fitness [ok, probably not quite literally, but then neither is it
exactly so in many modern GA variants either].

A statistician would
need to evaluate dozens of samples from thousands or millions of
regions to estimate the average fitness of each region. The genetic
algorithm manages to achieve the same result with far fewer strings
and virtually no computation.

This is just bogus.

The key to this rather surprising behavior is the fact that a single
string belongs to all the regions in which any of its bits appear. For
example, the string 11011001 is a member of regions 11****** (where
the * indicates that a bit's value is unspecified), 1******1, **0**00*
and so forth.

Ditto for SA.

The largest regions-those
containing many unspecified bits-will typically
be sampled by a large fraction of all the
strings in a population.

For SA: The largest regions - those containing many unspecified bits -
will typically be sampled by a large fraction of all strings created
during some given period [a period, say, during which as many strings are
sampled as there are strings in the GA population].

Thus, a genetic
algorithm that manipulates a population of a few
thousand strings actually samples a vastly
larger number of regions.

Thus a SA algorithm that evaluates a few thousand strings actually
samples a vastly larger number of regions.

This implicit
parallelism gives the genetic algorithm its
central advantage over other problem-solving
processes.

This implicit parallelism [?!] gives the SA algorithm its central advantage
over other problem-solving processes.

Sorry, I don't buy this.

Later, Holland added his "schema theorem" which showed just how
much faster than "serial" a GA can search:

Don't even get me started...

All of this has been known now for a very long time; this kind of
confusion shouldn't still be occurring in comp.ai.genetic.

I sincerely wish it weren't "known". I think Holland's ideas on GAs have
perverted the course of GA research for decades. It's perfectly
understandable that they should cause confusion; they are confused.

--
Lionel B
.

Relevant Pages

  • Re: Best Job Skill --> .NET or Java
    ... strings, ... But the same basic brute-force algorithm was ... It compiled a histogram of trigrams, ... finds one random trigram that is unique, it expands that one, ...
    (comp.programming)
  • Re: How to efficiently determine if a string contains any one of many strings
    ... If you are looking to apply an algorithm similar to determining what is ... the algorithm that is used in most heuristic spam filters. ... kinds of classifications lend themselves to searches for string literals: ... Of course, assuming more input strings to match, you'd have a lot more ...
    (microsoft.public.dotnet.languages.csharp)
  • Re: Data mining algorithm
    ... the "best" descriptive strings for data. ... That sounds like the first step of a compression algorithm. ... In a similar data set this column will show similar repetativeness at ...
    (comp.programming)
  • Re: Reversing a number
    ... )> Lemme ask you a question: Suppose I have an algorithm that solves the ... )> Return the base-10 digits of the input number, ... limited the problem space to specific strings and use numbers to ... I'm not working with numerals. ...
    (comp.programming)
  • Re: Factorisation algorithms
    ... general integer factorisation algorithm? ... Knuth cites John Douglas Dixon for an algorithm with a running time proven ... if the processing time for an arithmetic operation is ... -- Microsoft voice recognition live demonstration ...
    (sci.math)