（计算数学专业论文）量子粒子群算法及其应用.pdf

中文摘要 优化问题是工业设计中常遇到的问题 为了解决各种各样的优化问题 已经提出了许多优化算法 比较著名的有蚁群算法 遗传算法等 e b e r h a r t 博士和k e n n e d y 博士在1 9 9 5 年提出了一种新的算法 粒子群优化 p a r t i c l e s w a r mo p t i m i z a t i o n p s o 算法 该算法从随机解出发 通过迭代寻找最优 解 并通过适应度来评价解的优劣 这种算法以其参数少 形式简单 精度 高 收敛快等优点引起了学术界的重视 并且在解决实际问题中展示了其优越 性 为了更好地改善其收敛性 s u n 等人2 0 0 4 年在标准的p s o 基础上提出了 量子粒子群 q u a n t u m b e h a v e dp a r t i c l es w a r mo p t i m i z a t i o n q p s o 使得粒 子可以在整个可行解的空间中进行搜索 从而寻求全局最优解 因此比p s o 算法具有更好的全局收敛性和搜索能力 本文首先介绍了p s o 及q p s o 的算法思想 流程 参数 并对算法进行 了数学分析以及介绍了几种改进的p s o 和q p s o 算法 接着在q p s o 的基 础上提出一种改进的算法 利用柯西变异来替代q p s o 中的随机数 由于柯 西分布具有较长的两翼的特点 使得算法可以更快的跳出局部最优点 最后 在q p s o 的基础上对一些优化问题进行应用并求解 尤其是一些复杂的规划 问题的求解 通过数值实验更好的说明了q p s o 算法的优越性 文章最后对全文总结并展望了未来 关键词 优化问题 粒子群算法 收敛性 量子粒子群 a b s t r a c t 英文摘要 o p t i m i z a t i o np r o b l e mi so f t e ne n c o u n t e r e di ni n d u s t r i a ld e s i g np r o b l e m s i no r d e rt os o l v eaw i d er a n g eo fo p t i m i z a t i o np r o b l e m s w eh a sd e v e l o p e dal o t o fo p t i m i z a t i o na l g o r i t h m s s u c ha sa n tc o l o n ya l g o r i t h m g e n e t i ca l g o r i t h ma n d s 1 9o n t h ep a r t i c l es w a r mo p t i m i z a t i o n p s o o r i g i n a l l yd e v e l o p e db yk e n n e d y a n de b e r h a r ti n1 9 9 5 t h ea l g o r i t h mi ss t a r t i n gf r o mar a n d o ms o l u t i o n a n d t h r o u g ht h ef i t n e s st oe v a l u a t et h es o l u t i o n s t h i sa l g o r i t h mw i t hi t sl e s sp a r a m e t e r s s i m p l ef o r m h i g hp r e c i s i o na n df a s tc o n v e r g e n c ea d v a n t a g e sa t t r a c t e dm o r e a n dm o r ea c a d e m i ca t t e n t i o n a n di td e m o n s t r a t ei t ss u p e r i o r i t yi ns o l v i n gp r a c t i c a lp r o b l e m st o i no r d e rt oi m p r o v et h ec o n v e r g e n c e t h eq u a n t u m b e h a v e d p a r t i c l es w a r mo p t i m i z a t i o n q p s o d e v e l o p e di n2 0 0 4b ys u n a n do t h e r s w h i c h b a s e do nt h es t a n d a r dp s o i nt h eq u a n t u ms p a c e p a r t i c l e sc a nb es e a r c hi nt h e w h o l ef e a s i b l es o l u t i o ns p a c e t h e r e b yw ec a no b t a i nt h eg l o b a lo p t i m a ls o l u t i o n t h e r e f o r e q p s oa l g o r i t h mi sag l o b a lg u a r a n t e e da l g o r i t h m w h i c ho u t p e r f o r m s o r i g i n a lp s oa l g o r i t h mi ns e a r c hc a p a b i l i t i e s t h i sp a p e ri n t r o d u c e st h ea l g o r i t h mi d e a a l g o r i t h m i cp r o c e s s a l g o r i t h m i c p a r a m e t e r so ft h ep a r t i c l es w a r ma n dq u a n t u m p a r t i c l es w a r mo p t i m i z a t i o n a l g o r i t h m t h e nw ed ot h em a t h e m a t i c a la n a l y s i st ot h ea l g o r i t h m sa n di m p r o v e t h ea l g o r i t h m s a f t e rt h a tw ei m p r o v e dt h eq p s oa l g o r i t h mu s et h ec a u c h y m u t a t i o nt or e p l a c er a n d o mn u m b e ro ft h eq p s o a st h ec a u c h yd i s t r i b u t i o n f e a t u r e sm a k et h ea l g o r i t h mc a nb ef a s t e ro u to fl o c a lm i n i m a f i n a l l y w ec a n m a k eu s eo ft h eq p s ot os o l v es o m eo p t i m i z a t i o np r o b l e m s e s p e c i a l l y w ec a n s o l v es o m eo fc o m p l e xp r o g r a m m i n gp r o b l e m s n u m e r i c a le x p e r i m e n t si l l u s t r a t e t h es u p e r i o r i t yo ft h eq p s o f i n a l l y t h ef u l lt e x to ft h ea r t i c l es u m m a r i z e sa r eg i v e nw i t hl o o k e dt ot h e l l f u t u r e k e y w o r d s o p t i m i z a t i o n p a r t i c l es w a r mo p t i m i z a t i o n c o n v e r g e n c e q u a n t u m b e h a v e d p a r t i c l es w a r mo p t i m i z a t i o n 1 1 1 西北大学学位论文知识产权声明书 本人完全了解西北大学关于收集 保存 使用学位论文的规定 学校有权保留并向国家有关部门或机构送交论文的复印件和电子版 本人允许论文被查阅和借阅 本人授权西北大学可以将本学位论文的 全部或部分内容编入有关数据库进行检索 可以采用影印 缩印或扫 描等复制手段保存和汇编本学位论文 同时授权中国科学技术信息研 究所等机构将本学位论文收录到 中国学位论文全文数据库 或其它 相关数据库 保密论文待解密后适用本声明 学位论文作者签名 超指导教师签名 w o 年莎月f oe t九 拜6 月r o e t 西北大学学位论文独创性声明 本人声明 所呈交的学位论文是本人在导师指导下进行的研究工作及取得的研究 成果 据我所知 除了文中特别加以标注和致谢的地方外 本论文不包含其他人已经 发表或撰写过的研究成果 也不包含为获得西北大学或其它教育机构的学位或证书而 使用过的材料 与我一同工作的同志对本研究所做的任何贡献均已在论文中作了明确 的说明并表示谢意 学位论文作者签名 狐兰 弘如年6 月忆日 西北大学硕士学位论文 1 1 群体智能算法 第一章绪论 最优化是一门应用性很强的学科 主要研究系统在某些前提下寻找最优的 结果 因此涉及人工智能 计算机控制 模糊系统等多个不同学科 随着计 算技术的发展 最优化问题己成为当今科学研究的热点 数学上 最优化问 题 1 一般描述为如下形式 m i n f x s t z x zi h i x 0 i 1 2 仇 1 其中y x 为目标函数 h i z 为约束集x 中的约束函数 如果约束集 为x r n 则称 1 为无约束优化问题 对于优化问题 1 可通过某些方 法 如惩罚函数法 1 等 转化为无约束问题去求解 最优化问题的求解主要分为 古典算法和启发式算法 古典算法始 于1 9 4 7 年d a n t i z i g s u o 提出的单纯形法 随后又出现了梯度法 信赖域法 牛顿法等等 这些算法一般都要求有严格的数学推导和证明才能得出最优解 当实际问题变的比较复杂时 这些算法在求解时将会不可避免地陷入到局部最 优解 这些年随着计算机的发展 一些复杂的优化问题 如混合整数非线性规 划等 能通过借助计算机的启发式算法来求解 在这些算法中我们引入了 新的搜索策略 并通过大自然中的经验 运行规律得出 例如 m e t r o p o l i s 在1 9 5 3 年提出的模拟退火算法 2 这是通过模拟物理中物质的结晶过程而 得出的 h o l l a n d 在1 9 7 5 年提出的遗传算法 3 则是通过自然界的生物进化 启发而得出的 2 0 世纪9 0 年代 研究员从基础的进化算法 提出了群体智能算法 这 是一种新兴的优化方法 它指的是一种智能的行为 是群居性的生物通过 合作表现出的 如蚁群算法 粒子群算法等等 它们都是以群体生物的智 1 第一章绪论 能行为条件 通过计算机的仿真得来的 其中 蚁群算法 4 a n tc o l o n y o p t i m i z a t i o n a c o 是对蚂蚁寻找食物过程的模拟 本而课题所研究的粒 子群优化算法 是通过仿真鸟群寻食得到的 1 2 粒子群算法 1 2 1 粒子群算法的发展 粒子群算法 p a r t i c l es w a r mo p t i m i z a t i o n p s o 是e b e r h a r t 和k e n n e d y 5 6 于1 9 9 5 年提出的 它主要是通过模拟鸟群觅食的行 为 从而使群体取得最优 其基本思想源于g r a n gr e y n o l d s 于1 9 8 6 年提 出的b o i d b i r d o i d 模型 在该模型中 假设每只鸟都遵循下面三条准 则 7 1 所有的鸟向群体的中心运动 2 所有的鸟的速度是一致的 3 不和相邻的鸟碰撞 在此准则假设下 b o i d 系统中的鸟群表现出群集行为 随后h e e p n e r 和g e r n a n d e 在此基础上提出了鸟群的群聚性模拟 8 即当鸟群在空中飞行 时 如果有一只鸟被栖息地吸引时 其他的鸟也逐渐被其吸引 美国的社会心理学家k e n n e y 和电气工程师e b e r h a r t 在前人关于鸟群的 群聚行为的研究基础上 提出了粒子群优化算法 该算法是通过群体中粒子之 间的合作 竞争产生群体智能 在群迭代的基础上 不断的在解空间中更新最 优粒子 直到取得最优解 其基本原理将在下一章节详细介绍 1 2 2 粒子群算法的应用及研究热点 粒子群算法因其简单易行 参数少已广泛应用于函数优化 组合优化 模 糊控制学 神经网络训练等领域 p s o 算法自提出以来 引起了许多学者的研究 粒子群算法已在被作为 一个独立的研究分支 目前关于它的研究主要集中于以下三点 2 西北大学硕士学位论文 1 粒子群算法的理论 如何对粒子群算法的理论 计算复杂性 进行 更完整的数学分析 是目前的研究热点之一 2 粒子群算法的收敛性改进 如何将粒子群算法应用于非数值优化问 题 以及改进其收敛性也将是它的研究方向 3 粒子群算法的应用 拓宽其应用领域 以及和其他的算法的结合也 是今后研究的热点之一 1 3 本文主要研究内容 本文主要围绕粒子群算法的改进一量子粒子群及其应用进行展开 主要 章节内容如下 1 简要介绍最优化问题的求解方法 并在群体智能基础上概括粒子群 算法起源 发展及应用 2 引出基本粒子群算法的模型 其次介绍标准的粒子群算法并对其算 法分析 最后简单介绍了前人对该算法的一些改进 3 先介绍量子粒子群算法 分析了算法 其次引入柯西分布 改进了 量子粒子群算法并进行数值实验 4 将量子粒子群算法应用于函数优化 先提出基于量子粒子群的信赖 域算法 其次用其解非线性整数混合规划问题 5 对本文工作进行了总结 并给出粒子群算法今后工作的研究方向 最后是参考文献 致谢 以及作者在硕士学习阶段的科研情况 3 第二章粒子群算法 2 1引言u 一 第二章粒子群算法 粒子群算法 9 是美国的k e n n e d y 和e b e r h a r t 在1 9 9 5 年共同提出的 它是模拟鸟群寻食行为得出的一种新型的优化算法 p s o 算法源于h e p p e r 的 系统仿真 8 在该系统中 一群鸟在栖息地聚集着 它们随机地寻找食物 但它们并不知道食物具体的在哪 只知道当前所在地距食物多远 开始 所 有的鸟均无目的地飞行 直到有一只鸟飞向食物 其它鸟也跟随飞向食物所 在地 这就又形成了鸟群 鸟群就是用这种简单的规律来确定自己的飞行 在此基础上 k e n n e d y 又认为每只鸟之间有信息的交换 于是 增加了两个 最优变量 鸟群所经过的最好位置 全局最优g b e s t 每个鸟所经过的最好 位置 局部最优p b e s t 并通过鸟群的记忆不断更新这两个最优变量 综合这 些 k e n n e d y 和e b e r h a r t 得出了p s o 算法的模型 2 2 基本粒子群算法 在p s o 算法中 初始m 个粒子 假设在d 维搜索空间中 设第i 粒 子的位置记为x i x mx 2 x i d i 1 2 m 我们可根据目标函数 来计算z t 的适应度 从而判断其位置的优劣 第i 个粒子的飞行速度记 为v i v i l v i 2 r i d 在每一次迭代中 粒子不断更新两个最优变量 局 部最优p b i p b i l p b i 2 p b i d 和全局最优9 b i g b l g b 2 9 b o 每次 迭代粒子通过下式不断更新自己的速度和位置 v 2 1 口乞 c l r l p b k d z 谢k c 2 r 2 夕砖一z 乞 2 1 z 豺1 z 乞 u 铲1 其中 d 1 2 d 是空间的维数 4 2 2 西北大学硕士学位论文 i 1 2 m m 是种群的粒子数 冗l 和r 1 是介于 0 1 区间的随机数 k 1 2 礼是迭代次数 c 1 和c 1 为学习因子 分别调节向加和阳方向飞行的步长 使粒子具有 向群体中优秀的个体学习的能力 他们通常取2 z 砌 x m i n d x m a x d r i d 一v m a x d v m a x d 速度的最大值设为y m a x d 设置该阈值是为了更好 的搜索 如果值太大会跳过最优解 太小又会使得搜索地不充分 由以上两式可知 粒子的速度主要由三部分组成 1 0 第一部分唬代表 前一次的速度 第二部分称为认知部分 代表粒子i 的自身认知 即粒子自己 目前的最好位置与历史的最好位置之间的距离 p 6 试k z 毛 第三部分称为社会 部分 代表粒子之间的协作 即粒子自己与整个种群之间的距离 9 6 记k z 记k 式 2 2 正式通过这三部分来更新粒子新位置 粒子群算法步骤如下 9 s l 对种群进行初始化 设置粒子的初始速度 初始位置和种群的规 模 s 2 初始粒子的开始位置为个体最优加 群体中的最优粒子g b s 3 根据式 2 1 和式 2 2 对粒子的速度和位置不断更新 s 4 更新粒子的个体最优值加 群体的全局最优g b s 5 判断是否满足算法的终止条件 若满足条件 转向s t e p 7 否则 转向s t e p 3 s 6 输出全局最优值咖 算法运行结束 2 3 标准粒子群算法 为了改善粒子群算法的收敛性 s h i 和e b e r h a r t 1 1 在1 9 9 8 年的i e e e 进化会议中发表论文 引入了惯性权重因子 将速度更新公式 2 2 改为 5 第二章粒子群算法 2 3 所示 秽咎1 u 吨 c l r l b k i d z 乞 c 2 r 2 g b 5 一z 乞 z 寸1 z 乞 u 翁1 2 3 2 4 其中u 称为惯性因子 主要是为了权衡全局搜索和局部搜索的能 力 u u 1 2 较大时 其全 局搜索能力较强 且总是搜寻新的区域 随着迭代次数的增加 应不断减 小 因此u 一般设置为线性递减的函数 其形式为 u 兰三芋 二二 u m 孤一u m i n u m i n 2 5 其中u m i n 为最小惯性因子 o m a x 为最大惯性因子 t 为当前迭代次数 把带有 惯性权重因子的p s o 称为标准的粒子群算法 文献 1 2 将 从o 9 到o 4 线 性下降 算法开始时搜寻较大的区域 较快地找到最优解的大致位置 随着u 的减小 粒子速度减慢 开始局部搜索 为了更好的在更高维的解空间的搜寻 最优解 c h a t t e r j e e 1 3 等在p s o 中引入非线性的惯性因子 其中惯性因子 的自适应变化式u 为 u t 垒辞 0 3 m a x 5 d m i n u m n 2 6 在式 2 6 中 n 取不同的值0 6 0 8 1 0 1 2 和1 4 时 惯性因子数 的变化规律也会不相同 特别地 当n 取1 0 时 u 为线性变化规律 随 后 c l e r k 1 4 在p s o 算法中又引入了一个参数一收缩因子 从而保证了算 法的收敛 带有收缩因子西的粒子更新公式如下 饥d 七 1 qx 乞 c l r l p b i d 七一z 谢七 c 2 r 2 g b d 七一x i d 七 2 7 一阿南 8 其中 c l c 2 4 设 为4 1 c 2 c l 2 0 5 当恰当选取u c l c 1 的值 带惯性因子u 的算法与带收缩因子 的算法在数学上的分析是等价 西北大学硕士学位论文 的 前者的u 是为了平衡算法的全局收敛性和局部收敛性 后者的西是为了 保证算法的收敛性 2 4 粒子群算法分析 对于粒子群算法的的收敛性 这里从代数系统进行简要的分析 文献 1 5 对基本的粒子群的模型进行简化 先定义 重 兰堕 垒兰丝 2 9ptd 2 万而f 一 v iv y 则速度公式变为 r i d t 1 v i d t 鼽d x i d t 2 1 0 其中多 1 咖2 设鼽和咖为常量 进一步得系统为 定义动态方程如下 口 t 1 v t p z 2 1 1 z t 1 z t v t 1 2 1 2 v t l2v t 一 c y t y t 1 v t 1 一 纨 其中y t p 一兢 再令b m 二1 二妒 则系统由m 决定 可求得m 特征值为t 2 1 3 2 1 4 2 1 5 孕 7 一2 士l 寥 日 第二章粒子群算法 当 4 时 定义矩阵 满足a m a 1 l 三 则有 e 1 一善 v 2 手 4 定义q t a 只 则 r 1 a 一1 l a p t 2 1 6 q l q o 肚卜e 1 仁 eel cc os 口0 一i汹sinn 0p 当q t o o 时 解出现周期性 其中c s 0 l 一鲁 s i n0 巫2 ee lt cc os 0t 一i汹sinn 0 t i i q tl i i i a p t i i i q o l i i ii i q i i i i p t l l 而i i q o l l 时 系统在平行点附近振荡 平行点为满足y 0 和n 0 的点 当西 4 时 l i i q o l i i i a i ii i p i 8 西北大学硕士学位论文 可l tl l 矿q o l l l i f t 则有1 1 只0 i i a i il i i q o l i 此时系统发散 2 5 改进的粒子群 2 2 2离散的粒子群 p s o 算法开始主要用来求解连续的函数优化问题 但是实际问题中有许 多的离散的优化问题 k e n n e d y 等又提出了离散的粒子群算法 1 6 算法中状 态变量变为由0 1 概率来决定粒子的速度和位置的更新 即 l7 p b 1 1 k 口 噍 一9 k 埘 2 1 8 其中 离散化的函数 在要离散二进制的解空间中使粒子趋向0 或者1 即粒子的速度取决于 0 1 范围内的概率选择参数8 若8 接近于1 则粒子 速度取为1 否则 取为0 则粒子更新的公式如下 u 寸1 唬 e l r l l 矾t z c 2 嘞 z 6 e 时一z 2 1 9 f o ra l l i f r a n d 2 s k t h e n 兢 1 e l s e 兢 0 其中s k 再 雨隔1 为s i g m o i d 函数 2 2 2混沌粒子群算法 高鹰 1 8 等人把混沌的思想引入p s o 算法中 提出了混沌粒子群算法 c h a o sp a r t i c l es w a r mo p t i m i z a t i o n c p s o 混沌是指由确定的方程得出不 确定的随机的方程 方程里呈混沌状态的变量称为混沌变量 经典的混沌系统 是一l o g i s t i c 方程 1 9 y n 1 y n 1 一y n 2 2 0 9 第二章粒子群算法 n 0 1 2 0 p 1 其中p 为控制参数 当3 5 7 p 4 时 方程的解在迭代过程中呈现不确 定 则方程为混沌系统 在c p s o 中 以粒子群当前的全局最优解为基础 迭代生产混沌序列 用此序列中最优的位置 随机代替当前某一粒子的最优位置来进行迭代 具体更新如下 l s 钉譬1 屹 4 c l r l x 知 一z c 2 r 2 x g k 6 武一z 对z 口6 e s t 进行混沌优化 将z 6 e s 通过 虹靛k k 映射到l o g i s t i c 方程的定义域 o 1 上 对y 通过l o g i s t i c 方程蟾 1 肛城 1 一破 进行m 次迭代 得到混沌 序列y 豇 可 坊 可 将混沌序列通过下面的方程逆映射回原解空间 z 莨 m r 譬i n r 譬a x r 譬i n 缘 m 1 2 m 从而产生一个混沌变量可的行解序列 z 瓮武 z 莨咄 z 如 2 z 2 b 咄m 在相同的环境下 混沌粒子群具有较好的收敛性 1 8 o 2 2 2其他改进的粒子群算法 为了改进p s o 算法的收敛性 l o v b j e r g 等人提出带交叉算子的p s o 2 0 在每次迭代后 依照概率在粒子之间进行交换 最后由交叉得到更优的粒 子 h i g a s h i 等人提出带变异算子的p s o 2 1 引入变异算子增加群体的多样 性 使其不易进入局部最优 a n g e l i n e 将选择算子 2 2 引入p s o 算法中 选取 每次迭代后的较好的那个粒子替换下一次 以保证每次迭代具有较好的性能 1 0 西北大学硕士学位论文 另外 还有写一些与模糊系统 神经网络等等结合的粒子群算法 2 4 2 5 总 之 这些改进都是为了更好的改进算法的收敛性 1 1 第三章量子粒子群 3 1 引言 第三章量子粒子群 p s o 算法因为简单易行 其模型受到众多的学者关注 但大部分的改进 仍不能使得该算法有更好的收敛性 因为在p s o 系统中 粒子的收敛是以轨 道的形式去实现的 并且在搜索过程中 粒子又有最大速度的限制 因此 其 每一次的搜索区域是有限的 所以p s o 算法不能以概率1 全局收敛 为更好的解决这个问题 在标准的p s o 基础上s u n 2 6 等提出了新的算 法一量子粒子群 q u a n t u m b e h a v e dp a r t i c l es w a r m o p t i m i z a t i o nq p s o 在粒子的收敛过程中 粒子i 不断地靠近只点 直到它落在只内 从量 子学 2 7 角度看 在收敛过程中只点存在着吸引势 它吸引着粒子收敛于只 使整个群体具有聚集性 处于量子束缚态的粒子能够以一定的概率出现在任 何空间点 2 7 因此可以在整个解空间搜寻 从而具有更好的收敛性 3 2 量子粒子群 3 2 1量子粒子群基本原理 在量子粒子群 2 8 中 引入6 势降 假设粒子在以p 点为中心的6 势降 中 因为粒子的速度和位置在量子空间中不能一起确定 所以粒子的状态用波 函数 y 来表示 y 击e 掣 其中 l 万1 而h 2 为粒子出现在相对 的点位置的概率 采用蒙特卡洛方法 得出粒子的位置方程为 x p 士l l n 丢 3 1 其中u u o 1 l 刍 而h 2 为5 势降的特征长度 它随着时间t 变化 则 粒子的位置方程可表示为 x t l p 4 掣h 高 3 2 西北大学硕十学位论文 u t 一u o 1 由于t 为离散的时间 所以x t 为一随机变量 当t 一 2 0 时 若l t 一0 则位置x t 依概率收敛于p 点 以上都是在一维势降下研究的粒子位置 对于扎维空间也类似 设吸引 子只 p i l 只2 最 每一维以r 为坐标 只 j 为中心建立一维巧势 阱 对于r j 有粒子i 的每一维的波函数 啦幻 圳 志唧卜警 3 3 位置方程为 雄 p i d t 土挚h 丽1 4 u i j 一u o 1 引入平均最好位置 m e a nb e s tp o s i t i o n m b e s t 定义如下 m m m m m 6 e s t 面1 只 t 砑1 只 l 面1 只 2 击 只 n t 3 5 则有 厶 j t 2 alm b e s t j t 一x i j t l 3 6 则位置方程为 x i j 件1 只 荆土口f m b e s t j t 一x i j t i t j t 一u o 1 x l n 去 3 7 冥中q 为收缩扩张因子 把应用于公式 3 7 的p s o 算法称为量子粒子群算 法 综上 q p s o 算法中粒子的更新方程可归为如下 一m m m m m b e 时2 砑1 只 丽1 只 击 只 2 t 击 只 n 3 8 p i 等等 3 9 1tl 第三章量子粒子群 x i j 1 只 j 4 q m b e s t y t 一五 j t i i n 先幻 t 3 1 0 3 2 2算法流程 在量子粒子群群中 设搜索空间为n 维 种群规模为m x i t 1 2 7 n t 2 t x i n 为第i 个粒子的位置 其最好位置p b e s t 为p i t 1 慨l p i 2 t p i n 全局最好位置9 b e s t 为 g i t 1 g i l t g i 2 c t g 讯 t 且a t p g t 算法描述如下 初始化i 1t om i f x i t o 5 e l s e x i 歹 t 1 只j o li m b e s t j 一x i j 1 i n 幻 t x i j t 1 只 j 一ai m b e s t 3 t 一五 j t i i n 幻 t 3 2 2算法分析 粒子群算法中粒子以点p 为吸引子 随 的减小而不断靠近p 直到落 在p 即p s o 要收敛必须 2 8 z p w h e nt o 设d e l t a 为l l t 并假设l t 一0 w h e nt 西北大学硕士学位论文 i m u q o o 矧 况1 v e 郴 3 1 1 l 概率密度q 为q y i 咖 可 1 2 圭e 一2 l y l l 由 3 1 1 及q 可 满足归一化条 i m1 2 t 耖i l 6 秒 6 z p f ul j c z 一纠 了三二三 厂6 z p 妇 厂一j x p d x 1 j p j 0 0 3 3 带权系数的量子粒子群算法 在量子粒子群中引入m b e s t m e a nb e s tp o s i t i o n 是为了计算l 的值 从等式 3 5 可以看出m e a nb e s tp o s i t i o n 是所有的个体平均最优 也就意味 着每个粒子对m b e s t 的值的影响是相同的 这里的m b e s t 决定着群体的搜寻 范围 然而一样的权重在实际问题中是不符合的 因此 设计一种新的带权因 子的量子粒子群 2 9 m m m m m b e s 击萋只 击萋o l i 1 只 t 击 q 啦只 2 t 击 q 饥只 n 3 1 2 第三章量子粒子群 其中q i d 为每个粒子的权系数 取其从1 5 到0 5 线性递减 量子粒子群以及带权系数的量子粒子群每次迭代时保证粒子在整个空间搜 索 2 9 现通过标准测试函数来验证量子粒子群以及带权系数的量子粒子群算法的 优越性 取如下三个测试函数 如表1 所示 在表中 m a x r a n g 速度最大值 f o r m u l a t i o n s 函数表达式 i n i t i a l i z a t i o n 初始化区间 表l 测试函数 做如下实验 其中粒子数取4 0 和8 0 最大迭代次数为1 0 0 0 1 5 0 0 2 0 0 0 相应的维数为1 0 2 0 3 0 运行1 0 0 次 在p s o 中 令c 1 c 2 2 u 从0 9 线性递减到0 4 在q p s o 中 从1 0 递减到0 5 在w q p s o 中p 从1 0 递减到o 5 权系数q 从1 j 5 递减到0 5 在表中2 至4 中分别记录了运行1 0 0 次的平均最好适应值 在表中 d 测试函数的维数 m 种群大小 g 最大迭代次数 从表中可以看出 q p s o 算法和改进后的q p s o 具有更好的收敛性能 6 西北大学硕士学位论文 表2 函数 寻优结果 表3 函数厶寻优结果 表4 函数 3 寻优结果 1 7 第三章量子粒子群 3 4 基于柯西随机数的量子粒子群算法 大多数粒子群算法都是利用均匀分布来产生随机因子 越来越多的学者 开始采用g a u s s i a n 分布 3 0 c a u c h y 分布等等一些其他的分布来产生随机因 子 因柯西分布具有较高的两翼概率特点 即柯西分布的形状具有一条很长的 尾翼 所以 柯西分布易得到一个离原点较远的随机数 它比高斯分布产生的 随机数的分布的区域更大 使得柯西变异有可能很快跳出局部极小的范围 本 节在此基础上提出一种基于c a u c h y 分布随机数的量子粒子群 c q p s o 这里采用标准的柯西分布c o 1 分布 首先 将随机数u 由原来 的u u o 1 改为u 服从u c o 1 则粒子位置更新方程变为 五 j t 十1 p i j t ai m b e s t j 一x i j t i i n x i j t 1 只j t 一oi m b e s t j t 一五 1 i n 其次 对于等式 2 9 中妒1 和妒2 也采用c 0 1 分布 则等式修正为如下 一c l p i j q p g j p 产 茜干万一 其中c 1 一c o 1 6 2 一c o 1 则基于c 0 1 随机数的量子粒子群算法描述如下 初始化i 1t om i f x i 亡 0 5 五j 1 只j ai m b e s t j t 一咒 j i i n 8 西北大学硕士学位论文 e l s e x j t 1 只 j 一qi m b e s t j 一五 歹 i i n 下面采用上一小结中的四个测试函数来进行数值实验 其中粒子数取4 0 相 应的维数为1 0 2 0 3 0 最大迭代次数为1 0 0 0 1 5 0 0 2 0 0 0 运行1 0 0 次 在p s o 中和q p s o 中参数的选取和上一小节一致 在表5 中记录了运 行1 0 0 次的最优值的比较 下面采用上 j 结中的四个测试函数来进行数值 表5 不同算法比较 实验 其中粒子数取4 0 相应的维数为1 0 2 0 3 0 最大迭代次数为1 0 0 0 1 5 0 0 2 0 0 0 运行1 0 0 次 在p s o 中和q p s o 中参数的选取和上 4 节 一致 在表5 中记录了运行1 0 0 次的最优值的比较 本节通过柯西分布的特点 将其应用于q p s o 中 使得能很快跳出局部 最优解 而且搜索的空间也较大 有效的提高了算法性能 1 9 第四章量子粒子群应用 4 1 引言 第四章量子粒子群应用 量子粒子群因比经典的粒子群收敛性能好 所以已广泛应用于函数优化 电力系统 模糊控制等等 本章先结合量子粒子群和信赖域算法 提出了基于 量子粒子群的信赖域算法 其次又把量子粒子群应用于求解混合整数非线性规 划问题 数值实验表明量子粒子群具有更好的收敛性 4 2 基于量子粒子群的信赖域算法 4 2 1 信赖域算法 考虑无约束优化问题 m i n z x e n 其信赖域子问题为 r a i n q d f x k 十靠d 去d r g 七d s ti i d i i 七 其中川为册中某一范数 一般取 2 厶可微 g k v f x k 用拟牛顿法 的b f g s 公式构造h e s s i a n 阵风近似代替g k b k 1 b k 爨毫一 龉 b o k n a k 为信赖半径 信赖域算法的基本思想是要求在每一步迭代中 以当前迭代点x 七为中心 的一个小领域 x k d 川d l l 克 上 即信赖域上求解子问题 其中如为 试探步 并确定下次迭代的信赖域 如果如被接受 则x k 1 x k d k 否 则x 七 l x 七 本文将全局搜索性良好的量子粒子群用于信赖域算法的子问题 求解 这样既可避免精确确定a k 又可快速求解子问题的解呶 4 2 2 基于q p s o 的信赖域算法 1 子模型算法 s 1 确定种群的规模m 粒子维数 初始化群体p b e s t 和g b e s t 2 0 西北大学硕士学位论文 s 2 计算每个粒子的适应度 s 3 根据适应度更新个体最优位置p b e s t 和群体最优g b e s t s 4 根据公式 3 8 一 3 1 0 更新每个粒子的位置 生成新的群体 s 5 判断是否满足最优收敛条件 或是否达最大进化代数 是则输出最优 解 否则返回s t e p 2 2 基于q p s o 的信赖域算法 s 1 初始z o m i n 0 0 p 1 1 阮 0 0 风 厦 1 令a o m a x i i g o l l 1 0 m i n k 0 g 七 b k s 2 计算g k 若i l 鲰i i 停止 输出最优解 否则用q p s o 求解子问 题得d 七 s 3 计算住 选取 知 1 a k 1 1 胁 i i d k l i r k 之仍 a k x 风国川以 i r k 仍 s 4 用b f g s 生成g k 1 k k 1 转向s t e p l 4 2 3数值实验 下面通过计算机仿真来评价基于量子粒子群的信赖域算法的全局寻优能 力 本节通过2 个基本测试函数测试算法 通过以上测试函数表明 基于量 表6 不同算法比较 子粒子群的信赖域算法比基于基本粒子群的信赖域算法 3 l 的寻优能力好 且计算速度快 4 3 量子粒子群求解混合整数非线性规划 4 3 1 混合整数非线性规划问题 2 1 第四章量子粒子群应用 混合整数非线性规划 m i x e d i n t e g e rn o n l i n e a rp r o g r a m m i n g m n l p 是同时包含整数变量和连续变量的优化问题 许多组合优化问题如 t s p 问 题 背包问题等等都可视为m n l p 问题 对于m n l p 问题 其目标函数和约 束条件的非线性 使结果往往存在局部最优 解决m n l p 主要有确定性和随机性方法 确定性方法有 外逼近法 o a 分枝界定法 b b 广义b e n d e r 分解法 g b d 等 但这些方法 的局隙性比较大 如今 越来越多的随机性方法开始应用到m n l p 如进化 算法 e a 遗传算法 g a 等 但这些算法消耗时间多 且比较容易陷入 局部的最优 混合整数非线性规划其一般形式为 m i x f x 可 仇 z y 0 i 1 2 q 砖 z y o j 1 2 p z f d 伽e r z z t p p e r 们d e r 秒 鼽t p p e r 4 2 其中 z t y y n q p q n t y 是p 维空间 n q 是q 维整数空间 函数f x y 为非线性目标函数 仇 z y b z y 为非线性约束函数 4 3 2 约束条件的处理 对m n l p 问题 约束条件的处理也是一个重要环节 目前 广泛使用的 方法为惩罚函数法 但这种方法确定罚因子较困难 文献 3 2 1 提出了不需罚 因子而直接比较个体好坏的方法 即将约束条件和目标函数分离 并通过一定 的准则比较其好坏 对于许多的约束优化问题 由于其最优解在约束边界的附 近 因此 这里我们采用让可接受的不可行解和可行解按照比较准则比较 以 便保留一部分性能比较优的不可行解 在q p s o 中 每个粒子的适应度由目 2 2 西北大学硕士学位论文 标函数来度量 对于优化问题 4 2 采用约束条件和目标函数分离 则把 问题化为 f i t n e s s i y x qp v a i i n t i o n i m a x o g t 删 i h j x i l j l i 1 2 咒 4 3 其中i 为第i 个粒子 f i t n e s s i 和所求解的问题的目标函数值对应 v o i l a t i o n 和问题的约束条件对应 它反映粒子与约束边界的靠近程度 基于q p s o 的 比较个体优劣的准则如下 1 当第t 代个体鼢和鼽都是不可行解 比较他们之间v o i l a t i o n x i 和v o i l a t i o n p i 若v o i l a t i o n x i 较小 则用甄代替p i 否则不改变p i 2 当第t 代个体筑和鼽都是可行解时 比较他们之间适应值 鼢 和 慨 若y x i 较小 则用 代替p i 否则不改变p i 3 当第t 代个体甄可行而死不可行时 如果不可行的是可接受的 保留不可行解 并比较这些p i 的目标函数值 选择适应值小的p i 作为约 4 3 3算法设计 s l 确定种群规模m 和粒子维数 初始化群体p b e s t 和p b e s t s 2 计算每个粒子的适应度 s 3 根据适应度更新个体最优位置p b e s t 和群体最优g b e s t s 4 根据4 3 2 所述的比较准则更新每个粒子的p b e s t 和g b e s t s 5 判断算法的停止准则是否满足 如果满足转向步骤6 否则转向步 骤2 s 6 输出g b e s t 算法停止 4 3 4 数值实验 为验证该算法的性能 选取如下3 个实例进行检测 例1 取自于k o c i s 和g r o s s m a n n a a 问题描述如下 m i n k x y y 2 x l x 2 第阴章量子粒子群应用 s t 目前已知的最优解为 z 1 2e x p x 2 0 x 1 x 2 y 0 0 5 z 1 4 y o 1 x l x 2 y f 1 1 3 7 5 o 3 7 5 1 2 1 2 4 例2 3 4 3 5 1 中提到 问题如下 表7 问题1 实验结果 s t m i n f 2 x v l v 2 y l y 2 7 5 y l 5 5 y 7 v l 6 v 2 5 x z 1 0 9 1 一e x p o 5 v 1 x l z l 0 9 l e x p o 5 v 1 x l z 2 0 8 1 一e x p o 4 v 2 1x 2 名1 z 2 1 0 剪1 y 2 1 2 4 西北大学硕士学位论文 目前已知的最优解为 x l x 22z u 1 l o y l 钉2 l o y 2 z 1 2 0 y a z 2 2 0 y 2 z 1 z 2 1 u 2 z l z 2 0 y 1 y 2 o 1 k u a v 2 y l y 2 1 3 3 6 2 3 5 1 4 0 1 o 9 9 2 3 6 例3 这是一个压力容器设计问题 3 6 中提出是关于压力容器设计的问 表8 问题2 实验结果 题 描述如下 s t r a i nf x y 0 6 2 2 4 0 0 6 2 5 y 1 z l x 2 1 7 7 8 1 0 0 6 2 5 y 2 x i 3 1 6 6 1 0 0 6 2 5 y 1 2 x 2 1 9 8