遗传算法
最近开发了一个模型辨识的软件，发现在计算速度方面需要进行优化，于是查找优化相关的算法，这两天在网上搜了搜关于遗传算法相关的资料，记录一下自己对遗传算法的理解。
遗传算法通过模拟自然界生物种群进化的过程，通过选择、交叉、变异等机制，在某个范围的解空间内寻找一个最优解。遗传算法中通过适应度函数（可以看做目标函数的变形）来评价一个个体（解）与最优解的近似程度，设计适应度函数一定意义上与问题本身的目标函数线性相关。
遗传算法的组成：
1.编码。把解空间内的元素用一定的编码方式表示（常见为二进制数）。
2.初始化群体。选定种群大小（每次迭代过程中需要计算、评价的解的个数），随机填充
3.适应度。根据适应度函数对种群进行排序。
4.遗传算子。即通过选择、交叉、变异产生下一代种群。
5.根据终止判定法则判断是否已找到最优解或者继续循环。
这里有几个问题：
遗传算法的优点在于无需对解空间内的每一个解进行计算和比较，一定程度上优化了计算速度，但是收敛速度具有随机性。这里我对遗传算法还有一些疑问：假如解空间的规模不是很大，例如几百，那么如果选取的种群太大，可能进行一两次迭代就几乎遍历了解空间内的所有元素，与顺序遍历没什么差别；如果选取的种群太小，进行交叉、变异操作时，由于基数小，会不会导致算法停滞？（子代与父代完全相同）
选择（以轮盘赌选择方法为例）是不是相当于对父代进行种群大小次数的选择，产生子代，那么子代中适应度较高的解会重复出现，适应度越高偿付概率越大。重复项需要剔除，然后从解空间内随机填充吗？还是说保留重复项？（同理交叉、变异种出现的重复项如何处理？）
另外，该如何终止判定法则该如何确定？
遗传算法简单易懂的例子
遗传算法的例子如下：求解函数 f（x） ＝ x ＋ 10＊sin（5＊x） ＋ 7＊cos（4＊x） 在区间［0，9］的最大值。对于求解函数最大值问题，一般选择二进制编码：实数编码：直接用实数表示基因，容易理解且不需要解码过程，但容易过早收敛，从而陷入局部最优；二进制编码：稳定性高，种群多样性大，但需要的存储空间大，需要解码且难以理解。以目标函数 f（x） ＝ x ＋ 10sin（5x） ＋ 7cos（4x）， x∈［0，9］ 为例。设定求解的精度为小数点后4位，可以将x的解空间划分为 （9－0）×（1e＋4）＝90000个等分。2＾16＜90000＜2＾17，需要17位二进制数来表示这些解。换句话说，一个解的编码就是一个17位的二进制串。这些二进制串是随机生成的。一个这样的二进制串代表一条染色体串，这里染色体串的长度为17。对于任何一条这样的染色体将它复原（解码）到［0，9］这个区间中。可以采用以下公式来解码：x ＝ 0 ＋ decimal（chromosome）×（9－0）／（2＾17－1）decimal（ ）（ 将二进制数转化为十进制数。）一般化解码公式：f（x）， x∈［lower＿bound， upper＿bound］x ＝ lower＿bound ＋ decimal（chromosome）×（upper＿bound－lower＿bound）／（2＾chromosome＿size－1）f（x）， x∈［lower＿bound， upper＿bound］x ＝ lower＿bound ＋ decimal（chromosome）×（upper＿bound－lower＿bound）／（2＾chromosome＿size－1）lower＿bound：函数定义域的下限。upper＿bound：函数定义域的上限。chromosome＿size：染色体的长度。通过上述公式，我们就可以成功地将二进制染色体串解码成［0，9］区间中的十进制实数解。
遗传算法
例如：[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 次迭代结果
粒子群算法的优缺点
优点：PSO同遗传算法类似，是一种基于迭代的优化算法。系统初始化为一组随机解，通过迭代搜寻最优值。同遗传算法比较，PSO的优势在于简单容易实现，并且没有许多参数需要调整。缺点：在某些问题上性能并不是特别好。网络权重的编码而且遗传算子的选择有时比较麻烦。最近已经有一些利用PSO来代替反向传播算法来训练神经网络的论文。扩展资料：注意事项：基础粒子群算法步骤较为简单。粒子群优化算法是由一组粒子在搜索空间中运动，受其自身的最佳过去位置pbest和整个群或近邻的最佳过去位置gbest的影响。对于有些改进算法，在速度更新公式最后一项会加入一个随机项，来平衡收敛速度与避免早熟。并且根据位置更新公式的特点，粒子群算法更适合求解连续优化问题。参考资料来源：百度百科-粒子群算法
什么是粒子群算法
粒子群算法，也称粒子群优化算法，是近年来发展起来的一种新的进化算法，粒子群算法属于进化算法的一种，和模拟退火算法相似，它也是从随机解出发，通过迭代寻找最优解，它也是通过适应度来评价解的品质；
但它比遗传算法规则更为简单，它没有遗传算法的交叉和变异操作，它通过追随当前搜索到的最优值来寻找全局最优，这种算法以其实现容易、精度高、收敛快等优点引起了学术界的重视，并且在解决实际问题中展示了其优越性，粒子群算法是一种并行算法。
