优化一般非线性优化问题的遗传算法

一般非线性优化问题的数学模型如下：

式中：xi为未知变量；ai、bi为实常量；f为非线性目标函数。

利用GA来求解上述问题的步骤如下。

1）编码

就是将未知量xi编成位长为l的二进制代码字符串。若变量xi的变化范围是［ai，bi］，则用前述公式（9.3.34）来确定十进制数xi与其对应的二进制整数（xi）b之间的关系为

例如，二进制整数（xi）b=21，若位数l取5位，其对应的二进制代码为

10101

又若ai=30，bi=54，则对应有

对于（x1，x2，…，xr），其对应的字符串由每个xi对应的字符串串联而成，所以总长度为lr。

2）确定初始群体

群体的个体数（群体的规模）n应取得适中，n选得过小，不易求得全局最优解，且容易过早收敛，n选得过大，运算量过大，收敛速度减慢，通常取n为编码长度的两倍，即2lr较好。

确定了n的大小后，便要具体决定n个染色体串，也就是n个长度为lr的代码串。此时可以用前述的掷硬币随机法产生，也可以在区间［ai，bi］内随机选择xi，然后利用式（9.4.2）决定对应的二进制整数（xi）b，再由（xi）b决定二进制字符串。

3）决定适应度函数fi

对于非线性优化问题，通常定义目标函数f（x1，x2，…，xr）为该字符串的适应度函数。当f（·）有负值而无法作适应度函数时，则对f（·）做如下修正：(www.xing528.com)

设第t代规模为n的群体对应的目标值为fi（i=1，2，…，n），则修正值f＇i为

其中

4）进行复制操作

为防止已经搜寻到的最优结果丢失，我们把上一代群体中适应度最大的10%的个体不进行复制、交换、变异三种操作，而直接进入下一代群体中，对另外90%的个体进行上述三种操作。每个个体复制的比例由适应度决定：

5）进行交换操作

交换只对由复制产生的0.9n个个体进行。此时应适当地选取交换的概率pc，p c越大，产生新个体的机会越大，搜索效率越高，但pc过大，则已搜索到的较好的个体可能会丢失。一般pc以0.85为好。由于保留了10%的个体直接进入下一代，此时取pc=0.95较好。

6）进行变异操作

变异操作的作用是防止丢失有用的可能解，保证可搜索到空间的重要点，使算法具有全局收敛性。变异的概率较小，在实际运算中，通常取0.01～0.05。

7）令t=t+1，继续计算适应度fi

8）判断终止条件是否满足

通常选取的终止条件是如式（9.2.3）所示的最佳适应度无明显提高，用相对差值ε来判断。若相对差值小于ε，则停止，否则返回步骤4）。停止条件也有用迭代次数（即代数）N来决定的，当n为2lr时，选取N=30。

9）结束过程

找出最佳串Sm，并将Sm对应的字符串利用式（9.4.2）换算出最佳未知量（x1，x2，…，xr）m及其对应的最佳适应度函数值f（x1，x2，…，xr）m，过程结束。