《多目标线性规划下的遗传算法毕业论文》由会员分享，可在线阅读，更多相关《多目标线性规划下的遗传算法毕业论文（10页珍藏版）》请在金锄头文库上搜索。
1、多目标线性规划下的遗传算法 摘 要 求解多目标线性规划的基本思想大都是将多目标问题转化为单目标规划，本文介绍了理想点法、线性加权和法、最大最小法、目标规划法，然后给出多目标线性规划的模糊数学解法，最后对每种解法给出例子，并用Matlab软件加以实现。而在多目标遗传算法中加入决策者的决策信息来引导遗传算法的搜索过程的话，这将提高算法的求解效率，减少计算资源消耗，同时也便于决策者从较少的候选方案中作出最终决策。关键词：多目标线性规划；Matlab；模糊数学；遗传算法。Multiple objective linear programming genetic algorithm Abstract:
2、Solving multi objective linear programming the basic ideas are to the multi-objective problem is transformed into a single objective planning, this paper introduces the ideal point method, linear weighted method, the maximum and minimum method, goal programming, and then given the multiple objective
3、 linear programming fuzzy mathematics method, at the end of each method are given examples, and use Matlab software to realization of. In the multi-objective genetic algorithm in decision making information to guide the search process. This will improve the algorithm efficiency, reduce the consumpti
4、on of computational resources, but also to facilitate the decision makers from fewer candidate solutions to make the final decision.Key words: Multiple objective linear programming; Matlab; fuzzy mathematics; genetic algorithm.一引言多目标线性规划是多目标最优化理论的重要组成部分，由于多个目标之间的矛盾性和不可公度性,要求使所有目标均达到最优解是不可能的,因此多目标规划问
5、题往往只是求其有效解(非劣解)。多目标优化问题可以归结为，寻求一组决策变量，使其在满足的约束条件下，同时优化多个目标函数。在求解多目标优化问题中，多目标遗传优化算法显示了强大的优势。目前求解多目标线性规划问题有效解的方法,有理想点法、线性加权和法、最大最小法、目标规划法，然而这些方法对多目标偏好信息的确定、处理等方面的研究工作较少，本文也给出多目标线性规划的模糊数学解法。以便更好地解决遗传算法中所遇到的困难。二多目标线性规划模型 多目标线性规划有着两个和两个以上的目标函数,且目标函数和约束条件全是线性函数,其数学模型表示为： (1)约束条件为： (2)若（1）式中只有一个，则该问题为典型的单目
6、标线性规划。我们记:,，.则上述多目标线性规划可用矩阵形式表示为: 约束条件： （3）三MATLAB优化工具箱常用函数在MATLAB软件中，有几个专门求解最优化问题的函数，如求线性规划问题的linprog、求有约束非线性函数的fmincon、求最大最小化问题的fminimax、求多目标达到问题的fgoalattain等,它们的调用形式分别为：3.1. x,fval=linprog(f,A,b,Aeq,beq,lb,ub)f为目标函数系数,A,b为不等式约束的系数, Aeq,beq为等式约束系数, lb,ub为x的下限和上限, fval求解的x所对应的值。算法原理：单纯形法的改进方法投影法3.2
7、. x,fval =fmincon(fun,x0,A,b,Aeq,beq,lb,ub）fun为目标函数的M函数, x0为初值,A,b为不等式约束的系数, Aeq,beq为等式约束系数, lb,ub为x的下限和上限, fval求解的x所对应的值。算法原理：基于K-T（Kuhn-Tucker）方程解的方法。3.3. x,fval =fminimax(fun,x0,A,b,Aeq,beq,lb,ub)fun为目标函数的M函数, x0为初值,A,b为不等式约束的系数, Aeq,beq为等式约束系数, lb,ub为x的下限和上限, fval求解的x所对应的值。算法原理：序列二次规划法。3.4. x,fv
8、al =fgoalattain(fun,x0,goal,weight,A,b,Aeq,beq,lb,ub)fun为目标函数的M函数, x0为初值,goal变量为目标函数希望达到的向量值, wight 参数指定目标函数间的权重,A,b为不等式约束的系数, Aeq,beq为等式约束系数, lb,ub为x的下限和上限, fval求解的x所对应的值。算法原理：目标达到法。四遗传算法的内容及运算4.1遗传算法的内容众所周知，遗传算法是一类借鉴生物界的进化规律（适者生存，优胜劣汰遗传机制）演化而来的随机化搜索方法。它是由美国的J.Holland教授1975年首先提出，其主要特点是直接对结构对象进行操作，不
9、存在求导和函数连续性的限定；具有内在的隐并行性和更好的全局寻优能力；采用概率化的寻优方法，能自动获取和指导优化的搜索空间，自适应地调整搜索方向，不需要确定的规则。遗传算法的基本运算过程如下： (1)初始化:设置进化代数计数器t=0，设置最大进化代数T，随机生成M个个体作为初始群体P(0)。 (2)个体评价：计算群体P(t)中各个个体的适应度。 (3)选择运算:将选择算子作用于群体。选择的目的是把优化的个体直接遗传到下一代或通过配对交叉产生新的个体再遗传到下一代。选择操作是建立在群体中个体的适应度评估基础上的。 (4)交叉运算；将交叉算子作用于群体。所谓交叉是指把两个父代个体的部分结构加以替换重
10、组而生成新个体的操作。遗传算法中起核心作用的就是交叉算子。 (5)变异运算：将变异算子作用于群体。即是对群体中的个体串的某些基因座上的基因值作变动。 群体P(t)经过选择、交叉、变异运算之后得到下一代群体P(t 1)。 (6)终止条件判断:若t=T,则以进化过程中所得到的具有最大适应度个体作为最优解输出，终止计算。 基于遗传算法有这样的算法过程，我们会发现遗传算法有许多的特点。遗传算法是解决搜索问题的一种通用算法，对于各种通用问题都可以使用。搜索算法的共同特征为： 首先组成一组候选解 依据某些适应性条件测算这些候选解的适应度 根据适应度保留某些候选解，放弃其他候选解 对保留的候选解进行某些操作
11、，生成新的候选解。 在遗传算法中，上述几个特征以一种特殊的方式组合在一起： 4.2 遗传算法的特点基于染色体群的并行搜索，带有猜测性质的选择操作、交换操作和突变操作。这种特殊的组合方式将遗传算法与其它搜索算法区别开来。 遗传算法还具有以下几方面的特点： (1)遗传算法从问题解的串集开始搜索，而不是从单个解开始。这是遗传算法与传统优化算法的极大区别。传统优化算法是从单个初始值迭代求最优解的；容易误入局部最优解。遗传算法从串集开始搜索，覆盖面大，利于全局择优。 (2)许多传统搜索算法都是单点搜索算法，容易陷入局部的最优解。遗传算法同时处理群体中的多个个体，即对搜索空间中的多个解进行评估，减少了陷入
12、局部最优解的风险，同时算法本身易于实现并行化。 (3)遗传算法基本上不用搜索空间的知识或其它辅助信息，而仅用适应度函数值来评估个体，在此基础上进行遗传操作。适应度函数不仅不受连续可微的约束，而且其定义域可以任意设定。这一特点使得遗传算法的应用范围大大扩展。 (4)遗传算法不是采用确定性规则，而是采用概率的变迁规则来指导他的搜索方向。 (5)具有自组织、自适应和自学习性。遗传算法利用进化过程获得的信息自行组织搜索时，适应度大的个体具有较高的生存概率，并获得更适应环境的基因结构。五多目标线性规划的求解方法及MATLAB实现5.1理想点法在(3)中，先求解个单目标问题：，设其最优值为，称为值域中的一
13、个理想点，因为一般很难达到。于是，在期望的某种度量之下，寻求距离最近的作为近似值。一种最直接的方法是最短距离理想点法，构造评价函数，然后极小化，即求解，并将它的最优解作为（3）在这种意义下的“最优解”。例1：利用理想点法求解解：先分别对单目标求解：求解最优解的MATLAB程序为 f=3;-2; A=2,3;2,1; b=18;10; lb=0;0; x,fval=linprog(f,A,b,lb)结果输出为：x = 0.0000 6.0000fval = -12.0000即最优解为12.求解最优解的MATLAB程序为 f=-4;-3; A=2,3;2,1; b=18;10; lb=0;0; x
14、,fval=linprog(f,A,b,lb)结果输出为：x =3.0000 4.0000fval =-24.0000即最优解为24.于是得到理想点：（12，24）.然后求如下模型的最优解MATLAB程序如下： A=2,3;2,1; b=18;10; x0=1;1; lb=0;0; x=fmincon(-3*x(1)+2*x(2)-12)2+(4*x(1)+3*x(2)-24)2)(1/2),x0,A,b,lb,)结果输出为：x = 0.5268 5.6488则对应的目标值分别为,.5.2线性加权和法在具有多个指标的问题中，人们总希望对那些相对重要的指标给予较大的权系数，因而将多目标向量问题转
15、化为所有目标的加权求和的标量问题，基于这个现实，构造如下评价函数，即将它的最优解作为(3)在线性加权和意义下的“最优解”。（为加权因子，其选取的方法很多，有专家打分法、容限法和加权因子分解法等）.例2：对例1进行线性加权和法求解。（权系数分别取，）解：构造如下评价函数，即求如下模型的最优解。MATLAB程序如下： f=-0.5;-2.5; A=2,3;2,1; b=18;10; lb=0;0; x=linprog(f,A,b,lb)结果输出为：x =0.0000 6.0000则对应的目标值分别为,.5.3 最大最小法在决策的时候，采取保守策略是稳妥的，即在最坏的情况下，寻求最好的结果，按照此想法，可以构造如下评价函数，即然后求解： 并将它的最优解作为
