Re: TSP in CL &/or Screamer


Drew Krause schrieb:
> Hello, I've been searching for Lisp code to the Traveling Salesman
> Problem, but it looks like this problem might be a favorite classroom
> assignment -- so no luck.
>
> I'm more interested in using the algorithm than the (undoubtedly worthy)
> exercise of developing it. In particular, I'd like to add a constraint
> that allows me to choose the starting and ending 'cities'.
>
> Any help appreciated. Thanks!

Yes this is indeed a common classroom assignment. I've developed and
used TSP optimizers in CL using genetic algorithms (GA), simulated
annealing (SA) and treshold accepting (TA). The most difficult part
using genetic algorithms here is to make them running non-consing per
generation. SA or TA are easier to implement and works quite well for
the TSP. TA is, in my personal experience, faster and leads to better
results than SA. As mutation operator (in TA and GA) I either reversed
a randomly chosen segment of the path or swapped the positions of two
cities in the whole path (both operations chosen randomly per
generation). For the crossover in GA I used the so called
"order-crossover" which crosses two paths by randomly selecting
segments in both, applying the order constraints in those segments to
the other path and fix up both paths by removing double cities from the
end. I wrote a CAPI user interface around all those stuff so that I
can view the progress of the optimization and to manually choose
different parameters using sliders while the optimization is running.

I hope this is of any help to you,

ciao,
Jochen Schmidt

.

Relevant Pages

  • Re: design of analog circuits using genetic algorithm
    ... using optimizers (genetic algorithms or more traditional ones) to *tweak* ... simulated annealing codes though fun to watch on toy problems. ... Filter design is one case where diddling individual ... doing a linear or nearly linear optimization, or you start with a decent guess. ...
    (sci.electronics.design)
  • Re: design of analog circuits using genetic algorithm
    ... And so does circuit design. ... using optimizers (genetic algorithms or more traditional ones) to *tweak* ... Have you done genetic optimization of circuit values? ... simulated annealing codes though fun to watch on toy problems. ...
    (sci.electronics.design)
  • Re: Even Blinder Optimization
    ... The Kalman solution is optimal when your model matches reality well. ... Hence, the seat-of-the-pants tuning. ... I'm using blind optimization to find the best tuning parameters, to make the Kalman perform as best as it can. ... Has anyone used genetic algorithms for optimization? ...
    (comp.arch.embedded)
  • Re: std::partition
    ... segmented sequence I mean something which is split into some lower level ... actually represented by an array of subsequences, i.e. an array of segments. ... The problems with these sequences is that iterators typically ... The idea of the optimization is rather simple: ...
    (comp.lang.cpp)
  • Textbook
    ... I'm taking a graduate course in genetic algorithms this fall and we have ... been assigned the textbook "Genetic Algorithms in Search, Optimization, and ... Machine Learning" by David E. Goldberg. ...
    (comp.ai.genetic)