2012河南科技大学第九届大学生数学建模竞赛

2012河南科技大学第九届大学生数学建模竞赛

承诺书

我们仔细阅读了中国大学生数学建模竞赛的竞赛规则.

我们完全明白，在竞赛开始后参赛队员不能以任何方式（包括电话、电子邮件、网上咨询等）与队外的任何人（包括指导教师）研究、讨论与赛题有关的问题。

我们知道，抄袭别人的成果是违反竞赛规则的, 如果引用别人的成果或其他公开的资料（包括网上查到的资料），必须按照规定的参考文献的表述方式在正文引用处和参考文献中明确列出。

我们郑重承诺，严格遵守竞赛规则，以保证竞赛的公正、公平性。如有违反竞赛规则的行为，我们将受到严肃处理。

我们参赛选择的题号是（从题目编号中选择一项填写）：数学建模夏令营题目 D

题目：打孔机生产效能的提高

参赛队员：

姓名专业班级所在学

院

电话（手机）

是否报名全国竞

赛

队长马鹏自动化103班电子信

息工程

学院

152********

是

队员1 王耀辉自动化103班电子信

息工程

学院

152********

是

队员2 王美红自动化104班电子信

息工程

学院

152********

是

D打孔机生产效能的提高

摘要

问题一,由于所打的孔型已定，所以用于打孔的时间和费用为常数，分析时可以用一个常数表示或不考虑。钻头行进的费用要远大于刀片转换的费用,为了模型的简化和可行性,本模型将以寻找钻头行进的最短路径为重心.以减少钻头的行进费用,从而降低成本,单个需要转换刀片的孔数目较少且在板子上的分布比较分散(板子半径在8米左右),因此本模型采用将遗传算法求解TSP（Traveling Salesman Problem）问题的方法应用于印制板打孔工艺的最优路径选择中，根据印制板上孔的位置找出打孔的最佳路径，实现高效经济打孔.通过对50孔和1000个孔问题的仿真求解，其结果证明该方法是合理有效的。钻头每到一个孔就一次性把这个孔完成.

问题二,双钻头同时工作时,让两钻头分别从一中最优路径的起点和终点,沿该路径作业,设一中所需要的时间为T,则在该路径中的T/2附近(两者距离接近3cm)时，一个钻头沿路径继续作业且不转换刀具，另一个钻头则行进（行进过程中转换成未打孔中所需的第二种刀具）到该钻头后面，沿路径作业（行进过程不转换刀具）第一个钻头将未打孔的路径走完后，返回到未完成的孔处（行进过程中转换成所需的第三种刀具），沿路径作业（不转换刀具），依此类推，直至将所有孔打完为止。仿真出路径，计算该路径距离及所需费用即可。

关键字

最短路径印制板打印遗传算法

一、问题重述

印刷线路板的一个重要组成部分就是过孔，且过孔在加工费用中所占的比重也很大，因此减少打孔的费用就成为了降低成本的一项重要措施，而影响打孔德费用的因素有：钻头行进的时间（钻头行进的距离），刀片转换所需的时间。钻头行进和刀片转换可以同时进行，但是所需费用不减，因此建模的关键在于减少行进时间和转换刀片的次数。而减少行进时间方面，关键在于设计连接各个孔的最优路径，即钻头尽量不重复走同一条路；减少转换次数，使同一刀片的利用率达到最大。双钻头作业时虽然可以生产效能得到进一步的提高，但是过程将变得更加复杂，需要协调双钻头同时工作。

根据以上的分析，我们需要完成以下的工作：

（1）附件1提供了某块印刷线路板过孔中心坐标的数据，单位是密尔（mil）（也称为毫英寸，1 inch=1000 mil），请给出单钻头作业的最优作业线路（包括刀具转换方案）、行进时间和作业成本。

（2）为提高打孔机效能，现在设计一种双钻头的打孔机（每个钻头的形状与单钻头相同），两钻头可以同时作业，且作业是独立的，即可以两个钻头同时进行打孔，也可以一个钻头打孔，另一个钻头行进或转换刀具。为避免钻头间的触碰和干扰，在过孔加工的任何时刻必须保持两钻头间距不小于3cm（称为两钻头合作间距）。为使问题简化，可以将钻头看作质点。

（i）针对附件1的数据，给出双钻头作业时的最优作业线路、行进时间和作业成本，并与传统单钻头打孔机进行比较，其生产效能提高多少？

（ii）研究打孔机的两钻头合作间距对作业路线和生产效能产生的影响。

二、模型假设

对第一个问题假设：

单个过孔的钻孔作业时间一定设为T，钻头的行进紧贴板面

钻头在工作过程中，总是正常工作不会出现差错，没有机械损坏

由于刀片转换时间和成本都相对比较小，所以假设所有的孔都只需要一种刀片即可完成，即只考虑钻头行进时间和成本

三、符号约定

ta--行进时间 tb--转换刀片时间 tc--总计所用时间 ma--行进成本 mb--转换刀片成本 mc--总计成本

四、问题分析与模型的建立

1、引言

印制线路板PCB 是电子设备最重要的部件之一，而印制板的打孔是印制制作工程中的一个重要环节。其中打孔路径的优化对于提高工作效率至关重要。对孔加工的点位进行优化，可以缩短走刀路径，减少空行程的时间，从而提高加工效率。同时考虑对于需要多种刀片打孔的孔的打孔顺序，以及刀片更换所需要的时间，考虑这些时间带来的时间成本，传统的钻孔作业没有考虑打孔路径的优化，工作效率低下。如果用穷举法逐个计算并从中找到最优解，当印制板上孔的个数N 很大时，就会导致计算量急剧增大，产生“组合爆炸”问题，使得该方法在实际中难以应用。利用遗传算法能很好地解决这个问题，它是一种全局优化自适应概率搜索算法，能够进行快速的全局优化搜索，极大地减少运算量。该算法鲁棒性强、效率高，能够很快的解决印制板打孔的路径优化问题。

其基本思想是：从一个初始种群出发，不断重复执行选择、交叉和变异的过程，优胜劣汰，使种群向一个预定的目标进化。[1]

2、问题分析

a) 数学模型

打孔路径优化问题的数学描述如下：

设有N 个孔的集合H=[h1,h2,h3,…，hn],h1,h2,h3,…，hn 分别为这些孔的编号。 对于孔hi,hj ∈H ，从hi 到hj 的距离可记为：dij ∈R+且dij=dji.R+为正实数域。 要在集合H 中找到一个不重复的全排列hi(1),hi(2),hi(3),…，hi(n ，令：

)

(1

1)1(),(N i d D n j j i j i i ∈=∑-=+

求i D 的最小值。

b)染色体编码方法

对每条路线经过的N 个孔进行编号，并排成一个无重复的数字串。设一块PCB 板上共有N 个孔，编号分别为1,2,3，…,n ，那么任何一个包含有从一到N 的所有整数的排列便组成了一条染色体，每条染色体上的N 个数字是该染色体的N 个基因。染色体及其基因有均匀分布函数随机生成，如：

X={1 5 6 8 9 4 2 7 3}

表示一个个体，其染色体长度N=9，对应的路线为1→5→6→8→9→4→2→7→3

c)适应度函数的选择

在算法实现中，以个体的适应度来确定该个体被遗传到下一代的概率，它是衡量染色体优劣的的准则。适应度值越大的个体被遗传到下一代的概率越大。定义第i 条个体的适应度：

)

,,2,1(1

1

1

)

1(),(n i d

f n j j i j i i ?==

∑-=+

d)遗传算子的选择及相关参数 选择算子

选择算子采用比例选择算子。具体方法为：计算每个个体的适应度值i f 和总体的使

用度值

∑m

m

i f

1

,为每代种群中个体的数目；计算每一个个体适应的百分比，按百分比的值

来决定该个体被保留到下一代的概率的大小。值越大，被保留到下一代的概率越大

交叉算子

交叉运算是遗传算法获取新个体最总要的手段。这里使用单点交叉： 有如下两个父个体：

父个体1 5 2 6│1 9 4 7 3 10 8 父个体2 G K C │ D B I F E A H

设交叉点的位置为3，如下所示，则交叉后生成的两个子个体是： 子个体1 1 G K C │ 1 9 7 3 10 8 子个体2 2 5 2 6 │D B I F E A H 倒位算子

到位操作的实质就是颠倒个体编码串中随机指定的两个基因座之间的基因排列顺序，从而形成一个新的染色体。到位操作的具体过程是：

在个体编码中随机指定两个基因座之后的位置为到位点 以到位概率Pr ，颠倒这两个点之间的基因顺序 对个体A 进行到位A' A:5 2 │6 1 9 4 7 3│10 8 A':5 2│3 7 4 9 1 6│10 8 到位点1 到位点2

到位操作实质上也是一种变异操作，他改变了个体编码串部分基因的排列顺序，使对于形成一种较好模式有积极意义且在编码传中，隔离的较远的基因能够逐渐接近，从而形成较好的个体

变异算子

变异运算是对个体的某一种或某一些基因座上的值按一较小的概率进行改变，他是产生新个体的一种方法。变异本身是一种局部随机搜索，它与选择算子结合在一起，保证了遗传算法的有效性，使遗传算法具有局部搜索的能力，同时使遗传算法保持总群的多样性，以防止出现非成熟收敛。在运算中，变异概率Pm 不能太大，比如若大于0.5遗传算法将退化为随机搜索，遗传算法的一些重要数学特征和搜索能力将不复存在

路径优化遗传算法的视线

产生初始群

社初始群Po 中有m 个个体，每个个体都采用随机排序方法将n 个孔的编号随机排列产生，共产生m 个全排列，构成初始种群

b)适应度评估

初始种群产生以后，种群内的每个个体都代表一条染色体，对应一条打孔路线。计算出种群中每一个个体对应的路线长度及其适应度

如：第i 条路线的距离如是（1），其适应度为：

)

,,2,1(1

1

1

)

1(),(m i d

f n j j i j i i ?==

∑-=+

C)选择操作

在选择过程中，应用轮盘赌选择法，根据个体的适应度f i 来确定他的存活概率。定义选择概率：

)

,,2,1(1

m i m i i

i

h i

f

f

f

p i

?==

=

∑=

D)交叉选择

丛种群Ps 中任意选择两个父串，以一定的概率Pc （0.8

如果是杂交，则随机的在两个父串上选择一个杂交点，然后交换这两个串对应的子串。如假设两个父串是P1={w1w2…wn}，P2={z1z2…zn},随机产生一个1和n-1之间的数字K 作为交叉点，将此二染色体中前K 个位置作交换.

但这两个可能不是合法的染色体，因为可能又是重复的数码，不符合前述约束条件，要进行如下的合法化处理

E)变异操作

在种群Pm 中以一定的概率Pm （0.001

变异操作采取如下方法进行 ：设原染色体为含有n 个基因的串：w1w2…wk,随机产生一个1至n 的数k ，决定对染色体上的第K 个基因坐的值wk 做变异操作，又随机从w1到wn 中选取一个数wi ，代替wk ，并将wk 加到尾部得到：

w1w2w3w4…w …wn wk

这是该串中有n+1个数字，但必须删除重复的wi 就得到一条合法的染色体 F)倒位操作

到位操作实质上也是一种变异操作。

以一定的概率Pr （0.1

G)优化过程的计算步骤

综上所述，印制电路板打孔路径优化遗传算法的计算步骤总结如下：

初始化：在求解空间中随机选取m 个个体作为初始种群，即种群规模为m 。

评价：计算种群中每一个个体的适应度值f

i，以衡量个体的优良程度，为个体的

选择提供依据。

选择：根据轮盘赌规则选择个体，适应度值大的个体越易成活，进而产生新的种群交叉：选择交叉概率Pc，进行单点交叉操作，以产生下一代的新个体。

倒位：选择倒位概率Pr，进行到位操作。

变异：选择变异概率Pm，对种群中的个体进行变异操作。

输出：输出迭代次数、优化值、平均值，以观察算法的效果和收敛特性

精英选择：选择适应度最大的个体和适应度最小的个体，保存最好个体。如果本代最好的个体优于上一代保存的个体，则从本代中复制这一最好的个体保存，否则用上一代中最好的个体替代本代中最差的个体。

结束判断：终止条件设定为达到以确定的最大迭代次数，或者在连续演化若干代以后算法没有表现明显的收敛性。若达到终止条件则终止演化过程，否则返回步骤（2），重复以上过程。

数字仿真试验及结果分析

仿真实验结果显示，在最后一代种群内各个个体趋于相同，经过多次试验，最优解一般都稳定在同一个体。如果将每一代的平均路径长度数据全部输出，可以看出他们在整体上都随进化代数的增加而不断减小，即路径的长度越来越小，个体越来越优。

当印刷电路板上孔很多时，必须扩大种群规模以防止算法过早收敛。试验证明，使用该算法能够达到利用优化打孔路径的目的，且效果明显。

五、模型求解

现在我们这仅是一个求解的思路步骤而已，以及解决此问题需要运用的算法，为对于具体的如何实现此算法并求出具体结果，还有待我们知识的积累，继续学习探索。

下面是我们具体的解题思路及必要的算法：

由于钻头行进的费用要远大于刀片转换的费用,为了模型的简化和可行性,本模型将以寻找钻头行进的最短路径为重心.以减少钻头的行进费用,从而降低成本,单个需要转换刀片的孔数目较少且在板子上的分布比较分散(板子半径在8米左右),因此本模型采用将遗传算法求解TSP（Traveling Salesman Problem）问题的方法应用于印制板打孔工艺的最优路径选择中，根据印制板上孔的位置找出打孔的最佳路径，实现高效经济打孔.钻头每到一个孔就一次性把这个孔完成.

我们要使用的具体遗传算法：

相见论文最后附件。

六、模型评价

本文在建立模型时，对大量坐标数据进行统计处理。通过合理的假设，将许多问题都归结到一个模型中去，又通过运用遗传算法对大量数据处理，不仅使此类选择最优路线问题变得简化、直观、易于求解，更减少了处理问题时的人工运算量。并且我们所建立的数学模型在实际生活中也有一定推广意义，选择最佳阿路径问题在现实生活中是普

遍存在的。比如：乘坐公交车路径、邮递员送信上门、多景点儿旅游选择路线、紧急火灾救援…根据我们所建立的模型，在现实生活中的最优路径选择问题就可以做到科学性和合理性。不过我们的模型都是在合理假设的条件下建立的，我们所求解的值有近似性，对于那些需要精确计算的问题就需要做出进一步的深入和改进。

七、模型的改进与应用

进一步全面考虑分析实际问题，把刀片转换时间及成本考虑到实际工程中去。

模型的改进:在是否需要考虑减少刀片转换成本时,需要参照两个因素:生产效率和生产成本,具体情况依照应用而定。

八、参考文献

[1] 万方数据，印制板打孔最短路径的遗传算法实现[M]，百度文库，2012.5.1

[2] 萧树铁，大学数学[M]，北京市：高等教育出版社，2006

附件1：

我们使用的遗传算法具体程序：

说明: fga.m 为遗传算法的主程序; 采用二进制Gray编码,采用基于轮盘赌法的非线性排名选择, 均匀交叉,变异操作,而且还引入了倒位操作!

function

[BestPop,Trace]=fga(FUN,LB,UB,eranum,popsize,pCross,pMutation,pInversion,options) % [BestPop,Trace]=fmaxga(FUN,LB,UB,eranum,popsize,pcross,pmutation)

% Finds a maximum of a function of several variables.

% fmaxga solves problems of the form:

% max F(X) subject to: LB <= X <= UB

% BestPop - 最优的群体即为最优的染色体群

% Trace - 最佳染色体所对应的目标函数值

% FUN - 目标函数

% LB - 自变量下限

% UB - 自变量上限

% eranum - 种群的代数,取100--1000(默认200)

% popsize - 每一代种群的规模；此可取50--200(默认100)

% pcross - 交叉概率,一般取0.5--0.85之间较好(默认0.8)

% pmutation - 初始变异概率,一般取0.05-0.2之间较好(默认0.1)

% pInversion - 倒位概率,一般取0.05－0.3之间较好(默认0.2)

% options - 1*2矩阵,options(1)=0二进制编码(默认0),option(1)~=0十进制编%码,option(2)设定求解精度(默认1e-4)

%

% ------------------------------------------------------------------------

T1=clock;

if nargin<3, error('FMAXGA requires at least three input arguments'); end

if nargin==3, eranum=200;popsize=100;pCross=0.8;pMutation=0.1;pInversion=0.15;options=[0 1e-4];end if nargin==4, popsize=100;pCross=0.8;pMutation=0.1;pInversion=0.15;options=[0 1e-4];end

if nargin==5, pCross=0.8;pMutation=0.1;pInversion=0.15;options=[0 1e-4];end

if nargin==6, pMutation=0.1;pInversion=0.15;options=[0 1e-4];end

if nargin==7, pInversion=0.15;options=[0 1e-4];end

if find((LB-UB)>0)

error('数据输入错误,请重新输入(LB

end

s=sprintf('程序运行需要约%.4f 秒钟时间,请稍等......',(eranum*popsize/1000));

disp(s);

global m n NewPop children1 children2 VarNum

bounds=[LB;UB]';bits=[];VarNum=size(bounds,1);

precision=options(2);%由求解精度确定二进制编码长度

bits=ceil(log2((bounds(:,2)-bounds(:,1))' ./ precision));%由设定精度划分区间

[Pop]=InitPopGray(popsize,bits);%初始化种群

[m,n]=size(Pop);

NewPop=zeros(m,n);

children1=zeros(1,n);

children2=zeros(1,n);

pm0=pMutation;

BestPop=zeros(eranum,n);%分配初始解空间BestPop,Trace

Trace=zeros(eranum,length(bits)+1);

i=1;

while i<=eranum

for j=1:m

value(j)=feval_r(FUN(1,:),(b2f(Pop(j,:),bounds,bits)));%计算适应度end

[MaxValue,Index]=max(value);

BestPop(i,:)=Pop(Index,:);

Trace(i,1)=MaxValue;

Trace(i,(2:length(bits)+1))=b2f(BestPop(i,:),bounds,bits);

[selectpop]=NonlinearRankSelect(FUN,Pop,bounds,bits);%非线性排名选择[CrossOverPop]=CrossOver(selectpop,pCross,round(unidrnd(eranum-i)/eranum));

%采用多点交叉和均匀交叉，且逐步增大均匀交叉的概率

%round(unidrnd(eranum-i)/eranum)

[MutationPop]=Mutation(CrossOverPop,pMutation,VarNum);%变异

[InversionPop]=Inversion(MutationPop,pInversion);%倒位

Pop=InversionPop;%更新

pMutation=pm0+(i^4)*(pCross/3-pm0)/(eranum^4);

%随着种群向前进化，逐步增大变异率至1/2交叉率

p(i)=pMutation;

i=i+1;

end

t=1:eranum;

plot(t,Trace(:,1)');

title('函数优化的遗传算法');xlabel('进化世代数(eranum)');ylabel('每一代最优适应度(maxfitness)');

[MaxFval,I]=max(Trace(:,1));

X=Trace(I,(2:length(bits)+1));

hold on; plot(I,MaxFval,'*');

text(I+5,MaxFval,['FMAX=' num2str(MaxFval)]);

str1=sprintf('进化到%d 代,自变量为%s 时,得本次求解的最优值%f\n对应染色体是：%s',I,num2str(X),MaxFval,num2str(BestPop(I,:)));

disp(str1);

%figure(2);plot(t,p);%绘制变异值增大过程

T2=clock;

elapsed_time=T2-T1;

if elapsed_time(6)<0

elapsed_time(6)=elapsed_time(6)+60; elapsed_time(5)=elapsed_time(5)-1;

end

if elapsed_time(5)<0

elapsed_time(5)=elapsed_time(5)+60;elapsed_time(4)=elapsed_time(4)-1;

end %像这种程序当然不考虑运行上小时啦

str2=sprintf('程序运行耗时%d 小时%d 分钟%.4f 秒',elapsed_time(4),elapsed_time(5),elapsed_time(6));

disp(str2);

%初始化种群

%采用二进制Gray编码,其目的是为了克服二进制编码的Hamming悬崖缺点

function [initpop]=InitPopGray(popsize,bits)

len=sum(bits);

initpop=zeros(popsize,len);%The whole zero encoding individual

for i=2:popsize-1

pop=round(rand(1,len));

pop=mod(([0 pop]+[pop 0]),2);

%i=1时,b(1)=a(1);i>1时,b(i)=mod(a(i-1)+a(i),2)

%其中原二进制串:a(1)a(2)...a(n),Gray串:b(1)b(2)...b(n)

initpop(i,:)=pop(1:end-1);

end

initpop(popsize,:)=ones(1,len);%The whole one encoding individual

%解码

function [fval] = b2f(bval,bounds,bits)

% fval - 表征各变量的十进制数

% bval - 表征各变量的二进制编码串

% bounds - 各变量的取值范围

% bits - 各变量的二进制编码长度

scale=(bounds(:,2)-bounds(:,1))'./(2.^bits-1); %The range of the variables

numV=size(bounds,1);

cs=[0 cumsum(bits)];

for i=1:numV

a=bval((cs(i)+1):cs(i+1));

fval(i)=sum(2.^(size(a,2)-1:-1:0).*a)*scale(i)+bounds(i,1);

end

%选择操作

%采用基于轮盘赌法的非线性排名选择

%各个体成员按适应值从大到小分配选择概率：

%P(i)=(q/1-(1-q)^n)*(1-q)^i, 其中P(0)>P(1)>...>P(n), sum(P(i))=1

function [selectpop]=NonlinearRankSelect(FUN,pop,bounds,bits)

global m n

selectpop=zeros(m,n);

fit=zeros(m,1);

for i=1:m

fit(i)=feval_r(FUN(1,:),(b2f(pop(i,:),bounds,bits)));%以函数值为适应值做排名依据

end

selectprob=fit/sum(fit);%计算各个体相对适应度(0,1)

q=max(selectprob);%选择最优的概率

x=zeros(m,2);

x(:,1)=[m:-1:1]';

[y x(:,2)]=sort(selectprob);

r=q/(1-(1-q)^m);%标准分布基值

newfit(x(:,2))=r*(1-q).^(x(:,1)-1);%生成选择概率

newfit=cumsum(newfit);%计算各选择概率之和

rNums=sort(rand(m,1));

fitIn=1;newIn=1;

while newIn<=m

if rNums(newIn)

selectpop(newIn,:)=pop(fitIn,:);

newIn=newIn+1;

else

fitIn=fitIn+1;

end

end

%交叉操作

function [NewPop]=CrossOver(OldPop,pCross,opts)

%OldPop为父代种群，pcross为交叉概率

global m n NewPop

r=rand(1,m);

y1=find(r

y2=find(r>=pCross);

len=length(y1);

if len>2&mod(len,2)==1%如果用来进行交叉的染色体的条数为奇数，将其调整为偶数

y2(length(y2)+1)=y1(len);

y1(len)=[];

end

if length(y1)>=2

for i=0:2:length(y1)-2

if opts==0

[NewPop(y1(i+1),:),NewPop(y1(i+2),:)]=EqualCrossOver(OldPop(y1(i+1),:),OldPop(y1(i+2) ,:));

else

[NewPop(y1(i+1),:),NewPop(y1(i+2),:)]=MultiPointCross(OldPop(y1(i+1),:),OldPop(y1(i+2) ,:));

end

end

end

NewPop(y2,:)=OldPop(y2,:);

%采用均匀交叉

function [children1,children2]=EqualCrossOver(parent1,parent2)

global n children1 children2

hidecode=round(rand(1,n));%随机生成掩码

crossposition=find(hidecode==1);

holdposition=find(hidecode==0);

children1(crossposition)=parent1(crossposition);%掩码为1，父1为子1提供基因children1(holdposition)=parent2(holdposition);%掩码为0，父2为子1提供基因

children2(crossposition)=parent2(crossposition);%掩码为1，父2为子2提供基因children2(holdposition)=parent1(holdposition);%掩码为0，父1为子2提供基因

%采用多点交叉，交叉点数由变量数决定

function [Children1,Children2]=MultiPointCross(Parent1,Parent2)

global n Children1 Children2 VarNum

Children1=Parent1;

Children2=Parent2;

Points=sort(unidrnd(n,1,2*VarNum));

for i=1:VarNum

Children1(Points(2*i-1):Points(2*i))=Parent2(Points(2*i-1):Points(2*i));

Children2(Points(2*i-1):Points(2*i))=Parent1(Points(2*i-1):Points(2*i));

end

%变异操作

function [NewPop]=Mutation(OldPop,pMutation,VarNum)

global m n NewPop

r=rand(1,m);

position=find(r<=pMutation);

len=length(position);

if len>=1

for i=1:len

k=unidrnd(n,1,VarNum); %设置变异点数，一般设置1点

for j=1:length(k)

if OldPop(position(i),k(j))==1

OldPop(position(i),k(j))=0;

else

OldPop(position(i),k(j))=1;

end

end

end

end

NewPop=OldPop;

%倒位操作

function [NewPop]=Inversion(OldPop,pInversion)

global m n NewPop

NewPop=OldPop;

r=rand(1,m);

PopIn=find(r<=pInversion);

len=length(PopIn);

if len>=1

for i=1:len

d=sort(unidrnd(n,1,2));

if d(1)~=1&d(2)~=n

NewPop(PopIn(i),1:d(1)-1)=OldPop(PopIn(i),1:d(1)-1);

NewPop(PopIn(i),d(1):d(2))=OldPop(PopIn(i),d(2):-1:d(1));

NewPop(PopIn(i),d(2)+1:n)=OldPop(PopIn(i),d(2)+1:n);

end

end

end