Solve the Queen's Problem with ParadisEO

This exercice includes 4 parts. All parts have different degree of difficulty. While you progress throught the exercice, you have to look in Tutorials and API doc to help you finding the right answer. The main idea is to try ParadisEO and handle its major objects.

The correction concerns only the first part. Several examples are available in ParadisEO and in the differents contributions.

Installation

First you have to install ParadisEO.

Then download and compile the queen package (cf README file).

If you encounter any problems, refer to the installation section.

The package contains files that you have to fill in order to build all elements you need to solve the problem. It also contains the answers of the part I.

Problem's presentation

The Queen's Problem aims to place N Queens on a chessboard of N*N cases, such that no queen threatens the other ones. Two queens threaten mutually if they are on the same row, column or diagonal. Fore more details, you can refer to wikipedia.

Exercice1 - part I

Find a representation

To ensure the efficiency of our solution, a good representation has to be chosen.

Q1: We proposed three representations:

  • a Matrix (N*N)
  • a Permutation of size N (a vector including N int, example for N=4: [1,3,2,4])
  • N couples of coordinates

In your opinion, what is the most adapted representation? Why? What are the advantages and the drawbacks of each one? Answer

Code the representation

Q2: We choose the second representation. Try to find in the eo-doc the class to use in order to define a permutation (not to initialize it !). Answer
When you have found, you can open the file "queen.h" in "src" directory and see how a representation of the QUEEN problem is defined.

Initialize a solution

The initialization of a solution is to create a feasible solution.
Example: for a queen problem of size 8, it can be the permutation 3,2,5,8,7,6,4,1.

Q3: Let us use a random initialization: Find in the eo API doc a class which initializes a permutation. Answer
When you have found, you can open the file "queenInit.h" in "src" directory and see how to initialize a QUEEN.

Q4: Practice: In "application" directory, fill the file "tryInit.cpp" in order to instantiate a QUEEN, initialize it and print the result. You can refer to the eo API doc to see what are the appropriate methods.

  • fill the file "tryInit.cpp"
  • compile the "tryInit" target
  • run the "tryInit" executable


A solution displayed is represented by its fitness (a value or INVALID), then the size of the problem and the corresponding permutation.
Example: INVALID 8 1 3 4 7 5 6 2 8'

Evaluation

To evaluate a solution, a fitness value has to be calculated. To perform it, we will use an evaluation function to affect a score for each solution.

Q5: How to evaluate a QUEEN solution? Answer

It is important to evaluate efficiently of a solution because it is often the most time consuming part in a genetic algorithm.

Q6: Practice

  • In "src" directory, fill the file "queenEval.cpp" in order to code an efficient evaluation function. ("queenEval.h" contains declarations of the class)
  • In "application" directory, fill the file "tryEval.cpp" in order to instantiate a QUEEN, initialize it, evaluate it and print the result.

    Note: one of the best solutions must have a fitness equal to 0.

Operators

Let us use an "eoSwapMutation" and an "eoOrderXover".

Q7: Find these operators in the documentation and explain what they do. Give an example. Answer

Q8: Practice: You can then, open the files "queenMutation.h" and "queenCrossover.h" in "src" directory and see how the mutation and the crossover classes for the QUEEN's problem are defined.

  • In "application" directory, fill the file "tryMutation.cpp" in order to instantiate a QUEEN, initialize it, mute it and print the result.
  • In "application" directory, fill the file "tryCrossover.cpp" in order to instantiate two QUEENs, initialize them, cross them and print the result.

Q9: Ultimate Practice Question

  • In "application" directory, fill the file "main.cpp" in order to run an "eoEasyEA" on the QUEEN problem.

Q10: Challenge: Modify parameters in the "main.cpp" file to solve the QUEEN's Problem on a chessboard of 128*128 cases in 200 generations.

Exercice1 - part II

This part aims to discover and manipulate other classes of paradiseo for an advanced use. Thus we will try to improve the previous algorithm. Some new classes will be presented and you will have to understand them (i.e. look in the API doc how they run and how to use them). No correction will be available for this part.

Practice
You have to test all your manipulation with a simple example as in the part I.

Q11: your own operators

  • Code your own mutation or crossover operator for the queen's problem (If you have no idea, you can see the "eoShiftMutation")
  • Combine 2 mutations in a "eoPropCombinedMonOp"

Q12: new strategies Try new strategies:

  • Use another remplacement strategy (unherit of "eoReplacement")
  • Use another Continuator (unherit of "eoContinue")
  • Use another selection strategy (unherit of "eoSelect")

Q13: Checkpointing See how to use an "eoCheckPoint" and use it to do three things:

  • Include the continuator
  • Save the population in a file every 10 generation
  • Print the best solution at each generation

Q14: Parameters file Try to use all paramaters with a parameters file. See in the tutorials how to use "eoParser" and "eoState". Then you can run your algorithm with different parameters without recompiling (just change value in the parameters file).

Exercice1 - part III

This part aims to solve the queen's problem with a local search instead of a genetic algorithm. Consequently, we have to use some new classes of the module MO.

Q15: Learning
Look in the MO tutorial Lesson1 to understand how to use a hill-climbing.

Q16: Neighborhood
Find in the documentation, the neighborhood you can use.

Q17: AG -> LS Modify the "main.cpp" file to use a local search (hill climbing for example) instead of easyEA.

Q18: Others local search Look in the other MO tutorials and try the others local searches to solve the queen's problem.

Exercice1 - part IV

This part aims at discovering the multi-objective module (MOEO). To do so, we add a new feature to the queen's move. Indeed, we consider that a queen is also able to move as a knight. So, in the following, a queen move straight vertically, horizontally or diagonally, or move two squares horizontally and one square vertically, or move two squares vertically and one square horizontally. Therefore, these new characteristics should be considered as a new objective. Thus, the problem becomes a bi-objective problem where we have to minimize the number of queen threatens according to : 1) real queen move 2) knight move

Q19: Look at the MOEO tutorials and apply the necessary changes for the multiobjective optimization problem.

Q20: Try to solve the problem with different algorithms such as IBEA, NSGAII, SEEA...