模拟退火机制的遗传算法

近年来遗传算法在寻优领域得到了广泛的应用， 但是容易出现早熟、局部寻优能力差等问题， 在实际应用中可考虑与其他优化算法结合应用。遗传算法的局部搜索能力较差， 但全局搜索的能力较强； 模拟退火算法具有较强的局部搜索能力， 并能使搜索过程避免陷入局部极值点， 但模拟退火算法不适合整个搜索空间。 结合遗传算法和模拟退火算法的优点， 本节应用模拟退火机制的遗传算法解决可重构模块机器人逆解的最优化问题。算法的最优化过程分为两部分， 首先通过遗传算法的进化操作产生较优良的群体， 再利用模拟退火算法的退火操作来进行个体的进一步优化调整。

1. 编码方法

目前多采用二进制编码来搜索连续的解空间， 但对于一些多维、 高精度要求的连续空间搜索问题， 使用二进制编码来表示个体时将产生一些不利之处。 为了克服这个问题， 本节采用浮点数编码关节变量， 一个n自由度的可重构模块机器人的关节变量可以用一个由n个浮点数组成的染色体表示。

2. 适应度函数

遗传算法在进化搜索中以适应度函数为依据， 利用种群中每个个体的适应度值进行搜索， 因此适应度函数的选取至关重要， 其直接影响算法的收敛速度及最优解的寻找。 为了使劣解不至于过早被淘汰， 应用基于排序的适应度分配原则。 个体按照其响应的目标函数值排序， 目标函数值最大的个体排序为1， 目标函数值最小的个体排序为种群中个体的数量p， 排序为i的个体适应度值按照下面的公式计算:

3. 遗传操作和退火操作

选择操作采用轮盘赌选择， 所有选择是从当前种群中根据个体的适应度值， 挑选出好的个体进入下一代种群。 每个个体进入下一代的概率等于它的适应度值与整个种群中个体适应度值的和的比例， 适应度值越高， 被选中的概率就越大， 进入下一代的概率就越大。

交叉操作采用单点交叉， 单点交叉在个体编码串中只随机设置一个交叉点， 然后在该点相互交换两个配对个体的部分染色体。

变异操作体现了生物遗传的多样性。 变异操作使每个基因位上的浮点数以一定的概率发生变异， 发生变异的基因位被一个随机数所代替。

退火操作用适应度值作为模拟退火算法中的能量， 算法首先在个体附近产生一个随机扰动:

其中qi是种群中的第i个个体；是经扰动后产生的新个体；ri＝(ri1， ri2，…，rin)是个体i的扰动，其中rij(1≤j≤n)∈[-Range，Range]，Range代表扰动范围。

对于经过扰动后产生的新个体， 如果它的适应度值增加， 则接受该个体，否则以一定的概率pi接受该个体

其中fi为第i个个体的适应度，T为退火温度，T0为初始温度。