With the book "An Introduction to Optimization Algorithms" we try to develop an accessible and easy-to-read introduction to optimization, optimization algorithms, and, in particular, metaheuristics. We will do this by first building a general framework structure for optimization problems. We then approach the algorithms that have been developed to solve such problems from bottom-up, starting with simple approaches and step-by-step moving to more advanced methods. These moves are incremental, as problems of the current algorithm are discussed based on real results on a real example application, the Job Shop Scheduling Problem (JSSP).
If you have any comments or suggestions regarding the book, or if you spotted an error or typo, please feel free to submit an issue here. Your feedback would help us to improve the book.
The book "An Introduction to Optimization Algorithms" is available in the following formats:
- aitoa.pdf, in the PDF format for reading on the computer and/or printing (but please don't print this, save paper),
- aitoa.html, in the HTML5 format for reading in the browser on any device,
- aitoa.epub, in the EPUB3 format for reading on mobile phones or other hand-held devices, and
- aitoa.azw3, in the AZW3 format for reading on Kindle and similar devices.
The latter two formats are still a bit experimental, so they might not be beautiful. The html version of the book is fairly large, as it is a single stand-alone file.
Every algorithm that we discuss is implemented in Java 1.8 and all accompanying sources codes are provided in the GitHub repository aitoa-code. This means that you can run the same experiments that I did, but also do your own experiments and use the code for your own purposes. The code provides comprehensive facilities for logging and evaluating experimental results. It should be applicable to a wide range of scenarios. In particular, we tried to make it suitable for scientific experiments and provide built-in experiment execution, parallelization, distribution, and self-documenting output facilities. The code comes as a Maven project that can be integrated as library into your own software, as discussed here.
The final goal is to use this book as the foundation of a university course "Optimization Algorithms." Therefore, I am also trying to create a corresponding set of slides. The book is far from being complete, but the slides are even in a much earlier state of development. Only the first few topics from the book are covered as of now.
- Introduction
- Structure
- Metaheuristics
- Random Sampling
- Stochastic Hill Climbing
- Evolutionary Algorithm
- Simulated Annealing
- Comparing Optimization Algorithms★
Modules marked with "★" can be taught at any point after the Stochastic Hill Climbing module.
The LaTeX source code of the slides is provided in this repository.
It also includes all figures as pdf and svg.
A tar.xz archive with everything put together, i.e., the book, the source codes, and the slides, can be found here. We package everything as tar.xz because this format tends to achieve the best compression ratio.
Furthermore, many of the diagrams in this book are generated using an R package, which is published in the GitHub Repository aitoaEvaluate.
You can install and use it in R via devtools::install_github("thomasWeise/aitoaEvaluate").
The data from the experiments presented in the book is presented in the GitHub Repository aitoa-data.
jsspInstancesAndResults is an repository with lots of results from literature on the Job Shop Scheduling Problem (JSSP).
At the same time, it is also an R package.
You can use it to compare your own JSSP research with the state-of-the-art.
Around this book I have created a whole ecosystem of tools that help me by automating many of work involved in its development. The goal is to allow an author to fully concentrate on writing her material, while compiling the material to different formats and uploading them to the web should be automated. This tool suite is centered around GitHub and putting all material into a repository, which automatically allows for collaborative working as well.
The R package bookbuildeR provides the commands wrapping around pandoc and extending Markdown to automatically build electronic books.
There is a hierarchy of docker containers that forms the infrastructure for the automated builds:
- docker-bookbuilder is the docker container that can be used to compile an electronic book based on our tool chain. Here you can find it on GitHub and here on docker hub.
- docker-slidesbuilder is the docker container that can be used to compile
beamer-based LaTeX slides to pdf and upload them. Here you can find it on GitHub and here on docker hub. - docker-pandoc-r is a docker container with a complete pandoc, TeX Live, and R installation. It forms the basis for docker-bookbuilder and its sources are here while it is located here on docker hub.
- docker-pandoc-calibre is the container which is the basis for docker-pandoc-r. It holds a complete installation of pandoc, calibre, which is used to convert EPUB3 to AZW3, and TeX Live and its sources are here while it is located here.
- docker-pandoc is the container which is the basis for docker-pandoc-calibre. It holds a complete installation of pandoc and TeX Live and its sources are here while it is located here.
- docker-texlive-thin is the container which is the basis for docker-pandoc. It holds an installation of TeX Live and its sources are here while it is located here.
- The
Rpackage utilizeR holds some utility methods used by bookbuildeR.
Besides these containers, we also have some tools to make our work more efficiently.
The tool ultraSvgz combines several existing pieces (such as ultraGzip) of software to compile an svg graphic to a very small svgz.
This, in turn, makes it easier to keep the total size of the git repositories with our book and slides small.
This book "An Introduction to Optimization Algorithms" is released under the Attribution-NonCommercial-ShareAlike 4.0 International license (CC BY‑NC‑SA 4.0), see http://creativecommons.org/licenses/by-nc-sa/4.0/ for a summary.
The slides of the corresponding course are released under the same license.
The experiments have been conducted using the Java programs published in repository thomasWeise/aitoa-code, which under the MIT License.
The results of these experiments are provided in the repository thomasWeise/aitoa-data are under the CC BY‑NC‑SA 4.0 license.
Many of the graphics and diagrams in the book have been created from these data using the MIT-licensed R scripts in thomasWeise/aitoaEvaluate.
If you have any questions or suggestions, please contact Prof. Dr. Thomas Weise of the Institute of Applied Optimization at Hefei University in Hefei, Anhui, China via email to tweise@hfuu.edu.cn with CC to tweise@ustc.edu.cn.
