This is an erratum for the article “Introduction to the Special Issue on Large-Scale Optimization and Learning” published in ACM Trans. Evol. Learn. Optim. 5, 4, Article 23 (December 2025), 3 pages.

This paper introduces a hybrid algorithm that integrates the Construct, Merge, Solve and Adapt (CMSA) metaheuristic with Column Generation (CG) to solve the Variable-Sized Bin Packing Problem (VSBPP). The VSBPP, which requires packing items of varying sizes into bins of different types and costs, is a core combinatorial optimization problem with applications in logistics and resource allocation. Our approach builds upon a previously proposed CMSA-based framework by incorporating a column generation procedure to strengthen the linear programming relaxation and generate improved patterns. In each iteration, heuristic solution construction and merging phases produce a pool of feasible packing patterns. These are then used in a linear programming master problem, from which dual values are extracted and used to solve a knapsack pricing subproblem. This identifies new patterns (columns) with negative reduced cost to be added to the model. Finally, an integer programming phase refines the solution using a reduced subinstance. The algorithm is evaluated on benchmark instances and compared with both the previously published standalone CMSA approach and a standalone column generation method. Experimental results show that the combined CMSA-COLGEN approach consistently outperforms both baselines in terms of solution quality and robustness, particularly on larger and more complex instances.

This work presents a new variant of construct, merge, solve, and adapt (CMSA), a hybrid metaheuristic for combinatorial optimization. This variant, denoted as DL-CMSA, implements an online deep learning mechanism, which allows it to learn how to construct solutions in its “construct” step. Compared to an existing variant of CMSA with a learning mechanism, the so-called RL-CMSA, the deep learning component of the presented variant allows for a higher degree of detail in the learning process, as the partial solution under construction is taken into account for deciding which solution component to add next. An experimental evaluation is performed on the classical Maximum Independent Set (MIS) problem. The results show how the proposed deep learning mechanism is beneficial, yielding statistically superior results.

The integration of Large Language Models (LLMs) into optimization has created a powerful synergy, opening exciting research opportunities.This paper investigates how LLMs can enhance existing optimization algorithms.Using their pre-trained knowledge, we demonstrate their ability to propose innovative heuristic variations based on a semantic understanding of the algorithm's components.To evaluate this, we applied a nontrivial optimization algorithm, Construct, Merge, Solve & Adapt (CMSA)-a hybrid metaheuristic for combinatorial optimization problems that incorporates a heuristic in the solution construction phase.Our results show that an alternative heuristic proposed by GPT-4o outperforms the expert-designed heuristic of CMSA, with the performance gap widening on larger and denser graphs.

The Minimum Global Domination (MGD) problem is a challenging NP-hard variant of the classical Minimum Dominating Set (MDS) problem, which has numerous practical applications. Given an undirected graph, a global dominating set is a set of vertices that dominates all vertices both in the given graph and in its complement graph. In this work, we propose a Population-Based Iterated Greedy (PBIG) algorithm to effectively address the MGD problem. The algorithm employs a semi-greedy solution reconstruction strategy and a redundancy removal mechanism to enhance efficiency and solution quality. We benchmark PBIG against current state-of-the-art approaches, including the CMSA metaheuristic and the CPLEX solver, across 1440 problem instances. Experimental results demonstrate that PBIG outperforms existing methods in solution quality while significantly reducing computational time, establishing it as a powerful and efficient algorithm for the MGD problem.

This paper addresses the Restricted Longest Common Subsequence (RLCS) problem, an extension of the well-known Longest Common Subsequence (LCS) problem. This problem has significant applications in bioinformatics, particularly for identifying similarities and discovering mutual patterns and important motifs among DNA, RNA, and protein sequences. Building on recent advancements in solving this problem through a general search framework, this paper introduces two novel heuristic approaches designed to enhance the search process by steering it towards promising regions in the search space. The first heuristic employs a probabilistic model to evaluate partial solutions during the search process. The second heuristic is based on a neural network model trained offline using a genetic algorithm. A key aspect of this approach is extracting problem-specific features of partial solutions and the complete problem instance. An effective hybrid method, referred to as the learning beam search, is developed by combining the trained neural network model with a beam search framework. An important contribution of this paper is found in the generation of real-world instances where scientific abstracts serve as input strings, and a set of frequently occurring academic words from the literature are used as restricted patterns. Comprehensive experimental evaluations demonstrate the effectiveness of the proposed approaches in solving the RLCS problem. Finally, an empirical explainability analysis is applied to the obtained results. In this way, key feature combinations and their respective contributions to the success or failure of the algorithms across different problem types are identified. • A new learning-based beam search is proposed to tackle the RLCS problem. • Designed both instance-specific and global features of the RLCS instances. • These features served to train multilayer perceptron network in an offline mode. • Outcome of the trained network used to design prominent heuristic guidance. • State-of-the art results obtained by the learning algorithm on both benchmark sets.

Abstract In this paper, we propose SoftBinReduce, a data reduction method for Color Quantization. Our approach consists of four main steps: (1) identifying representatives in each channel, (2) generating three-dimensional bins, (3) distributing pixel values using a soft binning technique, and (4) repositioning the resulting bins. Additionally, we introduce an adapted Sort-Means algorithm for the Pixel Mapping phase, providing a strong initial guess. We conduct an extensive experimental evaluation primarily using the CQ100 dataset, but also the older Kodak and USC-SIPI datasets. We compare our method to two well-known data reduction techniques from the literature: pseudo-random and quasi-random sampling. The results demonstrate that our method outperforms both in terms of NMSE error versus the achieved speedup, particularly when the data is significantly reduced and with a higher number of colors in the generated palette. Moreover, an ablation study shows that all components of our method are necessary for producing high-quality results.

This article considers the longest common square subsequence (LCSqS) problem, a variant of the longest common subsequence (LCS) problem in which solutions must be square strings. A square string can be expressed as the concatenation of a string with itself. The LCSqS problem has applications in bioinformatics, for discovering internal similarities between molecular structures. We propose a metaheuristic approach, a biased random key genetic algorithm (BRKGA) hybridized with a beam search (BS) from the literature. Our approach is based on reducing the LCSqS problem to a set of promising LCS problems. This is achieved by cutting each input string into two parts first and then evaluating such a transformed instance by solving the LCS problem for the obtained overall set of strings. The task of the BRKGA is, hereby, to find a set of good cut points for the input strings. For this purpose, the search is carefully biased by problem-specific greedy information. For each cut point vector, the resulting LCS problem is approximately solved by the existing BS approach. The proposed algorithm is evaluated against a previously proposed state-of-the-art variable neighborhood search (VNS) on random uniform instances from the literature, new nonuniform instances, and a real-world instance set consisting of DNA strings. The results underscore the importance of our work, as our novel approach outperforms former state-of-the-art with statistical significance. Particularly, they evidence the limitations of the VNS when solving nonuniform instances, for which our method shows superior performance.

Introduction to the Special Issue on Large-Scale Optimization and LearningMany real-world optimization problems involve a large number of decision variables.The proliferation of big-data analytic applications has led to the emergence of Large-Scale Optimization Problems (LSOP) at the heart of many data analytics and learning problems [Bottou et al., 2018;Zhou et al., 2014].The curse of dimensionality has made large-scale optimization an exceedingly difficult task, and current optimization methods are often ill-equipped to deal with such problems.To overcome this scalability issue, a wide range of mathematical, metaheuristic, and learningbased optimization algorithms have been developed [Bengio et al., 2021;Omidvar et al., 2022].For example, decomposition methods based on variable interaction analysis have been developed for black-box LSOPs that learn and exploit problem structures [Omidvar et al., 2014].Similarly, there is an emerging set of techniques that leverage Machine Learning (ML) and data mining to significantly reduce the problem size for large-scale combinatorial optimization problems [Sun et al., 2021].This sort of ML-based methods can be incorporated into an optimization algorithm to boost its performance for solving large-scale combinatorial optimization problems [Sun et al., 2022].In recent years, there has been a growing recognition of the synergy between optimization and learning.ML techniques can be used effectively to solve large-scale continuous and combinatorial problems by learning and exploiting problem structures, predicting optimal solutions using data extracted from solved problem instances, reducing problem size, and boosting the performance of existing optimization algorithms.In turn, large-scale optimization can help ML by providing the backbone for many learning algorithms and applications.For example, large-scale optimization is essential for training deep neural networks, where optimization problems with billions of decision variables need to be solved [Hinton and Salakhutdinov, 2006].Therefore, the integration of optimization and learning will play a critical role in addressing the scalability issues that arise in many real-world applications.This special issue was conceived to fill this gap in research that explores the intersection between these two fields.After a rigorous peer-review process, it is our greatest pleasure to introduce the five accepted papers in this special issue.In "Island-Based Evolutionary Computation with Diverse Surrogates and Adaptive Knowledge Transfer for High-Dimensional Data-Driven Optimization" by Xian-Rong Zhang, Yue-Jiao Gong, Zhiguang Cao, and Jun Zhang, an offline data-driven evolutionary algorithm is proposed to make use of surrogate models to approximate an objective function with only a limited amount of

This paper presents a novel extension of the Electric Vehicle Routing Problem (EVRP) to better align with real-world logistics operations and urban environments. We incorporate additional nodes into the road network, representing road junctions. This is in contrast to traditionally considered road networks consisting merely of depots, charging stations, and customers. In addition, each edge of the road network has a specific road type, including highways, urban roads, and city streets. Each road type is characterized by a distinct speed limit. The objective function is designed around the energy consumption of vehicles, which varies based on load, speed, and distance traveled. This results in a more detailed and accurate modeling of the EVRP, making it more suitable for practical implementations. To solve the problem, we provide a construction heuristic based on the Clark and Wright Savings algorithm and an Ant Colony Optimization algorithm based on the MAX-MIN Ant System.

Search Trajectory Networks (STNs) serve as a tool for visualizing algorithm behavior within the realm of optimization problems. Despite their user-friendly nature, challenges arise in obtaining interpretable plots, for example, in the case of optimization problems with large solutions or many dimensions. To address this, we have introduced a new search space partitioning strategy utilizing hierarchical agglomerative clustering. This enhanced strategy, now available in STNWeb, the web version of STNs, produces plots that are easier to interpret than those produced by existing search space partitioning strategies. This facilitates an improved understanding of algorithm performance in complex scenarios.

The ability of Large Language Models (LLMs) to generate high-quality text and code has fuelled their rise in popularity. In this paper, we aim to demonstrate the potential of LLMs within the realm of optimization algorithms by integrating them into STNWeb. This is a web-based tool for the generation of Search Trajectory Networks (STNs), which are visualizations of optimization algorithm behavior. Although visualizations produced by STNWeb can be very informative for algorithm designers, they often require a certain level of prior knowledge to be interpreted. In an attempt to bridge this knowledge gap, we have incorporated LLMs, specifically GPT-4, into STNWeb to produce extensive written reports, complemented by automatically generated plots, thereby enhancing the user experience and reducing the barriers to the adoption of this tool by the research community. Moreover, our approach can be expanded to other tools from the optimization community, showcasing the versatility and potential of LLMs in this field.

The use of machine learning techniques within metaheuristics is a rapidly growing field of research. In this paper, we show how a deep learning framework can be beneficially used to improve an ant colony optimization algorithm. In particular, problem information obtained via deep learning is combined in our algorithm by means of Q-learning with the usual pheromone and greedy information. Our algorithm is applied to the Target Set Selection (TSS) problem, which is an NP-hard combinatorial optimization problem with applications, for example, in social networks. The specific problem variant considered in this paper asks for finding a smallest subset of the nodes of a given graph such that their influence can be spread to all other nodes of the graph via a diffusion process. The experimental results show, first, that the pure ant colony optimization approach can already compete with the state of the art. Second, the obtained results indicate that the hybrid algorithm variant outperforms the pure ant colony optimization approach especially in the context of large problem instances.

In this paper we solve a variant of the multi-hop influence maximization problem in social networks by means of a hybrid algorithm that combines a biased random key genetic algorithm with a graph neural network.Hereby, the predictions of the graph neural network are used with the biased random key genetic algorithm for a more accurate translation of individuals into valid solutions to the tackled problem.The obtained results show that the hybrid algorithm is able to outperform both the biased random key genetic algorithm and the graph neural network when used as standalone techniques.In other words, we were able to show that an integration of both techniques leads to a better algorithm.

The Network Alignment problem is a hard Combinatorial Optimization problem with a wide range of applications, especially in computational biology. Given two (or more) networks, the goal is to find a mapping between their respective nodes that preserves the topological and functional structure of the networks. In this work we extend a novel ant colony optimization approach for network alignment by adding a recently proposed Negative Learning mechanism. In particular, information for Negative Learning is obtained by solving sub-instances of the tackled problem instances at each iteration by means of an Integer Linear Programming solver. The results show that the proposed algorithm not only outperforms the standard ant colony optimization approach but also current state-of-the-art methods from the literature.

The Target Set Selection (TSS) problem is an NP-hard combinatorial optimization problem with origins in the field of social networks. There are various problem variants, all dealing with finding a smallest subset of vertices of a graph such that their influence is propagated to all nodes of the graph under a specific diffusion model. Despite the practical relevance of the problem, most existing research efforts have focused on theoretical properties restricted to certain classes of graphs. The richness in terms of theoretical results is in contrast to the scarceness of research aiming at efficiently solving the TSS problem. In this work we propose a Biased Random Key Genetic Algorithm (BRKGA) for solving the TSS problem in large-scale social networks. We consider the problem in combination with the Linear Threshold diffusion model. The obtained results show that our approach outperforms a recent heuristic from the literature.

Artificial intelligence, and the ability to learn optimized solutions that comply with a set of safety rules, could facilitate the human-based design process of safety-critical systems. However, the reconciliation of state-of-the-art artificial intelligence technology with current safety standards and safety engineering processes is a challenge to be addressed. In this article, this publication describes a method based on optimization and on formal verification for the design of safety-critical systems that are defined by Boolean algebra. Several diverse optimization techniques and a hybrid of these approaches are used to find an optimized design that considers performance requirements, availability rules, and complies with all defined safety rules. Subsequently, this solution is translated into an alternative knowledge representation that can be formally verified and developed in compliance with currently considered safety standards. This method is evaluated with a simplified safety-critical case study.

Peer-to-peer ridesharing enables people to arrange one-time rides with their own private cars, without the involvement of professional drivers. It is a prominent collective intelligence application producing significant benefits both for individuals (reduced costs) and for the entire community (reduced pollution and traffic). Despite these very promising potential advantages, the percentage of users who currently adopt ridesharing solutions is very low, well below the adoption rate required to achieve said benefits. One of the reasons of this insufficient engagement by the public is the lack of effective incentive policies by regulatory authorities, who are not able to estimate the costs and the benefits of a given ridesharing adoption policy. Here we address these issues by (i) developing a novel algorithm that makes large-scale, real-time peer-to-peer ridesharing technologically feasible; and (ii) exhaustively quantifying the impact of different ridesharing scenarios in terms of environmental benefits (i.e., reduction of CO2 emissions, noise pollution, and traffic congestion) and quality of service for the users. Our analysis on a real-world dataset shows that major societal benefits are expected from deploying peer-to-peer ridesharing depending on the trade-off between environmental benefits and quality of service. Results on a real-world dataset show that our approach can produce reductions up to a 70.78% in CO2 emissions and up to 80.08% in traffic congestion.

The minimum connected dominating set (MCDS) problem is an important extension of the minimum dominating set problem, with wide applications, especially in wireless networks. Despite its practical importance, there are few works on solving MCDS for massive graphs, mainly due to the complexity of maintaining connectivity. In this paper, we propose two novel ideas, and develop a new local search algorithm for MCDS called NuCDS. First, a hybrid dynamic connectivity maintenance method is designed to switch alternately between a novel fast connectivity maintenance method based on spanning tree and its previous counterpart. Second, we define a new vertex property called \emph{safety} to make the algorithm more considerate when selecting vertices. Experiments show that NuCDS significantly outperforms the state-of-the-art MCDS algorithms on both massive graphs and classic benchmarks.

Limited payload capacity on small unmanned aerial vehicles (UAVs) results in restricted flight time. In order to increase the operational range of UAVs, recent research has focused on the use of mobile ground charging stations. The cooperative route planning for both aerial and ground vehicles (GVs) is strongly coupled due to fuel constraints of the UAV, terrain constraints of the GV and the speed differential of the two vehicles. This problem is, in general, an NP-hard combinatorial optimization problem. Existing polynomial-time solution approaches make a trade-off in solution quality for large-scale scenarios and generate solutions with large relative gaps (up to 50%) from known lower bounds. In this work, we employ a hybrid metaheuristic known as Construct, Merge, Solve & Adapt (CMSA) in order to develop a scalable and computationally efficient solution approach. We discuss results for large scale scenarios and provide a comparative analysis with the current state-of-the-art.

This work deals with the so-called minimum capacitated dominating set (CAPMDS) problem, which is an NP-Hard combinatorial optimization problem in graphs. In this paper we describe the application of a recently introduced hybrid algorithm known as Construct, Merge, Solve & Adapt (CMSA) to this problem. Moreover, we evaluate the performance of a standalone ILP solver. The results show that both CMSA and the ILP solver outperform current state-of-the-art algorithms from the literature. Moreover, in contrast to the ILP solver, the performance of CMSA does not degrade for the largest problem instances. The experimental evaluation is based on a benchmark dataset containing two different graph topologies and considering graphs with variable and uniform node capacities.

The longest arc-preserving common subsequence problem is an NP-hard combinatorial optimization problem from the field of computational biology. This problem finds applications, in particular, in the comparison of art-annotated ribonucleic acid (RNA) sequences. In this work we propose a simple, hybrid evolutionary algorithm to tackle this problem. The most important feature of this algorithm concerns a crossover operator based on solution merging. In solution merging, two or more solutions to the problem are merged, and an exact technique is used to find the best solution within this union. It is experimentally shown that the proposed algorithm outperforms a heuristic from the literature.

Construct, Merge, Solve & Adapt (CMSA) is a recently proposed hybrid algorithm for combinatorial optimization. At each iteration, the algorithm solves a sub-instance of the original problem instance by means of an exact technique. The incumbent sub-instance is adapted at each iteration, first, by adding solution components present in probabilistically constructed solutions; and, second, by removing solution components that have reached a certain age limit and that do not appear in the optimal solution to the current sub-instance. In this work we propose a refined way for selecting the solution components to be removed from the current sub-instance in those cases in which the exact method employed is an integer linear programming solver. More specifically, the information on the reduced costs of the solution components with respect to the linear programming solution is used for this purpose. Experimental results for the chosen test case, the multidimensional knapsack problem, demonstrate the usefulness of this extension of CMSA.

First paragraph: In combinatorial optimization, the goal is to find an optimal solution, according to some objective function, from a discrete search space. These problems arise widely in industry and academia and, unfortunately, many of them are NP-hard and no polynomial time algorithm can guarantee their solution to a certified optimality unless. Therefore, in the last decades researchers have investigated the use of stochastic search algorithms to find near optimal solutions to these problems. In particular, great research efforts have been devoted to the development and application of metaheuristic algorithms to solve combinatorial optimization problems.

The most strings with few bad columns problem is an NP-hard combinatorial optimization problem from the bioinformatics field. This paper presents the first integer linear programming model for this problem. Moreover, a simple greedy heuristic and a more sophisticated extension, namely a greedy-based pilot method, are proposed. Experiments show that, as expected, the greedy-based pilot method improves over the greedy strategy. For problem instances of small and medium size the best results were obtained by solving the integer linear programming model by CPLEX, while the greedy-based pilot methods scales much better to large problem instances.

An artificial bioindicator system is developed in order to solve a network intrusion detection problem. The system, inspired by an ecological approach to biological immune systems, evolves a population of agents that learn to survive in their environment. An adaptation process allows the transformation of the agent population into a bioindicator that is capable of reacting to system anomalies. Two characteristics stand out in our proposal. On the one hand, it is able to discover new, previously unseen attacks, and on the other hand, contrary to most of the existing systems for network intrusion detection, it does not need any previous training. We experimentally compare our proposal with three state-of-the-art algorithms and show that it outperforms the competing approaches on widely used benchmark data.

Ants are generally believed to follow an intensive work routine. Numerous tales and fables refer to ants as conscientious workers. Nevertheless, biologists have discovered that ants also rest for extended periods of time. This does not only hold for individual ants. Interestingly, ant colonies exhibit synchronized activity phases that result from self-organization. In this work, self-synchronization in ant colonies is taken as the inspiring source for a new mechanism of self-synchronized duty-cycling in mobile sensor networks. Hereby, we assume that sensor nodes are equipped with energy harvesting capabilities such as, for example, solar cells. We show that the proposed self-synchronization mechanism can be made adaptive depending on variable energy resources. The main objective of this paper is to study and explore the swarm intelligence foundations of self-synchronized duty-cycling. With this purpose in mind, physical constraints such as packet collisions and packet loss are generally not considered.

The longest common subsequence problem is classical string problem. It has applications, for example, in pattern recognition and bioinformatics. In this work we present a so-called Beam-ACO approach for solving this problem. Beam-ACO algorithms are hybrid techniques that results from a combination of ant colony optimization and beam search, which is an incomplete branch and bound derivative. Our results show that Beam-ACO is able to find new best solutions for 31 out of 60 benchmark instances that we chose for the experimental evaluation of the algorithm.

In this work we present a protocol for self-synchronized duty-cycling in wireless sensor networks with energy harvesting capabilities. The protocol is implemented in Wiselib, a library of generic algorithms for sensor networks. Simulations are conducted with the sensor network simulator Shawn. They are based on the specifications of real hardware known as iSense sensor nodes. The experimental results show that the proposed mechanism is able to adapt to changing energy availabilities. Moreover, it is shown that the system is very robust against packet loss.

Biological studies have shown that some species of ants rest quite large fractions of their time. Interestingly, not only single ants show this behaviour, but whole ant colonies exhibit synchronized activity phases resulting from self-organization. Inspired by this behaviour, we previously introduced an adaptive and self-synchronized duty-cycling mechanism for mobile sensor networks with energy harvesting capabilities. In this paper, we focus on the study of this mechanism in the context of static sensor networks, because most sensor networks deployed in practice are static. We consider various scenarios that result from the combination of different network topologies and sizes. Our results show that our mechanism also works in the case of static sensor networks with energy harvesting capabilities.

When asked if ants rest or if they work untiringly all day long, most people would probably respond that they had no idea. In fact, when watching the bustling life of an ant hill it is hard to imagine that ants take a rest from now and then. However, biologists discovered that ants rest quite a large fraction of their time. Surprisingly, not only single ants show alternate phases of resting and being active, but whole ant colonies exhibit synchronized activity phases that result from self-organization. Inspired by this self-synchronization behaviour of ant colonies, we develop a mechanism for self-synchronized duty-cycling in mobile sensor networks. In addition, we equip sensor nodes with energy harvesting capabilities such as, for example, solar cells. We show that the self-synchronization mechanism can be made adaptive depending on the available energy.

Assembly line balancing problems are concerned with the optimization of manufacturing processes. In this paper we consider the so-called simple assembly line balancing problem with the objective of minimizing the number of used workstations. This problem is denoted by SALB-1 in the literature. For tackling this problem, we present a so-called Beam-ACO approach. This technique results from hybridizing the metaheuristic ant colony optimization with beam search. The experimental results show that our algorithm is a state-of-the-art method for this problem. It can solve 263 of 269 existing benchmark instances to optimality.

Frequency planning is a very important task for current GSM operators. In this work we present a new mathematical formulation of the problem in which the frequency plans are evaluated by using accurate interference information coming from a real GSM network. We have developed an ant colony optimization (ACO) algorithm to tackle this problem. After accurately tuning this algorithm, it has been compared against a (1,10) Evolutionary Algorithm (EA). The results show that the ACO clearly outperforms the EA when using different time limits as stopping condition for a rather extensive comparison.

This paper contains complimentary material to the tutorial "ant colony optimization: introduction and hybridizations" given by the author at HIS 2007, Kaiserslautern, Germany. First, ant colony optimization is shortly introduced. Then, successful recent hybridizations of ant colony optimization algorithms with other techniques for optimization are reviewed.

In recent years it has been shown that an intelligent combination of metaheuristics with other optimization techniques can significantly improve over the application of a pure metaheuristic. In this paper, we combine the evolutionary computation paradigm with dynamic programming for the application to the NP-hard k-cardinality tree problem. Given an undirected graph G with node and edge weights, this problem consists of finding a tree in G with exactly k edges such that the sum of the weights is minimal. The genetic operators of our algorithm are based on an existing dynamic programming algorithm from the literature for finding optimal subtrees in a given tree. The simulation results show that our algorithm is able to improve the best known results for benchmark problems from the literature in 60 cases.

The edge-disjoint paths (EDP) problem The EDP problem is interesting for different research fields such as combinatorial optimization, algorithmic graph theory and operations research. In general, there is a lack of efficient algorithms for tackling the EDP problem. Only some greedy approaches and a preliminary ant colony optimization (ACO) approach (Blesa and Blum, 2004) exist for tackling the problem. The greedy approaches are used as approximation algorithms for theoretical purposes, but the quality of the solutions they obtain are susceptible to improvement. Based on the (basic) approach in Blesa and Blum (2004), we have evolved a more sophisticated ACO algorithm

Ant colony optimization (ACO) is an optimization technique that was inspired by the foraging behaviour of real ant colonies. Originally, the method was introduced for the application to discrete optimization problems. Research efforts led to the development of algorithms for the application to continuous optimization problems. In this paper we extend and apply one of the most successful variants for the training of feed-forward neural networks. For evaluating our algorithm we apply it to pattern classification problems from the medical field. The results show that our algorithm is comparable to specialized algorithms for neural network training, and that it has advantages over other general purpose optimizers.

One of the problems encountered when applying ant colony optimization (ACO) to combinatorial optimization problems is that the search process is sometimes biased by algorithm features such as the pheromone model and the solution construction process. Sometimes this bias is harmful and results in a decrease in algorithm performance over time, which is called second-order deception. In this work, we study the reasons for the occurrence of second-order deception. In this context, we introduce the concept of competition-balanced system (CBS), which is a property of the combination of an ACO algorithm with a problem instance. We show by means of an example that combinations of ACO algorithms with problem instances that are not CBSs may suffer from a bias that leads to second-order deception. Finally, we show that the choice of an appropriate pheromone model is crucial for the success of the ACO algorithm, and it can help avoid second-order deception.

Ant colony optimization is a metaheuristic approach belonging to the class of model-based search algorithms. In this paper, we propose a new framework for implementing ant colony optimization algorithms called the hyper-cube framework for ant colony optimization. In contrast to the usual way of implementing ant colony optimization algorithms, this framework limits the pheromone values to the interval [0,1]. This is obtained by introducing changes in the pheromone value update rule. These changes can in general be applied to any pheromone value update rule used in ant colony optimization. We discuss the benefits coming with this new framework. The benefits are twofold. On the theoretical side, the new framework allows us to prove that in Ant System, the ancestor of all ant colony optimization algorithms, the average quality of the solutions produced increases in expectation over time when applied to unconstrained problems. On the practical side, the new framework automatically handles the scaling of the objective function values. We experimentally show that this leads on average to a more robust behavior of ant colony optimization algorithms.

In this work we deal with the FOP shop scheduling problem which is a general scheduling problem including job shop scheduling, open shop scheduling and mixed shop scheduling as special cases. The aim of this paper is to compare different pheromone representations taken from the literature with our new approach. The pheromone representations are used by an ant colony optimization algorithm to construct solutions to the FOP shop scheduling problem.