非支配排序算法
一、插入排序
介绍
插入排序的基本操作就是将一个数据插入到已经排好序的有序数据中，从而得到一个新的、个数加一的有序数据。
算法适用于少量数据的排序，时间复杂度为O(n^2)。
插入排算法是稳定的排序方法。
步骤
①从第一个元素开始，该元素可以认为已经被排序
②取出下一个元素，在已经排序的元素序列中从后向前扫描
③如果该元素（已排序）大于新元素，将该元素移到下一位置
④重复步骤3，直到找到已排序的元素小于或者等于新元素的位置
⑤将新元素插入到该位置中
⑥重复步骤2
排序演示
算法实现
二、冒泡排序
介绍
冒泡排序（Bubble Sort）是一种简单的排序算法，时间复杂度为O(n^2)。
它重复地走访过要排序的数列，一次比较两个元素，如果他们的顺序错误就把他们交换过来。走访数列的工作是重复地进行直到没有再需要交换，也就是说该数列已经排序完成。
这个算法的名字由来是因为越小的元素会经由交换慢慢“浮”到数列的顶端。
原理
循环遍历列表，每次循环找出循环最大的元素排在后面；
需要使用嵌套循环实现：外层循环控制总循环次数，内层循环负责每轮的循环比较。
步骤
①比较相邻的元素。如果第一个比第二个大，就交换他们两个。
②对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。在这一点，最后的元素应该会是最大的数。
③针对所有的元素重复以上的步骤，除了最后一个。
④持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。
算法实现：
三、快速排序
介绍
快速排序（Quicksort）是对冒泡排序的一种改进，借用了分治的思想，由C. A. R. Hoare在1962年提出。
基本思想
快速排序的基本思想是：挖坑填数 + 分治法。
首先选出一个轴值(pivot，也有叫基准的)，通过一趟排序将待排记录分隔成独立的两部分，其中一部分记录的关键字均比另一部分的关键字小，则可分别对这两部分记录继续进行排序，以达到整个序列有序。
实现步骤
①从数列中挑出一个元素，称为 “基准”（pivot）；
②重新排序数列，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面（相同的数可以到任一边）；
③对所有两个小数列重复第二步，直至各区间只有一个数。
排序演示
算法实现
四、希尔排序
介绍
希尔排序（Shell Sort）是插入排序的一种，也是缩小增量排序，是直接插入排序算法的一种更高效的改进版本。希尔排序是非稳定排序算法，时间复杂度为：O(1.3n)。
希尔排序是基于插入排序的以下两点性质而提出改进方法的：
·插入排序在对几乎已经排好序的数据操作时， 效率高， 即可以达到线性排序的效率；
·但插入排序一般来说是低效的， 因为插入排序每次只能将数据移动一位。
基本思想
①希尔排序是把记录按下标的一定量分组，对每组使用直接插入算法排序；
②随着增量逐渐减少，每组包1含的关键词越来越多，当增量减至1时，整个文件恰被分成一组，算法被终止。
排序演示
算法实现
五、选择排序
介绍
选择排序(Selection sort)是一种简单直观的排序算法，时间复杂度为Ο(n2)。
基本思想
选择排序的基本思想：比较 + 交换。
第一趟，在待排序记录r1 ~ r[n]中选出最小的记录，将它与r1交换；
第二趟，在待排序记录r2 ~ r[n]中选出最小的记录，将它与r2交换；
以此类推，第 i 趟，在待排序记录ri ~ r[n]中选出最小的记录，将它与r[i]交换,使有序序列不断增长直到全部排序完毕。
排序演示
选择排序的示例动画。红色表示当前最小值，黄色表示已排序序列，蓝色表示当前位置。
算法实现
六、堆排序
介绍
堆排序（Heapsort）是指利用堆积树（堆）这种数据结构所设计的一种排序算法，它是选择排序的一种。
利用数组的特点快速指定索引的元素。
基本思想
堆分为大根堆和小根堆，是完全二叉树。
大根堆的要求是每个节点的值不大于其父节点的值，即A[PARENT[i]] >=A[i]。
在数组的非降序排序中，需要使用的就是大根堆，因为根据大根堆的要求可知，最大的值一定在堆顶。
排序演示
算法实现
七、归并排序
介绍
归并排序（Merge sort）是建立在归并操作上的一种有效的排序算法。该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。
基本思想
归并排序算法是将两个（或两个以上）有序表合并成一个新的有序表，即把待排序序列分为若干个子序列，每个子序列是有序的。然后再把有序子序列合并为整体有序序列。
算法思想
自上而下递归法（假如序列共有n个元素）
① 将序列每相邻两个数字进行归并操作，形成 floor(n/2)个序列，排序后每个序列包含两个元素；
② 将上述序列再次归并，形成 floor(n/4)个序列，每个序列包含四个元素；
③ 重复步骤②，直到所有元素排序完毕。
自下而上迭代法
① 申请空间，使其大小为两个已经排序序列之和，该空间用来存放合并后的序列；
② 设定两个指针，最初位置分别为两个已经排序序列的起始位置；
③ 比较两个指针所指向的元素，选择相对小的元素放入到合并空间，并移动指针到下一位置；
④ 重复步骤③直到某一指针达到序列尾；
⑤ 将另一序列剩下的所有元素直接复制到合并序列尾。
排序演示
算法实现
八、基数排序
介绍
基数排序（Radix Sort）属于“分配式排序”，又称为“桶子法”。
基数排序法是属于稳定性的排序，其时间复杂度为O (nlog(r)m) ，其中 r 为采取的基数，而m为堆数。
在某些时候，基数排序法的效率高于其他的稳定性排序法。
基本思想
将所有待比较数值（正整数）统一为同样的数位长度，数位较短的数前面补零。然后，从最低位开始，依次进行一次排序。这样从最低位排序一直到最高位排序完成以后，数列就变成一个有序序列。
基数排序按照优先从高位或低位来排序有两种实现方案：
MSD（Most significant digital） 从最左侧高位开始进行排序。先按k1排序分组, 同一组中记录, 关键码k1相等,再对各组按k2排序分成子组, 之后, 对后面的关键码继续这样的排序分组, 直到按最次位关键码kd对各子组排序后. 再将各组连接起来,便得到一个有序序列。MSD方式适用于位数多的序列。
LSD （Least significant digital）从最右侧低位开始进行排序。先从kd开始排序，再对kd-1进行排序，依次重复，直到对k1排序后便得到一个有序序列。LSD方式适用于位数少的序列。
排序效果
算法实现
九、总结
各种排序的稳定性、时间复杂度、空间复杂度的总结：
平方阶O(n²)排序：各类简单排序：直接插入、直接选择和冒泡排序；
从时间复杂度来说：
线性对数阶O(nlog₂n)排序：快速排序、堆排序和归并排序；
O(n1+§))排序，§是介于0和1之间的常数：希尔排序 ；
线性阶O(n)排序：基数排序，此外还有桶、箱排序。
2. 多目标优化问题
形式化定义：
特点：
①包含多个可能有冲突的目标函数。
②希望找到能够很好平衡全部优化目标的解集；
帕累托最优是指资源分配的一种理想状态。给定固有的一群人和可分配的资源，如果从一种分配状态到另一种分配状态，在没有使得任何人的境况变坏的前提下，使得至少有一个人变得更好，这就是帕累托改善的状态；换言之，不可能在不是任何其他人受损的情况下再改善某些人的境况。
支配（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/
3. 学习多目标优化需要掌握哪些python知识
多目标优化
目标优化问题一般地就是指通过一定的优化算法获得目标函数的最优化解。当优化的目标函数为一个时称之为单目标优化(Single-
objective Optimization Problem,
SOP)。当优化的目标函数有两个或两个以上时称为多目标优化(Multi-objective Optimization Problem,
MOP)。不同于单目标优化的解为有限解，多目标优化的解通常是一组均衡解。
多目标优化算法归结起来有传统优化算法和智能优化算法两大类。
1. 传统优化算法包括加权法、约束法和线性规划法等，实质上就是将多目标函数转化为单目标函数，通过采用单目标优化的方法达到对多目标函数的求解。
2. 智能优化算法包括进化算法（Evolutionary Algorithm, 简称EA）、粒子群算法（Particle Swarm Optimization, PSO）等。
Pareto最优解：
若x*∈C*,且在C中不存在比x更优越的解x，则称x*是多目标最优化模型式的Pareto最优解，又称为有效解。
一般来说，多目标优化问题并不存在一个最优解，所有可能的解都称为非劣解，也称为Pareto解。传统优化技术一般每次能得到Pareo解集中的一个，而
用智能算法来求解，可以得到更多的Pareto解，这些解构成了一个最优解集，称为Pareto最优解。它是由那些任一个目标函数值的提高都必须以牺牲其
他目标函数值为代价的解组成的集合,称为Pareto最优域，简称Pareto集。
Pareto有效(最优)解非劣解集是指由这样一些解组成的集合：与集合之外的任何解相比它们至少有一个目标函数比集合之外的解好。
求解多目标优化问题最有名的就是NSGA-II了，是多目标遗传算法，但其对解的选择过程可以用在其他优化算法上，例如粒子群，蜂群等等。这里简单介绍一下NSGA-II的选择算法。主要包含三个部分：
1. 快速非支配排序
要先讲一下支配的概念，对于解X1和X2，如果X1对应的所有目标函数都不比X2大（最小问题），且存在一个目标值比X2小，则X2被X1支配。
快速非支配排序是一个循环分级过程：首先找出群体中的非支配解集，记为第一非支配层，irank=1（irank是个体i的非支配值），将其从群体中除去，继续寻找群体中的非支配解集，然后irank=2。
2. 个体拥挤距离
为了使计算结果在目标空间比较均匀的分布，维持种群多样性，对每个个体计算拥挤距离，选择拥挤距离大的个体，拥挤距离的定义为：
L[i]d=L[i]d+(L[i+1]m−L[i−1]m)/(fmaxm−fminm)
L[i+1]m是第i+1个个体的第m目标函数值，fmaxm 和 fminm是集合中第m个目标函数的最大和最小值。
3. 精英策略选择
精英策略就是保留父代中的优良个体直接进入子代，防止获得的Pareto最优解丢失。将第t次产生的子代种群和父代种群合并，然后对合并后的新种群进行非支配排序，然后按照非支配顺序添加到规模为N的种群中作为新的父代。
4. NSGA_2需不需要像遗传算法那样计算适应度函数
不需要的，NSGA-II里直接通过非支配排序来分级，后面再根据分级和精英保留策略来选择更好的解
5. NSGA2算法
多目标的遗传算法。刚看的。希望能帮助你……
其实其他方面都和普通的遗传算法差不多，只是在选择之前，要进行非支配排序，并且要计算crowding distance，选择的时候，选择非支配的rank小的，如果同意的rank时，选择distance大的。