智能优化-模糊规划.ppt

主要内容,一 遗传算法 二 模糊优化 三 随机规划 四 神经网络优化方法 五 退火算法 六 动态规划,智能优化方法,主要参考书目,1、刘宝碇 不确定规划与模糊规划 清华大学出版社 2、方述诚 模糊数学与模糊优化 科学出版社 3、所有智能(软)优化的书 都可以作为参考书，以工科的教材为主,复习 标准线性规划,线性规划是最优化方法中理论完整、方法成熟、应用广泛的一个重要分支 . 标准(矩阵)形式：,非标准线性规划问题：,单纯形解法引入m个松弛变量xn+1 , , xn+m将原问题化成如下标准形式：,普通线性规划其约束条件和目标函数都是确定的，但在一些实际问题中，约束条件可能带有弹性，目标函数可能是不确定的，必须借助模糊集的方法来处理. 模糊线性规划是将约束条件和目标函数模糊化，引入隶属函数，从而导出一个新的线性规划问题，它的最优解称为原问题的模糊最优解.,模糊线性规划,模糊规划的几个相关概念: 1) 模糊集及其隶属度； 2) 隶数度函数的表示；,3) 模糊集合的交与并运算； 4) 模糊集的水平截集；,0. 模糊的概念,天气冷热,雨的大小,风的强弱,人的胖瘦,年龄大小,个子高低,1) 模糊集合和隶属函数 精确集合（非此即彼）： A=x|x6 精确集合的隶属函数(二值函数)：,模糊集合： 如果A是对象x的集合，而x以一定程度属于A：,1,13,精确集合,模糊集合,1,13,6,接近6的数构成的集合,2) 隶属度有离 散的形式和连续形式:,例 令X = R+ 为人类年龄的集合(这是一个精确集合), 而模糊集合 B = “年龄在50岁左右”则表示为:,图示如右:,5)隶属函数参数化,三角形隶属函数,梯形隶属函数,高斯形隶属函数,一般钟形隶属函数,Trig(x;20,60,80),Trap(x;10,20,60,90),g(x;50,20),bell(x:20,4,50),c,c-a,c+a,斜率=-b/2a,隶属函数的参数化(续)：,以钟形函数为例，,a,b,c,的几何意义如图所示.,改变a,b,c,即可改变隶属函数的形状。,支集,核,交叉点,截集,概念:,4) 模糊集合的运算,包含或子集：,并（析取）,交（合取）,补（负）,模糊集合的 交与并集的隶属度,二维的隶属函数可以进行max(OR) 和 min(AND)运算：,梯形Trap(x,-6,-2,2,6)和Trap(y,-6,-2,2,6)的min和 max运算,钟形bell(x,4,3,0)和bell(y,4,3,0)的min和 max运算,22,8) 模糊与概率的差别：,C,A,口极渴的人饮用哪杯液体？,隶属度为何值时最模糊？,6. 线性规划的例子： 例 设某玩具公司生产两种玩具。玩具A是高附加值玩具，每个可以获利0.40美分；玩具B是较低附加值玩具，每个可以获利0.30美分；但是玩具A的生产时间是玩具B的两倍，生产一个玩具B需要一个小时. 该公司每天有生产400具玩具的材料和500个劳动小时, 假设所有的玩具都可以销售出去，试求一个能够获得最大利润的生产计划.,导出的模糊规划的例子：管理者的一个考虑是 1）他可以让工人多加班获取更多的劳动时间； 2）他可以让供应商哪里获取更多的原材料；,因此原线性规划及其模糊规划的目标函数分别为：,设x1和x2分别是A和B种玩具的产量,模型类型: 资源，目标函数，系数等模糊的情况,线性规划 模糊线性规划,结构类型: 分为对称型与不对称型,1.对称优化数学模型 若论域X上的模糊目标集为G，模糊约束集为C，则它们的交集D=GC称为模糊优越集。 对称模糊优化设计的基本思想是，在设计空间中寻求模糊优越集的隶属度取大值的x*，称为模糊最优解: 可以证明: *maxG(x)=0 x C 据此，可以求出X*,例6.2.1.设目标函数为 “x尽可能大于10”， 此目标函数可以用以下的隶属函数表述 约束条件“x应在11附近”则可以 用以下隶属函数表达为,则决策的隶属函数为 容易看出，该表达式的解为， 即是由方程 解出.,设普通线性规划的标准形式为,若约束条件带有弹性，即右端常数bi可能取 (bi di , bi + di ) 内的某一个值，这里的di0，它是决策人根据实际问题选择的伸缩指标.,模糊线性规划的一般对称模型及解法.,把约束条件带有弹性的模糊线性规划记为,这里的ti (x) = bi, di 表示当di = 0(普通约束)时, ti (x) = bi；当di0(模糊约束)时, ti (x) 取(bi - di, bi + di )内的某一个值.,下面将约束条件和目标函数模糊化.,将(2)中带有弹性的约束条件(di0)的隶属函数定义为,而(2)中普通约束条件(di = 0)的隶属函数的定义为 ui (x) = 1, ti (x) = bi .,其图形如右图,由ui (x)定义可知，0, 1,设普通线性规划(1)和(3)的最优值分别为 f0, f1 , 记 d0 = f 0 - f 1 , 则d00, 它为模糊线性规划(2)中目标函数的伸缩指标，d0也可由决策人确定.,定义模糊线性规划(2)中目标函数的隶属函数为,由Gi (x)定义可知，0, 1,Gi (x) t0 (x) + d0 f0,要求模糊线性规划(2)的模糊最优解x*，则要求使所有约束条件及目标函数的隶属函数尽可能达到最大，即求x* 满足 Ai (x)及G(x)， 且使达到最大值,相当于求解普通线性规划问题,i = 1, 2, , m.,设普通线性规划(4)的最优解为x*, , 则模糊线性规划(2)的模糊最优解为x*, 最优值为t0 (x*).,所以，求解模糊线性规划(2)相当于求解普通线性规划(1), (3), (4). 此外，再补充两点说明： 若要使某个模糊约束条件尽可能满足，只需将其伸缩指标降低直至为0； 若模糊线性规划(2)中的目标函数为求最大值，或模糊约束条件为近似大(小)于等于，其相应的隶属函数可类似地写出.,例1 解本例中模糊线性规划问题：,解之得到最优解和最优解的集合：,余下的问题是如何确定S*?,1) Verdegay 的非对称模型:,该隶属函数如下图所示, 并定义a截集为：,ui(x),1,a,bi,bi+pi,不能接受,存在容差,绝对接受,对于任意 ，考虑清晰规划:,设其最优解为 ，对应隶属度为a, 则记最优解集为,按照隶属度的定义具体表达Xa集合