一种基于博弈策略的群智能属性约简算法

建立了粒子群算法与博弈论之间的联系,在此基础上,引入一种基于博弈策略的群智能搜索机制,并应用于粗糙集最小属性约简问题的求解。由此构建的属性约简算法,可以设置不同的参与团体及其博弈策略,构建相应的支付效用矩阵,并能通过博弈过程构建策略的最优组合。多个UCI数据集的实验计算表明提出的基于博弈策略的新算法求解质量优于粒子群优化算法、禁忌搜索、遗传变异和变异粒子群优化算法,并具有较小的计算开销。     

粗糙集多目标并行属性约简算法

粗糙集理论(RST)中,求解最小属性约简MAR (minimal attribute reduction)是一种NP-难(non-deterministic polynomialhard)组合优化问题.蚁群优化算法ACO(antcolonyoptimization)是进化算法中的一种启发式全局优化算法,粗糙集理论与ACO相结合,是求解属性约简的一种有效、可行的方式.针对蚁群优化算法易于陷入局部最优解、收敛速度慢等问题,首先以一种改进的信息增益率作为启发信息,提出了冗余检测机制,对每个被选属性和每代最优约简集合进行冗余检测,并提出了概率提前计算机制,可避免每只蚂蚁在搜索过程中相同路径上的信息反复计算;针对大数据集的属性约简问题,考虑到蚁群优化算法具有并行能力以及粗糙集中“等价类”计算的可并行性,提出一种将ACO与云计算相结合用于求解大数据集的属性约简算法,在此基础上,进一步提出一种多目标并行求解方案.该方案可以同时计算出其余属性相对于当前属性或约简集合的重要度.实验结果表明,该算法在处理大数据的情况下能够得到最小属性约简,计算属性重要度的时间复杂度由O(n2)降至O(|n|).     

信息熵最小约简问题的若干随机优化算法

现有的启发式属性约简算法一般无法得到信息熵意义下的最小属性约简。为此,文中探讨应用随机优化算法计算信息熵意义下最小属性约简的问题。首先通过定义适当的适应值函数,将信息熵意义下的最小属性约简问题转化为不含约束的适应值优化问题,证明问题转化的等价性。研究基于遗传算法、粒子群优化算法、禁忌搜索以及蚁群算法等若干随机优化算法的求解效率和求解质量,并用一批UCI数据集来加以测试。实验结果表明,文中设计的带增强策略的基于全息粒子群的属性约简算法,具有较高的获得信息熵意义下最小属性约简的概率和较优的算法性能。关键词随机优化算法,粗糙集,信息熵,最小属性约简,全息粒子群中图法分类号TP181ResearchonComputingMinimumEntropyBasedAttributeReductionviaStochasticOptimizationAlgorithmsMASheng-Lan,YEDong-Yi(CollegeofMathematicsandComputerScience,FuzhouUniversity,Fuzhou350108)ABSTRACTExistingheuristicattributereductionalgorithmsgenerallyfailtogetaminimumentropy-basedattributereductionofadecisiontable。Somestochasticoptimizationalgorithmsarediscussedtosolvetheproblemofentropy-basedattributereduction。Firstly,aproperfitnessfunctionisdefinedtotransformtheminimumattributereductionproblemintoafitnessoptimizationproblemwithoutadditionalconstraintsandtheequivalenceoftransformationisproved。Then,thesolvingefficiencyandthesolutionqualityofsomestochasticoptimizationalgorithmsarestudiedsuchasGeneticAlgorithm,ParticleSwarmOptimization,TabusearchandAntColonyOptimization。SomeUCIdatasetsareappliedtotestthoseperformances。TheexperimentalresultsshowthatthefullyinformedPSObasedattributereductionalgorithmwithrefineschemehasahigherprobabilitytofindaminimumentropy-basedattributereductionandgoodperformance。     

具有博弈概率选择的多子群粒子群算法

针对粒子群算法在求解复杂多峰函数时存在早熟、易陷入局部最优、全局收敛性能差等缺陷,考虑种群结构、多模式学习和个体间博弈等因素,提出了具有博弈概率选择的多子群粒子群算法.该算法从改善群体多样性、提升个体搜索能力的角度出发,构建了动态多种群结构,并针对每个子群构建不同的学习策略(极端学习、复合学习、邻域学习和随机学习),子群间进行最优信息共享,形成异构多子群的多源学习方式;将进化博弈思想引入群体搜索过程中,个体通过收益矩阵和扎根概率进行策略概率选择,进入适合个体能力提升的子群进行学习.基于12个标准测试函数,针对算法中重要参数子群规模L的取值进行了组合实验,结果表明L取值N/2或N/3时,种群适应度分布及中位值具有明显优势;针对算法性能测试,利用不同维度下的标准测试函数与7种同类型算法进行对比实验,实验结果显示,改进算法在最优值、求解稳定性及收敛特征上整体优于对比算法,说明多源学习和博弈概率选择策略可以有效改善粒子群算法的性能.     

基于量子粒子群优化的属性约简

量子粒子群优化(QPSO)算法改进了粒子进化策略,使粒子具有更大搜索空间,可更好地避免陷入局部最优。该文将普通QPSO算法转化为二进制QPSO算法,提出基于QPSO优化的属性约简算法。实验结果表明,二进制QPSO算法的约简结果优于Hu算法和粒子群优化约简算法。     

基于禁忌搜索的动态粒子群算法

惯性权重线性递减的线性群粒子算法往往不能反映实际的优化搜索过程。动态粒子群算法虽然能较好地实现非线性的搜索,但是更容易陷入局部最优。提出了基于禁忌搜索的动态粒子群算法,引入了禁忌搜索的思想,来解决动态粒子群算法的容易陷入局部最优问题;并对禁忌公式进行了修改,使其不仅可以解决极小值最优问题,也可以解决极大值最优问题。根据实验结果,改进的算法不仅较好地避免了陷入局部最优,而且收敛速度也有提高。     

最小约简问题的一个免疫离散粒子群算法

把求决策表最小属性约简问题归结为一个不含非线性约束的0-1组合优化问题,证明了两个问题之间最优解的等价性.针对问题的特性,对原有的二进制粒子群算法进行改进,引入基于决策表差别矩阵的疫苗接种机制以及k-精英保优策略,由此提出一个免疫二进制粒子群算法并用于求解转化后的组合优化问题.仿真计算结果表明该算法有效地提高了获得最小属性约简的可能性,同时还具有较快的收敛速度.与其它类型的最小属性约简算法相比较,该算法取得明显的改进效果.     

具有拓扑时变和搜索扰动的混合粒子群优化算法

粒子群优化（PSO）算法在求解复杂多峰函数时极易早熟,陷入局部最优无法跳出。研究表明改变粒子间的拓扑结构和调整算法的迭代机制有助于改善种群的多样性,提高算法的寻优能力。因此,提出一种具有拓扑时变和搜索扰动的混合粒子群优化（HPSO-TS）算法。该算法采用K-medoids聚类算法对粒子群进行动态分簇,形成多个异构子群,以利于子群内粒子间进行信息流通。在速度更新中,增加簇最优粒子的引导,并引入非线性变化极值扰动,帮助粒子搜索更多的区域。而后在位置迭代中引入花授粉算法（FPA）中的转换概率,使粒子在全局搜索和局部搜索之间转换。在全局搜索时结合狮群算法中的母狮觅食机制对粒子的位置进行更新;在局部搜索时引入正弦扰动因子,帮助粒子跳出局部最优。实验结果表明所提算法在求解精度和鲁棒性方面明显优于FPA、PSO、改进粒子群算法（IPSO）、具有动态拓扑结构的粒子群算法（PSO-T）;并且随着测试维度和次数的增加,这种优势更加明显。HPSO-TS算法所引入的拓扑时变策略和搜索扰动机制能有效地提高种群的多样性和粒子的活性,从而改善寻优能力。     

一种双层可变子群的动态粒子群优化算法

粒子间信息的共享方式对粒子群优化算法的收敛速度和全局搜索能力有重要的影响.针对全互联、环形拓扑结构,提出基于双层子群的信息共享方式,以收敛率作为子群规模变化的标识,实现子群规模动态变化,协调了算法的全局搜索能力和局部寻优能力.子群排斥机制使子群跳出局部最优解的束缚,提高解的多样性.选取目前比较流行的几种粒子群优化算法,通过五种经典的Benchmark高维函数优化问题进行实验仿真.结果表明基于双层可变子群的动态粒子群优化算法可以有效的避免算法陷入局部最优,在保证收敛速度的同时算法的全局搜索能力和精度有明显的提高.     

多种群粒子群算法与混合蛙跳算法融合的研究

针对粒子群算法和混合蛙跳算法在复杂函数寻优上易于陷入局部最优值的缺点,提出一种新的粒子群与混合蛙跳融合算法.算法采用多种群粒子群方法,每次进化后,将各子群中的最优粒子组成新的群体,采用混合蛙跳模式进化,以提高种群的多样性.粒子群各子群的进化模式中,除考虑本子群最好的粒子外,还考虑整合群体最好的粒子.相对于其它一些改进的粒子群或混合蛙跳算法,融合算法概念简单,易于实现,具有良好的全局搜索能力和较快的收敛速度.基准测试函数的仿真结果表明,本文算法优于目前一些常见的改进粒子群算法.     

用于特征子集选择的异步并行微粒群优化方法

针对大量无关或冗余的特征通常会降低模式分类中分类器性能的问题,提出一种基于异步并行微粒群优化的特征子集选择方法（AP-PSO）.该方法采用二进制微粒群优化搜索特征子集,利用异步并行方式提高算法的运算效率;为有效协调种群的全局探索和局部开发能力,充分利用混沌运动的遍历性和随机性,提出一种一致混沌变异算子.与已知4种特征子集选择方法进行比较,所得结果验证了该算法的有效性.     

一种新型的动态粒子群优化算法

为了改进标准粒子群优化算法全局搜索性能,提出了一种种群动态变化的多种群粒子群优化算法。当算法搜索停滞时,把种群分裂成2个子种群,通过子种群粒子随机初始化及个体替代机制增强种群多样性,两个子种群并行搜索一定代数后,通过混合子种群来完成不同子种群中粒子的信息交流。收敛性分析表明,本文算法能以概率1收敛到全局最优解。实验结果表明,本文算法具有较好的全局寻优能力和较快的收敛速度。     

具有量子行为粒子群优化算法的并行化研究

在研究了具有量子行为粒子群算法的基础上,受遗传算法并行化的启发,对具有量子行为的粒子群算法提出并实现了新的并行化策略。针对通信时间过长的问题,提出了改进方法。最后通过benchmark测试函数,将并行化量子粒子优化算法和二进制遗传算法、十进制遗传算法、粒子群优化算法的并行化方法进行了仿真比较,并对结果进行了分析。     

基于分组混沌PSO算法的模糊神经网络建模研究

为改善记忆功放建模的精度,且针对粒子群算法早期收敛速度较快,但在后期易陷入早熟收敛,局部最优等特点,提出了一种分组并行混沌粒子群优化算法（Grouping Parallel-Chaotic Particle Swarm Optimization,GP-CPSO）,将分组粒子群优化算法与混沌思想相结合,并用该算法优化动态模糊神经网络（Dynamic Fuzzy Neural Network,DFNN）参数,建立DFNN功放模型。引入分组的CPSO群算法,将种群划分为若干个组,每组单独计算,大大提高了收敛速度,同时将混沌思想运用到每个粒子当中去,避免早熟和局部最优,缩短了迭代时间。通过仿真结果可以看到,GP-CPSO优化后的动态模糊神经网络建模的训练误差减小到0.1以内,收敛速度提高32.5%,从而验证了这种建模方法有效且可靠。     

基于三次样条插值的自动入库泊车免疫粒子群改进算法

传统自动入库泊车轨迹优化算法不易寻到光滑、精确且优化的泊车轨迹。结合智能自动入库泊车原理,本文提出一种基于三次样条插值的自动入库泊车方法,从而获得理想优化的泊车参考轨迹。为了有效地提升自动入库泊车轨迹寻优算法的性能,以泊车轨迹最短作为优化目标来选定一组合适的泊车位置参考点,在三次样条插值的基础上,又提出一种免疫粒子群改进算法。首先,为提升算法全局搜索性能和收敛速度,引入自适应变异策略;然后,引入免疫机制来有效提升其全局优化能力。测试函数及自动入库泊车实际算例的仿真结果表明,所提出的自动入库泊车免疫粒子群改进算法具有更高的寻优精度和较快的收敛速度。     

用协同演化并行PSO重构扩展的超二次曲面模型

针对用传统方法难以求解的扩展的超二次曲面三维模型参数拟合问题,提出了用协同演化的并行粒子群优化算法求解的新方法。通过对扩展的超二次曲面三维表示特性的研究,设计和实现了基于岛屿群体模型的并行粒子群优化算法,并用协同演化的思想,将约束非线性优化转化为极小极大问题进行求解。实验结果表明用协同演化的并行粒子群优化算法重构扩展的超二次曲面三维模型,扩大了模型表示能力,建模精确且效率高。     

自适应惯性权重的分组并行粒子群优化算法

针对岛屿模型的并行粒子群算法没有根本改变粒子速度更新的问题,提出一种自适应惯性权重的分组并行粒子群优化算法。该算法在迭代过程中能自适应地选择加入分组的数量,同时对各组粒子的惯性权重按照组内最优位置的变化进行自适应调整。各组运用多线程技术并行处理,粒子间采用新的信息共享的方式。仿真结果证实,该算法具有较高的收敛速度和收敛精度。     

一种随机粒子群算法及应用

为提高粒子群算法的优化效率,在分析量子粒子群优化算法的基础上,提出了一种随机粒子群优化算法。该算法只有一个控制参数,搜索步长由一个随机变量的取值动态决定,通过合理设计控制参数的取值,实现对目标位置的跟踪。标准测试函数极值优化和聚类优化的实验结果表明,与量子粒子群和普通粒子群算法相比,该算法在优化能力和优化效率两方面都有改进。     

微粒群并行聚类在客户细分中的应用 *

提出了基于自适应微粒群优化的并行聚类算法 ,采用了任务分布方案和部分异步并行通信 ,降低了计算时间。这种并行自适应微粒群算法结合了并行微粒群算法的快速寻优能力和自适应参数动态优化特性 ,保持了群体多样性从而避免了种群退化。最后将该算法应用于电信客户细分中。实验证明 ,该算法在并行机群上具有了较好的准确性、加速性和可扩展性。     

异构系统中基于可用性的粒子群任务调度算法

任务调度技术是并行分布式系统中的关键技术之一,对系统的性能起着重要作用,但通常情况下大型系统的任务调度问题属于NP问题。而现代启发式生物进化算法是找出很多NP问题近似解的有效方法。本文将粒子群算法应用于基于可用性的网格系统调度中,提出了一种调度算法,对算法的性能进行了理论分析和模拟实验。结果表明:和最近文献中的基于可用性的调度算法SSAC相比,所提出的新算法在保证系统资源具有同样的可用性条件下,能够产生更好的调度长度。