A shortest path finder using a genetic algorithm in C++
This project was a part of the University of Strasbourg IT bachelor's degree during the distributed systems class. It was a complete discovery of the Genetic Algorithm paradigm and we implemented it from scratch. Report is in French.
Lansiné : GA evaluation / GA scoring / collision detection / UML Nicolas: RPC / GA distribution / GA structures choice / GA population Archade : GA mutation / GA reproduction / tests / GA population / report Arthur Scheidel : UI / random map generation / OpenGL / specific paths / GA population / report / team management
Qtcreator (compile with qmake)
tirpc (/ usr / include / tirpc or change the variable INCLUDEPATH of Projet_SD.pro) rpcbind freeglut pthread
To compile the project:
Open the Projet_SD.pro and sd_s6_rpc_client.pro files. in qtcreator Compile and run the first one by pressing the execute button. If all goes well, a window should appear.
You can start a test session after choosing settings and drawn a map (generated by the draw button according to the settings). The result is displayed as the artificial evolution progresses. Note the checkbox "assisted convergence", which allows to insert affines and sinusoids in the villages. The test session runs a single village.
Put 100 inhabitants per village for better results. Remember to increase the generation number, especially for non-converged runs - with convergence the time of a run becomes long enough for 5000 generation. Do not put too many mutations. Good results are found with steps from 4.5px to 10px even if larger steps work too.
You can also choose to launch the RPC server. In this case, the small counter in the right indicates the current number of connected clients. To launch the customers, define the sd_s6_rpc_client project as an active project and run as many times as necessary (parameter Number of villages). Customers receive the connection information (check the consistency in the console) and immediately run their server). Exchanges will take place when all customers are connected. Note that the exchanges do not work (the decoded structure always contains a null vector field ?!) and make to crash the server, but villages continue to turn properly.