From user-return-19173-apmail-mahout-user-archive=mahout.apache.org@mahout.apache.org Sun Jan 12 20:20:05 2014 Return-Path: X-Original-To: apmail-mahout-user-archive@www.apache.org Delivered-To: apmail-mahout-user-archive@www.apache.org Received: from mail.apache.org (hermes.apache.org [140.211.11.3]) by minotaur.apache.org (Postfix) with SMTP id 50087107C6 for ; Sun, 12 Jan 2014 20:20:05 +0000 (UTC) Received: (qmail 89609 invoked by uid 500); 12 Jan 2014 20:19:41 -0000 Delivered-To: apmail-mahout-user-archive@mahout.apache.org Received: (qmail 89574 invoked by uid 500); 12 Jan 2014 20:19:38 -0000 Mailing-List: contact user-help@mahout.apache.org; run by ezmlm Precedence: bulk List-Help: List-Unsubscribe: List-Post: List-Id: Reply-To: user@mahout.apache.org Delivered-To: mailing list user@mahout.apache.org Received: (qmail 89566 invoked by uid 99); 12 Jan 2014 20:19:35 -0000 Received: from athena.apache.org (HELO athena.apache.org) (140.211.11.136) by apache.org (qpsmtpd/0.29) with ESMTP; Sun, 12 Jan 2014 20:19:35 +0000 X-ASF-Spam-Status: No, hits=1.5 required=5.0 tests=HTML_MESSAGE,RCVD_IN_DNSWL_LOW,SPF_PASS X-Spam-Check-By: apache.org Received-SPF: pass (athena.apache.org: domain of ted.dunning@gmail.com designates 209.85.213.177 as permitted sender) Received: from [209.85.213.177] (HELO mail-ig0-f177.google.com) (209.85.213.177) by apache.org (qpsmtpd/0.29) with ESMTP; Sun, 12 Jan 2014 20:19:30 +0000 Received: by mail-ig0-f177.google.com with SMTP id k19so1103380igc.4 for ; Sun, 12 Jan 2014 12:19:09 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20120113; h=mime-version:in-reply-to:references:from:date:message-id:subject:to :content-type; bh=axNFCygPJQjfBvdgY7DBQm43frVvSBLqCXDiXVNDFEI=; b=G5o1b9TV/jDOJLBAs+NTNuWvL33wV1K6gICUDC15o4f8ZMfan4JKJk4E7Q8hjq/KPZ MqHybv1UnvHC5VcVKJHVCBlGDwEvuK7YhRaLmAH+hx+K6UJB88jVfmImO4L9/dLK/LAb CZp+R/ZkbyXnmXoioLWj6EfllT3DtrvhgvpzUhU8g+GLnndof2R2BujKHFn9E+0YHD6r 1oPL834CokR6ROUPr0DbqgIVoWUtgIaz4YKBQQLKkxLpNFp68g+lHRwZc8Yj9HvpfOKF Orc4bwJ2bqZ8Ez2m0sz07510YD09wdgW8cdNtB4bCINJsdJrzJ7Cw5q1rF/pVwADW5zc nmSA== X-Received: by 10.42.208.211 with SMTP id gd19mr17958891icb.15.1389557949548; Sun, 12 Jan 2014 12:19:09 -0800 (PST) MIME-Version: 1.0 Received: by 10.64.87.231 with HTTP; Sun, 12 Jan 2014 12:18:39 -0800 (PST) In-Reply-To: References: From: Ted Dunning Date: Sun, 12 Jan 2014 12:18:39 -0800 Message-ID: Subject: Re: travelling salesman on Mahout To: "user@mahout.apache.org" Content-Type: multipart/alternative; boundary=20cf303ea90afa4d0f04efcbab60 X-Virus-Checked: Checked by ClamAV on apache.org --20cf303ea90afa4d0f04efcbab60 Content-Type: text/plain; charset=UTF-8 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 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 > >> > --20cf303ea90afa4d0f04efcbab60--