贪心算法及其实例探究

贪心算法就是在求最优解问题的过程中,依据某种贪心标准,从问题的初始状态出发,直接去求每一步的最优解,通过若干次的贪心选择,最终得出整个问题的最优解的方法。贪心算法所作的选择可以依赖于以往所作过的选择,但决不依赖于将来的选择,也不依赖于子问题的解,因此贪心算法与其它算法相比具有一定的速度优势。如果一个问题可以同时用几种方法解决,贪心算法应该是最好的选择之一。     

自适应代表个体选择方法的协作协进化算法

协作协进化算法中,代表个体选择按贪心度不同可分为最优选择和随机选择.最优选择对于大多数子模块之间关联性不是很强的问题都较为有效,但对于子模块间有很强关联性的问题,随机选择比最优选择更为有效.所以,提出一种自适应代表个体选择方法的协作协进化算法,该算法通过进化停滞判断函数将最优选择和随机选择两种代表个体选择方法结合起来.仿真结果表明,该算法对于子模块间强弱不同的问题都能有效的找到解.     

完全图哈密尔顿圈遗传算法的MATLAB模拟实现

求解完全图上的哈密尔顿圈是典型的组合优化问题,遗传算法是解决此类NP问题的一种较理想的方法。对基本的遗传算法进行改进,在选择操作和变异操作中加入贪心优化思想,使算法获得更优的全局最优解。在MATLAB环境下模拟实现了哈密尔顿圈的经典问题———TSP( travelling salesman problem)旅行商问题,从而验证了该算法的可行性和正确性。     

完全图哈密尔顿圈遗传算法的MATLAB模拟实现

求解完全图上的哈密尔顿圈是典型的组合优化问题,遗传算法是解决此类NP问题的一种较理想的方法。对基本的遗传算法进行改进,在选择操作和变异操作中加入贪心优化思想,使算法获得更优的全局最优解。在MATLAB环境下模拟实现了哈密尔顿圈的经典问题——TSP(travelling salesman problem)旅行商问题,从而验证了该算法的可行性和正确性。       

空洞探测的数学模型与算法

为了解决最优空洞探测计算复杂度较高的问题,利用贪心算法对空洞探测问题的数据进行分析后设定了合理的误差,以理论时间与实际时间的误差作为贪心选择标准,最终确定空洞所处的区域以及空洞的个数.这种算法复杂度为多项式级.     

求解一类二层非线性规划问题的全局优化方法

根据模拟退火算法能够有效地求非凸数学规划全局最优解的特点,对一类二层非线性规划问题的上、下层问题求解,并根据二层规划的特点,给出了求解一类二层非线性规划问题全局最优解的有效算法。该算法思路清晰,易于在计算机上实现。     

有限阶段非马氏决策规划的ε最优策略及算法

建立了一类转移概率依赖于历史的有限阶段决策规划模型（即有限阶段非马氏决策规划模型）,并对其ε最优策略问题进行了讨论．给出相应的最优方程,证明了确定性ε最优策略的存在性,最后得到求ε最优策略的算法并证明了该算法的有效性．     

基于时间最优的费诺编码算法研究与设计

针对费诺编码的算法研究与实现问题,提出一种最优偏差值与分治法相结合的算法。算法以最小偏差值为目标,在概率序列中寻找最佳断开位置,通过最佳断开位置实现费诺编码。鉴于费诺编码算法的递归属性,分别设计了编码的多模块算法和单模块算法。通过对算法时间复杂度的分析,对设计的算法进行了改进。算例仿真表明,不同算法对同一信源编码所耗费的时间差异很大,选择时间最优的费诺编码算法能更好地满足费诺编码系统对适时性的要求。     

图着色问题的蚂蚁算法研究

随机蚂蚁着色算法是根据蚂蚁算法的搜索机制和反馈功能提出的解决图着色问题的新算法,继承了蚂蚁算法快速收敛以及跳出局部最优解的优良特性,结合传统图着色算法的着色思想,提出了逆序蚂蚁着色算法和贪心蚂蚁着色算法,进一步提高了求解质量,加快了收敛速度.实验结果证明了逆序蚂蚁着色算法和贪心蚂蚁着色算法的优良特性.为了合理选取蚂蚁着色算法参数,进行了大量随机图着色实验分析,得出了关键参数的最佳取值范围.     

多人合作多目标交叉规划的一种算法

随着现代社会经济的飞速发展,各个经济系统的联系不断加强,如何实现各个系统的利益最大化和成本最小化,成为人们日益关注的焦点.针对该类问题,研究了一类多人合作多目标交叉规划.首先给出了多人合作交叉多目标规划的模型,从该模型出发给出了求解多人交叉多目标规划的一种算法:对交叉规划问题中的每个子目标函数求解,将交叉规划问题转化为非线性规划问题,通过引入罚因子,用外罚函数法求出非线性规划的最优解.该解也是多人多目标交叉规划问题的非劣解,从该非劣解出发进行搜索,寻找最优解.最后通过算例验证了算法的可行性和有效性.     

贪婪算法在InSAR相位解缠中的应用

针对干涉SAR二维相位解缠问题，提出了一种利用贪婪算法提高解缠精度的新方法．首先从理论上推导了贪婪算法相位解缠的基本原理，然后提出了一种迭代加权的贪婪算法，以克服传统贪婪算法解缠结果收敛于局部最优解的弊病，最后利用仿真数据进行了实验分析，验证了本文算法的有效性．仿真实验结果表明，该算法实时，高效，准确．     

路径重链接的GRASP最优化无线自组织网络能耗

针对无线自组织网络的能耗和容错问题,提出了一种基于路径重链接的贪婪随机自适应搜索程序(GRASP)启发式算法.首先,通过构建双连通图使得任意2个连通的节点之间至少有2条通信路径,从而提高容错能力;然后,在双连通网络的基础上,利用对功率的操作进行局部搜索,找出功率分配的最优值,从而达到优化整个网络能耗的目的.在随机生成的非对称测试问题上的仿真实验结果表明,相比MST-aug算法和贪婪算法,提出的算法在欧氏实例中的总能耗分别降低了37.85%、5.39%,在随机实例中的总能耗分别降低了74.63%、3.15%,且明显降低了边干扰和节点干扰,适用于故障容错需求较高的无线自组织网络环境.     

用离散粒子群优化算法求解WTA问题

为了提高武器-目标分配(WTA)问题的求解效率和性能,提出了一种用离散粒子群(DPSO)算法求解此问题的新方法.对粒子群算法中的速度和位置进行了重新定义,使其可求解WTA这类离散组合优化问题,并采用贪心的启发式策略对迭代产生的方案进行调整,以利于快速找到最优或次优的分配方案.算法测试表明新算法执行速度快,结果令人满意,...     

非连通无线传感器网络的最少传感器节点部署

传感器节点的部署包括连通网络和非连通网络2种情况. 为了最小化网络部署开销,对非连通网络的传感器节点部署问题进行了研究,建立了整数线性规划模型,并证明该问题为NP complete问题. 为找到该问题的近似最优解,通过理论分析确定了传感器节点的候选部署区域,提出了一种启发式的传感器节点贪婪部署算法,迭代地将传感器节点部署到覆盖目标点数最多的候选部署区域,直到覆盖所有目标点. 通过仿真实验将所提出的贪婪部署算法和现有的遗传算法以及问题模型的最优解进行了比较,验证了算法的有效性.     

应用运输问题和贪心算法的电力交易行为分析

为了找出南方区域电力市场互联电网效果不佳的原因，在满足电力撮合交易的条件下，运用带权拟阵的贪心算法分析了现行模拟电力市场中购售电双方存在的“就近购买”行为；采用平衡运输问题的线性规划模型分析了南方电力市场购电方存在的“购电整体最优”方案.指出联网效果不佳不是技术上的原因，而是由于在统一电力市场电能交易中存在着整体和局部利益的冲突.省间电力交易的价格应经过严格的经济调度和交易计划分析后确定，送电端所获利润应与受电端分享，依靠市场来解决问题.     

利用自主策略机制实现联合无线资源管理

提出了一种基于案例推理的最优策略产生方法,用于异构无线网络系统自主高效的无线资源管理及优化.该方法利用案例检索与匹配算法,从案例库中寻找最合适的再用策略;利用基于相似度概率的策略再用算法,改进新策略学习的效率和质量;应用贪婪算法,产生没有可用案例情况下的应对策略.此外,该方法在学习的基础上对策略案例库进行实时的更新.仿真结果表明,该算法具有高效的在线学习能力,能够有效提升网络在频谱效用和阻塞率方面的性能,实现自主的无线资源管理.     

基于TSP的孔群加工路径优化算法

建立以孔群加工最短路径为优化目标的数学模型,采用蚁群算法与2-OPT算法相融合的优化方法,研究了模具顶针板孔群加工刀具路径优化问题.结果表明,该融合算法加快了收敛速度,可有效避免陷入局部最优解,加工优化路径比贪心算法缩短12.34%,比基本蚁群算法缩短14.78%,即有效缩短了加工路径,减少了空走刀时间,提高了数控加工效率.     

基于贪婪搜索的IEEE 802.16j带宽分配算法研究

为满足IEEE 802.16j网络中不同类型业务的带宽需求, 同时达到可接入用户数最多的目的, 提出了一种基于贪婪搜索的基站、中继站联合带宽分配算法. 其中, 固定带宽的主动授权业务由中继站分配带宽; 基站分配其他类型业务所需的最少带宽. 该算法利用贪婪搜索寻求最优用户组, 并将剩余带宽分配给该组的用户. 仿真结果表明, 该贪婪搜索带宽分配算法能保证网络接入的用户数最多, 且复杂度低于一般的穷举搜索带宽分配算法.     

考虑组件复制的SA软件部署可靠性研究

复制软件组件能提高服务的可靠性和系统可靠性,然而,复制额外的软件组件需要消耗系统可用系统资源.为了充分利用系统可用资源,得到更高的可靠性优化值,设计了启发式的贪婪复制算法,该算法根据单位带宽的可靠性优化值增量OB和单位内存的可靠性优化值增量OM,利用贪婪思想选择出将被复制的两个软件组件集合,其中具有更高可靠性优化值的集合是该算法确定的将被复制的软件组件集合.实验结果表明:当给定有限的系统可用资源时,与贪婪复制算法相比,该算法能得到更高的可靠性优化值和更高的服务可靠性.