rob174 / fibi_recherche Goto Github PK

Comparison of first and best improvement, 2 local search strategies as a follow up study of Hansen et al: https://www.sciencedirect.com/science/article/pii/S0166218X05003070

Python 8.28% C++ 72.83% CMake 0.06% Makefile 0.17% Shell 0.01% Jupyter Notebook 18.65%

fibi_recherche's Introduction

Repository of the paper BI vs FI revisited

FIBI/analysis_results/ contains the code used to extract the results and build the figures from the metrics gathered in the c++ local searches programs. cpp_generation/FIBI/ contains the acctual local searches (TSP, MSSC, wMAXSAT)

Litterature review

To see the litterature review, go on https://rob174.github.io/BibliographyMaker/.

Load the litterature_review_papers.json file with the button load data.
Click on the Graph menu at the top left of the window
Click on "add structure": load the file structure_categorization.json
Then click on the "View Graph" tab

Algorithms

Below are the initialization algorithms used in this paper. The code is in folder cpp_generation/FIBI/src/data/improvements/

TSP

MSSC

wMAXSAT

fibi_recherche's People

Contributors

Watchers

fibi_recherche's Issues

Check TSP

Sumary

Quad

TSPLIB

Change in effect size characterization

After discussion a novel characterization of the effect size intervals has been chosen:

with for instance 0.2 small, 0.5 medium, 0.8 big we will say

Wrong TOPK for MSSC

Take the topk nearest point to choose the next center. Is in contradiction with the principle of the algorithm Kmeans++ that takes the point with a higher probability if its shortest distance to a centroid is the biggest compare to other points

Clustering benchmark GREEDY different results

Comes from the fact that before applying the GREEDY algorithm, we start from a RANDOM initial clustering different from each instance:
9f0f701

FIBI_Recherche/cpp_generation/FIBI/src/factories/clustering.hpp

Lines 66 to 80 in 9f0f701

 unique_ptr<const vector<double>> points_pos(points_pos_ptr); 

 vector<int>* assignements_ptr = random_clust(cf.NUM_CLUST.get(), cf.NUM_POINTS.get(), cf.SEED_ASSIGN.get()); 

 auto [centroids_ptr, npts_per_clust_ptr] = cmpt_centroids_and_npts_per_clust(*points_pos, *assignements_ptr, cf.NUM_DIM.get(), cf.NUM_CLUST.get()); 

 switch (cf.IMPR.get()) 

 { 

 case 0: 

 /* Random assignement: already done*/ 

 break; 

 case 1: 

 /* Kmeans++ */ 

 init_clustering_greedy_randomized(*centroids_ptr, *points_pos, *assignements_ptr, *npts_per_clust_ptr, cf.NUM_DIM.get(), cf.SEED_ASSIGN.get()); 

 break; 

 case 2: 

 /* KMeans++ super glutton */ 

 init_clustering_greedy(*centroids_ptr, *points_pos, *assignements_ptr, *npts_per_clust_ptr, cf.NUM_DIM.get(), cf.SEED_ASSIGN.get());

TSP TSPLIB GREEDY different results

Comes from the fact that before applying the GREEDY algorithm, we start from a RANDOM initial clustering different from each instance:
9f0f701

FIBI_Recherche/cpp_generation/FIBI/src/data/improvements/tsp.hpp

Lines 14 to 26 in 9f0f701

 vector<int>* init_tsp_greedy(const long num_towns, const long seed, const DistanceMatrix& distances) 

 { 

 vector<int>* tour = new vector<int>(num_towns); 

 // Add a set to avoid duplicates (a points can be the nearest one for two different points) 

 set<int> available_points; 

 for (int i = 0; i < num_towns; i++) 

 { 

 available_points.insert(i); 

 } 

 mt19937 gen_dist(seed); 

 uniform_int_distribution<> dis_choice(0, num_towns - 1); 

 int start_point = dis_choice(gen_dist); 

 tour->at(0) = start_point;

Differences initial results, current results

Summary of the differences

TSP
- Quad: Same conclusion everywhere except for GREEDY TOP3 even if not same numbers (cf issue #1)
- TSPLIB: Same conclusion everywhere even if not same numbers (cf issue #1)
Clustering
- Quad: Same conclusion even not same numbers and sometimes categories appearing
- Benchmark Aloise: Same conclusion even not same numbers and sometimes categories appearing
- Benchmark Franti: Same conclusion even not same numbers and sometimes categories appearing
MAXSAT
- Benchmark evaluation benchmark 2021:

Note: for clustering and tsp and maxsat the definition of the intervals has been changed (cf issue #5 )

Cross plateform random number generator?

For reproductibility purposes

	unique_ptr<const vector<double>> points_pos(points_pos_ptr);
	vector<int>* assignements_ptr = random_clust(cf.NUM_CLUST.get(), cf.NUM_POINTS.get(), cf.SEED_ASSIGN.get());
	auto [centroids_ptr, npts_per_clust_ptr] = cmpt_centroids_and_npts_per_clust(points_pos, assignements_ptr, cf.NUM_DIM.get(), cf.NUM_CLUST.get());
	switch (cf.IMPR.get())
	{
	case 0:
	/* Random assignement: already done*/
	break;
	case 1:
	/* Kmeans++ */
	init_clustering_greedy_randomized(centroids_ptr, points_pos, assignements_ptr, npts_per_clust_ptr, cf.NUM_DIM.get(), cf.SEED_ASSIGN.get());
	break;
	case 2:
	/* KMeans++ super glutton */
	init_clustering_greedy(centroids_ptr, points_pos, assignements_ptr, npts_per_clust_ptr, cf.NUM_DIM.get(), cf.SEED_ASSIGN.get());

	vector<int>* init_tsp_greedy(const long num_towns, const long seed, const DistanceMatrix& distances)
	{
	vector<int>* tour = new vector<int>(num_towns);
	// Add a set to avoid duplicates (a points can be the nearest one for two different points)
	set<int> available_points;
	for (int i = 0; i < num_towns; i++)
	{
	available_points.insert(i);
	}
	mt19937 gen_dist(seed);
	uniform_int_distribution<> dis_choice(0, num_towns - 1);
	int start_point = dis_choice(gen_dist);
	tour->at(0) = start_point;