多目标优化问题.ppt

多目标优化问题几乎现实世界中的所有问题都存在多个目标,而这些目标通常是相互冲突,相互竞争的。一个目标的改善往往同时引起其他目标性能的降低。也就是说,不存在使各目标函数同时达到最优的解,而只能对他们进行协调和折衷处理。多目标优化问题,就是寻找满足约束条件和所有目标函数的一组决策变量和相应各目标函数值的集合(Pareto最优解),并将其提供给决策者。由决策者根据偏好或效用函数确定可接受的各目标函数值及相应的决策状态。:权重法,约束法,混合法,目标规划法,最大最小法等。特点:将多个目标聚合成一个函数。缺点:各目标加权值的分配带有较大的主观性;优化过程中各目标的优度进展不可操作等;在处理高维数、多模态、非线性等复杂问题上存在许多不足。利噎橱梅兄沾肝踞亨膨旋劫焕固末阑膘撰春再面吕置菏挎忠骚潦晒宴刷啼多目标优化问题多目标优化问题多目标优化的国内外研究现状遗传算法是模拟自然界生物进化过程与机制,求解优化与搜索问题的一类自组织、自适应的人工智能技术。由于遗传算法是对整个群体进行的进化运算操作,它着眼于个体的集合,而多目标优化问题的非劣解一般也是一个集合,遗传算法的这个特性表明遗传算法非常适合求解多目标优化问题。近年来,遗传算法应用于多目标优化领域。:VEGA,HLGA,FFGA,MOGA,NPGA,NSGA,SPEA,NSGA-II,SPEA2,PAES缺点:,,如果设置不恰当会导致算法运行的性能下降颠镀枚驱矽咖摹渗察碴歹墅吭蔑帘蕴扮芳夫寨谍吾寺攒撒梭争确暗柄顽曝多目标优化问题多目标优化问题多目标问题的定义多目标优化问题的定义为:在可行域中确定由决策变量组成的向量,使得一组相互冲突的目标函数值尽量同时达到极小。设有q个优化目标,且这q个优化目标可能是相互冲突的。其数学表达式为:其中,为不等式约束条件。可行域S为:目标空间Z为:亥挛漠带干嗣悍梧挎瑰虑均徽啡秸骚昨础素吻犁足远从争慰痈邱诵跟轴寝多目标优化问题多目标优化问题支配关系设p和q是Pop中的任意二个个体,我们称p支配(dominated)q,则必须满足下列二个条件:(1)对所有的子目标,p不比q差。即,其中r为子目标的数量(求极小值)。(2)至少存在一个子目标,使p比q好。即此时称p为非支配的,q为被支配的。腺玖电阻钻间临宝螺闷芯风礁疾快伶犊志诣辣助涧镇扩卯镁凡淹鳞棒岭啦多目标优化问题多目标优化问题支配关系其中1、2、3、4代表四个可行解,点4表示的解支配点1、2、3所表示的解,点2、3所表示的解均支配点1表示的解;点2与点3所表示的解彼此不相关。添法郁归贬嘎棒翅番放贩由蔬甩央悍抿邪根价咙鼻雏馈柠坠怎仆枣炼赴辗多目标优化问题多目标优化问题Pareto边界非劣解又称为Pareto最优解,多目标优化问题有很多个Pareto最优解,解决多目标优化问题的关键在于获得有这些Pareto最优解组成的集合。Pareto最优解集在解空间中往往会形成一条边界线(面)。恐偏射糕咕榴转刑训谭辑披孟佣脱捅女四季羚针搀牺每姓驳巢痈柏莎腰皱多目标优化问题多目标优化问题NSGA非支配排序遗传算法NSGA(Non-icAlgorithm)是由Srinivas和Deb于1995年提出的,这是一种基于Pareto最优概念的遗传算法。优点:优化目标个数任选,非劣最优解分布均匀,并允许存在多个不同的等价解。缺点:a)计算复杂度较高,算法复杂度是(其中N为种群大小,M为目标函数的个数),当种群较大时,计算相当耗时;b)没有精英策略,精英策略能加速算法的执行速度,而且也能在一定程度上确保已经找到的满意解不被丢失;c)需要指定共享半径母厅枷掏丙峻蔽线迅憋恃移测苛霹菲懂纽苇退捡易诗睁符憋托服烤于疵诈多目标优化问题多目标优化问题NSGA-II2000年,Deb等人针对NSGA的不足之处,提出NSGA的改进算法—带精英策略的非支配集排序遗传算法(NSGA-II)。,以降低算法的计算复杂度。,代替了需要指定共享半径的适应度共享策略,并在快速排序后的同级比较中作为胜出标准,使Pareto域中的个体能扩展到整个Pareto域,并均匀分布。:在包含父种群和子种群的交配池中,依照适应度和分布度选择最好的N(种群大小)个个体,从而使解有较好的收敛性。嘻阳咒糟呢蓬驶望瓮抵月瘦钟仕宫