random-key genetic algorithms were introduced by Bean (ORSA J. Comput. 6:154-160, 1994) for solving sequencing problems in combinatorial optimization. Since then, they have been extended to handle a wide class of comb...
详细信息
random-key genetic algorithms were introduced by Bean (ORSA J. Comput. 6:154-160, 1994) for solving sequencing problems in combinatorial optimization. Since then, they have been extended to handle a wide class of combinatorial optimization problems. This paper presents a tutorial on the implementation and use of biased random-key genetic algorithms for solving combinatorial optimization problems. Biased random-key genetic algorithms are 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. After introducing the basics of biased random-key genetic algorithms, the paper discusses in some detail implementation issues, illustrating the ease in which sequential and parallel heuristics based on biased random-key genetic algorithms can be developed. A survey of applications that have recently appeared in the literature is also given.
A divisible load is an amount W of computational work that can be arbitrarily divided into chunks and distributed among a set P of worker processors to be processed in parallel. Divisible load applications occur in ma...
详细信息
A divisible load is an amount W of computational work that can be arbitrarily divided into chunks and distributed among a set P of worker processors to be processed in parallel. Divisible load applications occur in many fields of science and engineering. They can be parallelized in a master-worker fashion, but they pose several scheduling challenges. The divisible load scheduling problem consists in (a) selecting a subset AP of active workers, (b) defining the order in which the chunks will be transmitted to each of them, and (c) deciding the amount of load i that will be transmitted to each worker iA, with Sigma iAi=W, so as to minimize the makespan, i.e., the total elapsed time since the master began to send data to the first worker, until the last worker stops its computations. In this work, we propose a biased random-keygenetic algorithm for solving the divisible load scheduling problem. Computational results show that the proposed heuristic outperforms the best heuristic in the literature.
Given a set of lightpath requests, the problem of routing and wavelength (RWA) assignment in wavelength division multiplexing (WDM) optical networks consists in routing a subset of these requests and assigning a wavel...
详细信息
Given a set of lightpath requests, the problem of routing and wavelength (RWA) assignment in wavelength division multiplexing (WDM) optical networks consists in routing a subset of these requests and assigning a wavelength to each of them, such that two lightpaths that share a common link are assigned to different wavelengths. There are many variants of this problem in the literature. We focus in the variant in which the objective is to maximize the number of requests that may be accepted, given a limited set of available wavelengths. This problem is called max-RWA and it is of practical and theoretical interest, because algorithms for this variant can be extended for other RWA problems that arise from the design of WDM optical networks. A number of exact algorithms based on integer programming formulations have been proposed in the literature to solve max-RWA, as well as algorithms to provide upper bounds to the optimal solution value. However, the algorithms based on the state-of-the-art formulations in the literature cannot solve the largest instances to optimality. For these instances, only upper bounds to the value of the optimal solutions are known. The literature on heuristics for max-RWA is short and focus mainly on solving small size instances with up to 27 nodes. In this paper, we propose new greedy constructive heuristics and a biased random-keygenetic algorithm, based on the best of the proposed greedy heuristics. Computational experiments showed that the new heuristic outperforms the best ones in literature. Furthermore, for the largest instances in the literature where only upper bounds to the value of the optimal solutions are known, the average optimality gap of the best of the proposed heuristics is smaller than 4 %.
The problem of Fiber Installation in Optical Network Optimization consists in routing a set of lightpaths (all-optical connections), such that the cost of the optical components necessary to operate the network is min...
详细信息
ISBN:
(纸本)9781424478354
The problem of Fiber Installation in Optical Network Optimization consists in routing a set of lightpaths (all-optical connections), such that the cost of the optical components necessary to operate the network is minimized. We propose a genetic algorithm with randomkeys that extends the best heuristic in the literature by embedding it into an evolutionary framework. Computational results showed that the new heuristic improves the best heuristic in the literature.
暂无评论