共享信息素矩阵:一种新的并行ACO方法

提出并实现了一种新的蚁群优化(ACO)并行化策略SHOP(Sharing one pheromone matrix). 主要思想是基于多蚁群在解的构造过程和信息素更新过程中共享同一个信息素矩阵. 以ACS和MMAS的SHOP并行实现为例, 简要描述了SHOP 设计思想和实现过程, 尝试了ACS和MMAS并行混合. 以对称TSP测试集为对象, 将SHOP的实现与相应串行算法在相同计算环境下的实验结果比较, 以及与现有的并行实现进行比较, 结果表明SHOP并行策略相对于串行ACO及现有的并行策略具有一定的优势.     

初始信息素筛选的蚁群优化算法在HDFS副本选择中的研究

随着社会信息化程度的不断提高,各种形式的数据急剧膨胀.HDFS成为解决海量数据存储问题的一个分布式文件系统,而副本技术是云存储系统的关键.提出了一种基于初始信息素筛选的蚁群优化算法(InitPh_ACO)的副本选择策略,通过将遗传算法(GA)与蚁群优化算法(ACO)算法相结合,将它们进行动态衔接.提出基于初始信息素筛选的ACO算法,既克服了ACO算法初始搜索速度慢,又充分利用GA的快速随机全局搜索能力.利用云计算仿真工具CloudSim来验证此策略的效果,结果表明:InitPh_ACO策略在作业执行时间、副本读取响应时间和副本负载均衡性三个方面的性能均优于基于ACO算法的副本选择策略和基于GA的副本选择策略.     

基于混合优化算法的最大独立集问题求解

蚁群优化算法（ACO）的正反馈机制使其具有强大的局部搜索性能，但其全局优化性的优劣在很大程度上与挥发系数的选择有关，如选择得不合适则易将使算法陷入局部最优，而禁忌搜索算法（TS）则具有强大的全局优化性能。为了弥补单一ACO算法的局限性，将ACO算法与TS算法组合起来，提出了基于TS和ACO算法的混合优化算法HTSACO，并将该混合优化算法用于求解最大独立集问题。实验表明：与标准蚁群优化算法相比，该算法显示出了很高的全局优化性和计算效率。     

基于量子蚁群算法的机器人联盟问题研究

将量子进化算法与蚁群算法思想相融合,提出一种求解机器人联盟问题的量子蚁群算法。为了避免搜索陷入局部最优,采用多种群并行搜索及量子交叉策略,以改善种群信息结构;算法中还设计了一种新的信息素表示方式。仿真实验结果表明,该算法具有较快的收敛速度和全局寻优能力。     

基于蚁群算法的飞机定检人员均衡配置

将蚁群算法(ACO)应用于飞机定检人员均衡配置中.首先,根据均方差指标建立人员均衡配置模型;其次,运用3种精英策略并引入信息素限制和自适应机制对基本蚁群算法进行改进,同时提出一种新变异算子以进一步提高算法的性能;最后,运用改进蚁群算法求解模型.实例仿真表明,改进蚁群算法克服了基本蚁群算法搜索时间长、容易早熟的不足,均衡...     

基于蚁群算法的飞机定检原位工作流程优化

首次将蚁群算法（ACO）应用于飞机定检原位工作流程优化中。在建立原位工作流程优化模型的基础上,借鉴最优一最差蚂蚁系统的思想改进信息素更新机制,并采用改进的精英策略和变异特征对基本蚁群算法进行改进。实例仿真表明,改进蚁群算法在全局搜索能力和收敛速度上较基本蚁群算法有明显提高,克服了基本蚁群算法搜索时间长、容易早熟的不足。优化后原位工作完成时问较优化前缩短2．27％,验证了ACO在解决定检工作流程优化问题上的适用性。     

基于离散数字编码的蚁群连续优化算法

本文提出了一种基于离散编码的蚁群连续优化算法(CACO-DE),用于求解连续优化问题.以往蚁群算法(AC0)的研究,以求解离散优化问题为主,较少涉及连续优化问题.与经典的ACO算法不同,CACO-DE将有限精度的实数转化为一个数字串,数字串的每位取0到9之间的数字,从而实现了用离散编码描述实数的效果.CACO-DE延用了经典ACO算法的框架,并加入了特殊的选择机制、信息素更新方式和局部搜索策略.测试实验结果表明:CA-CO-DE比以往同类算法求解速度更快且精度更高.     

基于模糊粗糙集信息熵的蚁群特征选择方法

目前针对高维数据特征选择提出的启发式算法多数容易陷入局部最优,无法对整个特征空间进行有效搜索。为了提高对特征域的并行搜索能力,基于模糊粗糙集的信息熵原理,对蚁群模型的搜索策略、信息素更新和状态转移规则等进行了改进,提出蚁群特征选择方法。经UCI数据实验验证,该算法比传统的特征选择算法具有更好的选择效果,是有效的。     

求解模糊Job Shop调度的遗传算法与蚁群算法融合研究

提出一种算法融合策略,解决单一算法求解模糊Job Shop调度问题存在的不足,提高这类问题的求解质量.算法融合策略中,采用遗传算法和蚁群算法进行并行搜索;根据模糊Job Shop调度问题解的特征,提出基于关键工序的邻域选择方法,并将基于这种邻域选择方法的禁忌搜索算法作为局部搜索算法,加强了遗传算法和蚁群算法的局部搜索能力.采用算法融合策略的混合优化算法对以13个难的benchmarks问题经模糊化得到实例进行求解,在较短的时间内,得到的平均满意度较并行遗传算法(PGA)提高5.24%、较TSAB算法提高8.40% .采用算法融合策略构造的混合算法具有较强的搜索能力,说明提出的混合搜索策略是有效的.     

基于并行多种群自适应蚁群算法的聚类分析

数据聚类是数据挖掘中的一个重要课题。聚类问题可以归结为一个优化问题。蚁群算法作为一种鲁棒性很强的优化算法具有很强的全局优化能力。该文给出了一种并行多种群自适应蚁群算法。该算法采用多种群并行搜索,并在种群中采用基于目标函数值的启发式信息素分配策略和根据目标函数自动调整蚂蚁搜索路径的行为。理论分析和仿真实验表明,该算法是非常有效的。     

差异容量平行批机器环境下基于弱选择约束的调度算法

研究动态到达的差异工件在容量不同的平行批处理机环境下,最小化制造跨度的调度问题,并提出一种有效的元启发式算法.给出一个下界以评价算法的性能,针对所构建批的第1个工件的选择提出弱约束标准及两个基于弱约束的首工件选择策略,并引入到蚁群优化算法.最后通过仿真实验将所提出的改进蚁群算法与已有算法和使用传统选择策略的蚁群算法进行比较,实验结果表明,在建批过程中使用首工件弱约束策略和弱约束下工件尺寸大高概率选择策略是有效的,所提算法的搜索性能较其他算法具有明显优势.     

Parallel custom instruction identification for extensible processors

With the ability of customization for an application domain, extensible processors have been used more and more in embedded systems in recent years. Extensible processors customize an application domain by executing parts of application code in hardware instead of software. Determining parts of application code as custom instruction generally requires subgraph enumeration and subgraph selection. Both subgraph enumeration problem and subgraph selection problem are computationally difficult problems. Most of previous works focus on sequential algorithms for these two problems. In this paper, we present a parallel implementation of a latest subgraph enumeration algorithm based on a computer cluster. A standard ant colony optimization algorithm (ACO), a modified version of ACO with local optimum search and a parallel ACO algorithm are also proposed to solve the subgraph selection problem in this work. Experimental results show that the parallel algorithms outperform the sequential algorithms in terms of runtime or (and) quality of results. In addition, we have formally proved the upper bound on the number of feasible solutions in subgraph selection problem with or without the overlapping constraint.     

Parallel Ant Colony Optimization on Graphics Processing Units

The purpose of this paper is to propose effective parallelization strategies for the Ant Colony Optimization (ACO) metaheuristic on Graphics Processing Units (GPUs). The Max–Min Ant System (MMAS) algorithm augmented with 3-opt local search is used as a framework for the implementation of the parallel ants and multiple ant colonies general parallelization approaches. The four resulting GPU algorithms are extensively evaluated and compared on both speedup and solution quality on a state-of-the-art Fermi GPU architecture. A rigorous effort is made to keep parallel algorithms true to the original MMAS applied to the Traveling Salesman Problem. We report speedups of up to 23.60 with solution quality similar to the original sequential implementation. With the intent of providing a parallelization framework for ACO on GPUs, a comparative experimental study highlights the performance impact of ACO parameters, GPU technical configuration, memory structures and parallelization granularity.     

Reliability optimization of topology communication network design using an improved ant colony optimization

Network design problem is a well-known NP-hard problem which involves the selection of a subset of possible links or a network topology in order to minimize the network cost subjected to the reliability constraint. To overcome the problem, this paper proposes a new efficiency algorithm based on the conventional ant colony optimization (ACO) to solve the communication network design when considering both economics and reliability. The proposed method is called improved ant colony optimizations (IACO) which introduces two addition techniques in order to improve the search process, i.e. neighborhood search and re-initialization process. To show its efficiency, IACO is applied to test with three different topology network systems and its results are compared with those obtained results from the conventional approaches, i.e. genetic algorithm (GA), tabu search algorithm (TSA) and ACO. Simulation results, obtained these test problems with various constraints, shown that the proposed approach is superior to the conventional algorithms both solution quality and computational time.     

An efficient hybrid algorithm for resource-constrained project scheduling

We propose an efficient hybrid algorithm, known as ACOSS, for solving resource-constrained project scheduling problems (RCPSP) in real-time. The ACOSS algorithm combines a local search strategy, ant colony optimization (ACO), and a scatter search (SS) in an iterative process. In this process, ACO first searches the solution space and generates activity lists to provide the initial population for the SS algorithm. Then, the SS algorithm builds a reference set from the pheromone trails of the ACO, and improves these to obtain better solutions. Thereafter, the ACO uses the improved solutions to update the pheromone set. Finally in this iteration, the ACO searches the solution set using the new pheromone trails after the SS has terminated. In ACOSS, ACO and the SS share the solution space for efficient exchange of the solution set. The ACOSS algorithm is compared with state-of-the-art algorithms using a set of standard problems available in the literature. The experimental results validate the efficiency of the proposed algorithm.     

Parallel-machine scheduling problems with sequence-dependent setup times using an ACO,SA and VNS hybrid algorithm

This paper proposes a hybrid metaheuristic for the minimization of makespan in scheduling problems with parallel machines and sequence-dependent setup times. The solution approach is robust, fast, and simply structured, and comprises three components: an initial population generation method based on an ant colony optimization (ACO), a simulated annealing (SA) for solution evolution, and a variable neighborhood search (VNS) which involves three local search procedures to improve the population. The hybridization of an ACO, SA with VNS, combining the advantages of these three individual components, is the key innovative aspect of the approach. Two algorithms of a hybrid VNS-based algorithm, SA/VNS and ACO/VNS, and the VNS algorithm presented previously are used to compare with the proposed hybrid algorithm to highlight its advantages in terms of generality and quality for large instances.     

基于异构CMP的改进蚁群优化任务调度策略

为提高异构CMP任务调度执行效率,充分发挥异构CMP的异构性和并行能力,提出一种基于异构CMP的改进蚁群优化任务调度算法--IACOTS。IACOTS算法首先建立任务调度模型、路径选择规则和信息素更新规则,使蚁群算法能够适用于异构CMP任务调度问题。同时通过采用动态信息素更新、相遇并行搜索策略和引入遗传算法中的变异因子对基本的蚁群算法进行优化,克服蚁群算法搜索时间过长和“早熟”现象。通过仿真实验获得的结果表明,IACOTS算法执行效率优于现有的遗传算法,完成相同的任务需要的迭代次数最少,能有效降低程序执行时间,适用于异构CMP等大规模并行环境的任务调度。     

Hybrid large neighbourhood search algorithm for capacitated vehicle routing problem

This paper presents a new hybrid algorithm that executes large neighbourhood search algorithm in combination with the solution construction mechanism of the ant colony optimization algorithm (LNS–ACO) for the capacitated vehicle routing problem (CVRP). The proposed hybrid LNS–ACO algorithm aims at enhancing the performance of the large neighbourhood search algorithm by providing a satisfactory level of diversification via the solution construction mechanism of the ant colony optimization algorithm. Therefore, LNS–ACO algorithm combines its solution improvement mechanism with a solution construction mechanism. The performance of the proposed algorithm is tested on a set of CVRP instances. The hybrid LNS–ACO algorithm is compared against two other LNS variants and some of the formerly developed methods in terms of solution quality. Computational results indicate that the proposed hybrid LNS–ACO algorithm has a satisfactory performance in solving CVRP instances.     

Hybridizing ant colony optimization via genetic algorithm for mixed-model assembly line balancing problem with sequence dependent setup times between tasks

This paper presents a new hybrid algorithm, which executes ant colony optimization in combination with genetic algorithm (ACO-GA), for type I mixed-model assembly line balancing problem (MMALBP-I) with some particular features of real world problems such as parallel workstations, zoning constraints and sequence dependent setup times between tasks. The proposed ACO-GA algorithm aims at enhancing the performance of ant colony optimization by incorporating genetic algorithm as a local search strategy for MMALBP-I with setups. In the proposed hybrid algorithm ACO is conducted to provide diversification, while GA is conducted to provide intensification. The proposed algorithm is tested on 20 representatives MMALBP-I extended by adding low, medium and high variability of setup times. The results are compared with pure ACO pure GA and hGA in terms of solution quality and computational times. Computational results indicate that the proposed ACO-GA algorithm has superior performance.