混沌优化算法在组合优化问题中的应用

智能信息处理陈双等:混沌优化算 法在组合优化问题中的应用混沌优化算法在组合优化问题中的应用陈双',郭建勤”(1.山东大学计算机科学与技术学院山东 济南250014;2. 山东电子职业技术学院山东 济南250014)摘要:组合优化问题一 直都受到理论界和工程界的重视，此类问题的求解方法也有很多,却各有缺点和局限性,不能满足实际应用的需要。混沌优化算法在解决数值优化问题上具有一定的普遍性,可以很快找到全局最优解,不过组合优化.问题的解不是一个数值,因此在前人研究的基础上,提出求解组合优化问题的混沌优化算法。首先分析混沌优化,并针对组合优化问题中的TSP问题,提出一种混沌优化策略,探讨在TSP问题中应用混沌优化算法的方法。结果表明了该方法的有牧性。关键词:混沌优化算法;組合优化;TSP;教值优化中围分类号:TP18文献标识码:B文章编号:1004 - 373X(2008)18 - 068 - 03Application of Chaos Optimization Algorithm in the Solution ofCombination Optimization ProblemsCHEN Shuang' ,GUO Jianqin'(1. School of2. Shandong College of Electronice Technology .Jin' an,250014,China)Abstract: The combination optimization problems have been paid more attention in the field of theory and the engineering,there also has many solutions of this kind of problems, but actually they all have their disadvantages and limitations, so theycannot satisfy the need of the practical application. The chaos optimization algorithm has certain universality in the solution ofthe value optimization problems,and they can find the globally optimal solution very quickly , but the solution of the combina-tion optimization problems is not a value, therefore this article proposes the solution of the combination optimization problemschaos optimization algorithm on the studies of the predecessors. This article first analyzes the chaos optimization,and aims atthe TSP problems in the combination optimization problems,proposes one kind of strategy of the chaos optimization, and dis-cusses application of chaos optimization algorithm in the TSP problems , and finally it indicates that this method is effective.Keywords; chaos optimization algorithm; combination optimization; TSP;value optimization的现象。混沌并不是一片混乱,而是有着精致内在结构1引言的一类现象,混沌是非线性动力学系统在- -定条件下所许多实际工程问题都可以转换成组合优化问题加表现的一种运动形式,是系统处于非平衡过程中所呈现以解决,例如目标识别、特征点匹配、以及路径优化,火的随机行为;产生混沌的机制往往又是简单的非线性，力分配等问题。对于组合优化问题[1] ,通常采用神经网是丝毫不带随机因素的固定规则[印]。络或模拟退火等方法才能进行求解。这些算法虽然具混沌运动具有遍历性、随机性、规律性等特点,混沌有较快的寻优速度,但通常存在易于陷入局部极小等缺运动能在一定范围内按其自身的规律不重复地遍历所点。混沌在优化计算中具有独特的性能[2],混沌的随机有状态。混沌的遍历性特点可被用来进行优化搜索且性可使优化算法具有跳出局部极小的能力,混沌的遍历能避免陷入局部极小,因此,混沌优化搜索方法已成为性可使优化算法到达全局最优解附近。-种新颖的优化技术,混沌优化就是根据其遍历性和规律性特点采用混沌变量在一定范围内进行搜索,促使混2混沌优化屯变旱终达到全局最优点。混沌是指在确定系统中出现的一种貌似无规则,类量xTYH中国煤化工区min j(a),寻优变似随机的现象,是存在于非线性系统中的一种较为普遍c N M H G需构造混沌变量1与.寻优变量x取值区间的映射关系。本文的混合优化算法收稿日期:2008 -03-28使用x=c+d° t映射形式.其中c,d是当混沌变量在区8《现代电子技术)2008年第18期总第281期上计算机应用技术(间(0,1)遍历时寻优变量x均能在指定范围内变化的排列的计算问题,它共有二(n!) = (n- 1)!种方案.如常向量[]。混沌优化方法的迭代步骤为:果将沿同一闭合路径但是方向相反的方案只算为一个Step1设置控制误差 e,给定混沌初始向量t,令方案,则穷举法的方案数为六(n-1)!k=0;(3) TSP问题的拓展Step2将t° 映射到x°的优化区间:x° =c+ dt°,在旅行商问题的研究中,有一类多路旅行商问题并令工”=x°,f"= f°;(Multiple Traveling Salesman Problem,MTSP)。所谓Step3用混沌变量进行迭 代搜索得出x*和f*,多路旅行商问题是指m个推销员从同一城市(或不同如果1 f*-f-1l