[optimization][MMAS] Max-Min Ant System in finding the minimum value of a polynomial equation
Purpose:
- How to find minimum value in the polynomial equation using the Max-Min Ant System (MMAS) in Python.
- Understand the MMAS method philosophy without engineering expertise.
Introduction:
It is a common problem in finding maximum and minimum values in a given function. From calculus, we learn to solve by the first derivative and second derivative test method as below figure illustration. However, it comes up with other problems in what if the problem too complicated? or could we solve it by computers? “Optimization” aims to solve this using many different approaches. This article is using the MMAS method to solve a polynomial equation with its minimum value. MMAS method is from the Ant Colony Optimization (ACO) method by Stützle, 1997.
Recommended papers:
[1] T. Stützle and H. H. Hoos, “MAX-MIN Ant System,” Future Generation Comp. Syst., vol. 16, doi: http://dx.doi.org/10.1016/S0167-739X(00)00043-1. pp. 889–914, 2000.
[2] T. Stutzle and H. Hoos, “MAX-MIN Ant System and local search for the traveling salesman problem,” in Proceedings of 1997 IEEE International Conference on Evolutionary Computation (ICEC ‘97), 1997. doi: 10.1109/ICEC.1997.592327. pp. 309–314.
[3] 鄭逸亮, “以最大-最小螞蟻系統解決多模式有限資源專案排程問題之研究,” 碩士, 電腦與通訊工程所, 國立高雄第一科技大學, 高雄市, 2007.
Problem:
Given a polynomial equation f(x, y)=(x-1)²+(y+2)²-1.5, then find its minimum value and coordinates x, y in the -5<x<5 and -5<y<5 boundaries. Before diving into the solving steps, let’s classify the conditions form this problem. Hence, we should have two major parts
part1. a function f(x, y), and
part2. a variable set x, y inside the boundaries +/- 5 with real numbers.
All these concepts are essential in solving a real-world problem. Sometimes, the function may refer to the data model or another external program. The variable could be the forms of the vector, tensor, or matrix.
In this problem, the minimum value stays in the -1.5 when x, y equals 1, -2, respectively. This is what we are looking for in the later MMAS.
Software structure
OK, it is still an awkward moment on how to proceed from the blank IDE. Now, we need to think about the software framework for many reasons. The significant idea is to change the polynomial equation target into the own jobs to get the paycheck for milk. (Don’t forget to clap below.) And, to reserve the space to apply the other optimization algorithm. Thus, this study proposes the processing block below. It becomes handy in replacing the software’s MMAS class and the target equation afterward.
MMAS introduction
The below figure illustrates the MMAS introduction. It consists merely of the remained pheromones and walking path distance factors. In the best path, it should contain a higher density of pheromones and short travel distance. In this polynomial equation case, each potential solution in the x’, y’ position is ants’ travel node. The function f(x, y) is the remained pheromones on this path. In this minimum solver scenario, it is necessary to reverse it from the maximum condition (from the thickest pheromones into the thinnest case).
MMAS algorithm
It mainly computes the pheromones (τ) and desirability(η) and associates the probability (p) for every k-th ant. In step 2, the local search and global search routines design the new position of ants in the next [t+1] iteration time. Finally, the pheromone (τ) is updated according to the remained control factory (ρ, 0.9~0.8 normally) and total released pheromones (Q, a constant normally).
Execution Result
The below motion picture demonstrates the MMAS iteration in 100 times. In the end, the minimum value (-1.4999) and position (0.9978,-1.9973) are solved. It is very close to the analytic solution of the (-1.5) in the (1,-2).
In the beginning, the pink circle represents the initial solution. While an ant captured, this pink circle is dragged by the local search mechanism. In the end, this ant drags the pink circle into the big blue point (analytic solution).
The other ants may stay in either local search mode or the global mode according to the P-possibility value. All ants are surrounding with the big blue point to fit with the polynomial equation shape.
The reference Python code is below. (Python手把手构建蚁群算法（ACO）实现最优化搜索)
Conclusion
In this article, we introduced the optimization method on a polynomial equation problem. MMAS method demonstrated its applied software structure, introduction, algorithm flow, and implementation result.
