Commenced in January 2007
Frequency: Monthly
Edition: International
Paper Count: 5

permutation Related Publications

5 BeamGA Median: A Hybrid Heuristic Search Approach

Authors: Ghada Badr, Manar Hosny, Nuha Bintayyash, Eman Albilali, Souad Larabi Marie-Sainte


The median problem is significantly applied to derive the most reasonable rearrangement phylogenetic tree for many species. More specifically, the problem is concerned with finding a permutation that minimizes the sum of distances between itself and a set of three signed permutations. Genomes with equal number of genes but different order can be represented as permutations. In this paper, an algorithm, namely BeamGA median, is proposed that combines a heuristic search approach (local beam) as an initialization step to generate a number of solutions, and then a Genetic Algorithm (GA) is applied in order to refine the solutions, aiming to achieve a better median with the smallest possible reversal distance from the three original permutations. In this approach, any genome rearrangement distance can be applied. In this paper, we use the reversal distance. To the best of our knowledge, the proposed approach was not applied before for solving the median problem. Our approach considers true biological evolution scenario by applying the concept of common intervals during the GA optimization process. This allows us to imitate a true biological behavior and enhance genetic approach time convergence. We were able to handle permutations with a large number of genes, within an acceptable time performance and with same or better accuracy as compared to existing algorithms.

Keywords: Genetic Algorithm, Phylogenetic Tree, beam search, median problem, permutation, genome rearrangement distance

Procedia APA BibTeX Chicago EndNote Harvard JSON MLA RIS XML ISO 690 PDF Downloads 659
4 New Scheme in Determining nth Order Diagrams for Cross Multiplication Method via Combinatorial Approach

Authors: Sharmila Karim, Haslinda Ibrahim, Zurni Omar


In this paper, a new recursive strategy is proposed for determining $\frac{(n-1)!}{2}$ of $n$th order diagrams. The generalization of $n$th diagram for cross multiplication method were proposed by Pavlovic and Bankier but the specific rule of determining $\frac{(n-1)!}{2}$ of the $n$th order diagrams for square matrix is yet to be discovered. Thus using combinatorial approach, $\frac{(n-1)!}{2}$ of the $n$th order diagrams will be presented as $\frac{(n-1)!}{2}$ starter sets. These starter sets will be generated based on exchanging one element. The advantages of this new strategy are the discarding process was eliminated and the sign of starter set is alternated to each others.

Keywords: Determinant, permutation, starter sets, exchanging one element

Procedia APA BibTeX Chicago EndNote Harvard JSON MLA RIS XML ISO 690 PDF Downloads 910
3 An Algorithm of Finite Capacity Material Requirement Planning System for Multi-stage Assembly Flow Shop

Authors: T. Wuttipornpun, U. Wangrakdiskul, W. Songserm


This paper aims to develop an algorithm of finite capacity material requirement planning (FCMRP) system for a multistage assembly flow shop. The developed FCMRP system has two main stages. The first stage is to allocate operations to the first and second priority work centers and also determine the sequence of the operations on each work center. The second stage is to determine the optimal start time of each operation by using a linear programming model. Real data from a factory is used to analyze and evaluate the effectiveness of the proposed FCMRP system and also to guarantee a practical solution to the user. There are five performance measures, namely, the total tardiness, the number of tardy orders, the total earliness, the number of early orders, and the average flow-time. The proposed FCMRP system offers an adjustable solution which is a compromised solution among the conflicting performance measures. The user can adjust the weight of each performance measure to obtain the desired performance. The result shows that the combination of FCMRP NP3 and EDD outperforms other combinations in term of overall performance index. The calculation time for the proposed FCMRP system is about 10 minutes which is practical for the planners of the factory.

Keywords: Linear Programming, application in industry, permutation, Material requirement planning, Finite capacity

Procedia APA BibTeX Chicago EndNote Harvard JSON MLA RIS XML ISO 690 PDF Downloads 2009
2 A New Image Encryption Approach using Combinational Permutation Techniques

Authors: A. Mitra, Y. V. Subba Rao, S. R. M. Prasanna


This paper proposes a new approach for image encryption using a combination of different permutation techniques. The main idea behind the present work is that an image can be viewed as an arrangement of bits, pixels and blocks. The intelligible information present in an image is due to the correlations among the bits, pixels and blocks in a given arrangement. This perceivable information can be reduced by decreasing the correlation among the bits, pixels and blocks using certain permutation techniques. This paper presents an approach for a random combination of the aforementioned permutations for image encryption. From the results, it is observed that the permutation of bits is effective in significantly reducing the correlation thereby decreasing the perceptual information, whereas the permutation of pixels and blocks are good at producing higher level security compared to bit permutation. A random combination method employing all the three techniques thus is observed to be useful for tactical security applications, where protection is needed only against a casual observer.

Keywords: Encryption, permutation, Good key, Combinationalpermutation, Pseudo random index generator

Procedia APA BibTeX Chicago EndNote Harvard JSON MLA RIS XML ISO 690 PDF Downloads 1923
1 Two-Stage Approach for Solving the Multi-Objective Optimization Problem on Combinatorial Configurations

Authors: Liudmyla Koliechkina, Olena Dvirna


The statement of the multi-objective optimization problem on combinatorial configurations is formulated, and the approach to its solution is proposed. The problem is of interest as a combinatorial optimization one with many criteria, which is a model of many applied tasks. The approach to solving the multi-objective optimization problem on combinatorial configurations consists of two stages; the first is the reduction of the multi-objective problem to the single criterion based on existing multi-objective optimization methods, the second stage solves the directly replaced single criterion combinatorial optimization problem by the horizontal combinatorial method. This approach provides the optimal solution to the multi-objective optimization problem on combinatorial configurations, taking into account additional restrictions for a finite number of steps.

Keywords: Multi-objective optimization, Pareto solutions, permutation, discrete set, linear combinatorial optimization, partial permutation set, structural graph, multipermutation

Procedia APA BibTeX Chicago EndNote Harvard JSON MLA RIS XML ISO 690 PDF Downloads 118