---
# System prepended metadata

title: 0905

---

# 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 中，因為不是所有的人都被允許生存，相似的人口僅需部分代表即可，如下圖
    
 ![](https://pymoo.org/_images/nsga2_survival.png)
 
```
因此利用曼哈頓距離計算人口之間的擁擠程度 。
```
    
![](https://pymoo.org/_images/nsga2_crowding.png)

    並利用二元錦標賽策略保留菁英人口。
    
![](https://img-blog.csdnimg.cn/20191126211315281.gif#pic_center)

---

套件: 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)