Fliscopt

FLIght SCheduling OPTimization 🛫 or fliscopt is a simple optimization library for flight scheduling and related problems in the discrete domain. Flight scheduling opt here refers to generating schedules of optimal cost for round-trips.

The library supports plotting, asynchronous multiprocessing, and unimodal optimization benchmarks. The following repository contains code for the paper "XYZ". The experiments were performed in PyPy3.7 and CPython 3.8.10.

Following algorithms have been implemented and test as of date:

Algorithms:

• Hill Climbing
• Random Search
• Simulated Annealing
• Genetic Algorithm
• Genetic Algorithm in Reverse Mode
• Genetic Algorithm with Reversals
• Genetic Algorithm with Random Search as a Reversal/Reverse Process
• Iterated Chaining

Take a look at the docs or the Appendix for more details.

Getting Started

Install the library using pip:

pip install fliscopt

Or for unreleased versions:

pip install git+https://github.com/Agrover112/fliscopt/fliscopt@branchname

Or for development:

git clone https://github.com/Agrover112/fliscopt.git
cd fliscopt
pip install .

Download the flights.txt file from the following link and add it to a data/ directory within your parent directory.

A sample code demonstrating how to use fliscopt:

from fliscopt.utils.util import print_schedule, read_file,plot_scores
from fliscopt.rs import RandomSearch
from fliscopt.ga import GA, ReverseGA, GAReversals, GARSReversals
from fliscopt.hc import HillClimb
from fliscopt.chaining import IteratedChaining
from fliscopt.fitness import fitness_function,domain,griewank



read_file('flights.txt')
sga=GAReversals(seed_init=False,search=False,n_k=250,number_generations=1000)
soln, cost, scores, nfe, seed = sga.run(domain=domain['domain'], fitness_function=fitness_function,seed=5)
plot_scores(scores, sga.get_base(),fname='flight_scheduling', save_fig=False)


sga2=GARSReversals(seed_init=False,search=False,n_k=250,number_generations=1000)
soln, cost, scores, nfe, seed = sga2.run(domain=domain['domain'], fitness_function=fitness_function,seed=5)
plot_scores(scores, sga2.get_base(),fname='flight_scheduling', save_fig=False)

This results in the following two plots:

Checkout out the examples in the examples directory or run in Google Collab

For PyPy users

The instructions for setup are mentioned in the setup directory. Alternatively, you can set up using this bash script. A requirements file is provided just in case. The script creates and activates a PyPy Conda environment with all libraries and dependencies.

cd ./setup.sh
source setup.sh

Then install using:

pypy -mpip install fliscopt

Testing

After adding any new algorithm, you can run the tests to check if the code is working properly.

./run_tests.sh

Results

Experimental Results

Results were compared by using the same seeds. The following table shows the results of the experiments. Flight scheduling results have been shown below.

Algorithm	Mean cost	Std.dev	Min cost	Max cost	n.fe.	Time(millsecond)
SGA	2780.9	205.75	2356	3081	1000	9.36
GAwRo	2629.8	213.79	2356	3004	1000	9.66
GAwR	2593	183.89	2356	2973	1099	10.16
HC	4177.7	817.72	2759	5839	328	0.33
RS	4545.3	271.95	4143	5165	100	0.17
SA	3726.5	578.16	2759	4679	512	0.24
RS+HC	3050.7	399.72	2356	3771	1657	2.23
GARSRev	2592.9	168.45	2356	2888	1099	9.97

Accessing results

After running the experiments, the results are stored in the results directory. The results are stored in the following format in subdirectories:

.
├── multi_proc
│   ├── ackley_N2
│   │   ├── genetic_algorithm_results.csv
│   │   ├── genetic_algorithm_reversed_results.csv
│   │   ├── genetic_algorithm_with_reversals_results.csv
│   │   ├── hill_climb_results.csv
│   │   ├── random_search_results.csv
│   │   └── simulated_annealing_results.csv
│   ├── booth/...
|   |
|   |
│   └── zakharov
│       ├── genetic_algorithm_results.csv
│       ├── genetic_algorithm_reversed_results                  
│       ├── genetic_algorithm_with_reversals_results.csv
│       ├── random_search_results.csv
│       └── simulated_annealing_results.csv
├── plots
│   ├── ackley_N2
│   ├── fitness_function
│   │   ├── hill_climb.png
│   │   └── random_search.png
│   ├── flight_scheduling
│   │   ├── simulated_annealing.png
│   │   ├── sol_chaining.png
│   │   └── sol_chaining_a1.png
│   └── griewank

References

Read and Cite the following References for detailed understanding and use of our project.

[1] Grover, A., Yadav, V., Alicea, B. (2023). Flipping the Switch on Local Exploration: Genetic Algorithms with Reversals. In: Kumar, S., Sharma, H., Balachandran, K., Kim, J.H., Bansal, J.C. (eds) Third Congress on Intelligent Systems. CIS 2022. Lecture Notes in Networks and Systems, vol 608. Springer, Singapore

[2] Alicea B., Grover A., Lim A. ,Parent J, Unified Theory of Switching. Flash Talk presented at: 4th Neuromatch Conference; December 1 - 2, 2021

Contributing Guidelines

Refer Contributing.md and Project Board for mode details. This repository follows conventional commits!