README.md

K-cover-Metaheuristic

In this repo, two methods are presented to solve a K-minimum cover with Metaheuristics algorithms.

• An Evolutionary Algorithm
• A Local Search

Evolution of the best current solution at each iteration, with Evolutionary Algorithm

How to run the project

To run the project you need to run

python  main.py

Needed Arguments :

• -m for the method to run. Chose between genetic, local, bound
• -d for the path of the input data file

Parameters of the instance (defaults to (1, 1, 1))

• -rcapt for the captation radius (int)
• -rcomm for the communication radius (int)
• -k for the cover degree (int)

Optional Hyper-Parameters (defaults to (40, 15))

• -neighb for the maximum number of neighbours (for local searchs)
• -i for the maximum number of iterations (int)

Optional Parameters (defaults to False)

• --stats : add this option if you want output plots to be showed after the search
• --optim : only used in bash files, to run multiple instances in a row

Command examples per method

• To test the Evolutionary Algorithm Method, you can run

python main.py -m genetic -d data/captANOR150_7_4.dat -rcom 2 -rcapt 1 -k 1 -i 10 -neighb 40 --stats

• To test the Local Search Method, you can run

python main.py -m localsearch -d data/captANOR150_7_4.dat -rcom 2 -rcapt 1 -k 1 -i 15 -neighb 40 -t 400 --stats

Stucture of the code

The project is based on several Python Classes and associated files, each having a specific use ;

• instance_class.py reads data files and stores the instance-relative information ;
• solution_class.py contains Solution, the basic class for solution, with only main methods and attributes. Then, each specific resolution method is a child of this class ;
• chromosome_class.py and genetic_class.py contains objects relative to the Evolutionary Algorithm method ;
• solution_class.py also contains all classes relative to the Local Search Method ;
• milp_class.py contains the Class used for the MILP computing the bounds.