模糊环境下的最小权顶点覆盖问题  

Minimum weight vertex cover problem under fuzzy environments

作　　者：王辰尹[1] 倪耀东[1] 柯华[2] 

机构地区：[1]对外经济贸易大学信息学院,北京100029 [2]同济大学经济与管理学院,上海200092

出　　处：《计算机应用研究》2012年第1期38-42,共5页Application Research of Computers

基　　金：国家自然科学基金资助项目(71001080;71101027);对外经济贸易大学校级科研课题(10QD15)

摘　　要：最小权顶点覆盖问题在实际决策中应用广泛,但顶点上的权值在实际应用中通常代表费用、成本等,在很多情况下是不确定的。关注了最小权顶点覆盖问题中的模糊不确定性,对模糊环境下的最小权顶点覆盖问题进行了研究。引入了可信性理论以描述模糊不确定性,并根据不同的决策准则建立了求解模糊环境下最小权顶点覆盖问题的三个决策模型,结合模糊模拟和遗传算法设计了一种求解所建立模型的混合智能算法,并给出了数值实验。数值实验的结果验证了所提出的决策模型与算法的有效性。The minimum weight vertex cover problem is widely applied in real life;however the weights on vertices are usually uncertain.This paper focused on fuzziness in the minimum weight vertex cover problem and studied the minimum weight vertex cover problem under fuzzy environments.It introduced credibility theory to describe fuzziness.According to different decision criteria,formulated three decision models for solving the problem;and proposed a hybrid intelligent algorithm integrating fuzzy simulation with genetic algorithm.It performed numerical experiments,and the results show the effectiveness of the proposed decision models and the algorithm.

关 键 词：顶点覆盖 模糊变量 可信性理论 模糊模拟 遗传算法 

分 类 号：TP29[自动化与计算机技术—检测技术与自动化装置]