mahout-user mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From Pavan K Narayanan <pavan.naraya...@gmail.com>
Subject Re: travelling salesman on Mahout
Date Mon, 13 Jan 2014 16:42:18 GMT
Thanks again Ted, for the link -- Just read a few pages and it is very
interesting.

Please may I ask why TSP has been removed from Mahout. Its just that I
see discussions about distributed Genetic Algorithm and other
evolutionary algorithms being implemented in distributed environment
and feel it would be possible to implement in Mahout as well.

For example, the initial population generation and evaluating the best
initial route could be done in 'n' nodes using 'n' map phases and we
could have a reduce phase where the best of initial route from 'n'
nodes could be taken for further treatment like mutation, etc... What
are your thoughts on this?

Regards,
Pavan

On 13 January 2014 07:24, Ted Dunning <ted.dunning@gmail.com> wrote:
> For what it is worth, R has some really nice interfaces for the standard
> TSP solvers and several sample data sets.  That can really help you in your
> testing.
>
> See http://cran.r-project.org/web/packages/TSP/vignettes/TSP.pdf
>
>
>
> 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
View raw message