tailieunhanh - A new genetic representation for quadratic assignment problem

In this paper, we propose a new genetic encoding for well known Quadratic Assignment Problem (QAP). The new encoding schemes are implemented with appropriate objective function and modified genetic operators. The numerical experiments were carried out on the standard QAPLIB data sets known from the literature. The presented results show that in all cases proposed genetic algorithm reached known optimal solutions in reasonable time. | Yugoslav Journal of Operations Research 21 (2011), Number 2, 225-238 DOI: A NEW GENETIC REPRESENTATION FOR QUADRATIC ASSIGNMENT PROBLEM1 Jozef KRATICA Mathematical Institute, Serbian Academy of Sciences and Arts, Belgrade, Serbia jkratica@ Dušan TOŠIĆ, Vladimir FILIPOVIĆ, Đorđe DUGOŠIJA Faculty of Mathematics, University of Belgrade, Belgrade, Serbia {dtosic | vladaf | dugosija}@ Received: October 2009 / Accepted: November 2011 Abstract: In this paper, we propose a new genetic encoding for well known Quadratic Assignment Problem (QAP). The new encoding schemes are implemented with appropriate objective function and modified genetic operators. The numerical experiments were carried out on the standard QAPLIB data sets known from the literature. The presented results show that in all cases proposed genetic algorithm reached known optimal solutions in reasonable time. Keywords: Genetic algorithm, evolutionary computation, combinatorial optimization, quadratic assignment problem. MSC: 90C59, 68T20, 90e20. 1 This research was partially supported by Serbian Ministry of Education and Science under the grant no. 174010 226 J. Kratica, D. Tošić, V. Filipović, Đ. Dugošija / A New Genetic Representation for QAP 1. INTRODUCTION . Quadratic assignment problem The Quadratic Assignment Problem (QAP) is firstly proposed in [16] as a mathematical model related to economic activities. Since then, it has appeared in many practical applications as can be seen from [22]. We mention only several recent applications: • facility layout design problem in order to minimize work-in-process [29]; • website structure improvement [27]; • placement of electronic components [9]; • index assignment problem related to error control in communications [3]; • memory layout optimization in signal processors [34]. Several NP-hard combinatorial optimization problems, such as the traveling salesman problem, the bin-packing problem and the max clique

• Sinh học
• Genetic algorithm
• Evolutionary computation
• Combinatorial optimization
• Quadratic assignment problem
• Modified genetic operators