Answer of the Queen's problem

Return to Exercice 1

Q1 Representation

  • Matrix
    + easy to visualize
    - costly regarding the memory space
    - many useless solutions (queens on the same row or column)
  • Permutation
    + avoid some useless solutions
    + easiness to apply operators
    - difficult vizualisation
  • List of couples
    + easy to visualize
    - many useless solutions

So, we choose a permutation for a reduced complexity.

Q2 Permutation representation

Use the "eoInt" class.

Q3 Permutation initializer

Use the "eoInitPermutation" class.

Q5 Evaluation function

The chosen representation avoids to test if a queen threatens another on rows and columns. So you have to test only the diagonal threats:

  • Init a counter to 0
  • Test if each queen (from the first [index 0 of the vector !!] to the next to last) threatens the queens with an higher index. Increment the counter at each time you detect a threat.
  • Affect the counter value to the fitness of the solution.

Be careful to not count twice the same threat.

Q7 Mutation and Crossover

eoSwapMutation:
This mutation operator chooses randomly 2 queens and swap them.
Example: To mute [1,3,2,4] gives [1,2,3,4], if the queens at indexes 1 and 2 are changed.

eoOrderXOver: this crossover operator uses 2 solutions (parent1 and parent2) to give two other solutions (child1 and child2):

  • First two cut points and one direction are ramdomly taken
  • Then child1 (respectively child2) begins with the part of parent1 (resp. parent2) comprised between the two cut points and finishes with the missing part taken in the parent2 (resp. parent1) according the direction.

Example: To cross [1,2,3,4,6,5,7,8] and [3,5,6,4,1,8,2,7] with 2 cut points randomly taken (represented by the symbol "|") and 1 direction -> left to right, gives

  • parent1 [1,2|3,4,6,5|7,8]
  • parent2 [3,5|6,4,1,8|2,7]
  • child1 [3,4,6,5,2,7,1,8]
  • child2 [6,4,1,8,7,2,3,5]