TAILIEUCHUNG - Optimal recombination in genetic algorithms for combinatorial optimiyation problems – part II

This paper surveys results on complexity of the optimal recombination problem (ORP), which consists in finding the best possible offspring as a result of a recombination operator in a genetic algorithm, given two parent solutions. In Part II, we consider the computational complexity of ORPs arising in genetic algorithms for problems on permutations. | Yugoslav Journal of Operations Research 24 (2014) Number 2,165-186 DOI: OPTIMAL RECOMBINATION IN GENETIC ALGORITHMS FOR COMBINATORIAL OPTIMIYATION PROBLEMS – PART II Anton V. EREMEEV Sobolev Institute of Mathematics, Laboratory of Discrete Optimization 630090, Novosibirsk, Russia eremeev@ Julia V. KOVALENKO Omsk . Dostoevsky State University, Institute of Mathematics and Information Technologies, 644077, Omsk, Russia juliakoval86@ Received: July 2013 / Accepted: October 2013 Abstract: This paper surveys results on complexity of the optimal recombination problem (ORP), which consists in finding the best possible offspring as a result of a recombination operator in a genetic algorithm, given two parent solutions. In Part II, we consider the computational complexity of ORPs arising in genetic algorithms for problems on permutations: the Travelling Salesman Problem, the Shortest Hamilton Path Problem and the Makespan Minimization on Single Machine and some other related problems. The analysis indicates that the corresponding ORPs are NP-hard, but solvable by faster algorithms, compared to the problems they are derived from. Keywords: Genetic Algorithm, Optimal Recombination Problem, complexity, crossover, permutation problems. MSC: 90C59, 90C10. Performance of genetic algorithms (GA) depends significantly upon the choice of the crossover operator, where the components of parent solutions are combined to build the offspring. This survey is devoted to complexity and solution methods of the Optimal Recombination Problem (ORP), which consists in finding the best possible offspring as a result of a crossover operator, given two feasible parent solutions (see Part I for a formal definition). The experimental results of M. Yagiura and T. Ibaraki [30], C. Cotta, E. Alba and . Troya [8], W. Cook and P. Seymour [6], D. Whitley, D. Hains and A. Howe [29] indicate that optimal recombination may be used successfully in the GAs .

• Toán học
• Genetic Algorithm
• Optimal Recombination Problem
• Permutation problems
• Travelling salesman problem
• Shortest Hamilton Path Problem
• Makespan Minimization
• Solving uncapacitated multiple allocation p hub center problem
• Dijkstra’s algorithm based genetic algorithm and simulated annealing
• Dijkstra’s algorithm based genetic algorithm
• Large scale standard data sets
• P hub center problem
• International Journal of computer science & communication networks
• Anomaly detection using genetic
• SVM algorithm in data mining
• Algorithm in data mining
• K mean algorithm
• Two algorithm genetic and SVM
• Performance analysis of a sugar plant using genetic algorithm
• Optimization of crystallization system of a sugar plant using genetic algorithm
• A sugar plant using genetic algorithm
• Refining system fails
• The crystallization system includes crystallization units
• International Journal of Computer Networks and Communications Security
• Hybrid of genetic algorithm
• Continuous ant colony optimization for optimum solution
• Combining genetic algorithm
• The new hybrid algorithm
• Journal of Computer Science and Cybernetics
• Improved genetic algorithm
• Test data generation for simulink models
• Conventional genetic algorithm
• Generate test data for Simulink models
• Vietnam Journal of Mechanics
• The genetic algorithm
• The consequential convex approximation programming
• Composite structure optimization
• Linear elastic fiber reinforced composite laminate
• Survey on cloud computing steganography using genetic algorithm
• Cloud computing steganography using genetic algorithm
• Cloud computing steganography
• Protect stored data
• Bi objective optimization
• Integrated forward/reverse logistic network
• Non dominated sorting genetic algorithm II
• Bi objective freight scheduling optimization
• Bài giảng Máy học nâng cao
• Máy học nâng cao
• Genetic algorithm operators and parameters Working mechanism
• Successive Zooming
• Network Operator
• Mathematical Equation
• Solving a multi objective location routing problem
• Infectious waste disposal
• Hybrid goal programming and hybrid genetic algorithm
• Hybrid goal programming
• Hybrid genetic algorithm
• Portfolio optimization
• Objective function
• Artificial intelligence methods
• Portfolio selection using genetic algorithm
• Evolutionary computation
• Fleet sizing problem
• Time windows using genetic algorithm
• Differential evolution algorithm
• Fuel reloading optimization
• Nuclear reactor
• Meta heuristic approaches
• A genetic algorithm for preemptive scheduling of a single machine
• Preemptive scheduling of a single machine
• Large scale problems
• A genetic algorithm
• Boolean Linear Programming
• Optimal recombination
• BMC Bioinformatics
• Genetic code adaptability
• Evolutionary computing
• Fitness sharing
• Ensemble learning
• Co evolution algorithm
• Feature selection
• Ensemble learning algorithm to produce
• A new Approach to Improving Multilingual Summarization
• a Genetic Algorithm
• Marina Litvak Ben Gurion
• báo cáo khoa học
• báo cáo ngôn ngữ
• ngôn ngữ tự nhiên
• TSP solver using genetic algorithm
• The outline of the GA for TSP
• Mutation by 2 opt
• Crossover operator
• Greedy Subtour Crossover
• Survivor Selection
• Other parameters
• Method for university course timetabling problems
• Application in Hanoi open university
• University course timetabling
• P hub maximal covering problem
• Binary coverage
• r allocation strategy
• DHL services
• Supply chains
• Possibility measures
• Time value of money
• Necessity measures
• Rented warehouse
• Piezoelectric laminated composite plate using genetic algorithm
• The generalized displacements
• Piezoelectric laminated composite plate
• The piezoelectric actuator efficiency
• Requirements based upon quality approach
• Interactive genetic algorithm focussed on agile methodologies
• The successive releases of the system