Parallel machine scheduling problems using memetic algorithms

In this paper, we investigate how to apply the hybrid genetic algorithms (the memetic algorithms) to solve the parallel machine scheduling problem. There are two essential issues to be dealt with for all kinds of parallel machine scheduling problems: job partition among machines and job sequence within each machine. The basic idea of the proposed method is that (a) use the genetic algorithms to evolve the job partition and then (b) apply a local optimizer to adjust the job permutation to push each chromosome climb to his local optima. Preliminary computational experiments demonstrate that the hybrid genetic algorithm outperforms the genetic algorithms and the conventional heuristics.     

The impact of parametrization in memetic evolutionary algorithms

Memetic (evolutionary) algorithms integrate local search into the search process of evolutionary algorithms. As computational resources have to be spread adequately among local and evolutionary search, one has to care about when to apply local search and how much computational effort to devote to local search. Often local search is called with a fixed frequency and run for a fixed number of iterations, the local search depth. There is empirical evidence that these parameters have a significant impact on performance, but a theoretical understanding as well as concrete design guidelines are missing.     

A memetic algorithm for the Minimum Sum Coloring Problem

Given an undirected graph G, the Minimum Sum Coloring Problem (MSCP) is to find a legal assignment of colors (represented by natural numbers) to each vertex of G such that the total sum of the colors assigned to the vertices is minimized. This paper presents a memetic algorithm for MSCP based on a tabu search procedure with two neighborhoods and a multi-parent crossover operator. Experiments on a set of 77 well-known DIMACS and COLOR 2002–2004 benchmark instances show that the proposed algorithm achieves highly competitive results in comparison with five state-of-the-art algorithms. In particular, the proposed algorithm can improve the best known results for 15 instances.     

Profit based unit commitment using memetic binary differential evolution algorithm

Profit-based unit-commitment problem (PBUCP) is a notable combinatorial optimizing problem faced in the deregulated power industry. The PBUCP finds the best profitable solution by committing and scheduling the thermal generating units efficiently. To solve the PBUCP, a new memetic binary differential evolution algorithm is proposed which considers binary differential evolution (BDE) algorithm as global search operator to improve the exploration aspect and binary hill-climbing (BHC) algorithm as local search operator to improve the exploitation aspect. A binary differential evolution algorithm is introduced whereby a new mutation strategy is implemented. A novel BHC algorithm makes priority-based perturbations on unit’s status to improve the global best solution searched by the BDE algorithm alone. A new excessive unit de-commitment strategy based on priority and total profit is also proposed. The power to committed units is allocated based on priority of units. The efficacy of algorithms has been researched on the PBUCP test systems comprising of 10-, 40- and 100-units over a time horizon. The outcomes of the proposed algorithms are compared with previously known best solutions. Simulated outcomes achieved by the proposed algorithms compete with the already reported algorithms to solve the PBUCP. Wilcoxon signed-rank test proves the predominance of the proposed algorithms statistically.     

Extensive experiments with hybrid genetic algorithms for the solution of the quadratic assignment problem

In this paper we perform extensive computational experiments solving quadratic assignment problems using various variants of a hybrid genetic algorithm. We introduce a new tabu search (simple tabu). We compared the modified robust tabu and the simple tabu as improvement algorithms in a hybrid genetic algorithm with other tabu searches (concentric tabu, ring moves, all moves, robust tabu) with superior results. We also tested several modifications of the hybrid genetic algorithm and all of them produced good results.     

A memetic algorithm for cardinality-constrained portfolio optimization with transaction costs

A memetic approach that combines a genetic algorithm (GA) and quadratic programming is used to address the problem of optimal portfolio selection with cardinality constraints and piecewise linear transaction costs. The framework used is an extension of the standard Markowitz mean–variance model that incorporates realistic constraints, such as upper and lower bounds for investment in individual assets and/or groups of assets, and minimum trading restrictions. The inclusion of constraints that limit the number of assets in the final portfolio and piecewise linear transaction costs transforms the selection of optimal portfolios into a mixed-integer quadratic problem, which cannot be solved by standard optimization techniques. We propose to use a genetic algorithm in which the candidate portfolios are encoded using a set representation to handle the combinatorial aspect of the optimization problem. Besides specifying which assets are included in the portfolio, this representation includes attributes that encode the trading operation (sell/hold/buy) performed when the portfolio is rebalanced. The results of this hybrid method are benchmarked against a range of investment strategies (passive management, the equally weighted portfolio, the minimum variance portfolio, optimal portfolios without cardinality constraints, ignoring transaction costs or obtained with L₁ regularization) using publicly available data. The transaction costs and the cardinality constraints provide regularization mechanisms that generally improve the out-of-sample performance of the selected portfolios.     

Enhancing the performance of hybrid genetic algorithms by differential improvement

A differential improvement modification to Hybrid Genetic Algorithms is proposed. The general idea is to perform more extensive improvement algorithms on higher quality solutions. Our proposed Differential Improvement (DI) approach is of rather general character. It can be implemented in many different ways. The paradigm remains invariant and can be easily applied to a wider class of optimization problems. Moreover, the DI framework can also be used within other Hybrid metaheuristics like Hybrid Scatter Search algorithms, Particle Swarm Optimization, or Bee Colony Optimization techniques.     

A Tabu search algorithm for the network pricing problem

In this paper, we propose an efficient Tabu Search procedure for solving the NP-hard network pricing problem. By exploiting the problem's features, the algorithm allows the near-optimal solution of problem instances that are out of reach of exact combinatorial methods.     

Memetic algorithm with route decomposing for periodic capacitated arc routing problem

In this paper, the Periodic Capacitated Arc Routing Problem (PCARP) is investigated. PCARP is an extension of the well-known CARP from a single period to a multi-period horizon. In PCARP, two objectives are to be minimized. One is the number of required vehicles (nv), and the other is the total cost (tc). Due to the multi-period nature, given the same graph or road network, PCARP can have a much larger solution space than the single-period CARP counterpart. Furthermore, PCARP consists of an additional allocation sub-problem (of the days to serve the arcs), which is interdependent with the routing sub-problem. Although some attempts have been made for solving PCARP, more investigations are yet to be done to further improve their performance especially on large-scale problem instances. It has been shown that optimizing nv and tc separately (hierarchically) is a good way of dealing with the two objectives. In this paper, we further improve this strategy and propose a new Route Decomposition (RD) operator thereby. Then, the RD operator is integrated into a Memetic Algorithm (MA) framework for PCARP, in which novel crossover and local search operators are designed accordingly. In addition, to improve the search efficiency, a hybridized initialization is employed to generate an initial population consisting of both heuristic and random individuals. The MA with RD (MARD) was evaluated and compared with the state-of-the-art approaches on two benchmark sets of PCARP instances and a large data set which is based on a real-world road network. The experimental results suggest that MARD outperforms the compared state-of-the-art algorithms, and improves most of the best-known solutions. The advantage of MARD becomes more obvious when the problem size increases. Thus, MARD is particularly effective in solving large-scale PCARP instances. Moreover, the efficacy of the proposed RD operator in MARD has been empirically verified.     

Towards hybrid evolutionary algorithms

Metaheuristics have received considerable interest these recent years in the field of combinatorial optimization. However, the choice of a particular algorithm to optimize a certain problem is still mainly driven by some sort of devotion of its author to a certain technique rather than by a rationalistic choice driven by reason. Hybrid algorithms have shown their ability to provide local optima of high quality. Hybridization of algorithms is still in its infancy: certain combinations of algorithms have experimentally shown their performance, though the reasons of their success is not always really clear. In order to add some rational to these issues, we study the structure of search spaces and attempt to relate it to the performance of algorithms. We wish to explain the behavior of search algorithms with this knowledge and provide guidelines in the design of hybrid algorithms. This paper briefly reviews the current knowledge we have on search spaces of combinatorial optimization problems. Then, we discuss hybridization and present a general classification of the way hybridization can be conducted in the light of our knowledge of the structure of search spaces.     

Evolutionary algorithms and dynamic programming

Recently, it has been proven that evolutionary algorithms produce good results for a wide range of combinatorial optimization problems. Some of the considered problems are tackled by evolutionary algorithms that use a representation which enables them to construct solutions in a dynamic programming fashion. We take a general approach and relate the construction of such algorithms to the development of algorithms using dynamic programming techniques. Thereby, we give general guidelines on how to develop evolutionary algorithms that have the additional ability of carrying out dynamic programming steps. Finally, we show that for a wide class of the so-called DP-benevolent problems (which are known to admit FPTAS) there exists a fully polynomial-time randomized approximation scheme based on an evolutionary algorithm.     

Improving fuzzy cognitive maps learning through memetic particle swarm optimization

Fuzzy cognitive maps constitute a neuro-fuzzy modeling methodology that can simulate complex systems accurately. Although their configuration is defined by experts, learning schemes based on evolutionary and swarm intelligence algorithms have been employed for improving their efficiency and effectiveness. This paper comprises an extensive study of the recently proposed swarm intelligence memetic algorithm that combines particle swarm optimization with both deterministic and stochastic local search schemes, for fuzzy cognitive maps learning tasks. Also, a new technique for the adaptation of the memetic schemes, with respect to the available number of function evaluations per application of the local search, is proposed. The memetic learning schemes are applied on four real-life problems and compared with established learning methods based on the standard particle swarm optimization, differential evolution, and genetic algorithms, justifying their superiority.     

On the efficiency of maximum-flow algorithms on networks with small integer capacities

The performance of maximum-flow algoirthms that work in phases is studied as a function of the maximum arc capacity,C, of the network and a quantity we call thetotal potential, P, of the network, which is related to the average amount of flow that can be sent through a node. Extending results by Even and Tarjan, we derive a tightO(min{C ^1/3¦V¦^2/3,P ^1/2, ¦V¦}) upper bound on the number of phases. AnO(min{P log¦V¦,C¦V¦^3/2, ¦V¦²¦E¦}) upper bound is derived on the total length of the augmenting paths used by Dinic's algorithm. The latter quantity is useful in estimating the performance of Dinic's method on certain inputs. Our results show that on a natural class of networks, the performance of Dinic's algorithm is significantly better than would be apparent from a bound based on ¦V¦ and ¦E¦ alone. We present an application of our bounds to the maximum subgraph density problem.     

Approximation algorithms for combinatorial multicriteria optimization problems

The computational complexity of combinatorial multiple objective programming problems is investigated. NP-completeness and # P -completeness results are presented. Using two definitions of approximability, general results are presented, which outline limits for approximation algorithms. The performance of the well-known tree and Christofides' heuristics for the traveling salesman problem is investigated in the multicriteria case with respect to the two definitions of approximability.     

On extending de Bruijn sequences

We give a complete proof of the following theorem:Every de Bruijn sequence of order n in at least three symbols can be extended to a de Bruijn sequence of order n+1. Every de Bruijn sequence of order n in two symbols can not be extended to order n+1, but it can be extended to order n+2.     

Low-autocorrelation binary sequences: On improved merit factors and runtime predictions to achieve them

The search for binary sequences with a high figure of merit, known as the low autocorrelation binary sequence (labs) problem, represents a formidable computational challenge. To mitigate the computational constraints of the problem, we consider solvers that accept odd values of sequence length L and return solutions for skew-symmetric binary sequences only – with the consequence that not all best solutions under this constraint will be optimal for each L. In order to improve both, the search for best merit factor and the asymptotic runtime performance, we instrumented three stochastic solvers, the first two are state-of-the-art solvers that rely on variants of memetic and tabu search (lssMAts and lssRRts), the third solver (lssOrel) organizes the search as a sequence of independent contiguous self-avoiding walk segments. By adapting a rigorous statistical methodology to performance testing of all three combinatorial solvers, experiments show that the solver with the best asymptotic average-case performance, lssOrel_8 = 0.000032 * 1.1504^L, has the best chance of finding solutions that improve, as L increases, figures of merit reported to date. The same methodology can be applied to engineering new labs solvers that may return merit factors even closer to the conjectured asymptotic value of 12.3248.     

大线性复杂度三值自相关的二元三阶分圆序列的构造

对于一类周期为素数p,p≡1(mod 3)的二元三阶分圆序列提出了一种构造方法,确保其少自相关值及大线性复杂度。利用分圆的知识计算其自相关值,并进一步考虑序列的自相关值为三值时,素数p应满足的条件。此时p应满足p=a²+12,a为整数。当p满足此形式时,序列的线性复杂度为p-1,否则为2(p-1)/3。通过计算机实验,找出了满足所给形式的p,并能生成对应的序列集,验证了序列的自相关性及线性复杂度。新序列的线性复杂度和已有的三元三阶分圆序列的相同;和二元偶数阶分圆序列的相比,大部分相同或较优(已有的有些情况为(p-1)/2、(p+1)/2或1+(p-1)/6)。所提出的构造方法可推广至其他少自相关值、大线性复杂度的奇数阶分圆序列集的构造上。大奇数阶分圆序列的平衡性也会提高,能被较好地应用于密码与通信系统中。     

A memetic algorithm for the flexible flow line scheduling problem with processor blocking

This paper introduces an efficient memetic algorithm (MA) combined with a novel local search engine, namely, nested variable neighbourhood search (NVNS), to solve the flexible flow line scheduling problem with processor blocking (FFLB) and without intermediate buffers. A flexible flow line consists of several processing stages in series, with or without intermediate buffers, with each stage having one or more identical parallel processors. The line produces a number of different products, and each product must be processed by at most one processor in each stage. To obtain an optimal solution for this type of complex, large-sized problem in reasonable computational time using traditional approaches and optimization tools is extremely difficult. Our proposed MA employs a new representation, operators, and local search method to solve the above-mentioned problem. The computational results obtained in experiments demonstrate the efficiency of the proposed MA, which is significantly superior to the classical genetic algorithm (CGA) under the same conditions when the population size is increased in the CGA.