智能优化算法求解 ① 传统算法与智能优化算法的比较： 在上述的传统的算法中，整体的思想都是将多目标规划转化为但目标规划问题，如果要得到多个解的话，就要进行多次的运行，无法得到pareto最优解集，整体上的效率并不高。而智能优化算法能在一次运行过程中找到Pareto最优解集中的多个解，且不限于Parato前沿解集的形状和连续性，易于解决不连续的，凹的Pareto前沿。 ② 基于精英策略的快速非支配排序遗传算法（NSGA-II） （1）算法概述 遗传算法( Genetic Algorithm , GA) 是借鉴生物界自然选择和群体进化机制形成的一种全局寻优算法。为方便理解，首先从宏观角度了解遗传算法。 在遗传算法中，将问题空间的决策变量通过一定的编码方法转换为遗传空间中的个体。将目标函数转化成为一定的适应值，这个适应值将作为评价个体优劣的依据。 遗传算法中涉及到三个算子：选择算子，交叉算子和变异算子，这三个算子模拟了种群遗传和变异产生后代，并且适者生存的过程。其中选择算子反映了“适者生存”，通过种群个体的“适应值”判断个体能否被加入交配池进行交配产生“子代个体”。交叉算子则是模拟种群产生个体的过程，互相交换“染色体”完成产生下一代的过程，而这里的染色体可以理解为编码的序列，具体的我们下面会通过一个例子进行说明。最后变异算子则是较小概率的改变个体的“染色体序列”，实现新个体的出现。 需要说明的是遗传算法中需要确定的参数有：编码串长度、种群大小、交叉和变异概率。编码串长度由优化问题所要求的求解精度决定。种群大小表示种群中所含个体的数量 ,种群较小时,可提高遗传算法的运算速度 ,但却降低了群体的多样性，可能找不出最优解;种群较大时 ,又会增加计算量 ,使遗传算法的运行效率降低。一般取种群数目为20～100。交叉操作是遗传算法中产生新个体的最主要的方法，所以交叉的概率应该设定得比较大，保证种群能进行充分的交配，但若过大可能破坏群体的优良模式。一般取 0. 4～0. 99。变异概率也是影响新个体产生的一个因素,变异概率小 ,产生新个体少;变异概率太大 ,又会使遗传算法变成随机搜索。一般取变异概率为0. 0001～0. 1。遗传算法常采用 的收敛判据有:规定遗传代数;连续几次得到的最优个 体的适应值没有变化或变化很小等。 下面我们给出遗传算法的流程图，说明遗传算法的主要流程： 首先，建立一个随机的种群规模大小为 N 的初始种群P_0,并初始化计数器 t=0。然后对种群 P_t进行遗传操作产生子代种群Q_t，将P_t和Q_t合并产生R_t，并对具有 2N 规模的种群R_t进行非劣分类操作，并生成下一代种群P_(t+1)。 进化代数计数器 t 加 1 并判断 t 是否大于最大进化代数 MaxGen。如果是，那么该算法结束；否则，继续进化。如此循环，直到进化到指定的最大进化代数。 每一个个体都有其对应的适应值，正如每一个决策变量都有其对应的目标函数值。非劣分类操作的原则即是根据上述的由优化问题的目标函数对应转换成的个体的适应值来进行筛选。在进行非劣分类排序时需要保存的值有两个S_p和n_p。S_p对应的被个体p支配的集合，n_p对应个体p被多少个其他的个体所支配，保存这个被其他个体的个数，即是n_p。这个过程也被称为“快速非支配排序算法”的过程。 我们以需求目标最小值来描述“快速非支配排序算法”过程： 首先找出n_p=0的所有点，即这些点不被任何点所支配，并且保存这些点的S_p，将这些点标记为Pareto等级①。不考虑等级①的点（即图中蓝色的点，或者说删除这些点），在剩余的点中继续寻找n_p=0的点，标记为Pareto等级②……以此类推分完所有的等级。其中①中的解是最好的，也就是前面所提到的精英解集，它只支配其他解而不被其他任何解支配，②中的个体只被 ①不被其它解支配，依次类推。 但在实际的操作中，并不需要完成对所有的等级的分类——由于整个种群R_t的种群大小为2N，新种群P_(t+1)的N个位置不能容纳所有的非劣等级。当考虑被允许的最后一个等级中的解时，该非劣等级可能存在比新种群剩下位置更多的个体。在这种情况下，使用密度估计的方法从最后一等级选择位于该等级较稀疏区域的个体填充满新种群。这里着重要指出的是R_t的非劣分类和P_(t+1)填充过程可以一起执行。这样，对每一个非劣等级先看它的大小,看它是否 能被新种群容纳，如果不能，那么就不必再进行非劣分类，这样能减少该算法的运行时间。 b. 拥挤选择算子以及交叉算子与变异算子的实现 拥挤距离的定义 在上述的“快速非支配排序算法”的叙述中，我们提到了“密度估计”，需要选择较为“疏松”的个体填充P_(t+1)中不足的个体数量。这样是为了使Pareto Front宽广度和均匀度更加合理。 拥挤距离：第i个个体的拥挤距离定义为第i+1和i-1个体的所有目标函数值的差的和。第一个和最后一个个体的距离设为无穷大—— 拥挤选择算子 下面给出拥挤距离的求解算法： 第一步：对该层（等 Pareto 排序值）的所有点排序，排序结果如上图所示。 对于两个目标函数值的而言，先选择其中一个目标函数 然后按照该目标函数值从小到大的顺序进行排列，按式（3）计算距离，进而可以用下面的第三步计算拥挤距 离，至到累积完所有的目标函数。 第二步：每个点的拥挤距离d_i初始化为 0； 伪代码如下：