NeuroGenetic approach for combinatorial optimization: an exploratory analysis

Given the NP-Hard nature of many optimization problems, it is often impractical to obtain optimal solutions to large-scale problems in reasonable computing time. For this reason, heuristic and metaheuristic search approaches are used to obtain good solutions fast. However, these techniques often struggle to develop a good balance between local and global search. In this paper we propose a hybrid metaheuristic approach which we call the NeuroGenetic approach to search for good solutions for these large scale optimization problems by at least partially overcoming this challenge. The proposed NeuroGenetic approach combines the Augmented Neural Network (AugNN) and the Genetic Algorithm (GA) search approaches by interleaving the two. We chose these two approaches to hybridize, as they offer complementary advantages and disadvantages; GAs are very good at searching globally, while AugNNs are more proficient at searching locally. The proposed hybrid strategy capitalizes on the strong points of each approach while avoiding their shortcomings. In the paper we discuss the issues associated with the feasibility of hybridizing these two approaches and propose an interleaving algorithm. We also provide empirical evidence demonstrating the effectiveness of the proposed approach.     

Review of combinatorial problems induced by spatial forest harvesting planning

In the last two decades forest planning and management has become very much focused on spatially oriented decisions, due to the introduction of spatial details, such as road building, and environmental concerns, like wildlife protection, biodiversity, reducing erosion and improving water quality. This has led to modeling transformations and extensions in planning forest activities, as mixed integer decision variables are necessary to account for spatial restrictions. These new models are much harder to solve due to the added combinatorial complexity. In this paper, we discuss issues of modeling spatial criteria, as well as algorithms that have been developed to solve them, both heuristic and exact. We present these results as they have evolved in a state-of-the-art structure.     

A multi-objective evolutionary algorithm for facility dispersion under conditions of spatial uncertainty

Avoiding concentration or saturation of activities is fundamental in many environmental and urban planning contexts. Examples include dispersing retail and restaurant outlets, sensitivity to impacts in forest utilization, spatial equity of waste disposal, ensuring public safety associated with noxious facilities, and strategic placement of military resources, among others. Dispersion models have been widely applied to ensure spatial separation between activities or facilities. However, existing approaches rely on deterministic approaches that ignore issues of spatial data uncertainty, which could lead to poor decision making. To address data uncertainty issues in dispersion modelling, a multi-objective approach that explicitly accounts for spatial uncertainty is proposed, enabling the impacts of uncertainty to be evaluated with statistical confidence. Owing to the integration of spatial uncertainty, this dispersion model is more complex and computationally challenging to solve. In this paper we develop a multi-objective evolutionary algorithm to address the computational challenges posed. The proposed heuristic incorporates problem-specific spatial knowledge to significantly enhance the capability of the evolutionary algorithm for solving this problem. Empirical results demonstrate the performance superiority of the developed approach in supporting facility and service planning.     

Methods based on data envelopment analysis for deriving group priorities in analytic hierarchy process

In recent years, group decision making has become one of the important issues in multiple criteria decision making, and analytic hierarchy process (AHP) is considered an appropriate method when dealing with this kind of problems. Many different approaches for attaining a group valuation in AHP have been developed. The applications most commonly employ the weighted geometric mean method. In the paper, we focus on the group AHP methods, which are based on the data envelopment analysis (DEA). First we discuss two methods for deriving a group priority vector: Wang and Chin’s DEA group method and Hosseinian et al.’s DEA-WDGD. Further, we propose a new WGMDEA method and compare all three methods with the WGMM on theoretical examples and on a real case study. The objective of the case study is to examine the current state of forest owners’ cooperatives. An analysis of the influence of forest owners’ cooperatives on private forest management in Slovenia was put forward. The A’WOT analysis, which is a combined method of AHP and SWOT analysis, an approach for identifying the strengths, weaknesses, opportunities and threats of the object under consideration, was performed.     

A graph-based hyper-heuristic for educational timetabling problems

This paper presents an investigation of a simple generic hyper-heuristic approach upon a set of widely used constructive heuristics (graph coloring heuristics) in timetabling. Within the hyper-heuristic framework, a tabu search approach is employed to search for permutations of graph heuristics which are used for constructing timetables in exam and course timetabling problems. This underpins a multi-stage hyper-heuristic where the tabu search employs permutations upon a different number of graph heuristics in two stages. We study this graph-based hyper-heuristic approach within the context of exploring fundamental issues concerning the search space of the hyper-heuristic (the heuristic space) and the solution space. Such issues have not been addressed in other hyper-heuristic research. These approaches are tested on both exam and course benchmark timetabling problems and are compared with the fine-tuned bespoke state-of-the-art approaches. The results are within the range of the best results reported in the literature. The approach described here represents a significantly more generally applicable approach than the current state of the art in the literature. Future work will extend this hyper-heuristic framework by employing methodologies which are applicable on a wider range of timetabling and scheduling problems.     

Enhancing the performance of constraint programming through the introduction of linear programming

Constraint Programming (CP) has been successful in a number of combinatorial search and discrete optimisation problems. Yet other more traditional approaches, such as Integer Programming (IP), can still give a better performance on the same problem types. Central to IP's success is its reliance on a fast Linear Programming (LP) solver providing solutions during the search to the corresponding relaxed problems. These solutions are used to guide the search within IP as well as a means of detecting infeasibility and integrality. This paper shows that there is scope also to include LP within the CP framework, in order to similarly guide the CP search. The problems examined here are one for which CP on its own had proved markedly inferior to IP. Hence a hybrid solver based on the CP search and using an LP solver is configured and run on these problems. The outcome shows that using the LP solver within the CP search is a valuable addition to the available search strategies. An improved performance over the CP-only strategies is obtained and, further, comparable results are obtained to those from IP. Overall, CP+LP can be considered as a more robust approach than either CP or IP on their own on a variety of combinatorial search problems.     

Meta-heuristics for dynamic lot sizing: A review and comparison of solution approaches

Proofs from complexity theory as well as computational experiments indicate that most lot sizing problems are hard to solve. Because these problems are so difficult, various solution techniques have been proposed to solve them. In the past decade, meta-heuristics such as tabu search, genetic algorithms and simulated annealing, have become popular and efficient tools for solving hard combinatorial optimization problems. We review the various meta-heuristics that have been specifically developed to solve lot sizing problems, discussing their main components such as representation, evaluation, neighborhood definition and genetic operators. Further, we briefly review other solution approaches, such as dynamic programming, cutting planes, Dantzig–Wolfe decomposition, Lagrange relaxation and dedicated heuristics. This allows us to compare these techniques. Understanding their respective advantages and disadvantages gives insight into how we can integrate elements from several solution approaches into more powerful hybrid algorithms. Finally, we discuss general guidelines for computational experiments and illustrate these with several examples.     

Particle swarm optimization for the Steiner tree in graph and delay-constrained multicast routing problems

This paper presents the first investigation on applying a particle swarm optimization (PSO) algorithm to both the Steiner tree problem and the delay constrained multicast routing problem. Steiner tree problems, being the underlining models of many applications, have received significant research attention within the meta-heuristics community. The literature on the application of meta-heuristics to multicast routing problems is less extensive but includes several promising approaches. Many interesting research issues still remain to be investigated, for example, the inclusion of different constraints, such as delay bounds, when finding multicast trees with minimum cost. In this paper, we develop a novel PSO algorithm based on the jumping PSO (JPSO) algorithm recently developed by Moreno-Perez et al. (Proc. of the 7th Metaheuristics International Conference, 2007), and also propose two novel local search heuristics within our JPSO framework. A path replacement operator has been used in particle moves to improve the positions of the particle with regard to the structure of the tree. We test the performance of our JPSO algorithm, and the effect of the integrated local search heuristics by an extensive set of experiments on multicast routing benchmark problems and Steiner tree problems from the OR library. The experimental results show the superior performance of the proposed JPSO algorithm over a number of other state-of-the-art approaches.     

Lagrangean duals and exact solution to the capacitated p-center problem

In this work, we address the capacitated p-center problem (CpCP). We study two auxiliary problems, discuss their relation to CpCP, and analyze the lower bounds obtained with two different Lagrangean duals based on each of these auxiliary problems. We also compare two different strategies for solving exactly CpCP, based on binary search and sequential search, respectively. Various data sets from the literature have been used for evaluating the performance of the proposed algorithms.     

Solving the short-term electrical generation scheduling problem by an adaptive evolutionary approach

In this paper, we introduce an adaptive evolutionary approach to solve the short-term electrical generation scheduling problem (STEGS). The STEGS is a hard constraint satisfaction optimization problem. The algorithm includes various strategies proposed in the literature to tackle hard problems with constraints such as: the representation used a non-binary coding scheme that drastically reduces the search space compared with the traditional evolutionary approaches. Specialized operators are especially designed for this problem and for this kind of representation, which also includes a local search procedure. Furthermore, the algorithm is guided by an adaptive parameter control strategy. We used some very well known benchmarks for STEGS to evaluate our approach. The results are very encouraging and we have obtained new better values for all the systems tested. Our aim here is to show that evolutionary approaches can be considered as good techniques to be used to solve real-world highly constrained problems.     

Experiments with successive quadratic programming algorithms

There are many variants of successive quadratic programming (SQP) algorithms. Important issues include: the choice of either line search or trust region strategies; the QP formulation to be used; and how the QP is to be solved. Here, we consider the QP's proposed by Fletcher and Powell and discuss a specialized reduced-gradient procedure for solving them. A computer implementation is described, and the various options are compared on some well-known test problems. Factors influencing robustness and speed are identified.     

Parameter adaptive harmony search algorithm for unimodal and multimodal optimization problems

This paper presents a parameter adaptive harmony search algorithm (PAHS) for solving optimization problems. The two important parameters of harmony search algorithm namely Harmony Memory Consideration Rate (HMCR) and Pitch Adjusting Rate (PAR), which were either kept constant or the PAR value was dynamically changed while still keeping HMCR fixed, as observed from literature, are both being allowed to change dynamically in this proposed PAHS. This change in the parameters has been done to get the global optimal solution. Four different cases of linear and exponential changes have been explored. The change has been allowed during the process of improvization. The proposed algorithm is evaluated on 15 standard benchmark functions of various characteristics. Its performance is investigated and compared with three existing harmony search algorithms. Experimental results reveal that proposed algorithm outperforms the existing approaches when applied to 15 benchmark functions. The effects of scalability, noise, and harmony memory size have also been investigated on four approaches of HS. The proposed algorithm is also employed for data clustering. Five real life datasets selected from UCI machine learning repository are used. The results show that, for data clustering, the proposed algorithm achieved results better than other algorithms.     

A computational study of the one‐dimensional parabolic equation subject to nonclassical boundary specifications

Certain problems arising in engineering are modeled by nonstandard parabolic initial‐boundary value problems in one space variable, which involve an integral term over the spatial domain of a function of the desired solution. Hence, in the past few years interest has substantially increased in the solutions of these problems. As a result numerous research papers have also been devoted to the subject. Although considerable amount of work has been done in the past, there is still a lack of a completely satisfactory computational scheme. Also, there are some cases that have not been studied numerically yet. In the current article several approaches for the numerical solution of the one‐dimensional parabolic equation subject to the specification of mass, which have been considered in the literature, are reported. Finite difference methods have been proposed for the numerical solution of the new nonclassic boundary value problem. To investigate the performance of the proposed algorithm, we consider solving a test problem. © 2005 Wiley Periodicals, Inc. Numer Methods Partial Differential Eq, 2006     

Global and Local Search Algorithms for Concave Cost Transshipment Problems

Traditionally, the minimum cost transshipment problems have been simplified as linear cost problems, which are not practical in real applications. Recently, some advanced local search algorithms have been developed that can directly solve concave cost bipartite network problems. However, they are not applicable to general transshipment problems. Moreover, the effectiveness of these modified local search algorithms for solving general concave cost transshipment problems is doubtful. In this research, we propose a global search algorithm for solving concave cost transshipment problems. Effecient methods for encoding, generating initial populations, selection, crossover and mutation are proposed, according to the problem characteristics. To evaluate the effectiveness of the proposed global search algorithm, four advanced local search algorithms based on the threshold accepting algorithm, the great deluge algorithm, and the tabu search algorithm, are also developed and are used for comparison purpose. To assist with the comparison of the proposed algorithms, a randomized network generator is designed to produce test problems. All the tests are performed on a personal computer. The results indicate that the proposed global search algorithm is more effective than the four advanced local algorithms, for solving concave cost transshipment problems.     

A sequential LCP method for bilevel linear programming

In this paper, we discuss an SLCP algorithm for the solution of Bilevel Linear Programs (BLP) which consists of solving a sequence of Linear Complementarity Problems (LCP) by using a hybrid enumerative method. This latter algorithm incorporates a number of procedures that reduce substantially the search for a solution of the LCP or for showing that the LCP has no solution. Computational experience with the SLCP algorithm shows that it performs quite well for the solution of small- and medium-scale BLPs with sparse structure. Furthermore, the algorithm is shown to be more efficient than a branch-and-bound method for solving the same problems.     

Routing and scheduling in a flexible job shop by tabu search

A hierarchical algorithm for the flexible job shop scheduling problem is described, based on the tabu search metaheuristic. Hierarchical strategies have been proposed in the literature for complex scheduling problems, and the tabu search metaheuristic, being able to cope with different memory levels, provides a natural background for the development of a hierarchical algorithm. For the case considered, a two level approach has been devised, based on the decomposition in a routing and a job shop scheduling subproblem, which is obtained by assigning each operation of each job to one among the equivalent machines. Both problems are tackled by tabu search. Coordination issues between the two hierarchical levels are considered. Unlike other hierarchical schemes, which are based on a one-way information flow, the one proposed here is based on a two-way information flow. This characteristic, together with the flexibility of local search strategies like tabu search, allows to adapt the same basic algorithm to different objective functions. Preliminary computational experience is reported.     

Dynamic function optimisation with hybridised extremal dynamics

Dynamic function optimisation is an important research area because many real-world problems are inherently dynamic in nature. Over the years, a wide variety of algorithms have been proposed to solve dynamic optimisation problems, and many of these algorithms have used the Moving Peaks (MP) benchmark to test their own capabilities against other approaches. This paper presents a detailed account of our hybridised Extremal Optimisation (EO) approach that has achieved hitherto unsurpassed results on the three standardised scenarios of the MP problem. Several different components are used in the hybrid EO, and it has been shown that a large proportion of the quality of its outstanding performance is due to the local search component. In this paper, the behaviour of the local search algorithms used is analysed, and the roles of other components are discussed. In the concluding remarks, the generalisation ability of this method and its wider applicability are highlighted.     

A simulated annealing hyper-heuristic methodology for flexible decision support

Most of the current search techniques represent approaches that are largely adapted for specific search problems. There are many real-world scenarios where the development of such bespoke systems is entirely appropriate. However, there are other situations where it would be beneficial to have methodologies which are generally applicable to more problems. One of our motivating goals for investigating hyper-heuristic methodologies is to provide a more general search framework that can be easily and automatically employed on a broader range of problems than is currently possible. In this paper, we investigate a simulated annealing hyper-heuristic methodology which operates on a search space of heuristics and which employs a stochastic heuristic selection strategy and a short-term memory. The generality and performance of the proposed algorithm is demonstrated over a large number of benchmark datasets drawn from two very different and difficult problems, namely; course timetabling and bin packing. The contribution of this paper is to present a method which can be readily (and automatically) applied to different problems whilst still being able to produce results on benchmark problems which are competitive with bespoke human designed tailor made algorithms for those problems.     

An efficient grouping genetic algorithm for U-shaped assembly line balancing problems with maximizing production rate

U-type assembly line is one of the important tools that may increase companies’ production efficiency. In this study, two different modeling approaches proposed for the assembly line balancing problems have been used in modeling type-II U-line balancing problems, and the performances of these models have been compared with each other. It has been shown that using mathematical formulations to solve medium and large size problem instances is impractical since the problem is NP-hard. Therefore, a grouping genetic and simulated annealing algorithms have been developed, and a particle swarm optimization algorithm is adapted to compare with the proposed methods. A special crossover operator that always obtains feasible offspring has been suggested for the proposed grouping genetic algorithm. Furthermore, a local search procedure based on problem-specific knowledge was applied to increase the intensification of the algorithm. A set of well-known benchmark instances was solved to evaluate the effectiveness of the proposed and existing methods. Results showed that while the mathematical formulations can only be used to solve small size instances, metaheuristics can obtain high quality solutions for all size problem instances within acceptable CPU times. Moreover, grouping genetic algorithm has been found to be superior to the other methods according to the number of optimal solutions, or deviations from the lower bound values.