A new ant colony optimization algorithm for the multidimensional Knapsack problem

The paper proposes a new ant colony optimization (ACO) approach, called binary ant system (BAS), to multidimensional Knapsack problem (MKP). Different from other ACO-based algorithms applied to MKP, BAS uses a pheromone laying method specially designed for the binary solution structure, and allows the generation of infeasible solutions in the solution construction procedure. A problem specific repair operator is incorporated to repair the infeasible solutions generated in every iteration. Pheromone update rule is designed in such a way that pheromone on the paths can be directly regarded as selecting probability. To avoid premature convergence, the pheromone re-initialization and different pheromone intensification strategy depending on the convergence status of the algorithm are incorporated. Experimental results show the advantages of BAS over other ACO-based approaches for the benchmark problems selected from OR library.     

基于蚁群算法的多维0-1背包问题的研究

系统地阐述了蚁群算法,并对它进行改进、优化。将蚁群算法应用于求解多维0-1背包问题,提出一种求解多维0-1背包问题的算法——多维0-1背包问题蚁群算法。它大大减少了蚁群算法的搜索时间,有效改善了蚁群算法易于过早地收敛于非最优解的缺陷。仿真实验取得了较好的结果。     

Ant colony optimization for the traveling purchaser problem

The traveling purchaser problem (TPP) is a generalization of the traveling salesman problem where markets have to be visited to collect a set of commodities. Each market sells a number of commodities at a known price. The TPP consists in selecting a subset of markets purchasing every product, while minimizing the routing costs and the purchase costs. In this work, we address the solution of the TPP with an ant colony optimization procedure. We combine it with a local-search scheme exploring a new neighborhood structure. This procedure is evaluated on a set of benchmark instances from the literature and permits to improve most of the best-known solutions.     

一种新的求解0-1背包问题的混合算法

该文汲取了蚁群算法（ACA）和抗体免疫克隆算法（AICA）的优点,提出了一种求解0-1背包问题的混合型算法,该算法充分利用了前者的搜索能力和后者的种群多样性。仿真实验对算法的部分参数进行了分析,并与其他文献的算法进行比较,结果表明,该算法是一种具有较高性能的混合优化算法。     

求解0-1背包问题的量子蚁群算法

0-1背包问题是组合优化中经典的NP难题,在蚁群算法的基础上结合量子计算提出一种求解0-1背包问题的量子蚁群算法。算法采用量子比特表示信息素,用量子旋转门来更新信息素。大量数据实例的比较测试表明,算法可有效提高蚂蚁算法的性能,减少搜索时间,具有更好的全局寻优能力。     

多巷道固定货架拣选作业优化问题的研究

拣选作业的效率直接影响自动化立体仓库系统的整体效益.为满足客户货单动态变化的需求,分析了自动化仓库单存/取机对多巷道固定货架拣选操作的工作特点,构建了含装箱约束条件的多目标货物拣选路径问题的数学模型,并提出一种带选择算子、插入点操作和动态自适应调整算法参数的改进蚁群算法.实验表明,该算法具有较好的全局寻优能力,收敛速度快,是解决货物拣选路径优化问题的有效算法.     

时间依赖型车辆路径问题的一种改进蚁群算法

时间依赖型车辆路径规划问题(TDVRP),是研究路段行程时间随出发时刻变化的路网环境下的车辆路径优化.传统车辆路径问题(VRP)已被证明是NP-hard问题,因此,考虑交通状况时变特征的TDVRP问题求解更为困难.本文设计了一种TDVRP问题的改进蚁群算法,采用基于最小成本的最邻近法(NNC算法)生成蚁群算法的初始可行解,通过局部搜索操作提高可行解的质量,采用最大--最小蚂蚁系统信息素更新策略.测试结果表明,与最邻近算法和遗传算法相比,改进蚁群算法具有更高的效率,能够得到更优的结果;对于大规模TDVRP问题,改进蚁群算法也表现出良好的性能,即使客户节点数量达到1000,算法的优化时间依然在可接受的范围内.     

离散杂草优化算法在0/1背包问题中的应用

为解决粒子群优化算法在求解0/1背包问题中的早熟收敛问题,将杂草优化算法应用到离散问题,提出了一种离散杂草优化算法(DIWO)。根据组合优化问题的特点,对原算法中正态分布于父代周围的子代进行离散化分析,引入遗传操作中的一种改进的变异机制,保证了新算法的有效性,使其具有局部的随机搜索能力。通过三个仿真实例验证,对比粒子群算法,新算法在种群数量较小、迭代次数较少的情况下能取得更好的结果。     

一种求解TSP问题的ACO&SS算法设计

提出一种求解旅行商(TSP)问题的新型分散搜索算法.将蚁群算法(ACO)的构解方法引入分散搜索(SS)算法,在搜索过程中既考虑解的质量,又考虑解的分散性.采用一种将蚁群算法的信息素更新技术与分散搜索的组合机制相结合的新型子集组合成新解的构解机制,同时采用动态更新参考集与临界准则策略来加快收敛速度.实验结果表明,该算法优于其他现有的方法,获得了较好的结果.     

蚁群算法求解连续空间优化问题

借鉴蚁群算法的进化思想，提出一种求解连续空问优化问题的蚁群算法。该算法主要包括全局搜索、局部搜索和信息素强度更新规则。在全舄搜索过程中，利用信息素强度和启发式函数确定蚂蚁移动方向。在局部搜索过程中，嵌入了确定性搜索，以改善寻优性能，加快收敛速率。通过一个实例问题的求解表明了该算法的有效性。     

Savings based ant colony optimization for the capacitated minimum spanning tree problem

The problem of connecting a set of client nodes with known demands to a root node through a minimum cost tree network, subject to capacity constraints on all links is known as the capacitated minimum spanning tree (CMST) problem. As the problem is NP-hard, we propose a hybrid ant colony optimization (ACO) algorithm to tackle it heuristically. The algorithm exploits two important problem characteristics: (i) the CMST problem is closely related to the capacitated vehicle routing problem (CVRP), and (ii) given a clustering of client nodes that satisfies capacity constraints, the solution is to find a MST for each cluster, which can be done exactly in polynomial time. Our ACO exploits these two characteristics of the CMST by a solution construction originally developed for the CVRP. Given the CVRP solution, we then apply an implementation of Prim's algorithm to each cluster to obtain a feasible CMST solution. Results from a comprehensive computational study indicate the efficiency and effectiveness of the proposed approach.     

0-1背包问题的萤火虫群优化算法

根据群集智能优化原理,给出了一种基于萤火虫寻优思想的新算法———萤火虫群优化算法,并针对0-1背包问题进行求解。经仿真实验并与蜂群算法、蚁群算法和微粒群算法进行了比较,获得了满意的结果,这说明了算法在0-1背包问题求解上的有效性和具有更快的收敛速度,拓展了萤火虫群优化算法的应用领域。     

求解多处理机调度问题的蚁群算法

蚁群算法是受自然界中的蚂蚁觅食行为启发而设计的智能优化算法,特别适合处理离散型的组合优化问题。提出一种求解多处理机调度的蚁群算法,利用一个蚂蚁代表一个处理机来选择任务,并通过分析关键路径及每个任务的最早、最迟开始时间来确定每个任务的紧迫程度,让蚂蚁以此来选择任务。实验证明,该算法可比传统算法取得有更好运行效率的调度策略。     

蚁群算法在考试安排中的应用

蚁群算法是一种新的进化算法，目前的研究表明该算法具有许多优良的性质，它为组合优化等问题提供了新的思路。利用蚁群算法对考试课程安排这一实际问题进行求解。综合了图论中的着色和运筹学中的背包问题。通过实例的解决和分析，说明了该算法的优越性。     

求解旅行商问题的混合粒子群优化算法

结合遗传算法、蚁群算法和模拟退火算法的思想，提出用混合粒子群算法来求解著名的旅行商问题．与模拟退火算法、标准遗传算法进行比较，24种混合粒子群算法的效果都比较好，其中交叉策略D和变异策略F的混合粒子群算法的效果最好，而且简单有效．对于目前仍没有较好解法的组合优化问题，通过此算法修改很容易解决．     

基于和声搜索算法求解组合优化问题

为了能够应用和声搜索算法（HSA）求解组合优化问题,基于HAS的三种操作的离散化实现提出了一种二进制和声搜索算法(BHSA),并将BHSA用于求解著名的k-可满足性(k-SAT)问题和0-1背包问题,通过与粒子群优化（BPSO）和遗传算法（GA）的实例计算对比验证了新算法的可行性与有效性。     

An efficient algorithm for the collapsing knapsack problem

The collapsing knapsack problem (CKP) is a type of nonlinear knapsack problem in which the knapsack size is a non-increasing function of the number of items included. This paper proposes an exact algorithm for CKP by partitioning CKP to some subproblems, then solving them with the improved expanding-core technique. The proposed algorithm solves the subproblems in the special processing order resulting in the reduction of computing time. Experimental results show that the proposed algorithm is an efficient approach for various random instances of size up to 1000.     

一种求解Job-Shop调度问题的新型蚁群算法

Job-Shop调度问题是一类具有很高理论研究和工程应用价值的问题。针对使用蚁群算法求解Job-Shop调度问题时较难设置合适参数的问题,提出一种动态设置参数的新型蚁群求解算法。分析了蚁群算法中参数对求解结果的影响,给出了算法求解Job-Shop调度问题的关键技术和实现过程。最后对五个基本测试问题进行了仿真实验,并与遗传算法、模拟退火算法、基本蚁群算法进行了比较。结果表明,该算法能得到较优的结果,具有一定的应用价值。     

Nodal ant colony optimization for solving profit based unit commitment problem for GENCOs

This paper proposes a nodal ant colony optimization (NACO) technique to solve profit based unit commitment problem (PBUCP). Generation companies (GENCOs) in a competitive restructured power market, schedule their generators with an objective to maximize their own profit without any regard for system social benefit. Power and reserve prices become important factors in decision process. Ant colony optimization that mimics the behavior of ants foraging activities is suitably implemented to search the UCP search space. Here a search space consisting of optimal combination of binary nodes for unit ON/OFF status is represented for the movement of the ants to maintain good exploration and exploitation search capabilities. The proposed model help GENCOs to make decisions on the quantity of power and reserve that must be put up for sale in the markets and also to schedule generators in order to receive the maximum profit. The effectiveness of the proposed technique for PBUCP is validated on 10 and 36 generating unit systems available in the literature. NACO yields an increase of profit, greater than 1.5%, in comparison with the basic ACO, Muller method and hybrid LR-GA.     

一种基于模式替代的遗传算法解0/1背包问题*

背包问题是一个典型的 NP完全问题。提出一种基于模式替代的遗传算法解0/1背包问题思想,通过收集每代种群中最好的几个个体生成模式来引导种群的搜索方向,以提高遗传算法的搜索速度和寻找最优解的能力。通过仿真数值实验,将该方法与简单遗传算法、贪心算法计算结果比较分析,充分证明了使用基于模式替代遗传算法来求解背包问题的有效性和实用性。