FLIght SCheduling OPTimization - a simple optimization library for flight scheduling and related problems in the discrete domain

Overview

Fliscopt

Stars Forks License Issues made-with-python Open Source Love png1 Maintenance PRs Welcome PyPI Tweet Say Thanks!

image

FLIght SCheduling OPTimization πŸ›« or fliscopt is a simple optimization library for flight scheduling and related problems in the discrete domain. 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

Getting Started

Install the library using pip:

pip install fliscopt

Or for unreleased versions:

pip install 'git+https://github.com/Agrover112/fliscopt/[email protected]

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.

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. (Will be shortly added)

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 the following for detailed understanding of our project.

[1] Alicea B., Grover A., Lim A. ,Parent J, Unified Theory of Switching. Flash Talk to be 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!

Comments
  • Add message for failed unittests.

    Add message for failed unittests.

    A message indicating a failure for each unit-test, should give the user a small idea of what went wrong in the test. ex: self.assertEqual ( f(values), 0, msg ='HEURISTIC MESSAGE INDICATING WHY TEST CASE FAILED')

    good first issue Hacktoberfest Hacktoberfest-accepted 
    opened by Agrover112 12
  • fix:Add docstrings for each algorithm file.

    fix:Add docstrings for each algorithm file.

    Fixing Issue #27 , Please check the added docstrings and if the format is correct, if wrong please help me to correct the mistakes because I am a complete beginner to Google Docstrings and even large Python Codebases. Thank you and have a great day!

    Hacktoberfest Hacktoberfest-accepted 
    opened by subhamgcon 11
  • Add docstrings for each algorithm file.

    Add docstrings for each algorithm file.

    There are few files which contain implementation of the algorithms: [**sa,ga,hc,chaining,rs].py** you need to write the docstring for the classes present in each file using Google Docstring Convention. Refer: algorithms.py on how to write docstrings for functions and similarily refer THIS and THIS link for on getting started on how to write docstrings for the classes. PS : Google Style Guide

    • [ ] chaining.py
    • [ ] ga.py
    • [ ] rs.py
    • [ ] sa.py
    • [ ] hc.py
    documentation good first issue Hacktoberfest 
    opened by Agrover112 6
  •  #10 Upload docs & set up wrangler for vercel @agrover112 @gizmotronn

    #10 Upload docs & set up wrangler for vercel @agrover112 @gizmotronn

    Creating pr to reference #10

    Docs should also be accessible in main branch (aka master) imo, we can autogenerate docs based on markdown files @Agrover112 inside the module/library

    E.g. let's say you create a doc page in /docs branch called "Why bees can't fly" with the meta tag for doc-tag being bees

    We can setup a script in main branch that when using module in ide, user can type /fliscopt help bees and will find the "intro" meta about the bees entry in the markdown file in /docs branch, as well as a link to view the documentation site

    documentation enhancement 
    opened by Gizmotronn 5
  • Add an Pull Request template

    Add an Pull Request template

    πŸ‘Ž Actual Behavior

    A template for raising a Pullreq.

    πŸ‘ Expected behavior

    same as above

    ✍️ Suggestions to rectify this issue

    Create a .yml template for creating a PR template.

    πŸ‘€ Have you spent some time to check if this issue has been raised before?

    • [X] I checked and didn't find similar issue
    good first issue Hacktoberfest Hacktoberfest-accepted 
    opened by Agrover112 5
  • fix(readme): Add graphic

    fix(readme): Add graphic

    Closes #11 @Agrover112 I have added a graphic and a logo file in the project, and updated the readme file. I have referred to the above mentioned graphics. Please mention any suggestion or changes to the graphic/logo file. I will look into it and make the necessary changes.

    enhancement Hacktoberfest Hacktoberfest-accepted 
    opened by Anik-Bardhan 5
  • Comparing differences between config files -> #10

    Comparing differences between config files -> #10

    Seems like it's a plugin dependancy issue that's causing the build issues. @Agrover112 Docs should be ready to go, I haven't been able to get the lightweight CMS editor working BUT I'd advise setting this up with GitHub pages by tomorrow and then logging in with prose.io for now UNTIL I can fix the plugin issue

    gem bundle build is the worst thing I can imagine rn.

    bug documentation 
    opened by Gizmotronn 2
  • πŸ› Bug Report: GA Reversals wrong number of reversals

    πŸ› Bug Report: GA Reversals wrong number of reversals

    πŸ‘Ÿ Reproduction steps

    Just use the api normally and enter any combination of n_k and number_generations.

    πŸ‘ Expected behavior

    The number of reversals would be = iter/n_k

    πŸ‘Ž Actual Behavior

    Only 1 reversal process takes place , as seen due to default parameters, thus entered parameters are not registering.

    πŸ‘€ Have you spent some time to check if this issue has been raised before?

    • [X] I checked and didn't find similar issue
    bug 
    opened by Agrover112 2
  • Add an Pull Request template #39

    Add an Pull Request template #39

    Closes #39

    Renamed PULL_REQUEST.md to to pull_request_template.md following these instructions https://docs.github.com/en/communities/using-templates-to-encourage-useful-issues-and-pull-requests/creating-a-pull-request-template-for-your-repository

    This has been tested as shown in the screenshot. image

    opened by LittleBigProgramming 2
  • Merge this

    Merge this

    What does this PR do?

    Updates README.md with some missing information wrt Results tables.

    Test Plan

    (Write your test plan here. If you changed any code, please provide us with clear instructions on how you verified your changes work.)

    Related PRs and Issues

    (If this PR is related to any other PR or resolves any issue or related to any issue link all related PR and issues here.)

    Have you read the Contributing Guidelines on issues?

    (Write your answer here.)

    opened by So-bonkers 1
  • Add PyPy tests.

    Add PyPy tests.

    Current ./run_tests.sh due to oversight were written and run using python filename.py. In order to appropriately test it , it needs yo be replaced by: pypy filename.py

    opened by Agrover112 1
  • Github Sync Fork action not working

    Github Sync Fork action not working

    πŸ‘Ž Actual Behavior

    Failed to create or merge pull request: HttpError: Validation Failed: {"resource":"PullRequest","field":"head","code":"invalid"}

    πŸ‘ Expected behavior

    Should technically sync forks?

    ✍️ Suggestions to rectify this issue

    I'm currently using secrets.TOKEN, a token which I use for the repo with public_repo permissions enabled. Not sure what is going wrong really. image

    πŸ‘€ Have you spent some time to check if this issue has been raised before?

    • [X] I checked and didn't find similar issue
    bug help wanted Hacktoberfest Hacktoberfest-accepted 
    opened by Agrover112 0
  • πŸ“‹General Issues: Exception handling

    πŸ“‹General Issues: Exception handling

    πŸ‘Ž Actual Behavior

    The Error isn't handled properly.

    πŸ‘ Expected behavior

    Should raise a particular Error (exception) when unintended input is passed to the given fn,etc.

    ✍️ Suggestions to rectify this issue

    Add exception handling for each of the core functions and algorithms

    πŸ‘€ Have you spent some time to check if this issue has been raised before?

    • [X] I checked and didn't find similar issue
    bug 
    opened by Agrover112 0
  • Fix #FIX-NEEDED

    Fix #FIX-NEEDED

    πŸ‘Ÿ Reproduction steps

    Implemented in: mulit_mutattion in ga_utils.py Can be tested by replacing mutation with multi_mutation in ga.py.

    πŸ‘ Expected behavior

    Mulit_mutattion in ga_utils.py should change N bits as selected. [1,2,3,4] for 2 bits could be: [1,3,3,5]

    πŸ‘Ž Actual Behavior

    Mulit_mutattion in ga_utils.py doesn't work as expected. Gives an Index Error when used , since the implementation is not correct.

    πŸ‘€ Have you spent some time to check if this issue has been raised before?

    • [X] I checked and didn't find similar issue
    bug help wanted good first issue Hacktoberfest 
    opened by Agrover112 5
  • Add more problem functions in fitness.py

    Add more problem functions in fitness.py

    Add more problems rel to current flightscheduling problem. (No matrix problems) Only problems whose solution is of the form: [1,2,3,4] OR [x1,z2..........xn] and corresponding domain : [(-a,b),(-c,-d).......nth-tuple]. Refer fitness.py for existing problems and cost functions and their domains.

    Ideally the isse requires you to add a sample cost function to solve a particular problem, whose inputs are of form 1*n

    enhancement help wanted good first issue Hacktoberfest 
    opened by Agrover112 7
Releases(v0.4.1)
Owner
Humans trying to understand machines...
Search algorithm implementations meant for teaching

Search-py A collection of search algorithms for teaching and experimenting. Non-adversarial Search There’s a heavy separation of concerns which leads

Dietrich Daroch 5 Mar 07, 2022
A pure Python implementation of a mixed effects random forest (MERF) algorithm

Mixed Effects Random Forest This repository contains a pure Python implementation of a mixed effects random forest (MERF) algorithm. It can be used, o

Manifold 199 Dec 06, 2022
A simple python application to visualize sorting algorithms.

Visualize sorting algorithms A simple python application to visualize sorting algorithms. Sort Algorithms Name Function Name O( ) Bubble Sort bubble_s

Duc Tran 3 Apr 01, 2022
A collection of Python Scripts made for fun, while exploring Python 🐍

JFF-Python-Scripts A collection of Python Scripts made for fun, while exploring Python 🐍 Inspiration πŸ’‘ Many of the programs in this repository are i

Pushkar Patel 16 Oct 07, 2022
The DarkRift2 networking framework written in Python 3

DarkRiftPy is Darkrift2 written in Python 3. The implementation is fully compatible with the original version. So you can write a client side on Python that connects to a Darkrift2 server written in

Anton Dobryakov 6 May 23, 2022
A fast python implementation of the SimHash algorithm.

This Python package provides hashing algorithms for computing cohort ids of users based on their browsing history. As such, it may be used to compute cohort ids of users following Google's Federated

Hybrid Theory 19 Dec 15, 2022
A fast, pure python implementation of the MuyGPs Gaussian process realization and training algorithm.

Fast implementation of the MuyGPs Gaussian process hyperparameter estimation algorithm MuyGPs is a GP estimation method that affords fast hyperparamet

Lawrence Livermore National Laboratory 13 Dec 02, 2022
Robotic Path Planner for a 2D Sphere World

Robotic Path Planner for a 2D Sphere World This repository contains code implementing a robotic path planner in a 2D sphere world with obstacles. The

Matthew Miceli 1 Nov 19, 2021
Path tracing obj - (taichi course final project) a path tracing renderer that can import and render obj files

Path tracing obj - (taichi course final project) a path tracing renderer that can import and render obj files

5 Sep 10, 2022
Visualisation for sorting algorithms. Version 2.0

Visualisation for sorting algorithms v2. Upped a notch from version 1. This program provides animates simple, common and popular sorting algorithms, t

Ben Woo 7 Nov 08, 2022
Dynamic Programming-Join Optimization Algorithm

DP-JOA Join optimization is the process of optimizing the joining, or combining, of two or more tables in a database. Here is a simple join optimizati

Haoze Zhou 3 Feb 03, 2022
Using Bayesian, KNN, Logistic Regression to classify spam and non-spam.

Make Sure the dataset file "spamData.mat" is in the folder spam\src Environment: Python --version = 3.7 Third Party: numpy, matplotlib, math, scipy

0 Dec 26, 2021
This repository provides some codes to demonstrate several variants of Markov-Chain-Monte-Carlo (MCMC) Algorithms.

Demo-of-MCMC These files are based on the class materials of AEROSP 567 taught by Prof. Alex Gorodetsky at University of Michigan. Author: Hung-Hsiang

Sean 1 Feb 05, 2022
Benchmark for Robustness Tests of Control Alrogithms

A gym-like classical control benchmark for evaluating the robustnesses of control and reinforcement learning algorithms.

Kim Taekyung 4 Jan 18, 2022
Genetic Algorithm for Robby Robot based on Complexity a Guided Tour by Melanie Mitchell

Robby Robot Genetic Algorithm A Genetic Algorithm based Robby the Robot in Chapter 9 of Melanie Mitchell's book Complexity: A Guided Tour Description

Matthew 2 Dec 01, 2022
An open source algorithm and dataset for finding poop in pictures.

The shitspotter module is where I will be work on the "shitspotter" poop-detection algorithm and dataset. The primary goal of this work is to allow for the creation of a phone app that finds where yo

Jon Crall 29 Nov 29, 2022
Slight modification to one of the Facebook Salina examples, to test the A2C algorithm on financial series.

Facebook Salina - Gym_AnyTrading Slight modification of Facebook Salina Reinforcement Learning - A2C GPU example for financial series. The gym FOREX d

Francesco Bardozzo 5 Mar 14, 2022
marching rectangles algorithm in python with clean code.

Marching Rectangles marching rectangles algorithm in python with clean code. Tools Python 3 EasyDraw Creators Mohammad Dori Run the Code Installation

Mohammad Dori 3 Jul 15, 2022
This is a Python implementation of the HMRF algorithm on networks with categorial variables.

Salad Salad is an Open Source Python library to segment tissues into different biologically relevant regions based on Hidden Markov Random Fields. The

1 Nov 16, 2021
Python sample codes for robotics algorithms.

PythonRobotics Python codes for robotics algorithm. Table of Contents What is this? Requirements Documentation How to use Localization Extended Kalman

Atsushi Sakai 17.2k Jan 01, 2023