logo资料库

基于的改进自适应遗传算法.doc

发布时间：2022-06-08 发布人：admin 分类：说明书 资料大小：4.50M 资料格式：doc 举报 版权申诉
第1页 / 共31页
第2页 / 共31页
第3页 / 共31页
第4页 / 共31页
第5页 / 共31页
第6页 / 共31页
第7页 / 共31页
第8页 / 共31页
资料共31页，剩余部分请下载后查看
    基于的改进自适应遗传算法 及在背包问题中的应用 摘 要 本文将改进的自适应遗传算法和相结合用于 0-1 背包问题的求解。此算法对 交叉率和变异率进行了优化，实现了交叉率和变异率的非线性自适应调整，并对 不可行解进行了贪婪修复。实验结果表明，相比传统的自适应遗传方法，新算法 收敛速度快，寻优能力强，具有更可靠的稳定性。 关键词：0-1 背包问题 遗传算法 鲁棒性 自适应 0 引言 背包问题（KnapsackProblem，KP）又称子集和问题，是计算科学中的一个经 典ＮＰ难题，最早由 Dantzig 于 20 世纪 50 年代首先提出并研究。在实际应用中， 许多工业与经济问题都可以用背包问题来描述，如货舱装载，资源分配，资金运 算等。KP 问题的求解一直是计算智能领域研究的热点，已有的求解方法分为精 确算法（如动态规划、回溯法、分支定界、隐枚举法等）和近似算法（如贪心法、 tabu 搜索算法、蚂蚁算法、模拟退火算法、遗传算法等）。精确算法的优点是当 n 较小时一定可以求得最优解，缺点是对于较大规模的问题，求解复杂度将以指 数形式增加，运算时间可能无法满足实际应用的要求，还会因计算量较大而难以 实现。近似算法的优点是使计算复杂性大大降低。这些方法都有它的局限性，解 析解对于目标函数是连续可微的情况，通过求解使目标函数梯度为零的一组非线 性方程，可以解决该问题，但对于任意目标函数却无能为力，但这些算法虽然不 能求出最优解，但是能在可接受时间内近似解决背包问题。1975 年，Holland 等 人 基 于 自 然 界 的 遗 传 和 自 然 选 择 ， 提 出 了 全 局 优 化 算 法 -- 遗 传 算 法 （geneticalgroithms,GA）[1]。遗传算法是模拟达尔文的遗传选择和自然淘汰的生 物进化论过程的计算模型，它的思想源于生物遗传学和适者生存的自然规律，是 具有“生存+检测”的迭代过程的随机搜索算法. 遗传算法克服了传统优化方法的 缺点，借助了大自然的演化过程，是多线索而非单线索的全局优化方法，采用的 1
    是种群和随机搜索机制.遗传算法以其简单通用性鲁棒性强，适用于并行处理以 及高效性 实用性等显著特点，在各个领域得到了广泛应用，取得了良好效果， 并逐渐成为重要的智能算法之一。 已经有学者利用各种遗传算法来解决背包问题[2-9]。2002 年，虞安波和杨家 本提出了利用简单遗传算法求解背包问题的优化算法，取得了较好的效果[8]。自 Srinvas 等提出了自适应遗传算法(adaptive GA,以下简称 AGA)以来，自适应调整 交叉率和变异率被应用到 GA 中，从而较好地提高了 GA 的收敛速度。然而， AGA 在演化初期存在停滞现象，故将自适应的调整交叉率和变异率的方法应用 于 GA 以提高算法收敛速度和鲁棒性仍十分具有挑战性[8-12]。 本文将文献文[2]中的自适应遗传算法应用于求解 0-1 背包问题，并利用对不 可行解和背包资源利用不足的问题进行修复，提出了一种基于的改进的自适应遗 传算法。数值实验表明此算法在求解 0-1 背包问题时非常有效。 1 背包问题描述 背包问题可以描述如下：假设要从多种物体（或称为项目）中悬着几种物 体，装满背包，若有 n 个不同的物体，对于物体 j，其重量为 iw ，价值为 jp ,b 是背包承受的最大重量，背包问题就是要在不超过背包承受重量的前提下，是装 入背包价值最大。设 jx 为 0-1 决策变量（当项目 j 被选择时 jx =1，否则 jx =0）。 则背包问题的数学模型如下： max px i i n  1 i  n   .. ts    b xw i i  1 i  10 x ，或 i  i  ,...,2,1 n 2 贪婪算法 贪婪算法属于一步式启发算法,即每采用一个贪婪准则,便做出一个不可撤 回的决策,是指从问题的初始状态出发,通过若干次的贪婪选择而得出最优解的 一种解题方法, 贪婪策略总是做出在当前看来最优的选择,并不是从总体上加以 考虑,它所做的选择只是某种意义上的局部最优解;从全局上看,得到的最终解一 般是近似最优解。背包问题的如下：按照上述价值密度对物体排序为非增序列（若 2
    两个物体的价值密度相同则重量大的排在前面），在按次序逐一选取物体，装入 到剩余容量最大的背包中（若该物体能装入的话），使背包价值增大，直到任何 背包都不能装入任一物体为止。 物体的放入次序采用规则：若两个物体的价值密度相同时，采用重量大的排 在前面的排序方法，可以提高的质量。 3 基本遗传算法 遗传算法(GA)作为一种解决复杂问题的有效方法。它是基于生物进化中自然 选择、适者生存和物种遗传思想的一种搜索算法。 它将问题的每一个可能解看 作是群体中的一个个体(染色体),并将每一个染色体编码成串的形式,再根据预 定的目标函数对每个个体进行评价,给出一个适应值。 算法将根据适应值进行寻 优过程。遗传算法的寻优过程是通过选择、杂交和变异等遗传算子来具体实现的, 它的搜索能力由选择算子和杂交算子决定,变异算子则保证了算法能够搜索到问 题空间的每一个点,从而使其具有搜索全局最优的能力。遗传算法有着其鲜明的 特点： (1)遗传算法的操作对象是一组可行解, 而非单个可行解; 搜索轨道有多条, 而非单条, 因而具有良好的并行性。 (2)遗传算法只需利用目标的取值信息,而无需递度等高价值信息, 因而适用 于任何规模, 高度非线型的不连续多峰函数的优化以及无解析表达式的目标函 数的优化, 具有很强的通用性。 (3)遗传算法择优机制是一种“软”选择, 加上良好的并行性, 使它具有良好 的全局优化性和稳健性。 (4)遗传算法操作的可行解集是经过编码化的(通常采用二进制编码), 目标 函数解释为编码化个体(可行解)的适应值, 因而具有良好的可操作性与简单性。 4 自适应遗传算法 运用 SGA 求解背包问题时若问题的规模不大也能够得到最优解或近似最优 解,但当求解的背包问题的规模比大时,用简单的遗传算法得不到较理想的结果。 SGA 在运行早期个体差异比较大,后代产生的个数与父个体适应度大小成比例, 因此在早期容易使个别好的个体的后代充斥整个种群,过快的收敛于某一局部极 小值,造成”早熟”;而在 SGA 后期,适应度趋向一致,优秀的个体在产生后代时, 3
    优势不明显,从而使得整个种群进化停滞不前。变异率是决定算法跳出局部最优 解的一个关键因素。变异率过小，不易生成新的模式结构，而变异率过大，会使 SGA 成为纯粹的随机搜索算。自 Srinvas 等提出了自适应遗传算法(adaptive GA, 以下简称 AGA)以来，自适应调整交叉率和变异率被应用到 GA 中，从而较好地提 高了 GA 的收敛速度。是否收敛到全局最优解将不再取决于选择、交叉和变异操 作，而主要取决于种群规模和演化代数。如果使用 SGA，针对不同程度的优化问 题就必须通过反复地试验调整好交叉率和变异率，这是极不方便的，且难以保证 获得最佳的参数值。在 AGA 中，交叉率和变异率随着个体的适应度在种群平均适 应度和最大适应度之间进行线性调整。如公式（1）、（2）所示，图（A）是交叉 率自适应调整曲线，图（B）是变异率自适应调整曲线。 p c p m              ( k f  1 max f f  , k f 2 max avg '   f max  avg f ( 3 f max k     k 4 f ' ), ' f  f avg f avg f ' ) （1） （2） f  f . avg f  f . avg （a）自适应交叉率调整曲线（k1=k2=k3） 4
    （b）自适应变异率调整曲线（ k’=k3=k4） 根据 Srinvas 等提出的 AGA，当个体的适应度低于当代种群的平均适应度时， 认为该个体性能不佳，若该个体在选择机制下被选中，将对其采用较大的交叉率 和变异率。当个体适应度接近当代种群中的最大适应度时，认为该个体性能较好， 应尽可能保留其优良模式，即使该个体在选择机制中被选中，也会对其采用较低 的交叉率和变异率。 在进化初期并不理想，因为在进化初期的群体中，较优个 体几乎处于一种不发生变化的状态，而此时的优良个体不一定是全局最优解，这 容易使进化走向局部收敛的可能性增加。进化后期，由于初期难以跳出局部最优 解，导致算法最终陷入局部收敛。 5 改进的自适应遗传算法 GA 的自适应能力应该体现在种群中的个体能根据周围环境的变化自动发现 环境的特性和规律，最明显的环境特征就是种群中个体的适应度，最明显的演化 规律就是种群中个体适应度与平均适应度、最小适应度以及最大适应度的关系。 生物在进化过程中，并不记忆当前演化到哪一代，它所关心的是自身适应环境的 能力是否得到了提高，如果没有，那么它被自然界淘汰的几率就增大，如果有提 高，表明它拥有较良好的模式，在算法设计中，尽可能地把这种模式保留下来。 在 AGA 中，个体的交叉率及变异率根据个体的适应度在平均适应度与最大适应度 之间进行线性变换，并且最低交叉率和最低变异率为 0。当种群中出现较多适应 度接近平均适应度的个体时，这些个体的模式相当，且占据了种群的大部分，如 图（a）中较密集部分所示。若平均适应度与当代种群中的最大适应度接近，AGA 自适应交叉、变异调整曲线会变得更陡峭，这些个体的交叉率和变异率也因此产 生较大差异，导致大部分个体只能拥有较低的交叉率和变异率，使演化停滞不前。 另外，在算法演化初期，种群中适应度较大的个体一般不是全局最优解，若采用 AGA 自适应调整，这些个体的交叉率及变异率接近 0，导致非全局最优解的模式 得到了较多地保留，算法也会停滞不前，容易陷入局部收敛。 5
    （a）个体在 AGA 中的自适应交叉变异调整 （b）个体在 IAGA 中的自适应交叉变异调整 图 1 IAGA 的优化机理 为避免 AGA 在上述情况下停滞不前，首先应使交叉率和变异率的自适应调 整曲线在 avg f 处缓慢改变，从而大面积地提高适应度接近平均适应度的个体的交 叉率和变异率。其次，保证当代种群中较优个体仍具有一定的交叉率和变异率。 为了能在算法演化后期尽可能地保留较优个体的模式，应平滑 max f 处的自适应 调整曲线。 文献[1]采用在构造神经元激活函数中最常用、并且在线性和非线性行为之 间显现出较好的平衡的 sigmoid 函数来构造本文所使用的交叉与变异率，sigmoid 函数如下： 6
    图 3 sigmoid 函数 如图 3 所示，sigmoid 函数拥有平滑的顶部和底部。 av 9.903438 时， ）（ =1；当 av  -9.903438 时， ）（ =0。利用 sigmoid 函数设计出的求解最 大优化问题时的交叉率及变异率的自适应调整公式分别如公式（4）及公式（5） 所示，其中 A=9.903438。图 4（a）是 IAGA 求解最大优化问题时的自适应交叉 率调整曲线，图 4（b）是 IAGA 求解最大优化问题时的自适应变异率调整曲线。  p c min , ' f  f avg ) 1))  p c max 2( f '  f p c min   max p c min f avg f avg , f '  f avg p c p m     1 exp( ( A         1     exp(   p p f min , m p   min c f avg f avg  p c min , f  f avg )  )1  ' f max m (2 f max f  ' avg (a)交叉率自适应调整曲线 (4) (5) 7
    (b)变异率自适应调整曲线 f 为群体中最大的适应度值, avg max f 为每代群体的平均适应度值, 'f 为要交 叉的两个个体中较大的适应度值, f 为要变异个体的适应度值。 分析公式（4）及公式（5）可知，交叉率和变异率按照个体的适应度在平均 适应度和最大适应度之间随 曲线进行非线性调整。显然，当种群中大部分个体 具有相当的适应度且平均适应度与最大适应度接近时，大多数个体的交叉率和变 异率被提高，如图 2（b）中的 a 点所示。同时，最大适应度附近的个体的模式 得到了尽可能地保留，在保证它们的交叉率和变异率大于 0 的前提下，压低了 它们的交叉率和变异率，如图 2（b）中的 b 点所示，为这类模式的个体参与交 叉配对的概率变大，使算法力求跳出局部收敛。公式（6）给出 IAGA 求解最小 优化问题时的自适应调整公式，公式（7）给出 IAGA 求解最小优化问题时的自 适应变异调整公式，其中 A=9.903438，图 5（a）是 IAGA 求解最小优化问题时 的自适应交叉率调整曲线，图 5（b）是 IAGA 求解最小优化问题时的自适应变 异率调整曲线。 p c p m f avg f avg , f '  f p c min   max p c min p  c min ' f  avg f  p c max 2( f     1 exp( ( A         1      p m max (2 exp( f max f  p m min ' , f  f avg avg  p c min , ' f  f avg ) 1))  '  f avg  p c min , f  f avg ) )1  (6) (7) 8
    分享到：
    赞 收藏

    相关推荐

    资料库

    课程资源

    共收录17145份资料，累计13个分类，关注成员有19位，主要包括：PHP,网络管理,网页制作,Java,.Net,数据库,3G/移动开发,C/C++,游戏开发,嵌入式,讲义,软件测试,专业指导

    热门标签

    PHP 网络管理 网页制作 Java .Net 数据库 3G/移动开发 C/C++ 游戏开发 嵌入式 讲义 软件测试 专业指导

    最新资料