Abstract: In this paper, we proposed a new routing protocol for
Unmanned Aerial Vehicles (UAVs) that equipped with directional
antenna. We named this protocol Directional Optimized Link State
Routing Protocol (DOLSR). This protocol is based on the well
known protocol that is called Optimized Link State Routing Protocol
(OLSR). We focused in our protocol on the multipoint relay (MPR)
concept which is the most important feature of this protocol. We
developed a heuristic that allows DOLSR protocol to minimize
the number of the multipoint relays. With this new protocol the
number of overhead packets will be reduced and the End-to-End
delay of the network will also be minimized. We showed through
simulation that our protocol outperformed Optimized Link State
Routing Protocol, Dynamic Source Routing (DSR) protocol and Ad-
Hoc On demand Distance Vector (AODV) routing protocol in
reducing the End-to-End delay and enhancing the overall
throughput. Our evaluation of the previous protocols was based
on the OPNET network simulation tool.
Abstract: In this paper a new robust and efficient algorithm to automatic text extraction from colored book and journal cover sheets is proposed. First, we perform wavelet transform. Next for edge detecting from detail wavelet coefficient, we use dynamic threshold. By blurring approximate coefficients with alternative heuristic thresholding, achieve effective edge,. Afterward, with ROI technique get binary image. Finally text boxes would be extracted with new projection profile.
Abstract: This article proposes a novel Pareto-based multiobjective
meta-heuristic algorithm named non-dominated ranking
genetic algorithm (NRGA) to solve multi-facility location-allocation
problem. In NRGA, a fitness value representing rank is assigned to
each individual of the population. Moreover, two features ranked
based roulette wheel selection including select the fronts and choose
solutions from the fronts, are utilized. The proposed solving
methodology is validated using several examples taken from the
specialized literature. The performance of our approach shows that
NRGA algorithm is able to generate true and well distributed Pareto
optimal solutions.
Abstract: In this paper we have proposed a novel dynamic least cost multicast routing protocol using hybrid genetic algorithm for IP networks. Our protocol finds the multicast tree with minimum cost subject to delay, degree, and bandwidth constraints. The proposed protocol has the following features: i. Heuristic local search function has been devised and embedded with normal genetic operation to increase the speed and to get the optimized tree, ii. It is efficient to handle the dynamic situation arises due to either change in the multicast group membership or node / link failure, iii. Two different crossover and mutation probabilities have been used for maintaining the diversity of solution and quick convergence. The simulation results have shown that our proposed protocol generates dynamic multicast tree with lower cost. Results have also shown that the proposed algorithm has better convergence rate, better dynamic request success rate and less execution time than other existing algorithms. Effects of degree and delay constraints have also been analyzed for the multicast tree interns of search success rate.
Abstract: The article describes a case study on one of Czech
Republic-s manufacturing middle size enterprises (ME), where due to
the European financial crisis, production lines had to be redesigned
and optimized in order to minimize the total costs of the production
of goods. It is considered an optimization problem of minimizing the
total cost of the work load, according to the costs of the possible
locations of the workplaces, with an application of the Greedy
algorithm and a partial analogy to a Set Packing Problem. The
displacement of working tables in a company should be as a one-toone
monotone increasing function in order for the total costs of
production of the goods to be at minimum. We use a heuristic
approach with greedy algorithm for solving this linear optimization
problem, regardless the possible greediness which may appear and
we apply it in a Czech ME.
Abstract: This research deals with a flexible flowshop
scheduling problem with arrival and delivery of jobs in groups and
processing them individually. Due to the special characteristics of
each job, only a subset of machines in each stage is eligible to
process that job. The objective function deals with minimization of
sum of the completion time of groups on one hand and minimization
of sum of the differences between completion time of jobs and
delivery time of the group containing that job (waiting period) on the
other hand. The problem can be stated as FFc / rj , Mj / irreg which
has many applications in production and service industries. A
mathematical model is proposed, the problem is proved to be NPcomplete,
and an effective heuristic method is presented to schedule
the jobs efficiently. This algorithm can then be used within the body
of any metaheuristic algorithm for solving the problem.
Abstract: Scheduling of diversified service requests in
distributed computing is a critical design issue. Cloud is a type of
parallel and distributed system consisting of a collection of
interconnected and virtual computers. It is not only the clusters and
grid but also it comprises of next generation data centers. The paper
proposes an initial heuristic algorithm to apply modified ant colony
optimization approach for the diversified service allocation and
scheduling mechanism in cloud paradigm. The proposed optimization
method is aimed to minimize the scheduling throughput to service all
the diversified requests according to the different resource allocator
available under cloud computing environment.
Abstract: Finding the minimal logical functions has important applications in the design of logical circuits. This task is solved by many different methods but, frequently, they are not suitable for a computer implementation. We briefly summarise the well-known Quine-McCluskey method, which gives a unique procedure of computing and thus can be simply implemented, but, even for simple examples, does not guarantee an optimal solution. Since the Petrick extension of the Quine-McCluskey method does not give a generally usable method for finding an optimum for logical functions with a high number of values, we focus on interpretation of the result of the Quine-McCluskey method and show that it represents a set covering problem that, unfortunately, is an NP-hard combinatorial problem. Therefore it must be solved by heuristic or approximation methods. We propose an approach based on genetic algorithms and show suitable parameter settings.
Abstract: The multiple traveling salesman problem (mTSP) can be used to model many practical problems. The mTSP is more complicated than the traveling salesman problem (TSP) because it requires determining which cities to assign to each salesman, as well as the optimal ordering of the cities within each salesman's tour. Previous studies proposed that Genetic Algorithm (GA), Integer Programming (IP) and several neural network (NN) approaches could be used to solve mTSP. This paper compared the results for mTSP, solved with Genetic Algorithm (GA) and Nearest Neighbor Algorithm (NNA). The number of cities is clustered into a few groups using k-means clustering technique. The number of groups depends on the number of salesman. Then, each group is solved with NNA and GA as an independent TSP. It is found that k-means clustering and NNA are superior to GA in terms of performance (evaluated by fitness function) and computing time.
Abstract: This study considers the problem of determining
operation and maintenance schedules for a containership equipped
with components during its sailing according to a pre-determined
navigation schedule. The operation schedule, which specifies work
time of each component, determines the due-date of each maintenance
activity, and the maintenance schedule specifies the actual start
time of each maintenance activity. The main constraints are component
requirements, workforce availability, working time limitation,
and inter-maintenance time. To represent the problem mathematically,
a mixed integer programming model is developed. Then,
due to the problem complexity, we suggest a heuristic for the objective
of minimizing the sum of earliness and tardiness between the
due-date and the starting time of each maintenance activity. Computational
experiments were done on various test instances and the
results are reported.
Abstract: In this paper, a novel associative memory model will be proposed and applied to memory retrievals based on the conventional continuous time model. The conventional model presents memory capacity is very low and retrieval process easily converges to an equilibrium state which is very different from the stored patterns. Genetic Algorithms is well-known with the capability of global optimal search escaping local optimum on progress to reach a global optimum. Based on the well-known idea of Genetic Algorithms, this work proposes a heuristic rule to make a mutation when the state of the network is trapped in a spurious memory. The proposal heuristic associative memory show the stored capacity does not depend on the number of stored patterns and the retrieval ability is up to ~ 1.
Abstract: Self-organizing map (SOM) is a well known data
reduction technique used in data mining. It can reveal structure in
data sets through data visualization 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 SOM, 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 an adaptive heuristic particle swarm optimization (PSO)
algorithm for finding cluster boundaries directly from the code
vectors obtained from SOM. The application of our method to
several standard data sets demonstrates its feasibility. PSO algorithm
utilizes a so-called U-matrix of SOM to determine cluster boundaries;
the results of this novel automatic method compare very favorably to
boundary detection through traditional algorithms namely k-means
and hierarchical based approach which are normally used to interpret
the output of SOM.
Abstract: This paper discusses a new, systematic approach to
the synthesis of a NP-hard class of non-regenerative Boolean
networks, described by FON[FOFF]={mi}[{Mi}], where for every
mj[Mj]∈{mi}[{Mi}], there exists another mk[Mk]∈{mi}[{Mi}], such
that their Hamming distance HD(mj, mk)=HD(Mj, Mk)=O(n), (where
'n' represents the number of distinct primary inputs). The method
automatically ensures exact minimization for certain important selfdual
functions with 2n-1 points in its one-set. The elements meant for
grouping are determined from a newly proposed weighted incidence
matrix. Then the binary value corresponding to the candidate pair is
correlated with the proposed binary value matrix to enable direct
synthesis. We recommend algebraic factorization operations as a post
processing step to enable reduction in literal count. The algorithm
can be implemented in any high level language and achieves best
cost optimization for the problem dealt with, irrespective of the
number of inputs. For other cases, the method is iterated to
subsequently reduce it to a problem of O(n-1), O(n-2),.... and then
solved. In addition, it leads to optimal results for problems exhibiting
higher degree of adjacency, with a different interpretation of the
heuristic, and the results are comparable with other methods.
In terms of literal cost, at the technology independent stage, the
circuits synthesized using our algorithm enabled net savings over
AOI (AND-OR-Invert) logic, AND-EXOR logic (EXOR Sum-of-
Products or ESOP forms) and AND-OR-EXOR logic by 45.57%,
41.78% and 41.78% respectively for the various problems.
Circuit level simulations were performed for a wide variety of
case studies at 3.3V and 2.5V supply to validate the performance of
the proposed method and the quality of the resulting synthesized
circuits at two different voltage corners. Power estimation was
carried out for a 0.35micron TSMC CMOS process technology. In
comparison with AOI logic, the proposed method enabled mean
savings in power by 42.46%. With respect to AND-EXOR logic, the
proposed method yielded power savings to the tune of 31.88%, while
in comparison with AND-OR-EXOR level networks; average power
savings of 33.23% was obtained.
Abstract: Sensor network applications are often data centric and
involve collecting data from a set of sensor nodes to be delivered
to various consumers. Typically, nodes in a sensor network are
resource-constrained, and hence the algorithms operating in these
networks must be efficient. There may be several algorithms available
implementing the same service, and efficient considerations may
require a sensor application to choose the best suited algorithm. In
this paper, we present a systematic evaluation of a set of algorithms
implementing the data gathering service. We propose a modular
infrastructure for implementing such algorithms in TOSSIM with
separate configurable modules for various tasks such as interest
propagation, data propagation, aggregation, and path maintenance.
By appropriately configuring these modules, we propose a number
of data gathering algorithms, each of which incorporates a different
set of heuristics for optimizing performance. We have performed
comprehensive experiments to evaluate the effectiveness of these
heuristics, and we present results from our experimentation efforts.
Abstract: This paper considers the problem of scheduling maintenance actions for identical aircraft gas turbine engines. Each one of the turbines consists of parts which frequently require replacement. A finite inventory of spare parts is available and all parts are ready for replacement at any time. The inventory consists of both new and refurbished parts. Hence, these parts have different field lives. The goal is to find a replacement part sequencing that maximizes the time that the aircraft will keep functioning before the inventory is replenished. The problem is formulated as an identical parallel machine scheduling problem where the minimum completion time has to be maximized. Two models have been developed. The first one is an optimization model which is based on a 0-1 linear programming formulation, while the second one is an approximate procedure which consists in decomposing the problem into several two-machine subproblems. Each subproblem is optimally solved using the first model. Both models have been implemented using Lingo and have been tested on two sets of randomly generated data with up to 150 parts and 10 turbines. Experimental results show that the optimization model is able to solve only instances with no more than 4 turbines, while the decomposition procedure often provides near-optimal solutions within a maximum CPU time of 3 seconds.
Abstract: In this paper, a heuristic method for simultaneous
rescue robot path-planning and mission scheduling is introduced
based on project management techniques, multi criteria decision
making and artificial potential fields path-planning. Groups of
injured people are trapped in a disastrous situation. These people are
categorized into several groups based on the severity of their
situation. A rescue robot, whose ultimate objective is reaching
injured groups and providing preliminary aid for them through a path
with minimum risk, has to perform certain tasks on its way towards
targets before the arrival of rescue team. A decision value is assigned
to each target based on the whole degree of satisfaction of the criteria
and duties of the robot toward the target and the importance of
rescuing each target based on their category and the number of
injured people. The resulted decision value defines the strength of the
attractive potential field of each target. Dangerous environmental
parameters are defined as obstacles whose risk determines the
strength of the repulsive potential field of each obstacle. Moreover,
negative and positive energies are assigned to the targets and
obstacles, which are variable with respects to the factors involved.
The simulation results show that the generated path for two cases
studies with certain differences in environmental conditions and
other risk factors differ considerably.
Abstract: We study the spatial design of experiment and we want to select a most informative subset, having prespecified size, from a set of correlated random variables. The problem arises in many applied domains, such as meteorology, environmental statistics, and statistical geology. In these applications, observations can be collected at different locations and possibly at different times. In spatial design, when the design region and the set of interest are discrete then the covariance matrix completely describe any objective function and our goal is to choose a feasible design that minimizes the resulting uncertainty. The problem is recast as that of maximizing the determinant of the covariance matrix of the chosen subset. This problem is NP-hard. For using these designs in computer experiments, in many cases, the design space is very large and it's not possible to calculate the exact optimal solution. Heuristic optimization methods can discover efficient experiment designs in situations where traditional designs cannot be applied, exchange methods are ineffective and exact solution not possible. We developed a GA algorithm to take advantage of the exploratory power of this algorithm. The successful application of this method is demonstrated in large design space. We consider a real case of design of experiment. In our problem, design space is very large and for solving the problem, we used proposed GA algorithm.
Abstract: The major goal in defining and examining game
scenarios is to find good strategies as solutions to the game. A
plausible solution is a recommendation to the players on how to play
the game, which is represented as strategies guided by the various
choices available to the players. These choices invariably compel the
players (decision makers) to execute an action following some
conscious tactics. In this paper, we proposed a refinement-based
heuristic as a machine learning technique for human-like decision
making in playing Ayo game. The result showed that our machine
learning technique is more adaptable and more responsive in making
decision than human intelligence. The technique has the advantage
that a search is astutely conducted in a shallow horizon game tree.
Our simulation was tested against Awale shareware and an appealing
result was obtained.
Abstract: Facility Layout Problem (FLP) is one of the essential
problems of several types of manufacturing and service sector. It is
an optimization problem on which the main objective is to obtain the
efficient locations, arrangement and order of the facilities. In the
literature, there are numerous facility layout problem research
presented and have used meta-heuristic approaches to achieve
optimal facility layout design. This paper presented genetic algorithm
to solve facility layout problem; to minimize total cost function. The
performance of the proposed approach was verified and compared
using problems in the literature.
Abstract: This paper presents an effective framework for Chinesesyntactic parsing, which includes two parts. The first one is a parsing framework, which is based on an improved bottom-up chart parsingalgorithm, and integrates the idea of the beam search strategy of N bestalgorithm and heuristic function of A* algorithm for pruning, then get multiple parsing trees. The second is a novel evaluation model, which integrates contextual and partial lexical information into traditional PCFG model and defines a new score function. Using this model, the tree with the highest score is found out as the best parsing tree. Finally,the contrasting experiment results are given. Keywords?syntactic parsing, PCFG, pruning, evaluation model.