A biased random key genetic algorithm applied to the electric distribution network reconfiguration problem

This work presents a biased random-key genetic algorithm (BRKGA) to solve the electric distribution network reconfiguration problem (DNR). The DNR is one of the most studied combinatorial optimization problems in power system analysis. Given a set of switches of an electric network that can be opened or closed, the objective is to select the best configuration of the switches to optimize a given network objective while at the same time satisfying a set of operational constraints. The good performance of BRKGAs on many combinatorial optimization problems and the fact that it has never been applied to solve DNR problems are the main motivation for this research. A BRKGA is a variant of random-key genetic algorithms, where one of the parents used for mating is biased to be of higher fitness than the other parent. Solutions are encoded by using random keys, which are represented as vectors of real numbers in the interval (0,1), thus enabling an indirect search of the solution inside a proprietary search space. The genetic operators do not need to be modified to generate only feasible solutions, which is an exclusive task of the decoder of the problem. Tests were performed on standard distribution systems used in DNR studies found in the technical literature and the performance and robustness of the BRKGA were compared with other GA implementations.     

A biased random-key genetic algorithm for road congestion minimization

One of the main goals in transportation planning is to achieve solutions for two classical problems, the traffic assignment and toll pricing problems. The traffic assignment problem aims to minimize total travel delay among all travelers. Based on data derived from the first problem, the toll pricing problem determines the set of tolls and corresponding tariffs that would collectively benefit all travelers and would lead to a user equilibrium solution. Obtaining high-quality solutions for this framework is a challenge for large networks. In this paper, we propose an approach to solve the two problems jointly, making use of a biased random-key genetic algorithm for the optimization of transportation network performance by strategically allocating tolls on some of the links of the road network. Since a transportation network may have thousands of intersections and hundreds of road segments, our algorithm takes advantage of mechanisms for speeding up shortest-path algorithms.     

A particle swarm optimization-based hybrid algorithm for minimum concave cost network flow problems

Traditionally, minimum cost transshipment problems have been simplified as linear cost problems, which are not practical in real applications. Some advanced local search algorithms have been developed to solve concave cost bipartite network problems. These have been found to be more effective than the traditional linear approximation methods and local search methods. Recently, a genetic algorithm and an ant colony system algorithm were employed to develop two global search algorithms for solving concave cost transshipment problems. These two global search algorithms were found to be more effective than the advanced local search algorithms for solving concave cost transshipment problems. Although the particle swarm optimization algorithm has been used to obtain good results in many applications, to the best of our knowledge, it has not yet been applied in minimum concave cost network flow problems. Thus, in this study, we employ an arc-based particle swarm optimization algorithm, coupled with some genetic algorithm and threshold accepting method techniques, as well as concave cost network heuristics, to develop a hybrid global search algorithm for efficiently solving minimum cost network flow problems with concave arc costs. The proposed algorithm is evaluated by solving several randomly generated network flow problems. The results indicate that the proposed algorithm is more effective than several other recently designed methods, such as local search algorithms, genetic algorithms and ant colony system algorithms, for solving minimum cost network flow problems with concave arc costs.     

Almost sure convergence for stochastically biased random walks on trees

We are interested in the biased random walk on a supercritical Galton?CWatson tree in the sense of Lyons (Ann. Probab. 18:931?C958, 1990) and Lyons, Pemantle and Peres (Probab. Theory Relat. Fields 106:249?C264, 1996), and study a phenomenon of slow movement. In order to observe such a slow movement, the bias needs to be random; the resulting random walk is then a tree-valued random walk in random environment. We investigate the recurrent case, and prove, under suitable general integrability assumptions, that upon the system??s non-extinction, the maximal displacement of the walk in the first n steps, divided by (log n)³, converges almost surely to a known positive constant.     

A hybrid algorithm for nonlinear minimax problems

In this paper, a hybrid algorithm for solving finite minimax problem is presented. In the algorithm, we combine the trust-region methods with the line-search methods and curve-search methods. By means of this hybrid technique, the algorithm, according to the specific situation at each iteration, can adaptively performs the trust-region step, line-search step or curve-search step, so as to avoid possibly solving the trust-region subproblems many times, and make better use of the advantages of different methods. Moreover, we use second-order correction step to circumvent the difficulties of the Maratos effect occurred in the nonsmooth optimization. Under mild conditions, we prove that the new algorithm is of global convergence and locally superlinear convergence. The preliminary experiments show that the new algorithm performs efficiently.     

A biased random-key genetic algorithm for routing and wavelength assignment

The problem of routing and wavelength assignment in wavelength division multiplexing optical networks consists in routing a set of lightpaths and assigning a wavelength to each of them, such that lightpaths whose routes share a common fiber are assigned different wavelengths. This problem was shown to be NP-hard when the objective is to minimize the total number of wavelengths used. We propose a genetic algorithm with random keys for routing and wavelength assignment with the goal of minimizing the number of different wavelengths used in the assignment. This algorithm extends the best heuristic in the literature by embedding it into an evolutionary framework. Computational results show that the new heuristic improves the state-of-the-art algorithms in the literature.     

Fuzzy nonlinear programming for mixed-discrete design optimization through hybrid genetic algorithm

Many practical engineering optimization problems involve discrete or integer design variables, and often the design decisions are to be made in a fuzzy environment in which the statements might be vague or imprecise. A mixed-discrete fuzzy nonlinear programming approach that combines the fuzzy λ-formulation with a hybrid genetic algorithm is proposed in this paper. This method can find a globally compromise solution for a mixed-discrete fuzzy optimization problem, even when the objective function is nonconvex and nondifferentiable. In the construction of the objective membership function, an error from the early research work is corrected and the right conclusion has been made. The illustrative examples demonstrate that more reliable and satisfactory results can be obtained through the present method.     

A biased random-key genetic algorithm for the Steiner triple covering problem

We present a biased random-key genetic algorithm (BRKGA) for finding small covers of computationally difficult set covering problems that arise in computing the 1-width of incidence matrices of Steiner triple systems. Using a parallel implementation of the BRKGA, we compute improved covers for the two largest instances in a standard set of test problems used to evaluate solution procedures for this problem. The new covers for instances A ₄₀₅ and A ₇₂₉ have sizes 335 and 617, respectively. On all other smaller instances our algorithm consistently produces covers of optimal size.     

A sharp threshold for minimum bounded-depth and bounded-diameter spanning trees and Steiner trees in random networks

In the complete graph on n vertices, when each edge has a weight which is an exponential random variable, Frieze proved that the minimum spanning tree has weight tending to ζ(3) = 1/1³ + 1/2³ + 1/3³ +… as n → ∞. We consider spanning trees constrained to have depth bounded by k from a specified root. We prove that if k ≥ log₂ logn+ω(1), where ω(1) is any function going to ∞ with n, then the minimum bounded-depth spanning tree still has weight tending to ζ(3) as n → ∞, and that if k < log₂ logn, then the weight is doubly-exponentially large in log₂ logn ? k. It is NP-hard to find the minimum bounded-depth spanning tree, but when k≤log₂ logn?ω(1), a simple greedy algorithm is asymptotically optimal, and when k ≥ log₂ logn+ω(1), an algorithm which makes small changes to the minimum (unbounded depth) spanning tree is asymptotically optimal. We prove similar results for minimum bounded-depth Steiner trees, where the tree must connect a specified set of m vertices, and may or may not include other vertices. In particular, when m=const×n, if k≥log₂ logn+ω(1), the minimum bounded-depth Steiner tree on the complete graph has asymptotically the same weight as the minimum Steiner tree, and if 1 ≤ k ≤ log₂ logn?ω(1), the weight tends to $(1 - 2^{ - k} )\sqrt {8m/n} \left[ {\sqrt {2mn} /2^k } \right]^{1/(2^k - 1)}$ in both expectation and probability. The same results hold for minimum bounded-diameter Steiner trees when the diameter bound is 2k; when the diameter bound is increased from 2k to 2k+1, the minimum Steiner tree weight is reduced by a factor of $2^{1/(2^k - 1)}$ .     

A hybrid grouping genetic algorithm for bin packing

The grouping genetic algorithm (GGA) is a genetic algorithm heavily modified to suit the structure of grouping problems. Those are the problems where the aim is to find a good partition of a set or to group together the members of the set. The bin packing problem (BPP) is a well known NP-hard grouping problem: items of various sizes have to be grouped inside bins of fixed capacity. On the other hand, the reduction method of Martello and Toth, based on their dominance criterion, constitutes one of the best OR techniques for optimization of the BPP to date.In this article, we first describe the GGA paradigm as compared to the classic Holland-style GA and the ordering GA. We then show how the bin packing GGA can be enhanced with a local optimization inspired by the dominance criterion. An extensive experimental comparison shows that the combination yields an algorithm superior to either of its components.     

A biased random-key genetic algorithm for the tree of hubs location problem

Hubs are facilities used to treat and dispatch resources in a transportation network. The objective of Hub Location Problems (HLP) is to locate a set of hubs in a network and route resources from origins to destinations such that the total cost of attending all demands is minimized. In this paper, we investigate a particular HLP, called the Tree of Hubs Location Problem in which hubs are connected by means of a tree and the overall network infrastructure relies on a spanning tree. This problem is particularly interesting when the total cost of building the hub backbone is high. We propose a biased random key genetic algorithm for solving the tree of hubs location problem. Computational results show that the proposed heuristic is robust and effective to this problem. The method was able to improve best known solutions of two benchmark instances used in the experiments.     

A hybrid macroscopic-based model for traffic flow in road networks

Recently, the unquestionable growth of interest to increase the operational efficiency and capability of transportation systems led to the development of a large number of traffic modeling theories. One of the major operational issues when developing a transportation system management model lies in the selection of the appropriate methodological approach with respect to several decisions, such as the selection of the type of input and output data as well as the qualitative representation and the computational power of the model. Despite the considerable effort in the area, there is still not an approach which per se models effectively the various dynamically evolving features of traffic in road networks. The present paper addresses this issue by introducing a new hybrid approach which combines the complementary features and capabilities of both continuum mathematical models e.g. 1, 6, 23 and 26 and knowledge-based models e.g. 7, 22 and 28 in order to describe effectively traffic flow in road networks.     

A polynomial algorithm for minimum quadratic cost flow problems

Network flow problems with quadratic separable costs appear in a number of important applications such as; approximating input-output matrices in economy; projecting and forecasting traffic matrices in telecommunication networks; solving nondifferentiable cost flow problems by subgradient algorithms. It is shown that the scaling technique introduced by Edmonds and Karp (1972) in the case of linear cost flows for deriving a polynomial complexity bound for the out-of-kilter method, may be extended to quadratic cost flows and leads to a polynomial algorithm for this class of problems. The method may be applied to the solution of singly constrained quadratic programs and thus provides an alternative approach to the polynomial algorithm suggested by Helgason, Kennington and Lall (1980).     

A novel hybrid genetic algorithm for solving Sudoku puzzles

In this article, a novel hybrid genetic algorithm is proposed. The selection operator, crossover operator and mutation operator of the genetic algorithm have effectively been improved according to features of Sudoku puzzles. The improved selection operator has impaired the similarity of the selected chromosome and optimal chromosome in the current population such that the chromosome with more abundant genes is more likely to participate in crossover; such a designed crossover operator has possessed dual effects of self-experience and population experience based on the concept of tactfully combining PSO, thereby making the whole iterative process highly directional; crossover probability is a random number and mutation probability changes along with the fitness value of the optimal solution in the current population such that more possibilities of crossover and mutation could then be considered during the algorithm iteration. The simulation results show that the convergence rate and stability of the novel algorithm has significantly been improved.     

A hybrid genetic algorithm for the container loading problem

This paper presents a hybrid genetic algorithm (GA) for the container loading problem with boxes of different sizes and a single container for loading. Generated stowage plans include several vertical layers each containing several boxes. Within the procedure, stowage plans are represented by complex data structures closely related to the problem. To generate offspring, specific genetic operators are used that are based on an integrated greedy heuristic. The process takes several practical constraints into account. Extensive test calculations including procedures from other authors vouch for the good performance of the GA, above all for problems with strongly heterogeneous boxes.     

A biased random-key genetic algorithm for the project scheduling problem with flexible resources

In this paper, we investigate a resource-constrained project scheduling problem with flexible resources. This is an \(\mathcal {NP}\)-hard combinatorial optimization problem that consists of scheduling a set of activities requiring specific resource units of several skills. The goal is to minimize the makespan of the project. We propose a biased random-key genetic algorithm for computing feasible solutions for the referred problem. We study different decoding mechanisms: an already existing method in the literature, a new adapted serial scheduling generation scheme, and a combination of both. The new procedure is tested using a set of benchmark instances of the problem. The results provide strong evidence that the new heuristic is robust and yields high-quality feasible solutions.     

Minimum cost flow algorithms for series-parallel networks

It is shown that an acyclic multigraph with a single source and a single sink is series-parallel if and only if for arbitrary linear cost functions and arbitrary capacities the corresponding minumum cost flow problem can be solved by a greedy algorithm. Furthermore, for networks of this type with m edges and n vertices, two O(mn+logm)-algorithms. One of them is based on the greedy scheme.     

A genetic algorithm for flow shop scheduling problems

Many scheduling problems are NP-hard problems. For such NP-hard combinatorial optimization problems, heuristics play a major role in searching for near-optimal solutions. In this paper we develop a genetic algorithm-based heuristic for the flow shop scheduling problem with makespan as the criterion. The performance of the algorithm is compared with the established NEH algorithm. Computational experience indicates that genetic algorithms can be good techniques for flowshop scheduling problems.