Analyses of solution of circles packing problem with space structure constraints of equilibrium

带平衡约束的packing问题属于NP-hard问题，不同问题的函数往往对应不同的解空间结构，解空间的结构对算法的寻优搜索效果有很大影响．以一类2D带平衡约束的圆形packing问题（转动圆桌平衡摆盘问题）为例，利用主元分析，对用进化算法求解的该问题的解空间结构进行分析，给出可视化主元地貌图，指出该问题的主元解空间结构是一种极限突变和对称的多模态的地貌结构．该解空间结构可以为构造具有针对性的新算法或选择算法提供理论依据．     

一个基于蚁群优化解决2D packing问题的算法

2D packing问题是一种二维变量的打包问题,是典型的组合优化问题.本文首先通过贪婪方法得到一个初始解,然后利用经典的最大、最小蚂蚁算法作为解决问题的主要框架,并针对该问题将一种特定的局部搜索算法整合到主算法框架中.通过实验结果表明,该算法在解决此类问题上具有一定的优势.     

带约束的离散全局优化问题的填充函数法

通过构造一个新的双参数填充函数求解带约束的离散全局优化问题的全局最优解,研究了填充函数的分析性质,并据此给出了带约束的离散全局优化问题的一个填充函数算法.数值试验证结果表明该算法是可行的、有效的.     

带约束PSO算法的最优多带协作式频谱感知

针对无约束粒子群优化(PSO)算法在进行多带协作频谱感知时存在难以控制系统总干扰的问题，设计了一种带约束PSO算法的最优多带协作式频谱感知方法.该方法通过引入惩罚函数，将带约束条件下的优化问题转化为无约束优化问题.仿真实验结果表明，相对于无约束PSO算法，带约束PSO算法能够解决带约束的多带协作式频谱感知问题，所得最优解满足约束条件，避免造成总干扰过大.     

主元加权迭代法求解病态线性方程组

由于病态线性方程组的系数矩阵条件数很大,使用迭代法求解病态线性方程组时,收敛速度慢且数值解的精度很低.针对此问题,设计了一种主元加权迭代算法.该算法在系数矩阵主元上叠加一个权值,以此来降低系数矩阵的条件数.最后以希尔伯特矩阵构成的病态线性方程组为例,对提出的主元加权迭代算法和高斯-赛德尔迭代法以及雅克比迭代法进行了测试.对比试验结果表明:主元加权迭代算法能有效地提高数值解的精度.     

有容量约束车辆路径问题的蒙特卡洛模拟算法

带容量约束的车辆路径问题是一个NP-hard问题,针对此问题将蒙特卡洛模拟方法与流行的节省算法结合,提出Flag-MCS-CWS算法,该方法通过对CWS算法得到的节省序列进行蒙特卡洛模拟,适用于不同节点数、不同车辆载重量的车辆路径问题.在标准数据集测试,相比当前最优解有平均0.75%的改进,为车辆路径问题提供了更加有效的解决方案.     

求解带性能约束凸多边形布局的混合算法

针对带性能约束的凸多边形布局问题,设计了一种波纹探测启发式定位算法(REHA),并将其与广义模拟退火算法(GSA)相结合,形成混合算法.波纹探测启发式算法模拟波纹的现象,以圆形容器的圆心为中心,构造同心圆,逐步增大同心圆半径向外探测,根据同心圆与质心临界多边形的交来确定布局物的放置位置.该算法同时兼顾布局问题的紧凑性和静平衡约束,是一种定位启发式方法,其解的质量受布局顺序的影响.利用广义模拟退火算法优化布局顺序,形成混合算法,并将其与经典的模拟退火算法作分析对比,数值试验验证了提出算法的有效性.     

基于拉格朗日松弛的水灾逃生路径规划

研究了假设路段通行时间为随机变量的交通网络约束最短路径问题.建立0-1整数规划模型,求出最小期望通行时间路径.除流量平衡和路段通行能力约束外,还引入了唯一通路选择约束以保证最终只能生成最优路径.然后,提出了拉格朗日松弛法对难约束进行松弛处理,并将松弛模型分解成两个子问题.结合次梯度算法、标号修正算法和k-最短路径算法设计了一个算法框架,以最小化上下界的差距寻找近似最优解,用改进的算法框架进行求解.最后将该框架应用于龙岩市新罗区进行了计算试验.结果表明,该算法能够找到相对间隙较小的高质量解,验证了该方法的有效性.     

带队列约束的RHFS列生成调度算法

为有效提升多重入车间的生产效率,考虑实际生产中队列约束,提出了基于列生成算法的可重入混合流水车间的调度方法.首先对两阶段生产调度问题进行描述,以最小化工件总完成时间为优化目标,建立数学规划模型.针对该调度模型提出列生成算法,设计带多重决策的动态规划方法来求解工件级子问题,为更快收敛,主问题求解中采用自适应加速策略.在使用分支定界将得到的解整数化的过程中,构造列池并设计局部变异.最后,对各种不同问题规模进行了数值实验,结果表明所提出的调度算法是有效可行的.     

具有反向学习的多目标元胞遗传算法的空间桁架结构优化设计

为了解决具有多约束的桁架结构问题,提出一种具有反向学习的多目标元胞遗传算法应用于空间桁架结构多目标优化设计中。根据分析元胞遗传算法特点,引入一种反向学习策略、差分进化策略和约束处理技术。通过标准测试函数对比分析,算法能很好地保持Pareto解集的收敛性和均匀性。针对空间桁架结构优化的数学模型,采用实数编码和个体修正方法,将该算法对72杆空间桁架优化问题进行求解,并与MOCell的优化结果进行比较。结果表明,新算法获得的Pareto解集更加均匀,极端点值域更宽广,具有一定的工程实用性。     

基于Backbone的空间收缩与划分算法

搜索空间的规模和复杂程度是决定问题求解难度的重要因素,而解空间的信息往往可以引导搜索找到最优解。在已知JSP空间结构的基础上,提出一种空间收缩与划分算法。算法利用搜索算法获得的较优解,结合组合优化问题解的backbone的概念,将搜索空间收缩并划分为一个或多个优解域,在优解域内再进行小规模问题的优化。该算法不必在求解前或求解过程中进行大量的统计分析工作,可以利用求解信息对解空间的地形进行估计,提高求解速度和解的质量。实验结果也证明了算法的有效性。     

一种基于信息熵的多种群遗传算法

通过模型变换建立了一种约束优化的演化设计模型．并构造出求解此模型的多种群空间收缩遗传算法．利用最优解在各种群中的存在概率将信息熵概念引入进化过程,构造出一种含有熵的多目标优化模型,利用该模型可以直接显式地给出作为拉格朗日乘子的种群最优解存在概率,从而得出多种群遗传操作的空间收缩因子,控制各种群寻优搜索时解空间的收缩．用种群的多样性避免遗传进化的早熟现象,以空间收缩尺度作为停机判据,有效地控制了算法的收敛．数值算例显示,熵的介入使随机搜索类进化算法的寻优目的性大为增强,从而提高了演化设计的计算效率。     

基于混合蛙跳算法的聚类问题研究

混合蛙跳算法(SFLA)是一种基于子群——种群进化模式的群智能优化算法,通过自身特有的分组算子实现不同解的合理分布,能够有效跳出局部最优;局部位置更新算子只对最差解进行更新,加快了算法的收敛速度。针对传统算法在解决聚类问题时存在聚类精度低和算法收敛速度较慢等缺点,本文提出了运用混合蛙跳算法来解决聚类问题,通过采用基于图像二维空间像素特征提取的方法构造青蛙个体解,设计青蛙进化的目标函数和青蛙位置更新策略,并通过数字,图形等验证了该算法解决聚类问题的有效性.     

基于可替换路径对的多用户均衡交通分配算法

针对多用户均衡交通分配问题，依据多用户均衡条件，给出了该问题的变分不等式模型和间隙函数。利用可替换路径对的概念，设计了基于可替换路径对的多用户均衡交通分配算法。在大规模交通网络上，对比分析了提出的交通分配算法、外梯度算法、基于用户的对角化算法和基于起点的对角化算法等的性能。数值结果表明，提出的基于可替换路径对的交通分配算法在求解精度、算法效率以及稳定性等方面都显著优于其他算法。     

基于多邻域策略重心反向学习的差分进化算法

针对标准差分进化(DE)算法探索能力差、难以逃出局部最优的问题,提出一种基于多邻域策略和邻域重心反向学习的差分进化算法(MCOBDE)。该算法根据当前进化状态动态地选择不同的邻域策略:在算法前期大概率选择局部邻域策略,其采用的环形邻域结构有利于探索种群空间;在算法后期大概率选择全局邻域策略,其采用的星形邻域结构能加快算法收敛。同时在不同的邻域结构下辅以重心反向学习,能进一步扩大搜索范围,避免陷入局部最优。通过与其他DE算法针对15个CEC2015测试函数在低维和高维情况下的实验对比,证明本文算法具有较快的收敛速度和较高的收敛精度,能有效克服探索能力差、早熟收敛的缺点。     

基于离散粒子群优化的MPSoC节能调度算法

为了降低多核片上系统MPSoC在应用中的能耗,在MPSoC上提出了基于优化离散粒子群算法的节能任务调度算法.通过比例选择算子生成初始种群,以任务在MPSoC上不同内核执行的能耗作为解空间,粒子群在整个解空间上搜索最低能耗调度方案,并在算法中优化了粒子群算法的局部早熟问题,使算法性能进一步提升.仿真实验表明:基于优化离散粒子群算法的节能调度算法与常用的3种调度算法相比,能耗得到了降低,且算法的截止期错失率并没有升高,保证了算法的整体性能.     

求解矩形放置问题的亲属帮助遗传算法

用基于几何位置的方法求解矩形放置问题,解空间有限,且包含最优放置,但解空间太大。为了解决这个问题,将基于几何位置的序列对算法作为遗传算法的编解码过程,同时根据序列对编码空间中局部最优解相互间保持一定距离的特点,从父代中随机地选出一定比例的个体,用这些个体作为排斥体,使子代个体与排斥体都保持一定的距离,有效地避免了种群过早收敛到局部最优解。3组试验表明:这种算法在问题规模小时能有效地搜索到全局最优解;在问题规模较大时,能得到较好的结果。     

Koch曲线的序数理论与新算法设计

生成Koch曲线的常见算法是递归算法、Ls算法和IFS算法.针对现有三种算法的局限性,提出Koch曲线的序数理论,设计生成Koch曲线的OV算法.OV算法不需要递归调用,不占用大量空间,并且兼容于LS算法,还可以推广到Koch结构.最后,以OV算法为基础,提出LS2算法,有效地解决了LS算法的问题.     

基于文化混洗蛙跳算法求解连续空间优化问题

针对混洗蛙跳算法在求解高维函数时易陷入局部最优解的问题, 提出一种文化混洗蛙跳算法, 利用群体空间和信念空间的个体通过接受函数和影响函数完成 信息交换和全局寻优. 首先, 信念空间个体通过螺旋更新和随机游走的方式在较优个体附近寻找更优个体; 其次, 群体空间的最差个体通过借鉴不同知识平衡局部寻优与全局探索的关系, 进而提高算法的寻优精度并加快收敛速度; 最后, 将该算法与12种智能算法进行寻优对比, 对典型高维基准函数的测试结果表明, 该算法的收敛精度和计算速度均较好.