（计算机软件与理论专业论文）结合遗传算法的粒子群优化模型及其应用研究.pdf

山东师范大学硕士学位论文 结合遗传算法的粒子群优化模型及其应用研究 摘要 群体智能( s w a n ni n t e l l i g e n c e ) 作为一个新兴领域，自从2 0 世纪8 0 年代出现以来，引 起了多个学科领域研究人员的关注，已经成为人工智能以及经济、社会、生物等交叉学科 的热点和前沿领域。其中，1 9 9 5 年提出的微粒群算法也已经成功地应用于多个领域。它与 遗传算法类似，也有初始种群经过一步步迭代进化，但是，p s o 没有遗传操作( 如交叉算子 和变异算子) ，而是根据自己的速度来决定搜索过程，而且微粒具有记忆性，它的信息共享 机制也不同于g a ，在遗传算法中，染色体之间互相共享信息，所以单个种群的移动是比 较均匀地向最优区域移动，而在p s o 中，只有最优的粒子把信息给予其他的粒子，这是单 向的信息流动，整个搜索更新过程是跟随当前最优解的过程，与遗传算法比较，在大多数 的情况下，所有的粒子可能更快的收敛于最优解。由于微粒群算法简单，容易实现，越来 越多的学者对它进行了研究，已成为一个研究的热点问题。 随着市场竞争的日趋激烈，社会的消费观念不断发生变化，产品的功能已不再是消费 者决定购买的最主要因素。产品的创新性、环保性、宜人性、外观造型等因素愈来愈受到 重视，在竞争中占据突出地位。在这种情况下，许多企业都意识到产品设计将成为抢占市 场的决定性因素，因而试图通过产品的创新性来获得核心竞争力。创新设计能够满足求新 和多变的市场需求，有效地提高产品的市场竞争力。因此，创新设计研究倍受国内外相关 学者的关注。 到目前为止，尚未有一种系统化的方法引导设计者有条理的进行创新设计。大多数的 设计实例不是凭空创造新产品，而是在现有产品的基础上对其进行修改，以改进产品的质 量和性能，满足用户需求。智能算法的兴起，为我们探索新的概念创新设计途径提供了很 好的支持。 本文致力于研究结合遗传算法的粒子群优化模型的建立及其应用问题，目的是通过研 究新的、适用于创新设计的优化机制，将已有的进化设计的研究融入到新的智能算法中， 为设计师创新思路的开拓提供支撑平台。主要工作为： 1 提出一种基于云模型的进化机制 云是用语言值表示的某个定性概念与其定量表示之间的不确定转换模型，它把不确定， 性概念的模糊性和随机性有机地结合在一起，成功地解决了定性概念与定量值之间的转 换。而创新概念设计本身也带有一定的不确定性，基于此，本文在标准g a 的基础之上， 将云模型引入了遗传变异之中，保留了原有算法的全局优化能力，能够克服原有遗传算法 的缺点，加快设计速度，拓宽设计思路，能够增强构件概念设计的创新性。 2 提出一种基于动态小生境的微粒群优化模型 自然界的小生境为新物种的形成提供了可能性，是生物界保持近乎无限多样性的根本 原因之一。现有的微粒群算法及其变种都有着收敛速度慢、容易陷入局部极值问题，再针 i 山东师范大学硕士学位论文 对目前创新概念设计的特点，本文提出一种改进的基于动态小生境的微粒群优化模型。 3 将g a 与p s 0 相结合，提出结合遗传算法的粒子群优化技术 在动态小生境微粒群算法的基础上，引入杂交及变异机制，使微粒群具有遗传特性， 杂交能充分利用现有的信息，而变异能够产生新的解以扩大搜索的范围，在新解产生时， 对其进行杂交，以产生更好的解，当搜索陷入停滞阶段时再对其进行变异，杂交和变异可 以互补的，将两者结合实现了优势互补，从而减少计算时间以及避免早熟现象。 4 实现了一个基于结合遗传算法的粒子群优化技术的手机创新设计系统 将结合遗传算法的粒子群优化技术应用于手机创新设计领域，设计并实现了一个手机 创新设计系统。系统三维引擎a c i s 为造型内核，采用s q l s e r v e r 2 0 0 0 数据库系统，利用 v c + + n e t2 0 0 3 在w i n d o w s ，平台上开发完成。分别针对手机构件的设计、选择、组装 优化等等进行了实验分析，设计结果令人满意。 关键词：微粒群优化；共享小生境；遗传算法；云模型；创新设计；手机设计 分类号：t p 3 9 l 。7 2 山东师范大学硕士学位论文 第一章绪论 本章首先介绍了遗传算法和微粒群算法的研究背景及前沿，其次阐述创新概念设计的 发展现状，最后介绍了本文的主要工作和组织结构。 1 1 研究现状 1 1 1 遗传算法的研究现状 遗传算法是在2 0 世纪6 0 至7 0 年代由美国m 蕊g 孤大学的j o h nh o l l a n d 教授等人提出 的。他们试图从生物在自然系统中的适应的复杂过程寻求规律和解释，模拟生物在种群中 的进化机制来构造现实的系统模型。在此之前，已经有少数计算枫科学家提鲞并进行了所 谓“人工进化”系统的研究，其目的是借用自然界中“优胜劣汰，适者生存”的法则来解 决许多工程中的优化阀题。其中有些系统已经提出了种群印u l 旋。国、选择和变异操作等 概念。6 0 年代初，柏林工业大学的i r e c h e n b e r g 和h p - s c h e w e f e l 等人将生物变异的思想应 用到了风洞实验中，获得了良好的效果。同时期，l j f o g e l 等人将进化思想应用在有限自 动机俘锄t es t a 沧m a c 城n e ，f s m ) 的研究中，取褥了比较好的结果。 2 0 世纪6 0 年代中期，j o h nh 0 1 l a l l d 在前人研究的基础上提出了位串的编码技术，加强 了遗传算法遗传操作的特性。在随后的著作“a 纛雄t 藤o n 遗n 稳越a l 躲da 蠢i 纛c 潍s y 氐e 燃s 弦n 中正式提出了遗传算法。由于其通用的编码技术和简单有效的遗传操作方法使得该算法被 广泛的应用到许多领域中。g f e 螽魏s t e 懿开发了遗传算法软件 g 】巳n e s i s 口1 ，使得遗传算 法得到进一步推广和普及。1 9 8 9 年，美圜伊利诺大学的g o l d b e r g 的著作“g e n e t i c 砧g o r i m m s i ns e a r c h ，o p t i m i z a t i o n ，a n dm a c 址n el e 嬲洫g ”睇1 ，对遗传算法理论及其多领域的应用进行 了全面的分析和阐述。m i c l l a l 蝴i c z 在1 9 9 2 年出版的著作“g e t i e 触g o r i 髓强s + d 蹴 s t m c t i l r e s = e v o l u t i o n p r o 酉狮s ”【4 】，进步推动了遗传算法在优化问题中的应用。以上两本 都是对遗传算法研究影响力非常大的经典著作。 2 0 世纪8 0 年代中期以来是遗传算法蓬勃发展的时期。遗传算法、进化计算为主题的 多个国际会议在世界各地召开。很多学者对遗传算法的理论和应用都作了深入的分析和研 究。其中，g o l d b e r g 发表了一系列的具有代表性的论文醑制，为遗传算法的研究做出了很大 贡献。 1 9 8 0 年以来，随着人们意识到传统人工智能方法的局限性和计算枫速度的大幅度提高 以及并行计算的普及，遗传算法的计算速度瓶颈已经消失。遗传算法在机器学习、过程控 制、经济预测、工程优化等领域都取得了成功，并弓| 起了数学、物理学、化学、生物学、 计算机科学、社会科学、经济举以及工程应用等领域专家的极大兴趣。9 0 年代后人们比较 注重遗传算法的一些基本阀题，很多研究者提融了改进的遗传算法。如协同进化算法的研 究与应用h 引；分散的、并行的遗传算法的提出与发展融卜“3 ；自适应遗传算法的研究弧砖等等。 1 山东师范大学硕士学位论文 自从2 0 世纪9 0 年代以来，我国有关遗传算法和进化计算的研究一直处于上升的时期， 许多专著相继出版。尤其是近年来，相关应用已经在许多领域取得了令人瞩目的成果。相 关的专著和讨论网站也日益增多。 由于遗传算法在应用研究方面的长处主要是在求解的有效性、可实现性、可扩充性和 易于与其他方法相结合，所以不难预见随着相关理论研究的不断深入和应用领域的不断拓 广，遗传算法、进化计算将取得长足的发展。 1 1 2 微粒群算法的研究现状 群体智能( 洲a 玎1 1i m e l l i g e n c e ) 作为一个新兴领域，自从2 0 世纪8 0 年代出现以来，引 起了多个学科领域研究人员的关注，已经成为人工智能以及经济、社会、生物等交叉学科 的热点和前沿领域。由单个复杂个体完成的任务可由大量简单的个体组成的群体合作完 成，而后者往往更具有健壮性、灵活性和经济上的优势。群体智能利用群体优势，在没有 集中控制，不提供全局模型的前提下，为寻找复杂问题解决方案提供了新的思路。m i l l o n 嬲 在1 9 9 4 年提出群体智能应该遵循五条基本原则，分别为：( 1 ) 邻近原则( p r o x i i n 曲 p r i n c i p l e ) ，群体能够进行简单的空间和时间计算；( 2 ) 品质原则( q u a l 时p r i n c i p l e ) ，群体能 够响应环境中的品质因子；( 3 ) 多样性反应原则( p r i n c i p l eo f d i v e r s er e s p o n s e ) ，群体的行 动范围不应该太窄；( 4 ) 稳定性原则( s t a b i l i t yp r i n c i p l e ) ，群体不应在每次环境变化时都改 变自身的行为；( 5 ) 适应性原则( a d a p t a b i l i t yp 血c i p l e ) ，在所需代价不太高的情况下，群体 能够在适当的时候改变自身的行为。以上原则说明，实现群体智能的智能个体必须能够在 环境中表现自主性、反应性、学习性和自适应性等智能特性。但是，这并不代表群体中的 每个个体都相当复杂，事实恰恰相反，群体智能的核心就是由众多简单个体组成的，群体 能够通过相互之间的简单合作来实现某一较复杂的功能，完成某一较复杂的任务。其中， “简单个体”是指只具有简单能力或智能的单个个体，而“简单合作 是指个体与其邻近 个体进行某种简单的直接通讯或通过改变环境因素间接与其他个体通讯，从而实现相互影 响和协同合作n 引。目前，群体智能主要有两种算法模式，分别是蚁群算法( a mc 0 1 0 n ys y s t e m ， 简称a c s ) 和微粒群优化算法( p a n i c l es w 锄0 l p t i m i z a t i o n ，简称p s o ) 。 微粒群算法( p 硪i c l es w a 肌o p t i m i z a t i o n ) 是由k e n n e d y 和e b e d l 矾于19 9 5 年提出的 一种新的进化计算技术。其基本思想是受到早期对鸟类群体行为研究结果的启发，并利用 和改进了生物学家的生物群体模型，以使微粒能够飞向解空间并在最优解处降落。设想这 样一个场景：一群鸟在随即搜索食物，在这个区域里只有一块食物，所有的鸟都不知道食 物在哪里，但是它们知道当前的位置离食物还有多远，那么找到食物的最优策略是什么 呢? 最简单有效的就是搜索目前离食物最近的鸟的周围区域，p s o 从这种模型中得到启发 并用于解决优化问题，p s o 最初是用于处理连续优化问题的，目前其应用已扩展到组合优 化问题。 p s 0 和g a 有很多共同之处，两者都随机初始化种群，而且都使用适应值来评价个体， 2 山东师范大学硕士学位论文 拟系统控制、动念系统拦艮踪、数据分类、专家系统、多目标优化和约束优化等问题中。此 外，p s 0 还应用到很多的工业领域。比如，p s 0 已被成功地应用到反应能源和电压的控制， 以及成分混合优化等。 1 1 3 创新概念设计的研究现状 产品设计是一个复杂的创造性过程，对产品设计过程的描述，国内外已有很多的论述。 概括的说，设计可被分成两个阶段n8 i ：概念设计( c o n l p u t e r d e dc o n c 印t u a ld e s i 弘，c a c d ) 阶段和构型设计( c o n 丘g 盯a t i o nd e s i 盟，c d ) 阶段，前者的主要任务是构思设计方案，从宏观 的角度出发对产品进行创造，后者是根据设计方案进行具体的产品设计，是概念设计的延 伸和实现，两个阶段相互依赖又相互制约，是不可分割的两个部分。 概念设计阶段是产品设计过程中的最首要阶段和最具有创新性的阶段。p a l l l 和b e 娩 在其e n g i n e e r i n gd e s i 印一书中指出：“在明确任务之后，经过抽象化，拟定功能结构， 寻求适当的作用原理及其组合，确定出基本的求解路径，得出求解方案，这一部分设计工 作称之为概念设计”。概念设计主要由产品规划、功能设计、结构方案设计等内容组成。 创新设计贯穿于整个产品设计过程，也是其最富创意的环节，集各种创造力以及各种 创造性方法于一体的创新思维活动。创新设计是指在设计中采用新型技术、非常规方法、 新流程等等，在旧产品改进、新产品研制以及节约能源的消耗、改进生产加工工艺等方面 的设计，以满足人们不断更新的需求。 创新概念设计是设计学中重要的研究课题n9 l 。目前的创新设计主要体现在对产品创新 原理、创新过程的描述模型和计算模型等建模技术的研究上。创新设计方法己由原来的仿 生法、智爆法、联想法、形象思维法和阵列法等基于认知的方法过渡到基于系统的方法。 对设计进程和设计对象进行建模、模拟人类的认知思维模式，极大地推进了创新设计的自 动化。另外利用系统论和信息论的研究成果，创新设计开始向智能化发展。创新设计中的 其他方法，如虚拟仿真设计技术、广义优化设计技术己经取得相当水平的理论和应用成果； 快速设计的协同设计技术、系列化模块化技术、快速原型技术和虚拟制造技术等发展也较 为迅速。随着c a d 、多媒体、人工智能、虚拟现实、人机交互等技术的进一步成熟，产品 的创新设计将朝着多元化、优化、一体化的方向发展，人机交互方式更加自然，创新设计 的手段更为先进、有效瞳0 l 。 概念设计不仅需要设计者具有一定的设计知识，而且需要具有相当的工程经验、创造 力、观察力、直觉能力等多方面的条件。这是一种发明行为，不仅是设计过程中最关键最 富有创造性的部分，也是设计过程中最为困难的部分。到目前为止，尚未有一种系统化的 方法引导设计者有条理地进行创新设计。大量研究表明，大多数的设计实例不是凭空创造 新产品，而是在现有产品或以往设计的基础上对其进行修改和改进，从而产生新的设计方 案以改善产品的外观、质量或者性能，满足用户需求。进化计算( e v 0 1 u t i o n a r yc o m p u t a t i o n ， e c ) 技术的兴起，为我们探索一种支持进化的概念创新辅助设计途径提供了很好的支持。 4 山东师范大学硕士学位论文 将遗传算法的思想用于辅助设计就产生了进化设计。进化设计是一种基于实例的设 计方法，针对以往的设计实例进行变化、修改和完善，它在一定程度上可以促进设计的重 用，加快设计的速度。牛津大学的e h 戚d a w k i 燃，在著作疆羽孛，展现了酋个计算机进化 程序“b l i n dw 缸c 胁a l ( e r ”，用于模拟大自然模拟出的树群。p e t c rb e n t l e y 在专著豫3 1 中，综 合了众多研究成果，系统的描述了进化设计的理论框架。k 越ls i m s 则首次将计算机辅助进 化设计应用到了艺术领域疆射，开辟了“进化艺术”的新领域。美国进化艺术家m i c h a e l w i t b r o c k ，s c o t tn e i l r e i l l y 编有程序g e n e t i ca r t 。特点是由艺术家来决定进化设计方向。英 国的进化艺术家纽d 羚wr o 确o t t o m 编有程序f o 船，首次将进化设计从二维图像发展至l 三 维形体。此外，遗传算法还在乐曲设计瞳鄙以及优化布局踟中得到应用。 香港理工大学设计学院院长了o hf 蹴嚣教授多年来致力予研究进化计算在设计中应 用，成功的将遗传算法应用于建筑设计，产生令人耳目新的建筑，被誉为遗传算法在建 筑设计中应用的奠基者；刘弘、刘希玉和唐明晰教授在这个领域作了进一步的研究，研发 了相关的开发环境泌捌。悉尼大学以m a r o s e n m a i l 和j g e 【g e r o1 9 9 7 】为代表的非常规模 设计研究小组，将进化应用到建筑设计中，实现了轮廓布局方案的组合创新；c h a l l 等【c h a i l e t e2 0 0 0 ：2 0 既】将设计看作是从概念设计到后期详细设计阶段的演化过程，并以酒杯的设计 为例对进化设计技术进行了探讨；l e e 等 l e ee t c2 0 0 0 】探索了一种集成设计师设计知识和 进化语法的计算模型来进行三维产品模型生成的研究。麓j 。b e 嫩l 魁的论文系统地揭示了利 用遗传算法进行创新和优化概念设计的思想，他提出了种利用遗传算法作为其核心的遗。 传算法设计系统。目前，进化创新概念设计已经成为最重要的设计技术之一。 1 2 研究意义 l 。基于遗传算法的计算枫辅助设计已经应用在某些领域如建筑设计、工业产品设计等等 并取得了一定的成果。但其应用表现出了易出现未成熟收敛，并且收敛的速度较慢等缺陷。 如何改进遗传算法的性能并将其应用到更加广阔的领域得以使英在特定设计场合发挥作 用值得探讨。 2 嘲于微粒群算法提出的时间不长，算法缺乏深刻的、具有普遍意义的理论分析。其数 学基础相对薄弱，且存在许多不完善和未涉及到的问题。如何利用有效的数学工具对算法 的收敛性，收敛速度的估计，计算的复杂性、鲁棒性，以及预防陷入局部最优和参数设置 影响等进行分析将是今后的研究热点之一。 3 虽然微粒群算法已经成功的应用到许多领域，但其在创新概念设计中的应用还少之甚 少，设计好的算法将其完美的应用到创新设计中将有很好的发展前景。 4 将遗传算法和微粒群算法栩结合，幂| 用两种算法各蠢的优点，并将其应用到创新概念 设计中，为设计人员创新思路的开拓提供空间，促进设计的自动化和智能化，还是一个新 的缀有吸引力的研究课题。 5 作品的创新概念设计涉及到多方面的因素，如何设计一个从概念设计师的角度出发并于 设计思维较好融合的针对特定应用问题的交互设计系统一直是辅助设计的主体研究内容。 利用手机设计特有的性质构造合适的设计模型也是一项很有价值的研究课题。 5 山东师范大学硕士学位论文 1 3 本文的主要工作和组织结构 本文致力于研究结合遗传算法的粒子群优化模型及其在创新概念设计方面的应用问 题，主要工作体现在以下几个方面： 1 提出一种基于云模型的进化机制 云是用语言值表示的某个定性概念与其定量表示之间的不确定转换模型，它把不确定 性概念的模糊性和随机性有机地结合在一起，成功地解决了定性概念与定量值之间的转 换。而创新概念设计本身也带有一定的不确定性，基于此，本文在标准g a 的基础之上， 将云模型引入了遗传变异之中，保留了原有算法的全局优化能力，能够克服原有遗传算法 的缺点，加快设计速度，拓宽设计思路，能够增强构件概念设计的创新性。 2 提出一种基于动态小生境的微粒群优化模型 自然界的小生境为新物种的形成提供了可能性，是生物界保持近乎无限多样性的根本 原因之一。现有的微粒群算法及其变种都有着收敛速度慢、容易陷入局部极值问题，再针 对目前创新概念设计的特点，本文提出一种改进的基于动态小生境的微粒群优化模型。 3 将g a 与p s 0 相结合，提出结合遗传算法的粒子群优化技术 在动态小生境微粒群算法的基础上，引入杂交及变异机制，使微粒群具有遗传特性， 杂交能充分利用现有的信息，而变异能够产生新的解以扩大搜索的范围，在新解产生时， 对其进行杂交，以产生更好的解，当搜索陷入停滞阶段时再对其进行变异，杂交和变异可 以互补的，将两者结合实现了优势互补，从而减少计算时间以及避免早熟现象。 4 实现了一个基于结合遗传算法的粒子群优化技术的手机创新设计系统 将结合遗传算法的粒子群优化技术应用于手机创新设计领域，设计并实现了一个手机 创新设计系统。系统三维引擎a c i s 为造型内核，采用s q l s e r v e r 2 0 0 0 数据库系统，利用 v c + + n e t2 0 0 3 在w i n d o w s ，平台上开发完成。分别针对手机构件的设计、选择、组装 优化等等进行了实验分析，设计结果令人满意。 本文的组织如下： 第一章绪论。 第二章介绍了遗传算法的基本理论、基本操作。 第三章提出了基于云模型的变异进化机制。首先给出相关的云模型基本理论；其次详 细介绍了基于云模型的进化算法框架。 第四章构造了一个改进的动态小生境粒子群优化模型，并将遗传机制和微粒群算法相 结合，提出了结合遗传算法的粒子群优化模型。首先介绍了微粒群算法的研究背景，基本 的算法流程以及它的发展现状；其次给出小生境的基本概念以及与p s o 算法的密切结合； 最后详细介绍了适于创新设计的改进的动态小生境粒子群优化模型以及结合遗传算法的 粒子群优化模型。 第五章将结合遗传算法的粒子群优化模型在手机创新概念设计中的应用进行了研究， 设计并实现了一个手机创新设计系统。首先介绍了系统的主要实现技术a c i s ；然后给出 模型的总体框架以及系统的总体结构；并以手机轮廓为例，对基于云模型的遗传机制进行 6 山东师范大学硕士学位论文 了仿真实验，结果表明该进化机制能够克服原有遗传算法的缺点，增强灵活性，拓宽设计 思路，能够产生满足适应度分析的创新构件；最后，给出本文提出的粒子群优化模型在手 机构件设计、选择、组装等方面的实例分析，设计结果令人满意。 第六章总结了本文的主要工作和进一步的研究方向。 7 山东师范大学硕士学位论文 ( 6 ) 便于设计针对设计问题的专门知识的知识型遗传算子； ( 7 ) 便于处理复杂的决策变量约束条件。 2 2 1 3 符号编码方式 符号编码方式是指个体染色体编码串中的基因值取自一个无数值含义、而只有代码含 义的符号集。这个符号集可以是一个字母表，如 a ，b ，c ，d ，) ，也可以是一个数字符号表， 如 1 ，2 ，3 ，4 ，5 ，) ，还可以是一个代码表，如 a l ，a 2 ，a 3 ，a 5 ，) 等等。 符号编码的主要优点是： ( 1 ) 符合定义积木块编码原则； ( 2 )便于在遗传算法中利用所解问题的专业知识； ( 3 )便于遗传算法与相关近似算法之间的混合使用。 2 2 2 交叉算子 交叉是将选择后的种群中的个体( 称为父代) 随机配对。按照选定的交叉方式及确定的 交叉概率p 。把个体的基因部分地进行交换，形成一对子代个体。下面主要介绍二进制及浮 点数编码方式下的交叉算子。 2 2 2 1 二进制编码的交叉算子 二进制编码的交叉方式一般分为如下几种： ( 1 )单点交叉( o n e p o i n tc r o s s o v e r ) 单点交叉又称简单交叉，具体操作为：在个体染色体串中随机设定一个交叉点，两个个体在此位置 进行前后两部分的交换。 ( 2 )多点交叉伽u l t i p o 缸c r o s s o v e r ) 将一对父代个体的染色体串随机地多点切断，部分交换重组，产生一对新个体为子代。 ( 3 )一致交叉( u n i f o mc r o s s o v e r ) 一致交叉是指通过设定屏蔽数字( m 2 l s k ) 来决定个体的基因继承两个父个体中的哪个个 体的对应基因。一致交叉的操作过程为：当屏蔽字中的位为0 时，后代l 继承父个体1 中 对应的基因，当屏蔽字位为1 时，后代1 继承父个体2 中对应的基因，从而生成一个完整 的后代1 。反之，可生成后代2 。 1 2 山东师范大学硕士学位论文 2 2 3 1 二进制编码的变异算子 二进制变异算子较为简单，主要有以下几种： ( 1 ) 基本位变异( s i m p l em u t a t i o n ) 基本位变异操作是指对个体编码串中以变异概率p 。随机指定的某一位或某几位基因 座上的基因值作变异运算。 ( 2 )均匀变异( u m f o m lm u t a t i o n ) 均匀变异操作是指分别用符合某一范围内均匀分布的随机数，以某一较小概率来替换 个体编码串中各个基因座上的原有基因值。 ( 3 )边界变异( b o u n d a r ym u t a t i o n ) 边界变异操作是均匀变异操作的一个变形遗传操作。在进行边界变异操作时，随机地 取基因座的两个对应边界基因值之一去替代原有的基因值。特别适应于最优点位于或接近 于可行解的边界时的一类问题。 2 2 3 2 浮点数编码的变异算子 浮点数编码方式下的变异方式也有多种，设第t 代n 维向量个体x ；= ( 工，x ：，x 。) ， 变异后新值为x 。其变异方式一般有以下几种： ( 1 )单重均匀变异( 吼f o 锄m u t a t i o n ) 算子 按均匀分布随机选择一个变元石，并将它变异为 口，饥】中的均匀随机数r ： z = 二；喜1 嵩土，j 1 ，2 ，n ) 均匀随机选择 ( 2 ) 单重边界变异( b o u n d a 呵m u t a t i o n ) 算子 按均匀分布随机选择一个变元蜀，并根据( 0 ，1 ) 上的均匀随机数r 将它变为所在区 间的上界或下晃： f 口f ， 若i = j ，r o 5 葛= b i ， 若i _ j ，r o 5 ，j 1 ，2 ，n ) 均匀随机选择，若i = j ，r 4 。 此模型中五的作用类似与参数耐的作用，用来控制与约束微粒的飞行速度。实验结 果表明，元比玩积更麓有效地控制微粒速度的振动，助藤越t 和溺】b 韬is 撼详细分析比较了 两种参数对算法性能的影响，他们谦虚地承认所提出的收缩因子比惯性权重更能有效地控 制微粒的飞行速度，同时增强了算法的局部搜索能力。僚在早期的实验和应用中，认为当 采用收敛因子模型时以无足轻重，因此将默设置为个极大值如1 0 5 。后来的研究表 明将其限定为焉麟( 即每个粒子在每一维度上位置的允许变化范围) 可以取得更好的优化结 果【f 黼h y ，s h iy h ( 2 2 ) 】。 4 。3 2 离散p s o 模型 p s o 的基本算法最初是周来对连续函数进行优化的，丽实际皆许多闽题是组合优化闯 题，k e m e d y 和e b e r h 铖( 19 9 7 ) 在基本p s o 算法的基础上提出了一种离散二进制p s o 算法 m 3 来解决这一类问题。而c l e r c 推广了这一工作，研究了离散版p s o 算法，并将其应用于 旅行商问题汀s p ) 的求解，取得了较好的结果。 2 5 山东师范大学硕士学位论文 离散二进制p s o 算法与基本p s o 算法的主要区别在于更新方程，其更新方程为： 旷y = + c ，木厂，幸眵一叉抄c ：牟厂：木幔一贾：) ( 4 7 ) y ，。矿，+ c ，木厂1 幸屺一x 户c ：牟厂z 木妒。一x ， 【4 7 ) i f p l ” ( r 融曼_ 曩玉鲢熹融毛蠛2 戆( 。寰照。) ) ： 甍g 蠛e 出r g s 融囊戛棼2 ( 1 3 秘置 ： 骚窜e 眈= 佃h ：a r ) ( 蛰懿夏熹) j 0 毫羞： 淞翱啦：毯札姗醌d 磺婶。蛾3 e 鹫= 糊u x s 捆l 2 ：置珏d d 。掌鞋矗嚣若瑟铡= 弼l l ： 夏黑嬲妇r 然聪s e i 蝣毫僵酗故莓竞) ： - 薹g e 1 0 n 霉= l ：i 夏毫主砉主毫系( i ，i 妇t r 工t e 1 ) j 善( 1 嗽醯d e d 妇) ) 黜i ；嚣嚣艮耋菇至r 蹙有找劐曩性僵4 ) ： 曼玻鑫 p a t t r i t 卜 # 鲢最规醒鸯弛2 争强想煞如动： 菇珐i s e 2 鲢粥f ( 如r ) l 熬夏s ) 黧瞧勋融壤： 图5 1 3 帆文件部分操作代码 5 4 5 手机构件装配 本文第四章，研究了结合遗传算法的动态小生境粒子群优化模型，在本文系统环境下， 设计人员在进行手机外观概念设计中，可以运用以上模型，从现有的构件库中选择并装配 构件，使设计出的构件、存储于构件库中的构件最终装配成手机实体。 利用本文提出的g n p s 0 算法从各种构件库中选出手机外壳、手机按键以及手机屏幕， 然后再对这些构件进行选择组合，最终装配成手机。图5 1 4 是手机组装过程的图例。图 5 1 5 是多种组装结果。图5 1 6 展示了设计主体在特定环境中的渲染效果。 图5 1 4 手机装配过程 4 5 山东师范大学硕士学位论文 6 1 本文的工作 第六章结束语 本文研究了结合遗传算法的粒子群优化模型的建立及其应用问题。基于隶属云的模糊 性和随机性，提出一种基于云模型的变异进化模型；针对创新设计的特点以及原有微粒群 算法的优缺点，提出了基于动态小生境的改进粒子群优化模型；以此为基础，构造了结合 遗传算法的粒子群优化模型，并将其应用于手机创新概念设计中，为设计师创新思路的开 拓提供了支撑平台。主要工作体现在以下方面： 1 提出一种基于云模型的进化机制 云是用语言值表示的某个定性概念与其定量表示之间的不确定转换模型，它把不确定 性概念的模糊性和随机性有机地结合在一起，成功地解决了定性概念与定量值之间的转 换。丽创新概念设计本身也带有一定的不确定性，基于此，本文在标准g a 的基础之上， 将云模型弓l 入了遗传变异之中，保留了原有算法的全局优化能力，能够克服原有遗传算法 的缺点，加快设计速度，拓宽设计思路，能够增强构件概念设计的创新性。 2 提出一神基于动态小生境的微粒群傀纯模型 自然界的小生境为新物种的形成提供了可能性，是生物界保持近乎无限多样性的根本 原因之一。现有的微粒群算法及其变种都有羞收敛速度慢、容易陷入局部极值问题，再针 对目前创新概念设计的特点，本文提出一种改进的基于动态小生境的微粒群优化模型。 3 将g a 与p s 0 相结合，提出结合遗传算法的粒子群优化技术 在动态小生境微粒群算法的基础上，弓| 入杂交及变异机制，使微粒群具有遗传特性， 杂交能充分利用现有的信息，而变异能够产生新的解以扩大搜索的范围，在新解产生时， 对其进行杂交，以产生更好的解，当搜索陷入停滞阶段时再对其进行交异，杂交和变异可 以互补的，将两者结合实现了优势互补，从而减少计算时间以及避免早熟现象。 4 。实现了一个基于结合遗传算法的粒子群优化技术的手杏凡创新设计系统 将结合遗传算法的粒子群优化技术应用于手机创新设计领域，设计并实现了二个手机 创新设计系统。系统三维引擎a c i s 为造型内核，采用s q ls e r v e r2 0 0 0 数据库系统，利用 v c 抖n e t2 0 0 3 在w i 荫o w s p 平台上开发完成。分别针对手机构件的设计、选择、组装 优化等等进行了实验分析，设计结果令人满意。 6 2 进一步的研究方向 本文对基于智熊算法的创新设计的研究还处在初步阶段，需要探讨和开展的工作尚有 许多，进一步的工作主要包括以下几个方面： l 。进一步改进结合遗传算法的粒子群优化模型 4 7 山东师范大学硕士学位论文 本文提巍的模型在一定程度上为设计人员创新思路的开拓提供支持，但设计中的细节 问题，如手机构件选择、组装中的若干因素尚未考虑在内，如何将这些约束条件加入模型 中，是一个值得研究的闻题。 2 基于粒子群优化模型的创新设计系统尚需进一步完善 手机设计本身是一项高度创新的工作，该系统只能从整体上展示手机模型，是一个忽 略细节的概念模型，函此需要设计实用的造型工具，完成造型过程中逐步细化的过程。 4 8 山孝毛嘻螽季l 警亭宁窆马箩茎曼蓄薹朝垂塞篓遥喜；菩萋耋童量辇i 蓁童，鼍害妻薹j 蓁：茎! i 圭妻雪一萋雩萝 妻霉；羹鬟塞羹篓薹至姜喜豢搴霉搴；主蔫! 参垂! 薹夏薹i 主篓萋莲l l i i 熏萼妻驴耋! l 堇攀l i 霎i ，饕星譬囊妻囊；蚕毒羹鬟誊一譬i l ij 露蠢雾 謇霉i 霪蓥震鐾兰l 乓耋垂主要霎j 蛩嚣l 妻g 霎己霎萎鋈善耋虿i 圭主说明并表示谢意。 学位论文作者签名： 砂莹、 导师签字： 学位论文版权使用授权书 本学位论文作者完全了解堂撞有关保留、使用学位论文的规定，有权保留并向国家有 关部门或机构送交论文莳复印件和磁盘，允许论文被查阅和借阕。本人授权堂楚可以将学 位论文的全部或部分内容编入有关数据库进行检索，可以采用影印、缩印或扫描等复制手 段保存、汇编学位论文。( 保密的学位论文在解密后适用本授权书) 学位论文作者签名：导师签字 签字曰 授权书) 学位论文作者签名：导师签字签字日期：2 。善年月弓p 匿签字日赣：2善年多月弓日 x 山东师范大学硕士学位论文 发表的论文： 研究生期间发表论文 1 ) 王慧，刘希玉。基于最具影嘲力粒子群优诧的静神经网络训练 朋，计黧枕工程与应 用，2 0 0 7 ，4 3 ( 1 8 ) ：6 9 7 1 2 ) 王慧，刘希玉。基于云模型的手机外观创新进化设计方法研究与实现 j 3 计算机工程与 应用，2 0 0 7 ，4 3 ( 3 3 ) ：1 0 8 一l l l 3 ) 王慧，刘希玉基于a c i s 和优化排料的手机创新设计研究与实现 j 计算机工程与设 计，基录用 4 ) h u iw a n g ， x i y ul i u r e s e a r c ha n da p p l i c a t i o no fp a r t i c l os w a r mo p t i m i z a t i o no n i 毯n i f o l d s c p r o c e e d i n g so ft h e2 0 0 7i n t e r n a t i o n a lc o n f e r e n c eo ni n d u s t r i a l d e s ig n ，s h e nz h e n ，c h 主n a ，c h i n a 麓a e h 主n ep r e s s p p 。2 5 2 9 5 ) x i y ul i u ，h o n gl i u ，h u iw a n g at o p 0 1 0 9 i c a lf