Abstract: The equivalence class subset algorithm is a powerful
tool for solving a wide variety of constraint satisfaction problems and
is based on the use of a decision function which has a very high but
not perfect accuracy. Perfect accuracy is not required in the decision
function as even a suboptimal solution contains valuable information
that can be used to help find an optimal solution. In the hardest
problems, the decision function can break down leading to a
suboptimal solution where there are more equivalence classes than
are necessary and which can be viewed as a mixture of good decision
and bad decisions. By choosing a subset of the decisions made in
reaching a suboptimal solution an iterative technique can lead to an
optimal solution, using series of steadily improved suboptimal
solutions. The goal is to reach an optimal solution as quickly as
possible. Various techniques for choosing the decision subset are
evaluated.
Abstract: In this paper, multi-processors job shop scheduling problems are solved by a heuristic algorithm based on the hybrid of priority dispatching rules according to an ant colony optimization algorithm. The objective function is to minimize the makespan, i.e. total completion time, in which a simultanous presence of various kinds of ferons is allowed. By using the suitable hybrid of priority dispatching rules, the process of finding the best solution will be improved. Ant colony optimization algorithm, not only promote the ability of this proposed algorithm, but also decreases the total working time because of decreasing in setup times and modifying the working production line. Thus, the similar work has the same production lines. Other advantage of this algorithm is that the similar machines (not the same) can be considered. So, these machines are able to process a job with different processing and setup times. According to this capability and from this algorithm evaluation point of view, a number of test problems are solved and the associated results are analyzed. The results show a significant decrease in throughput time. It also shows that, this algorithm is able to recognize the bottleneck machine and to schedule jobs in an efficient way.
Abstract: Economic Load Dispatch (ELD) is a method of determining
the most efficient, low-cost and reliable operation of a power
system by dispatching available electricity generation resources to
supply load on the system. The primary objective of economic
dispatch is to minimize total cost of generation while honoring
operational constraints of available generation resources. In this paper
an intelligent water drop (IWD) algorithm has been proposed to
solve ELD problem with an objective of minimizing the total cost of
generation. Intelligent water drop algorithm is a swarm-based natureinspired
optimization algorithm, which has been inspired from natural
rivers. A natural river often finds good paths among lots of possible
paths in its ways from source to destination and finally find almost
optimal path to their destination. These ideas are embedded into
the proposed algorithm for solving economic load dispatch problem.
The main advantage of the proposed technique is easy is implement
and capable of finding feasible near global optimal solution with
less computational effort. In order to illustrate the effectiveness of
the proposed method, it has been tested on 6-unit and 20-unit test
systems with incremental fuel cost functions taking into account the
valve point-point loading effects. Numerical results shows that the
proposed method has good convergence property and better in quality
of solution than other algorithms reported in recent literature.
Abstract: As far as the latest technological improvements are concerned, digital systems more become popular than the past. Despite this growing demand to the digital systems, content copy and attack against the digital cinema contents becomes a serious problem. To solve the above security problem, we propose “traceable watermarking using Hash functions for digital cinema system. Digital Cinema is a great application for traceable watermarking since it uses watermarking technology during content play as well as content transmission. The watermark is embedded into the randomly selected movie frames using CRC-32 techniques. CRC-32 is a Hash function. Using it, the embedding position is distributed by Hash Function so that any party cannot break off the watermarking or will not be able to change. Finally, our experimental results show that proposed DWT watermarking method using CRC-32 is much better than the convenient watermarking techniques in terms of robustness, image quality and its simple but unbreakable algorithm.
Abstract: This paper presents an approach for the design of
fuzzy logic power system stabilizers using genetic algorithms. In the
proposed fuzzy expert system, speed deviation and its derivative
have been selected as fuzzy inputs. In this approach the parameters of
the fuzzy logic controllers have been tuned using genetic algorithm.
Incorporation of GA in the design of fuzzy logic power system
stabilizer will add an intelligent dimension to the stabilizer and
significantly reduces computational time in the design process. It is
shown in this paper that the system dynamic performance can be
improved significantly by incorporating a genetic-based searching
mechanism. To demonstrate the robustness of the genetic based
fuzzy logic power system stabilizer (GFLPSS), simulation studies on
multimachine system subjected to small perturbation and three-phase
fault have been carried out. Simulation results show the superiority
and robustness of GA based power system stabilizer as compare to
conventionally tuned controller to enhance system dynamic
performance over a wide range of operating conditions.
Abstract: Graph partitioning is a NP-hard problem with multiple
conflicting objectives. The graph partitioning should minimize the
inter-partition relationship while maximizing the intra-partition
relationship. Furthermore, the partition load should be evenly
distributed over the respective partitions. Therefore this is a multiobjective
optimization problem (MOO). One of the approaches to
MOO is Pareto optimization which has been used in this paper. The
proposed methods of this paper used to improve the performance are
injecting best solutions of previous runs into the first generation of
next runs and also storing the non-dominated set of previous
generations to combine with later generation's non-dominated set.
These improvements prevent the GA from getting stuck in the local
optima and increase the probability of finding more optimal
solutions. Finally, a simulation research is carried out to investigate
the effectiveness of the proposed algorithm. The simulation results
confirm the effectiveness of the proposed method.
Abstract: An effort to develop a unit commitment approach
capable of handling large power systems consisting of both thermal
and hydro generating units offers a large profitable return. In order to
be feasible, the method to be developed must be flexible, efficient
and reliable. In this paper, various proposed methods have been
described along with their strengths and weaknesses. As all of these
methods have some sort of weaknesses, a comprehensive algorithm
that combines the strengths of different methods and overcomes each
other-s weaknesses would be a suitable approach for solving
industry-grade unit commitment problem.
Abstract: The Minimum Weighted Vertex Cover (MWVC) problem is a classic graph optimization NP - complete problem. Given an undirected graph G = (V, E) and weighting function defined on the vertex set, the minimum weighted vertex cover problem is to find a vertex set S V whose total weight is minimum subject to every edge of G has at least one end point in S. In this paper an effective algorithm, called Support Ratio Algorithm (SRA), is designed to find the minimum weighted vertex cover of a graph. Computational experiments are designed and conducted to study the performance of our proposed algorithm. Extensive simulation results show that the SRA can yield better solutions than other existing algorithms found in the literature for solving the minimum vertex cover problem.
Abstract: In this paper, by introducing twice continuously differentiable mappings, we develop an interior path following following method, which enables us to give a constructive proof of the general Brouwer fixed point theorem and thus to solve fixed point problems in a class of non-convex sets. Under suitable conditions, a smooth path can be proven to exist. This can lead to an implementable globally convergent algorithm. Several numerical examples are given to illustrate the results of this paper.
Abstract: The overall objective of this paper is to retrieve soil
surfaces parameters namely, roughness and soil moisture related to
the dielectric constant by inverting the radar backscattered signal
from natural soil surfaces.
Because the classical description of roughness using statistical
parameters like the correlation length doesn't lead to satisfactory
results to predict radar backscattering, we used a multi-scale
roughness description using the wavelet transform and the Mallat
algorithm. In this description, the surface is considered as a
superposition of a finite number of one-dimensional Gaussian
processes each having a spatial scale. A second step in this study
consisted in adapting a direct model simulating radar backscattering
namely the small perturbation model to this multi-scale surface
description. We investigated the impact of this description on radar
backscattering through a sensitivity analysis of backscattering
coefficient to the multi-scale roughness parameters.
To perform the inversion of the small perturbation multi-scale
scattering model (MLS SPM) we used a multi-layer neural network
architecture trained by backpropagation learning rule. The inversion
leads to satisfactory results with a relative uncertainty of 8%.
Abstract: In this paper a new cost function for blind equalization
is proposed. The proposed cost function, referred to as the modified
maximum normalized cumulant criterion (MMNC), is an extension
of the previously proposed maximum normalized cumulant criterion
(MNC). While the MNC requires a separate phase recovery system
after blind equalization, the MMNC performs joint blind equalization
and phase recovery. To achieve this, the proposed algorithm
maximizes a cost function that considers both amplitude and phase of
the equalizer output. The simulation results show that the proposed
algorithm has an improved channel equalization effect than the MNC
algorithm and simultaneously can correct the phase error that the
MNC algorithm is unable to do. The simulation results also show that
the MMNC algorithm has lower complexity than the MNC algorithm.
Moreover, the MMNC algorithm outperforms the MNC algorithm
particularly when the symbols block size is small.
Abstract: In this paper, we propose APO, a new packet scheduling
scheme with Quality of Service (QoS) support for hybrid of
real and non-real time services in HSDPA networks. The APO
scheduling algorithm is based on the effective channel anticipation
model. In contrast to the traditional schemes, the proposed method is
implemented based on a cyclic non-work-conserving discipline.
Simulation results indicated that proposed scheme has good
capability to maximize the channel usage efficiency in compared to
another exist scheduling methods. Simulation results demonstrate the
effectiveness of the proposed algorithm.
Abstract: This paper presents a hybrid algorithm for solving a timetabling problem, which is commonly encountered in many universities. The problem combines both teacher assignment and course scheduling problems simultaneously, and is presented as a mathematical programming model. However, this problem becomes intractable and it is unlikely that a proven optimal solution can be obtained by an integer programming approach, especially for large problem instances. A hybrid algorithm that combines an integer programming approach, a greedy heuristic and a modified simulated annealing algorithm collaboratively is proposed to solve the problem. Several randomly generated data sets of sizes comparable to that of an institution in Indonesia are solved using the proposed algorithm. Computational results indicate that the algorithm can overcome difficulties of large problem sizes encountered in previous related works.
Abstract: This work presents a recursive identification algorithm. This algorithm relates to the identification of closed loop system with Variable Structure Controller. The approach suggested includes two stages. In the first stage a genetic algorithm is used to obtain the parameters of switching function which gives a control signal rich in commutations (i.e. a control signal whose spectral characteristics are closest possible to those of a white noise signal). The second stage consists in the identification of the system parameters by the instrumental variable method and using the optimal switching function parameters obtained with the genetic algorithm. In order to test the validity of this algorithm a simulation example is presented.
Abstract: We constructed a method of noise reduction for
JPEG-compressed image based on Bayesian inference using the
maximizer of the posterior marginal (MPM) estimate. In this method,
we tried the MPM estimate using two kinds of likelihood, both of
which enhance grayscale images converted into the JPEG-compressed
image through the lossy JPEG image compression. One is the
deterministic model of the likelihood and the other is the probabilistic
one expressed by the Gaussian distribution. Then, using the Monte
Carlo simulation for grayscale images, such as the 256-grayscale
standard image “Lena" with 256 × 256 pixels, we examined the
performance of the MPM estimate based on the performance measure
using the mean square error. We clarified that the MPM estimate via
the Gaussian probabilistic model of the likelihood is effective for
reducing noises, such as the blocking artifacts and the mosquito noise,
if we set parameters appropriately. On the other hand, we found that
the MPM estimate via the deterministic model of the likelihood is not
effective for noise reduction due to the low acceptance ratio of the
Metropolis algorithm.
Abstract: Automated discovery of Rule is, due to its applicability, one of the most fundamental and important method in KDD. It has been an active research area in the recent past. Hierarchical representation allows us to easily manage the complexity of knowledge, to view the knowledge at different levels of details, and to focus our attention on the interesting aspects only. One of such efficient and easy to understand systems is Hierarchical Production rule (HPRs) system. A HPR, a standard production rule augmented with generality and specificity information, is of the following form: Decision If < condition> Generality Specificity . HPRs systems are capable of handling taxonomical structures inherent in the knowledge about the real world. This paper focuses on the issue of mining Quantified rules with crisp hierarchical structure using Genetic Programming (GP) approach to knowledge discovery. The post-processing scheme presented in this work uses Quantified production rules as initial individuals of GP and discovers hierarchical structure. In proposed approach rules are quantified by using Dempster Shafer theory. Suitable genetic operators are proposed for the suggested encoding. Based on the Subsumption Matrix(SM), an appropriate fitness function is suggested. Finally, Quantified Hierarchical Production Rules (HPRs) are generated from the discovered hierarchy, using Dempster Shafer theory. Experimental results are presented to demonstrate the performance of the proposed algorithm.
Abstract: Self-organizing map (SOM) is a well known data reduction technique used in data mining. Data visualization can reveal structure in data sets that is otherwise hard to detect from raw data alone. However, interpretation through visual inspection is prone to errors and can be very tedious. There are several techniques for the automatic detection of clusters of code vectors found by SOMs, but they generally do not take into account the distribution of code vectors; this may lead to unsatisfactory clustering and poor definition of cluster boundaries, particularly where the density of data points is low. In this paper, we propose the use of a generic particle swarm optimization (PSO) algorithm for finding cluster boundaries directly from the code vectors obtained from SOMs. The application of our method to unlabeled call data for a mobile phone operator demonstrates its feasibility. PSO algorithm utilizes U-matrix of SOMs to determine cluster boundaries; the results of this novel automatic method correspond well to boundary detection through visual inspection of code vectors and k-means algorithm.
Abstract: This paper describes the pipeline architecture of
high-speed modified Booth multipliers. The proposed multiplier
circuits are based on the modified Booth algorithm and the pipeline
technique which are the most widely used to accelerate the
multiplication speed. In order to implement the optimally pipelined
multipliers, many kinds of experiments have been conducted. The
speed of the multipliers is greatly improved by properly deciding the
number of pipeline stages and the positions for the pipeline registers to
be inserted. We described the proposed modified Booth multiplier
circuits in Verilog HDL and synthesized the gate-level circuits using
0.13um standard cell library. The resultant multiplier circuits show
better performance than others. Since the proposed multipliers operate
at GHz ranges, they can be used in the systems requiring very high
performance.
Abstract: Matching algorithms have significant importance in
speaker recognition. Feature vectors of the unknown utterance are
compared to feature vectors of the modeled speakers as a last step in
speaker recognition. A similarity score is found for every model in
the speaker database. Depending on the type of speaker recognition,
these scores are used to determine the author of unknown speech
samples. For speaker verification, similarity score is tested against a
predefined threshold and either acceptance or rejection result is
obtained. In the case of speaker identification, the result depends on
whether the identification is open set or closed set. In closed set
identification, the model that yields the best similarity score is
accepted. In open set identification, the best score is tested against a
threshold, so there is one more possible output satisfying the
condition that the speaker is not one of the registered speakers in
existing database. This paper focuses on closed set speaker
identification using a modified version of a well known matching
algorithm. The results of new matching algorithm indicated better
performance on YOHO international speaker recognition database.
Abstract: In this paper we propose a new approach to constructing the Delaunay Triangulation and the optimum algorithm for the case of multidimensional spaces (d ≥ 2). Analysing the modern state, it is possible to draw a conclusion, that the ideas for the existing effective algorithms developed for the case of d ≥ 2 are not simple to generalize on a multidimensional case, without the loss of efficiency. We offer for the solving this problem an effective algorithm that satisfies all the given requirements. But theoretical complexity of the problem it is impossible to improve as the Worst - Case Optimality for algorithms of solving such a problem is proved.