42

10007366

BeamGA Median: A Hybrid Heuristic Search Approach

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.

41

10006733

A Genetic Algorithm Based Permutation and Non-Permutation Scheduling Heuristics for Finite Capacity Material Requirement Planning Problem

This paper presents a genetic algorithm based permutation and non-permutation scheduling heuristics (GAPNP) to solve a multi-stage finite capacity material requirement planning (FCMRP) problem in automotive assembly flow shop with unrelated parallel machines. In the algorithm, the sequences of orders are iteratively improved by the GA characteristics, whereas the required operations are scheduled based on the presented permutation and non-permutation heuristics. Finally, a linear programming is applied to minimize the total cost. The presented GAPNP algorithm is evaluated by using real datasets from automotive companies. The required parameters for GAPNP are intently tuned to obtain a common parameter setting for all case studies. The results show that GAPNP significantly outperforms the benchmark algorithm about 30% on average.

40

10006471

Combinatory Nutrition Supplementation: A Case of Synergy for Increasing Calcium Bioavailability

This paper presents an overview of how calcium interacts with the various essential nutrients within an environment of cellular and hormonal interactions for the purpose of increasing bioavailability to the human body. One example of such interactions can be illustrated with calcium homeostasis. This paper gives an in-depth discussion on the possible interactive permutations with various nutrients and factors leading to the promotion of calcium bioavailability to the body. The review hopes to provide further insights into how calcium supplement formulations can be improved to better influence its bioavailability in the human body.

39

10005307

Tree Based Data Fusion Clustering Routing Algorithm for Illimitable Network Administration in Wireless Sensor Network

In wireless sensor networks, locality and positioning information can be captured using Global Positioning System (GPS). This message can be congregated initially from spot to identify the system. Users can retrieve information of interest from a wireless sensor network (WSN) by injecting queries and gathering results from the mobile sink nodes. Routing is the progression of choosing optimal path in a mobile network. Intermediate node employs permutation of device nodes into teams and generating cluster heads that gather the data from entity cluster’s node and encourage the collective data to base station. WSNs are widely used for gathering data. Since sensors are power-constrained devices, it is quite vital for them to reduce the power utilization. A tree-based data fusion clustering routing algorithm (TBDFC) is used to reduce energy consumption in wireless device networks. Here, the nodes in a tree use the cluster formation, whereas the elevation of the tree is decided based on the distance of the member nodes to the cluster-head. Network simulation shows that this scheme improves the power utilization by the nodes, and thus considerably improves the lifetime.

38

10003837

Assessment of Multiscale Information for Short Physiological Time Series

This paper presents a multiscale information measure of
Electroencephalogram (EEG) for analysis with a short data length.
A multiscale extension of permutation entropy (MPE) is capable of
fully reflecting the dynamical characteristics of EEG across different
temporal scales. However, MPE yields an imprecise estimation due
to coarse-grained procedure at large scales. We present an improved
MPE measure to estimate entropy more accurately with a short
time series. By computing entropies of all coarse-grained time series
and averaging those at each scale, it leads to the modified MPE
(MMPE) which provides an enhanced accuracy as compared to
MPE. Simulation and experimental studies confirmed that MMPE
has proved its capability over MPE in terms of accuracy.

37

10002423

A General Variable Neighborhood Search Algorithm to Minimize Makespan of the Distributed Permutation Flowshop Scheduling Problem

This paper addresses minimizing the makespan of the
distributed permutation flow shop scheduling problem. In this
problem, there are several parallel identical factories or flowshops
each with series of similar machines. Each job should be allocated to
one of the factories and all of the operations of the jobs should be
performed in the allocated factory. This problem has recently gained
attention and due to NP-Hard nature of the problem, metaheuristic
algorithms have been proposed to tackle it. Majority of the proposed
algorithms require large computational time which is the main
drawback. In this study, a general variable neighborhood search
algorithm (GVNS) is proposed where several time-saving schemes
have been incorporated into it. Also, the GVNS uses the sophisticated
method to change the shaking procedure or perturbation depending
on the progress of the incumbent solution to prevent stagnation of the
search. The performance of the proposed algorithm is compared to
the state-of-the-art algorithms based on standard benchmark
instances.

36

10001355

Deterministic Random Number Generator Algorithm for Cryptosystem Keys

One of the crucial parameters of digital cryptographic
systems is the selection of the keys used and their distribution. The
randomness of the keys has a strong impact on the system’s security
strength being difficult to be predicted, guessed, reproduced, or
discovered by a cryptanalyst. Therefore, adequate key randomness
generation is still sought for the benefit of stronger cryptosystems.
This paper suggests an algorithm designed to generate and test
pseudo random number sequences intended for cryptographic
applications. This algorithm is based on mathematically manipulating
a publically agreed upon information between sender and receiver
over a public channel. This information is used as a seed for
performing some mathematical functions in order to generate a
sequence of pseudorandom numbers that will be used for
encryption/decryption purposes. This manipulation involves
permutations and substitutions that fulfill Shannon’s principle of
“confusion and diffusion”. ASCII code characters were utilized in the
generation process instead of using bit strings initially, which adds
more flexibility in testing different seed values. Finally, the obtained
results would indicate sound difficulty of guessing keys by attackers.

35

10005234

Real-Time Image Encryption Using a 3D Discrete Dual Chaotic Cipher

In this paper, an encryption algorithm is proposed for real-time image encryption. The scheme employs a dual chaotic generator based on a three dimensional (3D) discrete Lorenz attractor. Encryption is achieved using non-autonomous modulation where the data is injected into the dynamics of the master chaotic generator. The second generator is used to permute the dynamics of the master generator using the same approach. Since the data stream can be regarded as a random source, the resulting permutations of the generator dynamics greatly increase the security of the transmitted signal. In addition, a technique is proposed to mitigate the error propagation due to the finite precision arithmetic of digital hardware. In particular, truncation and rounding errors are eliminated by employing an integer representation of the data which can easily be implemented. The simple hardware architecture of the algorithm makes it suitable for secure real-time applications.

34

9998142

An Efficient Separation for Convolutive Mixtures

This paper describes a new efficient blind source separation method; in this method we uses a non-uniform filter bank and a new structure with different sub-bands. This method provides a reduced permutation and increased convergence speed comparing to the full-band algorithm. Recently, some structures have been suggested to deal with two problems: reducing permutation and increasing the speed of convergence of the adaptive algorithm for correlated input signals. The permutation problem is avoided with the use of adaptive filters of orders less than the full-band adaptive filter, which operate at a sampling rate lower than the sampling rate of the input signal. The decomposed signals by analysis bank filter are less correlated in each sub-band than the input signal at full-band, and can promote better rates of convergence.

33

9998250

An Improved Ant Colony Algorithm for Genome Rearrangements

Genome rearrangement is an important area in computational biology and bioinformatics. The basic problem in genome rearrangements is to compute the edit distance, i.e., the minimum number of operations needed to transform one genome into another. Unfortunately, unsigned genome rearrangement problem is NP-hard. In this study an improved ant colony optimization algorithm to approximate the edit distance is proposed. The main idea is to convert the unsigned permutation to signed permutation and evaluate the ants by using Kaplan algorithm. Two new operations are added to the standard ant colony algorithm: Replacing the worst ants by re-sampling the ants from a new probability distribution and applying the crossover operations on the best ants. The proposed algorithm is tested and compared with the improved breakpoint reversal sort algorithm by using three datasets. The results indicate that the proposed algorithm achieves better accuracy ratio than the previous methods.

32

9998281

Applying Sequential Pattern Mining to Generate Block for Scheduling Problems

The main idea in this paper is using sequential pattern mining to find the information which is helpful for finding high performance solutions. By combining this information, it is defined as blocks. Using the blocks to generate artificial chromosomes (ACs) could improve the structure of solutions. Estimation of Distribution Algorithms (EDAs) is adapted to solve the combinatorial problems. Nevertheless many of these approaches are advantageous for this application, but only some of them are used to enhance the efficiency of application. Generating ACs uses patterns and EDAs could increase the diversity. According to the experimental result, the algorithm which we proposed has a better performance to solve the permutation flow-shop problems.

31

9997666

System Reduction by Eigen Permutation Algorithm and Improved Pade Approximations

A mixed method by combining a Eigen algorithm and improved pade approximations is proposed for reducing the order of the large-scale dynamic systems. The most dominant Eigen value of both original and reduced order systems remain same in this method. The proposed method guarantees stability of the reduced model if the original high-order system is stable and is comparable in quality with the other well known existing order reduction methods. The superiority of the proposed method is shown through examples taken from the literature.

30

7673

On the Wreath Product of Group by Some Other Groups

In this paper, we will generate the wreath product
11 12 M wrM using only two permutations. Also, we will show the
structure of some groups containing the wreath product 11 12 M wrM .
The structure of the groups founded is determined in terms of wreath
product k (M wrM ) wrC 11 12 . Some related cases are also included.
Also, we will show that 132K+1 S and 132K+1 A can be generated
using the wreath product k (M wrM ) wrC 11 12 and a transposition in
132K+1 S and an element of order 3 in 132K+1 A . We will also show
that 132K+1 S and 132K+1 A can be generated using the wreath
product 11 12 M wrM and an element of order k +1.

29

3038

Using Fractional Factorial Designs for Variable Importance in Random Forest Models

Random Forests are a powerful classification technique, consisting of a collection of decision trees. One useful feature of Random Forests is the ability to determine the importance of each variable in predicting the outcome. This is done by permuting each variable and computing the change in prediction accuracy before and after the permutation. This variable importance calculation is similar to a one-factor-at a time experiment and therefore is inefficient. In this paper, we use a regular fractional factorial design to determine which variables to permute. Based on the results of the trials in the experiment, we calculate the individual importance of the variables, with improved precision over the standard method. The method is illustrated with a study of student attrition at Monash University.

28

6457

The Design of Self-evolving Artificial Immune System II for Permutation Flow-shop Problem

Artificial Immune System is adopted as a Heuristic
Algorithm to solve the combinatorial problems for decades.
Nevertheless, many of these applications took advantage of the benefit
for applications but seldom proposed approaches for enhancing the
efficiency. In this paper, we continue the previous research to develop
a Self-evolving Artificial Immune System II via coordinating the T
and B cell in Immune System and built a block-based artificial
chromosome for speeding up the computation time and better
performance for different complexities of problems. Through the
design of Plasma cell and clonal selection which are relative the
function of the Immune Response. The Immune Response will help
the AIS have the global and local searching ability and preventing
trapped in local optima. From the experimental result, the significant
performance validates the SEAIS II is effective when solving the
permutation flows-hop problems.

27

6073

A Particle Swarm Optimization Approach for the Earliness-Tardiness No-Wait Flowshop Scheduling Problem

In this researcha particle swarm optimization (PSO)
algorithm is proposedfor no-wait flowshopsequence dependent
setuptime scheduling problem with weighted earliness-tardiness
penalties as the criterion (|,
|Σ
"
).The
smallestposition value (SPV) rule is applied to convert the continuous
value of position vector of particles in PSO to job permutations.A
timing algorithm is generated to find the optimal schedule and
calculate the objective function value of a given sequence in PSO
algorithm. Twodifferent neighborhood structures are applied to
improve the solution quality of PSO algorithm.The first one is based
on variable neighborhood search (VNS) and the second one is a
simple one with invariable structure. In order to compare the
performance of two neighborhood structures, random test problems
are generated and solved by both neighborhood
approaches.Computational results show that the VNS algorithmhas
better performance than the other one especially for the large sized
problems.

26

6772

A Hybrid Genetic Algorithm for the Sequence Dependent Flow-Shop Scheduling Problem

Flow-shop scheduling problem (FSP) deals with the
scheduling of a set of jobs that visit a set of machines in the same
order. The FSP is NP-hard, which means that an efficient algorithm
for solving the problem to optimality is unavailable. To meet the
requirements on time and to minimize the make-span performance of
large permutation flow-shop scheduling problems in which there are
sequence dependent setup times on each machine, this paper
develops one hybrid genetic algorithms (HGA). Proposed HGA
apply a modified approach to generate population of initial
chromosomes and also use an improved heuristic called the iterated
swap procedure to improve initial solutions. Also the author uses
three genetic operators to make good new offspring. The results are
compared to some recently developed heuristics and computational
experimental results show that the proposed HGA performs very
competitively with respect to accuracy and efficiency of solution.

25

12156

New Scheme in Determining nth Order Diagrams for Cross Multiplication Method via Combinatorial Approach

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.

24

11363

An Efficient Ant Colony Optimization Algorithm for Multiobjective Flow Shop Scheduling Problem

In this paper an ant colony optimization algorithm is
developed to solve the permutation flow shop scheduling problem. In
the permutation flow shop scheduling problem which has been vastly
studied in the literature, there are a set of m machines and a set of n
jobs. All the jobs are processed on all the machines and the sequence
of jobs being processed is the same on all the machines. Here this
problem is optimized considering two criteria, makespan and total
flow time. Then the results are compared with the ones obtained by
previously developed algorithms. Finally it is visible that our
proposed approach performs best among all other algorithms in the
literature.

23

743

Using Tabu Search to Analyze the Mauritian Economic Sectors

The aim of this paper is to express the input-output
matrix as a linear ordering problem which is classified as an NP-hard
problem. We then use a Tabu search algorithm to find the best
permutation among sectors in the input-output matrix that will give
an optimal solution. This optimal permutation can be useful in
designing policies and strategies for economists and government in
their goal of maximizing the gross domestic product.

22

13722

Blind Source Separation for Convoluted Signals Based on Properties of Acoustic Transfer Function in Real Environments

Frequency domain independent component analysis has
a scaling indeterminacy and a permutation problem. The scaling
indeterminacy can be solved by use of a decomposed spectrum. For
the permutation problem, we have proposed the rules in terms of gain
ratio and phase difference derived from the decomposed spectra and
the source-s coarse directions.
The present paper experimentally clarifies that the gain ratio and
the phase difference work effectively in a real environment but their
performance depends on frequency bands, a microphone-space and
a source-microphone distance. From these facts it is seen that it is
difficult to attain a perfect solution for the permutation problem in a
real environment only by either the gain ratio or the phase difference.
For the perfect solution, this paper gives a solution to the problems
in a real environment. The proposed method is simple, the amount of
calculation is small. And the method has high correction performance
without depending on the frequency bands and distances from source
signals to microphones. Furthermore, it can be applied under the real
environment. From several experiments in a real room, it clarifies
that the proposed method has been verified.

21

6909

An Algorithm of Finite Capacity Material Requirement Planning System for Multi-stage Assembly Flow Shop

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.

20

13384

Self-evolving Artificial Immune System via Developing T and B Cell for Permutation Flow-shop Scheduling Problems

Artificial Immune System is applied as a Heuristic
Algorithm for decades. Nevertheless, many of these applications
took advantage of the benefit of this algorithm but seldom proposed
approaches for enhancing the efficiency. In this paper, a
Self-evolving Artificial Immune System is proposed via developing
the T and B cell in Immune System and built a self-evolving
mechanism for the complexities of different problems. In this
research, it focuses on enhancing the efficiency of Clonal selection
which is responsible for producing Affinities to resist the invading of
Antigens. T and B cell are the main mechanisms for Clonal
Selection to produce different combinations of Antibodies.
Therefore, the development of T and B cell will influence the
efficiency of Clonal Selection for searching better solution.
Furthermore, for better cooperation of the two cells, a co-evolutional
strategy is applied to coordinate for more effective productions of
Antibodies. This work finally adopts Flow-shop scheduling
instances in OR-library to validate the proposed algorithm.

19

3504

A Systematic Approach for Finding Hamiltonian Cycles with a Prescribed Edge in Crossed Cubes

The crossed cube is one of the most notable variations of hypercube, but some properties of the former are superior to those of the latter. For example, the diameter of the crossed cube is almost the half of that of the hypercube. In this paper, we focus on the problem embedding a Hamiltonian cycle through an arbitrary given edge in the crossed cube. We give necessary and sufficient condition for determining whether a given permutation with n elements over Zn generates a Hamiltonian cycle pattern of the crossed cube. Moreover, we obtain a lower bound for the number of different Hamiltonian cycles passing through a given edge in an n-dimensional crossed cube. Our work extends some recently obtained results.

18

15048

Computing SAGB-Gröbner Basis of Ideals of Invariant Rings by Using Gaussian Elimination

The link between Gröbner basis and linear algebra was
described by Lazard [4,5] where he realized the Gr┬¿obner basis
computation could be archived by applying Gaussian elimination over
Macaulay-s matrix .
In this paper, we indicate how same technique may be used to
SAGBI- Gröbner basis computations in invariant rings.

17

9545

A Case Study of Key-Dependent Permutations in Feistel Ciphers

Many attempts have been made to strengthen Feistel based block ciphers. Among the successful proposals is the key- dependent S-box which was implemented in some of the high-profile ciphers. In this paper a key-dependent permutation box is proposed and implemented on DES as a case study. The new modified DES, MDES, was tested against Diehard Tests, avalanche test, and performance test. The results showed that in general MDES is more resistible to attacks than DES with negligible overhead. Therefore, it is believed that the proposed key-dependent permutation should be considered as a valuable primitive that can help strengthen the security of Substitution-Permutation Network which is a core design in many Feistel based block ciphers.

16

11586

Minimal Critical Sets of Inertias for Irreducible Zero-nonzero Patterns of Order 3

If there exists a nonempty, proper subset S of the set of all (n + 1)(n + 2)/2 inertias such that S Ôèå i(A) is sufficient for any n × n zero-nonzero pattern A to be inertially arbitrary, then S is called a critical set of inertias for zero-nonzero patterns of order n. If no proper subset of S is a critical set, then S is called a minimal critical set of inertias. In [3], Kim, Olesky and Driessche identified all minimal critical sets of inertias for 2 × 2 zero-nonzero patterns. Identifying all minimal critical sets of inertias for n × n zero-nonzero patterns with n ≥ 3 is posed as an open question in [3]. In this paper, all minimal critical sets of inertias for 3 × 3 zero-nonzero patterns are identified. It is shown that the sets {(0, 0, 3), (3, 0, 0)}, {(0, 0, 3), (0, 3, 0)}, {(0, 0, 3), (0, 1, 2)}, {(0, 0, 3), (1, 0, 2)}, {(0, 0, 3), (2, 0, 1)} and {(0, 0, 3), (0, 2, 1)} are the only minimal critical sets of inertias for 3 × 3 irreducible zerononzero patterns.

15

5655

A Hamiltonian Decomposition of 5-star

Star graphs are Cayley graphs of symmetric groups of permutations, with transpositions as the generating sets. A star graph is a preferred interconnection network topology to a hypercube for its ability to connect a greater number of nodes with lower degree. However, an attractive property of the hypercube is that it has a Hamiltonian decomposition, i.e. its edges can be partitioned into disjoint Hamiltonian cycles, and therefore a simple routing can be found in the case of an edge failure. The existence of Hamiltonian cycles in Cayley graphs has been known for some time. So far, there are no published results on the much stronger condition of the existence of Hamiltonian decompositions. In this paper, we give a construction of a Hamiltonian decomposition of the star graph 5-star of degree 4, by defining an automorphism for 5-star and a Hamiltonian cycle which is edge-disjoint with its image under the automorphism.

14

1875

A New Knapsack Public-Key Cryptosystem Based on Permutation Combination Algorithm

A new secure knapsack cryptosystem based on the
Merkle-Hellman public key cryptosystem will be proposed in this
paper. Although it is common sense that when the density is low, the
knapsack cryptosystem turns vulnerable to the low-density attack. The
density d of a secure knapsack cryptosystem must be larger than
0.9408 to avoid low-density attack. In this paper, we investigate a
new Permutation Combination Algorithm. By exploiting this
algorithm, we shall propose a novel knapsack public-key cryptosystem.
Our proposed scheme can enjoy a high density to avoid the
low-density attack. The density d can also exceed 0.9408 to avoid
the low-density attack.

13

7584

Low Complexity Multi Mode Interleaver Core for WiMAX with Support for Convolutional Interleaving

A hardware efficient, multi mode, re-configurable
architecture of interleaver/de-interleaver for multiple standards,
like DVB, WiMAX and WLAN is presented. The interleavers
consume a large part of silicon area when implemented by using
conventional methods as they use memories to store permutation
patterns. In addition, different types of interleavers in different
standards cannot share the hardware due to different construction
methodologies. The novelty of the work presented in this paper is
threefold: 1) Mapping of vital types of interleavers including
convolutional interleaver onto a single architecture with flexibility
to change interleaver size; 2) Hardware complexity for channel
interleaving in WiMAX is reduced by using 2-D realization of the
interleaver functions; and 3) Silicon cost overheads reduced by
avoiding the use of small memories. The proposed architecture
consumes 0.18mm2 silicon area for 0.12μm process and can
operate at a frequency of 140 MHz. The reduced complexity helps
in minimizing the memory utilization, and at the same time
provides strong support to on-the-fly computation of permutation
patterns.