Optimization Course [최민주 교수님 최적화 수업]
1. Linear programming
2. Simplex
3. Mixed integer programming
4. Binary integer programming
5. Goal programming
6. Network models, Graph theory
7. Minimum spanning tree
8. Stenier tree problem
9. A* (A star)
10. Non-linear optimization problems and nonlinear programming
11. Meta-heuristics
12. Genetic algorithm (GA)
13. Particle swarm optimizationLinear programming
: to find optimal value(s) for unknown parameter(s) to maximize/minimize a cost function
https://brilliant.org/wiki/linear-programming/
Simplex
: an algorithm to solve the linear programming iteratively (including mixed integer, binary integer, and goal programming)
https://www.youtube.com/watch?v=jh_kkR6m8H8
Mixed-integer (linear) programming
: types of the parameters are integer (not float or double)
https://www.youtube.com/watch?v=RhHhy-8sz-4&list=LL3ox-8ZsbTY0E9Y2-RYqTYw&index=4&t=6s
Binary integer (linear) programming
: types of the parameters are binary (zero or one)
https://www.youtube.com/watch?v=-3my1TkyFiM&list=LL3ox-8ZsbTY0E9Y2-RYqTYw&index=5&t=0s
Goal programming
: has multiple cost functions (= multiple goals)
https://www.youtube.com/watch?v=D1xYQdnmKvY
Network models, Graph theory
: network model is just like a neural network model, which consists of nodes and edges
: In mathematics, graph theory is the study of graphs, which are mathematical structures used to model pairwise relations between objects
- graph theory video: https://www.youtube.com/watch?v=82zlRaRUsaY&list=PLsJWgOB5mIMAuH3cHa-MXukX6-RPpDXgl&index=4
Minimum spanning tree (MST)
: to find the shortest path for the traveling salesman person problem
: there are two main algorithms to find the minimum spanning tree.
1) Prims algorithm, 2) Kruskals algorithms
- Prims algorithm in detail: https://www.youtube.com/watch?v=jsmMtJpPnhU
- comparative explanation about the Prims and Kruskals: https://www.youtube.com/watch?v=4ZlRH0eK-qQ
Stenier tree problem
: to find the mimimum spanning tree, it adds "stenier point" to bridge the existing nodes.
- algorithm for the Stenier tree problem: more research is required, not yet understood.
A* (A star)
: 전산학 분야에 있어서, A* 알고리즘(A* algorithm 에이 스타 알고리듬[*])은 주어진 출발 꼭짓점에서부터 목표 꼭짓점까지 가는 최단 경로를 찾아내는(다시 말해 주어진 목표 꼭짓점까지 가는 최단 경로임을 판단할 수 있는 테스트를 통과하는) 그래프/트리 탐색 알고리즘 중 하나이다.
https://www.youtube.com/watch?v=-L-WgKMFuhE
Non-linear optimization problems and nonlinear programming
: In mathematics, nonlinear programming (NLP) is the process of solving an optimization problem where some of the constraints or the objective function are nonlinear.
https://apmonitor.com/pdc/index.php/Main/NonlinearProgramming (includes the python code)
On the reference website, scipy.optimize is used and there are lots of multivariate optimization methods for minimize (link).
Meta-heuristics
: 휴리스틱이란? 합리적인 계산 비용으로 최적 또는 거의 최적의 솔루션을 찾는 기술
: 메타휴리스틱이란? 특정 문제에 특화되지 않고 자연에서 영감을 얻은 경험적 방법
: 자주 사용되는 메타휴리스틱 방법
- Genetic Algorithm(GA)
- Tabu Search(TS)
- Ant Colony Optimization(ACO)
- Partical Swarm Optimization(PSO)
- Simulated Annealing(SA)
https://zzsza.github.io/data/2019/03/26/metaheuristics/
Genetic algorithm (GA)
: In computer science and operations research, a genetic algorithm (GA) is a metaheuristic inspired by the process of natural selection that belongs to the larger class of evolutionary algorithms (EA). Genetic algorithms are commonly used to generate high-quality solutions to optimization and search problems by relying on biologically inspired operators such as mutation, crossover, and selection.
Particle swarm optimization (PSO)
: In computational science, particle swarm optimization (PSO) is a computational method that optimizes a problem by iteratively trying to improve a candidate solution with regard to a given measure of quality. It solves a problem by having a population of candidate solutions, here dubbed particles, and moving these particles around in the search-space according to simple mathematical formulae over the particle's position and velocity. Each particle's movement is influenced by its local best-known position but is also guided toward the best-known positions in the search-space, which are updated as better positions are found by other particles. This is expected to move the swarm toward the best solutions. This is one of the EA algorithms.
