第1页 / 共9页
第2页 / 共9页
第3页 / 共9页
第4页 / 共9页
第5页 / 共9页
第6页 / 共9页
第7页 / 共9页
第8页 / 共9页
matlab在遗传算法中的应用.doc
遗传算法及其 MATLAB 实现
主要参考书：
MATLAB 6.5 辅助优化计算与设计 飞思科技产品研发中心编著
电子工业出版社 2003.1
遗传算法及其应用 陈国良等编著
人民邮电出版社 1996.6
主要内容：
遗传算法简介
遗传算法的 MATLAB 实现
应用举例
在工业工程中,许多最优化问题性质十分复杂,很难用
传统的优化方法来求解.自 1960 年以来,人们对求解这类难
解问题日益增加.一种模仿生物自然进化过程的、被称为“
进化算法（evolutionary algorithm）”的随机优化技术在解这
类优化难题中显示了优于传统优化算法的性能。目前，进化
算法主要包括三个研究领域：遗传算法、进化规划和进化
策略。其中遗传算法是迄今为止进化算法中应用最多、比较
成熟、广为人知的算法。
一、遗传算法简介
遗传算法（Genetic Algorithm, GA）最先是由美国 Mic-
hgan 大学的 John Holland 于 1975 年提出的。遗传算法是
模拟达尔文的遗传选择和自然淘汰的生物进化过程的计算
模型。它的思想源于生物遗传学和适者生存的自然规律，
是具有“生存+检测”的迭代过程的搜索算法。遗传算法
以一种群体中的所有个体为对象，并利用随机化技术指
导对一个被编码的参数空间进行高效搜索。其中，选择、
交叉和变异构成了遗传算法的遗传操作；参数编码、初始
群体的设定、适应度函数的设计、遗传操作设计、控制参
数设定等 5 个要素组成了遗传算法的核心内容。
遗传算法的基本步骤：
遗传算法是一种基于生物自然选择与遗传机理的随机
搜索算法，与传统搜索算法不同，遗传算法从一组随机产
生的称为“种群(Population)”的初始解开始搜索过程。种
群中的每个个体是问题的一个解，称为“染色体(chromos
ome)”。染色体是一串符号，比如一个二进制字符串。这
些染色体在后续迭代中不断进化，称为遗传。在每一代中
用“适值(fitness)”来测量染色体的好坏，生成的下一代染
色体称为后代（offspring）。后代是由前一代染色体通过交
叉(crossover)或者变异（mutation）运算形成的。
在新一代形成过程中，根据适度的大小选择部分后代，淘
汰部分后代。从而保持种群大小是常数。适值高的染色体
被选中的概率较高，这样经过若干代之后，算法收敛于最
好的染色体，它很可能就是问题的最优解或次优解。
主要步骤如下所示：
(1)编码：GA 在进行搜索之前先将解空间的解数据表示成
遗传空间的基因型串结构数据，这些串结构数据的不同组
合便构成了不同的点。
(2)初始群体的生成：随机产生 N 个初始串结构数据，每个
串结构数据称为一个个体，N 个个体构成了—个群体。
GA 以这 N 个串结构数据作为初始点开始迭代。
(3)适应性值评估检测：适应性函数表明个体或解的优劣性。
对于不同的问题，适应性函数的定义方式也不同。
(4)选择：选择的目的是为了从当前群体个选出优良的个体
，使它们有机会作为父代为下一代繁殖子孙。遗传算法通
过选择过程体现这一思想，进行选择的原则是适应性强的
个体为下一代贡献一个或多个后代的概率大。选择实现了
达尔文的适者生存原则。
(5)交叉：交叉操作是遗传算法中最主要的遗传操作。通过
交叉操作可以得到新一代个体，新个体组合了其父辈个体
的特性。交叉体现了信息交换的思想。
(6)变异：变异首先在群体中随机选择一个个体，对于选中
的个体以一定的概率随机地改变串结构数据中某个串的值。
同生物界一样，GA 中变异发生的概率很低，通常取值在
0.001~0.01 之间。变异为新个体的产中提供了机会。
实际上，遗传算法中有两类运算：
● 遗传运算：交叉和变异
● 进化运算：选择
GA 的计算过程流程图
编码和种群生成
种群适应度估计
选择
交叉
变异
遗传算法的特点
GA 是对问题参数的编码组进行计算，
而不是针对参数本身。
GA 的搜索是从问题解的编码组开始搜素、
而不是从单个解开始。
GA 使用目标函数值（适应度）这一信息进行搜索，
而不需导数等其他信息。
GA 算法使用的选择、交叉、变异这三个算子都是随机操作，
而不是确定规则。
举例图解说明计算流程
二、遗传算法的 MATLAB 实现
需要如下主函数：
编码和种群生成
function [pop] = initializega(num,bounds,evalFN,evalOps,options)
% pop
% num
- the initial, evaluated, random population
- the size of the population, i.e. the number to create
of cities in a tsp
% bounds - the number of permutations in an individual (e.g., number
%
% evalFN - the evaluation fn, usually the name of the .m file for evaluation
% evalOps- any options to be passed to the eval function defaults [ ]
% options- options to the initialize function, ie. [eps, float/binary, prec]
where eps is the epsilon value and the second option is 1 for
%
%
orderOps, prec is the precision of the variables defaults [1e-6 1]
交叉
function [c1,c2] = arithXover(p1,p2,bounds,Ops)
% Arith crossover takes two parents P1,P2 and performs an interpolation
% along the line formed by the two parents.
%
% function [c1,c2] = arithXover(p1,p2,bounds,Ops)
% p1
% p2
% bounds
% Ops
- the first parent ( [solution string function value] )
- the second parent ( [solution string function value] )
- the bounds matrix for the solution space
- Options matrix for arith crossover [gen #ArithXovers]
选择
normGeomSelect：NormGeomSelect is a ranking selection
function based on the normalized geometric distribution.
（基于正态分布的序列选择函数）
变异
function[newPop] = normGeomSelect(oldPop,options)
% NormGeomSelect is a ranking selection function based on
the normalized
% geometric distribution.
%
% function[newPop] = normGeomSelect(oldPop,options)
% newPop
% oldPop - the current population
% options - options to normGeomSelect
- the new population selected from the oldPop
[gen probability_of_selecting_best]
一些辅助函数：
f2b ：Return the binary representation of the float number
fval（将浮点数转化为二进制数）
b2f：Return the float number corresponing to the binary
representation of bval. （将二进制数转化为
浮点数）
nonUnifMutation： Non uniform mutation changes one
of the parameters of the parent based on a non-uniform
probability distribution. This Gaussian distribution starts wide,
and narrows to a point distribution as the current generation
approaches the maximum generation.
（基于非均一概率分布进行非均一变异）
maxGenTerm：Returns 1, i.e. terminates the GA when the
maximal_generation is reached.
（当迭代次数大于最大迭代次数时，终止遗传算法，返回
为 1，否则返回为 0。）
roulette：roulette is the traditional selection function with the
probability of surviving equal to the fittness of i / sum of the
fittness of all individuals
三、应用举例
1.计算下列函数的最大值。
f(x)=x+10*sin(5x)+7cos(4x) , x∈[0,9]
方式 1 >>gademo
方式 2
step 1 编写目标函数 gademo1eval1.m
function [sol, val] = gaDemo1Eval(sol,options)
x=sol(1);
val = x + 10*sin(5*x)+7*cos(4*x);
step 2 生成初始种群，大小为 10
initPop=initializega(10,[0, 9],'gademo1eval1',[],[1e-6,1]);
step 3 25 次遗传迭代
[x, endPop,bpop,trace] = ga([0 9],'gademo1eval1',[],initPop,...
[1e-6 1 1],'maxGenTerm',25,...
'normGeomSelect',[0.08],...
['arithXover'],[2],...
'nonUnifMutation',[2, 25 ,3])
% Output Arguments:
% x
% endPop
% bPop
- the best solution found during the course of the
run
% traceInfo
- a matrix of best and means of the ga
- the final population
- a trace of the best population
(解的变化)
for each generation
(种群平均值的变化)
%
% Input Arguments:
% bounds - a matrix of upper and lower bounds
on the variables
% evalFN - the name of the evaluation .m function
% evalOps
- options to pass to the evaluation function ([NULL])
- a matrix of solutions that can be initialized
% startPop
%
% opts
from initialize.m
- [epsilon, prob_ops ,display]
%
change required to consider two solutions
different, prob_ops 0 if you want to apply the
genetic operators probabilisticly to each solution,
1 if you are supplying a deterministic number
of operator
progress 0 for quiet. ([1e-6 1 0])
% termFN - name of the .m termination function
applications and display is 1 to output
% termOps
% selectFN
% selectOpts
%
(['maxGenTerm'])
- options string to be passed to the termination
function
([100]).
- name of the .m selection function
(['normGeomSelect'])
- options string to be passed to select after
select(pop,#,opts) ([0.08])
% xOverFNS
% xOverOps
% mutFNs
%
% mutOps
- a string containing blank seperated names
of Xover.m files (['arithXover heuristicXover
simpleXover'])
- A matrix of options to pass to Xover.m files
with the first column being the number of that
xOver to perform similiarly for mutation
([2 0;2 3;2 0])
- a string containing blank seperated names of
mutation.m files (['boundaryMutation
multiNonUnifMutation ...
nonUnifMutation unifMutation'])
- A matrix of options to pass to Xover.m files
with the first column being the number of that
xOver to perform similiarly for mutation
([4 0 0;6 100 3;4 100 3;4 0 0])
2.求 sin(x) 在 0 到 3.14 之间的最大值.
function [sol, val] = sin1(sol,options)
x=sol(1);
val =sin(x);
initPop=initializega(10,[0, 3.14],'sin1',[],[1e-6,1]);
[x, endPop,bpop,trace] = ga([0 3.14],'sin1',[],initPop,...
[1e-6 1 1],'maxGenTerm',25,...
'normGeomSelect',[0.08],...
['arithXover'],[2],...
'nonUnifMutation',[2, 25 ,3])
3. binaryExample.m
二元函数例子 二进制编码
方式 1 >> binaryExample
方式 2
function [sol,val] = gaMichEval(sol,options)
val = 21.5 + sol(1) * sin(4*pi*sol(1)) + sol(2)*sin(20*pi*sol(2));
%%%%%%%%%%%%%%
global bounds
% Setting the seed back to the beginning for comparison sake
rand('seed',0)
% Crossover Operators
xFns = 'simpleXover';
xOpts = [.4];
% Mutation Operators
mFns = 'binaryMutation';
mOpts = [0.005];
% Termination Operators
termFns = 'maxGenTerm';
termOps = [200]; % 200 Generations
% Selection Function
selectFn = 'roulette'
selectOps = [];
% Evaluation Function
evalFn = 'gaMichEval';
evalOps = [];
% Bounds on the variables
bounds = [-3, 12.1; 4.1, 5.8];
% GA Options [epsilon float/binar display]
gaOpts=[1e-6 0 1];
% Generate an intialize population of size 20
startPop = initializega(20,bounds,'gaMichEval',[],[1e-6 0]);
[x endPop bestPop trace]=ga(bounds,evalFn,evalOps,startPop,gaOpts,...
termFns,termOps,selectFn,selectOps,xFns,xOpts,mFns,mOpts);
% x is the best solution found
x
% endPop is the ending population
endPop
% trace is a trace of the best value and average value of generations
trace
clf
plot(trace(:,1),trace(:,2));
hold on
plot(trace(:,1),trace(:,3));
% Lets increase the population size by running the defaults
%
rand('seed',0)
termOps=[100];
[x endPop bestPop trace]=ga(bounds,evalFn,evalOps,[],gaOpts,termFns,termOps,...
selectFn,selectOps);
% x is the best solution found
x
% endPop is the ending population
%endPop
% trace is a trace of the best value and average value of generations
%trace
% Plot the best over time
clf
plot(trace(:,1),trace(:,2));
% Add the average to the graph
hold on
plot(trace(:,1),trace(:,3));
4. floatExample.m
二元函数例子 浮点编码
global bounds
% Setting the seed to the same for binary
rand('seed',156789)
% Crossover Operators
xFns = 'arithXover heuristicXover simpleXover';
xOpts = [1 0; 1 3; 1 0];
% Mutation Operators
mFns = 'boundaryMutation multiNonUnifMutation nonUnifMutation unifMutation';
mOpts = [2 0 0;3 200 3;2 200 3;2 0 0];
% Termination Operators
termFns = 'maxGenTerm';
termOps = [200]; % 200 Generations
% Selection Function
selectFn = 'normGeomSelect';
selectOps = [0.08];
% Evaluation Function
evalFn = 'gaMichEval';
evalOps = [];
% Bounds on the variables
bounds = [-3 12.1; 4.1 5.8];
% GA Options [epsilon float/binar display]
gaOpts=[1e-6 1 1];
% Generate an intialize population of size 20
startPop = initializega(20,bounds,'gaMichEval',[1e-6 1])
[x endPop bestPop trace]=ga(bounds,evalFn,evalOps,startPop,gaOpts,...
termFns,termOps,selectFn,selectOps,xFns,xOpts,mFns,mOpts);
% x is the best solution found
x
% endPop is the ending population
endPop
% bestPop is the best solution tracked over generations
bestPop
% Plot the best over time
clf
plot(trace(:,1),trace(:,2));
% Add the average to the graph
hold on
plot(trace(:,1),trace(:,3));
% Lets increase the population size by running the defaults
[x endPop bestPop trace]=ga(bounds,evalFn,evalOps,[],gaOpts);
% x is the best solution found
x
% endPop is the ending population
endPop
% bestPop is the best solution tracked over generations
bestPop
% Plot the best over time
clf
plot(trace(:,1),trace(:,2));
% Add the average to the graph
hold on
plot(trace(:,1),trace(:,3));
5. 求解货郎担问题（TSP）
orderBasedExample.m
6. 求解非线性规划问题
max f(x)
s.t. gi(x)<=0,i=1,...,m
hi(x)=0,i=m+1,...,n
x∈Ω
？不可行的后代？
拒绝策略
修复策略
改进遗传算子策略
惩罚策略
e.g. min f(x)=(x1-2)2+(x2-1)2
s.t. g1(x)=x1-2x2+1>=0
g2(x)=x12/4-x22+1>=0
分析：取加法形式的适值函数：
val(x)=f(x)+p(x)
惩罚函数 p(x)由两部分组成，可变乘法因子和
违反约束乘法，其表达式如下：
)x(p
m
1i
0
)x(gr
i
i
可行若
x
其它
其中 ri 是约束 i 的可变惩罚系数。
步骤如下：
相关推荐
2023年江西萍乡中考道德与法治真题及答案.doc
2012年重庆南川中考生物真题及答案.doc
2013年江西师范大学地理学综合及文艺理论基础考研真题.doc
2020年四川甘孜小升初语文真题及答案I卷.doc
2020年注册岩土工程师专业基础考试真题及答案.doc
2023-2024学年福建省厦门市九年级上学期数学月考试题及答案.doc
2021-2022学年辽宁省沈阳市大东区九年级上学期语文期末试题及答案.doc
2022-2023学年北京东城区初三第一学期物理期末试卷及答案.doc
2018上半年江西教师资格初中地理学科知识与教学能力真题及答案.doc
2012年河北国家公务员申论考试真题及答案-省级.doc
2020-2021学年江苏省扬州市江都区邵樊片九年级上学期数学第一次质量检测试题及答案.doc
2022下半年黑龙江教师资格证中学综合素质真题及答案.doc
