genetic algorithm Traveling Salesman Problem data representation (was: Scheduling with Genetic Algorithm) - Theory

Kent Paul Dolan wrote:
> "Mika Viljanen" <mika.viljanen{}iki.fifi.invalid> wrote:
> > Thijssss <t.stuurman{}> wrote:
>
> >> Before this assignment I create a GA solution to
> >> the traveling salesman problem, the chromosome
> >> for the TSP would look like
> >> '1,2,3,4,5,6,7,8,9,0,10,11'. So the length equals
> >> the amount of cities and the order of the cities
> >> be a possible solution (in length). So the
> >> bitstring contained the entire possible solution.
>
> > Just out of curiosity, how did you ensure the
> > chromosomes were valid (i.e. the possible
> > solutions were permutations of the city list so
> > that no individual city could appear twice on a
> > given solution)?
>
> I cannot answer for Herr Stuurman, but I can answer
> for myself, since I've also written a T.S. "solver"

There is just one further point on the travelling salesperson (you must
be more PC) and that is that it is one of the few NP hard problems
where solutions have ever been found that can be shown to be NP
complete.

The minimum distance is the sum of the distances of all the closest
cities. We can also calculate minimum distances assuming that we have a
particular permutation. You are required therefore to demonstrate that
all permutations + minimum disance exceed the didtance you have.
>
> http://www.well.com/user/xanthian/ja...vellerDoc.html
>
> in which I used the approach, standard for that
> problem, of using data considered as strings of
> integers, rather than data considered as strings of
> bits, and using initial population generating
> operations which create genomes as permutations of
> the integers 0 to N-1, and mutation operators and
> crossover operators which preserve invariant the
> property that the string of integers representing
> the genome is a permutation of the integers from 0
> to N-1.
>
> It turns out, after some work with the ideas, to be
> fairly "easy" (for personal definitions of "easy")
> to create many such "invariant preserving" mutation
> and crossover operators, [In a larger version of my
> T.S. solver than the one shown online, I have dozens
> of them] and, for me, that is much more successful
> than the alternative technique of using purely
> unintelligent mutation and crossover, and letting
> huge fitness penalties for invalid genomes weed out
> the huge majority of genomes created without regard
> for a validity invariant.
>
> FWIW
>
> xanthian.
>
>
>
> --
> Posted via Mailgate.ORG Server - http://www.Mailgate.ORG

On 1 Jun 2006 08:01:53 -0700, "Ian Parker" <ianparker2{}>
wrote:

>
>Kent Paul Dolan wrote:
>> "Mika Viljanen" <mika.viljanen{}iki.fifi.invalid> wrote:
>> > Thijssss <t.stuurman{}> wrote:
>>
>> >> Before this assignment I create a GA solution to
>> >> the traveling salesman problem, the chromosome
>> >> for the TSP would look like
>> >> '1,2,3,4,5,6,7,8,9,0,10,11'. So the length equals
>> >> the amount of cities and the order of the cities
>> >> be a possible solution (in length). So the
>> >> bitstring contained the entire possible solution.
>>
>> > Just out of curiosity, how did you ensure the
>> > chromosomes were valid (i.e. the possible
>> > solutions were permutations of the city list so
>> > that no individual city could appear twice on a
>> > given solution)?
>>
>> I cannot answer for Herr Stuurman, but I can answer
>> for myself, since I've also written a T.S. "solver"
>
>There is just one further point on the travelling salesperson (you must
>be more PC) and that is that it is one of the few NP hard problems
>where solutions have ever been found that can be shown to be NP
>complete.
>

The sentence above has no sense.

>The minimum distance is the sum of the distances of all the closest
>cities. We can also calculate minimum distances assuming that we have a
>particular permutation. You are required therefore to demonstrate that
>all permutations + minimum disance exceed the didtance you have.

The above sentence has no sense.

A.L.

"Ian Parker" <ianparker2{}> wrote:

> There is just one further point on the travelling
> salesperson (you must be more PC) and that is that
> it is one of the few NP hard problems where
> solutions have ever been found that can be shown
> to be NP complete.

> The minimum distance is the sum of the distances
> of all the closest cities. We can also calculate
> minimum distances assuming that we have a
> particular permutation. You are required therefore
> to demonstrate that all permutations + minimum
> disance exceed the distance you have.

Yes, but.

For traveling salesman problems whose known brute
force solution times (for every permutation, compute
its length, choose the shortest) on current hardware
exceed the heat death schedule for the universe
(10^100 years, which a problem with around 80 cities
will exceed), with _known_ correct solutions, a
genetic algorithm running on current hardware can
find such a correct solution in less than a minute.
The problem is that you cannot _guarantee_ that
performance.

That said, "cut and branch" solutions for the TSP
supposedly can check that a solution is the correct
one, in polynomial time, even though, I think, they
can't find that solution in polynomial time.

Given that 80 cities _should_ overwhelm current
hardware, and that the solution time for TSP is
factorial (worse than exponential) in the number of
cities, it is a bit astonishing that some problems
with tens of thousands of cites have been solved and
proved to be solved (the current record is Sweden's
24,978 cities, IIUC, seen here:
http://www.tsp.gatech.edu/index.html ).

HTH

xanthian.


--
Posted via Mailgate.ORG Server - http://www.Mailgate.ORG

"AL." <alewando{}ziuta66.com> wrote:

> The sentence above has no sense.
> The above sentence has no sense.

No, they make perfect sense to a worker
in the field, you are just too ignorant
of the subject matter to understand them,
which suggests rather strongly that you
refrain from making a fool of yourself
this way in the future in areas where you
have no expertise and are easily confused.

verb. sap.

xanthian.


--
Posted via Mailgate.ORG Server - http://www.Mailgate.ORG

On Thu, 1 Jun 2006 17:26:43 +0000 (UTC), "Kent Paul Dolan"
<xanthian{}well.com> wrote:

>"AL." <alewando{}ziuta66.com> wrote:
>
>> The sentence above has no sense.
>> The above sentence has no sense.
>
>No, they make perfect sense to a worker
>in the field, you are just too ignorant
>of the subject matter to understand them,
>which suggests rather strongly that you
>refrain from making a fool of yourself
>this way in the future in areas where you
>have no expertise and are easily confused.

No, they don't. Maybe they do, but must be tranlated into correct
English first.

On Thu, 1 Jun 2006 17:22:57 +0000 (UTC), "Kent Paul Dolan"
<xanthian{}well.com> wrote:


>
>For traveling salesman problems whose known brute
>force solution times (for every permutation, compute
>its length, choose the shortest) on current hardware
>exceed the heat death schedule for the universe
>(10^100 years, which a problem with around 80 cities
>will exceed), with _known_ correct solutions, a
>genetic algorithm running on current hardware can
>find such a correct solution in less than a minute.
>The problem is that you cannot _guarantee_ that
>performance.
>

And you cannot guarantee that your solution is "correct"

>That said, "cut and branch" solutions for the TSP
>supposedly can check that a solution is the correct
>one, in polynomial time, even though, I think, they
>can't find that solution in polynomial time.
>

Then how they find the solution that they check? From crystal ball?...

>Given that 80 cities _should_ overwhelm current
>hardware, and that the solution time for TSP is
>factorial (worse than exponential) in the number of
>cities, it is a bit astonishing that some problems
>with tens of thousands of cites have been solved and
>proved to be solved

Astonishing for you?...

A.L.

AL. wrote:
> "Kent Paul Dolan" <xanthian{}well.com> wrote:

>> For traveling salesman problems whose known brute
>> force solution times (for every permutation, compute
>> its length, choose the shortest) on current hardware
>> exceed the heat death schedule for the universe
>> (10^100 years, which a problem with around 80 cities
>> will exceed), with _known_ correct solutions, a
>> genetic algorithm running on current hardware can
>> find such a correct solution in less than a minute.
>> The problem is that you cannot _guarantee_ that
>> performance.

> And you cannot guarantee that your solution is
> "correct"

Apparently your incompetence reading English is very
intense indeed. Which part of "with _known_ correct
solutions" was too hard for you to understand?

It is perfectly simple to design traveling salesman
problems whose solution is obvious to a human eye,
but must still be found by an algorithm according to
that algorithm's design.

>> That said, "branch and cut" solutions for the TSP
>> supposedly can check that a solution is the
>> correct one, in polynomial time, even though, I
>> think, they can't find that solution in
>> polynomial time.

> Then how they find the solution that they check?
> From crystal ball?...

I suppose it is too much to expect that you would
be willing to chew your own food, say, by reading
the site with whose URL you had been provided?

>> http://www.tsp.gatech.edu/index.html

The solution which is checked is found by running
the Lin Kernigan _heuristic_ algorithm until it
converges to a solution.

http://www.akira.ruc.dk/~keld/research/LKH/

That solution is then checked for correctness.

http://www.tsp.gatech.edu/methods/opt/opt.htm

>> Given that 80 cities _should_ overwhelm current
>> hardware, and that the solution time for TSP is
>> factorial (worse than exponential) in the number
>> of cities, it is a bit astonishing that some
>> problems with tens of thousands of cites have
>> been solved and proved to be solved

> Astonishing for you?...

Apparently, as well as illiterate, you are also
innumerate, and thus incapable of understanding what
a feat that solution was. To achieve some less
innumerate understanding of how awesome that feat
is, why don't you, say, try to figure out how many
digits are in the brute force solution time, in
_years_, for the Swedish cities problem, run on a
2GHz laptop. When you have, get back to us.

If that's too hard for you, try to figure out how
many digits are in the engineering notation power
of ten _exponent_ for that solution time, and provide
that information here instead.

xanthian.

Kent Paul Dolan wrote:
> That said, "cut and branch" solutions for the TSP
> supposedly can check that a solution is the correct
> one, in polynomial time, even though, I think, they
> can't find that solution in polynomial time.
Are you certain about that? The actual NP-complete problem at the heart
of the Traveling Salesman Problem is "Is there a tour of length B or
less?" It seems odd to me that answering the question "Is this tour
optimal?" doesn't answer that question as well.


Jack Saalweachter

In <e5q045$e20$1{}mailhub227.itcs.purdue.edu> Jack Saalweachter <saalweachter{}purdue.edu> writes:

> Kent Paul Dolan wrote:
> > That said, "cut and branch" solutions for the TSP
> > supposedly can check that a solution is the correct
> > one, in polynomial time, even though, I think, they
> > can't find that solution in polynomial time.
> Are you certain about that? The actual NP-complete problem at the heart
> of the Traveling Salesman Problem is "Is there a tour of length B or
> less?" It seems odd to me that answering the question "Is this tour
> optimal?" doesn't answer that question as well.

Determining that a given tour of length L is optimal does of course
answer that question: yes if B >= L, and no if B < L. Determining that
it isn't optimal answers: yes if B >= L, and "don't know" if B < L.
So if B < L(T) for every we tour T we examine, we won't know the answer
to the decision problem until we examine a tour that the optimality
check says yes to.

Thus, being able to determine optimality in polynomial time does not
allow one to solve the classic decision problem in polynomial time,
because one may have to examine an exponential number of candidate
tours to find one that is optimal.

HTH,
David