Re: Path from a walk in a graph.

On 17 Mar, 18:51, riderofgiraffes <mathforum....@xxxxxxxxxxxxxx>
wrote:
Your usage of the term "genetic" in this context does
not match my understanding, nor that of my colleagues.
In what sense is it genetic? Help me to understand.

A genetic algorithm is the knee jerk approach to NP
hard problems like the travelling salesperson.

This is an unreasonable and emotionally laden statement.

No the algorithm I have given for the solution of the walk is
polynomial. The "genes" I am talking about reflect elements of the
permutation group. We can divide up permutations in a number of ways.

The basic principle of the genetic algorithm is to take a non optimal
solution. This solution is then presented in the form of a series of
variables which we can loosely describe as being genes. In the case of
graphs these will be permutation subgroups. The travelling salesperson
is solved by permutation. The travelling salesperson has been proved
to be NP complete. That is we know we have the shortest route. NP
completeness is proved by showing that no permutation or set of
permutations can produce a better solution. In general genetic
algorithms do not produce NP complete solutions.

The question of the effectiveness of GAs in general is an interesting
one. GAs are used quite often where they should not be. For solving
problems which Calculus would solve far more efficiently. I am now
going to ask a Fields Medal type of question. If you have a ball
hidden somewhere there is no way of finding it other than to search
through all the possible locations systematically. If you work by
survival of the fittest (as I said analogue fitness is sinply another
word for Calculus) you are not going through every possibility.
Clearly there must be some logic which is allowing the GA to "home
in". How do you characterize this? Lets say you are sitting people
next to one and other round a dinner table. You know some of them are
friends. How do you you sit them round the dinner table. - GA with
genes as permutation subgroups and fitness defined however you want it
defined. This works because evaluation of fitness will in general
correspond to an evaluation of subgroups. ie. friends sitting next to
one and other form a complete subgroup. Question - can we solve the
problem without a GA?
This problem is a polynomial one, problems should
be solved polynomially if you can.


The algorithm given above, of removing loops, is a
polynomial algorithm - it has complexity O(n^2). I do
not understand why you think otherwise, nor why you
label it "genetic".

I don't think it is. You think it is, but I say the solution is
obtained by INSERTING and then removing loops. And you don't know when
to stop!

In fact what you are suggesting is very like the flagellum of a
protozoa which has 50 genes controlling it any one of which will cause
it not to work. This has been dubbed "irreducible complexity" by the
Discovery Insitute. In fact it evolved with more genes and then
steadily removed them. Suppose we inserted some more loops in the
protozoa and then reduced them. Could we get to 49 genes? I don't
know. It is inevitable that you will arrive at a situation where 1
gene will destroy a flagellum, it is not obvious that we have NP
completeness. In fact I feel instinctively that we don't.
Let me now put a spanner in and propose another
(harder) problem. Here we are simply walking.
Suppose what we need to do is write a program
and connect up inputs of subroutines. Here we not
only need to walk from a to b, we need the network
to be completely connected. This must in the first
instance be genetic. We walk from a to b and then
walk again filling in the vacant inputs.

What?

Perhaps I should not have posted this. It is a little bit away from
the start of the discussion. However it is


.

Relevant Pages

  • Some PERL code for detecting/displaying "toroidal" trees "invariant under a half-turn
    ... This algorithm will be reviewed by Dr. David Wagner ... Such trees can be termed "invariant" under a half-turn ... not display "the same" oDAG as the first, ... and detects whether this permutation will yield a tree ...
    (sci.math.num-analysis)
  • Re: Challenae question for mathematician
    ... problems relating to permutation groups. ... adjacent books. ... called "bubble sort" - it is a quadratic time algorithm, ... efficient as a sorting method - efficient sorting is O. ...
    (sci.math)
  • Some PERL code for detecting/displaying "toroidal" trees " invariant under a half-tur
    ... This algorithm will be reviewed by Dr. David Wagner ... "oDAGs " invariant under a half-turn. ... Such trees can be termed "invariant" under a half-turn ... and detects whether this permutation will yield a tree ...
    (sci.math)
  • Imperfect random permutation of 2^k elements
    ... given that one has available the Algorithm P of ... from the given random bit sequence real-valued random numbers ... to any other permutation by applying to it a certain permutation ... It may be noted that the dynamically varying S-box of RC4 is ...
    (sci.crypt)
  • Re: permutations and combinations
    ... > Right now I'm using a string, sorting it and passing it repeated into ... In this article he defines a generic algorithm: ... for_each_permutation calls fn for each permutation of last-first items ... The printing functor keeps a simple state which is just the line number. ...
    (comp.lang.cpp)