Abstract: The Block Sorting problem is to sort a given
permutation moving blocks. A block is defined as a substring
of the given permutation, which is also a substring of the
identity permutation. Block Sorting has been proved to be
NP-Hard. Until now two different 2-Approximation algorithms
have been presented for block sorting. These are the best known
algorithms for Block Sorting till date. In this work we present
a different characterization of Block Sorting in terms of a
transposition cycle graph. Then we suggest a heuristic,
which we show to exhibit a 2-approximation performance
guarantee for most permutations.
Abstract: The heuristic decision rules used for project
scheduling will vary depending upon the project-s size, complexity,
duration, personnel, and owner requirements. The concept of project
complexity has received little detailed attention. The need to
differentiate between easy and hard problem instances and the
interest in isolating the fundamental factors that determine the
computing effort required by these procedures inspired a number of
researchers to develop various complexity measures.
In this study, the most common measures of project complexity are
presented. A new measure of project complexity is developed. The
main privilege of the proposed measure is that, it considers size,
shape and logic characteristics, time characteristics, resource
demands and availability characteristics as well as number of critical
activities and critical paths. The degree of sensitivity of the proposed
measure for complexity of project networks has been tested and
evaluated against the other measures of complexity of the considered
fifty project networks under consideration in the current study. The
developed measure showed more sensitivity to the changes in the
network data and gives accurate quantified results when comparing
the complexities of networks.
Abstract: A heuristic conceptual model for to develop the
Reliability Centered Maintenance (RCM), especially in preventive
strategy, has been explored during this paper. In most real cases
which complicity of system obligates high degree of reliability, this
model proposes a more appropriate reliability function between life
time distribution based and another which is based on relevant
Extreme Value (EV) distribution. A statistical and mathematical
approach is used to estimate and verify these two distribution
functions. Then best one is chosen just among them, whichever is
more reliable. A numeric Industrial case study will be reviewed to
represent the concepts of this paper, more clearly.
Abstract: Introduction applicability of high-speed cutting stock problem (CSP) is presented in this paper. Due to the orders continued coming in from various on-line ways for a professional cutting company, to stay competitive, such a business has to focus on sustained production at high levels. In others words, operators have to keep the machine running to stay ahead of the pack. Therefore, the continuous stock cutting problem with setup is proposed to minimize the cutting time and pattern changing time to meet the on-line given demand. In this paper, a novel method is proposed to solve the problem directly by using cutting patterns directly. A major advantage of the proposed method in series on-line production is that the system can adjust the cutting plan according to the floating orders. Examples with multiple items are demonstrated. The results show considerable efficiency and reliability in high-speed cutting of CSP.
Abstract: In recent years, copulas have become very popular in
financial research and actuarial science as they are more flexible in
modelling the co-movements and relationships of risk factors as compared
to the conventional linear correlation coefficient by Pearson.
However, a precise estimation of the copula parameters is vital in
order to correctly capture the (possibly nonlinear) dependence structure
and joint tail events. In this study, we employ two optimization
heuristics, namely Differential Evolution and Threshold Accepting to
tackle the parameter estimation of multivariate t distribution models
in the EML approach. Since the evolutionary optimizer does not rely
on gradient search, the EML approach can be applied to estimation of
more complicated copula models such as high-dimensional copulas.
Our experimental study shows that the proposed method provides
more robust and more accurate estimates as compared to the IFM
approach.
Abstract: In this paper, a framework for the simplification and
standardization of metaheuristic related parameter-tuning by applying
a four phase methodology, utilizing Design of Experiments and
Artificial Neural Networks, is presented. Metaheuristics are multipurpose
problem solvers that are utilized on computational optimization
problems for which no efficient problem specific algorithm
exist. Their successful application to concrete problems requires the
finding of a good initial parameter setting, which is a tedious and
time consuming task. Recent research reveals the lack of approach
when it comes to this so called parameter-tuning process. In the
majority of publications, researchers do have a weak motivation for
their respective choices, if any. Because initial parameter settings
have a significant impact on the solutions quality, this course of
action could lead to suboptimal experimental results, and thereby
a fraudulent basis for the drawing of conclusions.
Abstract: We proposed a technique to identify road traffic
congestion levels from velocity of mobile sensors with high accuracy
and consistent with motorists- judgments. The data collection utilized
a GPS device, a webcam, and an opinion survey. Human perceptions
were used to rate the traffic congestion levels into three levels: light,
heavy, and jam. Then the ratings and velocity were fed into a
decision tree learning model (J48). We successfully extracted vehicle
movement patterns to feed into the learning model using a sliding
windows technique. The parameters capturing the vehicle moving
patterns and the windows size were heuristically optimized. The
model achieved accuracy as high as 99.68%. By implementing the
model on the existing traffic report systems, the reports will cover
comprehensive areas. The proposed method can be applied to any
parts of the world.
Abstract: This article proposes an Ant Colony Optimization
(ACO) metaheuristic to minimize total makespan for scheduling a set
of jobs and assign workers for uniformly related parallel machines.
An algorithm based on ACO has been developed and coded on a
computer program Matlab®, to solve this problem. The paper
explains various steps to apply Ant Colony approach to the problem
of minimizing makespan for the worker assignment & jobs
scheduling problem in a parallel machine model and is aimed at
evaluating the strength of ACO as compared to other conventional
approaches. One data set containing 100 problems (12 Jobs, 03
machines and 10 workers) which is available on internet, has been
taken and solved through this ACO algorithm. The results of our
ACO based algorithm has shown drastically improved results,
especially, in terms of negligible computational effort of CPU, to
reach the optimal solution. In our case, the time taken to solve all 100
problems is even lesser than the average time taken to solve one
problem in the data set by other conventional approaches like GA
algorithm and SPT-A/LMC heuristics.
Abstract: Connected dominating set (CDS) problem in unit disk
graph has signi£cant impact on an ef£cient design of routing protocols
in wireless sensor networks, where the searching space for a
route is reduced to nodes in the set. A set is dominating if all the
nodes in the system are either in the set or neighbors of nodes in the
set. In this paper, a simple and ef£cient heuristic method is proposed
for £nding a minimum connected dominating set (MCDS) in ad hoc
wireless networks based on the new parameter support of vertices.
With this parameter the proposed heuristic approach effectively
£nds the MCDS of a graph. Extensive computational experiments
show that the proposed approach outperforms the recently proposed
heuristics found in the literature for the MCD
Abstract: In this paper an average number of re-handlings
analysis is proposed to solve the problem of finding bays
configuration in small container terminal in Gliwice, Poland.
Rehandlings in this terminal can be performed only by reachstackers.
The goal of the heuristic is to plan the reachstacter moves in the
terminal, assuming that the target containers are reached and the
number of re-handings is minimized. The real situation requires also
to take into account the model of the problem environment
uncertainty caused by the fact that many containers are not delivered
to the terminal on time, or can not be sent on scheduled time. To
enable this, the heuristic uses some assumptions to simplify problem
analysis.
Abstract: In this paper a procedure for the split-pipe design of looped water distribution network based on the use of simulated annealing is proposed. Simulated annealing is a heuristic-based search algorithm, motivated by an analogy of physical annealing in solids. It is capable for solving the combinatorial optimization problem. In contrast to the split-pipe design that is derived from a continuous diameter design that has been implemented in conventional optimization techniques, the split-pipe design proposed in this paper is derived from a discrete diameter design where a set of pipe diameters is chosen directly from a specified set of commercial pipes. The optimality and feasibility of the solutions are found to be guaranteed by using the proposed method. The performance of the proposed procedure is demonstrated through solving the three well-known problems of water distribution network taken from the literature. Simulated annealing provides very promising solutions and the lowest-cost solutions are found for all of these test problems. The results obtained from these applications show that simulated annealing is able to handle a combinatorial optimization problem of the least cost design of water distribution network. The technique can be considered as an alternative tool for similar areas of research. Further applications and improvements of the technique are expected as well.
Abstract: Economic dispatch (ED) has been considered to be one of the key functions in electric power system operation which can help to build up effective generating management plans. The practical ED problem has non-smooth cost function with nonlinear constraints which make it difficult to be effectively solved. This paper presents a novel heuristic and efficient optimization approach based on the new Bat algorithm (BA) to solve the practical non-smooth economic dispatch problem. The proposed algorithm easily takes care of different constraints. In addition, two newly introduced modifications method is developed to improve the variety of the bat population when increasing the convergence speed simultaneously. The simulation results obtained by the proposed algorithms are compared with the results obtained using other recently develop methods available in the literature.
Abstract: Pairwise testing, which requires that every
combination of valid values of each pair of system factors be covered
by at lease one test case, plays an important role in software testing
since many faults are caused by unexpected 2-way interactions among
system factors. Although meta-heuristic strategies like simulated
annealing can generally discover smaller pairwise test suite, they may
cost more time to perform search, compared with greedy algorithms.
We propose a new method, improved Extremal Optimization (EO)
based on the Bak-Sneppen (BS) model of biological evolution, for
constructing pairwise test suites and define fitness function according
to the requirement of improved EO. Experimental results show that
improved EO gives similar size of resulting pairwise test suite and
yields an 85% reduction in solution time over SA.
Abstract: With data centers, end-users can realize the pervasiveness of services that will be one day the cornerstone of our lives. However, data centers are often classified as computing systems that consume the most amounts of power. To circumvent such a problem, we propose a self-adaptive weighted sum methodology that jointly optimizes the performance and power consumption of any given data center. Compared to traditional methodologies for multi-objective optimization problems, the proposed self-adaptive weighted sum technique does not rely on a systematical change of weights during the optimization procedure. The proposed technique is compared with the greedy and LR heuristics for large-scale problems, and the optimal solution for small-scale problems implemented in LINDO. the experimental results revealed that the proposed selfadaptive weighted sum technique outperforms both of the heuristics and projects a competitive performance compared to the optimal solution.
Abstract: Power loss reduction is one of the main targets in power industry and so in this paper, the problem of finding the optimal configuration of a radial distribution system for loss reduction is considered. Optimal reconfiguration involves the selection of the best set of branches to be opened ,one each from each loop, for reducing resistive line losses , and reliving overloads on feeders by shifting the load to adjacent feeders. However ,since there are many candidate switching combinations in the system ,the feeder reconfiguration is a complicated problem. In this paper a new approach is proposed based on a simple optimum loss calculation by determining optimal trees of the given network. From graph theory a distribution network can be represented with a graph that consists a set of nodes and branches. In fact this problem can be viewed as a problem of determining an optimal tree of the graph which simultaneously ensure radial structure of each candidate topology .In this method the refined genetic algorithm is also set up and some improvements of algorithm are made on chromosome coding. In this paper an implementation of the algorithm presented by [7] is applied by modifying in load flow program and a comparison of this method with the proposed method is employed. In [7] an algorithm is proposed that the choice of the switches to be opened is based on simple heuristic rules. This algorithm reduce the number of load flow runs and also reduce the switching combinations to a fewer number and gives the optimum solution. To demonstrate the validity of these methods computer simulations with PSAT and MATLAB programs are carried out on 33-bus test system. The results show that the performance of the proposed method is better than [7] method and also other methods.
Abstract: Network reconfiguration in distribution system is realized by changing the status of sectionalizing switches to reduce the power loss in the system. This paper presents a new method which applies an artificial bee colony algorithm (ABC) for determining the sectionalizing switch to be operated in order to solve the distribution system loss minimization problem. The ABC algorithm is a new population based metaheuristic approach inspired by intelligent foraging behavior of honeybee swarm. The advantage of ABC algorithm is that it does not require external parameters such as cross over rate and mutation rate as in case of genetic algorithm and differential evolution and it is hard to determine these parameters in prior. The other advantage is that the global search ability in the algorithm is implemented by introducing neighborhood source production mechanism which is a similar to mutation process. To demonstrate the validity of the proposed algorithm, computer simulations are carried out on 14, 33, and 119-bus systems and compared with different approaches available in the literature. The proposed method has outperformed the other methods in terms of the quality of solution and computational efficiency.
Abstract: In the recent past Learning Classifier Systems have
been successfully used for data mining. Learning Classifier System
(LCS) is basically a machine learning technique which combines
evolutionary computing, reinforcement learning, supervised or
unsupervised learning and heuristics to produce adaptive systems. A
LCS learns by interacting with an environment from which it
receives feedback in the form of numerical reward. Learning is
achieved by trying to maximize the amount of reward received. All
LCSs models more or less, comprise four main components; a finite
population of condition–action rules, called classifiers; the
performance component, which governs the interaction with the
environment; the credit assignment component, which distributes the
reward received from the environment to the classifiers accountable
for the rewards obtained; the discovery component, which is
responsible for discovering better rules and improving existing ones
through a genetic algorithm. The concatenate of the production rules
in the LCS form the genotype, and therefore the GA should operate
on a population of classifier systems. This approach is known as the
'Pittsburgh' Classifier Systems. Other LCS that perform their GA at
the rule level within a population are known as 'Mitchigan' Classifier
Systems. The most predominant representation of the discovered
knowledge is the standard production rules (PRs) in the form of IF P
THEN D. The PRs, however, are unable to handle exceptions and do
not exhibit variable precision. The Censored Production Rules
(CPRs), an extension of PRs, were proposed by Michalski and
Winston that exhibit variable precision and supports an efficient
mechanism for handling exceptions. A CPR is an augmented
production rule of the form: IF P THEN D UNLESS C, where
Censor C is an exception to the rule. Such rules are employed in
situations, in which conditional statement IF P THEN D holds
frequently and the assertion C holds rarely. By using a rule of this
type we are free to ignore the exception conditions, when the
resources needed to establish its presence are tight or there is simply
no information available as to whether it holds or not. Thus, the IF P
THEN D part of CPR expresses important information, while the
UNLESS C part acts only as a switch and changes the polarity of D
to ~D. In this paper Pittsburgh style LCSs approach is used for
automated discovery of CPRs. An appropriate encoding scheme is
suggested to represent a chromosome consisting of fixed size set of
CPRs. Suitable genetic operators are designed for the set of CPRs
and individual CPRs and also appropriate fitness function is proposed
that incorporates basic constraints on CPR. Experimental results are
presented to demonstrate the performance of the proposed learning
classifier system.
Abstract: This paper compares the heuristic Global Search
Techniques; Genetic Algorithm, Particle Swarm Optimization,
Simulated Annealing, Generalized Pattern Search, genetic algorithm
hybridized with Nelder–Mead and Generalized pattern search
technique for tuning of fuzzy PID controller for Puma 560. Since the
actual control is in joint space ,inverse kinematics is used to generate
various joint angles correspoding to desired cartesian space
trajectory. Efficient dynamics and kinematics are modeled on Matlab
which takes very less simulation time. Performances of all the tuning
methods with and without disturbance are compared in terms of ITSE
in joint space and ISE in cartesian space for spiral trajectory tracking.
Genetic Algorithm hybridized with Generalized Pattern Search is
showing best performance.
Abstract: This paper presents the application of an enhanced
Particle Swarm Optimization (EPSO) combined with Gaussian
Mutation (GM) for solving the Dynamic Economic Dispatch (DED)
problem considering the operating constraints of generators. The
EPSO consists of the standard PSO and a modified heuristic search
approaches. Namely, the ability of the traditional PSO is enhanced
by applying the modified heuristic search approach to prevent the
solutions from violating the constraints. In addition, Gaussian
Mutation is aimed at increasing the diversity of global search, whilst
it also prevents being trapped in suboptimal points during search. To
illustrate its efficiency and effectiveness, the developed EPSO-GM
approach is tested on the 3-unit and 10-unit 24-hour systems
considering valve-point effect. From the experimental results, it can
be concluded that the proposed EPSO-GM provides, the accurate
solution, the efficiency, and the feature of robust computation
compared with other algorithms under consideration.
Abstract: Variable ordering heuristics are used in constraint satisfaction algorithms. Different characteristics of various variable ordering heuristics are complementary. Therefore we have tried to get the advantages of all heuristics to improve search algorithms performance for solving constraint satisfaction problems. This paper considers combinations based on products and quotients, and then a newer form of combination based on weighted sums of ratings from a set of base heuristics, some of which result in definite improvements in performance.