Search

In the last decade a new variety of nature inspired optimization algorithms has been appeared. After the swarm based models, researchers turned their inspiration in nature phenomena and laws of science. In this way a new category of algorithms was born, equally effective or even sometimes superior to known algorithms for optimization problems, like genetic algorithms and swarm intelligence schemes. The present survey depicts the evolution of research on nature inspired optimization algorithms related to physical phenomena and laws of science and discusses the possibilities of using the presented approaches in a number of different applications. An attempt has been made to draw conclusions on what algorithm could be used in which different problem areas, for those approaches that this information could be extracted from the related papers studied. The paper also underlines the usage of this kind of nature inspired algorithms in industrial research problems, due to their better confrontation with optimization problems represented with nodes and edges. [ABSTRACT FROM AUTHOR]

In this paper, we consider optimal scheduling algorithms for scientific workows with two typical structures, fork&join and tree, on a set of provisioned (virtual) machines under budget and deadline constraints in cloud computing. First, given a total budget B, by leveraging a bi-step dynamic programming technique, we propose optimal algorithms in pseudo-polynomial time for both workows with minimum scheduling length as a goal. Our algorithms are efficient if the total budget B is polynomially bounded by the number of jobs in respective workows, which is usually the common case in practice. Second, we consider the dual of this optimization problem to minimize the cost when the deadline of the computation D is fixed. We change this problem into the standard multiple-choice knapsack problem via a parallel transformation. [ABSTRACT FROM AUTHOR]

Many real world industrial applications involve the Traveling Salesman Problem (TSP), which is a problem that finds a Hamiltonian path with minimum cost. Examples of problems that belong to this category are transportation routing problem, scan chain optimization and drilling problem in integrated circuit testing and production. This paper presents a Bee Colony Optimization (BCO) algorithm for symmetrical TSP. The BCO model is constructed algorithmically based on the collective intelligence shown in bee foraging behaviour. The algorithm is integrated with a fixed-radius near neighbour 2-opt (FRNN 2-opt) heuristic to further improve prior solutions generated by the BCO model. To limit the overhead incurred by the FRNN 2-opt, a frequency-based pruning strategy is proposed. The pruning strategy allows only a subset of the promising solutions to undergo local optimization. Experimental results comparing the proposed BCO algorithm with existing approaches on a set of benchmark problems are presented. For 84 benchmark problems, the BCO algorithm is able to obtain an overall average solution quality of 0.31% from known optimum. The results also show that it is comparable to other algorithms such as Ant Colony Optimization and Particle Swarm Optimization. [ABSTRACT FROM AUTHOR]

This paper presents a parallel framework for the solution of multi-objective optimization problems. The framework implements some of the best known multi-objective evolutionary algorithms. The plugin-based architecture of the framework minimizes the end user effort required to incorporate their own problems and evolutionary algorithms, and facilitates tool maintenance. A wide variety of configuration options can be specified to adapt the software behavior to many different parallel models. An innovation of the framework is that it provides a self-adaptive parallel model that is based on the cooperation of a set of evolutionary algorithms. The aim of the new model is to raise the level of generality at which most current evolutionary algorithms operate. This way, a wider range of problems can be tackled since the strengths of one algorithm can compensate for the weaknesses of another. The model proposed is a hybrid algorithm that combines a parallel island-based scheme with a hyperheuristic approach. The model grants more computational resources to those algorithms that show a more promising behavior. The flexibility and efficiency of the framework were tested and demonstrated by configuring standard and self-adaptive models for test problems and real-world applications. [ABSTRACT FROM AUTHOR]

In this paper we present a radical approach to obtaining a backtrack-free representation for a constraint satisfaction problem: remove values that lead to dead-ends. This technique does not require additional space but has the drawback of removing solutions. We investigate a number of variations on the basic algorithm including the use of seed solutions, consistency techniques, and a variety of pruning heuristics. Our experimental results indicate that a significant proportion of the solutions to the original problem can be retained especially when an optimization algorithm that specifically searches for such “good” backtrack-free representations is employed. Further extensions increase solution retention by searching for high-coverage backtrack-free representations, by removing tuples rather than values, and by combining multiple backtrack-free representations. Our approach elucidates, for the first time, a three-way trade-off between space complexity, potential backtracks, and solution loss and enables algorithms that can actively reason about the trade-off between space, backtracks, and solution loss. [ABSTRACT FROM AUTHOR]

A complex model for evolving the update strategy of a Particle Swarm Optimisation (PSO) algorithm is described in this paper. The model is a hybrid technique that combines a Genetic Algorithm (GA) and a PSO algorithm. Each GA chromosome is an array encoding a meaning for updating the particles of the PSO algorithm. The Evolved PSO algorithm is compared to several human-designed PSO algorithms by using ten artificially constructed functions and one real-world problem. Numerical experiments show that the Evolved PSO algorithm performs similarly and sometimes even better than the Standard approaches for the considered problems. The Evolved PSO is highly scalable (regarding the size of the problem's input), being able to solve problems having different dimensions. [ABSTRACT FROM AUTHOR]

A temporal flexible planning problem that involves contingent and requirement events can be formulated as a simple temporal network with uncertainty (STNU). An STNU is controllable when there is a strategy for executing the requirement events (or actions) in such a way that all the conditions involving contingent events can be satisfied in all situations. The most interesting and useful controllability property is dynamic controllability in which the remaining actions in an STNU can always be scheduled under all possible feasible durations of future contingent events when all the past contingent events are known. In this paper, we propose and study a novel problem of assigning bounds on the duration of each requirement link in order for the resulting STNU to be dynamically controllable and to minimize the total cost over the allowed durations of all requirement links. We first prove the NP hardness of the problem with a linear cost function. We then formulate the dynamic controllability of an STNU as the constraints in a nonlinear optimization problem. Finally, we present methods for reducing the number of constraints in order to make the problem tractable and to demonstrate the computational performance of our methods. [ABSTRACT FROM AUTHOR]

The use of evolutionary algorithms (EAs) to solve problems with multiple objectives (known as Vector Optimization Problems (VOPs)) has attracted much attention recently. Being population based approaches, EAs offer a means to find a group of pareto-optimal solutions in a single run. Differential Evolution (DE) is an EA that was developed to handle optimization problems over continuous domains. The objective of this paper is to introduce a novel Pareto Differential Evolution (PDE) algorithm to solve VOPs. The solutions provided by the proposed algorithm for five standard test problems, is competitive to nine known evolutionary multiobjective algorithms for solving VOPs. [ABSTRACT FROM AUTHOR]