Pareto改善
给定固有的一群人和可分配的资源，从一种分配的状态到另一种状态的变化中，在没有人变坏的情况下，使得至少一个人变得更好。
也就是说资源分配的理想状态是不可能再有更多的Pareto改善的状态。
Pareto解
在有多个目标时，由于存在目标之间的冲突无法进行比较的情况，一个解在某个目标上是最好的，在其他目标上可能是最差的，一组目标函数最优解的集合是Pareto最优集，形成的曲面为Pareto前沿面。
进化计算
达尔文在进化论中提出了这样一个概念——物竞天择，适者生存。
进化计算是基于群体的启发式搜索优化问题。
遗传算法
约翰·霍兰德提出了遗传算法，是进化算法的一种。
Step1: ① 种群中个体随机初始化；
② 每个个体通过评价得到一个适应度值；
③ 适应度大的个体有更大的概率留下来；
④适应度大的个体交叉变异产生新的个体；
Step2：不断迭代②~④
经过足够多次的迭代后，最终能够得到好的解。
编码
编码具有三个特点：完备性，健全性，非冗余性。
每个特征都与编码结果一一对应。
适应度评价
位串（个体）->适应度->目标函数。
适应度是用于评价目标函数的一个自定义的函数，优化的方向为适应度增大的方向，对于最小化问题：
其中C_max可以是自己设定的值或者是当代的最大值。
相应的，对于最大化问题：
遗传操作
选择(selection)/复制(reproduction)
选择算子：选择适应度高的个体放入交配池。
交叉
模仿有性繁殖中的基因重组
为交叉概率，随机选择k个交叉位置，根据实行交叉操作。
一般比较大，比如0.8.
变异
模拟有性繁殖中的基因突变。
按
反转某位的二进制字符，一般比较小，比如0.005.
多目标进化
多目标进化
一种常见的优化策略的问题。
凸空间与凹空间
凸集(convexity):一个集合S的任意两个点的连线上的点仍为S中的点。
凹集：与凸集的定义相反。
基于Pareto多目标进化算法的一般框架
多目标Pareto最优解集构造方法
简单方法
通过个体与个体的比较，依次删除被支配的个体。
庄家法
初始化创造集Q，每取出一个个体，就在Q中去除这个个体，去除由这个个体支配的所有个体，若这个个体不被任何一个个体支配，则把它放入NDset。
擂台法
每一轮选出一个擂主，与其他个体进行比较，败者出局，胜者称为新的擂主。
注意需要保留与前一个擂主不相关的个体的比较。
递归法
快速排序方法
个体之间的关系：若x和y不存在支配关系，那么如果y支配x，那么x支配z或者x和z不相关。
快速排序中使用到了一个符号
，按照这个关系进行快速排序：x支配y或者x与y不相关。
每一次拿出一个个体，将群体分为两个部分，一部分是被个体支配的个体，另一部分是由个体支配的个体，被个体支配的个体被清除，进入下一轮比较。
多目标群体的分布性
小生境：把特定环境中有共同特性的组织称为物种。（物以类聚）
基于预选择机制(preselection):若子代的适应度高于父代的适应度，那么可以用子代代替父代。
基于排挤机制(crowding):设置排挤因子CF，选择规模为1/CF的子集为一个排挤子集，计算相似性，用新个体代替相似个体。
基于共享机制(sharing):
定义共享函数
，其中的d(i,j)为个体i和个体j的相似度。
则个体i的共享适应度为
设置共享半径，只计算共享半径以内的个体相似程度
多目标进化中的适应度
目标函数组合法
简单支配关系法
复合支配关系法
用聚类方法保持分布性
个体的相似度计算可以分为
实数编码
欧几里得距离：向量各位差的平方和的开方。
曼哈顿距离：向量各位差的绝对值之和。
明考斯基距离：向量各位差的q次方和的开q次方。
二进制编码
海明距离：向量各位差的平方和的开方。
符号编码
一般用asc2表示各位。
聚类分析
基于中心点
将群体分为m类，选择m个个体为初始中心点
① 计算选出的点与其他点的距离
② 将与选出的点最相似的个体指派到相应的类中，计算评价函数的值
③ 分别在各类中随机选择一个非中心点重复①②，计算E’，若优于E，则代替中心点，重新调整类。
类距离
把n个个体当成n个类，将具有最大相似度的个体聚集到同一类。