Databases
StackOverflow2013
Postsdbo
POGenetic Algorithm Sudoku - optimizing mutation
 

Note that there are some explanatory texts on larger screens.

plurals
  1. POGenetic Algorithm Sudoku - optimizing mutation
    primarykey
    data
    text
    <p>I am in the process of writing a genetic algorithm to solve Sudoku puzzles and was hoping for some input. The algorithm solves puzzles occasionally (about 1 out of 10 times on the same puzzle with max 1,000,000 iterations) and I am trying to get a little input about mutation rates, repopulation, and splicing. Any input is greatly appreciated as this is brand new to me and I feel like I am not doing things 100% correct.</p> <p>A quick overview of the algorithm</p> <p>Fitness Function</p> <p>Counts the number of unique values of numbers 1 through 9 in each column, row, and 3*3 sub box. Each of these unique values in the subsets are summed and divided by 9 resulting in a floating value between 0 and 1. The sum of these values is divided by 27 providing a total fitness value ranging between 0 and 1. 1 indicates a solved puzzle. </p> <p>Population Size: 100</p> <p>Selection:</p> <p>Roulette Method. Each node is randomly selected where nodes containing higher fitness values have a slightly better chance of selection</p> <p>Reproduction: Two randomly selected chromosomes/boards swap a randomly selected subset (row, column, or 3*3 subsets) The selection of subset(which row, column, or box) is random. The resulting boards are introduced into population.</p> <p>Reproduction Rate: 12% of population per cycle There are six reproductions per iteration resulting in 12 new chromosomes per cycle of the algorithm. </p> <p>Mutation: mutation occurs at a rate of 2 percent of population after 10 iterations of no improvement of highest fitness. Listed below are the three mutation methods which have varying weights of selection probability.</p> <p>1: Swap randomly selected numbers. The method selects two random numbers and swaps them throughout the board. This method seems to have the greatest impact on growth early in the algorithms growth pattern. 25% chance of selection</p> <p>2: Introduce random changes: Randomly select two cells and change their values. This method seems to help keep the algorithm from converging. %65 chance of selection</p> <p>3: count the number of each value in the board. A solved board contains a count of 9 of each number between 1 and 9. This method takes any number that occurs less than 9 times and randomly swaps it with a number that occurs more than 9 times. This seems to have a positive impact on the algorithm but only used sparingly. %10 chance of selection</p> <p>My main question is at what rate should I apply the mutation method. It seems that as I increase mutation I have faster initial results. However as the result approaches a correct result, I think the higher rate of change is introducing too many bad chromosomes and genes into the population. However, with the lower rate of change the algorithm seems to converge too early. </p> <p>One last question is whether there is a better approach to mutation. </p>
    singulars
    1. PO
      singulars
      1. PTAnswer
    1. This table or related slice is empty.
    1. PTQuestion
    1. This table or related slice is empty.
    1. USYellowledbet
    plurals
    1. This table or related slice is empty.
    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
    1. VO
      singulars
      1. POGenetic Algorithm Sudoku - optimizing mutation
      1. This table or related slice is empty.
      1. VTUpMod
    2. VO
      singulars
      1. POGenetic Algorithm Sudoku - optimizing mutation
      1. This table or related slice is empty.
      1. VTUpMod
    3. VO
      singulars
      1. POGenetic Algorithm Sudoku - optimizing mutation
      1. This table or related slice is empty.
      1. VTUpMod
    1. COI assume that there are certain values that are fixed and not subject to mutation? Another way of asking: is this problem designed to generate Sudoku puzzles or to solve a particular puzzle with fixed constraints?
      singulars
      1. POGenetic Algorithm Sudoku - optimizing mutation
      1. USStephen Rudolph
    2. COIt is designed to solve puzzles and yes I protect the initial cells. Thank You for the input
      singulars
      1. POGenetic Algorithm Sudoku - optimizing mutation
      1. USYellowledbet
 

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