关于求解难组合优化问题的蚁群优化算法

1.引言组合优化问题在规划、调度、资源分配、决策等工程问题中有着非常广泛的应用.在问题规模较小时,可以使用分支定界法或动态规划方法等来求解.当问题规模增大时,解的数目虽然有限,但呈指数增长,要在合理时间内求得准确的最优解实际上已不可能.为此,人们设计了各种启发式算法.近年来,最重要和最有希望的一个研究领域是构造'师法自然'的启发式.它们类比社会系统、物理系统、生物系统等的运行机制,设计算法在问题的解空间中进行非确定性搜索.

组合优化问题中遗传算法的局限性及其改进模式

遗传算法在解决多峰函数求解、多目标规划和生产调度等问题时 ,相比其它优化算法具有一定的优势 ,但仍存在严重的局限性 ,尤其表现在组合优化的求解问题中。为此 ,提出一种“生物进化过程 =遗传操作 +免疫功能”的新模式 ,并通过生产调度的求解问题验证了该算法的有效性。

模拟植物生长算法在组合优化问题中的应用:研究进展

首先介绍了系统文献综述方法论与操作流程,从不同维度给出了文献分类标准;然后基于行政机构和出版来源分类标准,梳理了模拟植物生长算法(PGSA)的研究现状;接着分别针对电力系统、应急管理、设施选址、斯坦纳树、车间调度和旅行商等组合优化问题,对PGSA应用的代表性研究进行了综述,重点介绍了PGSA在若干领域的应用;最后从不同视角总结了已有研究成果,并指出PGSA解决组合优化问题的未来研究方向和具体内容。

一种求解组合优化问题的演化算法

从蚁群算法中得到启示,将信息素的观点引入到求解组合优化问题的演化算法之中,提出了一种基因优化算法.该算法直接在基因的层面上进行优化,能学习劣解的基因,并用信息熵作为结束条件的判据.最后用该算法解决了两个典型的组合优化问题,取得了较好的结果.

组合优化问题简约与算法推演

针对组合优化类问题定义了代数结构模型,从问题的形式规约出发,通过一阶谓词和量词演算将问题逐步简约为搜索空间更小、复杂度更低的子问题,根据问题的简约关系推导出求解算法,并在构造算法的同时也证明了算法的正确性.开发了原型系统以支持上述形式化的开发过程.这种算法推演技术能够显著提高算法程序设计的自动化水平,而问题简约的思想也更有利于对算法本质特征的理解.

用改进的噪声混沌神经网络模型求解组合优化问题

混沌模拟退火方法 (CSA)在解决组合优化问题时有很强的搜索能力 .其中系数α代表能量函数对动态性的影响 ,α太大 ,能量函数影响太强 ,以至于无法得到暂态混沌现象 ,α太小 ,能量函数的影响太弱 ,从而无法收敛到最优解 .提出了一种自适应参数动态调整方法 ,随着能量函数的逐渐减小 ,通过加大 α,保持能量函数在整个搜索过程中对搜索动态性保持一定的影响 ,从而加快搜索速度 ,同时保持搜索的精度 .计算机仿真结果表明 ,在保持和增强搜索能力的同时 ,文中动态参数算法所用时间与现有的算法相比可以减少 2 0 %～ 5 0 % .

一种改进混沌神经网络及其在组合优化问题中的应用

在传统的混沌神经网络模型基础上,提出了一种改进的混沌神经网络(ICNN) .通过引入时变的输出函数增益和修正自反馈系数的表达式,使该模型可有效地控制Sigmoid输出函数图形的陡度和模型演化中混沌动态的收敛过程,从而拥有更丰富的神经动力学特性与初值鲁棒性.该模型可有效地解决一系列组合优化问题(COP) ,解决了10个与4

组合优化问题的一种精确求解方法

本文分析了深度优先搜索方法 (DFS)和广度优先搜索 (BFS)方法的特点 ,提出了一种混合使用动态规划方法和下界 (上界 )算法的精确求解方法求解组合优化问题。实验结果表明 ,下界 (上界 )非常接近问题的最优值时 。

基于Anytime算法的组合优化问题求解

介绍一种基于Ａｎｙｔｉｍｅ算法的组合优化问题求解框架，并报告了对ＴＳＰ问题进行求解的实验。实验结果表明，上述框架可以较好地协调问题的复杂度与求解时间要求之间的冲突。

组合优化问题反问题的研究进展

本文重点介绍了组合优化问题反问题的研究进展。具体内容包括:线性规划问题反问题、最短路问题反问题、最小费用流问题反问题和网络容量扩充问题反问题的提出背景、研究成果、应用前景及一些可能的研究方向。

组合优化问题的启发式搜索

组合优化是一个离散最优化问题,在规划,调度,资源分配,决策等问题中有着非常广泛的应用。入们已经认识到,组合优化问题的计算复杂度高,属于NP难一类的问题,除了枚举一部分解空间之外,

求解组合优化问题的改进型量子进化算法

根据组合优化问题的特点,提出了一种求解组合优化问题的改进型量子进化算法。借鉴小生境协同进化思想初始化种群,增加了个体多样性;采用动态策略调整量子门旋转角,加快了收敛速度;采用"优体交叉"策略实施染色体交叉操作,增强了局部搜索能力。利用典型组合优化问题——2个多维0/1背包问题实例对算法性能进行验证,结果表明了该算法的可行性和有效性。

强化学习求解组合优化问题的研究综述

组合优化问题广泛的存在于生产实践的各个领域,解决组合优化问题的主要手段通常包括使用由领域专家人工设计的启发式算法以及设计成熟的求解器,按照一定顺序构建一个解决方案.而随着实际问题复杂度逐渐的增加,这类方法无法于在线求解方面取得很好的效果,得到的结果可能往往是次优的.而强化学习给出了一个很好的替代方案,通过对智能体模型的良好训练,迅速地对此类问题进行求解.故回顾了近年来将强化学习框架应用于组合优化问题的研究,对其基本原理、相关方法、应用研究进行总结和综述,并指出未来该方向亟待解决的若干问题.

组合优化问题的人工鱼群算法应用

优化组合问题在现实生活中应用普遍,而且工程代表性强,可是想要实现最优化求解不容易,当今组合优化求解的主要方式采用启发式算法。人工鱼群算法是新型的群智能优化的算法,它的原理简单易懂,收敛速度快捷,求解精度颇高。最近几年得到了重视和广泛应用。

具有限额约束的投资组合优化问题的量子进化算法

将量子进化算法应用到投资组合优化问题中,设计了一种具有限额约束的投资组合优化问题的量子进化算法.首先,考虑收益与风险的均衡性,提出了一种新的收益风险评判准则,并以该准则为目标优化投资配置;其次,改进了初始种群生成方式,给出了量子染色体的编码、解码技巧及自适应量子门旋转策略;设计检查修复算子将染色体简单解码得到的解修复为问题的可行解.实证分析检验了量子进化算法的可行性和有效性,结果显示,量子进化算法能够有效消除算法早熟问题;设置的风险水平越低,收益率增长越明显;收益率随着风险水平的上升而增大,最后逐渐趋于稳定;算法具有较好的稳定性和可靠性.

圈图上的两类组合优化问题

在圈图上研究了两类组合优化问题.第一类问题主要研究在要求图中各边的最大调整费用不能超过给定预算时,如何对各边权进行调整,使得其他各顶点到给定顶点的距离之和最大,得到了线性时间算法;第二类问题主要研究在要求圈图上的所有边的调整费用之和不超过给定预算时,如何对各边权进行调整,使得某一固定顶点到给定顶点的距离尽可能的大,得到了求解该问题的多项式时间算法.

基于LINGO语言求解组合优化问题

LINGO9.0的主要功能是求解大型数学规划问题,但利用其求解组合问题尚未发现这方面的文献。本文从组合优化方面的一个经典问题———皇后问题入手,引入攻击函数,将该组合问题转化为一个线性规划问题,利用LINGO软件求解,取得了比较好的应用效果。但由于受到软件的限制,其求解规模还是受到一定的限制。

基于模拟退火算法组合优化问题的求解

文章基于模拟退火算法求解组合优化问题,首先给出了模拟退火算法的基本原理,并对模拟退火算法的核心Metropolis准则进行分析,指出迭代的初期,模拟退火算法以较高的概率跳出当前最优解,其目的是保证算法的全局收敛能力,在迭代的末期,模拟退火算法以较低的概率跳出当前最优解,其目的是在最优解附件搜索提高算法结果的精度。然后通过仿真算例证明模拟退火算法求解组合优化问题的有效性,进一步对仿真结果与分支界定算法仿真结果比较,发现仿真算例存在多个极值点,在原有基础上进一步对模拟退火算法的Metropolis准则进行改进,同时输出组合优化调度问题的多个极值点。

求解一类组合优化问题的混沌搜索法

把混沌引入各种传统的优化计算模型中以避免系统落入局部最优陷阱 ,是一种行之有效的方法 .本文提出一种利用混沌搜索一类组合优化问题最优解的模型 ,并对其进行了理论分析和数值模拟 .与混沌神经网络模型相比 ,本模型避免了模型参数选择的难题 ,具有实现方便 ,寻优效果好的优点 。