A survey on the Metaheuristics for Cryptanalysis of Substitution and Transposition Ciphers

This paper presents state-of-art cryptanalysis studies on attacks of the substitution and transposition ciphers using various metaheuristic algorithms. Traditional cryptanalysis methods employ an exhaustive search, which is computationally expensive. Therefore, metaheuristics have attracted the interest of researchers in the cryptanalysis field. Metaheuristic algorithms are known for improving the search for the optimum solution and include Genetic Algorithm, Simulated Annealing, Tabu Search, Particle Swarm Optimization, Differential Evolution, Ant Colony, the Artificial Bee Colony, Cuckoo Search, and Firefly algorithms. The most important part of these various applications is deciding the fitness function to guide the search. This review presents how these algorithms have been implemented for cryptanalysis purposes. The paper highlights the results and findings of the studies and determines the gaps in the literature.     

A survey on metaheuristics for stochastic combinatorial optimization

Metaheuristics are general algorithmic frameworks, often nature-inspired, designed to solve complex optimization problems, and they are a growing research area since a few decades. In recent years, metaheuristics are emerging as successful alternatives to more classical approaches also for solving optimization problems that include in their mathematical formulation uncertain, stochastic, and dynamic information. In this paper metaheuristics such as Ant Colony Optimization, Evolutionary Computation, Simulated Annealing, Tabu Search and others are introduced, and their applications to the class of Stochastic Combinatorial Optimization Problems (SCOPs) is thoroughly reviewed. Issues common to all metaheuristics, open problems, and possible directions of research are proposed and discussed. In this survey, the reader familiar to metaheuristics finds also pointers to classical algorithmic approaches to optimization under uncertainty, and useful informations to start working on this problem domain, while the reader new to metaheuristics should find a good tutorial in those metaheuristics that are currently being applied to optimization under uncertainty, and motivations for interest in this field.

A Memetic Chaotic Gravitational Search Algorithm for unconstrained global optimization problems

Metaheuristic optimization algorithms address two main tasks in the process of problem solving: i) exploration (also called diversification) and ii) exploitation (also called intensification). Guaranteeing a trade-off between these operations is critical to good performance. However, although many methods have been proposed by which metaheuristics can achieve a balance between the exploration and exploitation stages, they are still worse than exact algorithms at exploitation tasks, where gradient-based mechanisms outperform metaheuristics when a local minimum is approximated. In this paper, a quasi-Newton method is introduced into a Chaotic Gravitational Search Algorithm as an exploitation method, with the purpose of improving the exploitation capabilities of this recent and promising population-based metaheuristic. The proposed approach, referred to as a Memetic Chaotic Gravitational Search Algorithm, is used to solve forty-five benchmark problems, both synthetic and real-world, to validate the method. The numerical results show that the adding of quasi-Newton search directions to the original (Chaotic) Gravitational Search Algorithm substantially improves its performance. Also, a comparison with the state-of-the-art algorithms: Particle Swarm Optimization, Genetic Algorithm, Rcr-JADE, COBIDE and RLMPSO, shows that the proposed approach is promising for certain real-world problems.     

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

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

Native metaheuristics for non-permutation flowshop scheduling

The most general flowshop scheduling problem is also addressed in the literature as non-permutation flowshop (NPFS). Current processors are able to cope with the \((n!)^{m}\) combinatorial complexity of NPFS scheduling by metaheuristics. After briefly discussing the requirements for a manufacturing layout to be designed and modeled as non-permutation flowshop, a disjunctive graph (digraph) approach is used to build native solutions. The implementation of an Ant Colony Optimization (ACO) algorithm has been described in detail; it has been shown how the biologically inspired mechanisms produce eligible schedules, as opposed to most metaheuristics approaches, which improve permutation solutions. ACO algorithms are an example of native non-permutation (NNP) solutions of the flowshop scheduling problem, opening a new perspective on building purely native approaches. The proposed NNP-ACO has been assessed over existing native approaches improving most makespan upper bounds of the benchmark problems from Demirkol et al. (1998).     

A Hybrid Multi-Swarm Particle Swarm Optimization algorithm for the Probabilistic Traveling Salesman Problem

The Probabilistic Traveling Salesman Problem (PTSP) is a variation of the classic Traveling Salesman Problem (TSP) and one of the most significant stochastic routing problems. In the PTSP, only a subset of potential customers need to be visited on any given instance of the problem. The number of customers to be visited each time is a random variable. In this paper, a new hybrid algorithmic nature inspired approach based on Particle Swarm Optimization (PSO), Greedy Randomized Adaptive Search Procedure (GRASP) and Expanding Neighborhood Search (ENS) Strategy is proposed for the solution of the PTSP. The proposed algorithm is tested on numerous benchmark problems from TSPLIB with very satisfactory results. Comparisons with the classic GRASP algorithm, the classic PSO and with a Tabu Search algorithm are also presented. Also, a comparison is performed with the results of a number of implementations of the Ant Colony Optimization algorithm from the literature and in 13 out of 20 cases the proposed algorithm gives a new best solution.     

VERY STRONGLY CONSTRAINED PROBLEMS: AN ANT COLONY OPTIMIZATION APPROACH

Ant Colony Optimization (ACO) is a class of metaheuristic algorithms sharing the common approach of constructing a solution on the basis of information provided both by a standard constructive heuristic and by previously constructed solutions. This article is composed of three parts. The first one frames ACO in current trends of research on metaheuristics for combinatorial optimization. The second outlines some current research within the ACO community, reporting recent results obtained on different problems, while the third part focuses on a particular research line, named ANTS, providing some details on the algorithm and presenting results recently obtained on a prototypical strongly constrained problem: the set partitioning problem.     

仓储系统拣货路径规划问题的研究

本文针对仓储系统的拣货路径规划问题展开研究。以拣货路径长度和拣货时间为评价指标,分别采用蚁群算法、遗传算法、禁忌搜索算法、模拟退火算法进行对比研究。把仓库内拣货路径规划问题转化为转换为N=M+1的TSP问题。经MATLAB仿真研究,获得最短路径和适应度进化曲线。经实验测试发现了当拣货数量较多即N值偏大时,蚁群算法得到的路径距离相对于遗传算法、模拟退火算法和禁忌搜索算法更加优化,同时蚁群算法得到最优解的迭代次数更少,拣货时间更短。     

A two-stage Ant Colony optimization algorithm to minimize the makespan on unrelated parallel machines—part II: enhancements and experimentations

In a previous paper (Arnaout et al in J Intell Manuf 21:693–701, 2010), an Ant Colony optimization (ACO I) algorithm was introduced for minimizing the schedule’s makespan on unrelated parallel machines with sequence-dependent setup times. Optimal solutions for small instances of this problem were obtained by solving a mixed integer program. However, for larger instances (up to 10 machines and 120 jobs), heuristic and approximate algorithms were necessary to reach solutions in reasonable computational times. ACO I’s performance was evaluated by comparing its solutions to solutions obtained using Tabu Search and MetaRaPS (metaheuristic for Randomized Priority Search). While the results indicated that ACO I outperformed the other heuristics, it also showed that MetaRaPS had a better performance when all ratios of N/M (jobs to machines ratio) were considered. In this paper, we introduce an enhanced ACO which will be referred to as ACO II and compare its performance to other existing and new algorithms including ACO I, MetaRaPS, and SA. The extensive and expanded experiments conducted prove the superiority of the enhanced ACO II.     

A novel coordinated path planning method using k-degree smoothing for multi-UAVs

Coordinated path planning for multiple unmanned aerial vehicles (multi-UAVs) is a highly significant problem encountered in their coordinated control. In the interests of completing mission securely and efficiently, the advanced multi-UAVs control technology requires a universal smoothing method as well as a precise coordination strategy. In this paper, we propose a novel multi-UAVs coordinated path planning method based on the k-degree smoothing, a more complex environment consists of multiple threat sources of which is constructed. By employing the Improved Ant Colony Optimization algorithm, a k-degree smoothing method is also presented aiming at obtaining a more flyable path. Additionally, the multi-UAVs coordination algorithm is induced by k-degree smoothing, allowing the UAVs to arrive at the destination simultaneously or in an acceptable time interval. Finally, simulations of the comparison between the Improved Ant Colony Optimization and classic algorithm, the detailed smoothing method, and the coordination are respectively conducted to validate that the proposed approach is feasible and effective in multi-UAVs coordinated path planning problems.     

Fast Ant Colony Optimization on Runtime Reconfigurable Processor Arrays

Ant Colony Optimization (ACO) is a metaheuristic used to solve combinatorial optimization problems. As with other metaheuristics, like evolutionary methods, ACO algorithms often show good optimization behavior but are slow when compared to classical heuristics. Hence, there is a need to find fast implementations for ACO algorithms. In order to allow a fast parallel implementation, we propose several changes to a standard form of ACO algorithms. The main new features are the non-generational approach and the use of a threshold based decision function for the ants. We show that the new algorithm has a good optimization behavior and also allows a fast implementation on reconfigurable processor arrays. This is the first implementation of the ACO approach on a reconfigurable architecture. The running time of the algorithm is quasi-linear in the problem size n and the number of ants on a reconfigurable mesh with n ² processors, each provided with only a constant number of memory words.     

Analyzing the impact of MOACO components: An algorithmic study on the multi-objective shortest path problem

Multi-objective Ant Colony Optimization (MOACO) algorithms have been successfully applied to several multi-objective combinatorial optimization problems (MCOP) over the past decade. Recently, we proposed a MOACO algorithm named GRACE for the multi-objective shortest path (MSP) problem, confirming the efficiency of such metaheuristic for this MCOP. In this paper, we investigate several extensions of GRACE, proposing several single and multi-colony variants of the original algorithm. All variants are compared on the original set of instances used for proposing GRACE. The best-performing variants are also assessed using a new benchmark containing 300 larger instances with three different underlying graph structures. Experimental evaluation shows one of the variants to produce better results than the others, including the original GRACE, thus improving the state-of-the-art of MSP.     

Applying Ant Colony Optimization to configuring stacking ensembles for data mining

An ensemble is a collective decision-making system which applies a strategy to combine the predictions of learned classifiers to generate its prediction of new instances. Early research has proved that ensemble classifiers in most cases can be more accurate than any single component classifier both empirically and theoretically. Though many ensemble approaches are proposed, it is still not an easy task to find a suitable ensemble configuration for a specific dataset. In some early works, the ensemble is selected manually according to the experience of the specialists. Metaheuristic methods can be alternative solutions to find configurations. Ant Colony Optimization (ACO) is one popular approach among metaheuristics. In this work, we propose a new ensemble construction method which applies ACO to the stacking ensemble construction process to generate domain-specific configurations. A number of experiments are performed to compare the proposed approach with some well-known ensemble methods on 18 benchmark data mining datasets. The approach is also applied to learning ensembles for a real-world cost-sensitive data mining problem. The experiment results show that the new approach can generate better stacking ensembles.     

A local landscape mapping method for protein structure prediction in the HP model

The hydrophobic-polar (HP) model has been widely studied in the field of protein structure prediction both for theoretical purposes and as a benchmark for new optimization strategies. In this work we present results of the recently proposed Hybrid Monte Carlo Ant Colony Optimization heuristic in the HP model using a fragment assembly-like strategy. Moreover we extend that method introducing a general framework for optimization in the HP model, called Local Landscape Mapping, and we test it using the pull moves set to generate solutions. We describe the heuristic and compare results obtained on well known HP instances in the 3-dimensional cubic lattice to those obtained with standard Ant Colony optimization and Simulated Annealing. Fragment assembly-like tests were performed using a modified objective function to prevent the creation of overlapping walks. Results show that our method performs better than the other heuristics in all benchmark instances when the fragment assembly-like strategy is used while in the case of pull moves-based neighborhood its performance is comparable to that of simulated annealing.     

A new approach for dynamic fuzzy logic parameter tuning in Ant Colony Optimization and its application in fuzzy control of a mobile robot

Ant Colony Optimization is a population-based meta-heuristic that exploits a form of past performance memory that is inspired by the foraging behavior of real ants. The behavior of the Ant Colony Optimization algorithm is highly dependent on the values defined for its parameters. Adaptation and parameter control are recurring themes in the field of bio-inspired optimization algorithms. The present paper explores a new fuzzy approach for diversity control in Ant Colony Optimization. The main idea is to avoid or slow down full convergence through the dynamic variation of a particular parameter. The performance of different variants of the Ant Colony Optimization algorithm is analyzed to choose one as the basis to the proposed approach. A convergence fuzzy logic controller with the objective of maintaining diversity at some level to avoid premature convergence is created. Encouraging results on several traveling salesman problem instances and its application to the design of fuzzy controllers, in particular the optimization of membership functions for a unicycle mobile robot trajectory control are presented with the proposed method.     

Disassembly Sequencing Using Tabu Search

End-of-life disassembly has developed into a major research area within the sustainability paradigm, resulting in the emergence of several algorithms and structures proposing heuristics techniques such as Genetic Algorithm (GA), Ant Colony Optimization (ACO) and Neural Networks (NN). The performance of the proposed methodologies heavily depends on the accuracy and the flexibility of the algorithms to accommodate several factors such as preserving the precedence relationships during disassembly while obtaining near- optimal and optimal solutions. This paper improves a previously proposed Genetic Algorithm model for disassembly sequencing by utilizing a faster metaheuristic algorithm, Tabu search, to obtain the optimal solution. The objectives of the proposed algorithm are to minimize (1) the traveled distance by the robotic arm, (2) the number of disassembly method changes, and (3) the number of robotic arm travels by combining the identical-material components together and hence eliminating unnecessary disassembly operations. In addition to improving the quality of optimum sequence generation, a comprehensive statistical analysis comparing the previous Genetic Algorithm and the proposed Tabu Search Algorithm is also included     

A multi-start tabu search method for a single-machine scheduling problem with periodic maintenance and sequence-dependent set-up times

In this paper we study a problem of sequencing jobs in a machine with programmed preventive maintenance and sequence-dependent set-up times. The problem combines two NP-hard problems, so we propose a heuristic method for solving it, which hybridizes multi-start strategies with Tabu Search. We compare our method with the only published metaheuristic algorithm for this problem on a set of 420 instances. The comparison favors the method developed in this work, showing that is able to find high quality solutions in very short computational times.     

– Ant System

Ant System, the first Ant Colony Optimization algorithm, showed to be a viable method for attacking hard combinatorial optimization problems. Yet, its performance, when compared to more fine-tuned algorithms, was rather poor for large instances of traditional benchmark problems like the Traveling Salesman Problem. To show that Ant Colony Optimization algorithms could be good alternatives to existing algorithms for hard combinatorial optimization problems, recent research in this area has mainly focused on the development of algorithmic variants which achieve better performance than Ant System.In this paper, we present – Ant System ( ), an Ant Colony Optimization algorithm derived from Ant System. differs from Ant System in several important aspects, whose usefulness we demonstrate by means of an experimental study. Additionally, we relate one of the characteristics specific to — that of using a greedier search than Ant System — to results from the search space analysis of the combinatorial optimization problems attacked in this paper. Our computational results on the Traveling Salesman Problem and the Quadratic Assignment Problem show that is currently among the best performing algorithms for these problems.     

A two-stage Ant Colony Optimization algorithm to minimize the makespan on unrelated parallel machines with sequence-dependent setup times

This paper addresses the non-preemptive unrelated parallel machine scheduling problem with machine-dependent and sequence-dependent setup times. All jobs are available at time zero, all times are deterministic, and the objective is to minimize the makespan. An Ant Colony Optimization (ACO) algorithm is introduced in this paper and is applied to this NP-hard problem; in particular, the proposed ACO tackles a special structure of the problem, where the ratio of the number of jobs to the number of machines is large (i.e., for a highly utilized set of machines). Its performance is evaluated by comparing its solutions to solutions obtained using Tabu Search and other existing heuristics for the same problem, namely the Partitioning Heuristic and Meta-RaPS. The results show that ACO outperformed the other algorithms.