改进型粒子群算法解决多维背包问题

微粒群优化算法(PSO)是一种基于种群的随机优化技术.将EDA算法与PSO算法结合起来,形成一种新的改进的算法(EPSO).算法将全局统计信息和全局最优解运用于解空间搜索,以期能更有效解决组合优化问题,最后将EPSO算法用于解决多维背包问题并进行了对比仿真实验.实验结果表明,在解决多维背包问题上,EPSO优于传统的PSO算法以及多种启发式智能算法,与此同时,EPSO算法使用更少的参数,因此更容易实现,运行更加稳定,效果更好.     

一种求解多维背包问题的和声优化搜索算法

提出了一种解决多维背包问题的和声优化搜索算法.算法采用n进制编码初始化和声记忆库,采用自适应的和声保留概率、音调调节概率和音调调节步长产生新解.通过修正算子修正不可行解,以保证解满足约束条件,然后利用非劣解集更新算法优化最优前端,使其扩大覆盖率,保证均匀性.通过20次随机实验,结果表明,该算法能够有效的克服早熟收敛。能够保持种群多样性和求解精度,具有解决复杂多维背包问题的能力。     

基于核函数分类的多维时序特征选择方法应用

研究了多维时序的特征选择问题在目标距离像识别中的应用,提出了一种基于核函数分类算法的主分量分析方法。讨论了主分量分析的原理,提出了一种基于核函数的分类算法用于多维时序的特征选择,最后利用该方法对目标距离像多维时序进行了仿真实验,实验结果表明了所应用方法的可行性和有效性。     

基于自适应小区选择的切换控制算法研究

针对现有切换控制算法的不足,提出了一种基于自适应小区选择的优先级信道预留切换算法。该算法在切换时根据各小区的负载情况,通过调整导频功率使小区间负载均衡,以系统效用最大化为目标,进行基于预留信道的优先级切换。系统效用通过多选择多维背包算法建模实现,预留信道的优先级切换通过马尔科夫排队模型实现。通过多选择多维背包建模、马尔科夫排队建模与实验仿真表明,该算法的性能在相邻小区间负载不均衡的情况下比目前切换控制所用的优先级信道预留切换算法明显提高。在负载不均衡度为6时,话音业务阻塞率与数据业务分组丢失率比目前算法分别降低0.2%和3%左右,数据分组平均最大等待时间比目前算法降低0.15s,系统小区平均吞吐量最大时升高80kbit/s/cell/MHz。     

基于扩展背包问题的的软硬件划分算法

软硬件划分问题常以时间为约束对硬件面积进行优化。随着嵌入式的发展，功耗这一因素也越来越重要，故在约束条件中加入了功耗的约束。贪婪算法是解决0-1背包问题的一种简单有效的方法，因此建立多约束的软硬件划分问题与0-1背包问题之间的联系，采用扩展的贪婪算法解决多性能指标的软硬件划分问题。利用仿真与动态规划方法的对比，进行了有效性验证。     

特征选择中B&B算法的改进及比较

B&B(Branch & Bound)算法是特征选择中的一种全局最优算法,其固有缺点是运行时间太长.用B&B算法构造一棵搜索树,在树中搜索最优的特征子集.对B&B算法的研究集中在化简搜索树从而降低搜索复杂度上,提出了几种改进的B&B算法.从原理上分析了B&B算法及其各种改进的优缺点,将这一系列算法纳入到同一个算法框架,并在此基础上提出了一种针对BBPP算法的改进算法,BBPP+算法.通过比较各种实验数据,发现改进后的BBPP+算法的运行效率比已有的B&B算法更好.     

基于随机背包算法的容量分析方法及其应用

随机背包算法作为一种容量估算方法,能够分析不同业务在不同QoS要求下的传输,可用于解决通信系统多业务容量规划问题。文章从随机背包算法的理论推导出发,详细阐述了随机背包算法的假设、原理、证明过程以及理论结果,为模型应用做好充足的理论铺垫。与传统等效爱尔兰法、后爱尔兰法和坎贝尔方法等缺乏严格理论证明的方法相比,随机背包算法具有较强的理论依据。为了进一步阐述算法在容量规划方面的应用,文章介绍了TD-SCDMA系统的基本特性,以及基于随机背包算法的TD-SCDMA系统容量规划实例。结果表明随机背包算法能对TD-SCDMA系统的容量进行合理的规划。     

基于混合遗传算法的云计算任务节能调度算法

云计算中主机和任务的数量都是十分庞大的,如何通过任务分配调度来减少成本开销和降低能耗是当前云计算和绿色计算领域研究的热点问题。根据云计算任务以及运行环境的特点,将云计算任务分配问题抽象为多维多背包求解问题,并采用改进的混合遗传算法对该问题进行求解。实验结果表明,改进的混合遗传算法能够在较短的时间内找到问题的优化解,并且根据该算法实现的任务分配策略能够有效地减少任务执行的成本开销和能耗。     

基于0-1背包问题的两种算法

0-1背包问题是组合优化领域里的一个典型问题,是属于易于描述却难于解决的NP难题,有效解决0-1背包问题具有重要意义。首先给出了0-1背包问题的描述,然后详细介绍了回溯法和分支限界法的算法思想和搜索策略,并对两种算法进行了比较和分析。     

一种改进的多目标蚁群优化算法

提出了一种改进的多目标优化问题的蚁群算法.算法选择进化算法的定义的时候,种群中一定数量的个体信息来源作为中心的扩散,多个中心点之间有一定的距离;群体中的其他个体按照离源个体最近的距离的原则归属于其中一个信息素扩散源;按照信息素扩散算法,每一信息素扩散源中的个体获得源于中心点的信息素;保留每一代群体中的中心点到下一代种群中,确保了收敛性和维护种群的多样性.最后利用多目标背包问题来测试算法的性能,并与MOA和NSGA-II算法进行了分析比较.结果表明,该搜索效率高,向真实Pareto前沿逼近效果好,得到传播的多种解决方案,是一个多目标优化问题的解决和有效的方法.     

Joint resource allocation,routing and CAC for uplink OFDMA networks with cooperative relaying

In this paper, we propose a joint resource allocation, routing, and connection admission control (CAC) scheme for uplink transmission in orthogonal frequency division multiple access (OFDMA) relay networks with cooperative relaying. For cooperative relaying, relay station can relay uplink data from mobile station (MS) to base station with cooperation of the MS using transmit diversity. Transmit diversity can be achieved by virtual MISO via distributed space–time coding. The proposed scheme jointly allocates OFDMA resources and selects path for each user with CAC to maximize the upink throughput of cooperative OFDMA relay networks. The basic OFDMA resource unit is considered as a resource element which is one subcarrier over one OFDMA symbol. An efficient multi-choice multi-dimensional knapsack (MMKP) algorithm is presented for the proposed scheme. The proposed MMKP algorithm provides a unified framework which is applicable to OFDMA networks with and without cooperative relaying. We evaluate the performance of the proposed scheme with and without cooperative relaying in a hilly terrain with heavy tree density by using OPNET-based simulation. We show that the cooperative relaying improve the uplink system throughput compared with non-cooperative relaying, and the proposed scheme outperforms the conventional link quality-based scheme in both cooperative and non-cooperative relay networks.     

改进的遗传算法求解背包问题

为提高遗传算法在解决背包问题时的局部搜索能力,在遗传算法中加入禁忌搜索的思想,用遗传算法做全局搜索,禁忌搜索辅助做局部搜索。文中阐述了遗传算法和禁忌搜索算法的基本思想,并给出了适用于背包问题的模型。通过具体事例测试改进的算法,其结果表明改进后的遗传算法拥有更好的性能和更快的收敛速度。     

改进粒子群算法在货物装载中的应用

本文采用改进粒子群算法求解货物装载问题。首先对传统背包问题进行分析，指出其在现实生活中存在的问题，提出了以最大价值为目标的更具现实意义的多目标模型，然后用粒子群算法进行求解，给出了一个算法求解的实验实例。在实现粒子群算法时，我们对基本粒子群算法进行了一些改进。实验证明采用这种改进的粒子群算法解决货物装载问题切实可行，有较高的搜索效率。     

求解0-1背包问题的基于双禁忌对象的TS算法

0-1背包问题是一个典型的组合优化问题.针对这个问题,给出了一种基于双禁忌对象的禁忌搜索求解算法.该算法首先以解向量的分量为解对象进行禁忌搜索,当这个搜索过程完成后,然后以当前最优解为初始解对象再进行禁忌搜索.实验结果表明该算法可有效地解决0-1背包问题.     

Opening the knapsack by DFTs

A new simple algorithm which uses discrete Fourier transforms for breaking the general knapsack problem (also known as the subset sum problem) is presented along with the number of operations required for solving the problem. The method is applicable when the elements belong to a Galois field as well as that of a set of integers and is most effective for high-density knapsacks.     

量子进化膜算法及其背包问题应用

量子进化膜算法是基于量子进化算法和膜计算所提出的一种分布式优化算法。将量子进化膜算法应用于0-1背包问题,讨论了基本膜个数的变化对背包问题求解的影响,找到最适合的基本膜个数,并分别与三种不同的量子进化算法进行对比实验,通过多组实例数据进行测试,结果表明该算法具有更高的求解性能。     

Greedy–knapsack algorithm for optimal downlink resource allocation in LTE networks

The long term evolution as a mobile broadband technology supports a wide domain of communication services with different requirements. Therefore, scheduling of all flows from various applications in overload states in which the requested amount of bandwidth exceeds the limited available spectrum resources is a challenging issue. Accordingly, in this paper, a greedy algorithm is presented to evaluate user candidates which are waiting for scheduling and select an optimal set of the users to maximize system performance, without exceeding available bandwidth capacity. The greedy–knapsack algorithm is defined as an optimal solution to the resource allocation problem, formulated based on the fractional knapsack problem. A compromise between throughput and QoS provisioning is obtained by proposing a class-based ranking function, which is a combination of throughput and QoS related parameters defined for each application. The simulation results show that the proposed method provides high performance in terms of throughput, loss and delay for different classes of QoS over the existing ones, especially under overload traffic.     

基于模拟退火思想改进的粒子群算法求解背包问题

针对典型的背包问题,给出了一种基于粒子群算法的求解方法。考虑到粒子群算法在解决问题时容易陷入局部最优的缺点,将模拟退火（SA）思想引入到了粒子群算法中,得到了粒子群——模拟退火算法。该算法保持了粒子群算法原有的简单易实现特点,同时改善了粒子群算法易陷入局部最优的缺点。实验结果表明,该算法具有较好的求解质量。     

一类0-1背包问题的启发式网络策略模型与算法

针对遗传算法(GA)易陷入局部最优解、搜索精度低等缺点,提出了网络启发式策略的遗传算法(NSHGA),并将其成功地应用于0-1背包问题的求解。该算法采用网络节点关联策略,使算法具有良好的全局寻优能力。同时引入网络节点矩阵优化,利用其精细的局部遍历搜索性能,使算法具有较高地搜索精度。实例仿真结果表明,NSHGA算法可有效避免基本GA算法的早熟收敛,且具有寻优能力强、搜索精度高等特点。此外,与基本遗传算法仿真相比,可明显提高0-1背包问题求解的精度。