双目标优化模型

2024-09-15

双目标优化模型（共8篇）

双目标优化模型篇1

引言

过孔是印刷线路板 (也称为印刷电路板) 的重要组成部分, 过孔的加工费用通常占制板费用的30%和40%, 而在制造印刷线路板的流程中, 由打孔机进行打孔作业, 因此, 提高打孔机的生产效能是降低印刷线路板成本的主要途径之一, 所以研究打孔机路径优化问题就显得尤为重要。

本文首次采用不等式的方法[1,2,3]解决双钻头打孔机优先级问题及采用剥离和虚设过孔的思想解决一个过孔多次被钻的问题, 并设计嵌入优先级的遗传算法[4,5]来解决多目标的0-1规划模型。最后借用2012年“深圳杯”数学建模夏令营竞赛D题中的数据[6]进行实验, 并对实验结果进行分析。

一、建模准备

1.1 虚设过孔

由于同一线路板上的过孔不要求加工完毕后, 再加工下一个过孔, 故, 钻头每次钻孔是独立的。基于此, 可将需多个刀片加工的过孔剥离。若某过孔需要n种刀片加工, 那么对于该过孔, 再虚设n-1倍过孔。由题目的表一[6]可知, C、E、F、G、I、J都需要多种刀片加工, 分别对其虚设过孔;那么10种过孔表示为:Aa、Bb、Ca、Cc、Ec、Ef、Fg、Fh、Gd、Gg、Gf、Hh、Ie、Ic、Jf、Jc (Aa表示用a刀片加工的A种过孔) 。

1.2 几个定义

定义1设t'为钻头1打孔总时间, t"为钻头2打孔总时间, JT为钻头工作时间均衡度, 则有:

定义2设c'为钻头1打孔总成本, c"为钻头2打孔总成本, JC为钻头工作成本均衡度, 则有:

定义3设t'为钻头1打孔总时间, t"为钻头2打孔总时间, t为钻头工作时间跨度, 则有:

定义4设dij为i与j两点之间的距离, yki为钻头k是否钻过i孔, Dij为两钻头合作间距, 则有:

说明:其中, Tij为i过孔到j过孔的时间, xkij表示钻头k是否经过i孔到j孔, xkij∈{0, 1}, yki∈ (0, 1) 。

二、多钻头最佳作业线路的0-1规划模型

2.1 基于多目标优化的多钻头最佳作业线路模型

决策变量

目标函数

目标一:双钻头同时进行打孔作业, 当打孔时间用时最长的钻头完工时, 一块线路板才算加工完毕, 故追求打完一块线路板的时间跨度越短, 即:

目标二:每个钻头都有自己的作业成本, 当加工完一块线路板, 钻头所花的总作业成本尽量少则最优, 即:

其中, Qij为i过孔到j过孔的成本.。

目标三:两钻头工作时, 每个钻头都有自己的作业时间, 需保证两钻头的作业时间均衡, 即:

目标四:两钻头工作时, 每个钻头都有自己的作业成本, 需保证两钻头的作业成本均衡, 即:

约束条件

(1) 钻头数目约束:

起点过孔数目等于钻头总数, 其他过孔点的钻头数为0, 即:

其中, 线路板上的所有过孔编号集合为U, 两钻头开始打孔位置编号为集合D, CDU为除去钻头起始点的其他孔点编号集合, m为钻头总数。

(2) 平衡约束

任意一个终端过孔j仅有一条线路与起点i过孔相连, 且只被一个钻头经过, 即:

任意一个起点过孔i仅有一条线路与终点过孔j相连, 且只被一个钻头经过, 即:

所有过孔需被两钻头打完, 即:

其中, L为总的过孔数。

(3) 优先级约束

C种孔型用c刀片加工前, 必须经过a刀片加工;经过a刀片加工前, 不一定被c刀片加工, 且C种孔型可被一个钻头加工, 也可被两个钻头加工, 即:

其中, j为C种孔型的编号, n1为C种孔型的个数, k, h为两钻头编号, k, h∈{1, 2}。

同理, 可用同样的方法可以得到E、G、I、J种孔型的优先级模型。

(4) 每个钻头, 除起点与终点外, 各边不构成圈, 即:

(5) 钻头合作距离约束:

两钻头的合作距离至少大于a, 即:

其中, a为两钻头的最小合作距离.

综上所述, 双钻头最优线路2TSP模型为:

说明:其中n2、n3、n4、n5分别为E、G、I、J种孔型的个数。

2.2 多目标转化成单目标

(1) 数据处理:由于JT远小于t, JC远小于WC, 为防止大数吃小数, 将大小数相乘再加上大数, 得到如下式子, 即:

其中, JT与JC为钻头工作时间与成本的均衡度, WC为所有钻头的总成本的, t为两钻头行进最大时间。

(2) 转换为单目标:经过数据的处理, 将两目标相乘化为单目标, 即:

其中, Z=TW。

三、基于改进的遗传算法实验结果

首先将2TSP模型转换为TSP模型[7], 然后根据公式 (17) 和 (19) 的双钻头打孔机打孔路径优化模型, 借用2012年“深圳杯”数学建模夏令营竞赛D题附件中的数据, 研究双钻头打孔机打孔优化线路的问题。可知m=2、n1=270、n2=93、n3=20、n4=10、n5=29、a=30mil、L=2814。为找到打孔机最优线路, 本文主要采用嵌入优先级的遗传算法, 运用Matlab.10编程, 求出作业成本和作业时间以及最优作业线路。

(1) 双钻头最优作业线路图

运用Matlab 10.0编程得到下面两钻头的最优路线图, 见图1:

分析图1:图中不同颜色的线代表两个不同的钻头的行进路径, 明显地, 两种颜色的路径差不多, 意味着钻头的作业时间均衡。

(2) 刀具转换方案

根据上图的最优路线, 结合已知的刀片加工顺序原则, 可以确定过点的刀具转换方案, 由于数据量过大, 在此只给出两个钻头前10个点的刀片转换方案, 见表1、表2。

分析:根据表1、2, 可以直观的看出两个钻头在各个过孔间刀片的转换方案, 以此可以给出所有过点的刀片转换方案, 并得到总行进时间385.20秒、总作业成本701.67元。

四、结束语

本文将图论中的多旅行商问题的数学模型成功的应用于双钻头打孔机打孔中, 优化了打孔机运动的距离。减少了加工时间和打孔机总的成本。经过实际应用表明, 该模型满足实际要求, 提高了双钻头打孔机的工作效能。

参考文献

[1]姜启源.数学模型[M] (第三版) .北京:高等教育出版社, 2003.

[2]《运筹学》教材编写组.运筹学[M].北京:清华大学出版社, 2003.

[3]钱颂迪.运筹学[M].北京:清华大学出版社, 2003.

[4]王海龙, 等.基于遗传算法的多旅行商问题研究[J].计算机应用研究, 2009, 26 (5) .

[5]周辉仁, 等.基于递阶遗传算法的多旅行商问题优化[J].计算机应用研究, 2009, 26 (10) .

[6]2012年深圳杯数学建模夏令营竞赛赛题[EB/OL].http://www.sznews.com/zhuanti/node_112146.htm, 2012.10.27.

[7]余庆生, 等.多旅行商问题研究综述[J].价值工程, 2012, 03.

双目标优化模型篇2

关键词：汽车结构安全多目标优化代理模型智能布点信赖域

Multi-Objective Optimization Method Based on Metamodel for Vehicle Structural Safety

Han Xu Jiang Chao Chen Guodong Long Xiangyun

（Hunan University）

Abstract：Most vehicle structural safety optimization problems involve multiple objectives， which cannot be expressed explicitly but acquired by complex computational model， and thus it increases the difficulty of solving multi-objective optimization problems. Intelligent optimization method is able to search for multiple optimal solutions in one single simulation run， but the low efficiency limits its application to complex vehicle structural crash problems. Common multi-objective optimization methods based on metamodel can well deal with the low efficiency and become a research focus， but the solution accuracy is usually low. Therefore， this project studies the multi-objective optimization methods based on metamodel， aims to improve the efficiency and accuracy in the design of vehicle crash safety. A new multi-objective optimization algorithm is proposed based on adaptive radial basis function. This method effectively assesses metamodel by using inherit Latin hypercube design， radial basis function and intergeneration projection genetic algorithm. The proposed method is applied to the thin-walled sections for structural crashworthiness， which is beneficial to quickly find multi-group design schemes and can well balance energy absorption and collision force. A micro multi-objective genetic algorithm based on intelligent sampling technology is put forward. The algorithm adopts the extented radial basis function to build a global metamodel， and then employs the efficient micro multi-objective genetic algorithm for approximate optimization. The method has been used in the dynamic characteristic optimization of a heavy commercial vehicle cab and obtains many optimal design schemes. Optimization algorithm based on trust region model management is proposed to solve the multi-objective optimization problem in complex engineering. The method transforms the complex optimization problems in the entire design space into a series of approximation problems in trust region. The method has been applied in a door structure optimization， and well balances the static and dynamic performance by matching the thickness of key components. Based on trust region and intelligent sampling technology， an efficient multi-objective method is developed. The method has been successfully used in the lightweight design of car body based on crashworthiness and modal characteristics， and demonstrates its ability to solve multi-objective optimization problems in vehicle structural safety.

Key Words：Vehicle structural safety； Multi-objective optimization； Metamodel； Intelligent sampling； Trust region

改进的双模型的运动目标检测方法篇3

运动目标检测已经成为一个热门的课题,检测过程中时常会出现运动场景中光线变化、背景突变和运动目标产生的阴影等难题,到目前为止国内外研究人员已经提出了一些方法来解决这些问题[9,10,11,12,13]。当前目标检测的方法大致分为三种:光流法[9,10]、帧差法[11]和背景相减法[12,13]。光流法是通过利用输入图片的光流场来检测运动物体的,既适应于静态背景的目标检测,也适用于动态背景的目标检测。但这种方法计算量大,抗噪能力差,对于光照变化比较敏感。帧差法利用前后两幅图像的差值来检测判断出运动的目标,然而该方法不能检测速度过慢的物体,检测出的物体内部会容易造成空洞。由于背景相减法具有灵活性和有效性等的优点,它已经日益受到研究人员的关注。背景相减法首先建立一个无运动物体的背景模型,通过计算当前帧和模型的差异来检测运动物体。Maddalena等人[14]提出了基于人工神经网络的自组织背景减法模型(self organizing bachground subtraction,SOBS),该算法对光线的变化和遮挡有较强的鲁棒性,然而运算代价比较大。Barnich等人[15]提出了基于像素的非参数化随机样本模型(visual background extractor,Vi Be),该方法运算简单,静态场景下有很好的检测效果,但是其阈值固定,限制了算法对于动态背景(例如晃动的树叶、闪烁的灯光等)的自适应能力。Hofmann等人[16]提出了基于像素的自适应分割(pixel-based adaptive segmenter,PBAS),但是该算法对缓慢的光照变化具有较强的鲁棒性,而在背景动态区域检测目标精度较低。Baocai Yin等人[17]提出基于双模型的背景分割算法,该算法对于运动物体容易造成检测的目标缺失,检测会出现鬼影[18]现象。

由于双模型算法存在检测过程中运动目标检测不全、前景误检率高和出现鬼影等现象,本文提出一种适用于动态背景下改进的双模型目标检测算法。首先对前、背景的判断条件进行改进,用新一帧图像像素点像素值和背景模型对应位置样本值之间的距离和阈值比较,使前景更全面地被检测出来;通过对自适应决策阈值更新方式的改变,把邻域模型和自模型结合作为阈值增加或减少的条件,使得检测结果更精确,抗噪性能增强;本文结合帧间差分技术,通过比较对应位置像素值的时域变化来判断鬼影像素,以达到快速消除鬼影的目的。

1 双模型背景建模算法

双模型[17]算法由自模型和邻域模型两种模型构成,用来实现对背景提取和运动目标的提取。它是一种基于样本随机聚类的背景建模算法,其核心思想是:背景样本用两种相关联的模型来描述,分别称为自模型和邻域模型。自模型表示背景样本中在相同位置处的像素值;邻域模型表示背景样本中像素点周围邻域位置的像素值。该算法以新一帧中像素点像素值与样本中任意点像素值的距离作为判断前景背景条件,以背景特征为基础来改变阈值大小,用新来像素点依据更新条件随机代替样本中任意点,实现对视频序列的目标检测。

1.1 自模型和邻域模型

对于某个视频序列,前N1帧图片在位置点xi处的像素值I(xi)组成一个样本集合如式(1)所示。

该集合BS(xi)称为自模型;前N1帧图片在位置点xi邻域{y1,y2,…,yN2}处的像素值I(yj)组成一个样本集合如式(2)所示。

该集合BN(xi)称为邻域模型,此处N2表示在位置点xi处邻域中像素点的个数。

1.2 前景背景检测

前景检测的目的是从视频序列中将变化的目标从背景图像中提取出来,运动前景的有效检测在目标跟踪、目标分类、行为理解等后期处理至关重要。双模型检测算法中,运用视频序列中新一帧图片与背景模型的差异来区分前景和背景。前景和背景像素的判断方式如下:①当样本集合中若满足当前像素值I(xi)与背景模型中自模型样本值BSk(xi)(BSk(xi)是自模型BS(xi)中第k个样本)的距离小于给定的阈值R(xi)的条件的个数大于等于Smin时,则前景分割掩模F(xi)记为0表示背景;②若满足当前像素值I(xi)与背景模型中自模型样本值BSk(xi)的距离小于给定的阈值R(xi)+r的条件的个数大于等于Smin,则前景分割掩模F(xi)记为0表示背景;③若满足当前像素值I(xi)与背景模型中邻域模型样本值BNm(xi)(BNm(xi)是邻域模型BN(xi)中第m个样本)的距离小于给定的阈值R(xi)的条件的个数大于等于Nmin,则前景分割掩模F(xi)记为0表示背景;④不满足以上三种情况的将前景分割掩模F(xi)记为1则为前景。用公式(3)表示如下:

式(3)中Smin和Nmin是固定参数,取值大小分别取决于N1和N2的大小。当N1和N2增加或者减少时,Smin和Nmin也要对应地增加或减少。Smin和Nmin值过小时会使背景点增加;Smin和Nmin过大时前景点增多,算法抗噪能力减弱;“#”表示满足条件的总个数,用F1、F2、F3分别表示公式(3)中前三种情况的结果。式(3)中计算当前位置点xi像素值与背景模型样本值的距离如公式(4)所示:

在双模型检测过程中,R(xi)通常是一个低值,可能会导致错误的检测。然而,设置阈值R(xi)+r能够避免场景突然改变而引起的错误检测,所以当F1=0、F1≠0且F2=0时,当前像素被判断为静态背景像素;动态场景的像素值不是固定的,然而动态场景像素点的变化通常能够通过邻域像素点的变化来体现。因此,利用根据这种特征,当F2≠0且F3=0时,当前像素被判断为动态背景像素,判断过程如图1所示。

1.3 背景模型的更新

通常情况下检测到的前景区域不需要更新,背景模型只需要更新那些当前被判断为背景的像素点,然而双模型并不是所有的被检测为背景的像素点都要更新。更新原则如下:①当F1=0时,背景模型不需要更新;②当F1≠0和F2=0时,随机均匀选择k∈1,2,…,N1,自模型BSk(xi)中任意像素点被当前像素点I(xi)替换,邻域模型的邻域中任意像素点BN(yi)也被当前像素点I(xi)替换;③当F2≠0和F3=0时,从自模型BS(xi)中随机选取一个样本用I(xi)来代替,此时邻域模型不需要更新。

1.4 阈值更新

因为背景的复杂性和多样性,因而所有像素点对应的阈值并不是固定不变的。双模型的决策阈值更新方式如公式(5)所示。

式(5)中dr和ir是固定参数,由公式(5)可以看出阈值R(xi)的更新取决于前景的判断情况。

2 EMD运动目标检测算法

双模型背景建模运用到目标检测领域中实时性高,取得了较好的运动目标检测效果,但是也存在一些不足:①在前后帧运动目标运动幅度不明显时,容易产生检测缺漏不完整;②在动态场景下,双模型误检率比较大,产生的噪声比较大;③若在背景模型前N1帧中出现静止的运动目标,会产生出现鬼影的区域如图2(b)所示,并且后续运动目标出现在该鬼影区域会导致检测不完整,从而影响后面的运动目标检测。双模型的英文是dual model,文中简称为DM,本文改进的算法简称EDM(enhanced dual model),下面就以上三点不足进行改进。

2.1 EDM的前景背景检测方式

把模型中像素点样本值与当前帧对应位置像素点的像素值的距离作为前景背景判断依据,当前后帧变化不明显时,容易使得检测的目标缺漏丢失。为全面地检测出前景目标,判断前景背景的过程如公式(6)所示:

F1、F2、F3、F4分别表示公式(6)中前四种情况的结果。

为减少前景目标缺漏丢失的情况,模型中像素点样本值与当前帧像素点的像素值的距离反映了与背景样本的差异性,式(6)中采用平方的方式使得前后帧变化的差异更大,可以有效地弥补DM模型中前景检测缺漏的缺点;式(6)中相比DM模型多加的第四种情况并不是多余的,当F2≠0且F3=0时被判断为具有明显变化的动态背景,当F3≠0且F4=0时被判断为微小变化的动态背景,能够将背景区分得更明显,并且在自适应阈值更新中也会运用到。

2.2 EDM的自适应决策阈值更新

判断前景和背景是依据每个像素点对应的决策阈值R(xi),双模型中决策阈值的更新仅仅与自模型相关,和邻域模型的变化无关,容易对检测产生误检,检测精度比较低。

对于每个像素点,必须有一个合适的决策阈值来正确地检测出结果。合适的决策阈值不能太高,太高会将前景检测为背景;同时,阈值也不能太低,太低可能将背景像素检测为前景。根据式(6)可知,决策阈值在自模型和邻域模型中都相当重要。因此,根据前景背景判断式(6)提出改进DM模型的自适应决策阈值,决策阈值R(xi)的更新方式如公式(7)所示:

式(7)中设定S(xi)在每个像素点位置上为固定值,此阈值更新方式把自模型和邻域模型紧密结合。根据改进的阈值更新方式(7),自模型中当决策阈值能正确地检测到动态背景像素时,R(xi)在下一帧中就会变低;当阈值R(xi)低于合适值时,F1将会变成1但是F2仍然是0,此时R(xi)在下一帧增加,增加的幅度大于DM中阈值增加的幅度;在邻域模型中当F1≠0且F2≠0且F4=0时,此时F3的值是不能确定的,但始终是动态背景,决策阈值R(xi)不断地减少,当R(xi)的值满足F2=0时,在自模型中继续更新阈值。

2.3 DM鬼影的去除

DM模型阈值的更新方法无法快速地消除鬼影,鬼影是与实际运动目标不对应的前景区域,当背景模型中存在运动目标或者运动目标的状态转变会产生鬼影。为了更快地消除鬼影,总体思想是:如果某个检测区域检测的结果是前景区域,但是该区域在较长时间内一直是前景,则判断该区域为鬼影,应把该区域判断为背景,从而消除鬼影。算法详细步骤如下:为每一个像素设置一个计数变量T(xi),初始化为0,当像素xi被检测为前景像素时,用当前帧的像素值与前一帧该对应位置像素值作差,如果差值结果小于设定的差异阈值Tmax,则该像素的T(xi)加1,否则T(xi)为0。该算法用公式(8)表示如下:

式(8)中m(xi)表示像素点xi是否为前景像素,它的值为1时则表示为前景像素,为0时表示为背景像素;n(xi)表示相邻两帧在同一位置像素点对应的差值与阈值Tmax的比较情况,n(xi)=0表示差值小于等于阈值Tmax,n(xi)=1表示差值大于阈值;当T(xi)大于设定阈值Mmax时,把对应的像素更新到背景中,该方法对于去除长时间内像素点没有变化的前景像素更有效率。

接下来以某个视频为例描述鬼影的产生与消除。此处采用的视频序列是交通路口的监控图像,其中运动目标的特点是:原来静止的人突然骑自行车。实验输入的图片序列是交通路口的监控图像,从序列的第1008帧开始原先静止的人开始骑自行车,在原来静止的地方产生了鬼影,图2(a)、图2(b)、图2(c)分别是目标从静止到骑自行车一段时间后、DM模型检测效果、EDM模型算法消除鬼影的效果。从图中可以看出,由于目标突然改变运动状态,DM模型的检测产生了鬼影,而本文结合帧间差分EMD算法可以消除鬼影区域,从而具有更为准确的检测结果。

3 实验结果及分析

3.1 EDM的前景判断和阈值更新方法的目标检测实验

实验是在软件环境MATLAB平台下完成的,硬件环境处理器为AMD A6,4 G RAM。算法中所涉及的参数设置如下:N1=25,N2=8,Smin=2,Nmin=1,R0=30,r=15,ir=0.08,dr=0.02,S(xi)=0.05,Tmax=50,Mmax=40,文中k取值范围是[1,25],m的取值范围是[1,8]。

本文选取changedetection数据集[19]中的三个动态背景测试序列(canoe,overpass,fountain02)对动态背景进行鲁棒性的测试。图3是DM模型和EDM模型算法的效果对比图,图3(a)是原输入序列canoe中第957帧图像;图3(b)是该帧图像的真实前景,图3(c)是DM模型算法检测出来的效果图,从图中可以看出DM模型检测图中会有缺漏,船的整体没有被检测出来,图3(d)改进后EDM算法的检测结果,从效果图可以看出双模型由于前、背景判断条件不够完善,导致检测目标结果不完整,本文算法通过用新来像素点图像值与背景模型样本值之间的距离和阈值进行比较的改进方法则较完整地检测出运动目标。图3(e)是overpass图片序列中第2 366帧图像,图3(f)是该图片的真实前景,图3(g)是DM模型检测的结果,该算法不能完全消除动态背景晃动的树叶,人的身体部分也没有完整地被检测出来,通过对前景背景的判断情况把自模型和邻域模型结合起来,作为阈值增加减少的条件,能有效地消除动态背景的干扰,图3(h)是改进算法EDM的检测效果。图3(i)是fountain02图片序列中第743帧图像;图3(j)是该图片的真实前景,图3(k)是DM模型检测的结果,图中可以看出检测出的结果不全,图3(l)是EDM检测的结果。从图中可以看出,EDM算法检测到的运动目标像素更多,并且运动目标更加清晰和完整。

3.2 本文算法的定量分析

为了使本文改进的算法EDM更有说服力,在此采用正确分类百分比函数(PCC)来测试二值分类的性能,根据文献[20]该函数在图像处理领域应用比较广泛,如公式(9)

所示:

式(9)中TP是正确检测为前景像素点的个数;TN是正确检测为背景像素点的个数;FP是被错误检测为前景像素点的背景像素点个数;FN是被错误检测为背景像素点的前景像素点个数。选取上面实验中动态背景canoe、fountain02和overpass视频序列进行PCC统计,最终的数据如表1所示,可见本文DEM算法在正确分类百分比上比DM模型有较大提高。

4 结论

本文针对DM背景建模存在前景检测缺漏、误检和出现鬼影的问题进行改进。首先,使用改进的前景背景判断方式,用新像素点图像值与背景模型样本值之间的距离值和阈值进行比较,在动态背景下更能全面地检测出前景;其次,改进自适应阈值的更新方式,将阈值的更新与自模型和邻域模型紧密结合,不单单是根据自模型来改变阈值,通过把自模型和邻域模型对前景背景的判断结果作为阈值改变的依据,能更精确地进行检测;最后,本文结合帧间差分技术通过比较对应位置像素值的时域变化来判断鬼影像素,以达到快速消除鬼影的目的,有效地去除了鬼影带来的干扰,使检测结果更准确。实验结果表明,本文的EDM算法在动态背景下对目标检测有很强的适应性和鲁棒性。

摘要：在动态背景下,由于双模型算法对运动目标检测时会出现误检、目标检测不完整和出现鬼影的现象,提出一种改进的双模型的运动目标检测算法。该算法首先对双模型背景的判断方式改进,将新来像素点图像值与背景模型对应位置样本值之间的距离和阈值进行比较,可以全面地区分前景和背景。然后对自适应阈值更新方式改进,通过对前景背景的判断情况把自模型和邻域模型结合起来,作为阈值增加或减少的条件,能够更精确地检测出前景。最后,结合帧间差分技术,通过比较对应位置像素值的时域变化来判断鬼影像素,以达到快速消除鬼影的目的。实验结果表明,改进算法的检测结果比原来的双模型更加精确、全面。

双目标优化模型篇4

虽然近年来航空器制造技术的不断进步已使得航空器安全技术状况得到较大改善,但由于驾驶员人为操纵、航空器自身机械故障、恶劣天气等原因,航空器事故仍难以避免[1]。特别是,近年来直升机失事事故呈上升趋势,直接威胁到人民生命财产安全,并产生严重的经济、政治负面影响。为积极应对上述各种紧急态势,避免森林火灾等次生灾害的发生,国家有关部门制定了相应的搜寻救援预案,其中锁定直升机失事位置后的应急救援是搜救工作的重要内容,而应急救援路线的选择问题是确保这一工作顺利进行的前提[2]。国内外学者已对此开展了相关研究,并提出一系列基于网络理论的模型与算法[3,4,5]。一方面,这些研究大多是针对火灾、毒气泄漏等灾害进行的,很少有文献考虑直升机失事应急救援路线的选择优化问题。另一方面,现有研究大多将时间花费作为最重要的参数,优化目标是使物流传输过程所需时间实现最小化。然而,在实际应用中,应急救援路线的选择往往还涉及除时间以外的其他复杂因素,如安全性、经济性以及道路线的复杂性等,因此属于多目标优化问题[6]。部分文献[5]虽然考虑了应急救援路线的多目标优化问题,但在求解模型的算法时多是通过线性加权的方法,将路线选择的多目标优化问题转化为单目标优化问题,并假定不同优化目标的权重为常数,而在实际的应急物流路线选择问题中,不同优化目标的权重并不是一个常数,而是区间数[7]。

针对上述问题,笔者将对直升机失事应急救援路线的优化问题进行研究,基于运筹学的理论和方法建立路径选择的双目标优化数学模型,并设计出适合模型的算法,以期为决策者选择最佳应急救援路线提供依据。

1 问题描述与模型建立

从图论角度来看,地面错综复杂的道路实际上是一个连接的网络图,道路为图的边,道路之间的交点抽象成图的点的集合,组成网络图的顶点,应急救援物资支持保障中心所在地抽象为网络图的源结点,直升机失事地所在地抽象为网络图的目标结点。在无向网络图上赋予应急救援路线选择的影响因素,可把整个道路网络布局转化为图的拓扑优化问题。为便于表述,在此给出如下变量及名词定义:

1) 设应急交通网络G ( V,E) ,其中,V = { v1,v2,…,vn} 为有限节点集,E为有限弧集合,E V × V,v1,v2,…,vn表示网络中的各个节点,v1为源节点,代表参与应急救援行动的人员的初始位置,vn为目标节点,代表需要到达的目标位置。

2) lij,Lij和tij分别表示节点vi,vj之间的弧的实际长度、当量长度和通行时间,( vi,vj) E。

3) uijWTBZ|0 表示正常情况下人员或车辆在弧( vi,vj) 上的通行速度。ηtij为取决于弧( vi,vj) 中交通工具的影响系数; ηvij为取决于风速的影响系数; ηsij为取决于道路积水的影响系数; ρijm为弧( vi,vj) 上第m个局部通行障碍物的当量长度系数,1 ≤ m ≤nijm; nijm为弧( vi,vj) 中局部通行障碍物的个数; ηrij为取决于直升机失事引发的次生灾害的危险系数。

4) P表示v1→vn的一条有效路径,P为网络中结点的有序序列,P*表示v1→vn的一条最佳救援路径。

在求解最佳救援路线时,综合考虑路段本身和因直升飞机失事可能引发的次生灾害( 如森林火灾) 的影响,将对人类行走速度较大的影响因素用一个危险系数表示,计算各路段的当量长度:

在前述变量和名词定义的基础上,以通过路径所需的总行进时间最短为主要优化目标,表征道路安全性的“当量长度”为次要优化目标,建立直升机失事应急救援路线选择的双目标优化数学模型( 模型Ⅰ) :

式中: ft( P) 为路线P的总通行时间; fL( P) 为路线P的当量长度; xij为决策变量,i,j{ 1,2,…,n} ,xij= 0,1;xij= 1 表示弧( vi,vj) 在选定的路线P上; xij= 0 表示弧( vi,vj) 不在选定的路线P上。式( 7) 表示路线P安全可行的判定条件,Lt为安全通行的最低可承受值,由应急决策者根据直升机失事引发的次生灾害的类型及人体的脆弱性确定[9]。

2 模型的求解算法

2. 1 模型转化与求解

首先,利用理想点法[5]处理上述双目标优化模型,将其转化为单目标优化模型( 模型Ⅱ) :

式( 4) ~ ( 7) 中:为理性点,为权重向量。

根据理想点法定理可知,模型Ⅱ的最优解是模型Ⅰ的一个有效解[8]。当权重向量r珒变化时,可以得到模型Ⅰ一系列有效解,决策者据此可选择符合需要的有效解,即本文所求的直升机失事最佳救援路线P*。然而对于决策者而言,权重向量的确定是一件很困难的事情。为了解决这一问题,本文设计如图1 所示的算法流程。

2. 2 算法可行性证明

首先根据引入的权重向量,为应急交通网络G ( V,E) 的弧( vi,vj) 构建一个新的路权参数wij= r1tij/ ft( P)*+ ( 1 - r1) Lij/ fL( P)*,令Pr1表示对应于权重向量的模型Ⅱ的最优解,根据公式( 2) 和公式( 3) ,,即。作为图论的经典问题,最短路径问题的定义是在一个赋权图的两个顶点之间找出一条具有最小权值的路径[5]。而根据上述分析可知,求解模型Ⅱ的最优解实际上就是寻找应急交通网络G ( V,E) 中关于路权参数wij的最短路。因此图1 所示的算法中求解模型Ⅱ的最优解可通过传统的最短路算法实现。

然后,根据公式( 8) 构建2 个辅助函数: ft( r1) = ft( Pr1) ,fL( r1) = fL( Pr1) ,结合笔者已有的研究成果[10],容易得到下述辅助函数的性质:

性质1若r1= ( α - β) /3,其中[α,β][0,1 ],那么:

①若fL( r1) < Lt,则ft( Pζ) ≥ T( Pr1) 且fL( Pζ) <Lt,ζ[α,r1]。

②若fL( r1) > Lt,则ft( Pζ) ≤T( Pr1) 且fL( Pζ) >Lt,ζ[r1,β]。

③若fL( r1) = Lt,则P*= Pr1。

根据性质1 可知,如果模型Ⅰ有最优解,那么对于图1 所示算法流程图中的任意一个搜索区间[α,β]( 初始时[α,β] =[0,1]) ,可以通过选择试探点r1= ( α -β) /3,并调用传统最短路算法求解模型 Ⅱ 的最优解Pr1,若fL( r1) ≠ Lt,根据性质1 的结论①、②可知,可以将搜索区间缩小1 /3 或2 /3,那么通过反复迭代及试探性搜索,都可以得到求解最佳救援路线P*的一个更小的搜索区间,直至得到满足fL( r1) = Lt或循环终止条件NC > NCmax的路径Pr1,那么P*= Pλ。综上所述,图1 所设计算法可行,证毕。

3 实例模拟

图2 为一个具有20 个结点的应急交通网络,假设应急救援物资支持保障中心为结点1 所在位置,失事直升飞机坠落地点为结点20 所在位置。网络中各条弧的长度lij,初始通行速度uij0,弧( vi,vj) 中交通工具的影响系数 ηtij、风速影响系数 ηvij、道路积水影响系数 ηsij、危险系数 ηrij、局部通行障碍物的当量长度系数 ρijm以及弧( vi,vj) 中局部通行障碍物的个数nijm如表1 所示。

表1 的数据设置可以反映实际应急交通网络的结构并对灾害扩散对应急交通网络通行状况的影响实现了模拟。这里根据受灾害扩散影响程度的不同将应急交通网络与20 个节点划分为3 个区域,如图2 所示( 通过相邻两区边界的弧被视为在前一个区域内) ,危险系数 ηrij的不同反映了飞机失事引发的次生灾害对应急救援交通网络中各弧段的影响,ηrij的取值区间根据应急交通网络分区划分为3 个等级: 区Ⅲ为1,区Ⅱ为( 1,1.5) ,区Ⅰ为( 1. 5,3 ) ,具体数值根据取值区间随机假定设置,距离失事地点较近的路段具有较高的危险系数( 例如区Ⅰ内的路段) ,距离失事地点较远的路段具有较低的危险系数( 例如区Ⅲ内的路段) 。

为验证本文算法相比传统最短路算法的优势,假定决策者给出的当量长度的最低可承受值Lt= 480 m,编译图1 所示算法求解应急救援物资支持保障中心到失事直升飞机坠落地点的最佳救援路线,结果见表2。从表2 数据可以看出,根据传统最短路算法求解的两个理想点中: 路线1→6→7→8 →13→9 →14→15→20 的行驶时间最短,虽然满足了应急救援的时效性需求,但路线的当量长度过长,超过了安全性上可承受的范围,无法保障救援人员自身的生命安全; 路线1→6→7→8→13→18→20 的当量长度最短,但是行驶时间过长,从应急救援的时效性来看并不合理。根据双目标优化算法求解的路线为1→6→7→8→13→19→15→20,其当量长度相比1→6→7→8→13→18→20 少了63. 79% ,却只比1→6→7→8 →13→9 →14→15→20 的运输时间多了38. 99% ,据此可以得出结论,本文的双目标优化算法能同时兼顾时效性和安全性两方面的优化需求,因而相比传统的最短路算法更具优势。

4 结论

1) 本文直升飞机失事后造成的次生灾害对交通网络中各弧段通行状况的影响,建立了直升机失事应急救援路线的双目标优化模型。模型中将各弧段的安全性建模为弧段的“当量长度”,用不同的系数来表示各弧段的危险程度,从而实现了对应急交通网络更贴近实际的模拟。通过将双目标优化模型转化为单目标优化模型,设计了求解模型的双目标优化算法,算法的正确性证明及实例模拟表明了模型和算法的正确性和有效性。

2) 应急救援中还需要根据不同的事故情景考虑很多其他复杂的实际因素,本文针对直升飞机失事后的应急救援路径选择这一基础性问题建立了一个更贴近实际的数学模型。但是在有些事故灾难中,有时可能没有多余的救援路径可供选择,比如能只有单条可通行的路径,甚至道路完全被损坏,此时,紧急救援物资储存点的合理选址与优化则成为值得研究的问题。

参考文献

[1]王文博.民用航空器搜寻技术研究[D].北京:中国民用航空飞行学院,2015:1.

[2]张毅,郭晓汾,王笑风.应急救援物资车辆运输线路的选择[J].安全与环境学报,2006,6(3):51-53.ZHANG Yi,GUO Xiaofen,WANG Xiaofeng.Route choice for transporting emergency succor materials[J].Journal of Safety and Environment,2006,6(3):51.

[3]高蕊,蒋仲安,董枫,等.基于Map Object的矿井火灾动态最佳救灾路线数学模型和算法[J].北京科技大学学报,2008,30(7):705-709,755.GAO Ri,JIANG Zhongan,DONG Feng,et al.Mathematical model and algorithm of a dynamic optimum rescue route during mine fire time based on Map Object[J].Journal of University of Science and Technology Beijing,2008,30(7):705-709,755.

[4]肖国清,温丽敏,陈宝智,等.毒气泄漏时的最佳疏散路径[J].东北大学学报(自然科学版),2001,22(6):674.XIAO Guoqing,WEN Limin,CHEN Baozhi,et al.Shortest evacuation route on toxic leakage[J].Journal of Northeastern University(Natural Science),2001,22(6):674.

[5]Yuan Y,Wang D.Path selection model and algorithm for emergency logistics management[J].Computers&Industrial Engineering,2009,56(3):1081-1094.

[6]Xiao X W,Xiao D,Lin J G,et al.Overview on multi-objective optimization problem research[J].Application Research of Computers,2011,28(3):805-167.

[7]樊治平,尤天慧,张尧.属性权重信息不完全的区间数多属性决策方法[J].东北大学学报(自然科学版),2005,26(8):798-800.FAN Zhiping,YOU Tianhui,ZHANG Yao.Method for interval multiple attribute decision-making problem with incomplete attribute weights[J].Journal of Northeastern University(Natural Science),2005,26(8):798-800.

[8]邓云峰,李竞,盖文妹.基于个体脆弱性区域疏散最佳路径[J].中国安全生产科学技术,2013,9(11):53-58.DENG Yunfeng,LI Jing,GAI Wenmei.Study on the optimum escape route during zone evacuation based on vulnerability of humans[J].Journal of Safety and Technology,2013,9(11):53-58.

[9]刘亚威,彭再云,谭远顺.关于多目标规划问题绝对最优解、有效解、弱有效解间的关系[J].南京师大学报(自然科学版),2010(3):19-21.LIU Yawei,PENG Zaiyun,TAN Yuanshun.About multiobjective programming absolute optimal solution,efficient solutions,weak relationship between effective solution[J].Nanjing Normal University(Natural Science),2010(3):19-21.

双目标优化模型篇5

随着企业规模的不断扩大, 越来越有能力承担更多的项目, 因此对哪些项目进行选择, 就成为企业面临的首要问题, 在学术上称为项目组合选择问题, 即指在一系列约束条件下, 选择出一组项目, 以获得最优收益, 并能最大限度满足企业目标。属于较为复杂的运筹学难题, 无论从理论上还是从实践上均具有较强的研究价值。

项目组合选择问题最早可以追溯至Markowitz的研究[1], 其提出的很多思想, 至今仍具有借鉴意义。近年来, 很多学者对项目组合选择问题进行了发展和创新。S.Ghorbani研究了具有计划水平期限的双目标项目组合选择问题, 并设计了基于Pareto思想的多目标求解算法[2]; Chen Jiaqiong研究了具有网络调度形式的项目组合选择问题, 并采用隐枚举算法进行求解[3]; L.Andre′s总结已有研究提出了较为通用的项目组合选择运筹优化模型, 并通过一个案例说明了模型的应用效果[4]。在不确定条件下的研究方面, Christer Carlsson建立了模糊整数规划模型, 用以进行项目组合选择[5];Juite Wang提出了模糊组合选择0-1整数规划模型, 可以在没有可靠信息情况下辅助进行组合选择决策[6]。国内学者杜先进对模糊环境下多目标的项目组合选择问题进行了研究[7]。

从已有研究来看, 项目组合的选择过程均考虑在一个阶段内完成。但是实际上, 项目组合选择是一个多期连续的过程, 具有多阶段特点, 即在本期选择的项目中, 生命周期较长的, 会延续到下期或者后面几期才能完成, 先期完成的项目会释放占用的资源, 企业可以利用这些资源选择和实施新的项目, 因此企业的项目组合选择实际上是一个多阶段连续滚动的过程。当给定阶段数量限制, 并以整个计划阶段内项目整体收益最大为优化目标时, 则转化为底线 (类似总工期) 约束的多阶段项目组合选择问题, 这方面的研究还不多见。

同时, 现有研究或者单纯考虑确定性情景, 或者单纯考虑不确定情景, 但实际情况通常是各阶段情景渐变的。第一阶段选择的项目往往具有较为确定的环境信息, 越后面阶段选择的项目, 就越具有不确定的环境信息, 具有变情景特点。

通过上面分析, 本文研究定位于底线约束的多阶段变情景项目组合选择整体优化研究, 考虑两阶段双情景作为具体的建模仿真研究背景。

2 问题描述与建模

2.1 问题假设

企业要选择的项目通常具有不同的生命周期, 并且多为某标准时间单位 (年、季等) 的倍数, 这里将两阶段情况下, 生命周期长度为一个阶段的项目称为小项目, 为二个阶段的项目称为大项目。一般认为小项目具有较少的资源需求和项目价值, 大项目具有较大的资源需求, 当然也具有较大的项目价值。两个阶段均针对一个候选项目池进行选择, 这里结合实际情况做如下建模假设:

①项目在执行过程中没有间隔, 连续进行, 并且认为项目能够按阶段要求的时间如期完成;

②第一阶段选择的项目, 具有确定的项目价值。由于大项目只能在第一阶段选择, 因此认为大项目在两个阶段均具有确定的项目价值, 这是因为在选择并启动项目时, 往往以合同的形式来约定项目未来的收益, 这样就使得后阶段的项目价值较为确定;

③第二阶段选择的项目, 具有不确定的项目价值。由于第二阶段只能选择小项目, 并且要等到第二阶段才能启动选择的项目, 因此只能事先估计项目价值;

④第一阶段为确定性资源约束, 第二阶段为不确定性资源约束。这是出于对外部资源供应环境的考虑, 通常越往后的阶段供应会越不稳定;

⑤各项目均具有确定的资源需求。这是由项目自身的运作规律决定的。

2.2 问题描述

设有候选项目集A, 其中共有n个项目, A′1-1表示第一阶段已选择的小项目, A′1-2表示第一阶段已选择的大项目, A2-1表示第二阶段中可以选择的小项目, A2-2表示到第二阶段未选的大项目, A′2-1表示第二段中已选择的小项目。则有: A′1-1∩A′1-2=∅; A′2-1∈A2-1; A2-1= (AA′1-1∪A′1-2) ) A2-2; 符号表示去除后面的集合。具体组合选择结构如图1所示。

其中1, 2, 3表示第一阶段已选择的小项目A′1-1={1, 2, 3}, 4, 5, 6表示第一阶段已选择的大项目A′1-2={4, 5, 6}, 延伸到第二阶段完成, 第一阶段获得的总项目价值用确定值V1表示, 大项目在第二阶段内的项目值用确定值V1-2表示, 7, 8为第二阶段选择的小项目A′2-1={7, 8}, 具有模糊的项目价值 $\tilde{V}$ 2, 模糊期望值为E ( $\tilde{V}$ 2) 。第一阶段总资源约束为确定值R1, k, 表示对k型资源的总约束, 第二阶段总资源约束为模糊值 $\tilde{R}$ 2, k, 其中k=1, …, K, K为最大资源数量, 优化目标是求整体项目价值最大。即:

$\max V = V_{1} + V_{1 - 2} + E (\tilde{V}_{2}) (1)$

对于第二阶段选择的项目由于是不确定环境, 项目值为模糊数, 因此具有一定的收益风险, 以Var ( $\tilde{V}$ 2) 表示第二阶段所选项目值的方差, 用比值 $V a r (\tilde{V}_{2}) / E (\tilde{V}_{2})$ 作为风险的度量指标。则可建立如下双层0-1整数规划模型。

2.3 优化模型

上层模型:

$\begin{array}{l} \max V = \sum_{i = 1}^{n} v_{1, i} x_{1, i} + \sum_{l \in A^{'}_{1 - 2}} v_{2, l} + E (\tilde{V}_{2}) (2) \\ s . t . \sum_{i = 1}^{n} r_{1, i, k} x_{1, i} \leq R_{1, k}, k = 1, \dots, Κ (3) \end{array}$

其中, x1, i={0, 1}, 表示第一段项目组合选择的决策变量, 当选择项目i时, 值为1, 否则, 值为0。

式 (2) 为目标函数, 式 (3) 为资源约束, v1, i表示第一阶段选择的项目i在第一阶段的项目值; v2, l表示第一阶段选择的大项目l在第二阶段的项目值; r1, i, k为第一阶段项目i对资源k的需求。

下层模型:

$\begin{array}{l} \max E (\sum_{j \in A_{2 - 1}} \tilde{v}_{2, j} x_{2, j}) (4) \\ s . t . \sum_{l \in A^{'}_{1 - 2}} r_{2, l, k} + \sum_{j \in A_{2 - 1}} r_{2, j, k} x_{2, j} \leq \tilde{R}_{2, k} (5) \\ \frac{V a r (\sum_{j \in A_{2 - 1}} \tilde{v}_{2, j} x_{2, j})}{E (\sum_{j \in A_{2 - 1}} \tilde{v}_{2, j} x_{2, j})} \leq θ (6) \end{array}$

其中: x2, j={0, 1}, 表示第二段项目选择的决策变量, 当选择项目i时, 值为1, 否则, 值为0。

式 (4) 为下层目标函数, 即第二阶段选择项目的模糊期望值最大化;式 (5) 为资源约束;式 (6) 为风险约束, θ为风险置信水平。 $\tilde{v}$ 2, j表示第二阶段小项目j的模糊价值;r2, l, k表示第二阶段大项目l对资源k的需求;r2, j, k表示第二阶段小项目j对资源k的需求。对于下层模型可以采用模糊理论进行确定性转化。

2.4 确定性转换

①模糊期望值和方差[6]

设有梯形模糊数 $\tilde{A} = (a, b, α, β) ‚ a < b$ , 其中α、β为左右两边跨度;则 $\tilde{A}$ 的模糊期望值为:

$E (\tilde{A}) = \frac{(a + b)}{2} + \frac{(β - α)}{6} (7)$

$\tilde{A}$ 的模糊方差为:

$V a r (\tilde{A}) = \frac{(b - a)^{2}}{4} + \frac{(b - a) (α + β)}{6} + \frac{(α + β)^{2}}{24} (8)$

当a=b时, 则可转化为三角模糊数的表示形式。

②可能性理论的应用

由于下层模型具有模糊系数, 因此应用可能性理论对其进行确定性转换。

对于 $\tilde{a}$ , $\tilde{b}$ 两个模糊数, 其隶属度为μ $\tilde{a}$ (x) 、μ $\tilde{b}$ (x) , 则可能性pos (·) 度量方法如下[8]:

$p o s (\tilde{a} * \tilde{b}) = \sup {\min (μ_{\tilde{a}} (x), μ_{\tilde{b}} (x)), x, y \in R, x * y}$

其中, 符号*表示>、 <、 =、 ≥、 ≤等关系。当用c表示一个确定数, 用上文 $\tilde{A}$ 表示模糊数, 则对于形如: $c \leq \tilde{A}$ 的约束形式, 可采用可能性表示为 $p o s (c \leq \tilde{A}) \geq η$ , 其中η为约束置信水平, 进而转化为如下的确定性不等式:

$\frac{b + β - c}{β} \geq η (9)$

证明可参见文献[9]。

③下层的确定性优化模型

$\begin{array}{l} \max \frac{\sum_{j \in A_{2 - 1}} v_{2, j, a} x_{2, j} + \sum_{j \in A_{2 - 1}} v_{2, j, b} x_{2, j}}{2} + \frac{\sum_{j \in A_{2 - 1}} v_{2, j, β} x_{2, j} - \sum_{j \in A_{2 - 1}} v_{2, j, α} x_{2, j}}{6} (10) \\ s . t . \frac{R_{2, k, b} + R_{2, k, β} - (\sum_{l \in A^{'}_{1 - 2}} r_{2, l, k} + \sum_{j \in A_{2 - 1}} r_{2, j, k} x_{2, j})}{R_{2, k, β}} \geq η (11) \\ \frac{\frac{(\sum_{j \in A_{2 - 1}} v_{2, j, b} x_{2, j} - \sum_{j \in A_{2 - 1}} v_{2, j, a} x_{2, j})^{2}}{4} + \frac{(\sum_{j \in A_{2 - 1}} v_{2, j, b} x_{2, j} - \sum_{j \in A_{2 - 1}} v_{2, j, a} x_{2, j}) (\sum_{j \in A_{2 - 1}} v_{2, j, α} x_{2, j} + \sum_{j \in A_{2 - 1}} v_{2, j, β} x_{2, j})}{6} + \frac{(\sum_{j \in A_{2 - 1}} v_{2, j, α} x_{2, j} + \sum_{j \in A_{2 - 1}} v_{2, j, β} x_{2, j})^{2}}{24}}{\frac{\sum_{j \in A_{2 - 1}} v_{2, j, a} x_{2, j} + \sum_{j \in A_{2 - 1}} v_{2, j, b} x_{2, j}}{2} + \frac{\sum_{j \in A_{2 - 1}} v_{2, j, β} x_{2, j} - \sum_{j \in A_{2 - 1}} v_{2, j, α} x_{2, j}}{6}} \leq θ \\ (12) \end{array}$

对于上面建立的两层0-1整数优化模型, 采用智能优化算法是较为理想的选择。

3 算法设计

3.1 路径再连接技术及其改进

路径再连接是利用算法运行中产生精英解的相关信息进行局部搜索, 以期获得更高质量的解[10,11,12]。通常从精英解中选取两个多样性较好的解, 一个作为初始解, 另一个作为目标解。通过一定规则构建一个从初始解到目标解的路径, 路径中会形成中间解, 在这些中间解中寻找比精英解更好的解进行替换, 如果没有超过精英解, 则保留目前精英解。

本文依据路径再连接的基本思想, 设计了适用于0-1编码的路径再连接方法, 逐次替代反转法, 下面用实例加以说明:

设有初始精英解:<0, 1, 0, 0, 1, 0…>;目标解:<1, 0, 1, 1, 0, 1, …>。

逐次替代反转法:

$< 0, 1, 0, 0, 1, 0 \dots > \to < \underline{1}, 0, 1, 0, 0, 1 \dots > \to < \underline{1}, \underline{0}, 0, 1, 0, 0 \dots > \to < \underline{1}, \underline{0}, \underline{1}, 0, 1, 0 \dots > \to < \underline{1}, \underline{0}, \underline{1}, \underline{1}, 0, 1 \dots > \to < \underline{1}, \underline{0}, \underline{1}, \underline{1}, \underline{0}, 0 \dots > \to < \underline{1}, \underline{0}, \underline{1}, \underline{1}, \underline{0}, \underline{1}, \dots > \dots$ 该方法是以目标解逐次替代初始解的前端, 然后以初始解后端的反转作为中间解的后部分, 直到最终达到目标解。

3.2 GA+PR算法流程

本文对于上、下层模型均采用标准遗传算法 (GA) 进行求解, 在上层算法中嵌入PR局部搜索技术, 形成GA+PR算法, 以提高获得解的质量。算法流程如下:

① 上层随机生成初始个体, 并进行约束检查, 合格个体计算上层目标值;调用下层优化程序, 返回下层目标值和下层优化解, 计算总目标值。直至达到上层种群规模pop;

② 以总目标值表示适应度, 采用锦标赛方式进行选择;

③ 采用两点交叉和均匀变异, 生成子代个体, 并进行约束检查, 合格个体计算上层目标值;调用下层优化程序, 返回下层目标值和下层优化解, 计算总目标值;

④ 对产生的子代选出精英解, 应用本文设计的PR算法进行局部搜索;

⑤ 对父代和子代进行重组;

⑥ 如果没有达到最大迭代次数, 转②, 达到最大迭代次数, 进行相关信息保存;

⑦ 算法结束, 输出结果。

下层标准遗传算法中, 选择, 交叉, 变异方式同上层, 只是种群规模和迭代次数与上层有所差异, 且没有PR局部搜索的爬山环节。

4 实验分析

考虑某企业以两阶段 (如两年) 为期限进行项目组合选择, 可选项目数量为40, 各项目的生命周期按等概率在1和2之间随机选取。对于模糊变量为了便于计算, 这里采用三角模糊数表示模糊变量, 并且考虑一种类型的资源约束。大项目和小项目在两个阶段的资源需求在[45～50]和[55～60]区间随机生成, 大项目在两个阶段的价值在[250～300]区间随机生成, 小项目的确定价值和模糊价值在[200, 250]和 ([200～250], [10～20], [10～20]) 区间随机生成, 总资源约束R1, 1取1100, $\tilde{R}$ 2, 1取[1100, 200, 200], η取0.8, θ∈[0.2, 0.3.0.4, 0.5]表示不同的风险水平。算法参数方面: 上层种群规模和迭代次数均为40; 下层迭代次数10, 种群规模40。上、下层交叉和变异概率均为0.9和0.1。图2表示θ=0.5时算法的比较结果, 表1列举了不同风险水平下的项目组合选择结果和总项目价值。

注: 2～4列数字为选择的项目编号。

从表1可以看出随着风险水平的放宽, 第二阶段选择的项目数量有所增多, 项目值也逐渐变大。通过对表1的分析, 可以得出各种风险水平下具有鲁棒性的核心选择项目, 比如第一阶段大项目中的6, 9, 16, 18, 20, 21, …, 第二阶段的2, 8, 36等, 识别这些核心项目的意义在于:这些核心项目是构成企业未来稳定获利的基础, 可以使企业在进行选择决策时, 清楚哪些项目是选择的重点, 进而为制定应急选择计划提供依据。

5 结语

本文从实践角度对两阶段双情景情况下的项目组合选择整体优化问题进行了建模研究, 并设计了相应的求解算法, 得出了一些有益结论。比较单一阶段和单一情境下的研究, 更能反映现实的选择情况。后期研究考虑多阶段、多情景的项目组合选择优化建模, 设计更加高效的算法, 并考虑进行实践应用研究。

摘要：通过实践分析, 提练出两阶段双情景项目组合选择整体优化问题, 建立了双层0-1整数规划模型, 上层模型为确定性情景, 以两阶段所选项目整体价值最大为优化目标;下层为不确定性情景, 以下层选择项目期望值最大为优化目标, 并采用方差与期望值比值作为风险约束条件。应用可能性理论对下层模型进行了确定性转化。在遗传算法 (GA) 基础上, 结合路径再连接 (Path Relinking, PR) 局部搜索技术, 设计了GA+PR算法, 仿真测试验证了算法的有效性。实验得出了不同风险系数下的优化结果, 并通过分析获得了较为鲁棒的核心选择项目, 可以为企业进行项目组合选择决策提供参考。

关键词：两阶段,双情景,项目组合选择,整体优化

参考文献

[1]Markowitz H.Portfolio selection[J].Journal ofFinance, 1952, 7:77~91.

[2]Ghorbani S, Rabbani M.A new multi-objectivealgorithm for a project selection problem[J].ADvances in Engineering Software, 2009, (40) :9~14.

[3]Chen J Q, et al.Project selection, scheduling andresource allocation with time dependent returns[J].European Journal of Operational Research, 2009, (193) :23~34.

[4]Andre′s L, et al.A multiobjective model for theselection and timing of public enterprise projects[J].Socio-Economic Planning Sciences, 2008, (42) :31~45.

[5]Carlsson C, Robert F.A fuzzy approach to R&Dproject portfolio selection[J].International Journalof Approximate Reasoning, 2007, (44) :93~105.

[6]Wang J, Hwang W-L.A fuzzy set approach forR&D portfolio selection using a real optionsvaluation model[J].Omega, 2007, (35) :247~257.

[7]杜先进, 孙树栋, 司书宾, 蔡志强.不确定条件下多目标R&D项目组合选择优化[J].系统工程理论与实践, 2008, 2:98~104.

[8]Maity K, Maiti M.Possibility and necessity con-straints and their defuzzification—A multi-itemproduction-inventory scenario via optimal controltheory[J].European Journal of OperationalResearch, 2007, (177) :882~896.

[9]Das B, Maity K, Maiti M.A two warehousesupply-chain model under possibility/necessity/credibility measures[J].Mathematical andComputer Modelling, 2007, (46) :398~409.

[10]Alvarez-Valdes R, Crespo E, Tamarit J M.RASPand path relinking for project scheduling underpartially renewable resources[J].EuropeanJournal of Operational Research, 2008, (189) :1153~1170.

[11]Vallad E, Ruiz R.Genetic algorithms with pathrelinking for the minimum tardiness permutationflowshop problem[J].Omega, 2010, (38) :57~67.

双目标优化模型篇6

由于在社会、经济等活动中普遍存在着大量的多指标决策问题,因此近年来,国内外许多学者对多指标决策问题[1,2,3,4,5,6,7]进行了多方位的研究和探讨,并得到迅速发展。灰靶决策是灰色系统理论中解决多指标决策问题的方法之一,是应用较为广泛的灰色模型之一。文献[8]针对传统的灰靶决策研究中将指标的重要性同等看待,未体现不同指标在决策中的不同作用的问题,提出了基于“奖优罚劣”变换算子和主观定权的加权灰靶决策模型,对传统的灰靶决策模型进行了改进。文献[9]针对指标值为区间数的情形,提出了区间数规范方法,并在此基础上,建立了基于区间数的灰靶决策模型,把灰靶决策模型由实数序列拓展到区间数序列,使灰靶决策理论得到了发展。文献[10]针对方案的指标评价值为区间灰数并且权重未知的决策问题,提出了灰色决策问题的特征向量方法,并建立特征向量决策算法,给出的的算法避免了指标权重的计算,使基于区间灰数的灰靶决策问题在一定程度上得以解决。文献[11]针对方案评估指标值为区间灰数的风险决策问题,提出了灰色多指标风险决策概念,利用分析技巧,建立了灰色模糊关系法及双基点法两种决策方法。在灰色模糊关系算法中,利用信息熵确定的指标权重使决策方法更符合客观要求。双基点算法在一定程度上解决了单方面基于理想点或负理想点进行决策时,未能充分利用已知信息所产生的偏差,使决策更贴近于实际。文献[12]给出了多指标灰靶决策的靶心贴近法,并采用层次分析法和离差最大法相结合确定指标的权重,是对加权灰靶决策的一种改进。文献[13]基于区间数的距离和灰熵分析,将灰色局势决策拓展到决策信息为区间数的情况,给出了灰色局势决策目标权重的优化方法,进一步完善了传统的灰色局势决策理论。

但已有的关于灰靶决策的研究往往只考虑使决策方案离正靶心最近的情形,而未考虑最优的决策方案应是离正靶心最近同时离负靶心最远,而且现有的关于指标权重的确定往往没有充分利用决策矩阵信息。针对上述问题,现提出基于双基点法,充分利用决策矩阵信息,利用多目标规划的方法确定指标权重,建立优化的灰靶决策模型,并通过应用检验这种方法的有效性。

1基于双基点优化指标权重的灰色双靶决策模型

1.1 基于双基点定权的灰靶决策模型构建

设多指标决策问题有n个被评估对象或拟定的决策方案,组成决策方案集S,S={s1,s2,…,sn};m个评价指标或属性组成指标集A,A={A1,A2,…,Am};方案Sj对指标Aj效果样本值xij(i=1,2,…,n;j=1,2,…,m),则方案集S对指标集A的效果样本矩阵为X=(xij)n×m。

由于指标集合中的指标具有不同的量纲,在决策时难以对它们直接比较,因而需要对原始效果样本矩阵进行标准化处理。采用文献[8]的方法,使用“奖优罚劣”变换算子对原始效果样本矩阵进行标准化处理。“奖优罚劣”变换算子的基本思想:对评价对象的指标优于平均水平时,赋予0至1正值,劣于平均水平时,赋予0至-1负值,具体算子如下。

令 $z_{j} = \frac{1}{n} \sum_{i = 1}^{n} x_{i j} (j = 1, 2, \dots, m)$ 。

若Aj为效益型指标,则

$\begin{array}{l} r_{i j} = \frac{x_{i j} - z_{j}}{\max (\max_{1 \leq i \leq n} {x_{i j}} - z_{j}, z_{j} - \min_{1 \leq i \leq n} {x_{i j}})} \\ (j = 1, 2, \dots, m) ； \end{array}$

若Aj为成本型指标,则

$\begin{array}{l} r_{i j} = \frac{z_{j} - x_{i j}}{\max (\max_{1 \leq i \leq n} {x_{i j}} - z_{j}, z_{j} - \min_{1 \leq i \leq n} {x_{i j}})} \\ (j = 1, 2, \dots, m) ； \end{array}$

若Aj为区间型指标,则

$\begin{array}{l} r_{i j} = {\begin{matrix} 1 - \frac{2 (A - x_{i j})}{A - \min_{1 \leq i \leq n} {x_{i j}}}, & x_{i j} < A \\ 1 - \frac{2 (A - x_{i j})}{\max_{1 \leq i \leq n} {x_{i j}} - B}, & x_{i j} > B \\ 1, & A \leq x_{i j} \leq B \end{matrix} \\ (j = 1, 2, \dots, m) ； \end{array}$

定义1 设r*j=max{rij|1≤i≤n},r-j=min{rij|1≤i≤n},则称r*={r*1,r*2,…,r*m}为正靶心,r-={r-1,r-2,…,r-m}为负靶心。

设标准化处理得到到的矩阵为:R=(rij)n×m,根据标准化矩阵确定正负靶心分别为r*和r-。在确定正负靶心后,分别以正负靶心为基点,以欧氏范数作为距离的测度,建立双基点的加权灰靶决策模型,即求出各方案到正靶心的距离和负靶心的距离,再定义一种测度相对贴近度,来衡量各方案目标值靠近理想点和远离负理想点的程度,从而作为综合评判的依据。要求出各方案到正负靶心的加权距离需要事先确定决策指标的权重系数,为确定指标权重,分别以距正靶心距离最小和距负靶心距离最大为目标,建立两个优化模型如下

$\begin{array}{l} \min \sum_{i = 1}^{n} \sum_{j = 1}^{m} (r_{i j} - r_{j}^{*})^{2} ω_{j}^{*}^{2} \\ s . t . {\begin{cases} \sum_{i = 1}^{n} ω_{j}^{*} = 1 \\ ω_{j}^{*} > 0 \end{cases} (1) \\ \max \sum_{i = 1}^{n} \sum_{j = 1}^{m} (r_{i j} - r_{j}^{-})^{2} (ω_{j}^{-})^{2} \\ s . t . {\begin{cases} \sum_{i = 1}^{n} ω_{j}^{*} = 1 \\ ω_{j}^{*} > 0 \end{cases} (2) \end{array}$

其中ω*j为由式(1)确定的第j个指标的重,ω-j为由式(2)确定的第j个指标的权重。利用库恩-塔克条件可以求出模型式(1)的最优解为

$ω_{j}^{*} = \frac{1}{[\sum_{j = 1}^{m} \frac{1}{\sum_{i = 1}^{n} (r_{i j} - r_{j}^{*})^{2}}] [\sum_{i = 1}^{n} (r_{i j} - r_{j}^{*})^{2}]}$ ;

$λ = \frac{2}{\sum_{j = 1}^{m} \frac{1}{\sum_{i = 1}^{n} (r_{i j} - r_{j}^{*})^{2}}}$ 。

同理可以解出模型(2)的最优解。

根据式(1)和式(2)确定各指标权重分别ω*j和ω-j,j=1,2,…,m。然后根据ω*j和ω-j综合确定指标权重,令ωj=αω*j+(1-α)ω-j,(0≤α≤1),α可根据决策者的偏好取值。确定指标权重后可以计算各方案与正靶心与负靶心的加权距离,最后利用正负靶心距计算各方案的贴近度,根据贴近度对方案进行排序。

1.2 双基点加权灰靶决策模型的计算步骤

(1) 将决策矩阵X=(xij)n×m标准化,得标准化矩阵R=(rij)n×m;

(2) 确定标准化矩阵的正、负靶心;

(3) 根据决策矩阵的客观信息,基于离正靶心最近,负靶心最远的原则,构建指标权重确定的优化模型,根据优化模型确定指标权重ω*j和ω-j,j=1,2,…,m。根据决策者的偏好,计算各指标的综合权重ωj=αω*j+(1-α)ω-j,(0≤α≤1);

(4) 计算出加权的正负靶心距d*i和d-i,

$d_{i}^{*} = \sqrt{\sum_{j = 1}^{m} (ω_{j}^{*})^{2} (r_{i j} - r_{j}^{*})^{2}};$

$d_{i}^{-} = \sqrt{\sum_{j = 1}^{m} (ω_{j}^{-})^{2} (r_{i j} - r_{j}^{-})^{2}}$ ;i=1,2,…,n;

(5) 计算各方案的贴近度 $c_{i}^{*} = \frac{d_{i}^{-}}{d_{i}^{*} + d_{i}^{-}} ‚ i = 1, 2, \dots, n$ ;

(6) 根据贴近度的大小,对方案进行排序,相对贴近度大者为优。

2 应用分析

为开发新产品,拟定了五个投资方案S1,S2,S3,S4,S5,各方案的效果样本值见表1,试对选择的投资方案进行排序。

在指标集中,期望净现值、风险盈利值为效益型指标,投资额、风险损失值为成本型指标。

下面利用基于双基点定权的灰靶决策模型,对投资方案进行排序,具体步骤如下:

(1) 由表1中数据可得效果样本矩阵

利用“奖优罚劣”算子变换将样本效果矩阵标准化得

(2) 根据标准化后的矩阵R可得正负靶心分别为

r*={0.800 7,1,0.825 7,0.688 6}r-={-1,-0.755 9,-1,-1}

(3) 根据模型(1)和模型(2)计算各指标的权重为

ω*={0.23,0.21,0.24,0.30}ω-={0.20,0.34,0.21,0.22};

选取α=0.5,计算综合权重得ω={0.22,0.28,0.23,0.27};

(4) 计算各方案的正、负靶心距得

d*={0.30,0.60,0.53,0.55,0.67},d-={0.69,0.65,0.60,0.48,0.42};

(5) 计算各方案的贴近度得

c*={0.69,0.52,0.53,0.47,0.39};

(6) 按照c*i,(i=1,2,…,5)值的进行排序,可得对方案Si,(i=1,2,…,n)的排序为:S1≻S3≻S2≻S4≻S5。

经过问卷调查发现,大多数决策者对这五种方案的投资偏好和利用本文的模型计算结果基本相符,决策者对方案2的偏好强于方案4和5,这也表明,经改进模型与文献[8]中的模型的计算结果相比更加符合决策者的偏好。

3 小结

文章对传统的灰靶决策模型进行了改进,主要是利用正靶心距和负靶心距构造贴近度来对方案进行综合评判,利用“奖优罚劣”变换算子对决策矩阵进行标准化处理,并充分利用决策矩阵信息,以尽可能接近正靶心同时远离负靶心为目标,构建确定指标权重的优化模型,给出了一种确定指标权重的有效方法,通过具体的实例检验了改进的灰靶决策模型的有效性。

双目标优化模型篇7

关键词：多目标优化,物流,模糊综合评判法,决策网络计划,遗传算法

0 引言

随着21 世纪的到来, 电商迅速发展, 随之带来了物流企业的蓬勃发展, 物流运输问题也备受关注。在物流运输过程中, 会涉及很多运输目标。首先, 企业希望在规定的时间内, 尽快将商品或材料运达, 以争取有利的商机。其次, 在运输过程中要保证商品或材料的安全性。第三, 运输成本能得到有效控制。即企业希望商品或材料能及时、安全并且运输成本最小地运达目的地。目前, 关于运输优化问题的研究已有一定的基础, 很多学者也提出了有效的优化模型。对其进行分析, 主要可分三大类。第一, 关于物流配送中心选址问题的研究[1,2,3], 如朱鸿[2]提出了基于不确定需求环境下的配送中心动态选址模型。第二, 关于物流运输方单目标优化问题的研究, 如成本优化[4],进度优化[5], 风险优化[6]等。第三, 关于运输问题多目标优化, 如过晓方[7]提出了以物流服务满意度、物流运输费用和物流水平为目标的综合化模型。

计划评审技术广泛地被应用于工程项目管理中, 如李莎莎[8]提出了基于网络计划的工程质量—成本—进度的综合优化模型。通过实践分析表明, 网络计划对复杂工程的优化具有很大的实用价值。对于跨国运输, 常常涉及到多次中转, 第一次中转可供选择的运输方案也有很多, 每一种在时间、成本和可靠性方面都有差异。为了解决这种整个运输过程有着成百上千的运输方案择优问题, 本文以决策网络计划为基础, 以模糊综合评判为理论, 建立了以时间最短、费用最低和运输最安全的多目标综合优化模型。

1 多目标物流方案的决策网络计划模型

1.1 决策网络计划法

决策网络计划法( Decision Network Planning Technique, DN) 是一种在计划评审技术基础上发展起来的决策方法。与传统的计划评审技术最大的区别就是加入了决策点。每个决策点可以看作是由若干项互斥的方案组成[9],而决策的关键就是从整个网络的角度出发, 从这些互斥方案中选出对整体最优的方案。

设决策点Si有k个互斥方案,Si=(Si,1,Si,2,…,Si,k),决策变量表示决策点Si中的方案j是否被选中:

,1表示j方案被选中,0表示未被选中:

1.2 优化目标

物流运输方案主要实现以下三个目标的优化:

(1)时间优化目标

一般而言, 现代企业对商品、材料都有严格的时间限制。一旦时间延误, 则可以影响制作或销售的时机, 从而失去商机, 损失惨重。表示决策点Si中方案j所需时间, S为决策网络计划中总的决策点数, 则优化函数为:

( 2) 成本优化目标

从整个物流运输过程来看, 企业希望总的运输成本能控制到最小, 因此成本优化函数可表示为:

式中:表示决策点Si中对应j方案所需的成本。

(3)可靠性优化目标

确定一个运输方案的原则之一, 就是能保证商品或材料能安全地到达目的地。工序的安全性与整个运输过程的安全性有着密切的联系, 但也有本质的区别。为了简便运算, 现将整个运输过程的安全性表示为各个工序安全性的加权值:

式中:表示决策点Si中对应j方案的安全可靠性。

2 多目标物流方案的模糊综合优化模型

2.1 模糊综合评判法

模糊综合评判法( Fuzzy Comprehensive Evaluation Method) 是在模糊理论基础上发展起来的一种对模糊事物进行评价的方法。它由因素集、评判集和模糊映射三个因素组成, 主要有如下四个步骤:

步骤1:确定因素集U=(u1,u2,…,un)。

步骤2:确定评判集V=(v1,v2,…,vm)。

步骤3: 通过模糊映射确定单因素评判矩阵。

f: U→φ ×V×, 即: ui→f (ui)= (ri,1,ri,2,…,ri,m)∈φ (V), 模糊映射f导出模糊关系Ri,j∈φ (U×V)。 Rj(ui,vj)=f(ui,vj)=ri,j, 因此单因素矩阵R能够用下面的矩阵表示:

步骤4:综合评判。

根据给定的因素权重A=(a1,a2,…,an);,运用max-min数学运算,得出综合判矩阵B=A·R。

2.2 模糊综合评判法的构造

( 1) 因素集V为各工序组合构成的序列。

( 2) 评定集U为时间优化目标、成本优化目标、可靠性优化目标。因为时间和成本为最小函数, 因此对其进行取负处理。

( 3) 单因素判断矩阵R。

( 4) 因时间、成本和可靠性的度量单位不一样, 为了综合评价, 对其进行单位化处理。

( 5) 设定评判指标权重A= (a1,a2,…,an), 可请相关专家打分得到。

( 6) 综合评判B=A·R, 并根据综合评判结果, 得出各个工序的运输方案, 为了保证求算结果为正, 现对其进行处理。

3 模型求解

由上面的分析可知, 这是一个0~1 规划问题。解这类问题的常用方法有分枝定界法、动态规划法, 但当决策点数目很多时, 这些方法运算效率很低, 有适应能力较差。遗传算法可用来解复杂的多目标优化问题, 且运算效率高, 具有不依赖梯度变化的优势。这里应用遗传算法进行求解。

3.1 染色体结构

染色体代表物流运输过程各个运输方案的组合。基因位表示决策点, 基因值表示决策方案( 如表1 所示) 。

3.2 适应度函数

适应度函数就是目标函数:

3.3 终止条件

算法的终止准则为: 最优个体在20 代以内没有发生明显的变化时则终止算法。

4 应用分析

某半导体外企公司,需要从美国运进一大批电阻材料,现对其整个运输过程进行分析。

(1)决策网络计划模型

该电阻材料由美国运输到中国,需中转六次,两次海运,四次陆运。每次中转时可选择的运输方案如表2。

(2)模糊综合优化模型

由表2 分析可知, 一共有V=36=729 种运输方案, 评判集U= (T;C;Q)。假设时间、成本和可靠性对选择运输方案的影响大小分别为:

( 3) 模型求解

根据式( 2) 至式( 4) , 求出各种运输方案对应的目标值。然后根据式( 5) 至式( 10) , 运用遗传算法得出各工序的运输方案。

方案最优化结果为: S1,1→S2,2→S3,1→S4,1→S5,1→S6,1, 所需时间为366, 成本为867 元, 平均可靠程度为0.917,综合得分为9.82578。

5 结束语

本文引入决策网络计划技术, 用决策点表示实际运输方案的选择。然后分别给运输过程的三个主要优化目标的表达式, 运用模糊综合评判法对各个组合运输方案的三大目标进行综合评判, 从而得出最优的运输方案。本文对运输过程的多个目标进行优化, 从而克服了不同目标难以共优的难题。运用遗传算法求解, 提高了工作效率,现实生活中可供选择的运输组合成百上千, 运用计算机技术能迅速有效的求得最优解。通过实例分析可知, 该模型能在兼顾时间、成本和可靠性的三大目标的同时, 对整个运输流程进行优化, 因此能为各企业对商品、材料等的运输方案决策提供有力的支持

参考文献

[1]关菲,张强.模糊多目标物流配送中心选址模型及其求解算法[J].中国管理科学,2013(21):57-62.

[2]朱鸿,徐克林,朱伟.动态需求下的多目标配送中心选址研究[J].物流技术,2012,31(4):68-70.

[3]李艳,等.物流配送中心多目标优化选址的仿真设计[J].计算机仿真,2012,29(7):234-237.

[4]刘江.基于作业成本法的企业物流成本控制研究[J].贵州大学学报(社会科学版),2011,29(6):78-84.

[5]徐小峰,邓忆瑞,李亚平.基于weibull-bayes协同物流网络资源规划进度偏差应急控制[J].系统工程理论与实践,2015,35(3):695-701.

[6]冯留波.第三方物流的法律风险和规避机制[J].物流科技,2014,33(11):101-103.

[7]过晓芳,王宇平.考虑物流服务水平的物流配送规划多目标模型[J].西南交通大学学报,2012,47(5):874-880.

[8]李莎莎,等.基于遗传算法的建筑工程三大目标综合优化[J].建筑技术开发,2011,38(7):68-71.

双目标优化模型篇8

关键词：投资组合模型,非线性规划,多目标优化,进化算法

引言

投资组合就是如何配置各种有价证券的头寸来最好地符合投资者对风险和收益的权衡。Markowitz利用证劵收益的方差度量风险提出了M-V模型。该模型要求效用函数是二次的或者收益满足正态分布, 故在实际应用中受到较多限制, 若问题规模较大, 则需要解决一个带有稠密协方差矩阵的二次规划问题, 这给问题的求解带来高度的复杂性。

继Markowitz之后, 大量的模型及求解算法被提出[1]。2008年, Dellino等[2]基于遗传算法设计出一种动态目标聚集算法求解投资组合优化模型;Kawakami等[3]以信息率为目标函数建立了动态资产投资组合模型, 并利用遗传算法求解。

综上, 大量的投资组合优化模型及算法被提出。然而, 在实践中, 投资者频繁地进行交易, 交易费对收益的影响也是投资者不容忽视的问题。已有的求解方法主要是固定风险或效益使效益最大或风险最小, 需经过多次迭代才能获得不同要求下的最优投资组合。本文主要针对含交易费的投资组合模型, 从智能优化角度设计求解算法直接对模型求解。

一、投资组合模型

假设有n种资产可供投资, 现用数额为M的资金作一个时期的投资, 投资过程中存在一定的风险, 总体风险用投资项目中最大的一个风险度量。假设购买资产时要付一定的交易费, 当项目i投资额不超过给定值时, 交易费按投资额计算, 另外, 假定存入银行存款利率为定值。建立如下多目标投资组合模型 (POM) [4]。

为资产i交易费, x= (x1, x2, ……, xn) T∈Rn为投资权重向量, μi、pi、ri、qi分别表资产i的投资定额、交易率、平均收益率和风险损失率。

二、求解算法

K.Deb提出了NSGAII解决多目标优化问题, 该算法已广泛应用于求解各类多目标数值优化问题, 但其设计时只是针对无约束的多目标优化模型。在此, 基于NSGAII给予改进使其适合该模型的求解, 获得一种提高的多目标约束进化算法 (INSGAII) 用于模型POM的求解。

设最大迭代数为N, 当前代数为k, 算法步骤描述为:

Step1:随机产生初始可行个体群A (|A|=P) 及外部集S (S=Φ) , 置初始代数k=1;

Step2:若k≤N, 则输出结果, 算法结束;否则, 进入Step3;

Step3:群体A经由Pareto非控关系获Pareto个体集S, 若|S|≥S0, 则利用浓度抑制删去冗余的|S|-S0个个体;否则, 转入Step4。并获可行群B及非可行群C;

Step4:可行群B与非可行群C经交叉, 获群体D;

Step5:群体D经突变获群体E, 并对E中非可行个体修正, 获群体F;

Step6:置k←k+1, A←F, 转入Step2。

三、数值仿真

根据初始样本空间中投资项目数定义染色体 (个体) 的长度, 染色体上每一基因代表一个项目, 基因的数值表示投资比例, 一个个体x= (x1, x2, ……, xn) ∈Rn代表一种投资组合。采用数术交叉和多项式变异策略, 对不可行的个体进行修正使其可行[5]。

现设有5种投资项目供选择, 总投资金额M设为1, 各自的交易率、收益率等信息详见表1, 其中S1为无风险资产。

线性规划[4] (LP) 、GA和INSGAII应用于算例求解分析, 两种进化算法的最大迭代数N=200, 交叉概率为0.8, 变异概率为1/n, 群体规模P=100, GA利用权重系数法将模型转化为单目标求解。

由于交易费是分段函数, 已有的LP方法无法直接求解, 在此首先不考虑交易费为分段函数, 直接设为线性函数Ti= (xiM) pi获得如图1和表2比较结果。若交易费为分段函数, 获图2比较结果, 此时LP无法获得Pareto面, 故未画出。

图1中“-”为利用Matlab软件, 在风险固定的情况下算法LP所获风险-收益Pareto面, 虽然能得到较好的收益率, 但由于该方法通过固定风险使收益最大, 故需经过不同的固定风险才能获得不同的最大收益, 算法需经过多次运算。而GA在风险较小时能获得较好的收益, 当风险稍大时, 对收益率的收索较困难。INSGAII通过一次循环即可得出多组风险——收益Pareto面, 而且由图获知收索效果较好, 速度快捷。表2为各算法在获相同的风险——收益点对下所需的平均时间, 可见LP及GA所需的时间较长。特别, 在交易函数为分段函数时LP无法获风险-收益Pareto面 (图2) , 故未能描绘, 而与GA比较易知, GA获点较少, 且收敛性较差, 而INS-GAII获得pareto面较均匀, 效果较好。

四、结论及进一步研究

在交易费为线性函数时, INSGAII较其他两算法获较均匀的pareto面;在交易费为分段函数时, 算法LP便无法获得风险-收益点对, 而GA所获效果劣于INSGAII。对于INSGA在资产数量较大的情况的性能有待于进一步研究。

参考文献

[1]H.Konno, H.Yamazaki.Mean-absolute deviation portfolio optimization model and its application to Tokyo stock marcher[J].Management Science.1991, 37 (5) :519-531.

[2]G.Dellino, M.Fedele, C..Meloni.DOAM for Evolutionary Portfolio Optimization:a computational study[J].New economics pa-per, 2008:253-266.

[3]A.Kawakami, Y.Orito, M.Inoguchi.Dynamic Asset Portfolio Optimization by Using Genetic Algorithm[C].IEEE.Transactions onElectronics, Information and Systems, 2009, 129 (7) :1348-1355.

[4]赵静, 但琦.数学建模与数学实验[M].北京:高等教育出版社, 2008.

【双目标优化模型】推荐阅读：

双目标优化05-22

优化目标函数07-14

双目标06-14