一种新的求解约束多目标优化问题的遗传算法

黄冀卓１

１

王湛２马人乐１

（同济大学建筑工程系，上海２０００９２）２

（汕头大学土木工程系，汕头５１５０６３）

Ｅ－ｍａｉｌ：ｊｚｈｕａｎｇ＿ｆｊ＠ｓｏｈｕ．ｃｏｍ

摘

要

由于采用罚函数法将有约束多目标优化问题转化为无约束多目标优化问题会使求解不合理，因此，文章首先在

无约束Ｐａｒｅｔｏ排序遗传算法的基础上，提出了一个简单、实用的能分别考虑目标函数和约束函数，而又可以避免采用罚函数的全新排序方法。接着，针对小生境技术在遗传后期依旧会出现遗传漂移现象和共享半径不易确定等缺陷，提出了一种易于实现的超量惩罚策略来替代小生境技术，用以改进种群的多样性。此外，还采用了Ｐａｒｅｔｏ解集过滤器、邻域变异和群体重组等策略对算法的寻优能力进行改进，并最终形成了一种求解有约束多目标优化问题的Ｐａｒｅｔｏ遗传算法（ＣＭＯＰＧＡ），还给出了具体的算法流程图。最后采用两个数值算例对算法的求解性能进行了测试。数值试验表明，采用均布、多样等特点。ＣＭＯＰＧＡ可方便地求得问题的Ｐａｒｅｔｏ前沿，并能使求得的Ｐａｒｅｔｏ最优解集具有可靠、关键词

排序

有约束

多目标

Ｐａｒｅｔｏ遗传算法

文献标识码Ａ

中图分类号ＴＰ１８；Ｏ２２１

文章编号１００２－８３３１－（２００６）２３－００４７－０５

ＡＮｅｗＧｅｎｅｔｉｃＡｌｇｏｒｉｔｈｍｆｏｒＣｏｎｓｔｒａｉｎｅｄ

ＭｕｌｔｉｏｂｊｅｃｔｉｖｅＯｐｔｉｍｉｚａｔｉｏｎＰｒｏｂｌｅｍｓ

ＨｕａｎｇＪｉｚｈｕｏ１ＷａｎｇＺｈａｎ２ＭａＲｅｎｌｅ１

１

（ＴｏｎｇｊｉＵｎｉｖｅｒｓｉｔｙ，Ｓｈａｎｇｈａｉ２０００９２）２

（ＳｈａｎｔｏｕＵｎｉｖｅｒｓｉｔｙ，Ｓｈａｎｔｏｕ５１５０６３）

Ａｂｓｔｒａｃｔ：Ａｓｕｓｕａｌ，ｐｅｎａｌｔｙｆｕｎｃｔｉｏｎｍｅｔｈｏｄｓａｒｅｕｓｅｄｔｏｔｒａｎｓｆｏｒｍａｃｏｎｓｔｒａｉｎｅｄｉｎｔｏａｎｕｎｃｏｎｓｔｒａｉｎｅｄｍｕｌｔｉｏｂｊｅｃｔｉｖｅｏｐｔｉｍｉｚａｔｉｏｎｐｒｏｂｌｅｍ．Ｔｈｉｓｗａｙ，ｈｏｗｅｖｅｒ，ｍａｙｌｅａｄｔｏｕｎｒｅａｓｏｎａｂｌｅｓｅａｒｃｈｉｎｇｉｎＰａｒｅｔｏＧＡｓ．Ｓｏａｎｅｗｒａｎｋｉｎｇａｐｐｒｏａｃｈｗｉｔｈｏｕｔｕｓｉｎｇｐｅｎａｌｔｙｆｕｎｃｔｉｏｎｍｅｔｈｏｄｓｉｓｐｒｅｓｅｎｔｅｄｔｏｈａｎｄｌｅａｃｏｎｓｔｒａｉｎｅｄｍｕｌｔｉｏｂｊｅｃｔｉｖｅｏｐｔｉｍｉｚａｔｉｏｎｐｒｏｂｌｅｍ．Ｔｈｉｓａｐｐｒｏａｃｈｃａｎｄｅａｌｗｉｔｈｏｂｊｅｃｔｉｖｅａｎｄｃｏｎｓｔｒａｉｎｔｆｕｎｃｔｉｏｎｓｓｅｐａｒａｔｉｖｅｌｙ．Ｏｗｉｎｇｔｏｔｈｅｏｃｃｕｒｒｅｎｃｅｏｆｇｅｎｅｔｉｃｄｒｉｆｔｉｎｌａｔｅｒｇｅｎｅｒａｔｉｏｎｓａｎｄｔｈｅｄｉｆｆｉｃｕｌｔｙｉｎｄｅｔｅｒｍｉｎｉｎｇｔｈｅｓｈａｒｉｎｇｒａｄｉｕｓｗｈｅｎｕｓｉｎｇｎｉｃｈｅｔｅｃｈｎｉｑｕｅ，ａｎｅａｓｉｌｙｒｅａｌｉｚｅｄｐｅｎａｌｔｙｓｔｒａｔｅｇｙｆｏｒｅｘｃｅｓｓｉｎｄｉｖｉｄｕａｌｓｉｓｐｒｏｐｏｓｅｄｔｏｉｍｐｒｏｖｅｔｈｅｄｉｖｅｒｓｉｔｙｏｆｐｏｐｕｌａｔｉｏｎ．Ｉｎａｄｄｉｔｉｏｎ，ｓｏｍｅｔｅｃｈｎｉｑｕｅｓ，ｓｕｃｈａｓＰａｒｅｔｏｆｉｌｔｅｒ，ｎｅｉｇｈｂｏｒｈｏｏｄｍｕｔａｔｉｏｎ，ａｎｄｒｅｃｏｍｂｉｎａｔｉｏｎ，ａｒｅａｐｐｌｉｅｄｔｏｔｈｅｇｅｎｅｔｉｃａｌｇｏｒｉｔｈｍｓ．Ｏｎｔｈｅｂａｓｉｓｏｆｓｕｃｈｉｍ－ｐｒｏｖｅｍｅｎｔｓａｎｄｔｅｃｈｎｉｑｕｅｓ，ａｒａｎｋｉｎｇ－ｂａｓｅｄｇｅｎｅｔｉｃａｌｇｏｒｉｔｈｍｆｏｒｃｏｎｓｔｒａｉｎｅｄｍｕｌｔｉｏｂｊｅｃｔｉｖｅｏｐｔｉｍｉｚａｔｉｏｎｐｒｏｂｌｅｍｓｉｓｆｏｒｍｅｄ（ＣＭＯＰＧＡ），ａｎｄｉｔｓｃａｌｃｕｌａｔｉｎｇｆｌｏｗｃｈａｒｔｉｓａｄｖａｎｃｅｄ．Ｆｉｎａｌｌｙ，ｔｗｏｎｕｍｅｒｉｃａｌｅｘａｍｐｌｅｓａｒｅｇｉｖｅｎｔｏｔｅｓｔｔｈｅｐｅｒ－ｆｏｒｍａｎｃｅｏｆＣＭＯＰＧＡ．Ｔｈｅｒｅｓｕｌｔｓｏｆｅｘａｍｐｌｅｓｄｅｍｏｎｓｔｒａｔｅｔｈａｔｔｈｅｒｅｌｉａｂｌｅ，ｕｎｉｆｏｒｍｌｙｄｉｓｔｒｉｂｕｔｅｄ，ａｎｄｄｉｖｅｒｓｅＰａｒｅｔｏｏｐ－ｔｉｍａｌｓｏｌｕｔｉｏｎｓｃａｎｂｅｆｏｕｎｄｃｏｎｖｅｎｉｅｎｔｌｙｂｙＣＭＯＰＧＡｆｏｒｍｕｌｔｉｏｂｊｅｃｔｉｖｅｐｒｏｂｌｅｍｓ．Ｋｅｙｗｏｒｄｓ：ｒａｎｋｉｎｇ，ｃｏｎｓｔｒａｉｎｅｄ，ｍｕｌｔｉｏｂｊｅｃｔｉｖｅ，Ｐａｒｅｔｏ，ｇｅｎｅｔｉｃａｌｇｏｒｉｔｈｍｓ

１前言

在实际的优化问题中，我们有的时候更多的是考虑多目标

可能使至少一个人的状况变好，而又不使任何人的状况变坏。

求解ＭＯＰ的传统方法包括加权法、约束法、目标规划法、极小极大法、理想点法、分层序列法等，这些方法的基本思想是把多目标问题转化为单目标问题，然后运用单目标优化技术求解。由于在转化为单目标的过程中加进了算法设计者的主观因素，使得这些方法的每次优化结果只能得到一个妥协解，而不一定是设计者或决策者满意的解，而且采用不同的方法求解，结果可能会完全不同。

遗传算法是一种模拟自然进化过程的随机优化方法，是一个模拟由个体组成的群体的集体学习过程，其中每个个体表示给定问题解空间中的一点，遗传算法从任一初始的群体出发，

优化。通常，求解多目标优化问题（ＭｕｌｔｉｏｂｊｅｃｔｉｖｅＯｐｔｉｍｉｚａｔｉｏｎ因为单目Ｐｒｏｂｌｅｍ，ＭＯＰ）要比单目标优化问题（ＳＯＰ）困难得多。标优化问题的最优解一般可以清楚地定义；而在多目标优化问题中，由于可能存在相互冲突的多个目标，所以通常不存在一个对所有目标都是最优的解（即不能简单地定义多目标优化问题的最优解），而是存在一组均衡解，即所谓的Ｐａｒｅｔｏ最优解集。Ｐａｒｅｔｏ最优的概念最早是由意大利经济学家帕累托（Ｖｉｌ－

ｆｒｅｄｏＰａｒｅｔｏ）于１８９７年在研究资源配置时提出的，他认为最优

状态标准应该是：在某种既定的资源配置状态，任何改变都不

基金项目：广东省自然科学基金资助项目（编号：３２０３２）；广东省科技计划项目（编号：２００５Ｂ１０３０１０３０）：（），，计算机工程与应用２００６．２３４７