# 0905
### 多目標演算法發展
現實中工程問題和科學研究中優化問題，通常具有多個指標進行同時優化，且各指標之間會互相影響，往往只能對其中一個指標進行優化，很難客觀的評價多目標解法的優劣性。例如:在設計最佳路徑演算法時，我們一方面希望路程最少，一方面希望減少停紅綠燈的時間，一方面又行駛路徑中具有多個休息站。因此多目標問題的合理解並不是唯一的，而是具有一個近似最佳解集合，集合中的元素稱為Pareto最優或non-dominance。
以下為多目標演算法發展史
```
1975年 遺傳演算法(Genetic Algorithm) ----- John Holland
多目標演算法(Multi-objective Evolutionary Algorithm,MOEA)
第一代多目標演算法:以簡單好理解為特徵。
NSGA(Non-dominated Sorting Genetic Algorithm)
NPGA(Niched-Pareto-Genetic-Algorithm
MOGA( multi-objective genetic algorithm)
第二代多目標演算法:以菁英保留策略為主要進化方向。
SPEA(Strength Pareto. Evolutionary Algorithm)
SPEA2(Strength Pareto. Evolutionary Algorithm 2)
PAES(Pareto Archive EvolutionStrategy,PAES)
NSGAII(Non-dominated Sorting Genetic Algorithm)
PESA(Pareto envelope-based selection algorithm)
```
#### 參考文獻:
1. [多目標演算法發展](http://www.jsjkx.com/CN/article/openArticlePDF.jsp?id=7842)
2. [NSGA](https://blog.csdn.net/royce_feng/article/details/80310530)
3. [python-NPGA](https://github.com/EmilioSchi/Niched-Pareto-Genetic-Algorithm-NPGA)
4. [python-SPEA2](https://github.com/Valdecy/Metaheuristic-SPEA_2)
5. [交大 NSGA2論文](https://ir.nctu.edu.tw/bitstream/11536/38681/1/652401.pdf)
---
### NSGAII : 多目標基因演算法
NSGA-II 中，因為不是所有的人都被允許生存，相似的人口僅需部分代表即可，如下圖
```
因此利用曼哈頓距離計算人口之間的擁擠程度 。
```
並利用二元錦標賽策略保留菁英人口。
---
套件: pymoo
建立fitiness function
```
import numpy as np
from pymoo.model.problem import FunctionalProblem
objs = [
lambda x: x[0]**2 + x[1]**2,
lambda x: (x[0]-1)**2 + x[1]**2
]
constr_ieq = [
lambda x: 2*(x[0]-0.1) * (x[0]-0.9) / 0.18,
lambda x: - 20*(x[0]-0.4) * (x[0]-0.6) / 4.8
]
functional_problem = FunctionalProblem(2,
objs,
constr_ieq=constr_ieq,
xl=np.array([-2,-2]),
xu=np.array([2,2]))
```
設計問題
```
import numpy as np
from pymoo.util.misc import stack
from pymoo.model.problem import Problem
class MyProblem(Problem):
def __init__(self):
super().__init__(n_var=2,
n_obj=2,
n_constr=2,
xl=np.array([-2,-2]),
xu=np.array([2,2]),
elementwise_evaluation=True)
def _evaluate(self, x, out, *args, **kwargs):
f1 = x[0]**2 + x[1]**2
f2 = (x[0]-1)**2 + x[1]**2
g1 = 2*(x[0]-0.1) * (x[0]-0.9) / 0.18
g2 = - 20*(x[0]-0.4) * (x[0]-0.6) / 4.8
out["F"] = [f1, f2]
out["G"] = [g1, g2]
elementwise_problem = MyProblem()
```
建立 NSGA2 模型
```
from pymoo.algorithms.nsga2 import NSGA2
from pymoo.factory import get_sampling, get_crossover, get_mutation
algorithm = NSGA2(
pop_size=40,
n_offsprings=10,
sampling=get_sampling("real_random"),
crossover=get_crossover("real_sbx", prob=0.9, eta=15),
mutation=get_mutation("real_pm", eta=20),
eliminate_duplicates=True
)
```
建立停止條件
```
from pymoo.factory import get_termination
termination = get_termination("n_gen", 40)
```
建立最優化算法
```
from pymoo.optimize import minimize
res = minimize(problem,
algorithm,
termination,
seed=1,
save_history=True,
verbose=True)
```
執行
```
import copy
# perform a copy of the algorithm to ensure reproducibility
obj = copy.deepcopy(algorithm)
# let the algorithm know what problem we are intending to solve and provide other attributes
obj.setup(problem, termination=termination, seed=1)
# until the termination criterion has not been met
while obj.has_next():
# perform an iteration of the algorithm
obj.next()
# access the algorithm to print some intermediate outputs
print(f"gen: {obj.n_gen} n_nds: {len(obj.opt)} constr: {obj.opt.get('CV').min()} ideal: {obj.opt.get('F').min(axis=0)}")
# finally obtain the result object
result = obj.result()
```
驗證
```
from pymoo.visualization.scatter import Scatter
# get the pareto-set and pareto-front for plotting
ps = problem.pareto_set(use_cache=False, flatten=False)
pf = problem.pareto_front(use_cache=False, flatten=False)
# Design Space
plot = Scatter(title = "Design Space", axis_labels="x")
plot.add(res.X, s=30, facecolors='none', edgecolors='r')
if ps is not None:
plot.add(ps, plot_type="line", color="black", alpha=0.7)
plot.do()
plot.apply(lambda ax: ax.set_xlim(-0.5, 1.5))
plot.apply(lambda ax: ax.set_ylim(-2, 2))
plot.show()
# Objective Space
plot = Scatter(title = "Objective Space")
plot.add(res.F)
if pf is not None:
plot.add(pf, plot_type="line", color="black", alpha=0.7)
plot.show()
```
收斂及視覺化
```
from pymoo.visualization.scatter import Scatter
# get the pareto-set and pareto-front for plotting
ps = problem.pareto_set(use_cache=False, flatten=False)
pf = problem.pareto_front(use_cache=False, flatten=False)
# Design Space
plot = Scatter(title = "Design Space", axis_labels="x")
plot.add(res.X, s=30, facecolors='none', edgecolors='r')
if ps is not None:
plot.add(ps, plot_type="line", color="black", alpha=0.7)
plot.do()
plot.apply(lambda ax: ax.set_xlim(-0.5, 1.5))
plot.apply(lambda ax: ax.set_ylim(-2, 2))
plot.show()
# Objective Space
plot = Scatter(title = "Objective Space")
plot.add(res.F)
if pf is not None:
plot.add(pf, plot_type="line", color="black", alpha=0.7)
plot.show()
```
[程式碼下載](https://drive.google.com/file/d/1qSIkHSSby2N2BYwwW4sm5dWmuTbd9DET/view?usp=sharing)
#### 參考文獻:
[重要GA-選擇策略介紹](https://blog.csdn.net/hba646333407/article/details/103251008)
Sign in with Wallet
Connect another wallet