Answers.Body: <p>If you have lots of rules then you should be able to come up with lots of heuristics for A*. If I were you I would try A* first, and come up with as many heuristics as I could. You can also use Deep Q learning. I don't think you want to just throw coordinates into a Deep Q network. You want a simpler representation. I would probably give the nodes symbolic identifiers like sparse matrices, integers or sigmoids, and then craft the loss function to reflect the actual cost of moving from node to node and ascribe a high cost to illegal moves.</p>
  
Answers.ContentLicense: CC BY-SA 3.0
Answers.CreationDate: 2018-03-09T07:07:32.840Z
Answers.LastActivityDate: 2018-03-09T07:07:32.840Z
Answers.UserDisplayName: Default picture
Body: <p>I have an industrial problem which I'm trying to cast as a Traveling Salesman problem (TSP) in 3D euclidian space. There are physical limitations which implies that some subpaths may or may not be valid based on simple rules. </p>
  
  <p>What algorithm is best to deal with the TSP given that there are rules/model/constraints?</p>
  
  <p>It could be done with Genetic algorithms for example, but the only way i see how to incorporate those rules is by including them somehow within the fitness function. But i feel there should be more suitable approaches.</p>
  
  <p>Would reinforcement Q-learning or other algorithms be more appropriate for a rule-based euclidian TSP?</p>
  
Comments.ContentLicense: CC BY-SA 3.0
Comments.CreationDate: 2017-08-11T15:11:07.170Z
Comments.Text: Probably depends if those rules mean you have O(nodes) recognition, O(nodes) neighbor generation, O(nodes) solution generation, or something else. (I say O(n) but I mean comparative complexity in general)
Comments.UserDisplayName: Harrichael
Comments.ContentLicense: CC BY-SA 3.0
Comments.CreationDate: 2017-12-17T13:25:53.097Z
Comments.Text: How many nodes does a typical problem have? Did you consider heuristics tailored to the specific problem?
Comments.UserDisplayName: BKE
Tags: <machine-learning><reinforcement-learning><genetic-algorithms><combinatorics>
Title: Traveling salesman problem variant: which algorithm to choose?
UserDisplayName: Oliver
ThreadText: # Traveling salesman problem variant: which algorithm to choose?
  
  (Asked by: username_0 on 2017-08-11)
  
  I have an industrial problem which I'm trying to cast as a Traveling Salesman problem (TSP) in 3D euclidian space. There are physical limitations which implies that some subpaths may or may not be valid based on simple rules.
  
  What algorithm is best to deal with the TSP given that there are rules/model/constraints?
  
  It could be done with Genetic algorithms for example, but the only way i see how to incorporate those rules is by including them somehow within the fitness function. But i feel there should be more suitable approaches.
  
  Would reinforcement Q-learning or other algorithms be more appropriate for a rule-based euclidian TSP?
  
  **Tags:** machine-learning, reinforcement-learning, genetic-algorithms, combinatorics
  > **Comments:**
  > **username_1**: Probably depends if those rules mean you have O(nodes) recognition, O(nodes) neighbor generation, O(nodes) solution generation, or something else. (I say O(n) but I mean comparative complexity in general)  
  > **username_2**: How many nodes does a typical problem have? Did you consider heuristics tailored to the specific problem?  
  
  ---
  
  ## 1 answers
  
  ### Answer by username_3 on 2018-03-09. Score: -1
  
  If you have lots of rules then you should be able to come up with lots of heuristics for A\*. If I were you I would try A\* first, and come up with as many heuristics as I could. You can also use Deep Q learning. I don't think you want to just throw coordinates into a Deep Q network. You want a simpler representation. I would probably give the nodes symbolic identifiers like sparse matrices, integers or sigmoids, and then craft the loss function to reflect the actual cost of moving from node to node and ascribe a high cost to illegal moves.
  
  
  ---
  
  