遗传算法
最近开发了一个模型辨识的软件，发现在计算速度方面需要进行优化，于是查找优化相关的算法，这两天在网上搜了搜关于遗传算法相关的资料，记录一下自己对遗传算法的理解。
遗传算法通过模拟自然界生物种群进化的过程，通过选择、交叉、变异等机制，在某个范围的解空间内寻找一个最优解。遗传算法中通过适应度函数（可以看做目标函数的变形）来评价一个个体（解）与最优解的近似程度，设计适应度函数一定意义上与问题本身的目标函数线性相关。
遗传算法的组成：
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］区间中的十进制实数解。
