mahout-user mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From Ted Dunning <ted.dunn...@gmail.com>
Subject Re: travelling salesman on Mahout
Date Sun, 12 Jan 2014 20:18:39 GMT
I haven't seen that part of the cookbook yet either.  But the package that
it depends on has been removed from Mahout.

Evolutionary algorithms will generally be much better implemented on a
framework that supports iteration such as Giraph or Spark.  For TSP, the
natural representation would be to distribute members of the potential
solution population across the cluster.

If you choose to go with the evolving partial solution approach, you will
need to work out some way of compensating for length.  You want to have
different versions of partial solutions competing against each other, but
you also want long solutions to compete well against short solutions.  One
way to do that is to have "sponsors".  These are long solutions whose
points are a super set of a shorter solution.  Sponsors are used to
estimate the cost of adding the missing cities from the shorter solution so
that long and short solutions have a roughly equal playing field.




On Sun, Jan 12, 2014 at 1:20 AM, Pavan K Narayanan <
pavan.narayanan@gmail.com> wrote:

> Thanks Ted for your response. Any use cases where the evolutionary
> algorithm used apart from tsp ?  I got to know about a "mahout
> cookbook" that has a receipe walkthrough on implementing TSP on
> mahout. The book is not released in my country yet, but I would like
> to find out:
>
> which version of Mahout is being used?
> is there any results available on the internet for solving benchmark
> TSP problems using Mahout?
>
> I am not depending on Mahout to solve planning problems but I would
> like to know how the algorithm works in mapreduce paradigm and
> specifically whether the node arc incidence matrix has been split for
> purpose of mapreduce during run time. (I am not concerned about the
> obtaining optimal solutions from Mahout)
>
>
>
> On 11 January 2014 00:46, Ted Dunning <ted.dunning@gmail.com> wrote:
> > TSP is generally solved using a number of heuristics guiding a randomized
> > search.  Mahout has essentially no provision for helping with this.
> >
> > If you want a quick and dirty solution, I would recommend something like
> an
> > evolutionary algorithm in which you have segments that self-assemble or
> > split with the parameters controlling the assembly and splitting subject
> to
> > auto-mutation.
> >
> > Conventional genetic algorithms should also work reasonably well, but you
> > will almost certainly have to include some auto-evolution.
> >
> > Mahout does have a directed-step evolutionary algorithm, but it is not
> > suitable for discrete problems such as TSP.
> >
> >
> >
> > On Fri, Jan 10, 2014 at 1:11 AM, Pavan K Narayanan <
> > pavan.narayanan@gmail.com> wrote:
> >
> >> Hi
> >>
> >> Has anyone tried solving travelling salesman problem using Mahout?
> >> (could be any version) . If yes, I would like to know,
> >>
> >> 1. What is the format of input data? is it txt file or csv file or any
> >> other format.
> >> 2. do you have to divide the input data into so chunks? for example,
> >> if your tsp has 10k cities and you divided that into two 5k cities
> >> problems. (I understand running on hadoop will divide the data into
> >> chunks of 64mb or any other user defined, but was there any external
> >> division.
> >>
> >> I have not solved TSP using Mahout. Would appreciate if anyone could
> >> walk me thro the process of solving tsp.
> >>
> >> thanks
> >>
>

Mime
  • Unnamed multipart/alternative (inline, None, 0 bytes)
View raw message