一种求解路径优化问题的新型人工鱼群算法

针对人工鱼群算法由于固定视野导致寻优效率低、易陷入局部极值的弊端,引入视野递减反馈策略,提出一种改进人工鱼群算法.视野随着迭代次数和寻优反馈信息适时变化,旨在平衡算法的全局搜索和局部搜索能力.实验测试表明算法在保证收敛速度的基础上提高了计算精度,并且增加了算法陷入局部极值时快速跳出的可能性,最后将改进算法应用于求解国家AAAAA级风景区最短遍历路径问题.     

模糊人工蜂群算法的多选择多维背包问题求解

针对传统人工蜂群算法早熟收敛问题,基于模糊化处理和蜂群寻优的特点,提出一种模糊人工蜂群算法。将模糊输入输出机制引入到算法中来保持蜜源访问概率的动态更新。根据算法计算过程中的不同阶段对蜜源访问概率有效调整,避免算法陷入局部极值。通过对多选择多维背包问题的仿真实验和与其他算法的比较,表明本算法可行有效,有良好的鲁棒性。     

求解多维背包问题的改进二进制粒子群算法

针对二进制粒子群算法在求解大规模多维背包问题时存在迭代次数过多、精度不高的不足,提出一种改进的二进制粒子群算法,新算法利用种群个体极值的平均信息和粒子的个体极值决定粒子当前取值的概率,使粒子可以充分利用整个种群的信息,避免算法陷入局部极值,并利用贪婪算法对进化过程中的不可行解进行修复,对背包资源利用不足的可行解进行修正.通过对典型多维背包问题的仿真实验和与其它算法的比较,表明算法有良好的全局优化能力和较好的收敛速度.     

0-1背包问题的蜂群优化算法

在项目决策与规划、资源分配、货物装载、预算控制等工作中,提出了0-1背包问题.0-1背包问题是组合优化中的典型NP难题,根据群集智能原理,给出一种基于蜂群寻优思想的新算法—蜂群算法,并针对0-1背包问题进行求解.经实验仿真并与蚁群算法计算结果作对比,验证了算法在0-1背包问题求解上的有效性和更快的收敛速度.     

基于AFSA-RS的废旧航材可回收性判定研究

针对当前废旧航材回收处理工作存在的难题,在分析影响废旧航材回收因素的基础上,利用人工鱼群算法对粗糙集理论进行改进,将离散化过程转化为目标寻优问题,通过寻优对离散区间进行有效合并,从而得到较少的离散区间,以解决离散化过程中由于区间分割不当造成的病态问题,最终得到一种科学准确判定废旧航材是否值得回收的方法,提高了航材回收工作的科学性,减少了军费资金投入.     

基于自适应均匀变异人工鱼群投资组合优化算法的研究

投资市场具有一定的风险,影响因素包括经济、政治、市场自身规律等,根据市场机制构建合适的投资组合模型,可以有效降低市场风险,提高投资回报率.人工鱼群算法是模仿自然界鱼类的一种人工智能优化算法,具有较好的优化能力,但有时会陷入局部最优解.首先将人工鱼群算法与均匀变异相结合,加入均匀变异随机数,使算法能够跳出局部最优解,得到全局最优,从而提高算法精度.然后采用改进人工鱼群算法对投资组合模型进行优化求解.实验表明,改进人工鱼群算法具有较好的收敛精度和收敛速度,对投资组合模型的求解效果更好,风险下降,收益增加、     

基于IAFSA-MUSIC算法的阵列信号DOA估计

针对传统MUSIC算法运算量过大以及低信噪比下分辨率差的问题,提出将改进人工鱼群算法与MUSIC的谱峰搜索相结合,利用鱼群觅食和追逐来对解空间进行高效搜索,从而保证算法收敛的快速性和全局性.聚群的存在促使少量陷于局部最优解的人工鱼向着全局最优解的方向靠拢,提高了鱼群对不利环境的自适应性,也增强了算法的稳定性.与此同时,改进人工鱼群算法在一定程度上加快了后期收敛速度,提高了算法的估计性能.实验结果表明在低信噪比时方法相较于MUSIC而言具有更好的估计性能,并且大大减少了运算量,保证了算法的实时性.     

基于人工鱼群和分形学习的雾霾天气预报方法

针对目前较严重的雾霾污染,雾霾天气预报显得十分重要,通过将改进人工鱼群算法和分形学习相结合,提出了基于人工鱼群和分形学习的雾藕天气预报方法.首先对人工鱼群算法离散化改进,结合分形学习理论降维雾霾数据;其次运用支持向量机和5-折交叉验证技术分类分布可能不平坦的数据集;最后建立雾霾天气预报模型.实验结果表明,数据降维后更有利于提高分类器性能,与传统预报方法相比,预报性能更优,具有较高的稳定性和可信性.     

基于全局人工鱼群算法的变压器投切控制策略分析

钢铁企业中变压器的投切往往都是根据工作人员的经验而操作进行的,忽略了投切时机对于变压器损耗的影响.考虑到钢铁企业在电力负荷中占有很大的比重,所以投切不恰当而产生的费用是不可忽视的.针对上述问题,提出一种基于全局人工鱼群算法的变压器投切控制方法,根据钢铁企业变压器实际参数,计算出变电站不同运行情况下的临界负载量,通过结合实际负荷情况确定变压器投切点;全局人工鱼群算法具有较快的收敛速度,可以用于解决有实时性要求的问题.以最终节电效益用作为目标函数,基于全局人工鱼群算法得到最优投切方案.最后以某钢铁企业变压器投切为例,验证了所提方法的有效性.     

考虑车载容量的多区型仓库拣货路径优化研究

拣货作业是仓库核心作业之一,占据仓库运营大量的时间成本和资金成本.针对多区型仓库拣货路径优化问题,对多区型仓库布局、货位坐标、路径等问题进行了定义,构建了多区型仓库拣货路径优化建模,接着通过大量实验确定了人工鱼群算法在求解拣货路径问题时的最优算法参数组合,通过演示性实验验证了模型与算法的有效性,最后从波次订单对实验结果的影响、车载容量对实验结果的影响和算法对比分析3个方面验证了人工鱼群算法的实用性和优越性.结果表明,所建立的多区型仓库拣货路径优化的模型及其求解方法,能够有效提高仓储拣货作业效率.     

An Algorithm for the 0-1 Equality Knapsack Problem

The 0-1 knapsack problem is a linear integer-programming problem with a single constraint and binary variables. The knapsack problem with an inequality constraint has been widely studied, and several efficient algorithms have been published. We consider the equality-constraint knapsack problem, which has received relatively little attention. We describe a branch-and-bound algorithm for this problem, and present computational experience with up to 10,000 variables. An important feature of this algorithm is a least-lower-bound discipline for candidate problem selection.     

求解0-1背包问题的细菌觅食算法

0-1背包问题是组合优化中的一个典型NP难题,介于其具有广泛的实际应用,有效的解决该问题具有非常重要的意义.给出了一种新的群智能算法—细菌觅食算法,对0-1背包问题进行求解.经模拟仿真验证了该算法的有效性,并将其结果与其他方法进行对比分析.     

Extending Dantzig's bound to the bounded multiple-class binary Knapsack problem

 The bounded multiple-class binary knapsack problem is a variant of the knapsack problem where the items are partitioned into classes and the item weights in each class are a multiple of a class weight. Thus, each item has an associated multiplicity. The constraints consists of an upper bound on the total item weight that can be selected and upper bounds on the total multiplicity of items that can be selected in each class. The objective is to maximize the sum of the profits associated with the selected items. This problem arises as a sub-problem in a column generation approach to the cutting stock problem. A special case of this model, where item profits are restricted to be multiples of a class profit, corresponds to the problem obtained by transforming an integer knapsack problem into a 0-1 form. However, the transformation proposed here does not involve a duplication of solutions as the standard transformation typically does. The paper shows that the LP-relaxation of this model can be solved by a greedy algorithm in linear time, a result that extends those of Dantzig (1957) and Balas and Zemel (1980) for the 0-1 knapsack problem. Hence, one can derive exact algorithms for the multi-class binary knapsack problem by adapting existing algorithms for the 0-1 knapsack problem. Computational results are reported that compare solving a bounded integer knapsack problem by transforming it into a standard binary knapsack problem versus using the multiple-class model as a 0-1 form. Received: May 1998 / Accepted: February 2002-09-04 Published online: December 9, 2002 Key Words. Knapsack problem – integer programming – linear programming relaxation     

Pareto memetic algorithm for multiple objective optimization with an industrial application

Multiple objective combinatorial optimization problems are difficult to solve and often, exact algorithms are unable to produce optimal solutions. The development of multiple objective heuristics was inspired by the need to quickly produce acceptable solutions. In this paper, we present a new multiple objective Pareto memetic algorithm called PMS^MO. The PMS^MO algorithm incorporates an enhanced fine-grained fitness assignment, a double level archiving process and a local search procedure to improve performance. The performance of PMS^MO is benchmarked against state-of-the-art algorithms using 0–1 multi-dimensional multiple objective knapsack problem from the literature and an industrial scheduling problem from the aluminum industry.     

Lagrangean heuristics combined with reoptimization for the 0-1 bidimensional knapsack problem

First, this paper deals with lagrangean heuristics for the 0-1 bidimensional knapsack problem. A projected subgradient algorithm is performed for solving a lagrangean dual of the problem, to improve the convergence of the classical subgradient algorithm. Secondly, a local search is introduced to improve the lower bound on the value of the biknapsack produced by lagrangean heuristics. Thirdly, a variable fixing phase is embedded in the process. Finally, the sequence of 0-1 one-dimensional knapsack instances obtained from the algorithm are solved by using reoptimization techniques in order to reduce the total computational time effort. Computational results are presented.     

An iterative variable-based fixation heuristic for the 0-1 multidimensional knapsack problem

An iterative scheme which is based on a dynamic fixation of the variables is developed to solve the 0-1 multidimensional knapsack problem. Such a scheme has the advantage of generating memory information, which is used on the one hand to choose the variables to fix either permanently or temporarily and on the other hand to construct feasible solutions of the problem. Adaptations of this mechanism are proposed to explore different parts of the search space and to enhance the behaviour of the algorithm. Encouraging results are presented when tested on the correlated instances of the 0-1 multidimensional knapsack problem.     

Solving the bi-objective multi-dimensional knapsack problem exploiting the concept of core

This paper deals with the bi-objective multi-dimensional knapsack problem. We propose the adaptation of the core concept that is effectively used in single-objective multi-dimensional knapsack problems. The main idea of the core concept is based on the “divide and conquer” principle. Namely, instead of solving one problem with n variables we solve several sub-problems with a fraction of n variables (core variables). The quality of the obtained solution can be adjusted according to the size of the core and there is always a trade off between the solution time and the quality of solution. In the specific study we define the core problem for the multi-objective multi-dimensional knapsack problem. After defining the core we solve the bi-objective integer programming that comprises only the core variables using the Multicriteria Branch and Bound algorithm that can generate the complete Pareto set in small and medium size multi-objective integer programming problems. A small example is used to illustrate the method while computational and economy issues are also discussed. Computational experiments are also presented using available or appropriately modified benchmarks in order to examine the quality of Pareto set approximation with respect to the solution time. Extensions to the general multi-objective case as well as to the computation of the exact solution are also mentioned.     

A generalized knapsack problem with variable coefficients

The ordinary knapsack problem is to find the optimal combination of items to be packed in a knapsack under a single constraint on the total allowable resources, where all coefficients in the objective function and in the constraint are constant.In this paper, a generalized knapsack problem with coefficients depending on variable parameters is proposed and discussed. Developing an effective branch and bound algorithm for this problem, the concept of relaxation and the efficiency function introduced here will play important roles. Furthermore, a relation between the algorithm and the dynamic programming approach is discussed, and subsequently it will be shown that the ordinary 0–1 knapsack problem, the linear programming knapsack problem and the single constrained linear programming problem with upper-bounded variables are special cases of the interested problem. Finally, practical applications of the problem and its computational experiences will be shown.     

Consecutive Ones Matrices for Multi-dimensional Orthogonal Packing Problems

The multi-dimensional orthogonal packing problem (OPP) is a well studied decisional problem. Given a set of items with rectangular shapes, the problem is to decide whether there is a non-overlapping packing of these items in a rectangular bin. The rotation of items is not allowed. A powerful caracterization of packing configurations by means of interval graphs was recently introduced. In this paper, we propose a new algorithm using consecutive ones matrices as data structure. This new algorithm is then used to solve the two-dimensional orthogonal knapsack problem. Computational results are reported, which show its effectiveness.