Abstract: In this paper a combination approach of two heuristic-based algorithms: genetic algorithm and tabu search is proposed. It has been developed to obtain the least cost based on the split-pipe design of looped water distribution network. The proposed combination algorithm has been applied to solve the three well-known water distribution networks taken from the literature. The development of the combination of these two heuristic-based algorithms for optimization is aimed at enhancing their strengths and compensating their weaknesses. Tabu search is rather systematic and deterministic that uses adaptive memory in search process, while genetic algorithm is probabilistic and stochastic optimization technique in which the solution space is explored by generating candidate solutions. Split-pipe design may not be realistic in practice but in optimization purpose, optimal solutions are always achieved with split-pipe design. The solutions obtained in this study have proved that the least cost solutions obtained from the split-pipe design are always better than those obtained from the single pipe design. The results obtained from the combination approach show its ability and effectiveness to solve combinatorial optimization problems. The solutions obtained are very satisfactory and high quality in which the solutions of two networks are found to be the lowest-cost solutions yet presented in the literature. The concept of combination approach proposed in this study is expected to contribute some useful benefits in diverse problems.
Abstract: This paper presents a perturbation based search method
to solve the unconstrained binary quadratic programming problem.
The proposed algorithm was tested with some of the standard test
problems and the results are reported for 10 instances of 50, 100, 250,
& 500 variable problems. A comparison of the performance of the
proposed algorithm with other heuristics and optimization software is
made. Based on the results, it was found that the proposed algorithm
is computationally inexpensive and the solutions obtained match the
best known solutions for smaller sized problems. For larger instances,
the algorithm is capable of finding a solution within 0.11% of the
best known solution. Apart from being used as a stand-alone method,
this algorithm could also be incorporated with other heuristics to find
better solutions.
Abstract: A hybrid learning automata-genetic algorithm (HLGA) is proposed to solve QoS routing optimization problem of next generation networks. The algorithm complements the advantages of the learning Automato Algorithm(LA) and Genetic Algorithm(GA). It firstly uses the good global search capability of LA to generate initial population needed by GA, then it uses GA to improve the Quality of Service(QoS) and acquiring the optimization tree through new algorithms for crossover and mutation operators which are an NP-Complete problem. In the proposed algorithm, the connectivity matrix of edges is used for genotype representation. Some novel heuristics are also proposed for mutation, crossover, and creation of random individuals. We evaluate the performance and efficiency of the proposed HLGA-based algorithm in comparison with other existing heuristic and GA-based algorithms by the result of simulation. Simulation results demonstrate that this paper proposed algorithm not only has the fast calculating speed and high accuracy but also can improve the efficiency in Next Generation Networks QoS routing. The proposed algorithm has overcome all of the previous algorithms in the literature.
Abstract: This paper presents a comparison of metaheuristic
algorithms, Genetic Algorithm (GA) and Ant Colony Optimization
(ACO), in producing freeman chain code (FCC). The main problem
in representing characters using FCC is the length of the FCC
depends on the starting points. Isolated characters, especially the
upper-case characters, usually have branches that make the traversing
process difficult. The study in FCC construction using one
continuous route has not been widely explored. This is our
motivation to use the population-based metaheuristics. The
experimental result shows that the route length using GA is better
than ACO, however, ACO is better in computation time than GA.
Abstract: This paper introduces two decoders for binary linear
codes based on Metaheuristics. The first one uses a genetic algorithm
and the second is based on a combination genetic algorithm with
a feed forward neural network. The decoder based on the genetic
algorithms (DAG) applied to BCH and convolutional codes give good
performances compared to Chase-2 and Viterbi algorithm respectively
and reach the performances of the OSD-3 for some Residue
Quadratic (RQ) codes. This algorithm is less complex for linear
block codes of large block length; furthermore their performances
can be improved by tuning the decoder-s parameters, in particular the
number of individuals by population and the number of generations.
In the second algorithm, the search space, in contrast to DAG which
was limited to the code word space, now covers the whole binary
vector space. It tries to elude a great number of coding operations
by using a neural network. This reduces greatly the complexity of
the decoder while maintaining comparable performances.
Abstract: Assembly line balancing is a very important issue in
mass production systems due to production cost. Although many
studies have been done on this topic, but because assembly line
balancing problems are so complex they are categorized as NP-hard
problems and researchers strongly recommend using heuristic
methods. This paper presents a new heuristic approach called the
critical task method (CTM) for solving U-shape assembly line
balancing problems. The performance of the proposed heuristic
method is tested by solving a number of test problems and comparing
them with 12 other heuristics available in the literature to confirm the
superior performance of the proposed heuristic. Furthermore, to
prove the efficiency of the proposed CTM, the objectives are
increased to minimize the number of workstation (or equivalently
maximize line efficiency), and minimizing the smoothness index.
Finally, it is proven that the proposed heuristic is more efficient than
the others to solve the U-shape assembly line balancing problem.
Abstract: Application of Expert System in the area of agriculture would take the form of Integrated Crop Management decision aids and would encompass water management, fertilizer management, crop protection systems and identification of implements. In order to remain competitive, the modern farmer often relies on agricultural specialists and advisors to provide information for decision-making. An expert system normally composed of a knowledge base (information, heuristics, etc.), inference engine (analyzes knowledge base), and end user interface (accepting inputs, generating outputs). Software named 'CROP-9-DSS' incorporating all modern features like, graphics, photos, video clippings etc. has been developed. This package will aid as a decision support system for identification of pest and diseases with control measures, fertilizer recommendation system, water management system and identification of farm implements for leading crops of Kerala (India) namely Coconut, Rice, Cashew, Pepper, Banana, four vegetables like Amaranthus, Bhindi, Brinjal and Cucurbits. 'CROP-9-DSS' will act as an expert system to agricultural officers, scientists in the field of agriculture and extension workers for decision-making and help them in suggesting suitable recommendations.
Abstract: Sudoku is a kind of logic puzzles. Each puzzle consists
of a board, which is a 9×9 cells, divided into nine 3×3 subblocks
and a set of numbers from 1 to 9. The aim of this puzzle is to
fill in every cell of the board with a number from 1 to 9 such
that in every row, every column, and every subblock contains each
number exactly one. Sudoku puzzles belong to combinatorial problem
(NP complete). Sudoku puzzles can be solved by using a variety of
techniques/algorithms such as genetic algorithms, heuristics, integer
programming, and so on. In this paper, we propose a new approach for
solving Sudoku which is by modelling them as block-world problems.
In block-world problems, there are a number of boxes on the table
with a particular order or arrangement. The objective of this problem
is to change this arrangement into the targeted arrangement with the
help of two types of robots. In this paper, we present three models
for Sudoku. We modellized Sudoku as parameterized multi-agent
systems. A parameterized multi-agent system is a multi-agent system
which consists of several uniform/similar agents and the number of
the agents in the system is stated as the parameter of this system. We
use Temporal Logic of Actions (TLA) for formalizing our models.
Abstract: In this study, we are interested in the economic lot
scheduling problem (ELSP) that considers manufacturing of the
serviceable products and remanufacturing of the reworked products. In
this paper, we formulate a mathematical model for the ELSP with
reworks using the basic period approach. In order to solve this
problem, we propose a search algorithm to find the cyclic multiplier ki
of each product that can be cyclically produced for every ki basic
periods. This research also uses two heuristics to search for the optimal
production sequence of all lots and the optimal time length of the basic
period so as to minimize the average total cost. This research uses a
numerical example to show the effectiveness of our approach.
Abstract: Virtualization-based server consolidation has been
proven to be an ideal technique to solve the server sprawl problem by
consolidating multiple virtualized servers onto a few physical servers
leading to improved resource utilization and return on investment. In
this paper, we solve this problem by using existing servers, which are
heterogeneous and diversely preferred by IT managers. Five practical
consolidation rules are introduced, and a decision model is proposed to
optimally allocate source services to physical target servers while
maximizing the average resource utilization and preference value. Our
model can be regarded as a multi-objective multi-dimension
bin-packing (MOMDBP) problem with constraints, which is strongly
NP-hard. An improved grouping generic algorithm (GGA) is
introduced for the problem. Extensive simulations were performed and
the results are given.
Abstract: In this research, the flow pattern influence on
performance of a micro PEMFC was investigated
experimentally. The investigation focused on the impacts of
bend angels and rib/channel dimensions of serpentine flow
channel pattern on the performance and investigated how they
improve the performance. The fuel cell employed for these
experiments was a micro single PEMFC with a membrane of
1.44 cm2 Nafion NRE-212. The results show that 60° and 120°
bend angles can provide the better performances at 20 and 40
sccm inlet flow rates comparing to that the conventional design.
Additionally, wider channel with narrower rib spacing gives
better performance. These results may be applied to develop
universal heuristics for the design of flow pattern of micro
PEMFC.
Abstract: In this paper, we study the knapsack sharing problem, a variant of the well-known NP-Hard single knapsack problem. We investigate the use of a tree search for optimally solving the problem. The used method combines two complementary phases: a reduction interval search phase and a branch and bound procedure one. First, the reduction phase applies a polynomial reduction strategy; that is used for decomposing the problem into a series of knapsack problems. Second, the tree search procedure is applied in order to attain a set of optimal capacities characterizing the knapsack problems. Finally, the performance of the proposed optimal algorithm is evaluated on a set of instances of the literature and its runtime is compared to the best exact algorithm of the literature.
Abstract: Asynchronous Transfer Mode (ATM) is widely used
in telecommunications systems to send data, video and voice at a
very high speed. In ATM network optimizing the bandwidth through
dynamic routing is an important consideration. Previous research
work shows that traditional optimization heuristics result in suboptimal
solution. In this paper we have explored non-traditional
optimization technique. We propose comparison of two such
algorithms - Genetic Algorithm (GA) and Tabu search (TS), based on
non-traditional Optimization approach, for solving the dynamic
routing problem in ATM networks which in return will optimize the
bandwidth. The optimized bandwidth could mean that some
attractive business applications would become feasible such as high
speed LAN interconnection, teleconferencing etc. We have also
performed a comparative study of the selection mechanisms in GA
and listed the best selection mechanism and a new initialization
technique which improves the efficiency of the GA.
Abstract: Today, money laundering (ML) poses a serious threat
not only to financial institutions but also to the nation. This criminal
activity is becoming more and more sophisticated and seems to have
moved from the cliché of drug trafficking to financing terrorism and
surely not forgetting personal gain. Most international financial
institutions have been implementing anti-money laundering solutions
(AML) to fight investment fraud. However, traditional investigative
techniques consume numerous man-hours. Recently, data mining
approaches have been developed and are considered as well-suited
techniques for detecting ML activities. Within the scope of a
collaboration project for the purpose of developing a new solution for
the AML Units in an international investment bank, we proposed a
data mining-based solution for AML. In this paper, we present a
heuristics approach to improve the performance for this solution. We
also show some preliminary results associated with this method on
analysing transaction datasets.
Abstract: The physical methods for RNA secondary structure prediction are time consuming and expensive, thus methods for computational prediction will be a proper alternative. Various algorithms have been used for RNA structure prediction including dynamic programming and metaheuristic algorithms. Musician's behaviorinspired harmony search is a recently developed metaheuristic algorithm which has been successful in a wide variety of complex optimization problems. This paper proposes a harmony search algorithm (HSRNAFold) to find RNA secondary structure with minimum free energy and similar to the native structure. HSRNAFold is compared with dynamic programming benchmark mfold and metaheuristic algorithms (RnaPredict, SetPSO and HelixPSO). The results showed that HSRNAFold is comparable to mfold and better than metaheuristics in finding the minimum free energies and the number of correct base pairs.
Abstract: The Far From Most Strings Problem (FFMSP) is to obtain a string which is far from as many as possible of a given set of strings. All the input and the output strings are of the same length, and two strings are said to be far if their hamming distance is greater than or equal to a given positive integer. FFMSP belongs to the class of sequences consensus problems which have applications in molecular biology. The problem is NP-hard; it does not admit a constant-ratio approximation either, unless P = NP. Therefore, in addition to exact and approximate algorithms, (meta)heuristic algorithms have been proposed for the problem in recent years. On the other hand, in the recent years, hybrid algorithms have been proposed and successfully used for many hard problems in a variety of domains. In this paper, a new metaheuristic algorithm, called Constructive Beam and Local Search (CBLS), is investigated for the problem, which is a hybridization of constructive beam search and local search algorithms. More specifically, the proposed algorithm consists of two phases, the first phase is to obtain several candidate solutions via the constructive beam search and the second phase is to apply local search to the candidate solutions obtained by the first phase. The best solution found is returned as the final solution to the problem. The proposed algorithm is also similar to memetic algorithms in the sense that both use local search to further improve individual solutions. The CBLS algorithm is compared with the most recent published algorithm for the problem, GRASP, with significantly positive results; the improvement is by order of magnitudes in most cases.
Abstract: Selecting the routes and the assignment of link flow in a computer communication networks are extremely complex combinatorial optimization problems. Metaheuristics, such as genetic or simulated annealing algorithms, are widely applicable heuristic optimization strategies that have shown encouraging results for a large number of difficult combinatorial optimization problems. This paper considers the route selection and hence the flow assignment problem. A genetic algorithm and simulated annealing algorithm are used to solve this problem. A new hybrid algorithm combining the genetic with the simulated annealing algorithm is introduced. A modification of the genetic algorithm is also introduced. Computational experiments with sample networks are reported. The results show that the proposed modified genetic algorithm is efficient in finding good solutions of the flow assignment problem compared with other techniques.
Abstract: Simulation is a very powerful method used for highperformance
and high-quality design in distributed system, and now
maybe the only one, considering the heterogeneity, complexity and
cost of distributed systems. In Grid environments, foe example, it is
hard and even impossible to perform scheduler performance
evaluation in a repeatable and controllable manner as resources and
users are distributed across multiple organizations with their own
policies. In addition, Grid test-beds are limited and creating an
adequately-sized test-bed is expensive and time consuming.
Scalability, reliability and fault-tolerance become important
requirements for distributed systems in order to support distributed
computation. A distributed system with such characteristics is called
dependable. Large environments, like Cloud, offer unique
advantages, such as low cost, dependability and satisfy QoS for all
users. Resource management in large environments address
performant scheduling algorithm guided by QoS constrains. This
paper presents the performance evaluation of scheduling heuristics
guided by different optimization criteria. The algorithms for
distributed scheduling are analyzed in order to satisfy users
constrains considering in the same time independent capabilities of
resources. This analysis acts like a profiling step for algorithm
calibration. The performance evaluation is based on simulation. The
simulator is MONARC, a powerful tool for large scale distributed
systems simulation. The novelty of this paper consists in synthetic
analysis results that offer guidelines for scheduler service
configuration and sustain the empirical-based decision. The results
could be used in decisions regarding optimizations to existing Grid
DAG Scheduling and for selecting the proper algorithm for DAG
scheduling in various actual situations.
Abstract: This research elaborates decision models for product
innovation in the early phases, focusing on one of the most widely
implemented method in marketing research: conjoint analysis and the
related conjoint-based models with special focus on heuristics
programming techniques for the development of optimal product
innovation. The concept, potential, requirements and limitations of
conjoint analysis and its conjoint-based heuristics successors are
analysed and the development of conceptual framework of Genetic
Algorithm (GA) as one of the most widely implemented heuristic
methods for developing product innovations are discussed.
Abstract: In this paper, we study the multi-scenario knapsack problem, a variant of the well-known NP-Hard single knapsack problem. We investigate the use of an adaptive algorithm for solving heuristically the problem. The used method combines two complementary phases: a size reduction phase and a dynamic 2- opt procedure one. First, the reduction phase applies a polynomial reduction strategy; that is used for reducing the size problem. Second, the adaptive search procedure is applied in order to attain a feasible solution Finally, the performances of two versions of the proposed algorithm are evaluated on a set of randomly generated instances.