算法代码_Python进化算法之多⽬标优化与代码实战
前⾔
⾃从上三篇博客详细讲解了Python遗传和进化算法⼯具箱及其在带约束的单⽬标函数值优化中的应⽤、利⽤遗传算法求解有向图的最短路径、利⽤进化算法优化SVM参数之后，这篇不再局限于单⼀的进化算法⼯具箱的讲解，相反，这次来个横向对⽐，⽐较⽬前最流⾏的⼏个python进化算法⼯具箱/框架在求解多⽬标问题上的表现。
正⽂
1 多⽬标优化概念
⾸先⼤致讲⼀下多⽬标优化：
在⽣活中的优化问题，往往不只有⼀个优化⽬标，并且往往⽆法同时满⾜所有的⽬标都最优。例如⼯⼈的⼯资与企业的利润。那么多⽬标优化⾥⾯什么解才算是优秀的？我们⼀般采⽤“帕累托最优”来衡量解是否优秀，其定义我这⾥摘录百度百科的⼀段话：
帕累托最优（Pareto Optimality），是指资源分配的⼀种理想状态。假定固有的⼀群⼈和可分配的资源，从⼀种分配状态到另⼀种状态的变化中，在没有使任何⼈境况变坏的前提下，使得⾄少⼀个⼈变得更好。帕累托最优状态就是不可能再有更多的帕累托改进的余地；换句话说，帕累托改进是达到帕累托最优的路径和⽅法。 帕累托最优是公平与效率的“理想王国”。是由帕累托提出的。
这段话好像让⼈看着依旧有点懵逼，下⾯直接摘录⼀段学术性的定义：
因此，只要找到⼀组解，其对应的待优化⽬标函数值的点均落在上⾯的⿊⾊加粗线上，那么就是我们想要的“帕累托最优解”了。此外，假如帕累托最优解个数不可数，那么我们只需找到上⾯⿊⾊加粗线上的若⼲个点即可，并且这些点越分散、分布得越均匀，说明算法的效果越好。
2 多⽬标进化优化算法
多⽬标进化优化算法即利⽤进化算法结合多⽬标优化策略来求解多⽬标优化问题。经典⽽久经不衰的多⽬标优化算法有：NSGA2、
NSGA3、MOEA/D等。其中NSGA2和NSGA3是基于⽀配的MOEA(Multi-objective evolutionary algorithm)，⽽MOEA/D是基于分解的MOEA。
前两者（NSGA2、NSGA3）通过⾮⽀配排序
⾮⽀配排序（后⾯马上讲到）来筛选出⼀堆解中的“⾮⽀配解”，并且通过种群的不断进化，使得种群
具体算法就不作详细阐述了，可详见以下参考⽂献，或看下⽅的代码个体对应的解对应的⽬标函数值的点不断逼近上图的⿊⾊加粗线。具体算法就不作详细阐述了，可详见以下参考⽂献，或看下⽅的代码实战部分：
Deb K , Pratap A , Agarwal S , et al. A fast and elitist multiobjective genetic algorithm: NSGA-II[J]. IEEE Transactions on Evolutionary Computation, 2002, 6(2):0-197.
Deb K , Jain H . An Evolutionary Many-Objective Optimization Algorithm Using Reference-Point-Bad Nondominated Sorting Approach, Part I: Solving Problems With Box Constraints[J]. IEEE Transactions on Evolutionary Computation, 2014, 18(4):577-601.
后者（MOEA/D）通过线性或⾮线性的⽅式将原多⽬标问题中各个⽬标进⾏聚合，即将多个⽬标聚合成⼀个⽬标，然后利⽤种群进化不断逼近全局帕累托最优解。这⾥可能有⼈会有疑问：“为什么MOEA/D是基于分解的MOEA，但过程中需要对各个⽬标进⾏聚合？那不就不叫分解了吗？”答案很简单：分解
环境经济分解是指将多⽬标优化问题分解为⼀组单⽬标⼦问题或多个多⽬标⼦问题，利⽤⼦问题之间的邻域关系，通过协作来同时优化所有的⼦问题，从⽽不断逼近全局帕累托最优解；⽽聚合
聚合是指将多个⽬标聚合成⼀个⽬标，因此MOEA/D⾥⾯有“分
解”和“聚合”两个步骤，分解是确定邻域关系，聚合是⽤来⽅便⽐较解的优劣，两者并不是⽭盾的。具体算法就不作详细阐述了，可详
具体算法就不作详细阐述了，可详见以下参考⽂献，或看下⽅的代码实战部分：
Qingfu Zhang, Hui Li. MOEA/D: A Multiobjective Evolutionary Algorithm Bad on Decomposition[M]. IEEE Press, 2007.
那么存在只利⽤聚合⽽
聚合⽽没有分解这⼀步来进化优化的算法吗？答案是存在的，⽐如多⽬标优化⾃适应权重法（awGA），代码详见链接：
这个算法就是通过⾃适应地⽣成⼀个权重向量，来将所有的优化⽬标聚合成单⼀的优化⽬标，然后进⾏进化优化，当然这样效果⾃然⽐不上MOEA/D。
有些单⽬标优化学得⽐较溜的读者可能会疑问：”我找⼀组固定的权重，把各个优化⽬标加权聚合成⼀个⽬标，再⽤单⽬标优化的⽅法进⾏优化不就完事了吗？“答案⾮常简单：如果有理论能证明所找的这组权重是最合理、最适合当前的优化模型的，那么⽤单⽬标优化的⽅法来解决多⽬标优化问题当然是好事；相反，假如没有依据地随便设置⼀组权重，那么肯定不能⽤这种⽅法。
3 代码实战
下⾯以⼀个双⽬标优化测试函数ZDT1和⼀个三⽬标优化测试函数DTLZ1为例，横向对⽐deap、pymoo和geatpy三款进化算法代码包的NSGA2、NSGA3和MOEA/D算法的表现，版本分别为1.3、0.4.0、2.5.0，测试代码均为三款代码包官⽹给出的案例（在代码组织结构上稍作修改以⽅便本⽂显⽰）。
脸部护理
【注】：由于在计算ZDT1和DTLZ1时deap默认采⽤的是循环来计算种群中每个个体的⽬标函数值，⽽pymoo和geatpy均为利⽤numpy 来矩阵化计算的，为了统⼀个体评价时间，避免前者带来的性能下降，这⾥将deap也改⽤与后两者相同的⽅法。
实验设备：cpu i5 9600k，16g ddr4内存，windows10，Python 3.7 x64。
相关库的安装：
pip install deap
pip install pymoo
pip install geatpy
ZDT1的模型为：
其中M为待优化的⽬标个数，y为决策变量。
3.1 ⽤NSGA2 优化 ZDT1
下⾯⽤NSGA2算法来优化上⾯的ZDT1，实验参数为：【种群个体数40，进化代数200，其他相关参数均设为⼀样】，代码1、代码2、代码3分别为⽤deap、pymoo和geatpy的nsga2来优化ZDT1：
代码 1. deap_nsga2.py
import array
import random
from deap import ba
你怎么不在我身边from deap import creator
指路英语from deap import tools
import numpy as np
import matplotlib.pyplot as plt
import time
import time
def ZDT1(Vars, NDIM): # ⽬标函数
ObjV1 = Vars[:, 0]忘记手机锁屏密码怎么办
gx = 1 + 9 * np.sum(Vars[:, 1:], 1) / (NDIM - 1)
hx = 1 - np.sqrt(np.abs(ObjV1) / gx) # 取绝对值是为了避免浮点数精度异常带来的影响
冬字开头的成语ObjV2 = gx * hx
return np.array([ObjV1, ObjV2]).T
toolbox = ba.Toolbox()
# Problem definition
BOUND_LOW, BOUND_UP = 0.0, 1.0
NDIM = 30
def uniform(low, up, size=None):
try:
return [random.uniform(a, b) for a, b in zip(low, up)]
except TypeError:
return [random.uniform(a, b) for a, b in zip([low] * size, [up] * size)]
def main(ed=None):
random.ed(ed)
NGEN = 300
MU = 40
CXPB = 1.0
pop = toolbox.population(n=MU)
# Evaluate the individuals with an invalid fitness
invalid_ind = [ind for ind in pop if not ind.fitness.valid]
ObjV = ZDT1(np.array(invalid_ind), NDIM)
for ind, i in zip(invalid_ind, range(MU)):
ind.fitness.values = ObjV[i, :]
# This is just to assign the crowding distance to the individuals
# no actual lection is done
pop = toolbox.lect(pop, len(pop))
# Begin the generational process
for gen in range(1, NGEN):
# Vary the population
offspring = tools.lTournamentDCD(pop, len(pop))
offspring = [toolbox.clone(ind) for ind in offspring]
for ind1, ind2 in zip(offspring[::2], offspring[1::2]):
if random.random() <= CXPB:
toolbox.mate(ind1, ind2)
toolbox.mutate(ind1)
toolbox.mutate(ind2)
del ind1.fitness.values, ind2.fitness.values
# Evaluate the individuals with an invalid fitness
invalid_ind = [ind for ind in offspring if not ind.fitness.valid]
ObjV = ZDT1(np.array([ind for ind in offspring if not ind.fitness.valid]), NDIM)
for ind, i in zip(invalid_ind, range(MU)):
ind.fitness.values = ObjV[i, :]
# Select the next generation population
pop = toolbox.lect(pop + offspring, MU)
return pop
if __name__ == "__main__":
start = time.time()
pop = main()
end = time.time()
p = np.array([ind.fitness.values for ind in pop])
p = np.array([ind.fitness.values for ind in pop])
plt.scatter(p[:, 0], p[:, 1], marker="o", s=10)
plt.show()
print('耗时：', end - start, '秒')
上述代码1利⽤deap提供的进化算法框架来实现NSGA2算法。deap的主要特点是轻量化和⽀持扩展。
整个deap内部的代码量很少，可以通过”函数注册“来扩展模块，但由此带来的结果便是需要⾃⼰写⼤量的代码。⽐如要在deap上写⼀个基因表达式编程(GEP)，以geppy这个GEP框架为例，它除了使⽤到了deap中的”函数注册“功能（⽅便模块调⽤）外，⼏乎等于重写了⼀遍deap。
代码2：pymoo_nsga2.py
from pymoo.algorithms.nsga2 import NSGA2跄怎么读
from pymoo.factory import get_problem
from pymoo.optimize import minimize
import matplotlib.pyplot as plt
import time
problem = get_problem("ZDT1")
algorithm = NSGA2(pop_size=40, elimate_duplicates=Fal)
海阳旅游度假区start = time.time()
res = minimize(problem,
algorithm,
('n_gen', 300),
verbo=Fal)
end = time.time()
plt.scatter(res.F[:, 0], res.F[:, 1], marker="o", s=10)
plt.show()
print('耗时：', end - start, '秒')
上述代码2调⽤了pymoo内置的NSGA2算法模块，不过该模块与pymoo框架深度耦合，⽆法直观地看到NSGA2的执⾏过程，⾮pymoo开发者想要在上⾯扩展⾃⼰设计的算法会遇到较⼤的困难。
代码3：geatpy_nsga2.py
