Kratica J., Kovačević-Vujčić V., Čangalović M., The strong metric dimension of some generalized Petersen graphs, Applicable Analysis and Discrete Mathematics, Vol 11., No. 1, pp. 1-10., 2017. doi:10.2298/AADM161110032K Journal site - full paper
Matić D., Kratica J., Maksimović Z., Solving the minimum edge-dilation k-center problem by genetic algorithms, Computers & Industrial Engineering, Vol. 113, pp. 282-293, November 2017. doi:10.1016/j.cie.2017.09.029 Journal site - full paper
Maksimović Z., Kratica J., Savić A., Two metaheuristics for solving the connected multidimensional maximum bisection problem, Soft Computing, Vol. 21, No. 21, pp. 6453-6469, November 2017. doi:10.1007/s00500-016-2203-1 Journal site - full paper
This paper presents a variable neighborhood search (VNS) algorithm for solving bandwidth coloring problem (BCP) and bandwidth multicoloring problem (BMCP). BCP and BMCP are generalizations of the well known vertex coloring problem and they are of a great interest from both theoretical and practical points of view. Presented VNS combines a shaking procedure which perturbs the colors for an increasing number of vertices and a specific variable neighborhood descent (VND) procedure, based on the specially designed arrangement of the vertices which are the subject of re-coloring. By this approach, local search is split in a series of disjoint procedures, enabling better choice of the vertices which are addressed to re-color. The experiments show that proposed method is highly competitive with the state-of-the-art algorithms and improves 2 out of 33 previous best known solutions for BMCP.
Keywords: Bandwidth Coloring, Bandwidth MultiColoring, Frequency Assignment, Variable Neighborhood Search, Variable Neighborhood Descent
PDF arXivIn this paper, we address two metaheuristic approaches, a Variable Neighborhood Search (VNS) and an Electromagnetism-like metaheuristic (EM), on an NP-hard optimization problem: Multi-dimensional Two-way Number Partitioning Problem (MDTWNPP). MDTWNPP is a generalization of a Two-way Number Partitioning Problem (TWNPP), where a set of vectors is partitioned rather than a set of numbers. The simple $k$-swap neighborhoods allow an effective shaking procedure in the VNS search. The attraction-repulsion mechanism of EM is extended with a scaling procedure, which additionally moves EM points closer to local optima. Both VNS and EM use the same local search procedure based on 1-swap improvements. Computational results were obtained on 210 standard instances. Direct comparison with results from the literature confirm the significance of applying these methods to MDTWNPP.
Number partitioning, Metaheuristics, Combinatorial optimization.
Journal site - full paperThis paper considers the Multi Level Uncapacitated Facility Location Problem (MLUFLP). A new mixed integer linear programming (MILP) formulation is presented and validity of this formulation is given. Experimental results are performed on instances known from literature. The results achieved by CPLEX and Gurobi solvers, based on the proposed MILP formulation, are compared to the results obtained by the same solvers on the already known formulations. The results show that CPLEX and Gurobi can optimally solve all small and medium sized instances and even some large-scale instances using the new formulation.
Multi level location problems, Integer linear programming, Mathematical modelling, Discrete location.
Journal site - full paper | MLUFLP instances (.7z, 11 MB) | MLUFLP optimal and best known resultsThe strong metric dimension has been a subject of considerable amount of research in recent years. This survey describes the related development by bringing together theoretical results and computational approaches, and places the recent results within their historical and scientific framework.
Strong metric dimension, graph problems, combinatorial optimization.
AMS 2010 Primary Class. 05-02 AMS 2010 Secondary Class. 05C12; 90C10; 68T20
This paper deals with the uncapacitated multiple allocation p-hub median problem (UMApHMP). An electromagnetism-like (EM) method is proposed for solving this NP-hard problem. The new scaling technique combined with movement based on the attraction-repulsion mechanism directs EM towards promising search regions. Numerical results on a battery of benchmark AP and TM instances known from the literature are reported. The computational results show that EM reaches all previously known optimal solutions, and gives excellent results on large-scale instances.
Electromagnetism-like metaheuristic, hub location, combinatorial optimization
Journal site - full paperIn this paper, an electromagnetism-like approach (EM) for solving the maximum set splitting problem (MSSP) is applied. Hybrid approach consisting of the movement based on the attraction-repulsion mechanisms combining with the proposed scaling technique directs EM to promising search regions. Fast implementation of the local search procedure additionally improves the efficiency of overall EM system. Afterward, the performance of the proposed EM approach is evaluated on two classes of instances from the literature: minimum hitting set and Steiner triple systems. The results show, except in one case, that EM reached optimal solutions up to 500 elements and 50000 subsets on minimum hitting set instances. EM reached all optimal/best-known solutions for Steiner triple systems.
electromagnetism-like metaheuristic, combinatorial optimization, maximum set splitting problem, Steiner triple systems
Journal site - full paperIn this paper we consider the problem of determining the minimal cardinality of double resolving sets for prism graphs $Y_n$. It is proved that the minimal cardinality is equal to 4 if $n$ is even and equal to 3 if $n$ is odd.
metric dimension; minimal doubly resolving set; prism graphs, generalized Petersen graphs
AMS 2010 Primary Class. 05C12 AMS 2010 Secondary Class. 68R10; 05C75
Journal site - full paperThis paper is dealing with the rectangle packing problem where a big rectangle is filled with smaller rectangles, while the rectangle dimensions are real numbers. A new non-linear programming formulation is presented and validity of this formulation is being proven. In addition, two cases of the problem are presented in the paper - with and without rotation of smaller rectangles for $90^\circ$. The mixed integer piecewise linear formulation derived from the model is given, but with a simple form of the objective function.
nonlinear programming, piecewise linear relaxation, rectangle packing problem.
AMS 2010 Mathematics Subject Classification: 90C30; 90C11.
Journal site - full paperIn this paper, an improved genetic algorithm (GA) for solving the multi-level uncapacitated facility location problem (MLUFLP) is presented. First improvement is achieved by better implementation of dynamic programming, which speeds up the running time of the overall GA implementation. Second improvement is hybridization of the genetic algorithm with the fast local search procedure designed specially for MLUFLP. The experiments were carried out on instances proposed in the literature which are modified standard single level facility location problem instances. Improved genetic algorithm reaches all known optimal and the best solutions from literature, but in much shorter time. Hybridization with local search improves several best-known solutions for large-scale MLUFLP instances, in cases when the optimal is not known. Overall running time of both proposed GA methods is significantly shorter compared to previous GA approach.
evolutionary approach, metaheuristics, discrete location, combinatorial optimization.
MLUFLP instances (.7z, 11 MB) | MLUFLP optimal and best known results | Journal site - full paperIn this paper we consider two similar optimization problems on graphs: the strong metric dimension problem and the problem of determining minimal doubly resolving sets. We prove some properties of strong resolving sets and give an integer linear programming formulation of the strong metric dimension problem. These results are used to derive explicit expressions in terms of the dimension $n$, for the strong metric dimension of two classes of convex polytopes $D_n$ and $T_n$. On the other hand, we prove that minimal doubly resolving sets of $D_n$ and $T_n$ have constant cardinality for $n>7$.
Minimal doubly resolving set, Strong metric dimension, Convex polytopes
AMS 2010 Primary Class. 05C12, AMS 2010 Secondary Class. 90C10
Journal site - full paperIn this paper, two similar NP-hard optimization problems on graphs are considered: the metric dimension problem and the problem of determining a doubly resolving set with the minimum cardinality. Both are present in many diverse areas, including network discovery and verification, robot navigation, and chemistry. For each problem, a new mathematical programming formulation is proposed. For solving more realistic large-size instances, a variable neighborhood search based heuristic is designed. An extensive experimental comparison on five different types of instances indicates that the VNS approach consistently outperforms a genetic algorithm, the only existing heuristic in the literature designed for solving those problems.
Metaheuristics, Combinatorial optimization, Variable neighborhood search, Metric dimension, Minimal doubly resolving set
Journal site - full paper | GERAD PreprintWe consider the problem of determining the cardinality $\psi(H_{2,k})$ of minimal doubly resolving sets of Hamming graphs $H_{2,k}$. We prove that for $k \geq 6$ every minimal resolving set of $H_{2,k}$ is also a doubly resolving set, and, consequently, $\psi(H_{2,k})$ is equal to the metric dimension of $H_{2,k}$, which is known from the literature. Moreover, we find an explicit expression for the strong metric dimension of all Hamming graphs $H_{n,k}$.
Hamming graphs, metric dimension, minimal doubly resolving set, strong metric dimension, graph theory.
Journal site - Full paperIn this paper we present new evolutionary approach for solving the Routing and Carrier Selection Problem (RCSP). New encoding scheme is implemented with appropriate objective function. This approach in most cases keeps the feasibility of individuals by using specific representation and modified genetic operators. The numerical experiments were carried out on the standard data sets known from the literature and results were successful comparing to two other recent heuristic for solving RCSP.
vehicle routing problems, genetic algorithm, evolutionary computation, combinatorial optimization.
Journal site - full paperIn this paper the low autocorrelation binary sequence problem (LABSP) is modeled as a mixed integer quadratic programming (MIQP) problem and proof of the model's validity is given. Since the MIQP model is semidefinite, general optimization solvers can be used, and converge in a finite number of iterations. The experimental results show that IQP solvers, based on this MIQP formulation, are capable of optimally solving general/skew-symmetric LABSP instances up to 30/51 elements in a moderate time.
Integer programming, Quadratic programming, low autocorrelation binary sequence problem
ACM Computing Classification System (1998): G.1.6, I.2.8
We consider a variable neighborhood search (VNS) approach for solving the strong metric dimension problem. Computational experiments on ORLIB instances show that the VNS outperformes a genetic algorithm, the only existing heuristic in the literature for solving this problem.
Strong metric dimension, metaheuristics, combinatorial optimization.
Journal site - full paperIn this paper we propose a general variable neighborhood search approach for the balanced location problem. Next to large shaking neighborhoods, the embedded variable neighborhood descent utilizes three neighborhood structures that focus on different solution aspects. By a computational study, we show that this VNS outperforms existing methods with respect to average solution quality and stability.
discrete location, balanced allocation of clients, variable neighborhood search
Technical report | Journal site - full paperIn this paper we present a variable neighborhood search algorithm (VNS) for solving Multiple Level Warehouse Layout Problem (MLWLP). The algorithm deals with a specific representation of the solution, enabling the effective application of the shaking and local search procedures. System of neighborhoods changes the assignment ordering for an increasing number of items, while local search procedure tries to locally improve the solution by swapping the assignment ordering for pairs of items. Numerical experiments are performed on instances known in the literature. Computational results show that the proposed VNS achieves all optimal solutions for smaller instances, while for larger instances it finds rather better solutions than previously known method.
Warehouse Layout, Variable Neighborhood Search, Discrete Optimization
Journal site - full paperThis paper addresses the Capacitated Hub Location Problem (CHLP), which is a variant of the classical capacitated hub problem. What is presented is a modified mixed integer linear programming (MILP) formulation for the CHLP. This modified formulation includes fewer variables and constraints compared to the existing problem formulations in the literature. We propose two evolutionary algorithms (EAs) that use binary encoding and standard genetic operators adapted to the problem. The overall performance of both EA implementations is improved by a caching technique. In order to solve large-scale instances within reasonable time, the second EA also uses a newly designed heuristic to approximate the objective function value. The presented computational study indicates that the first EA reaches optimal solutions for all smaller and medium-size problem instances. The second EA obtains high-quality solutions for larger problem dimensions and provides solutions for large-scale instances that have not been addressed in the literature so far.
Genetic algorithms; Network design; Capacitated hub location problems; Transportation and telecommunication networks.
Journal site - full paperTwo metaheuristic methods for solving the $p$-ary transitive reduction (TR$_p$) problem are proposed: a genetic algorithm and a reduced variable neighborhood search method. Experiments were performed on a set of randomly generated instances. Presented results are the first experimental results in the literature so far for values $p>2$.
evolutionary algorithm, variable neighborhood search, transitive reduction, signal transduction networks, systems biology.
In this paper, we propose a new genetic encoding for well known Quadratic Assignment Problem (QAP). The new encoding schemes are implemented with appropriate objective function and modified genetic operators. The numerical experiments were carried out on the standard QAPLIB data sets known from the literature. The presented results show that in all cases proposed genetic algorithm reached known optimal solutions in reasonable time.
Genetic algorithm, evolutionary computation, combinatorial optimization, quadratic assignment problem.
Journal site - full paperThis paper considers the maximum betweenness problem. A new mixed integer linear programming (MILP) formulation is presented and validity of this formulation is given. Experimental results are performed on randomly generated instances from the literature. The results of CPLEX solver, based on the proposed MILP formulation, are compared with results obtained by total enumeration technique. The results show that CPLEX optimally solves instances of up to 30 elements and 60 triples in a short period of time.
Integer programming; Linear programming; Betweenness problem
Journal site - full paperIn this paper a variable neighborhood search (VNS) approach for the task assignment problem (TAP) is considered. Appropriate neighborhood scheme along with shaking operator and local search procedure are constructed specifically for this problem. The computational results are presented for the instances from the literature, and compared to optimal solutions obtained by the CPLEX solver and heuristic solutions generated by genetic algorithm. It can be seen that the proposed VNS approach reaches all optimal solutions in a quite short amount of computational time.
Task assignment, multiprocessor systems, variable neighborhood search, assignment problems, combinatorial optimization.
Abstract on the publisher siteRail transportation is very rich in terms of problems that can be modelled and solved using mathematical optimization techniques. Train scheduling problem as the most important part of a rail operating policy has a very significant impact on a rail company profit considering the fact that from the quality of a train timetable depends a flow of three most important resources on rail network: cars, locomotives and crews. The train timetabling problem aims at determining a periodic timetable for a set of trains that does not violate track capacities and satisfies some operational constraints. In this paper, we developed an integer programming approach for determining an optimal train schedule for a single, one-way track linking two major stations, with a number of intermediate stations between. The application has been tested on a realistic example suggested by the PE "Serbian Railways". Obtained results show a potential for a practical application of proposed approach.
rail transportation, scheduling, timetabling, integer programming
Abstract on the publisher siteIn this paper we consider the minimal doubly resolving sets problem (MDRSP) of graphs. We prove that the problem is NP-hard and give its integer linear programming formulation. The problem is solved by a genetic algorithm (GA) that uses binary encoding and standard genetic operators adapted to the problem. Experimental results include three sets of ORLIB test instances: crew scheduling, pseudo-boolean and graph coloring. GA is also tested on theoretically challenging large-scale instances of hypercubes and Hamming graphs. Optimality of GA solutions on smaller size instances has been verified by total enumeration. For several larger instances optimality follows from the existing theoretical results. The GA results for MDRSP of hypercubes are used by a dynamic programming approach to obtain upper bounds for the metric dimension of large hypercubes up to 2^90 nodes, that cannot be directly handled by the computer.
Minimal doubly resolving sets; Metric dimension; Genetic algorithms; Evolutionary approach; Hypercubes
Full paper on the publisher siteIn this paper we consider the NP-hard problem of determining the metric dimension of graphs. We propose a genetic algorithm (GA) that uses the binary encoding and the standard genetic operators adapted to the problem. The feasibility is enforced by repairing the individuals. The overall performance of the GA implementation is improved by a caching technique. Since the metric dimension problem up to now has been considered only theoretically, standard test instances for this problem do not exist. For that reason, we present the results of the computational experience on several sets of test instances for other NP-hard problems: pseudo boolean, crew scheduling and graph coloring. Testing on instances with up to 1534 nodes shows that GA relatively quickly obtains approximate solutions. For smaller instances, GA solutions are compared with CPLEX results. We have also modified our implementation to handle theoretically challenging large-scale classes of hypercubes and Hamming graphs. In this case the presented approach reaches optimal or best known solutions for hypercubes up to 131072 nodes and Hamming graphs up to 4913 nodes.
Graph theory; Metric dimension; Evolutionary approach
Full paper on the publisher siteThe problem that we will address here is the Super-Peer Selection Problem (SPSP). Two hybrid genetic algorithm (HGA) approaches are proposed for solving this NP-hard problem. The new encoding schemes are implemented with appropriate objective functions. Both approaches keep the feasibility of individuals by using specific representation and modified genetic operators. The numerical experiments were carried out on the standard data set known from the literature. The results of this test show that in 6 out of 12 cases HGAs outreached best known solutions so far, and that our methods are competitive with other heuristics.
Genetic algorithms, Evolutionary computation, %Peer-to-peer network topology, Combinatorial optimization.
Full paper on the publisher siteIn this article, the results achieved by applying GA-inspired heuristic on Uncapacitated Single Allocation Hub Location Problem (USAHLP) are discussed. Encoding scheme with two parts is implemented, with appropriate objective functions and modified genetic operators. The article presents several computational tests which have been conducted with ORLIB instances. Procedures described in related work round distance matrix elements to few digits, so rounding error is significant. Due to this fact, we developed exact total enumeration method for solving subproblem with fixed hubs, named Hub Median Single Allocation Problem (HMSAP). Computational tests demonstrate that GA-inspired heuristic reach all best solutions for USAHLP that are previously obtained and verified branch-and-bound method for HMSAP. Proposed heuristic successfully solved some instances that were unsolved before.
Genetic algorithms, Evolutionary computations, Hub location, USAHLP, HMSAP.
Full paper on the publisher siteThis paper exposes a research of the NP-hard Maximally Balanced Con- nected Partition problem (MBCP). The proposed solution comprises of a genetic algorithm (GA) that uses: binary representation, fine-grained tournament selection, one-point crossover, simple mutation with frozen genes and caching technique. In cases of unconnected partitions, penalty functions are successfully applied in or- der to obtain the feasible individuals. The effectiveness of presented approach is demonstrated on the grid graph instances and on random instances with up to 300 vertices and 2000 edges.
Balanced partitions, evolutionary computation, metaheuristics, combinatorial optimization
In this paper we consider the NP-hard problem of determining the strong metric dimension of graphs. The problem is solved by a genetic algorithm that uses binary encoding and standard genetic operators adapted to the problem. This represents the first attempt to solve this problem heuristically. We report experimental results for two special classes of ORLIB test instances: crew scheduling and graph coloring.
Strong metric dimension, genetic algorithms, evolutionary approach
Full paper on the publisher siteIn this paper a genetic algorithm (GA) for the task assignment problem (TAP) is considered.An integer representation with standard ge- netic operators is used. Computational results are presented for instances from the literature, and compared to optimal solutions obtained by the CPLEX solver. It can be seen that the proposed GA approach reaches 17 of 20 optimal solutions. The GA solutions are obtained in a quite a short amount of computational time.
evolutionary approach; genetic algorithms; assignment problems, multiprocessor systems, combinatorial optimization
Full paper on the publisher siteIn this paper the two-level Hierarchical Covering Location Problem - HCLP is considered. A new genetic algorithm for that problem is developed, including specific binary encoding with the new crossover and mutation operators that keep the feasibility of individuals. Modification that resolves the problem of frozen bits in genetic code is proposed and tested. Version of fine-grained tournament [5] was used as well as the caching GA technique [12] in order to improve computational performance. Genetic algorithm was tested and its parameters were adjusted on number of test examples and it performed well and proved robust in all cases. Results were verified by CPLEX.
Genetic Algorithms, Evolutionary computing, Location problem, Hierarchical location, Covering models
This paper deals with the Uncapacitated Single Allocation p-Hub Median Problem (USApHMP). Two genetic algorithm (GA) approaches are proposed for solving this NP-hard problem. New encoding schemes are implemented with appropriate objective functions. Both approaches keep the feasibility of individuals by using specific representation and modified genetic operators. The numerical experiments were carried out on the standard ORLIB hub data set. Both methods proved to be robust and efficient in solving USApHMP with up to 200 nodes and 20 hubs. The second GA approach achieves all previously known optimal solutions and achieves the best-known solutions on large-scale instances.
Genetic algorithms; Evolutionary computations; Location; p-Hub median problem; Single allocation
Full paper on the publisher siteIn this paper we present two new heuristic approaches to solve the Discrete Ordered Median Problem (DOMP). Described heuristic methods, named HGA1 and HGA2 are based on a hybrid of genetic algorithms (GA) and a generalization of the well-known Fast Interchange heuristic (GFI). In order to investigate the effect of encoding on GA performance, two different encoding schemes are implemented: binary encoding in HGA1, and integer representation in HGA2. If binary encoding is used (HGA1), new genetic operators that keep the feasibility of individuals are proposed. Integer representation keeps the individuals feasible by default, so HGA2 uses slightly modified standard genetic operators. In both methods, caching GA technique was integrated with the GFI heuristic to improve computational performance. The algorithms are tested on standard ORLIB p-median instances with up to 900 nodes. The obtained results are also compared with the results of existing methods for solving DOMP in order to assess their merits.
Genetic algorithms; Evolutionary computations; Discrete location
Full paper on the publisher site Additional computational resultsIn this paper we describe a genetic algorithm (GA) for the uncapacitated multiple allocation p-hub center problem (UMApHCP). Binary coding is used and genetic operators adapted to the problem are constructed and implemented in our GA. Computational results are presented for the standard hub instances from the literature. It can be seen that proposed GA approach reaches all solutions that are proved to be optimal so far. The solutions are obtained in a reasonable amount of computational time, even for problem instances of higher dimensions.
p-hub center problem; genetic algorithms; discrete location problems.
Full paper on the publisher siteHub location problems are widely used for network designing. Many variations of these problems can be found in the literature. In this paper we deal with the uncapacitated multiple allocation hub location problem (UMAHLP). We propose a genetic algorithm (GA) for solving UMAHLP that uses binary encoding and genetic operators adapted to the problem. Overall performance of GA implementation is improved by caching technique. We present the results of our computational experience on standard ORLIB instances with up to 200 nodes. The results show that GA approach quickly reaches all optimal solutions that are known so far and also gives results on some large-scale instances that were unsolved before.
Hub location problem, genetic algorithms, evolutionary computation, discrete location and assignment, network design, combinatorial optimization
We describe new results in developing of a satisfiability checker for probabilistic logic based on the genetic algorithm approach combined with a local search procedure. Computational experiences show that problems with 200 propositional letters can be solved. They are, to the best of our knowledge, the largest PSAT-problems reported in the literature.
This paper considers the problem of minimizing the response time for a given database workload by a proper choice of indexes. This problem is NP-hard and known in the literature as the Index Selection Problem (ISP). We propose a genetic algorithm (GA) for solving the ISP. Computational results of the GA on standard ISP instances are compared to branch-and- cut method and its initialisation heuristics and two state of the art MIP solvers: CPLEX and OSL. These results indicate good performance, reliability and efficiency of the proposed approach.
Full paper (PDF 188 KB) | Full paper on the publisher siteIn this paper is presented genetic algorithm (GA) for solving the uncapacitated network design problem (UNDP) with single sources and destinations for each commodity. UNDP is base in class of the network design problems, but it is still NP-hard. Robust GA implementation is additionally improved by caching GA technique. Computational results on instances up to 50 commodities, 100 nodes and 700 edges are reported.
This paper studies the behavior of the semidefinite programming method proposed by Helmberg, Rendl, Vanderbei and Wolkowicz on a special class of semidefmite programs obtained as relaxations of the symmetric traveling salesman problem (STSP. We propose modifications which reduce the computational time and improve numerical stability. Computational results for the STSP instances with dimensions up to 60 are reported.
This paper introduces a genetic algorithm for satisfiability problem in a probabilistic logic. A local search based improvement procedure is integrated in the algorithm. A test methodology is presented and some results are given. The results indicate that this approach could work well. Some directions for further research are described.
Full paper on the publisher siteThe simple plant location problem (SPLP) is considered and a genetic algorithm is proposed to solve this problem. By using the developed algorithm it is possible to solve SPLP with more than 1000 facility sites and customers. Computational results are presented and compared to dual based algorithms.
Simple plant location problem, genetic algorithms, combinatorial optimization. RAIRO RO Contents | Full paper | Go to RAIRO - Operations Research (RO) home page| SPLP - Original M instances win32 generator (ZIP - 33 KB) | SPLP - Original M instances win32 generator mirror (ZIP - 33 KB)
In the design of communication networks, robustness against failures in single links or nodes is an important issue. This paper proposes a new approach for the NP-complete edge-biconnectivity augmentation (E2AUG) problem, in which a given graph G (V;E) needs to be augmented by the cheapest possible set of edges AUG so that a single edge deletion does not disconnect G. The new approach is based on a preliminary reduction of the problem and a genetic algorithm (GA) using a binary vector to represent a set of augmenting edges and therefore a candidate solution. Two strategies are proposed to deal with infeasible solutions that do not lead to edge-biconnectivity. In the first, more traditional variant, infeasible solutions are detected and simply discarded. The second method is a hybrid approach that uses an effective heuristic to repair infeasible solutions by adding usually cheap edges to AUG until the graph augmented with AUG becomes edge-biconnected. The two GA-variants are empirically compared to each other and to another iterative heuristic for the E2AUG problem using instances involving up to 1270 edges.
Connectivity Augmentation Problems in Graphs | Full paper | Full paper on the publisher siteTomographic methods are often used to solve the geophysical inversion problem. This is the problem of determining the characteristics of an underground region by using measurement data. With a tomographic method, the pictures of the physical properties in the region between pairs of boreholes can be reconstructed. In this paper, we apply genetic algorithms to cross-hole seismic line-integral data. These data can be generated by the transmission problem through the cross-hole region using seismic energy. Some test-examples for measuring the performance of the applied genetic algorithms are presented. The obtained results are promising.
Genetic algorithm, tomography, geophysical inversion problem.
Full paper - PDF (62 KB)In this paper we optimize run-time performance of the genetic algorithm by caching. We are caching the genetic algorithm procedure for evaluation of an objective function. Least Recently Used (LRU) caching strategy is used, that is simple but effective. This approach is good for problems that have a relatively small length of item string, and a large evaluation time of objective function. We present results of the caching to genetic algorithm for solving one such problem - the simple plant location problem (SPLP).
Genetic algorithms, caching, simple plant location problem
Go to Journal home page | Vol. 18, No 3. AbstractsThis paper investigates the applicability of the improvement of simple genetic algorithm (SGA) method for solving the uncapacitated warehouse location problem (UWLP). Function for computing the item’s objective value is improved depending upon the number of established warehouses. It is efficiently implemented, giving excellent results in specified environment. Mutation rate is also changed and now depends on test problem size. Duplicate item strings in population are discarded, which makes the population more diversified. Overall performance of implementation is finally tuned by caching SGA. Through caching technique relatively smaller profit in performance is obtained when compared to previous techniques, but it is a general technique, and can be directly applied to other problems, not only to UWLP. Computational experience with given problem examples indicates that, when compared to code in [1], the implementation of the modified algorithm is faster several times. For large size test problems the increase of computational speed may even exceed factor 10, and quality of obtained solutions is also significantly better.
Genetic Algorithms, Uncapacitated Warehouse Location Problem.
The paper describes one method of implementation of LISP interpreter to transputers. Developed interpreter contains standard functions common for almost all LISP versions. Architecture is binary tree message passing. Implementation was developed on transputer parallel C language (ANSI C with procedures for interprocess or communications and synchronization). Part intended for evaluation of functions (expressions) was parallelized, but I/O operation and parsing were sequential. This is caused by the technical limitations of transputer systems, because I/O operations can executed only by first transputer, and interprocess or communication is slow. Maxima increase in speed equals 6.5 times, on transputer system with 17 transputers T800, by as compared to single transputer T800. That increase in speed is obtained for recursive problems demanding much computing. Small increase in speed is obtained for problems with more I/O operations.
Last update: 08. 05. 2012.