0—1背包问题的度优先算法

本文介绍了０－１背包问题的一种深度优先算法。并用概率分析方法给出了算法的时间复杂度和空间复杂度,一般情况下,其时间复杂度Ｔｎ在Ｏ?     

一种改进的二进制粒子群算法

为解决应用粒子群算法求解0-1整数规划问题,在Kenney和Eberhart的二进制粒子群算法(BPSO)的基础上提出一种改进的二进制粒子群算(IBPSO).该算法简化BPSO的概率计算模式,直接使用群体最佳值和个体最佳值决定粒子的当前取值概率,取消粒子当前值对下一步迭代的影响.在De Jong的测试集上,其结果要优于BPSO.在背包问题上的计算结果表明,与遗传算法相比,IBPSO具有更快的收敛速度.     

电力系统故障诊断的多智能体粒子群优化算法

电力系统的故障诊断是利用保护和断路器的动作信息来推断可能的故障位置,识别故障的元件和误动作的保护与断路器,并对保护和断路器的动作情况作出评价;其中故障元件的识别是故障诊断实现的关键;文中首次应用粒子群优化算法研究故障元件的识别方法;基本思想是根据保护动作原理将故障诊断问题表示为0-1整数规划问题,然后用粒子群优化算法求解;与传统的遗传算法求解比较,结果表明文中采用的粒子群优化算法具有稳定性高、收敛特性好、运行速度快的突出优点;仿真研究验证了该方法的可行性和有效性.     

基于蚁群算法的Web集群文档优化分布方案

在Web集群中优化分布海量级的Web文档是一个急需解决的问题.提出了一种以减少系统平均响应时间为目的的Web集群文档优化分布方案.该方案合适地拷贝网页簇,并通过对服务器进行建模将网页簇的分布问题转化为0-1整数规划问题.针对该问题的特点,设计实现了一种基于蚁群算法的求解方案,算法中蚂蚁对路径的选择分两步进行,并设置合适的启发值以加快收敛速度.实验结果表明了应用蚁群算法求解Web集群文档优化分布问题的可行性与有效性.     

基于状态空间分析的街面围堵凸包算法研究与应用

针对常见的城市街面犯罪事件,研究和分析布控追踪疑犯的逃逸路径,提出一种围堵博弈的凸包的算法。该算法以现代控制理论的状态空间分析为基础,并据事发区域的实时路况、移动速度和位置等参数,从而得出最佳围堵路径和布控区域。应用表明该研究成果可实现快速得出围堵犯罪嫌疑人的最佳路径,及有效调配警力构成最小布控范围。     

改进自适应差分进化算法求解大规模整数任务分配

针对0-1任务规划模型存在维数灾维的问题,提出一种基于改进自适应差分进化(SADE)算法的大规模整数任务分配算法。首先,将任务分配的0-1规划模型转化整数规划模型,不仅大幅减少了优化变量的维数,还减少了整式约束条件;然后,将常用的变异算子DE/rand/1/bin和DE/best/2/bin结合起来组成新的自适应变异算子,使得自适应差分进化算法既有较快的收敛速度,又降低了变异算子对具体问题的依赖;并用改进自适应差分进化算法求解整数规划。最后,通过典型的任务分配实例验证了算法在优化大规模任务分配的有效性和快速性。     

基于0-1规划的快速图像阈值分割算法

阈值方法是一种重要的图像分割方法,在图像分割中得到了广泛应用。Otsu算法虽然是图像分割阈值法中较好的方法之一,但是由于传统的Otsu算法通常用穷举法求解,使得处理多阈值问题时运算速度太慢,难以满足应用需求。为了快速有效地确定阈值,提出了一种改进的Otsu算法。将Otsu算法转化为一个非线性0-1数学规划问题,再利用遗传算法求解得到最优阈值。通过对测试图像的分割实验,表明该算法与传统的Ot-su算法相比运算速度有非常显著的提高,能够满足一般的应用需求。     

求解0-1背包问题的改进混合遗传算法

针对一种混合遗传算法所采用的贪心变换法的不足,给出了一种改进的贪心修正法;并基于稳态复制的策略,对遗传算法的选择操作进行改进,给出了随机选择操作。在此基础上,提出了一种改进的混合遗传算法,并将新算法用于解决大规模的0-1背包问题,通过实例将新算法与 HGA 算法进行实验对比分析,并研究了变异概率对新算法性能的影响。实验结果表明新算法收敛速度快,寻优能力强。     

0-1背包问题的两种扩展形式及其解法

0-1背包问题是经典的NP-HARD组合优化问题之一,由于其难解性,该问题在信息密码学和数论研究中具有极其重要的应用。首先对01背包问题及其解法进行了分析,然后提出01背包问题的两种扩展形式,并给出了基于动态规划和贪心算法的两种有效算法来解决这两类问题。实验结果验证了所提出方法的有效性。     

电力系统故障诊断的萤火虫和粒子群混合算法研究

电力系统故障诊断主要就是根据保护和断路器的动作信息来判别故障区域,而找出故障元件又是其难点和主要工作,以目标函数描述其模型,则故障诊断问题转化为0-1整数规划问题。适合于智能算法求解。用粒子群算法解决该问题时收敛速快,但容易陷入局部最优值;用萤火虫算法时能够找到全局最优值,但其后期收敛速度较慢。论文融合这两种算法并用之求解故障诊断的目标函数,仿真结果表明：融合后的算法兼备两种算法的优点,能够以较快速度收敛,并找到全局最优解,且收敛精度高,稳定性好。     

基于粗糙集和遗传约简算法的入侵检测方法

采用改进的贪心算法和遗传算法结合的混合遗传算法进行属性约简,并利用值约简后生成的入侵检测规则,提出一种基于粗糙集理论和遗传约简算法的入侵检测方法。基于KDDCUP99数据集的实验表明该方法取得了良好的入侵检测效果,并且改进的混合遗传算法生成约简的速度更快。     

集合覆盖问题的模型与算法

集合覆盖问题在网络设计领域中有着良好的应用背景,但它在算法复杂性上却是NP-困难问题。建立了集合覆盖问题的0-1规划模型,给出了源于贪心思想的近似算法,并从原始-对偶规划的角度进行了证明,基于LINGO软件的传感器网络最优设计案例验证了模型的正确性和算法的有效性。     

基于粗糙集的非监督快速属性选择算法

针对"大数据"中常见的大规模无监督数据集中特征选择速度难以满足实际应用要求的问题,在经典粗糙集绝对约简增量式算法的基础上提出了一种快速的属性选择算法。首先,将大规模数据集看作一个随机到来的对象序列,并初始化候选约简为空集;然后每次都从大规模数据集中无放回地随机抽取一个对象,并且每次都判断使用当前候选约简能否区分这一对象和当前对象集中所有应当区分的对象,并将该对象放入到当前对象集中,如果不能区分则向候选约简中添加合适的属性;最后,如果连续I次都没有发现无法区分的对象,那么将候选约简作为大规模数据集的约简。在5个非监督大规模数据集上的实验表明,所求得的约简能够区分95%以上的对象对,并且求取该约简所需的时间不到基于区分矩阵的算法和增量式约简算法的1%;在文本主题挖掘的实验中,使用约简后的数据集挖掘出的文本主题同原始数据集挖掘出的主题基本一致。两组实验结果表明该方法能够有效快速对大规模数据集进行属性选择。     

基于遗传算法的战略供应链集成研究

在战略供应链研究中,考虑供应链的三个主要阶段,采购、生产、配送和它们之间的相互作用,不同客户需求,设施配对关系,供应商优先权以及现有供应链设计模型的局限性,建立了混合整数非线性规划（MINLP）模型。为有效地解决这种大规模混合整数非线性规划模型的约束,采用自适应遗传算法（AGA）对该模型进行求解优化。实验结果表明,所提混合整数非线性规划模型能够有效解决战略供应链设计中的供应链协同优化问题,并能得到较优的供应链设计方案。     

求解0-1整数规划问题的混沌遗传算法*

针对一类特殊的0-1整数规划求解问题提出一种混沌遗传算法。该算法采用幂函数载波技术提高混沌搜索的充分性与遍历性,以混沌搜索算法得出的优化个体作为遗传算法的新群体进行交叉、变异等操作,提高种群质量,同时增加种群多样性,改善遗传算法的早熟问题。该算法被用于解决片上网络映射A3MAP(architecture-aware analytic mapping) 0-1整数规划问题。实验仿真证明,该算法的收敛速度和解的精度均优于A3MAP-GA。     

求解0-1背包问题的混合蝙蝠算法

针对基本蝙蝠算法易陷入局部最优、收敛速度慢等缺点,对其进行优化研究。基于0-1背包问题的具体特征,在基本蝙蝠算法原有概念和框架的基础上,引入遗传算法中的交叉机制以及反置算子建立全新的位置转移方式和局部搜索规则;加入贪心策略进行解的可行化和充分利用,增强局部搜索能力,加快算法收敛速度,构建全新的混合蝙蝠算法。将混合蝙蝠算法应用于两组0-1背包算例,仿真实验结果优于自适应元胞粒子群算法、基本蝙蝠算法和贪心二进制蝙蝠算法。结果验证了该混合算法求解0-1背包问题的可行性和有效性。     

基于OLSR协议的最小MPR集选择算法

针对传统优化链路状态路由(OLSR)协议中利用贪婪算法求解最小多点中继(MPR)集时存在冗余的问题,提出了一种基于全局改进的Global_OP_MPR算法。首先引入了一种基于贪婪算法改进的OP_MPR算法,该算法通过逐步优化MPR集的方法去除冗余,可以简单高效地得到最小MPR集;然后在OP_MPR算法的基础上,将全局因素加入MPR选择判据中,引入"全局优化"代替"局部优化",最终利用该算法可以得到整个网络的最小MPR集。在OPNET上采用Random Waypoint运动模型进行仿真,与传统OLSR协议相比,采用OP_MPR和Global_OP_MPR算法的OLSR协议在整个网络上有效地减少了MPR节点的数量,并且具有更少的网络负担拓扑控制(TC)分组数和更低的网络延时。仿真结果表明,所提出的算法均能优化MPR集的大小,提高协议的网络性能;同时,Global_OP_MPR算法由于考虑了全局因素,达到了更好的网络性能效果。