被选概率 0.1 0.02 0.2 0.0 0.0 0.1 0.1 0.0 0.0 0.09 2926493
数学建模工作室 2020/4/7
数学建模培训讲义
第5页 mecca_zj@
SUTM内点法（障碍函数法）
考虑问 m s .t.g fi X X i题 n 0i ： 1 ,2 ,.m ..( ,1 )
设集 D 0合 X|giX0,i1,2,,m ， D 0是可行
所有严格内点的集合。
后累加值 sum = ∑f(xi)
3） 产生一个随机数 N，0〈 N 〈 sum
4） 选择对应中间累加值S - mid 的第一个染色体进入交换集
5） 重复（3）和（4），直到获得足够的染色体。
(首个>=N的S-mid所对应的染色体被选中)
举例：
⒈具有6个染色体的二进制编码、适应度值、Pc累计 值。
数学建模工作室 2020/4/7
i 1
j 1
பைடு நூலகம்
将问 1 ） 题 转 （ 化为m 无 T iX n 约 ,M 束问 (3)题 X E n
其中T(X,M)称为罚函数，M称为罚因子，带M的项称为罚项，这
里的罚函数只对不满足约束条件的点实行惩罚：当XD 时，满
足各g iX 0 ,h iX 0，故罚项=0，不受惩罚．当X D 时，
必g i有X 0 或 h iX 0的约束条件，故罚项>0，要受惩罚．
数学建模培训讲义
第6页 mecca_zj@
遗传算法
关于优化问题
传统的优化方法（局部优化） 共轭梯度法、拟牛顿法、单纯形方法
全局优化方法 漫步法（Random Walk）、模拟退火法、GA
比较：传统的优化方法
1）依赖于初始条件。
2）与求解空间有紧密关系，促使较快地收敛到局部
解，但同时对解域有约束，如可微或连续。利用
构造障碍函数
m
IX,r： IX,rfXrlngiX i1
m
或I(X,r)f(X)r
i1
1
giX
m
m
其中 r 称 lngiX或r
i1
i1
gi1X为障碍 r为 项障 ，碍因子
这样问1题 ）（ 就转化为求一 值系 问列 题极 ：
XmDi0nIX,rk 得X（ k rk）
数学建模工作室 2020/4/7
选择方法——适应度比例法（转轮法） 按各染色体适应度大小比例来决定其被选择数目的多少。 某染色体被选的概率：Pc
Pc f(xi) f(xi)
xi 为种群中第i个染色体，
数学建模工作室 2020/4/7
数学建模培训讲义
第10页 mecca_zj@
具体步骤
1）计算各染色体适应度值
2）累计所有染色体适应度值，记录中间累加值S - mid 和最
• 现在的各种各样的算法都是针对各自特定的适用 范围的，这也是正处在研究发展中的学科领域。
数学建模工作室 2020/4/7
数学建模培训讲义
第3页 mecca_zj@
罚函数法
罚函数法基本思想是通过构造罚函数把 约束问题转化为一系列无约束最优化问题， 进而用无约束最优化方法去求解．这类方法 称为序列无约束最小化方法．简称为SUMT 法．
数学建模培训讲义
第2页 mecca_zj@
评注
• 非线性规划的求解一般要比线性规划的求解困难 的多，不像线性规划那样有适应于一般情况的单 纯形法。
• 我们知道线性规划的可行域一般是个凸集，其最 优解在可行域的边界上达到；而非线性规划问题 的可行域一般不是凸集，最优解也不一定在边界 上达到。
其一为SUMT外点法，其二为SUMT内点法．
数学建模工作室 2020/4/7
数学建模培训讲义
第4页 mecca_zj@
SUTM外点法
对一般的非 mfi线 n X 性规划：
s.t. h gjiX X 0 0
i1,2m ,.;.., ( 1)
j1 ,2,.l...,
m
l
可T 设 X ,M ： fX Mm 0 ,i g in X 2 Mh jX 2 (2 )
（1）
其中 Xx1,x2,,xnT E n，f , gi,hj 是定义在 En 上的实值函数，
简记:
f:E n E 1 , g i:E n E 1 , h j:E n E 1
其它情况: 求目标函数的最大值或约束条件为小于等于零 的情况，都可通过取其相反数化为上述一般形式．
数学建模工作室 2020/4/7
这些约束，收敛快。
3）有些方法，如Davison-Fletcher-Powell直接依赖
于至少一阶导数； 共轭梯度法隐含地依赖于梯度
。 数学建模工作室
2020/4/7
数学建模培训讲义
第7页 mecca_zj@
全局优化方法
1）不依赖于初始条件； 2）不与求解空间有紧密关系，对解域，无可微或连
遗传算法简介
数学建模工作室 2020/4/7
数学建模培训讲义
第1页 mecca_zj@
非线性规划的基本概念
定义 如果目标函数或约束条件中至少有一个是非线性函数 时的最优化问题就叫做非线性规划问题．
一般形式:
mifn X
s.t. h gijX X 0 0
i1,2m ,...;, j1,2,..l..,
续的要求。求 解稳健，但收敛速度慢。能获得全 局最优。适合于求解空间不知的情况
数学建模工作室 2020/4/7
数学建模培训讲义
第8页 mecca_zj@
遗传算法基本原理
模拟自然界优胜劣汰的进化现象，把搜索空间映射为遗传 空间，把可能的解编码成一个向量——染色体，向量的每个 元素称为基因。
数学建模培训讲义
第11页 mecca_zj@
染色体的 适应度和所占的比例
用转轮方法进行选择
数学建模工作室 2020/4/7
数学建模培训讲义
第12页 mecca_zj@
⒉10个染色体种群按比例的选择过程 染色体被选的概率
1 染色体编号 2 3 4 5 6 7 8 9 10
适应度 8 2 17 7 2 12 11 7 3 7
通过不断计算各染色体的适应值，选择最好的染色体，获 得最优解。
遗传算法的基本运算
⑴ 选择运算 ⑵ 交换操作 ⑶ 变异
数学建模工作室 2020/4/7
数学建模培训讲义
第9页 mecca_zj@
●选择运算
——从旧的种群中选择适应度高的染色体，放入匹配集（缓冲 区），为以后染色体交换、变异，产生新的染色体作准备。