Databases
StackOverflow2013
Postsdbo
POWhy does adding Crossover to my Genetic Algorithm gives me worse results?
 

Note that there are some explanatory texts on larger screens.

plurals
  1. POWhy does adding Crossover to my Genetic Algorithm gives me worse results?
    primarykey
    data
    text
    <p>I have implemented a Genetic Algorithm to solve the Traveling Salesman Problem (TSP). When I use only mutation, I find better solutions than when I add in crossover. I know that normal crossover methods do not work for TSP, so I implemented both the <a href="http://www.permutationcity.co.uk/projects/mutants/tsp.html" rel="nofollow noreferrer">Ordered Crossover</a> and the <a href="http://www.ceng.metu.edu.tr/~ucoluk/research/publications/tspnew.pdf" rel="nofollow noreferrer">PMX Crossover</a> methods, and both suffer from bad results. </p> <p>Here are the other parameters I'm using:</p> <p><strong>Mutation</strong>: Single Swap Mutation or Inverted Subsequence Mutation (<a href="https://stackoverflow.com/questions/1544055/rossover-operation-in-genetic-algorithm-for-tsp">as described by Tiendil here</a>) with mutation rates tested between 1% and 25%.</p> <p><strong>Selection</strong>: Roulette Wheel Selection</p> <p><strong>Fitness function</strong>: 1 / distance of tour</p> <p><strong>Population size</strong>: Tested 100, 200, 500, I also run the GA 5 times so that I have a variety of starting populations.</p> <p><strong>Stop Condition</strong>: 2500 generations</p> <p>With the same dataset of 26 points, I usually get results of about 500-600 distance using purely mutation with high mutation rates. When adding crossover my results are usually in the 800 distance range. The other confusing thing is that I have also implemented a very simple Hill-Climbing algorithm to solve the problem and when I run that 1000 times (faster than running the GA 5 times) I get results around 410-450 distance, and I would expect to get better results using a GA.</p> <p>Any ideas as to why my GA performing worse when I add crossover? And why is it performing much worse than a simple Hill-Climb algorithm which should get stuck on local maxima as it has no way of exploring once it finds a local max?</p>
    singulars
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. PTQuestion
    1. USCommunity
    1. USMahlerFive
    plurals
    1. PL
      singulars
      1. LTLinked
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. PO
      singulars
      1. PTAnswer
    2. PO
      singulars
      1. PTAnswer
    3. PO
      singulars
      1. PTAnswer
    1. VO
      singulars
      1. POWhy does adding Crossover to my Genetic Algorithm gives me worse results?
      1. This table or related slice is empty.
      1. VTUpMod
    2. VO
      singulars
      1. POWhy does adding Crossover to my Genetic Algorithm gives me worse results?
      1. This table or related slice is empty.
      1. VTUpMod
    3. VO
      singulars
      1. POWhy does adding Crossover to my Genetic Algorithm gives me worse results?
      1. This table or related slice is empty.
      1. VTUpMod
    1. This table or related slice is empty.
 

Querying!

 
Guidance
A row detail

Detail views are divided into sections. All the information in the data section comes from columns in the selected row. The other sections display data from other, related rows.

Related data can be related in a to-one or a to-many fashion. Captions of data related in a to-many fashion link to a list view showing a filtered view of the table.

Try moving around until you find a non-empty to-many entry and click on the label to get to one. You can move back to the root by clicking on the database name in the header.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload