遗传算法
根据问题的目标函数构造一个适值函数，对一个由多个解（每个解对应一个染色体）构成的种群进行评估、遗传、选择，经多代繁殖，获得适应值最好的个体作为问题的最优解。
1，产生一个初始种群
2，根据问题的目标函数构造适值函数
3，根据适应值的好坏不断选择和繁殖
4，若干代后得到适应值最好的个体即为最优解
1.种群和种群大小
一般越大越好，但是规模越大运算时间越大，一般设为100~1000
2. 编码方法 （基因表达方法
3. 遗传算子
包括交叉和变异，模拟了每一代中创造后代的繁殖过程。是遗传算法的精髓
交叉：性能在很大程度上取决于交叉运算的性能，交叉率Pc：各代中交叉产生的后与代数与种群中的个体数的比。Pc越高，解空间就越大，越耗时/
变异:Pm:种群中变异基因数在总基因数中的百分比。它控制着新基因导入种群的比例。太低，一些有用的基因就难以进入选择；太高，后代就可能失去从双亲继承下来的良好特性，也就失去了从过去中搜索的能力。
4.选择策略
适者生存，优胜劣汰
5.停止准则
最大迭代数
初始种群的产生：随机产生，具体依赖于编码方法
编码方法 ：二进制编码法、浮点编码法、符号编码法。顺序编码，实数编码，整数编码。
适值函数 ：根据目标函数设计
遗传运算 ： 交叉 ：单切点交叉，双切点交叉，均匀交叉，算术交叉
变异 ：基本位变异（Simple Mutation）：对个体编码串中以变异概率、随机指定的某一位或某几位仅因座上的值做变异运算。
均匀变异（Uniform Mutation）：分别用符合某一范围内均匀分布的随机数，以某一较小的概率来替换个体编码串中各个基因座上的原有基因值。（特别适用于在算法的初级运行阶段）
边界变异（Boundary Mutation）：随机的取基因座上的两个对应边界基因值之一去替代原有基因值。特别适用于最优点位于或接近于可行解的边界时的一类问题。
非均匀变异：对原有的基因值做一随机扰动，以扰动后的结果作为变异后的新基因值。对每个基因座都以相同的概率进行变异运算之后，相当于整个解向量在解空间中作了一次轻微的变动。
高斯近似变异：进行变异操作时用符号均值为P的平均值，方差为P**2的正态分布的一个随机数来替换原有的基因值。
选择策略 ：1.轮盘赌选择（Roulette Wheel Selection）：是一种回放式随机采样方法。每个个体进入下一代的概率等于它的适应度值与整个种群中个体适应度值和的比例。选择误差较大。
2.随机竞争选择（Stochastic Tournament）：每次按轮盘赌选择一对个体，然后让这两个个体进行竞争，适应度高的被选中，如此反复，直到选满为止。
3.最佳保留选择：首先按轮盘赌选择方法执行遗传算法的选择操作，然后将当前群体中适应度最高的个体结构完整地复制到下一代群体中。
4.无回放随机选择（也叫期望值选择Excepted Value Selection）：根据每个个体在下一代群体中的生存期望来进行随机选择运算。方法如下:
（1） 计算群体中每个个体在下一代群体中的生存期望数目N。
（2） 若某一个体被选中参与交叉运算，则它在下一代中的生存期望数目减去0.5，若某一个体未 被选中参与交叉运算，则它在下一代中的生存期望数目减去1.0。
（3） 随着选择过程的进行，若某一个体的生存期望数目小于0时，则该个体就不再有机会被选中。
5.确定式选择：按照一种确定的方式来进行选择操作。具体操作过程如下：
（1） 计算群体中各个个体在下一代群体中的期望生存数目N。
（2） 用N的整数部分确定各个对应个体在下一代群体中的生存数目。
（3） 用N的小数部分对个体进行降序排列，顺序取前M个个体加入到下一代群体中。至此可完全确定出下一代群体中M个个体。
6.无回放余数随机选择：可确保适应度比平均适应度大的一些个体能够被遗传到下一代群体中，因而选择误差比较小。
7.均匀排序：对群体中的所有个体按期适应度大小进行排序，基于这个排序来分配各个个体被选中的概率。
8.最佳保存策略：当前群体中适应度最高的个体不参与交叉运算和变异运算，而是用它来代替掉本代群体中经过交叉、变异等操作后所产生的适应度最低的个体。
9.随机联赛选择：每次选取几个个体中适应度最高的一个个体遗传到下一代群体中。
10.排挤选择：新生成的子代将代替或排挤相似的旧父代个体，提高群体的多样性。
之前在网上看到的一个比方，觉得很有趣：
{
既然我们把函数曲线理解成一个一个山峰和山谷组成的山脉。那么我们可以设想所得到的每一个解就是一只袋鼠，我们希望它们不断的向着更高处跳去，直到跳到最高的山峰。所以求最大值的过程就转化成一个“袋鼠跳”的过程。
下面介绍介绍“袋鼠跳”的几种方式。
爬山算法：一只袋鼠朝着比现在高的地方跳去。它找到了不远处的最高的山峰。但是这座山不一定是最高峰。这就是爬山算法，它不能保证局部最优值就是全局最优值。
模拟退火：袋鼠喝醉了。它随机地跳了很长时间。这期间，它可能走向高处，也可能踏入平地。但是，它渐渐清醒了并朝最高峰跳去。这就是模拟退火算法。
遗传算法：有很多袋鼠，它们降落到喜玛拉雅山脉的任意地方。这些袋鼠并不知道它们的任务是寻找珠穆朗玛峰。但每过几年，就在一些海拔高度较低的地方射杀一些袋鼠。于是，不断有袋鼠死于海拔较低的地方，而越是在海拔高的袋鼠越是能活得更久，也越有机会生儿育女。就这样经过许多年，这些袋鼠们竟然都不自觉地聚拢到了一个个的山峰上，可是在所有的袋鼠中，只有聚拢到珠穆朗玛峰的袋鼠被带回了美丽的澳洲。
}
（把那些总是爱走下坡路的袋鼠射杀，这就是遗传算法的精粹！）
遗传算法并不保证你能获得问题的最优解，但是使用遗传算法的最大优点在于你不必去了解和操心如何去“找”最优解。（你不必去指导袋鼠向那边跳，跳多远。）而只要简单的“否定”一些表现不好的个体就行了。（把那些总是爱走下坡路的袋鼠射杀，这就是遗传算法的精粹！）
改进与变形
编码方法：
遗传算法简单易懂的例子
遗传算法的例子如下：求解函数 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的影响。对于有些改进算法，在速度更新公式最后一项会加入一个随机项，来平衡收敛速度与避免早熟。并且根据位置更新公式的特点，粒子群算法更适合求解连续优化问题。参考资料来源：百度百科-粒子群算法
什么是粒子群算法
粒子群算法，也称粒子群优化算法，是近年来发展起来的一种新的进化算法，粒子群算法属于进化算法的一种，和模拟退火算法相似，它也是从随机解出发，通过迭代寻找最优解，它也是通过适应度来评价解的品质；
但它比遗传算法规则更为简单，它没有遗传算法的交叉和变异操作，它通过追随当前搜索到的最优值来寻找全局最优，这种算法以其实现容易、精度高、收敛快等优点引起了学术界的重视，并且在解决实际问题中展示了其优越性，粒子群算法是一种并行算法。
遗传算法路径规划中什么值影响最优解
在遗传算法路径规划中，影响最优解的值取决于具体问题的不同。一般来说，遗传算法路径规划的优化目标可以是时间、距离、成本、安全性等多个方面，因此影响最优解的值也会随着优化目标的不同而变化。举个例子，如果优化目标是时间最短，那么影响最优解的值可能是路径上每个节点之间的距离、车辆的最大速度、交通状况等因素。如果优化目标是成本最低，那么影响最优解的值可能是每个路径的经济成本、燃油消耗、人工成本等因素。总之，影响遗传算法路径规划中最优解的值取决于具体的优化目标，需要根据问题的特点来选择适当的目标函数，并结合实际情况选择影响最优解的相关因素。【摘要】
遗传算法路径规划中什么值影响最优解【提问】
遗传算法路径规划中什么值影响最优解【提问】
在遗传算法路径规划中，影响最优解的值取决于具体问题的不同。一般来说，遗传算法路径规划的优化目标可以是时间、距离、成本、安全性等多个方面，因此影响最优解的值也会随着优化目标的不同而变化。举个例子，如果优化目标是时间最短，那么影响最优解的值可能是路径上每个节点之间的距离、车辆的最大速度、交通状况等因素。如果优化目标是成本最低，那么影响最优解的值可能是每个路径的经济成本、燃油消耗、人工成本等因素。总之，影响遗传算法路径规划中最优解的值取决于具体的优化目标，需要根据问题的特点来选择适当的目标函数，并结合实际情况选择影响最优解的相关因素。【回答】
如果是路线最优呢。距离最近【提问】
如果优化目标是路线最优，那么影响遗传算法路径规划中最优解的值可能包括以下因素：距离：路径的总长度和各个节点之间的距离都是影响路线最优的重要因素。道路交通情况：路况、拥堵情况、道路限速等因素都会影响路径的行驶时间和路线规划。路线安全：考虑到道路的安全性，可能需要避开一些危险区域或路段，或是选择更安全的路径。时间窗口：在一些特定的情况下，需要考虑路径的行驶时间是否符合时间窗口的限制。费用：在一些特定的场景下，可能需要考虑路径的行驶费用是否符合预算。总之，在路线最优的情况下，距离是最重要的因素之一，同时也需要考虑其他因素，例如交通情况、安全性、时间窗口和费用等，以找到最优解。【回答】
如果是车辆路线最优呢老师【提问】
如果优化目标是车辆路线最优，那么影响遗传算法路径规划中最优解的因素可能包括以下几个：车辆载重和容积：不同的车辆载重和容积限制可能会影响到路径规划，需要根据车辆特性进行相应的调整。道路限制：一些道路可能有宽度、高度、重量等限制，需要避开或选择合适的道路，以保证车辆安全通行。路况和拥堵情况：路况和拥堵情况对于车辆行驶时间和路径规划具有很大的影响，需要考虑实时交通信息。费用和效率：在路径规划中需要考虑车辆行驶的费用和效率，避免在路径规划中出现不必要的浪费。服务质量：在一些特定的场景中，例如快递和物流领域，需要考虑到服务质量的因素，例如准确性和及时性等。综上所述，影响遗传算法路径规划中最优解的因素包括车辆载重和容积、道路限制、路况和拥堵情况、费用和效率、服务质量等。需要根据具体的应用场景来确定具体的优化目标和规划路径。【回答】
遗传算法
最近开发了一个模型辨识的软件，发现在计算速度方面需要进行优化，于是查找优化相关的算法，这两天在网上搜了搜关于遗传算法相关的资料，记录一下自己对遗传算法的理解。
遗传算法通过模拟自然界生物种群进化的过程，通过选择、交叉、变异等机制，在某个范围的解空间内寻找一个最优解。遗传算法中通过适应度函数（可以看做目标函数的变形）来评价一个个体（解）与最优解的近似程度，设计适应度函数一定意义上与问题本身的目标函数线性相关。
遗传算法的组成：
1.编码。把解空间内的元素用一定的编码方式表示（常见为二进制数）。
2.初始化群体。选定种群大小（每次迭代过程中需要计算、评价的解的个数），随机填充
3.适应度。根据适应度函数对种群进行排序。
4.遗传算子。即通过选择、交叉、变异产生下一代种群。
5.根据终止判定法则判断是否已找到最优解或者继续循环。
这里有几个问题：
遗传算法的优点在于无需对解空间内的每一个解进行计算和比较，一定程度上优化了计算速度，但是收敛速度具有随机性。这里我对遗传算法还有一些疑问：假如解空间的规模不是很大，例如几百，那么如果选取的种群太大，可能进行一两次迭代就几乎遍历了解空间内的所有元素，与顺序遍历没什么差别；如果选取的种群太小，进行交叉、变异操作时，由于基数小，会不会导致算法停滞？（子代与父代完全相同）
选择（以轮盘赌选择方法为例）是不是相当于对父代进行种群大小次数的选择，产生子代，那么子代中适应度较高的解会重复出现，适应度越高偿付概率越大。重复项需要剔除，然后从解空间内随机填充吗？还是说保留重复项？（同理交叉、变异种出现的重复项如何处理？）
另外，该如何终止判定法则该如何确定？