遗传算法入门报告

遗传算法入门报告

信息与计算科学专业基础课

Computer Graphics

摘要：

Report Of course experiment 遗传算法学课 程论文

遗传算法入门报告

遗传算法（Genetic Algorithm）是一类借鉴生物界的进化规律（适者生存，优胜劣汰遗传机制）演化而来的随机化搜索方法。它是由美国的J.Holland教授1975年首先提出，其主要特点是直接对结构对象进行操作，不存在求导和函数连续性的限定；具有内在的隐并行性和更好的全局寻优能力；采用概率化的寻优方法，能自动获取和指导优化的搜索空间，自适应地调整搜索方向，不需要确定的规则。遗传算法的这些性质，已被人们广泛地应用于组合优化、机器学习、信号处理、自适应控制和人工生命等领域。它是现代有关智能计算中的关键技术。

Concisely stated, a genetic algorithm (or GA for short) is a programming

technique that mimics biological evolution as a problem-solving strategy. Given a

specific problem to solve, the input to the GA is a set of potential solutions to that

problem, encoded in some fashion, and a metric called a fitness function that allows

each candidate to be quantitatively evaluated. These candidates may be solutions

already known to work, with the aim of the GA being to improve them, but more often they are generated at random.

The GA then evaluates each candidate according to the fitness function. In a pool

of randomly generated candidates, of course, most will not work at all, and these will be deleted. However, purely by chance, a few may hold promise - they may show

activity, even if only weak and imperfect activity, toward solving the problem.

关键词：

遗传算法、概念、发展、特点

正文：

一、遗传算法的发展及历史

遗传算法（Genetic Algorithms,缩写为GA）是基于生物进化理论的原理发展起来的一种广为应用的、高效的随机搜索与优化的方法。其主要特点是群体搜索策略和群体中个体之间的信息交换，搜索不依赖于梯度信息。它是在20世纪70年代初期由美国密执根大学的霍兰教授发展起来的。1975年霍兰教授发表了第一本比较系统论述遗传算法的专著《自然系统与人工系统中的适应性》（《Adaptation in Natural and Artifical Systems》）。遗传算法最初被研究的出发点不是为专门解决最优化问题而设计的，它与进化策略、进化规划共同构成了进化算法的主要框架，都是为当时人工智能的发展而

遗传算法入门报告

服务的。迄今为止，遗传算法是进化算法中最广为人知的算法。

近几年来，遗传算法主要在复杂问题求解和工业工程领域应用，取得了一些令人信服的结果，所以引起了很多人的关注，而且在发展过程中，进化策略、进化规则和遗传算法之间差异越来越小。遗传算法成功的应用包括：作业调度与排序、可靠性设计、车辆路径选择与调度、成组技术、设备布置与分配、交通问题等。

二、遗传算法的特点

遗传算法是解决搜索问题的一种通用算法，对于各种通用问题都可以使用。搜索算法的共同特征为：1、首先组成一组候选解；2、依据某些适应性条件测算这些候选解的适应度；3、根据适应度保留某些候选解，放弃其他候选解；4、对保留的候选解进行某些操作，生成新的候选解。在遗传算法中，上述几个特征以一种特殊的方式组合在一起：基于染色体群的并行搜索，带有猜测性质的选择操作、交换操作和突变操作。这种特殊的组合方式将遗传算法与其他搜索算法区别开来。

遗传算法还有以下几方面的特点：

1) 遗传算法的处理对象不是参数本身，而是对参数集进行了编码的个体。此操作使得遗传算法可直接对结构对象进行操作。

2) 许多传统搜索算法都是单点搜索算法，容易陷入局部的最优解。遗传算法同时处理群体中的多个个体，即对搜索空间中的多个解进行评估，减少了陷入局部最优解的风险，同时算法本身易于实现并行化。

3) 遗传算法基本上不用搜索空间的知识或其他辅助信息，而仅用适应度函数值来评估个体，在此基础上进行遗传操作。适应度函数不仅不受连续可微的约束，而且其定义域可以任意设定。这一特点使得遗传算法的应用范围大大扩展。

4) 遗传算法不是采用确定性规则，而是采用概率的变迁规则来指导它的搜索方向。

5) 具有自组织、自适应和自学习性。遗传算法利用进化过程获得的信息自行组织搜索，适应度大的个体具有较高的生存概率，并获得更适应环境的基因结构。

三、遗传算法的不足之处

遗传算法作为一种优化方法，它存在自身的局限性：

1) 编码不规范及编码存在表示的不准确性。

2) 单一的遗传算法编码不能全面地将优化问题的约束表示出来。考虑约束的一

遗传算法入门报告

个方法就是对不可行解采用阈值，这样，计算的时间必然增加。

3) 遗传算法通常的效率比其他传统的优化方法低。

4) 遗传算法容易出现过早收敛。

5) 遗传算法对算法的精度、可信度、计算复杂性等方面，还没有有效的定量分析方法。

四、遗传算法的运用领域

遗传算法提供了一种求解复杂系统优化间题的通用框架，它不依赖于问题的具体领域，对问题的种类有很强的鲁棒性，所以广泛应用于很多学科。下面是遗传算法的一些主要应用领域：

1) 函数优化

函数优化是遗传算法的经典应用领域，也是对遗传算法进行性能评价的常用算例。对于一些非线性、多模型、多目标的函数优化问题，用其他优化方法较难求解，用遗传算法可以方便地得到较好的结果。

2) 组合优化

随着问题规模的增大，组合优化问题的搜索空间也急剧扩大，有时在目前的计算机上用枚举法很难或甚至不可能求出其精确最优解。对这类复杂问题，人们己意识到应把主要精力放在寻求其满意解上，而遗传算法是寻求这种满意解的最佳工具之一。实践证明，遗传算法对于组合优化中的NP完全问题非常有效。例如，遗传算法已经在求解旅行商问题、背包问题、装箱问题、图形划分问题等方面得到成功的应用。

3) 生产调度问题

生产调度问题在很多情况下所建立起来的数学模型难以精确求解，即使经过一些简化之后可以进行求解，也会因简化得太多而使得求解结果与实际相差甚远。而目前在现实生产中也主要是靠一些经验来进行调度。现在遗传算法已成为解决复杂调度问题的有效工具，在单件生产车间调度、流水线生产车间调度、生产规划、任务分配等方面遗传算法都得到了有效的应用。

4) 自动控制

在自动控制领域中很多与优化相关的问题需要求解，遗传算法已在其中得到了初步的应用，并显示出了良好的效果。例如用遗传算法进行航空控制系统的优化、使用

遗传算法入门报告

遗传算法设计空间交会控制器、基于遗传算法的模糊控制器的优化设计、基于遗传算法的参数辨识、基于遗传算法的模糊控制规则的学习、利用遗传算法进行人工神经网络的结构优化设计和权值学习等，都显示出了遗传算法在这些领域中应用的可能性。

5) 机器人学

机器人是一类复杂的难以精确建模的人工系统，而遗传算法的起源就来自于对人工自适应系统的研究，所以机器人学理所当然地成为遗传算法的一个重要应用领域。例如，遗传算法已经在移动机器人路径规划、关节机器人运动轨迹规划、机器人逆运动学求解、细胞机器人的结构优化和行为协调等方面得到研究和应用。

6) 图像处理

图像处理是计算机视觉中的一个重要研究领域。在图像处理过程中，如扫描、特征提取、图像分割等不可避免地会存在一些误差，这些误差会影响图像处理的效果。如何使这些误差最小是使计算机视觉达到实用化的重要要求。遗传算法在这些图像处理中的优化计算方面找到了用武之地，日前已在模式识别、图像恢复、图像边缘特征提取等方面得到了应用。

7) 人工生命

人工生命是用计算机、机械等人工媒体模拟或构造出的具有自然生物系统特有行为的人造系统。自组织能力和自学习能力是人工生命的两大主要特征。人工生命与遗传算法有着密切的关系，基于遗传算法的进化模型是研究人工生命现象的重要基础理论。虽然人工生命的研究尚处于启蒙阶段．但遗传算法已在其进化模型、学习模型、行为模型、自组织模型等方面显示出了初步的应用能力，并且必将得到更为深入的应用和发展。人工生命与遗传算法相辅相成，遗传算法为人工生命的研究提供了一个有效的工具，人工生命的研究也必将促进遗传算法的进一步发展。

8) 遗传编程

Koza发展了遗传编程的概念，他使用了以LISP语言所表示的编码方法，基于对一种树型结构所进行的遗传操作来自动生成计算机程序。虽然遗传编程的理论尚未成熟，应用也有一些限制，但它已成功地应用于人工智能、机器学习等领域。

9) 机器学习

学习能力是高级自适应系统所应具备的能力之一。基于遗传算法的机器学习，特别是分类器系统，在很多领域中都得到了应用。例如，遗传算法被用于学习模糊控制

遗传算法入门报告

规则，利用遗传算法来学习隶属度函数，从而更好地改进了模糊系统的性能；基于遗传算法的机器学习可用来调整人工神经网络的连接权，也可用于人工神经网络的网络结构优化设计；分类器系统也在学习式多机器人路径规划系统中得到了成功的应用。

五、遗传算法中的基本概念

群体：又称种群、染色群体，个体的集合，代表问题的解空间子集。

串及串空间：串是个体的表达形式，对应着遗传学中的染色体，对应实际问题的一个解。

群体规模：染色体群中个体的数目称为群体的大小或群体规模。

基因：是指染色体的一个片段，基因可以是一个数值、一组数或一串字符。

交换：指在一定条件下两条染色体上的一个或几个基因相互交换位置。

交换概率：判断是否满足交换条件的一个小于1的阈值。

变异：指在一定条件下随即改变一条染色体上的一个或几个基因值。

变异概率：判断是否满足变异条件的一个小于1的阈值。

后代：染色体经过交换或变异后形成的新的个体。

适应度：用来度量种群中个体优劣的指标值，他通常表现为数值形式。

选择：根据染色体对应的适应值和问题的要求，筛选种群中的染色体，染色体的适应度越高，保存下来的概率越大，反之则越小，甚至被淘汰。

六、遗传算法终止规则

一般情况下遗传算法终止规则有三种情况：

1) 给定一个最大的遗传代数n，算法迭代在达到n时停止。

2) 给定问题一个下界x的计算方法，当进化达到要求的偏差范围时，算法终止。

3) 当监控得到的算法再进化已无法改进解的性能时停止计算。

遗传算法入门报告

图1 遗传算法工作原理示意图

遗传算法提供了一个求复杂系统优化问题的通用框架，它以适应度函数为依据，通过对群体中的个体施加遗传操作，实现群体内个体结构重组的迭代处理过程。一般来说，遗传算法有如下流程如图（如上图）。

七、遗传算法的关键步骤有：

1) 构造适应函数及选择规则：适应函数基本上依据优化问题的目标函数而定。当适应函数确定以后，自然选择规律是以适应函数值的大小及问题的要求来确定哪些染色体适应生存，哪些被淘汰。

2) 染色体编码：是指对优化问题的解进行编码。此处我们称一个解的编码为一个染色体，组成编码的元素称为基因。编码的目的主要用于优化问题解的表现形式和利于之后遗传算法中的计算。

3) 初始种群：由多个染色体组成具有一定群体规模的染色体集合或称解的集合。遗传算法将基于这个集合进行遗传算法，每一轮操作（包括交换、突变、选择）

遗传算法入门报告

后生存下来的染色体组成新的种群，形成可以繁衍下一代的群体。

4) 解码和染色体评估：运用适值函数计算种群（包括初始种群）中各染色体的适应值，计算各染色体的入选（生存）概率。

5) 选择：以适应函数值的大小以及问题的要求来确定哪些染色体适应生存，哪些被淘汰。生存下来的染色体形成可以繁衍下一代的新种群。判断是否满足问题要求，如果满足，停止操作，否则继续第6步以及后面的操作。

6) 交换：这一操作随机地选定一个位置，将两个染色体对应位置上的编码（基因）交叉呼唤，两个染色体得到两个后代。

7) 变异：这一操作随机地改变染色体中某一位置基因的值，一个染色体得到一个后代。这一步结束后，我们就得到了新一代染色体群体，重复第4步至第7步。

初始群体一般应该随机选取，随机选取达到所有状态遍历的可能性更大，因而最优解在遗传算法的进化中最终得以生存。

八、遗传算法应用举例：

1) 问题的提出

已知n个城市之间的相互距离，现有一个推销员必须遍访这n个城市，并且每个城市只能访问一次，最后又必须返回出发城市。如何安排他对这些城市的访问次序，可使其旅行路线的总长度最短？

用图论的术语来说，假设有一个图g=(v,e)，其中v是顶点集，e是边集，设d=(dij)

是由顶点i和顶点j之间的距离所组成的距离矩阵，旅行商问题就是求出一条通过所有顶点且每个顶点只通过一次的具有最短距离的回路。

这个问题可分为对称旅行商问题(dij=dji,,任意i,j=1,2,3，…,n)和非对称旅行商

问题(dij≠dji,,任意i,j=1,2,3，…,n)。

若对于城市v={v1,v2,v3,…,vn}的一个访问顺序为t=(t1,t2,t3,…,ti,…,tn),其中ti∈v(i=1,2,3,…,n)，且记tn+1= t1，则旅行商问题的数学模型为：

min l=σd(t(i),t(i+1)) （i=1,…,n）

旅行商问题是一个典型的组合优化问题，并且是一个np难问题，其可能的路径数目与城市数目n是成指数型增长的，所以一般很难精确地求出其最优解，本文采用遗传算法求其近似解。

2）遗传算法：

初始化过程：用v1,v2,v3,…,vn代表所选n个城市。定义整数pop-size作为染色体的个数，

遗传算法入门报告

并且随机产生pop-size个初始染色体，每个染色体为1到18的整数组成的随机序列。

适应度f的计算：对种群中的每个染色体vi，计算其适应度，f=σd(t(i),t(i+1)).

评价函数eval(vi)：用来对种群中的每个染色体vi设定一个概率，以使该染色体被选中的可能性与其种群中其它染色体的适应性成比例，既通过轮盘赌，适应性强的染色体被选择产生后台的机会要大，设alpha∈(0,1)，本文定义基于序的评价函数为eval(vi)=alpha*(1-alpha).^(i-1) 。[随机规划与模糊规划]

选择过程：选择过程是以旋转赌轮pop-size次为基础，每次旋转都为新的种群选择一个染色体。赌轮是按每个染色体的适应度进行选择染色体的。

step1 、对每个染色体vi,计算累计概率qi，q0=0;qi=σeval(vj) j=1,…,i;i=1,…pop-size. step2、从区间(0,pop-size)中产生一个随机数r；

step3、若qi-1 step4、重复step2和step3共pop-size次，这样可以得到pop-size个复制的染色体。

grefenstette编码：由于常规的交叉运算和变异运算会使种群中产生一些无实际意义的染色体，本文采用grefenstette编码《遗传算法原理及应用》可以避免这种情况的出现。所谓的grefenstette编码就是用所选队员在未选（不含淘汰）队员中的位置，如：

8 15 2 16 10 7 4 3 11 14 6 12 9 5 18 13 17 1

对应：

8 14 2 13 8 6 3 2 5 7 3 4 3 2 4 2 2 1。

交叉过程：本文采用常规单点交叉。为确定交叉操作的父代，从 到pop-size重复以下过程：从[0，1]中产生一个随机数r，如果r 将所选的父代两两组队，随机产生一个位置进行交叉，如： 8 14 2 13 8 6 3 2 5 7 3 4 3 2 4 2 2 1

6 12 3 5 6 8 5 6 3 1 8 5 6 3 3 2 1 1

交叉后为：

8 14 2 13 8 6 3 2 5 1 8 5 6 3 3 2 1 1

6 12 3 5 6 8 5 6 3 7 3 4 3 2 4 2 2 1

变异过程：本文采用均匀多点变异。类似交叉操作中选择父代的过程，在r 选择多个染色体vi作为父代。对每一个选择的父代，随机选择多个位置，使其在每位置

按均匀变异（该变异点xk的取值范围为[ukmin,ukmax],产生一个[0，1]中随机数r，该点

变异为x'k=ukmin+r(ukmax-ukmin)）操作。如：

8 14 2 13 8 6 3 2 5 7 3 4 3 2 4 2 2 1

遗传算法入门报告

变异后：

8 14 2 13 10 6 3 2 2 7 3 4 5 2 4 1 2 1

反grefenstette编码：交叉和变异都是在grefenstette编码之后进行的，为了循环操作

和返回最终结果，必须逆grefenstette编码过程，将编码恢复到自然编码。

循环操作：判断是否满足设定的带数xzome，否，则跳入适应度f的计算；是，结束遗传操作，跳出。

3）matlab 代码:

distTSP.txt

0 6 18 4 8

7 0 17 3 7

4 4 0 4 5

20 19 24 0 22

8 8 16 6 0

%GATSP.m

function gatsp1()

clear;

load distTSP.txt;

distance=distTSP;

N=5;

ngen=100;

ngpool=10;

%ngen=input('# of generations to evolve = ');

%ngpool=input('# of chromosoms in the gene pool = '); % size of genepool gpool=zeros(ngpool,N+1); % gene pool

for i=1:ngpool, % intialize gene pool

gpool(i,:)=[1 randomize([2:N]')' 1];

for j=1:i-1

while gpool(i,:)==gpool(j,:)

遗传算法入门报告

gpool(i,:)=[1 randomize([2:N]')' 1];

end

end

end

costmin=100000;

tourmin=zeros(1,N);

cost=zeros(1,ngpool);

increase=1;resultincrease=1;

for i=1:ngpool,

cost(i)=sum(diag(distance(gpool(i,:)',rshift(gpool(i,:))')));

end

% record current best solution

[costmin,idx]=min(cost);

tourmin=gpool(idx,:);

disp([num2str(increase) 'minmum trip length = ' num2str(costmin)])

costminold2=200000;costminold1=150000;resultcost=100000;

tourminold2=zeros(1,N);

tourminold1=zeros(1,N);

resulttour=zeros(1,N);

while

(abs(costminold2-costminold1) ;100)&(abs(costminold1-costmin) ;100)&(increase ;500)

costminold2=costminold1; tourminold2=tourminold1;

costminold1=costmin;tourminold1=tourmin;

increase=increase+1;

if resultcost>costmin

遗传算法入门报告

resultcost=costmin;

resulttour=tourmin;

resultincrease=increase-1;

end

for i=1:ngpool,

cost(i)=sum(diag(distance(gpool(i,:)',rshift(gpool(i,:))')));

end

% record current best solution

[costmin,idx]=min(cost);

tourmin=gpool(idx,:);

%==============

% copy gens in th gpool according to the probility ratio

% >1.1 copy twice

% >=0.9 copy once

% ;0.9 remove

[csort,ridx]=sort(cost);

% sort from small to big.

csum=sum(csort);

caverage=csum/ngpool;

cprobilities=caverage./csort;

copynumbers=0;removenumbers=0;

for i=1:ngpool,

if cprobilities(i) >1.1

copynumbers=copynumbers+1;

end

if cprobilities(i) <0.9

removenumbers=removenumbers+1;

end

end

遗传算法入门报告

copygpool=min(copynumbers,removenumbers);

for i=1:copygpool

for j=ngpool:-1:2*i+2 gpool(j,:)=gpool(j-1,:);

end

gpool(2*i+1,:)=gpool(i,:);

end

if copygpool==0

gpool(ngpool,:)=gpool(1,:);

end

%=========

%when genaration is more than 50,or the patterns in a couple are too close,do mutation

for i=1:ngpool/2

%

sameidx=[gpool(2*i-1,:)==gpool(2*i,:)];

diffidx=find(sameidx==0);

if length(diffidx)<=2

gpool(2*i,:)=[1 randomize([2:12]')' 1];

end

end

%===========

%cross gens in couples

for i=1:ngpool/2

[gpool(2*i-1,:),gpool(2*i,:)]=crossgens(gpool(2*i-1,:),gpool(2*i,:)); end

for i=1:ngpool,

cost(i)=sum(diag(distance(gpool(i,:)',rshift(gpool(i,:))')));

end

遗传算法入门报告

% record current best solution

[costmin,idx]=min(cost);

tourmin=gpool(idx,:);

disp([num2str(increase) 'minmum trip length = ' num2str(costmin)]) end

disp(['cost function evaluation: ' int2str(increase) ' times!'])

disp(['n:' int2str(resultincrease)])

disp(['minmum trip length = ' num2str(resultcost)])

disp('optimum tour = ')

disp(num2str(resulttour))

%====================================================

function B=randomize(A,rowcol)

% Usage: B=randomize(A,rowcol)

% randomize row orders or column orders of A matrix

% rowcol: if =0 or omitted, row order (default)

% if = 1, column order

rand('state',sum(100*clock))

if nargin == 1,

rowcol=0;

end

if rowcol==0,

[m,n]=size(A);

p=rand(m,1);

[p1,I]=sort(p);

B=A(I,:);

elseif rowcol==1,

Ap=A';

遗传算法入门报告

[m,n]=size(Ap);

p=rand(m,1);

[p1,I]=sort(p);

B=Ap(I,:)';

end

%=====================================================

function y=rshift(x,dir)

% Usage: y=rshift(x,dir)

% rotate x vector to right (down) by 1 if dir = 0 (default)

% or rotate x to left (up) by 1 if dir = 1

if nargin ;2, dir=0; end

[m,n]=size(x);

if m>1,

if n == 1,

col=1;

elseif n>1,

error('x must be a vector! break');

end % x is a column vectorelseif m == 1,

if n == 1, y=x;

return

elseif n>1,

col=0; % x is a row vector endend

if dir==1, % rotate left or up

if col==0, % row vector, rotate left

y = [x(2:n) x(1)];

elseif col==1,

y = [x(2:n); x(1)]; % rotate up

end

elseif dir==0, % default rotate right or down

遗传算法入门报告

if col==0,

y = [x(n) x(1:n-1)];

elseif col==1 % column vector

y = [x(n); x(1:n-1)];

end

end

%==================================================

function [L1,L2]=crossgens(X1,X2)

% Usage:[L1,L2]=crossgens(X1,X2)

s=randomize([2:12]')';

n1=min(s(1),s(11));n2=max(s(1),s(11));

X3=X1;X4=X2;

for i=n1:n2,

for j=1:13,

if X2(i)==X3(j),

X3(j)=0;

end

if X1(i)==X4(j), X4(j)=0;

end

end

end

j=13;k=13;

for i=12:-1:2,

if X3(i)~=0,

j=j-1;

t=X3(j);X3(j)=X3(i);X3(i)=t;

end

if X4(i)~=0,

k=k-1;

遗传算法入门报告

t=X4(k);X4(k)=X4(i);X4(i)=t;

end

end

for i=n1:n2

X3(2+i-n1)=X2(i);

X4(2+i-n1)=X1(i);

end

L1=X3;L2=X4;

九、参考文献：

【1】邵军力 张 景 魏长华 《人工智能基础》 电子工业出版社

【2】傅清祥 王晓东 《算法与数据结构》 电子工业出版社

【3】吴文虎 王建德 《实用算法的分析与程序设计》 电子工业出版社

【4】杨周妮,吴作伟,吴铁安. ANSYS优化方法与遗传算法在结构优化方面的比较[ J ]. 控制理论与应用, 2004 (7) : 2 - 6.

【5】马玉明,贺爱玲,李爱民. 遗传算法的理论研究综述. 山东轻工业学院学报, 2004,18(3):77～80

本文来源：https://www.bwwdw.com/article/9eji.html