Question

遗传算法

Answer 1

例如：[1,2,3]，[1,3,2]，[3,2,1]均是函数 3x+4y+5z<100 的可行解（代进去成立即为可行解），那么这些可行解在遗传算法中均称为“染色体”。可行解由 3 个元素构成，每个元素都称为染色体的一个基因。

遗传算法在运行过程中会进行 N 次迭代，每次迭代都会生成若干条染色体。适应度函数会给本次迭代中生成的所有染色体打个分，来评判这些染色体的适应度，然后将适应度低的染色体淘汰，只保留适应度高的染色体，从而讲过若干次迭代后染色体的质量将越来越好。

遗传算法每次迭代会生成 N 条染色体，在遗传算法中一次迭代被称为一次进化。每次进化新的染色体生成的方法——交叉。

每一次进化完成后，都要计算每一条染色体的适应度+适应度概率。在交叉过程中就需要根据这个概率来选择父母染色体。适应度高的染色体被选中的概率越高。（这就是遗传算法能够保留优良基因的原因）

交叉能保证每次进化留下优良的基因，但它仅仅是对原有的结果集进行选择，基因还是那么几个，只不过交换了它们的顺序。这只能保证 N 次进化后，计算结果更接近于局部最优解，而永远没办法达到全局最优解（？？？？？），为了解决这个问题，需引入变异。

假设每次进化都需要生成 N 条染色体，那么每次进化中，通过交叉方式需要生成 N-M 条，剩余的 M 条染色体通过复制上一代适应度最高的 M 条染色体而来。

本文的目标是使所有任务的总处理时间最少，时间越短适应度越大。适应度 = 1 / 所有任务的总处理时间

将任务从 0 开始编号，用一个一维数组存储每个任务的时长

tasks[i] ：表第 i 个任务的长度。
第 0 个任务的长度为 2；
第 1 个任务的长度为 4；
第 2 个任务的长度为 6；
第 3 个任务的长度为 8；

将处理器节点从 0 开始编号，用一个一维数组存储每个处理器的处理速度（单位时间内可处理的长度）

nodes[i] 表第 i 个节点的处理速度。
第 0 个节点的处理速度为 2；
第 1 个节点的处理速度为 1。

timeMatrix[i][j] 表第 i 个任务在第 j 个节点上处理的话，所需处理时间。

一个可行解就是一个染色体，就是一个一维数组

chromosome[i]=j 表将第 i 个任务分配到节点 j 上处理（任务编号从 0 开始；节点编号从 0 开始）

将任务 0 分配给 3 号节点处理；
将任务 1 分配给 2 号节点处理；
将任务 2 分配给 1 号节点处理；
将任务 3 分配给 0 号节点处理。

记录本次进化生成的 N 条染色体的适应度，将染色体从 0 开始编号。

adaptablility[i] 表第 i 个染色体的适应度

selectionProbability[i] 表第 i 个染色体的适应度概率，所有染色体的适应度概率和为 1 。

java中PriorityQueue优先级队列使用方法

第 2 次迭代结果

第 100 次迭代结果