3月13~19日学习总结
关于Jenetics库的学习
这是一个开源的遗传算法库，可以使用maven直接引入的项目中使用方便，而且扩展性好。
在Jenetics中，遗传算法的优化过程主要包括以下步骤：
-
初始化种群：生成一组随机的个体作为种群，每个个体代表一种可能的解决方案。
-
适应度评估：对于每个个体，计算其适应度（fitness），即其解决方案在问题域中的优劣程度。
-
选择：根据适应度，选择出一组优秀的个体，作为繁殖下一代的父母。
-
交叉：对于选出的父母个体，通过交叉（crossover）操作，生成新的后代个体。
-
变异：对于新生成的后代个体，通过变异（mutation）操作，产生一些变异的后代。
-
更新种群：将新生成的后代个体与原有个体进行合并，形成新一代的种群。
-
终止条件：检查是否达到了终止条件（如最大迭代次数、收敛性等），如果达到则停止算法，返回最优解。
我们使用Jenetics定制遗传算法的条件就是使用算子。
算子
是指用于产生新一代个体的操作
Jenetics提供了各种不同的算子，包括选择算子（selection operator）、交叉算子（crossover operator）和变异算子（mutation operator），以便用户可以根据自己的需求来定制算法。
1.选择算子
选择算子用于根据个体的适应度值来选择下一代的个体。Jenetics提供了多种不同的选择算子，包括轮盘赌算子（Roulette Wheel Selection）、排名选择算子（Rank Selection）和竞赛选择算子（Tournament Selection）等。
轮盘赌算子的具体规则
-
计算当前种群中所有个体的适应度总和。
-
对于每个个体，计算其适应度占适应度总和的比例，得到其选择概率。
-
在0到1之间随机生成一个数p，选择第一个满足选择概率之和大于等于p的个体作为父母。
-
重复步骤3，选择第二个父母。
-
将选出的两个父母作为交叉和变异操作的输入，生成新一代种群。
优缺点
轮盘赌算子的优点是简单易实现，适用于种群适应度分布比较均匀的优化问题。但是，当种群适应度分布较不均匀时，轮盘赌算子可能会出现早熟（premature convergence）的问题，即算法很快陷入局部最优解而无法发现更好的解决方案。
锦标赛选择（Tournament Selector）是Jenetics中一种常用的选择算子，它模拟了一个个体之间的比赛，通过不断地选出胜者来选择优秀的个体作为父母，进一步产生新一代种群。
锦标赛选择算子的步骤如下：
-
随机选择一定数量（通常为2或3）的个体，称为锦标赛选手。
-
从锦标赛选手中选择适应度最好的个体作为父母。
-
重复步骤1和2，选择第二个父母。
-
将选出的两个父母作为交叉和变异操作的输入，生成新一代种群。
对于适应度分布不均匀的算子，使用排名选择算子或者竞赛选择算子比较好
这两种算子的差别是排名选择算子不容易被较差的个体所取代，但是实现复杂，而且性能比较差
竞赛选择算子就是容易实现，性能高，但是会有较差个体被选中的情况。
交叉算子 ：用于将两个父母的基因组合并，生成新的后代。Jenetics提供了多种交叉算子，如单点交叉（SinglePointCrossover）、多点交叉（MultiPointCrossover）、均匀交叉（UniformCrossover）等。
比较优秀的是多点交叉。
不容易陷入局部最优解。
实现步骤
-
随机选择多个交叉点，该点位于两个父代染色体的相同位置处。
-
交换交叉点之间的基因片段，生成两个新的后代染色体。
-
将两个新的后代染色体添加到新一代种群中。
对于染色体的解释。
在遗传算法中，染色体（Chromosome）是指一个个体在遗传层面上的表现形式，是由一条线性的DNA序列组成的。染色体的每个位置上都有一个基因（Gene），每个基因可以编码一个特定的特征或参数，比如在优化问题中，基因可以表示一个决策变量的取值。
举例，而在求解排列问题中，可以将每个位置的编号作为基因，并将这些基因随机排列组成染色体的编码。也就是说对于每一种可能的排列结果是作为一个个体，然后对于每一个位置的选择作为基因，这些基因组成了染色体，也就是每个个体。
变异算子（Mutation Operators）：用于在基因组中随机改变一些基因，以产生变异的后代。Jenetics提供了多种变异算子，如位变异（BitwiseMutation）、高斯变异（GaussianMutator）等。
交换变异算子
实现步骤
-
随机选择两个位置，将它们的基因值进行交换。
-
重复以上步骤，直到满足变异概率的要求。
交换变异算子可以增加染色体的多样性，有助于避免陷入局部最优解。需要注意的是，变异概率需要根据具体情况进行设置，通常建议设置为较小的值，以避免变异过度导致优化结果变差。
对于我准备写的排班系统中，准备使用的是锦标赛选择算子，多点交叉算子，交换变异算子。
染色体设计
可以考虑使用多维数组作为染色体来表示，其中每一个维度代表一个班次，每个班次的取值范围为员工的编号。例如，如果有3个班次，6名员工，则可以设计一个3维数组，大小为3 x 7 x 6，其中第一维表示班次，第二维表示星期几，第三维表示员工编号。每个元素的取值为0或1，表示该员工是否在该班次上班。
然后对于偏好值可以设置在偏好时间的基因的权重，来做到让员工尽量在他偏好的工作时间进行工作。
然后就是对于算子的参数设置。
锦标赛选择算子：选择合适的锦标赛选手数量和比例
也就是进行选择的数量和选择出来的比例
多点交叉：选择合适的交叉点数量和比例
交换变异：变异概率需要根据具体情况进行设置，通常设置为较小的值。
然后设置最大迭代次数为1000次，完成后输出结果。
这就是我准备设计排班遗传算法的思路。