遗传算法复杂度

Ⅶ 多目标优化问题

形式化定义：

特点：

①包含多个可能有冲突的目标函数。

②希望找到能够很好平衡全部优化目标的解集；

帕累托最优是指资源分配的一种理想状态。给定固有的一群人和可分配的资源，如果从一种分配状态到另一种分配状态，在没有使得任何人的境况变坏的前提下，使得至少有一个人变得更好，这就是帕累托改善的状态；换言之，不可能在不是任何其他人受损的情况下再改善某些人的境况。

支配（Dominace） ：当x1和x2满足如下条件时称x1支配x2：①对于所有目标函数x1不比x2差；②至少在一个目标函数上，x1严格比x2要好。

对于点1和点2：对于目标函数f1是越大越好，在取相同f2时，点1比点2好；对于目标函数f2是越小越好，在取相同f1时，点1比点2好。所以点1支配点2。

对于点1和点4：目标函数f1上，取相同f2时，点4比点1好；目标函数f2上，取相同f1时，点1比点4好。所以点1和点4互不支配。

不可支配解集（Non-dominated solution set） ：当一个解集中任何一个解都不能被该集合中其他解支配，那么就称该解集为不可支配解集。

帕累托最优解集（Pareto-optimal set ）：所有可行中的不可支配解集被称为帕累托最优解集。

帕累托最优前沿面（Pareto-optimal front） ：帕累托最优解集的边界（boundary）被称为帕累托最优前沿面。

多目标优化问题的目标 ：①寻找尽可能接近最优的解集；②尽可能增大找到解的多样性。

优点：简单

缺点：①很难设定一个权重向量能够获得帕累托最优解；②在一些非凸情况下不能够保证获得帕累托最优解。

优点：能够应用到凸函数和非凸函数场景下。

缺点：函数需要精心选择，需要在独立函数的最小值或最大值之内。

优点：weighted Techebycheff metirc能够保证获得所有帕累托最优解。

缺点：①需要有每个函数最大值和最小值的先验知识；②需要每个目标函数的z*能够独立被找到；③对于较小的p值，不一定保证所有能够获得所有的帕累托最优解；④随着p增加，问题会变得不可求导。

①随机产生初始种群；

②计算各点的目标函数值和约束函数值；

③根据目标函数值对种群分级；

④根据约束函数值和分级结果计算各点的约束罚项、劣解罚项及总罚项；

⑤根据各点的总罚项计算适应度；

⑥根据各点的适应度，进行选择、交叉和变异操作，生成新种群；

⑦将总罚项为0的点放入非劣解集候选表，对候选表进行检查，保留第1级非劣点，删除其他点；

⑧检查是否收敛，如没有，转到步骤②；

⑨删除候选表中与其他店距离太近的点；

⑩输出候选表中的帕累托最优解集及对应的目标函数值；

最后，决策人根据个人偏好从帕累托最优解集中挑选出最适合该问题的解。

遗传算法相比传统的算法的优点是能够得到一个最优解集，而不是单单一个最优解，这样会提供更多的选择，但是计算的复杂度可能稍高，而且里面涉及的一些函数需要精心设计。

1.权重系数转换法

对每个目标函数fi(x)赋予权重wi，wi为目标函数的重要程度。μ=Σwi·fi(x)，这里就将多目标转化为单目标函数，将μ作为评价函数。

2.并列选择法

主要步骤：(1)将种群按照目标函数个数等分为子种群，为每个子种群分配一个目标函数。(2)将子种群中的个体按照各自的目标函数选择出适应度高的个体，然后将其组成一个子种群。(3)再将子种群进行交配、变异、生成下一代父亲种群。然后再重复第一步。

并列选择法的缺点在于易于生成单个目标函数的极端最优解，而较难生成一种多个目标在某种程度上都比较满意的折中解。

3.排序选择法

基本思想就是基于“帕累托最优个体”的概念对群体中的个体进行排序，然后根据这个次序进行种群选择。这样的话，就能够让帕累托最优个体有更多的机会遗传到下一代。这种方法的缺点是仅仅度量了各个个体之间的优越次序，而并未度量各个个体的分散程度，所以容易生成相似的解，而不是分布较广的多个最优解。

4.共享函数法

针对排序选择方法的缺点，即所求的几个最优解通常都是集中于最优解集合的某一个小区域内，而不是分散在整个帕累托最优解集合。由此，引出了基于共享函数的 小生境技术 （小生境技术就是将每一代个体划分为若干类，每个类中选出若干适应度较大的个体作为一个类的优秀代表组成一个群，再在种群中，以及不同种群中之间，杂交，变异产生新一代个体群。同时采用预选择机制和排挤机制或分享机制完成任务。）。该算法对相同个体或类似个体的数目加以限制，以便能够产生出种类较多的不同的最优解。这就引出一个问题，怎么衡量两个个体之间的相似度？这就是小生境数。顾名思义，小生境就是在一个小环境中相似的个体种群。最常见的公式为：

s(d)为共享函数，是表示群体中两个个体之间密切关系程度的一个函数。d(X,Y)为个体X,Y之间的hanmin距离，也是用于衡量个体间相似度的一个函数。在计算出小生境数后，可以是小生境数较小的个体能够有更多的机会被选中，遗传到下一代群体中，即相似程度较小的个体能够有更多的机会被遗传到下一代群体中。

缺点：每次选择操作时都需要进行大量的个体之间的优越关系的评价和比较运算，使得算法搜索效率较低。

5.Horn和Nafploitis印的基于小生境帕累托多目标遗传算法(NPGA)

类似于第2个的并列选择法，将每一代个体划分为若干类，每个类别选出若干适应度较大的个体作为一个类的优秀代表组成一个种群，然后交配变异产生新一代种群。基于这种小生境的遗传算法（Niched Genetic Algorithms，NGA），可以更好地保持解的多样性，同时具有很高的全局寻优能力和收敛速度，特别适合于复杂多峰函数的优化问题。

6.Srinvivas和Deb的非支配排序遗传算法NSGA

1980年提出来的，在遗传算法的基础上对选择再生方法进行改进：将每个个体按照他们的支配和非支配关系进行再分层，再做选择操作，从而达到目的。

其分层的含义就是取出种群中的非支配个体组成一个小种群（第一个非支配最优层），并赋予其中所有个体一个共享的虚拟适应度值。然后再取出个体后的种群中继续取出非支配个体，再将它们组成一个小种群（第二个非支配最优层），并且赋予所有个体一个共享的虚拟适应度值。重复上述步骤，直到原始种群分配完毕，这就是分层，也叫非支配型排序。

非支配型排序遗传算法的缺点：①计算复杂度较高；②没有精英策略；③需要制定共享半径。

针对以上问题，k·Deb 于2002年提出了 7 的方法。

7.带精英策略的非支配排序遗传散发——NSGAII

1).采用快速非支配型排序，降低了算法复杂度。其复杂度降为了O(MN**2)。

2).提出了拥挤度和拥挤度比较算子，代替需要指定共享半径的适应度共享策略。并在快速排序后的同级比较中作为胜出标准。使准pareto解中的个体能扩展到整个pareto域中，并均匀分布，保持了种群的多样性。

3).引入精英策略，扩大采样空间。将父代种群和子代种群合并，保证优良个体能够留存下来。

其算法步骤如下：1.首先随机产生数量为n的初始种群，然后对其进行非支配型排序。接下来，就是常规的选择，交叉，变异操作产生第一代子代种群。2.然后，从第二代开始，将父代和子代合并。然后对其进行快速非支配型排序，同时计算每个非支配层的个体进行拥挤度的计算。然后根据非支配关系和拥挤度来选择合适的个体组成新的父代种群。最后通过再通过选择，交叉，变异产生子代。3.接下来，重复第二步。

具体做法参考：https://blog.csdn.net/quinn1994/article/details/80679528/

Ⅷ 遗传算法和粒子群算法比较过程中，可以用那些指标进行比较

时间复杂度、空间复杂度、稳定性、求解精度等等

Ⅸ 请问简单遗传算法的时间复杂度和空间复杂度是多少

遗传算法其实就是二重迭代，时间复杂度不超过n平方
空间复杂度自己计算吧

Ⅹ 请问怎样确定遗传算法的参数

遗传算法的参数设计对于不同的实际问题都不同
目前还没有完整的理论来参考

种群大小越大 收敛效果越好 但计算量也会增大
在空间复杂度（内存大小）和计算速度允许的情况下 尽量大一些 不过如果问题的解空间不大或者是变化的话 则要另加考虑（解空间不大就没必要把种群定得很大了）

交叉率。。。一般都是全部参与交叉（染色体都会交叉嘛） 只是交叉方式的设计问题，有单点，多点，随机等等 另外还要考虑交叉后解的可行性 对于具体问题，可以各种方法都试一下（这方面的理论实在是很弱）

变异率不要设高，一般在%5以下，变异是为了避免把个体局限在较优的局部解空间内（模拟退火算法就有这个问题，所以经常会结合遗传算法）

总结一下，这个算法的理论支持目前还较弱，但是很实用，反正算得快，多算几遍，参数多改改，一般和近似解都很接近