下载文档原格式
多目标规划问题的几种常用解法(1) 主要目标法其基本思想是：在多目标问题中，根据问题的实际情况，确定一个目标为主要目标，而把其余目标作为次要目标，并且根据经验，选取一定的界限值。
这样就可以把次要目标作为约束来处理，于是就将原来的多目标问题转化为一个在新的约束下的单目标最优化问题。
(2) 线性加权和法其基本思想是：按照多目标f i (x) (i=1, 2, … ,m)的重要程度，分别乘以一组权系数λj (j=1, 2, … ,m)然后相加作为目标函数而构成单目标规划问题。
即 ∑==m j j j x f f 1)(min λ，其中∑==≥mj j j 110λλ且(3) 极大极小法其基本思想是：对于极小化的多目标规划，让其中最大的目标函数值尽可能地小，为此，对每个 x ∈R ，我们先求诸目标函数值f i (x)的最大值，然后再求这些最大值中的最小值。
即构造单目标规划：{})(max min 1x f f j mj ≤≤= (4) 目标达到法（步骤法）对于多目标规划：[])(,),(),(m in 21x f x f x f ms.t g j (x) ≤0 j=1, 2, … ,n先设计与目标函数相应的一组目标值理想化向量),,(**2*1m f f f ，再设γ为一松弛因子标量。
设),,,(21m w w w W =为权值系数向量。
于是多目标规划问题化为：()kj x g m j f w x f j j j j x ,,2,10)(,,2,1min *, =≤=≤-γγγ（5）字典序法对目标的重要性进行排序，依次求解各单目标规划（前一个目标的最优解不唯一，其结果作为下一个目标的约束），到有唯一解时结束。
多目标规划培训教材目录•什么是多目标规划•多目标规划的基本概念•多目标规划的解决方法•多目标规划在实际问题中的应用•多目标规划的案例分析•总结什么是多目标规划多目标规划是指在一个决策问题中同时考虑多个目标或者多个约束条件的一种优化方法。
通常情况下，单目标规划只需要优化一个目标函数，而多目标规划则需要优化多个同时存在的目标函数。
多目标规划非常适用于现实生活中的许多问题，比如企业决策、资源分配、物流运输等等。
因为在这些问题中，往往会涉及到多个冲突的目标或者限制条件。
多目标规划的基本概念在多目标规划中，有几个基本概念需要了解：1. 目标函数：多目标规划中的每个目标都可以表示为一个目标函数。
目标函数通常是需要最小化或最大化的某个指标，比如成本、利润等。
2. 约束条件：多目标规划中，可能存在多个约束条件，这些约束条件是决策问题的限制条件。
3. Pareto最优解：Pareto最优解是指在多目标规划中，无法再进行优化的解。
如果有两个解分别在某个目标上优于另一个解，而在另一个目标上又劣于另一个解，那么这两个解就是Pareto最优解。
4. Pareto前沿：Pareto前沿是指所有Pareto最优解组成的集合。
在Pareto前沿上的解都是没有劣势的，无法通过改进一个目标而不损害其他目标。
多目标规划的解决方法多目标规划的解决方法有多种，常见的有以下几种： 1. 加权和法：将多个目标函数加权求和，通过调整权重来找到最优解。
这种方法适用于目标函数之间不存在明显的权衡关系的情况。
2. 最小优先级法：按照优先级顺序逐个优化目标函数，直到找到满足所有约束条件的最优解。
这种方法适用于目标之间存在明显的优先级关系的情况。
3. 线性权衡法：将多目标规划问题转化为单目标规划问题，通过引入一个权衡参数来权衡多个目标函数。
这种方法适用于目标函数之间存在明显的权衡关系的情况。
4. 模糊规划法：将目标函数和约束条件转化为模糊的形式，通过模糊数学方法来求解多目标规划问题。
多目标规划的原理和多目标规划是一种优化方法，用于解决同时存在多个目标函数的问题。
与单目标规划不同，多目标规划的目标函数不再是单一的优化目标，而是包含多个决策者所关心的目标。
目标函数之间可能存在冲突和矛盾，因此需要找到一个平衡点，使得各个目标都能得到满意的结果。
1.目标函数的建立：多目标规划需要明确各个决策者所关心的目标，并将其转化为数学模型的形式。
目标函数可以是线性的、非线性的，也可以包含约束条件。
2.解集的定义：解集是指满足所有约束条件的解的集合。
在多目标规划中，解集通常是一组解的集合，而不再是单个的最优解。
解集可以是有限的或无限的，可以是离散的或连续的。
3.最优解的确定：多目标规划中的最优解不再是唯一的，而是一组解的集合，称为非劣解集。
非劣解集是指在所有目标函数下都没有其他解比其更好的解。
要确定最优解，需要考虑非劣解集中的解之间的关系，即解集中的解是否有可比性。
4.解的评价：首先需要定义一种评价指标来比较不同解之间的优劣。
常用的方法有加权法、广义距离法、灰色关联法等。
评价指标的选择应该能够反映出决策者对不同目标的重视程度。
5. Pareto最优解：对于一个多目标规划问题，如果存在一组解，使得在任意一个目标函数下都没有其他解比其更好，那么这组解就被称为Pareto最优解。
Pareto最优解是解集中最为重要的解，决策者可以从中选择出最佳的解。
6.决策者的偏好：在实际应用中，决策者对不同目标的偏好有时会发生变化。
因此，多目标规划需要考虑决策者的偏好信息，并根据偏好信息对解集进行调整和筛选。
多目标规划在解决实际问题中具有广泛的应用，尤其在决策支持系统领域发挥了重要作用。
它不仅能够提供一组有竞争力的解供决策者参考，还能够帮助决策者更好地理解问题的本质和各个目标之间的权衡关系。
多目标规划既可以应用于工程、经济、管理等领域的决策问题，也可以用于社会、环境等领域的问题求解。
总之，多目标规划通过将多个目标函数集成为一个数学模型，寻找一组最佳的解集，从而在多个目标之间实现平衡和协调。
疏散路线规划中的多目标优化问题探讨一、疏散路线规划的概念与重要性疏散路线规划是指在紧急情况下，如火灾、地震、袭击等，为确保人员安全、快速地撤离危险区域，而进行的路线设计和优化。
这一规划不仅关系到人员的生命安全，也是城市管理和公共安全的重要组成部分。
有效的疏散路线规划可以显著减少紧急情况下的伤亡和损失。
1.1 疏散路线规划的目标疏散路线规划的主要目标包括：- 最小化疏散时间：确保人员能够在最短的时间内撤离到安全区域。
- 均衡疏散流量：避免某些路线或区域因疏散人数过多而导致拥堵。
- 考虑疏散成本：在满足安全的前提下，尽量降低疏散过程中的资源消耗。
- 应对不确定性：在规划中考虑可能的不确定性因素，如路线损坏、交通管制等。
1.2 疏散路线规划的应用场景疏散路线规划的应用场景广泛，包括但不限于：- 建筑物内部疏散：如商场、学校、办公楼等人员密集场所的紧急疏散。
- 城市区域疏散：在自然灾害或大型活动结束后的城市区域疏散。
- 特殊事件疏散：如大型体育赛事、音乐会等特殊事件结束后的人员疏散。
二、疏散路线规划中的多目标优化问题多目标优化是指在规划过程中同时考虑多个目标，这些目标之间可能存在冲突，需要通过优化算法来平衡。
在疏散路线规划中，多目标优化问题尤为重要。
2.1 多目标优化问题的特点多目标优化问题具有以下特点：- 目标多样性：需要同时考虑疏散时间、疏散流量、疏散成本等多个目标。
- 目标冲突性：不同目标之间可能相互制约，如减少疏散时间可能增加疏散成本。
- 解决方案的多样性：存在多种可能的解决方案，每种方案在不同目标上的优劣不同。
2.2 多目标优化问题的难点疏散路线规划中的多目标优化问题存在以下难点：- 确定权重：如何合理分配不同目标的权重，以反映其在规划中的重要性。
- 解决冲突：如何在不同目标之间找到平衡点，避免过度偏重某一目标。
- 算法选择：选择合适的优化算法，以高效求解多目标优化问题。
2.3 多目标优化问题的解决策略解决疏散路线规划中的多目标优化问题，可以采取以下策略：- 权重法：为不同目标分配权重，将多目标问题转化为单目标问题求解。
第1节多目标规划问题第1节多目标规划问题一、线性规划的局限性第一,线性规划是在一组线性约束条件下,寻求某一项目标(如产量、利润或成本等)的最优值。
而实际问题中往往要考虑多个目标的决策问题。
第二,线性规划最优解存在的前提条件是可行域为非空集,否则,线性规划无解。
然而实际问题中,有时可能出现资源条件满足不了管理目标要求的情况,此时,仅做出无解的结论是没有意义的。
现实中,也有可能各个目标相互矛盾,根本找不出一个全部目标都满足的解,但是在决策时,也必须找出一个满意的解。
第三,线性规划问题中的约束条件是不分主次、同等对待的,是一律要满足的“硬约束”,而在实际问题中,多个目标和多个约束条件并不一定是同等重要的,而是有轻重缓急和主次之分;有近期目标,也有远期目标;有定量的,也有定性的;有互相补充的,也有互相对立的,对这样复杂的决策问题,线性规划方法就无能为力了。
第四,线性规划的最优解可以说是绝对意义的最优,但很多实际情况只需(或只能)找出满意解。
上述原因限制了线性规划的应用范围。
目标规划就是在解决以上问题的研究中应运而生,它能更确切地描述和解决经济管理中的许多实际问题。
二、多目标规划的提出[例4—1]对于例1—1的生产计划问题,问如何安排甲、乙产品的产量,使企业利润为最大?解设生产甲产品的产量为x1,乙产品的产量为x2,该问题的线性规划模型可以表示为: maxZ=3x1+5x2s.t.假设该厂根据市场需求或合同规定,希望尽量扩大产品甲的生产量,减少产品乙的生产,这时又增加了两个目标,则可建立如下的模型:maxZ1=3x1+5x2maxZ2=x1minZ3=x2s.t.容易看出,这是一个具有三个目标的线性规划模型,这些目标之间一般是相互矛盾的。
从上述例子不难得出,多目标线性规划模型的原始一般形式如下:max(min)Z1=c11x1+c12x2+…+c1n x nmax(min)Z2=c21x1+c22x2+…+c2n x n……max(min)Z l=c l1x1+c l2x2+…+c ln x n式中,有n个决策变量,m个约束条件,l个目标函数。
多目标规划问题3.5 黑龙江省可持续农业产业结构优化模型的求解鉴于上面的遗传算法的基本实现技术和理论分析，对标准遗传算法进行适当改进，将其用于求解黑龙江省可持续农业产业结构优化模型中。
黑龙江省农业产业结构优化模型具有大系统、多目标、非线性等特点，传统的求解方法受到了模型复杂程度的限制，由引言可知，遗传算法对解决此类问题具有明显的优势。
下面介绍具体采用的遗传多目标算法操作设计以及模型求解过程。
3.5.1遗传多目标算法操作设计3.5.1.1 实数编码方法在求解复杂优化问题时，二进制向量表示结构有时不太方便，并且浮点数编码的遗传算法对变异操作的种群稳定性比二进制编码好（徐前锋，2000）。
以浮点数编码的遗传算法也叫实数遗传算法（Real number Genetic Algorithms ，简称RGA ）。
每一个染色体由一个浮点数向量表示，其长度与解向量相同。
假如用向量),(21n x x x X 表示最优化问题的解，则相应的染色体就是),(21n x x x V ，其中n 是变量个数。
3.5.1.2 种群初始化方法遗传算法中初始群体的个体是随机产生的，由于本文优化模型所涉及的变量容易给出一个相对较大的问题空间的变量分布范围，并且若给出一定的搜索空间也会加快遗传算法的收敛速度；因此本文采取3.3.2中的第一种策略，对每一个变量设置可能区间，然后在可能区间内随机产生初始种群。
为保证不会遗漏最优解，选择区间跨度范围很大。
3.5.1.3 适应度函数设计用遗传算法求解多目标优化问题中出现的一个特殊情况就是如何根据多个目标来确定个体的适应值。
本文采用Gen 和Cheng 提出的适应性权重方法（Adaptive Weight Approach ），该方法利用当前种群中一些有用的信息来重新调整权重，从而获得朝向正理想点的搜索压力（玄光男等，2004）。
将目标函数按3.3.3所述转化成带有q 个目标（本文模型3 q ）的最大化问题：)}(,),(),({max 2211x f z x f z x f z q q （3-14） 对于每代中待检查的解来说，在判据空间中定义两个极限点：最大极限点z 和最小极限点 z 如下：},,,{},,,{m inm in2m in 1m axm ax 2m ax 1q q z z z zz z z z（3-15）其中m inm ax kk z z 和是当前种群中第k 个目标的最大值和最小值。
由两个极限点定义的超平行四边形是包含当前所有解的最小超平行四边形。
两个极限点每代更新，最大极限点最终将接近正理想点。
目标k 的适应性权重用下式计算：),,2,1(1min max q k z z kkk因此，权重和目标（Weighted-sum Objective ）函数由下面的公式确定qk kkk q k k k z z x f x f x z 1m in m ax 1)()()( （3-16）3.5.1.4 遗传操作（1）选择操作。
以比例选择法和最优个体保存法配合使用进行选择操作，即选择过程仍以旋转赌轮来为新的种群选择染色体，适应度越高的染色体被选中的概率越大；另一方面，为了保证遗传算法的全局收敛性，在选择作用后保留当前群体中适应度最高的个体，不参与交叉和变异，同时也确保当前最优个体不被随机进行的遗传操作破坏。
（2）交叉操作。
本文程序设计采用简单交叉（SimpleXover ）、算术交叉（ArithXover ）、启发式交叉（HeuristicXover ）三种交叉方式并用的方法，在交叉概率选定的条件下，为每种交叉算子设计分配参与该种交叉的染色体的比例，这样可以克服各种方法单独使用的不足，增加了种群的多样性。
交叉概率经多次尝试后确定。
对所使用的三种交叉算子做解释如下：简单交叉：如果种群中某两个体被选中进行交叉，则随机选取一基因位，在此基因位处进行交叉。
例如：若两个体),,,,,(111n k k x x x x X ),,,,(112n k k x x x x X 被选中，选择第k 基因位处交叉，交叉后有),,,,(''111n k k x x x x X),,,,(112n k k x x x x X 简单交叉具备较强的破坏性，即染色体交叉后突破临近解空间，可以促进解空间的搜索，而不致过早收敛；但是简单交叉不能对邻近解空间搜索，并且在约束优化过程中，交叉后可能突破解空间到不可行域中，从很大程度上减缓收敛。
算术交叉：大体有以下三种类型：凸杂交（convex crossover ）,仿射杂交（affine crossover ）和线性杂交（linear crossover ）,本文程序采用线性杂交。
种群中两个体1X ，2X 被选中进行交叉，交叉后1221222111X X X X X X其中121 。
经线性杂交后，杂交后代为两个体1X 、2X 连线上的两个子个体，从而可在临近空间进行搜索，有效弥补简单交叉的不足；然而若解空间为凹区域，则可能杂交后为不可行解，并且有可能收敛到局部最优解，须用简单交叉来弥补不足。
启发式交叉：如果种群中两个体1X 、2X 被选中进行交叉，首先比较两个体1X 、2X 适应度值，若)()(12X eval X eval ，则212'1)(X X X r X ，其中)1,0( r ，若'1X 不在可行域，重复以上步骤直至在可行域为止；2'2X X 。
启发式交叉可以向最优解或近似最优解快速收敛，并且交叉后两个子个体均在可行域内，这是简单交叉、算术交叉所不具备的优点；并且搜索方向可扩展到两个体1X 、2X 连线外侧，避免了算术交叉在这方面的不足。
然而启发式交叉有可能加速收敛到局部最优解，与其他交叉算子配合使用较好。
（3）变异操作。
类似于交叉操作，本文程序设计的变异操作也采用多种变异算子并用的方法，分别使用了下面四种变异算子：边界变异（BoundaryMutation ）、均匀变异（UnifMutation ）、动态（或称非均匀）变异（NonUnifMutation ）、多点非均匀变异（MultiNonUnifMutation ）参与变异运算，取长补短。
对四种变异算子解释如下：边界变异：对于给定的父代X ,如果它的元素k x 被选中进行变异，则子代L k U k k x x x 或 ，其中U k x 、Lk x 通常可取为变量k x 的上下界，一般由约束域确定。
这样设置变异算子是由于很多优化问题的全局最优解通常存在于可行区域的边界上。
边界变异运算的不足是不能变异为解空间内点。
均匀变异：若父代X 的元素k x 被选中进行变异，则后代为),,,('1n k x x x X ，其中k k kx rand x x *'，k x 为k x 的取值范围区间长度；均匀变异可以均匀搜索解空间，弥补边界变异的不足，但其不具备微调功能，变异步长选择比较困难。
非均匀变异：若父代X 的元素k x 被选出作变异，则后代为),,,('1n k x x x X ，其中'k x 从下面两种可能的方案中随机选择：),('k Uk k k x x t x x ),('L k k k k x x t x x函数),(y t 返回范围],0[y 中的一个值，其中b T tyr y t )1(),( ，r 是]1,0[上的随机数，T 是最大遗传代数，b 是确定非均匀程度的参数。
非均匀变异运算能得到较高的精度并且具备微调能力，即当遗传代数t 增加时，),(y t 越来越趋向于0，该特性将会使算子在早期均匀沿坐标轴方向搜索解空间，而到晚期则沿坐标轴方向在很小区域进行搜索，弥补了均匀变异的不足。
但非均匀变异只是在某一基因位发生变异，从几何上说只是在平行于坐标轴的方向变异，不能实现空间搜索。
多点非均匀变异：若父代X 的元素k x 被选出作变异，则后代为),,,('''1'n k x x x X其中'k x 的选择同于非均匀变异，即对于个体的每个基因位都进行非均匀变异；该变异运算不仅具有较高的精度和微调能力，而且可以实现整体空间变异，该特性使算子在早期均匀搜索解空间，而到晚期则在很小区域进行搜索。
然而无论是均匀变异，非均匀变异，多点非均匀变异均很难变异至边界，对于约束优化问题，有可能搜索不到边界最优解，故与边界变异共同使用在程序设计中。
3.5.1.5 约束条件的处理由于用来操作染色体的遗传算子常常产生不可行后代，因此遗传多目标优化中的一个重要问题就是如何处理约束。
本文采用Gen 和Cheng 提出的适应性罚函数（Adaptive Penalty Function ）方法来处理不可行个体。
在当前种群)(t P 中给定一个个体x ，设多目标优化模型的约束条件为),2,1(,0)(m i x g i ，其适应性罚函数构造如下：m i ki i b x b m x p 1m ax ))((11)( （3-17）其中，)}(|)(,max{})(,0max{)(m axt P x x b b b x g x b i i i i i （3-18）)(x b i 是当前染色体对第i 个约束的违背值，m ax i b 是当前种群中对约束i 的最大违背值， 是一个小正数，用来避免罚函数中出现被零除的情况。
对于高度约束的最优化问题，每代中不可行解占据相对较大的部分。
该罚函数在每代中适应性调整惩罚率，从而既保存了不可行解有用的信息，又对不可行解施加了选择压力，还避免了过度惩罚。
综合3.5.1.3和3.5.1.5，确定优化模型的适应度函数为 )()()(x p x z x eval （3-19）3.5.2 模型求解结果及分析根据遗传算法操作设计3.5.1，采用Matlab 6.5对黑龙江省可持续农业产业结构模型编写求解实现程序（见附录），为每个变量设置大略分布范围，种群规模取为60，交叉率0.4，其中单点交叉个体数量4对，算术交叉个体数量6对，启发式交叉个体数量14对；变异率0.3，其中边界变异个体数量为2，均匀变异个体数量为4，非均匀变异个体数量为4，多点非均匀变异个体数量为8。
经多次迭代后得到模型的一系列pareto解（有效解），见表3-1（此处列出50组）；绘出所得解的空间分布，见图3-1。
综合考虑得到的pareto解序列，对各个变量进行全面衡量，对目标函数进行结果分析，并咨询有关专家，选择第29个有效解为整个产业结构优化的“最优解”（注：决策者可根据个人对目标要求从表3-1中选择合适的解）。
见表3-2。
表3-1和3-2中，)E单位为亿元，其余单位与前面一致。
(X表3-2 可持续农业产业结构优化“最优解”图3-1 黑龙江省农业产业结构模型的pareto 解前沿面Fig. 3-1 Solving surface that pareto to the model of Heilongjiang’s agriculturalstructure表3-1 黑龙江省可持续农业产业结构优化pareto 解序号11X 12X 13X 14X 15X 16X 17X 18X 19X 110X 111X 112X精品文档收集于网络，如有侵权请联系管理员删除。
