多目标规划问题

3.5黑龙江省可持续农业产业结构优化模型的求解鉴于上面的遗传算法的基本实现技术和理论分析，对标准遗传算法进行适当改进，将其用于求解黑龙江省可持续农业产业结构优化模型中。黑龙江省农业产业结构优化模型具有大系统、多目标、非线性等特点，传统的求解方法受到了模型复杂程度的限制，由引言可知，遗传算法对解决此类问题具有明显的优势。下面介绍具体采用的遗传多目标算法操作设计以及模型求解过程。3.5.1遗传多目标算法操作设计3.5.1.1实数编码方法在求解复杂优化问题时，二进制向量表示结构有时不太方便，并且浮点数编码的遗传算法对变异操作的种群稳定性比二进制编码好（徐前锋，2000）。以浮点数编码的遗传算法也叫实数遗传算法（RealnumberGeneticAlgorithms，简称RGA）。每一个染色体由一个浮点数向量表示，其长度与解向量相同。假如用向量),(21nxxxX表示最优化问题的解，则相应的染色体就是),(21nxxxV，其中n是变量个数。3.5.1.2种群初始化方法遗传算法中初始群体的个体是随机产生的，由于本文优化模型所涉及的变量容易给出一个相对较大的问题空间的变量分布范围，并且若给出一定的搜索空间也会加快遗传算法的收敛速度；因此本文采取3.3.2中的第一种策略，对每一个变量设置可能区间，然后在可能区间内随机产生初始种群。为保证不会遗漏最优解，选择区间跨度范围很大。3.5.1.3适应度函数设计用遗传算法求解多目标优化问题中出现的一个特殊情况就是如何根据多个目标来确定个体的适应值。本文采用Gen和Cheng提出的适应性权重方法（AdaptiveWeightApproach），该方法利用当前种群中一些有用的信息来重新调整权重，从而获得朝向正理想点的搜索压力（玄光男等，2004）。将目标函数按3.3.3所述转化成带有q个目标（本文模型3q）的最大化问题：)}(,),(),({max2211xfzxfzxfzqq（3-14）对于每代中待检查的解来说，在判据空间中定义两个极限点：最大极限点z和最小极限点z如下：},,,{},,,{minmin2min1maxmax2max1qqzzzzzzzz（3-15）其中minmaxkkzz和是当前种群中第k个目标的最大值和最小值。由两个极限点定义的超平行四边形是包含当前所有解的最小超平行四边形。两个极限点每代更新，最大极限点最终将接近正理想点。目标k的适应性权重用下式计算：),,2,1(1minmaxqkzzkkk因此，权重和目标（Weighted-sumObjective）函数由下面的公式确定qkkkkqkkkzzxfxfxz1minmax1)()()(（3-16）3.5.1.4遗传操作（1）选择操作。以比例选择法和最优个体保存法配合使用进行选择操作，即选择过程仍以旋转赌轮来为新的种群选择染色体，适应度越高的染色体被选中的概率越大；另一方面，为了保证遗传算法的全局收敛性，在选择作用后保留当前群体中适应度最高的个体，不参与交叉和变异，同时也确保当前最优个体不被随机进行的遗传操作破坏。（2）交叉操作。本文程序设计采用简单交叉（SimpleXover）、算术交叉（ArithXover）、启发式交叉（HeuristicXover）三种交叉方式并用的方法，在交叉概率选定的条件下，为每种交叉算子设计分配参与该种交叉的染色体的比例，这样可以克服各种方法单独使用的不足，增加了种群的多样性。交叉概率经多次尝试后确定。对所使用的三种交叉算子做解释如下：简单交叉：如果种群中某两个体被选中进行交叉，则随机选取一基因位，在此基因位处进行交叉。例如：若两个体),,,,,(111nkkxxxxX),,,,(112nkkxxxxX被选中，选择第k基因位处交叉，交叉后有),,,,(''111nkkxxxxX),,,,(112nkkxxxxX简单交叉具备较强的破坏性，即染色体交叉后突破临近解空间，可以促进解空间的搜索，而不致过早收敛；但是简单交叉不能对邻近解空间搜索，并且在约束优化过程中，交叉后可能突破解空间到不可行域中，从很大程度上减缓收敛。算术交叉：大体有以下三种类型：凸杂交（convexcrossover）,仿射杂交（affinecrossover）和线性杂交（linearcrossover）,本文程序采用线性杂交。种群中两个体1X，2X被选中进行交叉，交叉后1221222111XXXXXX其中121。经线性杂交后，杂交后代为两个体1X、2X连线上的两个子个体，从而可在临近空间进行搜索，有效弥补简单交叉的不足；然而若解空间为凹区域，则可能杂交后为不可行解，并且有可能收敛到局部最优解，须用简单交叉来弥补不足。启发式交叉：如果种群中两个体1X、2X被选中进行交叉，首先比较两个体1X、2X适应度值，若)()(12XevalXeval，则212'1)(XXXrX，其中)1,0(r，若'1X不在可行域，重复以上步骤直至在可行域为止；2'2XX。启发式交叉可以向最优解或近似最优解快速收敛，并且交叉后两个子个体均在可行域内，这是简单交叉、算术交叉所不具备的优点；并且搜索方向可扩展到两个体1X、2X连线外侧，避免了算术交叉在这方面的不足。然而启发式交叉有可能加速收敛到局部最优解，与其他交叉算子配合使用较好。（3）变异操作。类似于交叉操作，本文程序设计的变异操作也采用多种变异算子并用的方法，分别使用了下面四种变异算子：边界变异（BoundaryMutation）、均匀变异（UnifMutation）、动态（或称非均匀）变异（NonUnifMutation）、多点非均匀变异（MultiNonUnifMutation）参与变异运算，取长补短。对四种变异算子解释如下：边界变异：对于给定的父代X,如果它的元素kx被选中进行变异，则子代LkUkkxxx或，其中Ukx、Lkx通常可取为变量kx的上下界，一般由约束域确定。这样设置变异算子是由于很多优化问题的全局最优解通常存在于可行区域的边界上。边界变异运算的不足是不能变异为解空间内点。均匀变异：若父代X的元素kx被选中进行变异，则后代为),,,('1nkxxxX，其中kkkxrandxx*'，kx为kx的取值范围区间长度；均匀变异可以均匀搜索解空间，弥补边界变异的不足，但其不具备微调功能，变异步长选择比较困难。非均匀变异：若父代X的元素kx被选出作变异，则后代为),,,('1nkxxxX，其中'kx从下面两种可能的方案中随机选择：),('kUkkkxxtxx),('Lkkkkxxtxx函数),(yt返回范围],0[y中的一个值，其中bTtyryt)1(),(，r是]1,0[上的随机数，T是最大遗传代数，b是确定非均匀程度的参数。非均匀变异运算能得到较高的精度并且具备微调能力，即当遗传代数t增加时，),(yt越来越趋向于0，该特性将会使算子在早期均匀沿坐标轴方向搜索解空间，而到晚期则沿坐标轴方向在很小区域进行搜索，弥补了均匀变异的不足。但非均匀变异只是在某一基因位发生变异，从几何上说只是在平行于坐标轴的方向变异，不能实现空间搜索。多点非均匀变异：若父代X的元素kx被选出作变异，则后代为),,,('''1'nkxxxX其中'kx的选择同于非均匀变异，即对于个体的每个基因位都进行非均匀变异；该变异运算不仅具有较高的精度和微调能力，而且可以实现整体空间变异，该特性使算子在早期均匀搜索解空间，而到晚期则在很小区域进行搜索。然而无论是均匀变异，非均匀变异，多点非均匀变异均很难变异至边界，对于约束优化问题，有可能搜索不到边界最优解，故与边界变异共同使用在程序设计中。3.5.1.5约束条件的处理由于用来操作染色体的遗传算子常常产生不可行后代，因此遗传多目标优化中的一个重要问题就是如何处理约束。本文采用Gen和Cheng提出的适应性罚函数（AdaptivePenaltyFunction）方法来处理不可行个体。在当前种群)(tP中给定一个个体x，设多目标优化模型的约束条件为),2,1(,0)(mixgi，其适应性罚函数构造如下：mikiibxbmxp1max))((11)(（3-17）其中，)}(|)(,max{})(,0max{)(maxtPxxbbbxgxbiiiii（3-18）)(xbi是当前染色体对第i个约束的违背值，maxib是当前种群中对约束i的最大违背值，是一个小正数，用来避免罚函数中出现被零除的情况。对于高度约束的最优化问题，每代中不可行解占据相对较大的部分。该罚函数在每代中适应性调整惩罚率，从而既保存了不可行解有用的信息，又对不可行解施加了选择压力，还避免了过度惩罚。综合3.5.1.3和3.5.1.5，确定优化模型的适应度函数为)()()(xpxzxeval（3-19）3.5.2模型求解结果及分析根据遗传算法操作设计3.5.1，采用Matlab6.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中，)(XE单位为亿元，其余单位与前面一致。表3-2可持续农业产业结构优化“最优解”Table.3-2Solvingoptimumlyoftheindustrialstructureofsustainableagriculture变量11X12X13X14X15X16X17X优化值154.6640.00198.56295.048.23812.97228.617变量18X19X110X111X112X113X114X优化值68.48323.07742.29925.94857.50926.35620.179变量115X21X22X23X24X25X3X优化值29.452500320.52898.51212.8299842378.4变量4X)(XE)(X)(XD优化值50.609604.320.0008855.71图3-1黑龙江省农业产业结构模型的pareto解前沿面Fig.3-1SolvingsurfacethatparetotothemodelofHeilongjiang’sagriculturalstructure表3-1黑龙江省可持续农业产业结构优化pareto解Table.3-1ParetosolvesofHeilongjiang’ssustainableagriculturalindustrialstructure序号11X12X13X14X15X16X17X18X19X110X111X112X1151.1529.72198.52296.687.999512.24139.08264.3127.62440.46424.40755.0732153.3829.06199.82295.617.962512.35137.2564.21325.1540.81724.60455.1473151.1529.72198.52296.687.999512.24139.08264.3127.62440.46424.40755.0734153.3629.056199.82295.618.19412.79249.99668.01429.82437.04723.156.106