（计算机软件与理论专业论文）社会演化算法及其在tsp问题中的应用.pdf

社会演化算法及其在t s p 问题中的应用 摘要 组合优化是运筹学的重要分支，主要通过对数学方法的研究寻找离散 事件的最优编排、分组、次序或筛选等。大多数这类问题属于n p 完全问题。 当问题规模逐渐扩大时，其解空间呈组合爆炸特征，无法用常规的方法求 解。此类问题目前只能用启发式算法进行求解。旅行商问题( t s p ) 就是一个 经典的组合优化问题。 本文给出了一种基于社会演化算法求解t s p 问题的方法，该算法用认 知主体取代了传统遗传算法的基于编码的可行解生成方式；用基于“范式 学习与更新 的进化寻优机制取代了传统遗传算法中基于模仿基因的遗传 和变异的进化寻优机制，使其计算效率更优。 在本文的应用研究中，将社会演化算法和蚁群算法相结合，以蚁群算 法作为认知主体的推理过程，得到认知主体进行学习的初步范式，再以社 会演化算法中基于“范式的学习和更新”方式获得最优解。通过具体算例 实验仿真与t s p 已知最优解进行对比分析，结果表明，社会演化算法在种 群规模较小，迭代次数较少的情况下也可获得t s p 最优解。 在求解t s p 问题的基础上，对社会演化算法的各种参数的取值及其对 解的影响进行讨论，寻找一些可供人们参考的经验规律，对同类问题进行 简化处理。 最后，对全文的研究工作进行了总结，并对社会演化算法今后的发展 方向作了展望。 关键词：社会演化算法，蚁群算法，旅行商问题( t s p ) ，认知主体 s o c i a le v o l u t i o n a r yp r o g r a m m i n ga l g o r i t h m a n di t sa p p l i c a t i o ni nt s p a b s t r a c t c o m b i n a t o r i a l o p t i m i z a t i o n p r o b l e mi so n eo ft h em o s t i m p o r t a n t e m b r a n c h m e n to fo p e r a t i o n a lr e s e a r c h t h em a t h e m a t i c a lm e t h o d sc a nb eu s e d t os e a r c ho p t i m i z a t i o na r r a n g e ，g r o u p i n g ，s e q u e n c eo rr i d d i n go ft h ed i s c r e t e e v e n t s t h e s e p r o b l e m s b e l o n g t ot h e n o n p o l y n o m i a l c o m p l e t e ( n p c ) q u e s t i o n s w i t ht h ee n l a r g e m e n to ft h es c a l eo fq u e s t i o n ，t h es o l u t i o ns p a c e m a k e st h ec h a r a c t e r i s t i co fe x p l o d i n g u p ，i su n l i k e l ys o l v e dw i t hg e n e r a l m e t h o d s t h e s eq u e s t i o n sc a no n l yb es o l v e db ym e t a h e u r i s t i c st o g e tt h e a p p r o x i m a t es o l u t i o n t s pi sa c l a s s i c a lc o m b i n a t o r i a lo p t i m i z a t i o np r o b l e m am e t h o db a s e do ns o c i a le v o l u t i o n a r ya l g o r i t h mi sg i v e ni nt h i sp a p e rt o s o l v et s rt h ep r o p o s e dm e t h o dr e p l a c e si n d i v i d u a l si nt h et r a d i t i o n a lg e n e t i c a l g o r i t h mw i t hc o g n i t i v ea g e n t s i ta l s or e p l a c e st h em e c h a n i s mo fc r o s s o v e r a n dm u t a t i o nw i t ht h em e c h a n i s mo f “p a r a d i g ms t u d ya n du p d a t e ”t h e r e f o r e t h ep r o p o s e da l g o r i t h mh a sa na d v a n t a g ei nt h ec o m p u t a t i o n a le f f i c i e n c y i nt h i sp a p e r , s o c i a l e v o l u t i o n a r ya l g o r i t h mi s c o m b i n e dw i t ha n tc o l o n y o p t i m i z a t i o n f i r s t l ya n tc o l o n yo p t i m i z a t i o ni su s e da sc o g n i t i v ea g e n t s c o g n i t i v el e a r n i n g ，a n dt h e nt h eg l o b a lo p t i m u mi so b t a i n e db yp a r a d i g m s l e a r n i n ga n ds h i f t f i n a l l ys o m er e s u l t sa r ec o m p a r e dw i t ht h eo p t i m u mt h a t w e r ek n o w n ，t h er e s u l ti n d i c a t et h a ts o c i a l e v o l u t i o n a r yp r o g r a m m i n gw i t h l i f e w e ra g e n t sa n dl e s si t e r a t i v et i m e sc a na l s oc o n v e r g et h eo p t i m u m o nt h eb a s i co fs o l u t i o nt ot s p , d i f f e r e n tp a r a m e t e r si ns o c i a le v o l u t i o n a r y a l g o r i t h ma n dt h e i ri m p a c tt o t h er e s u l ta r ea n a l y z e d ，t r y i n gt of i n ds o m e e x p e r i e n c el a w st os i m p l i f i e dt h es a m ep r o b l e m s f i n a l l y , t h ew o r ko ft h i sp a p e ri ss u m m a r i z e da n dt h ep r o s p e c t i v eo ff u t u r e r e s e a r c hi ns o c i a le v o l u t i o n a r ya l g o r i t h mi sd i s c u s s e d k e yw o r d s ：s o c i a le v o l u t i o n a r y a l g o r i t h m ，a n tc o l o n yo p t i m i z a t i o n ， t r a v e l i n gs a l e s m a np r o b l e m ( t s p ) ，c o g n i t i v ea g e n t i i i 广西大学学位论文原创性声明和学位论文使用授权说明 原创性声明 本人声明：所呈交的学位论文是在导师指导下完成的，研究工作所取得的成果和相 关知识产权属广西大学所有，本人保证不以其它单位为第一署名单位发表或使用本论文 的研究内容。除已注明部分外，论文中不包含其他人已经发表过的研究成果，也不包含 本人为获得其它学位而使用过的内容。对本文的研究工作提供过重要帮助的个人和集 体，均已在论文中明确说明并致谢。 论文作者签名：蓝醺兹 学位论文使用授权说明 弘。夕年6 月夕弓日 本人完全了解广西大学关于收集、保存、使用学位论文的规定，即： 按照学校要求提交学位论文的印刷本和电子版本： 学校有权保存学位论文的印刷本和电子版，并提供目录检索与阅览服务； 学校可以采用影印、缩印、数字化或其它复制手段保存论文； 在不以赢利为目的的前提下，学校可以公布论文的部分或全部内容。 请选择发饰时间： 口即时发布口解密后发布 ( 保密论文需注明，并在解密后遵守此规定) 论文作者签名：蓝观诌导师签名：同p 吁f 月形日 广西大学硕士学位论文社会演化算法及2 t t c q 莹t s p 问题中的应用 1 1 研究背景与意义 第一章绪论 社会演化算法n 1 是一种建立在社会认知模型( s o c i a lc o g n i t i v em o d e l ，s c m ) 之上的算 法。社会认知模型的参照系统是人类社会，所以它的组织结构与人类社会本身有许多相 似的地方。社会认知模型由许多认知主体( c o g n i t i v e a g e n t ) 构成，这与人类社会由大量个 体构成相似。一个认知主体就是一个具有一定简单的推理、决策等认知能力的人工系统， 每一个认知主体都有独立的认知能力，经过一系列认知行为后可以得到一个局部最优 解。社会演化算法的思想基础是库恩的范式转换理论，其寻优机制是基于范式的确立与 更新，以及认知主体对范式进行学习的一系列智能认知行为。社会演化算法是一种优良 的寻优算法，对解决组合优化问题有很好的适应性和有效性。 旅行商问题( t r a v e l i n gs a l e s m a np r o b l e m ，简记t s p ) ，是一个较古老的问题。最早可 追溯到1 7 5 9 年e u l e r 提出的骑士旅行问题。1 9 4 8 年，由美国兰德公司的推动，t s p 问 题成为近代组合优化领域的一个典型的、研究最多的n p 难问题之一瞳3 ，但至今尚未彻 底解决。它不但具有广泛的应用背景，而且具有重要的理论价值。 由于t s p 问题形式简单、易于描述、且属于典型的n p 难问题，因此其作为算法研 究与验证的平台而被广泛研究。在t s p 问题上取得的理论或者实验成果，可以用于其他 的n p 难解问题。实际上，求解n p 难问题的许多方法都源自于t s p 问题的研究。 t s p 问题不但具有很大的理论价值，在许多工程应用问题中，如网络布线、物流配 送、电路板钻孔等，都直接是t s p 问题原型，或可归转化为t s p 求解问题。因此，寻 找一种有效地解决t s p 问题的算法具有重要的理论价值和应用背景。 综上所述，求解t s p 问题仍是当前的一个研究热点和难点。目前t s p 问题的求解 已有不少方法，如遗传算法、蚁群算法和模拟退火算法等，而社会演化算法作为一种新 的算法仍未见应用于求解t s p 问题，因此，将社会演化算法用于探索解决t s p 问题具 有较大的理论意义和应用价值。 r - 西大学硕士掌位论文社会演化算法及其在t s p 问题中的应用 1 2 组合优化问题 组合优化问题( c o m b i n a t o r i a lo p t i m i z a t i o np r o b l e m s ，c o p ) 研究的是如何有效分配 有限的资源，以达到需要的目标。组合优化问题涉及几乎所有的管理科学领域( 如财经、 市场、生产、调度、设备分配与布局等) ，以及工程技术( 如超大规模集成电路、电力 运输优化规划等) 等许多领域中，其中许多问题都已被证明是n p 完全问题。组合优化 问题的三个基本要素为：变量、约束和目标函数，变量为求解过程中的基本参数，约束 为对变量取值的限制，目标为函数表示可行方案衡量标准的函数。组合优化问题就是在 给定的约束条件下，求目标函数最优值的问题。 c o p 可用如下数学模型n 1 表示： m i ni ( x ，x 2 x n ) ( 1 1 ) 其中：t o ，1 ) ，j 1 ，2 ，刀) 。x 。= 1 代表第i 个决策变量被选中；否则未被选中。 c o p 的一个可行解是一个n 维决策向量x = g 。，x ：，x 。) ，它由二进制变量组成， 它也可以被看成是一个n 位二进位串a = x ，x ：x 。，与决策向量x 相对应。假设在一个 可行解中被选中的决策变量的所有序列数集组成一个集合为d 。，则 b c d ( 1 2 ) 其中，d 是所有决策变量序列数集的全集。 c o p 通常附加有各种限制条件。一种常见的限制称为“不相容性限制( i r ) ”，它是 指“一些变量不允许共存”。这种限制由于难以用数学公式来表示，因此比其它的限制 更难处理，很多算法在此遇到困难。 一般而言，遗传算法( g e n e t i ca l g o r i t h m ，g a ) 比其它算法更适于解决c o p 。然而 g a 也碰到由i r 引起的问题。假设x 。和z ，不相容，比如，它们在c o p 中由于i r 彼此 不相容。根据g a 的原则，初始群体由m 个个体组成，这些个体是随机生成的力位二进 制位串。因此很难保证一和x ，不同时为1 ，即便x 。和x ，在此处满足不相容的条件，在遗 传操作中也同样会遇到这样的问题。比如，在个体a 。中的第f 位和个体彳：中的第位不 同时为l ，如下所示： 2 广西大掌硕士g 堰筻论文社会演1 匕算法及其在t s p 问题中的应用 b n j | h b i t ( 1 3 ) a 1 = 1 ) ：a 2 = 0 ) 但很难保证由a 。和a 2 经过“交叉”和“变异”产生的新个体都满足使x 。和不同时为 1 。 1 3t s p 问题 1 3 1t s p 问题的定义 t s p 问题可描述如下：给定，z 个城市和每两个城市f n 】的距离( 或给定拧个城市和各 城市的坐标，这样同样可以求任意两个城市间的距离) ，一个旅行商自某一个城市出发 巡回售货，旅行商应该如何选择路线，使每个城市经过一次且仅一次，以完成一个回路， 并且路径最短。t s p 问题可细分为对称和非对称问题两大类。 用图论的术语表示，假设有一个图用矿= ( g ，e ) 表示，其中1 1 是顶点集表示行个城 市，e 是边集表示各个城市之间的距离。非负矩阵d = 吒 表示各个边的距离，其中元 素z ，表示城市f ，间的距离。则对变量d 的约束是： ( 1 ) 每个元素是非负整数，即 谚，0 l s f ，j 船 ( 1 - 4 ) ( 2 ) 对角线上元素为0 ，即 z ，= 0 l f ，z 特别对于对称t s p 问题，其矩阵是对称矩阵，即 d 口= dj l 、s i ，js n ( 3 ) 任意三个元素满足三角不等式，即 吼+ t z 1 f ，k 疗 ( 1 5 ) ( 1 - 6 ) ( 1 7 ) t s p 问题的一个解可表示为万= ( 乃，乃，死) ，其中巧( 1 f 刀) 是该路径中第f 个经 广西大掌硕士掌位论文 社会演化算法及其在t s p 问题中的应用 过的城市。只有当乃乃，f 时所得的解才为可行解。所有可行解的集合构成解空间s ， 即 s = 补城市的所有循环排列) 。 t s p 问题解空间的规模为鱼亏坐，路径长度仁) = 喜吒吒+ 。是该问题的目标函数。 t s p 问题的目标是使路径长度最短，即使目标函数厂( 万) 最小。 1 3 2t s p 问题的标准测试库 t s p l i b 。”是由一系列t s p 问题以及相关问题组成的问题库，它是r i c e 大学并行计 算研究中心于1 9 9 0 年举行的t s p 问题研讨会上建立，最初包含8 4 个测试问题，并且收 集了一系列国际知名研究人员对t s p 问题的研究成果，之后不断更新扩充。目前该问题 库己成为国际上研究t s p 问题的通用标准测试库。 在该t s p l i b 中包括：对称t s p 问题( s y m m e t r i et r a v e l i n gs a l e s m a np r o b l e m ) 、哈密 尔顿回路问题( h a m i l t o n i a nc y e l ep r o b l e m ) 、非对称t s p 问题( a s y m m e t r it r a v e l i n g s a l e s m a np r o b l e m ) ，容量限定的车辆路径问题( c a p a c i t a t e dv e h i c l er o u t i n gp r o b l e m ) 等， 各类问题文件的后缀名分别为：t s p 、h c p 、a t s p 、c v r p 。对于部分对称t s p 问题和非对 称t s p 问题，t s p l i b 中还收集了到目前为止已知的全局最优解，其文件名为相应t s p 问题名+ o p t t o u r 。 一般来说，研究者们在使用t s p l i b 时，通常挑选那些全局最优解己知的实例，将 他们算法的运行结果与这些实例的全局最优解的环路长度相比较。 1 3 3t s p 问题求解算法 迄今为止，人们已提出了许多有效地解决t s p 问题的算法，归结起来，大致可分为 两类：精确算法和近似算法3 。精确算法就是找到t s p 问题的最优解，包括分枝定界法 嘲7 。、割平面法嘲例n 0 3 、分解法等，这些算法只能计算小规模的问题，并且算法实现比 较复杂，实际应用中存在很大的局限性。近似算法是在合理的时间内寻找t s p 问题相对 较优的解，主要有近邻法、边交换法、退火算法n2 1 、蚂蚁算法n 引、神经网络算法n4 1 、 遗传算法5 1 、混合优化算法等，这类算法特点是智能化，主要面向大规模的应用问题。 下面对遗传算法和蚁群算法在求解t s p 问题时的研究与改进进行概述。 4 广西大学硕士掌位论文社会演化算法及其在t s p 问题中的应用 a 遗传算法 遗传算法是创立于2 0 世纪6 0 年代末，由美国m i c h i g a n 大学的h o l l a n d 博士基于达 尔文的进化论和孟德尔的遗传学原理提出。h o ll a n d 最初设计的遗传算法，一般称为简 单遗传算法( s i m p l eg e n e t i ca l g o r i t h m ，简称为s g a ) 。该算法模拟了自然选择及在遗传 过程中发生的繁殖、交叉和变异现象，根据适者生存、优胜劣汰的自然法则，通过选择、 交叉和变异逐代产生候选解，最终得到较优的个体。从1 9 8 5 年在美国卡耐基梅隆大 学召开的第一届国际遗传会议到1 9 9 7 年5 月i e e e 的t r a n s a c t i o n so ne v o l u t i o n a r y c o m p u t a t i o n 创刊，遗传算法作为具有系统优化、适应和学习的高性能计算和建模方法 的研究日趋成熟。 与传统方法解决优化问题相比，遗传算法特别适应于解决些较困难的组合优化问 题，但对于t s p 问题特别是大规模t s p 问题还不是很有效。因此人们提出了许多方法 来改进遗传算法，包括设计t s p 问题专用算子、加入t s p 专用领域的局部搜索、保持 种群的多样性等。t s p 问题专用算子，比如部分匹配交叉( p a r t i a l l ym a t c h e dc r o s s o v e r ， 简称p m x ) 惦1 、循环交叉( c y c l ec r o s s o v e r ) m 1 、边重组交叉( e d g ea s s e m b l yc r o s s o v e r ) m 1 、 最大保留交叉( m a x i m a l l yp r e s e r v i n gc r o s s o v e r ) n 引、边组装交3 之( e d g ea s s e m b l yc r o s s o v e r ) 啪1 和反序重组算子( i n v e r - o v e r o p e r a t o r s ) 心订都能提高遗传算法解决t s p 问题的性能。加 入领域专家的局部搜索则同时拥有遗传算法的全局最优性又具有局部搜索的收敛性 2 2 m 州2 4 1 ，而保持种群的多样性则能避免早熟收敛瞳5 删。 b 蚁群算法 蚁群优化( a n tc o l o n yo p t i m i z a t i o n ) 他”算法兴起于上世纪九十年代，是模拟蚂蚁觅食 行为的仿生类构造型进化算法，其主要通过模仿蚂蚁依赖信息素进行通信而显示出的社 会协同性，以一个贪心法为指导的自催化过程引导每只蚂蚁的行动。 最初d o r i g o 等人将蚂群算法用于求解o l i v e r 3 0 、n u g e n t 3 0 、k r a r u p 3 0 问题( 3 0 个城 市的t s p 问题) 瞳7 1 等较小规模的t s p 问题，得到了非常满意的效果。但在将蚁群算法用 于解决更大规模的t s p 问题上时，得到的结果却不是很理想。原因为蚁群算法主要通过 正反馈机制强化一些已产生的次优解，通过迭代，次优解上的信息素不断得以强化，从 而使大多数蚂蚁都选择了这几条路径。在小规模t s p 问题中，最优解往往可这些次优解 中产生。但在大规模t s p 问题，会有多个局部最优解，在迭代计算中，蚂蚁仅重复经过 其中一条或几条路径，由此构造出完全相同的解，从而出现早熟和停滞等现象。 另外，该算法的收敛搜索时问较长。由于蚂蚁运动的随机性，虽然彼此间可通过交 社会演化算法及其在t s p 问题中的应用 换信息素向着最优路径进化，但在大规模t s p 问题中，要在短时间内搜索到一条较好的 路径是很难的。这是由于在进化的早期，各路径上信息素差别较小，经过较长时间，才 能通过信息正反馈机制使得较好路径上的信息素得到增大，并明显高于其他路径，这一 过程需要较长的时问。 在d o r i g o m 等人提出蚁群算法后，针对其在求解大规模t s p 问题存在的收敛速度 慢、求解精度不高、容易早熟等问题，后续研究者给出了一系列的改进。由于蚁群算法 最早用于解决t s p 问题，以致后来所有改进或新算法的提出大都以t s p 问题作为测试 用例。 1 4 本文主要内容及结构安排 本文主要研究社会演化算法及其在旅行商问题( t s p 问题) 的应用。社会演化算法 由我国学者余贻鑫于2 0 0 2 年提出口1 ，它是一种基于范式转换的全局搜索算法，它是建立 在社会认知模型之上的一种算法。本文主要研究内容如下： 第一：将社会演化算法和蚁群算法相结合，以蚁群算法作为认知主体的认知推理过 程，再以范式的学习和更新方式获得最优解，提出一种求解t s p 问题的社会演化算法。 第二：在社会演化算法求解t s p 问题的基础上，本文对社会演化算法中的参数进行 了全面的讨论，包括：认知推理的迭代次数日、认知主体个数a g e n t n u m 、最优范式的 学习概率p 。、最优范式衰减速率、个体变异概率阈值口、个体行为变异概率阈值。 本文的结构安排如下： 第一章绪论，介绍论文的研究背景和意义，并简单介绍了组合优化问题和t s p 问题 及本文的结构安排。 第二章详细描述了基本社会演化算法的背景、思路、方法及研究现状。 第三章针对t s p 问题应用社会演化算法，介绍算法的详细解决方法，并给出仿真实 验结果。 第四章在解决t s p 问题的基本上，讨论了社会演化算法中的各种参数的取值及其对 算法性能的影响。 第五章对本论文的工作进行了总结，说明算法存在的问题及进一步研究的方向，并 对未来的工作作出了展望。 6 广西大掌硕士掌位论文社会演化算法及其在t s p 问题中的应用 2 1 引言 第二章社会演化算法 近年来，认知科学( c o g n i t i v es c i e n c e ，c s ) 的分支之一社会分布认知( s o c i a l l y d i s t r i b u t e dc o g n i t i o n ，s d c ) 引起起来越多学者的关注。认知科学研究包含两个方向：个 体认知和社会群体认知。几十年来，对个体认知的研究已经取得众多成果并得到广泛应 用；而近些年，社会群体认知的研究才作为认知科学研究的一个分支，得到研究者的重 视。 对群体智能的研究源于人工智能领域，相关的研究成果包括遗传算法、蚁群算法及 多主体系统。也有部分研究不属于人工智能的领域。文献【2 8 】介绍了一种行为遗传概念， 文中提出了进化个体行为设计的观点。该方法尝试改变传统的经典进化范式的观点，该 文中认为比特串不该是个体的染色体，而是行为的结果。文献 2 9 】通过模仿灵长类社会 设计了一种用于多个体系统的社会认知模型。 这些研究提出了群体智能的概念，并表明：通过一群具有社会结构的简单智能体之 间的交互作用，可实现一些复杂的智能现象和智能行为，无需设计专用的、复杂的单一 智能体来实现同样的目标。 随着社会群体认知的研究逐渐发展为单独的学科，其研究对象也从蚁群这样的低级 智能群体转向具有高级智能的哺乳动物社会群体，主要的研究内容包括其社会的内部结 构，组织形式以及社会演化等口引。在人工智能研究时代，各种群体智能方法的一个主要 用途是解决各种工程组合优化问题，它们都表现出了良好的性能。 社会演化算法( s o c i a le v o l u t i o n a r yp r o g r a m m i n g ，s e p ) 就是基于社会群体认知基础 上的全局搜索算法。3 。 2 2 社会认知模型 社会演化算法是建立在社会认知模型( s o c i a lc o g n i t i v em o d e l ，s c m ) 之上的一种算 法。s c m 的参照系统是人类社会，因此它的组织结构与人类社会本身有很多相似之处。 分析一个社会通常包括两方面的研究。一个是社会组织结构；另一个是社会发展( 也 7 广西大掌硕士学位论文 社会演1 匕算法及其在t s p 问题中的应用 可以认为是进化) 规则，建立社会认知模型也需要两方面的研究。因此要引用一些社会 学和哲学方面的观点。 首先，给出人类社会和s c m 的三个相似之处。 第一，人类社会由大量个体组成。类似地，s c m 也由大量的认知个体组成，它与 g a 中“群体”和“个体”的概念相似。但每个认知主体有独立的认知能力，而不像g a 中的个体只有代码的组合。 第二，人类社会由大量社会规则来组织( 一般有法律、道德和习惯等) 。对于s c m 来说，对c o p 的所有约束与“社会规律”有相似的功能。一些约束条件如法律必须严 格执行，一些经验规则也可认为是松散的限制，这些松散的限制如道德和习惯一样有相 同的功能。 第三，在一个真实的社会中，人们的行为通常被限制在一定的行为空间中，这些行 为空间由社会规则来约束。在合法的行为空间，人们可以自由地选择，但所做的每个选 择会影响接下来的选择。实际上，人类的认知行为是一个动态的过程，它由人类不断地 从决策空间转换和删减而来。在s c m 中，所有认知主体都基于自己对约束的理解而独 立进行活动。和人类一样，认知主体的行为过程也是动态的。 一个认知主体可以是一个附以一些简单认知能力的人工系统，比如推理、计划和决 策等等。由于不同领域的人类专家有不同的知识结构，应用于不同c o p 的个体应该有 自己的设计方案。虽然不同个体都有各自的内部结构，但是它们可以有相同的外部行为 规律。认知主体的内部行为可设计为基于知识、基于规则、基于模糊逻辑和基于人工神 经网络等等。各种个体统一的行为规则是分析社会组织的所要关注的主要问题。 每个认知主体的最终认知结果是c o p 的一个可行解，它由一系列的认知行为产生。 用数学的观点表示，可行解只是被选择的决策变量的一系列数集( d 。，假设d 。由d 中 的d ( d ，z ) 个元素组成) 。所以，所有个体的统一行为规则意味着一个接一个确定d 。中 元素的相同的行为过程。此处的“一个接一个”不是说元素是按顺序从第一个到最后一 个地确定，它可以是一个任意的序列。 假设a 由o 一1 ) 个元素组成，它们在确定第f 个元素之前已经确定了。显然d ：也是d 的一个子集。要确定第f 个元素时，砭补集4 = d 一口的所有元素都是被选的候选元素， 可以将它们称为候选决策向量序列数集砬。但是由于不允许出现一些向量共存的限制， 社会演化算法j - a 其在t s p 问题中的应用 并不是d c 中的所有元素都被允许选择；眈中一个或多个元素可能与已经确定的一些元 素有冲突，认知主体需要排除d c 中的冲突元素。d c 中可选的所有元素组成的集合叫“允 许决策向量序列数集( 见) ”。反中的第f 个元素可以通过随机选择d 口中的一个元素来确 定( 这里需要使用一个统一的随机数生成器) 。 以上介绍的确定d ：中的第f 个元素的过程是单个认知主体整个认知过程的基本行 为，单个认知主体需要时时根据约束条件决定它的下一个“合法行为 。经过一系列的 认知行为，就得到c o p 的一个可行解。单个认知主体的认知过程如图2 1 所示。 以上介绍的认知主体只具备基本的智能，一些比较聪明的个体不但可以根据一些规 则进行推论，而且可以根据积累的经验给出一些预测。对于这种较聪明的的s c m ，个 体和社会都需要一些学习机制。在此，可将认知科学和智能研究的理论用于社会认知模 型以提高它的性能。 蒯重复 ： | ，2 - 当 0 所有规则 合 d 。 爿认知个体h 耽 法 的 j j r l j 行 为 冲突元素 认知主体的认知过程 卜个可行解l 1 拟知融敝 图2 1 单个认知主体的认知过程 f i g 2 1t h ec o g n i t i o np r o c e s so fa na g e n t 2 3 社会认知模型的进化 2 3 1 范式的转换 社会认知模型中的进化规则基于美国哲学家库恩的“范式转换”理论。 库恩于1 9 6 2 年在其著作科学革命的结构( t h es t r u c t u r eo f s c i e n t i f i cr e v o l u t i o n s ) 9 广西大学硕士学位论文社会演化算法及其在t s p 问题中的应用 一书中，提出了对科学革命的统一理解。他认为：科学发展过程的实质就是“范式转换” ( p a r a d i g mt r a n s i t i o n s ) 。科学的研究和思想可定义为范式，范式由正确的理论、典型的实 验和可信的方法构成。科学家们接受主要的有代表性的范式，并通过精练数据、解释模 糊数据、建立标准和对现象提供更精确的测量方法来扩展它的范围。然而，最后，他们 的努力可能会产生不能解决的理论问题或实验异常。这暴露了一个范式的不足和相互间 的矛盾，由此引发危机，只有通过智力进化以新的范式取代旧的范式才可解决这样的危 机。 库恩的著作改革了科学的历史和哲学的观点，且其中的范式转换概念可扩展到政治 学、经济学、社会学等，甚至是商业管理中。这个概念也可用于粗略描述人类社会的发 展规律。人类的生活是一个辩证的生产活动，这种活动不但要遗传现有的范式( 文化、 科学技术和艺术等) ，还要突破它们。这里范式转换的机制可以认为是一种优化机制， 从现存生物进化历史比人类社会发展历史要长这一事实，可在某些程度上证明这个机制 可能比基于达尔文进化论的g a 更有效， 在s c m 中，引入范式转换的机制以提高社会集体认知能力。c o p 的一个可行解由 个体的一系列认知行为产生，一些较优可行解的行为集可以为下一代个体的认知行为提 供范式，行为方式遗传的思想与文献 3 2 1 的e t h o g e n e t i c 的概念相似。 2 3 2 范式的建立与转换 范式的建立和转换应得到深入的研究，在s c m 中使用一种简单的原则，如下： 要选择的决策变量中的m 个序列数集池，f 1 ，2 ，m ”参照m 个不同的局部最优 解，这些局部最优解由前期进化过程得到，它们可以作为下一代进化过程的m 个范式。 精确原则的意思是，对于找到的每一个新的局部最优解x ) ，即从鼠中选择的决策 变量的序列数集可以作为一个新的范式来确定。我们假定总共有m 个范式，对所建立的 目标函数有较高适应性的范式将取代一些适应性较差的范式，在整个进化过程中，m 个 范式是一个动态更新的过程。 从数学的角度来看，m 个范式按适应度函数降序排列。如果在第g 代找到一个 新的局部最优解，该解比现存m 个范式的一些范式有更优的适应性，可将与该局部最优 解相应的范式插入m 个有序范式的适当位置中，插入点以后的那些范式依次向后替换， l o 社会演化算法及其在t s p 问题中的应用 并将现存的第硝个范式遗弃，按如下规则重写它们的序列： 如果 厂( 而j - ! ， ：j - t ，j 1 ) 厂( 砰，砭g ，巧) 厂( ，) 则 硝= 磷，剧“= 彬，球= 掣一。 2 3 3 对现有范式的继承( 认知主体对范式的学习) 如上所述，一个范式也只是决策变量序列数集p ) 的一个子集( n ) 。一个新的认知 主体通过复制子集皿中的一些元素而继承现有的一个范式。具体地说，遗传过程也就 是每一步确定如2 2 所述色中元素的过程，候选决策向量序列数集4 不再是砭，而是 从所个范式中选择一个，被选择的范式( a ) 可直接被当作皿，使用“轮盘赌”的方法 来选择一个范式，即第f 个范式的选择概率如下： 胪善 z i = l 其中z 是第i 个范式的目标适应度函数。 假定有一个随机数r ，2 d 【o ，1 】，则“轮盘赌”的规则如下： 如果： j - ib 尺耐 jb ，：0 ，2 ，肌) ( 2 1 ) ( 2 2 ) 则第个范式被选择。 例外：当认知主体由它的行为序列确定e 中的一个元素时，可能出现由m 个范式得 到的可选决策变量数集眈是空集的情况。在这种情况下，如下所定义的集合巧可以 被认为是“候选决策就是序列数集d c 。 巧= u 堪 j ；i 也就是d ，是肌个范式并集的补集。 ( 2 - 3 ) 广西大掌硕士学啦论文社会演化算法及其在t s p 问题中的应用 2 3 4 对范式的突破 一方面，一个真实的社会需要规则和法律来规范和组织个体。另一方面，社会也要 有些创造性机制允许一些个体具有变革精神，这样社会就可以不断向更高的层次发展。 与现实社会相似，s c m 也有些创造性机制让一些认知主体能突破现有范式的局限， 使它拥有全局优化能力，实现步骤如下： 第一步：设置两个阈值，一个是个体变异阈值口，另一个是行为变异阈值。阈值口 判断认知主体是否具有对传统规则的叛逆特性，而给出每个具有叛逆特性的个体的行 为叛逆概率。 第二步：在每个认知主体进行认知活动之前，由统一随机数生成器生成一些随机数 作为该个体的行为变异概率，以判断个体是否具有叛逆特性。如果该随机数小于口，则 个体不具有叛逆特性，它的行为严格遵循2 3 3 所介绍的认知过程，否则转入第三步。 第三步：如果在第二步判断一个个体具有叛逆特征，则在该个体的每次认知行为前， 由统一随机数生成器生成一个随机数作为它的行为变异概率，以判断此次认知行为是否 突破现有范式。如果该随机数小于，则它的认知行为仍不具有叛逆特性，严格按照 2 3 3 所介绍的方法得到新的个体。否则它就是一个叛逆个体，遵循2 3 3 所介绍的例 外情况产生新的个体。 1 2 广西大学硕士掌位论文 社会演化算法及其在t s p 问题中的应用 2 3 5s c m 草图 图2 3s c m 草图 f i g 2 3s k e t c hm a po fs c m 2 4 社会演化算法与遗传算法寻优机制的比较 社会演化算法的思想是库恩的范式转换理论，传统遗传算法的思想是达尔文的进化 论，这两个方法的寻优机制也是基于这两种不同的思想基础。传统遗传算法通过“选择、 交叉、变异”等一系列对编码的操作实现寻优，而s e p 则是通过范式的确立与更新、认 知主体对范式进行学习等智能认知行为实现寻优。两种寻优机制均是进化优化，其方法 体系都是基于群体进化、优胜劣汰的思想，在具体技术手段也有相同的地方，但它们仍 有本质上的区别。在社会演化算法中，由认知主体基于模仿人们认知过程的一系列决策 行为来得到问题的一个可行解；在其进化过程中，以基于范式学习与更新方式实现进化 寻优机制。 1 3 广西大学硕士学位论文 社会演化：算法及其在t s p 问题中的应用 社会演化算法的基于“范式学习与更新 的进化寻优机制与传统遗传算法的基于“模 仿基因的遗传和变异”的进化寻优机制的目的都是继承优良信息。它们之间的本质区别 为b 3 1 ：1 ) 传统遗传算法中优良信息的传播是一代传给一代的，不能隔代相传，所以没 有打破代的限制，而在s e p 中，范式是独立于群体而存在的，而且其存在时间不受“代” 的限制，直到被更好的范式所替换为止。因此，s e p 中优良信息的传播是持续而稳定的。 2 ) 传统遗传算法中个体所继承的基因只是来源于上一代群体中的两个个体，而s e p 则没有这个限制，认知主体可以继承多个甚至所有范式的优良信息。由以上两点可以看 出，s e p 中优良信息的传播是超越“空间( 两个个体) ”和“时间( 代) ”的限制的。 2 5 社会演化算法的现状 本文所引用的社会认知模型及其上的社会演化算法，在工程应用、聚类、文本聚类 方面，显示了很好的有效性和优越性。 文【1 】提出的社会认知模型( s o c i a lc o g n i t i v em o d e l ，s c m ) ，对于求解带有约束条件的 n p 难组合优化问题具有很好的适应性。在这一模型的基础上，该作者针对配电网优化 规划这一具体问题提出了一种新的社会演化算法，并对配电网进行优化规划，显示了很 好的优越性和有效性。该算法自提出并成功用于配电网优化规划后，相继被研究者用于 求解机电组合问题 3 3 】、聚类问题 3 4 】以及文本聚类问题【3 5 】。在聚类和文本聚类问题中， 研究者针对具体问题的特征，将社会演化与k 均值算法相结合，通过与传统遗传算法与 k 均值算法相结合所得结果比较，发现基于社会演化算法的方法效率和性能略高。同时 在文 3 6 】中，研究者在认知主体对范式的背叛中提出一种混沌变异算子，并将其与k 均 值结合，实验结果表明，基于社会演化算法的求解方法在效率方面得到了提高。 1 4 社会演化算法及其在t s p 问题中的应用 第三章基于社会演化算法求解t s p 问题的新方法 3 1 引言 蚁群算法是目前解决t s p 问题的一种较优的算法，本章将社会演化算法和蚁群算法 相结合，以蚁群算法作为认知主体的推理过程，再以范式的学习和更新方式获得最优解， 提出一种新的求解t s p 问题的社会演化算法。 3 2 蚁群算法简介 蚁群算法口刀汹m 9 1 兴起于上世纪九十年代，是一种随机搜索算法。该算法基于对自然 界真实蚂蚁的集体觅食行为的研究，模拟真实蚂蚁的协作过程。蚂蚁在寻找食物的过程 中，会在所经路径释放一种称为信息素( p h e o r m o n e ) 的物质，由此形成信息素轨迹。蚂蚁 间通过信息素传递信息。当它们在选择路径的时，将以概率选择信息素浓度大的路径。 大量实验表明，蚂蚁通过信息素寻找路径的方式可发现最短路径。即当食物源和巢 穴之间有多条路径时，蚂蚁通过信息素轨迹可发现巢穴和食物之间的最短路径。 蚁群算法的主要特点概括如下： ( 1 ) 分布式计算、正反馈机制和贪婪式搜索相结合； ( 2 ) 具有很强的并行性； ( 3 ) 更好的可扩充性； ( 4 ) 概率型的通用全局优化方法； ( 5 ) 不依赖于优化问题本身的严格数学性质，诸如连续性、可导性。 自从由意大利科学家m d o r i g o 等人于1 9 9 1 年首先提出蚂蚁系统( a n ts y s t e m ，a s l 并在t s p 问题上取得成功后，蚁群优化算法在求解j o b s h o p 问题n 引、二次分配d 引、图着 色问题h 、车辆调度n2 i 、通信网络负载问题的处理h 3 1 以及集成电路设计1 中都取得了较 好的结果。 广西大掌硕士掌位论文社会演1 匕算法及其在t s p 问题中的应用 3 3 基于社会演化算法求解t s p 问题的新方法 本方法使用m a t l a b 7 0 进行仿真，文中所使用的函数、代码说明均来自m a t l a b 7 0 。 3 3 1 认知主体的推理过程 在社会演化算法中，每个个体都是智能的，具有独立的认知能力。以下是基于蚁群 算法的认知过程。 蚁群算法h 5 1 的认知过程如下：蚂蚁七 = 1 , 2 ，脚) 在运动过程中，根据各条路径信 息素数量决定转移方向。禁忌表幻6 甜。 = 1 , 2 ，脚) 用来记录蚂蚁后