人工智能之遗传算法论文含源代码
30维线性方程求解
摘 要：非线性方程组的求解是数值计算领域中最困难的问题，大多数的数值求解算法例如牛顿法的收敛性和性能特征在很大程度上依赖于初始点。但是对于很多高维的非线性方程组， 选择好的初始点是一件非常困难的事情。本文采用了遗传算法的思想，提出了一种用于求解非线性方程组的混合遗传算法。该混合算法充分发挥了遗传算法的群体搜索和全局收敛性。选择了几个典型非线性方程组，考察它们的最适宜解。
关键词：非线性方程组；混合遗传算法；优化
1. 引言
遗传算法是一种通用搜索算法，它基于自然选择机制和自然遗传规律来模拟自然界的进化过程，从而演化出解决问题的最优方法。它将适者生存、结构化但同时又是随机的信息交换以及算法设计人的创造才能结合起来，形成一种独特的搜索算法，把一些解决方案用一定的方式来表示，放在一起成为群体。每一个方案的优劣程度即为适应性，根据自然界进化“优胜劣汰”的原则，逐步产生它们的后代，使后代具有更强的适应性，这样不断演化下去，就能得到更优解决方案。 随着现代自然科学和技术的发展，以及新学科、新领域的出现，非线性科学在工农业、经济政治、科学研究方面逐渐占有极其重要的位置。在理论研究和应用实践中，几乎绝大多数的问题都最终能化为方程或方程组，或者说，都离不开方程和方程组的求解。因此，在非线性问题中尤以非线性方程和非线性方程组的求解最为基本和重要。传统的解决方法，如简单迭代法、牛顿法、割线法、延拓法、搜索法、梯度法、共轭方向法、变尺度法，无论从算法的选择还是算法本身的构造都与所要解决的问题的特性有很大的关系。很多情况下, 算法中算子的构造及其有效性成为我们解决问题的巨大障碍。而遗传算法无需过多地考虑问题的具体形式，因为它是一种灵活的自适应算法，尤其在一些非线性方程组没有精确解的时候，遗传算法显得更为有效。而且，遗传算法是一种高度并行的算法，且算法结构简单，非常便于在计算机上实现。本文所研究的正是将遗传算法应用于求解非线性方程组的问题。
2. 遗传算法解非线性方程组
为了直观地观察用遗传算法求解非线性方程组的效果，我们这里用代数非线性方程组作为求解的对象
问题描述：
非线性方程组指的是有n 个变量（为了简化讨论，这里只讨论实变量方程组）的方程组
fi x 1, x 2, …, x n =0 i=1,2, …, m
中含有非线性方程。其求解是指在其定义域内找出一组数x ∗ x 1, x 2, …, x n 能满足方程组中的每一个方程。这里，我们将方程组转化为一个函数
m
F x 1, x 2, …, x n = fi
i=0
则求解方程组就转化为求一组值x ∗ x 1, x 2, …, x n 使得F x ∗ =0成立。即求使函数F x 1, x 2, …, x n 取得最小值0的一组数，于是方程组求解问题就转变为函数优化问题
3. 遗传算子
遗传算子设计包括交叉算子、变异算子和选择算子的设计。
（1）交叉算子
算术交叉算子是实数编码遗传算法中应用最广泛的一种算子, 该算子描述如下:
假设在两个体X 1 和X 2 之间进行算术交叉, 则交叉运算后所产生出的两个新个体为
∗X 1=aX 1+(1−a)X 2 ∗ X 2= 1−a X 1+aX 2
其中a 是在[0，1]区间内的参数，它可以是一个常数，也可以是由进化所决定的变量，本文选择为[ 0，1] 区间上的随机数。
（2）变异算子
设被选中变异的个体的染色体为X k , 随机产生一个扰动方向pk , 整个变异操作的过程是以X k 为起点, 沿方向pk 寻求最优点作为新的染色体, 即完成如下一维搜索运算:
min∅ τ =F X k +τpk
本文以黄金分割方法搜索得到最优步长τ° , 则变异后个体的新染色体X k ′
′X k =X k +τ°pk
（3）选择算子
传统的标准选择算子一方面要求适应度函数大于零, 给适应度函数的选择带了一定的困难; 另一方面基于适应值的排序选择算子是造成算法早熟、收敛速度慢的主要原因。为避免上述问题, 本文采用了既具有较高确定性和一定随机性的联赛竞争法为选择算子, 联赛规模取为3。由于遗传算法中有许多随机因素的影响, 当前群体的最好个体可能会被破坏, 影响算法的运行效率和收敛性, 因此采用了最优保存策略, 即当前群体中最优个体不参与交叉运算和变异运算, 而是用它来替代本代群体中经过交叉、变异操作后所产生的最差个体。
4. 实例验证
我们为了验证这个遗传算法是否能够找到我们需要的合适解，选取下面
的非线性方程组来验证：
x 1+x 2+x 3−0.5=0
x 1x 2+x 2x 3+x 3x 1+7.5=0
222x 1+x 2+x 3−15.25=0
运行得到的结果为：得出来的结果为逼近准确解
ans = 0 -2 1
由此可知能找到合适的解的。
参考文献：
[1]陈明. 基于进化遗传算法的优化计算[J]. 软件学报, Vol.9 No.11, 1998.11:876-879.
[2]陈火旺. 遗传程序设计（之一）[J]. 计算机科学, 1995.22(6):12-15.
[3]冯果忱. 非线形方程组迭代解法[M]. 上海科学技术出版社, 1989.
附件：实验源代码
function [popold,valParents,F,CR]=jde(F,CR,popold,problem,valParents)
%-------- Parameters Declination------------
% F and CR: are self-adaptive parameters coming from jde
% popold and valparameters: the evolutionary group and its fitness
% problem and lu: to be solved problem and its bound.
% omiga: the shifting vector for problem
% flag: the sign to be shifted.
% FES: the number of evaluation.
global lu %全局变量
tau1=0.1;tau2=0.1;
[ps,n]=size(popold);
pop=popold;
Fold = F; CRold = CR;
IF = rand(ps, 1)
F(IF) = 0.1 + 0.9 * rand(sum(IF), 1); CR(ICR) = 0.0 + 1.0 * rand(sum(ICR), 1);
% == == == == == = Mutation == == == == == == == == =
index= gnvect(randperm(ps),3); % generate three mutual vectors.
vi = pop(index(1,:), :) + F(:, ones(1, n)) .* (pop(index(2,:), :) -pop(index(3,:), :)); %变异算法
vi = boundConstraint(vi, lu);
% == == == == = Crossover == == == == =
mask = rand(ps, n) > CR(:, ones(1, n)); % mask is used to indicate which elements of ui comes from the parent
rows = (1:ps)'; cols = floor(rand(ps, 1) * n) + 1; % choose one position where the element of ui doesn't come from the parent
jrand = sub2ind([ps n], rows, cols); mask(jrand) = false;
ui = vi;
ui(mask) = pop(mask);
valOffspring =benchmark_func(ui,problem); % evaluate
% == == == == == = Selection == == == == == =
% I == 1: the parent is better; I == 2: the offspring is better
[valParents, I] = min([valParents, valOffspring], [], 2); % fitness values are replaced popold = pop;
popold(I == 2, :) = ui(I == 2, :); % some individuals are replaced F(I == 1) = Fold(I == 1); % refreshing F and CR.
CR(I == 1) = CRold(I == 1);
return;