Re: Path from a walk in a graph.
- From: riderofgiraffes <mathforum.org@xxxxxxxxxxxxxx>
- Date: Mon, 19 Mar 2007 11:59:56 EDT
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.
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.
Not necessarily. I have used GAs on proven NP-complete
problem, and in some cases the "genes" were not
permutation subgroups.
However, moving on ...
The travelling salesperson is solved by permutation.
Not necessarily - there are other approaches.
The travelling salesperson has been proved to be
NP complete. That is we know we have the shortest
route.
What?
NP completeness is proved by showing that no
permutation or set of permutations can produce a
better solution.
Wrong. Absolutely wrong. NP-completeness is proved
by showing that some every instance of an NP problem
can be reduced to an instance of the alleged NP-complete
problem. There are short-cuts, such as reducing a
known NP-complete problem, but it essence you have to
show that every NP problem can be reduced to the problem
in question.
In general, genetic algorithms do not produce
NP complete solutions.
I assume you mean "optimal solutions to instances of
NP-complete problems."
The question of the effectiveness of GAs in general
is an interesting one.
I have referred a paper that shows that they are
always exponential. It showed they are equivalent
to certain types of simulated annealing, and then
showed that SA is reducable to certain types of
percolation problems, which are then shown to be
exponential.
GAs are used quite often where they should not be.
Yes. They are often used because they are convenient
and quick, and the answers they give are good enough.
Sometimes exact answers take more work by people. If
you were in industry you would know that sometimes
getting a computer to spend many hours finding a near
enough solution is more cost effective than having
people deriving exact solutions.
That said, I actually agree that GAs are sometimes
used when there are better techniques and options.
I am now going to ask a Fields Medal type
of question.
GAs and SA work when there is some sort of "slope"
through the very high dimensional space that lets
a system hill-climb. I used this frequently in
various forms of optimisation. For a given problem
Hill-climbing, GAs and SAs all either work, or don't.
The problems where they work are "globally smooth"
in some sense.
Shame I can't get a Fields Medal, I'm over 40.
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.
Sorry, but can you quote where loops are inserted?
Here, let me help you by quoting the algorithm.
Alg> If a walk (a_1..... a_n) contains two
Alg> repeated vertices a_i=a_j (for i<j), then
Alg> you can construct a new and shorter walk
Alg> (a_1..a_i,a_(j+1)..a_n) by removing a cycle
Alg> from the original walk.
Alg> You can repeat this process you until you
Alg> get a walk with no repeated vertices.
Where are loops inserted?
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.
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.
It seems that your understanding of NP-completeness
is significantly different from mine. I've written
papers about it, and deal with NP-complete problems
and near solutions to them regularly as a part of
my business. I'll read with some interest what you
write about it, and your understanding, but I have
no response to your comments about the evolution of
protozoa.
.
- Follow-Ups:
- Re: Path from a walk in a graph.
- From: Ian Parker
- Re: Path from a walk in a graph.
- References:
- Re: Path from a walk in a graph.
- From: Ian Parker
- Re: Path from a walk in a graph.
- Prev by Date: A partial differential equation problerm
- Next by Date: Calculus II proof 1
- Previous by thread: Re: Path from a walk in a graph.
- Next by thread: Re: Path from a walk in a graph.
- Index(es):
Relevant Pages
|
