（车辆工程专业论文）关于tsp问题的两种现代优化方法的研究及优化软件系统开发.pdf

东北大学硕士学位论文 摘要 关于t s p 问题的两种现代优化方法 的研究及优化软件系统开发 摘要 随着z o 世纪7 0 年代初期计算复杂性理论的形成，科学工作者发现并证明了 大量来源于实际的组合晟优化问题是非常难解的问题，即所谓的n p 完全和n p 难 问题，其计算时间使人难以忍受或因问题的高难度而使其计算时问随问题规模的 增加眺指数速度延长。旅行商问题( t r a v e l i n gs a l e s m e np r o b l e m ，简称t s p ) 即是该 类典型问题之一，因此，对t s p 问题最优化解法的研究具有重要的理论与现实意 义。 本文分别介绍了现代优化算法中的蚁群算法和模拟退火算法的原理、模型和 实现步骤，并成功的应用上述两种算法求解t s p 问题，同时对两种方法的优化结 果进行了比较，分析了这两种方法对于求解t s p 问题的优缺点，同时论证了上述 两种算法的正确性和有效性。 本文将优化设计方法与软件开发相结合，开发出了专门的工程优化设计应用 软件。以w i n d o w g x p 环境为开发平台，运用v c + + 语言开发了上述蚁群算法和模拟 退火算法的优化设计应用程序。该应用程序针对在工程实际中，人们虽然拥有扎 实的专业知识和技能，但往往缺乏专业的优化设计方面的知识年1 l 技能，同时对工 程优化设计拥有迫切需求的现状，应用程序采用模块化结构，拥有友好的人机对 话界面，实现了缺乏优化设计知识的工程技术人员可以解决工程优化设计实际问 题的愿望。 优化系统有包涵了较全面的优化算法和良好的用户使用界面等优点。本优化 软件系统包括了传统优化算法和现代优化算法两部分，其中传统算法包括了9 种 优化掉法，现代算法有3 种，共1 2 种优化算法。该优化软件系统有较完善的用户 使用界面，可以方便的输入优化参数和目标函数，同时也根据不茜| 的算法采用了 不同优化结果输出界而。优化应用软件运行速度快，工作可靠，彻底解决了由于 缺乏优化专门知识而进行优化设计的障碍，因此，本课题的研究成果具有重要的 工程应用价值， i i 东北是毕砸士学位论丈 关键词：t s p 问题；蚁群算法；模拟退火算法；优化设计软件 i l l 查些垄兰翌圭望堡丝圭 一生壁塑墨垒! ! 一 t h er e s e a r c ho ft w om o d e r no p t i m i z a t i o nm a t h o d sf o rt s p p r o b l e ma n do p t i m i z a t i o nm e t h o ds o f td e s i g n a b s t r a c t a l o n gw i t ht h ef o r m a t i o no ft h et h e o r yo fc a l c u l a t i o nc o m p l e x i t yo n7 0a g eo f 2 0 c e n t u r i e s ，s c i e n c ew o r k e rd i s c o v e ra n dp r o o ft h a ti t sh a r dt os o l v et h ec o m b i n a t i o n o p t i m i z a t i o np r o b l e m ，i t ss o c a l l e dn pc o m p l e t i o na n dn pp r o b l e m ，i t st i m ef o r c a l c u l a t i o ni sh a r dt ot o l e r a t eo rt h ec a l c u l a t i o nt i m ep r o l o n gw i t hi n d e xn u m b e rs p e e d b e c a u s eo ft h ep e o b l e m sh i 曲d i f f i c u l t y t h et r a v e l i n gs a l e s m a np r o b l e m ( t s p ) i sa t y p i c a lc o m b i n a t i o no p t i m i z a t i o np r o b l e m ，s ot h er e s e a r c ho ft s ph a st h eg r e a tt h e o r y a n dr e a l i s t i cm e a n i n g t h i st e x ti n t r o d u c et h et w om o d e mo p t i m i z a t i o n s ( a n ta l g o r i t h ma n ds i m u l a t e d m m e a l i n ga l g o r i t h m ) p r i n c i p l e 、m o d e la n dt h er e a l i z es t e po nt s p ( t r a v e l i n gs a l e s m a n p r o b l e m ) w h i c hi st y p i c a lo o m b i n a t i u no p t i m i z a t i o np r o b l e m a tt h es a l l q e t i m et h i st e x t g i v e st h ec o m p a r i s o no ft h eo p t i m i z a t i o nr e s u l t ，a n a l y z e st h ea d v a n t a g ea n dt h e d i s a d v a n t a g eo f t h et w om o d e mo p t i m i z a t i o n s u s i n go nt s p a tt h es s d l 2 et i m e ，t h i st e x t p r o v e st h eu s e f u l n e s sa n dt i g h t n e s so f t h et w om e t h o d s t h i st e x te o m b i n a t et h eo p t i m i z a t i o nt e c h n i ca n ds o , w a r e ，a n dd e v e l o p eaw a yt o r e s o l v et h ep r o b l e mo fo p t i m i z a t i o nt e c h n i c sa p p l i c a t i o n t h i st e x td e s i g nt h es o f t w a r e t e r r a c 七f o ra n ta l g o r i t h ma n ds i m u l a t e da n n e a l i n ga l g o r l t h n aw i t ht h ev c 十+ l a n g u a g e u n d e rw i n d o w sx pe n v o t i m e n ti t sf o rt h ew o r k e r sw h oh a v ep r o f e s s i o nk n o w l e d g eb u t t h e ym h a r dt ok n o wt h eo p t i m i z a t i o nm e t h o d t h i ss o f t w a r eh a st h e p e r f e c ti n t e r f a c ef o r u s e ra n dr e s o l v et h ea p p l i c a t i o np r o b l e mo f o p t i m i z a t i o nt e c h n i c s t h es o f t w a r eh a v e ss o m ea d v a n t a g e ss u c ha s ：e n o u g ho p t i m i z a t i o nm e t h o d s 、p e r f e c t h s e ri n t e r f a c ea n ds oo n t h es o f t w a r et e r r a c ei n c l u d et h et r a d i t i o n a lo p t i m i z a t i o nm e t h o d a n dm o d e mo p t i m i z a t i o nm e t h o d ，t h e r ea r e9k i n d so ft r a d i t i o n a lo p t i m i z a t i o nm e t h o d a n d3k i n d so fm o d e r no p t i m i z a t i o nm e t h o d ，t o t a l l y1 2k i n d s t h es o f t w a r eh a v eag o o d i v 东北大学硕士学位论文 a b s t r a c t i n t e r f a c ef o ru s e g i t sc o n v e n i e n tt oi n p u tt h en u m b e ra n dt a r g e tf u n c t i o n ，i ta l s oc a l l c h a n g ei t s i n t e r f a c ef o ro u p u t t h eo p t i m i z a t i o ns o f t w a r er u nq l l i k l ya n dw o r k d e p e n d e n t l y r e s o l v et h ep r o b l e mw h i c h i s b r i n g e db yt h e l a c ko fo p t i m i z a t i o n k n o w l e d g ef o rw o r k e r s t h e r e f o r et h er e a r c h i n gr e s u l to ft h i sl e s s o nh a si m p o r t a n t a p p l i c a t i o nv a l u e k e yw o r d s ：t s pp r o b l e m ；t h ea n ta l g o r i t h m ；t h eg e n e t i ca l g o r i t h m ；o p t i m i z a t i o ns o f n a r e v 独创性声明 本人声明所呈交的学位论文是在导师的指导下完成的。论文中取 得的研究成果除加以标注和致谢的地方外，不包含其他人己经发表或 撰写过的研究成果，也不包括本人为获得其他学位而使用过的材料。 与我一同工作的同志对本研究所做的任何贡献均己在论文中作了明确 的说明并表示谢意。 学位论文作者签名：否静 日 期：) 屯0 6 2 z 3 学位论文版权使用授权书 本学位论文作者和指导教师完全了解东北大学有关保留、使用学 位论文的规定：即学校有权保留并向国家有关部门或机构送交论文的 复印件和磁盘，允许论文被查阅和借阅。本人同意东北大学可以将学 位论文的全部或部分内容编入有关数据库进行检索、交流。 ( 如作者和导师同意网上交流，请在下方签名；否则视为不同意。) 怯铲o 、爷沙学一w 东北大学硕士学位论文 第一章绪论 1 1 前言 第一章绪论 人们在进行各种设计工作时，总是力求从各种可能方案中选择最优方案，这 就是优化设计的基本思想。从远古时代开始，人类在认识世界和改造世界的过程 中，形成了进行最有效活动的思维方法，这就尾一种寻优的过程。可以说，人们 在从事每一项有意义的活动时，都包含着特定的目标，在制定了日标后，并要求 在一定的限制条件下使该目标达到最优的状态。这就是人们要解决的最优化问题， 为了解决此问题所采用的方法，就是最优化方法。 目前优化设计方法在结构设_ | 、化工系统设计、电器传动设计、制造工艺设 计等方面中都有广泛的应用，而且取得了不少成果。实践证明，在工程设计中采 用优化设计方法，不仅可以减轻机械设备自重，降低材料消耗与制造成本，而且 可以提高产品的质量与工作性能。因此，优化设计已成为现代设计理论和方法中 的个重要领域，并且愈来愈受到从事设计工作的科学工作者和工程技术人员的 重视。 工程优化设计包括两个方面的内容：一是讲工程实际问题抽象成优化设计的 数学模型；二是应用最优化方法求解这个数学模型。工程优化问题的数学模型是 设计问题的数学表现形式，它反映了设计问题中各主要因素间内在联系的数学关 系。因此，从t 程实际问题中抽象出正确的数学模型，足工程优化设计关键，也 是工程设计人员进行优化设计的主要任务。求解这个数学模型的优化方法，是工 程设计的一种工具。研制优化算法库的主要目的是为了提供一个先进且实用的工 具。工程设计者只要懂优化算法的基本原理和优化软件的使用方法，就可以很方 便的使用这个工具来解决工程优化问题。这样，工程设计者就能够集中精力去解 决优化数学模型的主要任务，使工程优化设计达到更高的水平。每种优化方法都 有自身特点和适用场台，如随机射线法用于寻找一个较好的初始点，遗传算法全 局搜索能力强，但局部搜索能力不足等。 东北大学硕士学位论文 第一章绪论 1 2 优化设计的基本概念 1 2 1 设计变量 为了进行产品设计，要寻找并确定最佳的结构参数。这些参数中，有的呵根 据标准、规定等选定，在优化设计中可认为是设计常量，例如静摩擦系数、系列 化齿轮传动的中心距等：有的必须通过设计确定，这些参数称为设计变量 1 l ( 通过 设计确定的最佳结构参数) ，例如齿数、模数、齿宽等。设 ，托，j ，靠为摄优化问 题中的2 千变量，我们可以用一个n 维向量x 表示，记为： 墨 如 j 矗 或 x = f ，乇，d ，矗r 按照进行产品设计变量的取值特点，可分为连续变量( 例如轴径、轮廓尺寸 等) 和离散变量( 例如各种标准规格等) 。 1 2 2 目标函数 为了对设计进行定量评价，必须构造包含设计变量的评价函数，它是优化的目 标，称为目标函数，以，御表示。 在优化过程中，通过设计变量不断向尺值改善的方向自动调整，最后求得 f ( 值最好或最满意的j 值。在构造目标函数时，应注意目标函数必须包含全部 设计变量。所有的设计变量必须包含在约束函数中。在机械设计中，可作为参考 目标函数的有： 体积最小、重量最轻、效率最高、承载能力最大、结构运动精度最高、振幅或 噪声最小、成本最低耗能最小、动负荷最小等等。 1 2 3 约束条件 任何设计，都有各种各样的限制条件，例如强度、刚度等。每个限制条件都可 写成包含设计变量的函数，称为约束条件。 函数约束的形式有两种 函数约束的形式有两种 查些查兰堑主堂堡垒查 堑：二蔓! ! 鱼 1 2 优化设计的基本概念 1 2 1 设计变量 为了进行产品设计，要寻找并确定最佳的结构参数。这些参数中，有的可根 据标准、规定等选定，在优化设计中可认为是设计常量，例如静摩擦系数、系列 化齿轮传动的中心距等；有的必须通过设计确定，这些参数称为设计变量“1 ( 通过 设计确定的最佳结构参数) ，例如齿数、模数、齿宽等。设x 1 ，x ：，占，x n 为最优化问 题中的1 7 爹变量，我们可以用一个n 维向量x 表示，记为： x l 屯 占 矗 或 x = k 乇，占，x 1 7 按照进行产品设计变量的取值特点，可分为连续变量( 例如轴径、轮廓尺寸 等) 和离散变量( 例如各种标准规格等) 。 1 2 2 目标函数 为了对设计进行定量评价，必须构造包含设计变量的评价函数，它足优化的目 标，称为目标函数以f 伍j 表示。 在优化过程中，通过设计变量不断向只值改善的方向自动调整，是后求得 爿m 值最好或最满意的值。在构造目标函数时，应注意目标函数必须包含全部 设计变量，所有的设计变量必须包含在约束函数中。在机械设计中，可作为参考 目标函数的有； 体积最小、重量最轻、效率最高、承载能力最大、结构运动精度最高、振幅或 噪声最小、成本最低耗能最小、动负荷最小等等。 1 2 3 约束条件 任何设计，都有各种各样的限制条件，例如强度、剐度等。每个限制条件都可 写成包含设计变量的函数，称为约束条件。 函数约束的形式有两种 2 一 东北大学硕士学位论文 第一章绪论 ( i ) 不等式约束 g ，( y ) 0 ，耳o ，f = 1 ，2 ，= 1 ，2 ，j ，掰 ( 2 ) 等式约束 ( j r ) = 0 ，j = m + 1 ，m + 2 ，j ，p 对设计变量的可能取值范围的限制： x i 0 ， i = l ，2 ，d ，n 。 ( 12 ) ( 1 3 ) 确定约束函数时应注意：不能有矛盾约束，可行域不能无界，尽蹙避免等价约束 不能遗漏必须的约束等。 1 2 4 优化设计问题的数学描述 12 41 向量空间和矩阵 最优化问题涉及的变量经常不止一个。为了简明。在研究最优化问题时一般都 采用向量和矩阵表示法。下面几个和向量与矩阵有关的概念在最优化技术中经常 使用： ( a ) 向量运算。 设x = h ，屯，j ，矗】1 ，y = 胁，乃，正以】7 是设计空间中的任意两个点， 则有： ( 1 ) 置= y l ，i = 1 ，2 ，d ， 时，称t 与y 相等。 ( 2 ) x q ，的和、差定义：y = h m ，叠4 y 2 ，占，x n 虬】 ( 3 ) 向量与实数口的乘积定义为； c t x = a x t ，x ：，j ，r = 1 2 x 1 ，d ：j ，q j ( 4 ) 当薯= 0 ，i = 1 ，2 ，j ，”时，称x 为零向量。 ( b ) 欧氏空间。 ( 1 ) 向量的模： i 1 4 | = 如2 + 恐2 十占+ 矗2 ( 2 ) 向量 j 与 y 之 间的距离： i t x - y = “h ) 2 + ( t y 2 ) 2 + j + ( 一儿) 2 ( 3 ) n nz 与，的内积：x r y = 而* 吲瞎向孰如舵脯夹角：c o s 拈崩( 畦眺口) ( 5 ) 在实空间彤中，称掣为欧氏空间，记作f 。 ( c ) 向量的线性相关与基。 3 东北大学硕士学位论文 第一章绪论 ( 1 ) 设x ( ”，x ( ”，占，z ( ”为月”中的历个向量( 肿柚，若有爿i 全为零的个数q ， i = l ，2 ，1 1 1 ，使q z ( 1 ) + a 2 x ( 2 ) + j + x “= o 成立，称向量组x ( ”，”，d ，一“是线性 相关的。 ( 2 ) 若月一中一组向量e o ) 8 ( 2 ) ，d ，8 【“线性相关，且”中任一向量j 都可表示 为：x = a t e ( 1 + 啦p ( 2 + 占+ p ( 川，则称p “，日”，占，p n ) 为r “的一组基。 ( d ) ，矩阵。 设4 = ( 嘞) ，四= ( ) ，a 为实数，则有： 肚丑= 【q ) ，a a 2 ( ) 。( 1 4 ) ( e ) 二次型与恒定矩阵 ( 1 ) 在优化问题中，有类二次型函数很重要：，( x ) = 一0 。 ( 2 ) 设为n 阶对称矩阵，若对彤任意非零向量z ，恒有1 = 1 ，j ( - i x ) ：，血 0 ， 则称，( x ) 为正定矩阵 1 2 4 2 设计空间和可行域 以设计变量而，t ，t 矗为坐标所构成的空间称为设计空间。 设计空间指出设 计变量可能取得的空间。以二维为例，若要求置o ，i = 1 ，2 ，则= 维直角坐标的第 一象限为设计空间。 在设计空间中，满足所有约束所构成的空间，称为可行域。在可行域中，任 一点都是可行点。当设计变量均为连续变量时，可行点有无穷多个。优化设计过 程就是在可行域中沿着目标函数值不断改善的方向去搜索出最好的解。优化方法 的巧妙和威力就是用有限次搜索找出最好点，这种点称最优点或最优解，用表 示。图1 1 表示可行域的几种情况： 东北大学硕士学位论文 第一章绪论 0。逵鏖 鼍 如卸 图1 1可行域的几种示例 f i g1is e v e r a le x a m p l e so f a v a i l a b l ea r e a 1 3 优化设计的发展及研究 1 3 1 优化设计方法的发展 1 3i 1 传统优化方法的发展及应用 最优化理论和方法，是现代科学技术发展的综合产物。最优化方法成为一种 科学方法，一般认为是从1 8 世纪开始的，当时主要是微分法和变分法，但进展缓 慢。从上世纪三十年代末开始，微分学带动了人们对极值问题的研究，极值问题 促使人们对极值解的必要条件进行讨论， i 发为对拉格朗日问题的研究。马克申 在著作中，借助于新型变分和凸锥分离定理，提出了对现代最优控制理论有着决 定意义的方法。从而，各种最优化方法和理论蓬勃兴起。电子计算机出现之后， 使最优化方法研究有了大踏步的前进，出现了单纯形法、共轭方向法、惩罚函数 法等传统方法。 第二次世界大战期间，在军事上首先应用了优化技术。1 9 6 7 年，美国的r l 福克斯等发表了第一篇机构最优化论文。1 9 7 0 年，c s ，贝特勒等用几何规划解决 了液体动压轴承的优化设计问题后，优化设计在机械设计中得到应用和发展。随 着数学理论和电子计算机技术的进一步发展，优化设计已逐步形成为一门新兴的 独立的工程学科。并在生产实践中得到了广泛的应用。通常设计方案町以用一组 参数来表示这些参数有些已经给定，有些没有给定，需要在设计中优选，称为 东北大学硕士学位论文 第一章绪论 设计变量。如何找到一组最合适的设计变量，在允许的范围内，能使所设计的产 品结构最合理、性能最好、质量最高、成本最低( 即技术经济指标最佳) ，有市 场竞争能力，同时设计的时间又不要太长，这就足优化设计所要解决的问题。一 般来说，优化设计有以下几个步骤：建立数学模型，选择最优化算法，程序设计， 制定目标要求，计算机自动筛选最优设计方案等。通常采用的最优化算法是运步 逼近法，有线性规划和非线性规划。 从近l o 年发表的工程优化设计的论文可以看出，罚函数法、复合形法、约束 变尺度法、随机方向法、筒约梯度法、可行方向法等，都有较为广泛的应用。别 重庆维普信息数据库中的工程技术类刊物做检索，1 9 9 3 年至2 0 0 3 年，这6 种约束 优化方法应用的文献检出率的比例，依次约为1 2 ：1 0 ；3 ：1 5 ：1 5 。以机械设计 为例，传统优化方法主要应用于机构和机械零部件的优化设计，主要对零件或机 构的性能、形状和结构进行优化。在结构方面，如对升降天线杆的结构优化设计， 采用内点罚函数法优化，在保证天线杆具有足够的剐度和压弯组合强度的前提下 所设计出的结构尺寸比按一般的常规设计方法所计算的尺寸要小，自重更轻。在 形状方面，赵新海等对一典型的轴对称h 型锻件的毛坯形状进行了优化设计，取 得了明显的效果。在性能方面，文献【2 中以最大压力角为最小做为优化目标，并 采用坐标轮换法和黄金分割法等优化方法对书本打包机中的推书机构( 凸纶一连 杆组合机构) 进行优化设计，从而使得机构确保运动的平衡性的前提下具有良好的 传力性能，使设计结果更加合理。在文献【3 中，利用改进的约束变尺度法，求解 基于噪声控制的弹性连杆机构结构控制同步优化问题，同步优化后机构的噪声辐 射性能指标具有明显改善。 将优化技术与可靠性理论相结合，形成了可靠性优化设计法。按照可靠性优 化设计方法没计的产品，既能定量地回答产品在运行中的可靠性，又能使产品的 功能参数获得优化解，两种方法相辅相成，是一种非常具有工程实用价值的设计 方法。如采用惩罚函数内点法求解齿轮传动的可靠性优化设计的数学模型，以及 运用二阶矩法和约束随机方向法对钢板弹簧进行可靠性优化设计。 目前，随着工程问题的日益扩大，优化要面对的问题的规模和复杂程度在逐 渐增大，传统的优化方法解决这些问题时，就显露出了其局限性与缺陷。于是就 出现了在分析现有算法的基础上，针对方法的不足或应用问题而作出的改进应用。 6 东北大学硕士学位论文 第一章绪论 对传统优化方法应用于离散变量优化的改进和应用 工程设计问题中，经常遇到设计变量必须符合本行业的设计规范和标准， 只能取为限定的离散值或整数值的情况，如果应用连续变量优化方法，得到晟优 解后再作简单的圆整处理，町能造成设计上的不可行解，或得到一个非最优解。 为此适用于变量取离散值的优化方法发展起来。惩罚函数优化方法是一种常用的 求解约束非缉f 生问题的方法，但它仅限于求解连续变量的优化问题。在文献 4 中， 对含离散变量的工程问题，构造了一个离散性惩罚项，得到的优化结果是离散值， 不需要圆整便可直接应用于工程设计巾。何燕将改进的惩罚函数优化法应用于机 械的优化设计中，将整个优化过程分为连续变量惩罚函数法的初始优化、带离散 变量的惩罚函数法优化和网格法检验三步进行，消除了优化变最初始值对优化结 果的影响，使优化结果更为准确、合理。 传统优化方法在非线性约束问题中的应用 针对多维非线性有约束问题，文献 5 考虑了搜索方向和约束条件，提出了 改进的进退法来确定搜索区间。由于此方法不需要对目标函数进行求导，因而它 更加适合于多约束非线性优化问题。在内点罚函数法调用p o w e l l 法求优问题中， 文献 6 】分析了内点罚函数法调用p o w e l l 法求优时，涉及到一个爿，= 2 咒一x 0 的计 算，因无法确保五落在可行域内，面一旦置落在可行域之外，将影响搜索速度或 计算的收敛，甚至会引起算法错误导致计算半途终l 匕。文中依据p o w e l l 法的判据 原理，对其应用于内点罚函数法求优时进行了改进，对所进行的比较算例进行统 计，用改进后的方法计算，调用目标函数次数下降了3 2 3 ，罚函数构造轮次( 蹦 因子r 的递减次数) 减少了1 8 2 。 针对约束坐标轮换法收敛速度较慢，可靠性差的缺点，对求解约束优化问题 中的变量轮换法的改进一一文在利用约束变量轮换法优点的基础上，建立了一个 新的搜索方向，迭代过程类似于约束变量轮换法，并使约束变量轮换法的敬能得 到加强【，j 。对优化设计复合形法的改进一文巾，针对一些文献介绍的现行复合 形法在快速构造初始复合形，有效进行一维搜索，合理构造新复合形等方面存在 不足之处，进行了改进，使计算机程序比较简短，使用操作方便，计算效率比现 行复合形法有所提高，适用于求解中、小型约束优化设计问题1 8 。同样，在剥优 化设计随机方向法的改进一文中，对约束随机方向法也进行了改进，从而提高 东北大学硕士学位论文 第一章绪论 了计算效率t g 。由以上的例子可以看出，传统优化方法仍然具有不可忽视的作用。 1 3 1 2 现代优化方法的发展及应用 近年来，各种优化方法如雨后春笋般纷纷涌现。在对组合优化问题的研究中， 人们发现用确定性的优化算法求最优解，其计算时间使人难以忍受，或因问题的高 难度而使计算时间随着问题规模的增加以指数速度延长。用近似算法如启发式算 法求解得到的近似解，则不能保证其可行性和最优性，甚至无法知道所得解同最优 解的近似程度。因而在求解大规模组台优化问题时，传统的优化算法就显得无能为 力了。2 0 世纪5 0 年代中期创立了仿生学，人们从生物进化的机理中受到启发，提出 了许多用| 2 上解决复杂优化问题的新方法，如遗传算法、蚁群算法、禁忌搜索算法、 模拟退火算法等。遗传算法、蚁群算法、禁忌搜索算法都是随机搜索算法。它们 的搜索过程都具有非确定性，具有避免陷入局部最优以收敛于全局最优( 或次优) 的能力。这些算法已在求解组合优化问题上得到广泛的应用，并出现了很多改进的 算法，取得了令人满意的效果。 近十年来，模糊优化设计在模糊数学基础上发展起来，并具有较广的前景。由 于事物差异之间的中介过渡过程所带来的事物普遍存在的模糊性；由于定量的研 究从物理领域进入到事理领域必然要遇到大量的模糊概念：由于研究对象的复杂 化必然耍涉及种种模糊因素；由于信息技术、人工智能的研究必然要考虑对模糊 信息的识别和处理等。这些都必然使优化设计问题涉及种种模糊因素。过去，由 于缺乏处理模糊概念的方法和手段，把许多模糊因素人为地当成是确定性的或| 直 机性的进行处理，这样往往漏掉了真正的优化方案，甚至带来一些矛盾的结果。求 解模糊优化问题的一个基本途径，是把模糊优化问题转化为非模糊优化问题，再 用普通优化方法求解。目前实现这种转化的基本方法有两个：一是最优水平截集 法，二是近似模糊集合法。最优水平截集法，是王光远等于1 9 8 4 年提出来的。其 基本思想是：从安全可靠又经济实用的要求出发，寻求一最优水平截集，即在标 志模糊性的中介过渡过程中，截取一晟优的非模糊状态。把原来的模糊优化问题 转化为相应的普通优化问题。于是，该普通优化问题的最优解，就是原模糊优化 问题的优化方案。可见在设计过程中充分考虑各设计变量和约束条件的模糊性， 将模糊分析和优化设计结合起来，可为设计提供理想的结果。 剐复杂系统进行动态优化设计，其目标函数很难建立，因而用传统优化方法 8 东北大学硕士学位论文 第一章绪论 就难以解决，人工神经网络模型是山大量神经元互连而成的嘲络，具有极强的非 线性映射功能，是一种描述和处理非线性关系的有力数学：【：具。因此，可以通过 神经网络实现系统设计变量与其动态特性参数之间的映射，并利用该神经网络模 型建立目标函数，从而使一个复杂的动态优化问题转化为一个相当简单的优化问 题，这样就可以利用数学规划法自动实现动态优化设计。人工神经网络用于优化 设汁多为b p 神经网络和h o p f i e l d 网络，其中应用最为广泛的是b p 神经网络。 遗传算法( g e n e t i ca l g o r i t h m ，简称g a ) 是新近发展起来的一种模拟生命进化 机制的搜索和优化方法，是把自然遗传学和计算机科学结合起来的优化方法。它 是根据生物界中基因的遗传变异及达尔文的自然选择和适者生存原理对问题进行 随机的进化操作，逐步迭代寻求问题最优解的方法。因为g a 有很强的解决问题 的能力和广泛的适应性，因而近年来渗透到研究与工程的各个领域，取得良好的 效果。与传统搜索方向不同的是g a 不是对具体参数的搜索空间的一个解进行评 估，而是对整个搜索空间的大量可行解同时并行搜索，这样就克服了传统方法( 如 反向传播算法) 可能陷入收敛于局部最优的困境。g a 采用对一组可行解的搜索从 某种意义上来说可以理解成对多维参数空间的并行搜索。问题解可编制成一种编 码串，大量的串群组成一代种群，该种群覆盖了整个解空间，初代的赋值是随机 的，在进化过程中，由于采用的策略是适者生存的方针，因此，下一代比上一代 总是更接近最优解。遗传算法的优点随着计算机技术的高速发展，其应用前景更 加广阔。目前主要的应用领域有复杂函数的优化求解、结构优化设计，系统控制， 自适应控制，供气、供电系统的优化设计等。遗传算法随着应用而发展，出现了 许多改进的算法以及混合算法。不少设计者根据所研究的问题，对遗传算法作了 一些改进，或与其他算法相结台，提出混合遗传算法，提高了执行效率，使计算 更有效。例如熊雪峰等用惩罚函数、实值编码策略和联赛选择机制对标准遗传算 法进行了改进，使得改进后的遗传算法在机械优化设计中有了一定的实用价值 1 ”。 杨建国等将生物免疫算法与遗传算法相结合，提出了一种基于免疫遗传机理的优 化计算模型，避免了遗传算法容易出现早熟、搜索效率低及不能很好保持个体多 样性等问题“。 现代优化方法目前应用的十分活跃，应用领域广泛，具有很大的优越性和良好 的应用前景。 东北大擘硕士学位论文 第一章绪论 13 2 建立数学模型的发展 建立正确、实用的数学模型是优化设计成败的关键。6 0 7 0 年代国际上出现一 些建模专家，但对机械优化设讣缺乏具体的指导作用。8 0 年代，国际上每2 年举 行一次数学建模学术会泌，在数学建模方面已有实质性的进展。 1 3 3 作为c a d c a m 中资源库的发展 如何构思设计本身，向设计的前沿渗透，是c a d 的发展方向之一。对设计过 程来说，当设计方案和原理初步形成，采用优化设计可以在确定结构参数过程中 评价方案的优劣和技术性能的满足程度，是解决设计本身向设计前沿的一个桥梁 或过渡。c a d 应向图示化、集成化、标准化和智能化发展，逐步达到设计自动化。 作为c a d 资源之一的优化设计和模型库，也应与此相应发展。 134 优化软件的发展 1 3 4 1 国外优化软件的发展 优化方法软件是使最优化理论得阻实践的媒介，对于最优化理论的应用有着 巨大的作用。最早出现的优化程序都是针对单一问题而设计的，不具备通用性， 随后出现了可以共享的优化软件。七十年代之后，国外对优化软件进行了大规模 的开发，研制出了一批优化程序。 有的以大型数学软件库存在，如美国的i m s l 库，共有5 0 0 多种计算方法程 序，这个库包含的优化程序不多而且缺乏最重要的约束非线性规划算法程序。 又如英国的n a g 库，包含了3 5 个有关最优化方法的程序，n a g 程序的特点是考 虑到了各耐用户的需要，对熟练的用户和没有经验的用户提供不同的程序。再如 英国的h a r w e l l 库，包含了许多最优化程序，这些程序大都是一些访问学者在 访问h a r w e l 时编制的，内容比较丰富，算法比较先进。还有美国斯坦福大学国 家物理实验室研制的n p l 库，这个库由一组优化工作者经过长期持续的工作逐渐 发展成功，在算法和软件两个方面都居于先进水平，而且还在不断更新版本，因 而一直保持着领先地位。 有的以常用优化方法软件包的形式存在。这类软件一般都具有很高的软件水 平，可靠性好，稳定性好，服务功能完善，易于学习和使用。例虫l l ，c m i n l 6 是先 1 0 东北大学硕士学位论丈 第一章绪论 进且成熟的惩罚函数法程序包；g r g 一2 是序列二次规划法程序包；v m c w d 是约束变 尺度法程序包。 1 3 4 2 国内优化算法及软件的发展及研究情况 我国的优化软件距离国际先进水甲还有一定差距，但是优化方法在我国各行 各业中的应用十分广泛，发展也分迅速。 目前国内的优化软件虽然不少，但大多为某一领域的设计者针对设计对象而 丌发的，为某领域或某设备专用的软件。它们往往根据设汁者的经验而作出来的。 如干式变压器电磁优化设计软件，航空发动机转子动力优化设计软件，采用模糊 数学中的正态分布约隶属函数的加权之和，对多阶临界转速相对于多个常用1 二作 转速的分布状态进行了描述，并由此构造了目标函数，按照设计规范的要求选定 性能约束，从而成功地建立了航空发动机转子动力学优化数学模型，在w m d o w s 9 8 n t 平台上开发了航空发动机转子动力学优化设计软件工具 1 2 】。该工具可以实现 多转子系统的转子动力学优化设计和整体转子的有限元变形与应力分析。通用结 构优化设计系统的研究与实现一文是专用于结构优化的，实现了杆、板、壳、 梁单元的组合结构的优化设计【l 。计算机辅助材料的优化设计软件应用于材料的 研究与开发基于模式识别判别分析、人工神经网络、分类图和遗传算法，适用 于材料研究的多元非线性建模和优化。这样专用的软件对所研究的领域是很有效 的，并且随着优化的发展而越来越多。 随着优化算法的发展，近几年一砦算法开始被应用于工业过程的在线优化。 但这些通用算法成功应用的前题，在于要有一个良好的描述过程系统的模型。对 于某些复杂的过程系统而言，由于包括的设备多、工艺流程复杂、工作物料品种 多、描述系统的参变量多、再加上对象机理不甚清楚，或者物性参数难以获得等 情况，给建立系统的机理模型带来了很大的困难。在这种情况下，唯一切实可行 的就是利用实际生产过程的输入输出数据，用合适的算法建立过程的辨识模型。 神经网络强有力的学习能力和非线性特性，使之非常适合应用于工业过程，它可 以有效地对过程系统的输入输出数据进行辨识，建立起符合实际生产状况的辨识 模型。张帆等将神经网络运用于在线优化软件，成功开发了n e u m a x 在线优化软件 包1 。陈霁威等将神经网络和遗传算法运用于在线优化，设计并实现了基于神经 网络和遗传算法的在线优化软件包，并将该软件成功应用于甲醇合成的在线操作 东北大学硕士学位论文 第一章绪论 优化中“。 在编制优化软件所采用的计算机算法语言巾，先后采用了b a s i c 语言、c 语言、 f o r t r a n 语言、m a t l a b 语言、v i s u a l c + + 语言等。其中，b a s i c 语言作为最先兴起 的计算机语言，在早期的优化软件丌发中得到了广泛采用，早期国外的一些优化 软件以及我国的些优化软件如优化方法程序库o p b 一1 都采用了b a s i c 语言。c 语 言、f o r t r a n 语音的出现使优化软件的开发有了更进一步的发展。 m m l a b ( m a t t l xl a b o r a t o r y ) 则是功能十分强大的工程计算及数值分析软件。 8 0 年代中期，m a t h w o r k s 公司将m a t l a b 投向市场。9 0 年代又逐步拓展其数值计算、 符号解析运算、文字处理、图形功能等等，并采用面向对象的超高级语言作为用 户界面，使砒t l a b 成为一个多领域、多学科、多功能的优秀科技应用软件，占居 了数值型软件市场的主导地位。利用m a t l a b 的优化工具箱，可以求解线性规划、 非线性规划和多目标规划问题。为工程优化设计，提供了更方便、快捷的途径。 运用此工具箱进行优化求解时，要先对优化问题进行分析，建立优化数学模型， 定义目标函数，对于约束优化问题，要同时定义出其约束条件，列出约束函数。然 后利用文件编辑器编写一个能返回函数值的m 文件，即把函数表达式写入m a t l a b 系统中，再在命令宙口调用优化程序，就能得到优化解。陈满意等用m a t l a 8 优化 工具箱解决齿轮减速器的参数优化问题，并与外点罚函数法并调用p o w e l l 优化求 解的结果比较，结果接近。但也有不少学者指出“只要目标函数和约束条件稍微 复杂一点，这些数值软件( 指m a t l a b 和l i n g o ) 都求不出最优解”。因此，在求解工 程复杂优化问题或大型优化问题时，通用型数值软件，尚有一定的局限性。 1 9 7 9 年，b j a r n es t r o u s t r u p 在新泽西州m u r r a yh i l l 的实验室中发明了c + + 。 最初他将其称为“带类的c ”。但在1 9 8 3 年，这种语言的名称改为c + + 。尽管c 十十 最初的设计目标是帮助管理超大型的程序，但是他的作用并不局限于此。事实上， c + + 的面向对象功能实际上可以高效地运用在所有编程任务上。c + + 在诸如编辑器、 数据库、个人文件系统、联网工具和通信程序这样的项目中的应用都不鲜见。随 着计算机多媒体技术、图形图像技术、计算机遇信与网络技术的发展，应用程序 设计也需要有强大的可视化设计工具来支持，v i s u a lc + + 就是m i c r o s o f t 公司推 出的支持可视化编程的集成环境。v i s u a lc + + 对于大型、复杂的程序编程，不失 为一种良好的应用软件。本课题所采用的编程语言为v i s u a lc + + 语言。 1 2 东北大学硕士学位论文 第一章绪论 1 4 课题研究的主要内容及其意义 本课题的题目为两个求解t s p 问题的现代优化方法的研究及优化软件系统开 发针对优化算法在各行各业中的广泛应用，开发出集成化的软件包，为工程技术 人员提供方便实效的应用软件。着重论述了蚁群算法及模拟退火算法及这两种方 法在求解t s p 问题中的研究及应用。 工程优化设计，包括两个方面的内容：一是将工程实际问题抽象成为优化设 计的数学模型；二是应用最优化数值方法求解这个数学模型。工程优化设计的数 学模型，是设计问题的数学表现形式，反映了设计问题中莽主要因素间内在联系 的数学关系。因此，从工程实际问题中抽象出正确的数学模型，使工程优化设计 的关键，也是工程设计人员进行优化设计的主要任务。至于求解这个数学模型的 优化方法，则是工程优化设计的一种工具，属于计算数学和应用数学的范畴。研 制优化方法软件包的主要目的，就是为了提供一个先进且实用的工具。工程设计 者只要懂得优化算法的基本原理和优化软件的使用方法，就可以得心应手的使用 这个工具去解决工程优化设计问题。这样，工程设计者就能够集中精力去解决优 化数学模型的主要任务，使工程优化设计达到更高的水平。 本研究课题的主要内容以及完成的工作主要有以下几部分： ( 1 ) 根据优化算法在工程中的实际应用情况，重点论述了蚁群算法及模拟退 火算法的原理及其在求解t s p 问题中的应用研究。 ( 2 ) 通过详细的算法分析，建立传统优化算法与现代优化算法软件的体系结 构，井根据工程人员对优化算法的实际功能需求设计优化软件包，建立系统总体 及其各功能子系统的模型。 ( 3 ) 确定系统开发的技术平台，选择合适的开发语言工具，根据软件包的算 法流程完成优化软件包的开发工作。 ( 4 ) 解决系统开发过程中的关键问题，完成实际优化考题的测评，并对软件 的考核结果进行分析。 优化方法的广泛实际应用对优化方法软件的研制提出了更高的要求，促进了 优化软件的更新工作。本软件的开发，将为工程优化设计工作者提供优良的工具， 使工程优化设计工作人员能够更方便的解决优化设计问题。 1 3 - 东北大学硕士学位论文 第= 章t s p 问题概述 2 1 引言 第二章t s p 问题概述 伴随计算机技术的飞速发展，