贪婪法在算法设计中的应用与局限

利用贪婪法进行算法设计时速度快,但由于算法只是考虑局部最优解,未从整体最优上加以考虑,有时不能得到全局最优解.以背包问题、克鲁斯卡尔算法为例系统阐述了贪婪法在算法设计中的应用,又以找零钱、数塔问题、货郎担问题为例对于贪婪法求解以及实际最优解做了对比,系统地分析了贪婪法在算法设计中的局限.     

基于表上作业原理的运输问题计算机寻优算法

针对运输问题寻优的高度复杂性,提出了一种基于表上作业原理的计算机寻优算法。在算法中,采用"最小元素法"获取初始基可行解,采用"位势法"获取检验数数组,采用"递归过程"获取闭合回路数组,根据闭合回路数组和基可行解获取调整量,根据闭合回路数组、调整量对基可行解进行调整,通过While循环不断寻优直到最小检验数非负。While循环退出时,若存在0检验数,则任选一个0检验数,以其为起点寻找一个闭合回路数组,通过调整得到随机最优解。应用案例表明,该算法实现了表上作业求解过程的计算机程序化,提高了计算效率、确保了计算准确性。     

求解一般D.C.规划的全局最优解

给出一种求解一般D.C.规划非孤立全局最优解的算法. 该算法克服了目前一些逼近算法在计算过程中有时得到的解为不可行解、 甚至远离真正全局最优解的问题. 数值结果表明了算法的有效性.     

一种改进的量子退火算法

为了进一步提高量子退火算法在优化问题上的计算速度,对量子退火算法如何移动到新解这个问题的方法进行改进,将粒子透射系数引入到量子退火算法中,并通过透射系数来确定是否移动到新解.实验结果表明:通过透射系数确定新解的方法能在更短的计算时间内得到最优解.     

求解二次双层规划问题的全局最优解

针对现有的一些逼近算法在计算过程中有时得到的解为不可行解, 甚至远离真正全局最优解的问题, 给出一种解二次双层规划非孤立全局最优解的算法. 数值实例结果表明, 该算法行之有效.     

递归回溯法求解整数线性规划及MATLAB实现

基于递归回溯法解决整数线性规划问题的算法思想及求解过程,使用MATLAB软件编写通用程序,实现了求解整数线性规划问题.通过MATLAB中的文件存储功能,对符合要求的整数解可存储在文件中,并舍弃从该解出发的分支,从而得到了符合要求的所有整数解和最优整数解.实验结果表明,该算法达到了局部最优.     

基于DNA计算的指派问题

给出了推广的闭环DNA计算模型及其生化实验.用闭环DNA计算模型设计出了指派问题的DNA算法.对决策变量进行4组DNA编码来存放决策变量和效益值;通过有目的的终止技术和删除实验得到指派问题的全部可行解;通过批接入实验、电泳实验和检测实验获得最优指派问题的最优解.举例说明了算法的可行性.最后讨论了推广的闭环DNA计算模型的应用前景和不足之处.     

星际转移发射机会搜索方法

针对星际探测任务发射机会搜索中,等高线图法计算量大和基于遗传算法的搜索方法难以得到精确最优解的问题,提出了一种混合搜索方法.该方法根据探测任务要求,定义待搜索目标函数,并确定搜索域;结合Lam-bert定理与Gauss算法对该问题进行降维;采用全局-局部混合搜索方法求解,解决了传统方法计算量大、计算效率低、求解最优解困难的问题.以1627 Ivar小行星的交会任务为例验证了该方法,其结果表明,采用混合搜索方法可以快速获得最优的星际转移发射机会.     

基于仿射算法的确定性全局优化算法

针对传统区间算法求解全局优化问题耗时长、空间复杂度较高及收敛速度较慢的缺点,引入仿射算法及局部优化算法,给出了一种全局优化求解的仿射算法.由局部优化算法和各求解区间上待优化函数的仿射运算得到全局最优解的一个上界,再依据对各区间仿射运算的下界与全局最优解上界的比较来确定相应区间的去留,通过对不含全局最优解的子区间的删除来确定最优解所在的子区间,并最终找到全局最优解.数值实验表明,该算法相对于传统的区间优化算法有较高的收敛速度,且占用的系统资源较少.     

基于Matlab的数值分析算法演示系统开发——非线性方程的数值方法

数值分析是一门利用计算机研究分析数学计算问题的计算方法的学科.通过介绍数学软件Matlab在解决数值分析上非线性方程数值解方面的应用.利用这个基于Matlab实现算法分析演示系统,详细讨论了非线性方程数值方法经常用到的二分法、试位法、牛顿-拉普森法和割线法等方法的运用以及各种方法之间的误差比较,并用实例解释如何在求解过程选择数值方法才能获得最优解.     

基于一种新的γ-扩张凹极小化问题的割平面算法

首先,介绍凹极小化问题的有关内容及割平面算法的思想.然后,给出一种变上限函数积分法,并利用该积分法来求解凹极小化过程中γ-扩张的γ数.新算法在有限步内得到原问题的一个近似最优解,且算法的近似最优解为全局最优解.最后,通过数值试验证明了新算法是可行有效的。     

演化神经网络算法

演化算法的应用使神经网络的训练有了一个崭新的面貌,目标函数既不要求连续,也不要求可微,仅要求该问题可计算,而且它的搜索始终遍及整个解空间,因此容易得到全局最优解.应用这一思想,本文提出了一种新的演化神经网络算法—EPANN,并通过算法实例说明EPANN是可行的.     

多目标线性不可微指派问题的优化简算法

建立了最短时限指派问题的多目标线性不可微数学模型,根据该模型的特征,找出其中一个目标函数的最优解F1,进而转化为与其等价的单目标规划模型.定义了基元素的概念,在耗时矩阵中标记不大于F1的元素,并将大于F1的元素置换成无穷大数M,划去全部基元素所在的行与列得到降阶矩阵,对降阶矩阵实施匈牙利算法得到最优指派.经分析,该算法为多项式算法,因而是有效的.     

一种求解变量有界非线性规划的全局最优解新方法

提出了一种求解变量有界非线性规划的全局最优解新方法——不可行域移除(IRIR)法.在优化过程中,先计算原最优化问题的不可行域,然后在原最优化问题的求解空间中移除确定的不可行域,使得新的求解空间不断缩小,并通过研究不可行域的线性表达,在不影响最优解的前提下将非线性约束转化为线性约束,以求解非线性规划问题,其特点是所得最优解对原最优化问题约束函数的凸性和优化迭代起始点的位置不敏感.同时,阐述了IRIR法的原理和实现过程,在序列二次规划(SQP)算法的基础上,应用数值算例和弹簧设计2个典型实例,以验证IRIR法的可行性和正确性.结果表明:IRIR法可以有效降低原最优化问题的求解难度,且无需引入新参数,是一种具有较高求解能力和实用价值的全局最优化方法,但其不适用于求解设计变量无界的最优化问题.     

元素差额法在指派问题中的应用

元素差额法求解指派问题的目的在于克服原匈牙利法较繁琐的求解步骤，该方法提出了便于掌握的近似求法。此种方法虽在人员和任务数不多时不够理想，但当人员和任务数较大时优势明显，可以节省大量计算步骤，很方便求出近似最优解。即使非要求出最优解，也可在近似最优解基础上，通过闭合回路法进行调优，得到最优解。     

集合覆盖问题闭环DNA算法

介绍了闭环DNA计算模型及其生化实验,分析了集合覆盖问题及其数学模型.根据任何一个元素至少属于一个集合构成可行集合覆盖的原理,设计了集合覆盖问题闭环DNA算法,该算法首先对集合的0-1决策变量按照0和1的取值、对应的价值系数进行两组DNA编码并形成所有可能解;再用接入实验和删除实验筛选出全部可行解;然后用接入实验得到这些可行解的目标函数值,并用电泳实验得到全部最优解;最后通过检测实验输出所有最优解.首次提出基于电泳技术检测实验以"接入-电泳-删除"为实验顺序,可以检测多种DNA编码.算例说明了算法的有效性.     

求解安全约束机组组合问题的邻域搜索外逼近方法

提出一种求解安全约束机组组合(security constrained unit commitment,SCUC)问题的邻域搜索外逼近(outer approximation based on neighborhood search,NS-OA)法. OA将SCUC问题分解为一系列混合整数线性规划(mixed integer linear programming,MILP)主问题和非线性规划(nonlinear programming,NLP)子问题,通过MILP主问题和NLP子问题的最优解来逼近SCUC问题的最优解.为克服迭代过程中MILP主问题规模大的不足,利用SCUC问题对应UC问题的最优解为中心来构造邻域,然后在此邻域内搜索MILP主问题的最优解.数值结果表明,所提邻域搜索能有效减小搜索空间,大大提高了算法的计算效率,所提NS-OA算法能有效求解大规模SCUC问题,具有良好的应用前景.     

DNA计算在电路设计中的应用

讨论了DNA计算的机理,给出了DNA计算的基本生化实验.对电路布线问题,提出了DNA算法,即首先对导线的顺序进行DNA编码,其次通过杂交反应产生所有可行解,最后通过电泳实验得到最优解.对所得结果进行检测时采用了DNA芯片和分子信标技术,对探针进行生物素标记解读出最优解.该算法的核心运算是杂交反应,算法总的操作次数为n 3,其中n为电路布线问题的规模.最后,通过6对接线柱的例子说明了DNA算法的有效性和正确性.     

一种解决群进化算法参数设置问题的最优向量法

群进化算法是智能计算领域研究的核心内容,而算法中数值型参数的设置是影响算法搜索效率的重要因素,因此设计解决参数设置问题的方法也是群进化算法研究的重要内容.目前解决参数设置问题的常规统计方法是根据算法搜索的部分结果组成有限样本数据,依据统计最好值个数大小的判定结果来确定最优参数预设值.常规统计方法在有些测试样本数据中很难确定唯一的最优参数预设值.为了解决常规统计方法的缺点,提出了一种最优向量法,该方法可以将任意形式有限样本数据转换为向量,依据向量计算的判定规则进行最优参数预设值的确定.实验结果表明,依据获取的有限样本数据通过最优向量法找到最优参数值,采用该参数值的群进化算法搜索效率相对最优,从而验证了最优向量法的有效性.     

基于最优最小二乘的红外目标单站定位算法

为消除红外目标单站定位算法估计有偏性,解决现有估计算法中有可能出现多个解向量的问题,提出了一种基于最优最小二乘的目标估计算法.对总体最小二乘定位算法进行了研究,针对扩展测量矩阵出现最小奇异值多重的问题,构造了一个由多重奇异特征向量组成的测度函数,将该函数进行偏微分得到最优的最小二乘解;通过理论分析,证明了最优最小二乘解向量是渐进无偏的;最后,将该算法与总体最小二乘法和修正辅助变量法进行仿真对比.仿真实验结果表明,该方法在不同测量环境噪声下所得到的位置、速度误差曲线能快速地逼近克拉美罗下限,且具有更高的估计精度和稳定性,说明了算法的有效性.