Search

This paper presents a mathematical stochastic methodology for transit route network optimization. The goal is to provide an effective computational tool for the optimization of a large-scale transit route network to minimize transfers with reasonable route directness while maximizing service coverage. The methodology includes representation of transit route network solution search spaces, representation of transit route and network constraints, and a stochastic search scheme based on an integrated simulated annealing and genetic algorithm solution search method. The methodology has been implemented as a computer program, tested using previously published results, and applied to a large-scale realistic network optimization problem. [ABSTRACT FROM AUTHOR]

In this paper, a hybrid Taguchi-genetic algorithm (HTGA) is applied to solve the problem of tuning both network structure and parameters of a feedforward neural network. The HTGA approach is a method of combining the traditional genetic algorithm (TGA), which has a powerful global exploration capability, with the Taguchi method, which can exploit the optimum offspring. The Taguchi method is inserted between crossover and mutation operations of a TGA. Then, the systematic reasoning ability of the Taguchi method is incorporated in the crossover operations to select the better genes to achieve crossover, and consequently enhance the genetic algorithms. Therefore, the HTGA approach can be more robust, statistically sound, and quickly convergent. First, the authors evaluate the performance of the presented HTGA approach by studying some global numerical optimization problems. Then, the presented HTGA approach is effectively applied to solve three examples on forecasting the sunspot numbers, tuning the associative memory, and solving the XOR problem. The numbers of hidden nodes and the links of the feedforward neural network are chosen by increasing them from small numbers until the learning performance is good enough. As a result, a partially connected feedforward neural network can be obtained after tuning. This implies that the cost of implementation of the neural network can be reduced. In these studied problems of tuning both network structure and parameters of a feedforward neural network, there are many parameters and numerous local optima so that these studied problems are challenging enough for evaluating the performances of any proposed GA-based approaches. The computational experiments show that the presented HTGA approach can obtain better results than the existing method reported recently in the literature. [ABSTRACT FROM AUTHOR]

We discuss two approximation paradigms that were used to construct many approximation algorithms during the last two decades, the primal-dual schema and the local ratio technique. Recently, primal-dual algorithms were devised by first constructing a local ratio algorithm and then transforming it into a primal-dual algorithm. This was done in the case of the $2$-approximation algorithms for the feedback vertex set problem and in the case of the first primal-dual algorithms for maximization problems. Subsequently, the nature of the connection between the two paradigms was posed as an open question by Williamson [Math. Program., 91 (2002), pp. 447--478]. In this paper we answer this question by showing that the two paradigms are equivalent. [ABSTRACT FROM AUTHOR]

Abstract: Trade-off (aka Pareto) curves are typically used to represent the trade-off among different objectives in multiobjective optimization problems. Although trade-off curves are exponentially large for typical combinatorial optimization problems (and infinite for continuous problems), it was observed in Papadimitriou and Yannakakis [On the approximability of trade-offs and optimal access of web sources, in: Proc. 41st IEEE Symp. on Foundations of Computer Science, 2000] that there exist polynomial size approximations for any , and that under certain general conditions, such approximate -Pareto curves can be constructed in polynomial time. In this paper we seek general-purpose algorithms for the efficient approximation of trade-off curves using as few points as possible. In the case of two objectives, we present a general algorithm that efficiently computes an -Pareto curve that uses at most 3 times the number of points of the smallest such curve; we show that no algorithm can be better than 3-competitive in this setting. If we relax to any , then we can efficiently construct an -curve that uses no more points than the smallest -curve. With three objectives we show that no algorithm can be c-competitive for any constant c unless it is allowed to use a larger value. We present an algorithm that is 4-competitive for any . We explore the problem in high dimensions and give hardness proofs showing that (unless P=NP) no constant approximation factor can be achieved efficiently even if we relax by an arbitrary constant. [Copyright &y& Elsevier]

Clustering is inherently a difficult problem, both with respect to the construction of adequate objective functions as well as to the optimization of the objective functions. In this paper, we suggest an objective function called the Weighted Sum Validity Function (WSVF), which is a weighted sum of the several normalized cluster validity functions. Further, we propose a Hybrid Niching Genetic Algorithm (HNGA), which can be used for the optimization of the WSVF to automatically evolve the proper number of clusters as well as appropriate partitioning of the data set. Within the HNGA, a niching method is developed to preserve both the diversity of the population with respect to the number of clusters encoded in the individuals and the diversity of the subpopulation with the same number of clusters during the search. In addition, we hybridize the niching method with the k-means algorithm. In the experiments, we show the effectiveness of both the HNGA and the WSVF. In comparison with other related genetic clustering algorithms, the HNGA can consistently and efficiently converge to the best known optimum corresponding to the given data in concurrence with the convergence result. The WSVF is found generally able to improve the confidence of clustering solutions and achieve more accurate and robust results. [ABSTRACT FROM AUTHOR]

This paper presents a new strongly polynomial cut canceling algorithm for minimum cost submodular flow. The algorithm is a generalization of our similar cut canceling algorithm for ordinary min-cost flow. The algorithm scales a relaxed optimality parameter and creates a second, inner relaxation that is a kind of submodular max flow problem. The outer relaxation uses a novel technique for relaxing the submodular constraints that allows our previous proof techniques to work. The algorithm uses the min cuts from the max flow subproblem as the relaxed most positive cuts it chooses to cancel. We show that this algorithm needs to cancel only ${\mathrm O}(n^3)$ cuts per scaling phase, where $n$ is the number of nodes. Furthermore, we show how to slightly modify this algorithm to get a strongly polynomial running time. Finally, we briefly show how to extend this algorithm to the separable convex cost case and that the same technique can be used to construct a polynomial time maximum mean cut canceling algorithm for submodular flow. [ABSTRACT FROM AUTHOR]

Abstract: Research on a new metaheuristic for optimization is often initially focused on proof-of-concept applications. It is only after experimental work has shown the practical interest of the method that researchers try to deepen their understanding of the method''s functioning not only through more and more sophisticated experiments but also by means of an effort to build a theory. Tackling questions such as “how and why the method works’’ is important, because finding an answer may help in improving its applicability. Ant colony optimization, which was introduced in the early 1990s as a novel technique for solving hard combinatorial optimization problems, finds itself currently at this point of its life cycle. With this article we provide a survey on theoretical results on ant colony optimization. First, we review some convergence results. Then we discuss relations between ant colony optimization algorithms and other approximate methods for optimization. Finally, we focus on some research efforts directed at gaining a deeper understanding of the behavior of ant colony optimization algorithms. Throughout the paper we identify some open questions with a certain interest of being solved in the near future. [Copyright &y& Elsevier]

This paper presents an improved genetic algorithm with multiplier updating (IGA•MU) to solve power economic dispatch (PED) problems of units with valve-point effects and multiple fuels. The proposed IGA•MU integrates the improved genetic algorithm (IGA) and the multiplier updating (MU). The IGA equipped with an improved evolutionary direction operator and a migration operation can efficiently search and actively explore solutions, and the MU is employed to handle the equality and inequality constraints of the PED problem. Few FED problem-related studies have seldom addressed both valve-point loadings and change fuels. To show the advantages of the proposed algorithm, which was applied to test FED problems with one example considering valve-point effects, one example considering multiple fuels, and one example addressing both valve-point effects and multiple fuels. Additionally, the proposed algorithm was compared with previous methods and the conventional genetic algorithm (CGA) with the MU (CGA•MU), revealing that the proposed IGA•MU is more effective than previous approaches, and applies the realistic PED problem more efficiently than does the CGA•MU. Especially, the proposed algorithm is highly promising for the large-scale system of the actual FED operation. [ABSTRACT FROM AUTHOR]

In this paper, efficient reinforcement learning through dynamic-form symbiotic evolution (DSE) is proposed for solving nonlinear control problems. Compared with traditional symbiotic evolution, DSE uses the sequential search-based dynamic evolution (SSDE) method to generate an initial population and to determine dynamic mutation points. Therefore, better chromosomes will be initially generated while better mutation points will be determined for performing dynamic mutation. The proposed DSE design method was applied to different control systems, including the cart-pole balancing system and the water bath temperature control system, and control problems were simulated on these systems. The proposed DSE method was verified to be efficient and superior for solving these control problems and from comparisons with some traditional genetic algorithms. [ABSTRACT FROM AUTHOR]

Abstract: Vehicle routing encompasses a whole class of complex optimization problems that target the derivation of minimum total cost routes for a number of resources (vehicles) located at a central point (depot) in order to service efficiently a number of demand points (customers). Several practical issues in the food industry, involving both production and transportation decisions are modelled as VRP instances and are hard combinatorial problems in the strong sense (NP-hard). For such problems, metaheuristics, i.e., general solution procedures that explore the solution space to identify high quality solutions and often embed some standard route construction and improvement algorithms have been proposed. This paper surveys the recent research efforts on metaheuristic solution methodologies for the standard and most widely studied version of the Vehicle Routing Problem (VRP), i.e., the Capacitated VRP. The computational performance of each metaheuristic is presented for the 14 benchmark instances of Christofides et al. [Christofides, N., Mingozzi, A., & Toth, P. (1979). Combinatorial optimization (p. 315). Chichester: Wiley]. [Copyright &y& Elsevier]

Abstract: Combining Reproducing Kernel Particle Method (RKPM) with the proposed Multi-Family Genetic Algorithm (MFGA), a novel approach to continuum-based shape optimization problems is brought forward in this paper. Taking full advantage of the features of meshfree method and the merits of MFGA, the new method solves shape optimization problems in such a unique way that remeshing is avoided and particularly the computation burden and errors caused by sensitivity analysis are eliminated completely. The effectiveness, versatility and performance of the proposed approach are demonstrated via three 2-D numerical examples. [Copyright &y& Elsevier]

This paper describes the synthesis method of linear array geometry with minimum sidelobe level and null control using the particle swarm optimization (PSO) algorithm. The PSO algorithm is a newly discovered, high-performance evolutionary algorithm capable of solving general N-dimensional, linear and nonlinear optimization problems. Compared to other evolutionary methods such as genetic algorithms and simulated annealing, the P50 algorithm is much easier to understand and implement and requires the least of mathematical preprocessing. The array geometry synthesis is first formulated as an optimization problem with the goal of sidelobe level (SLL) suppression and/or null placement in certain directions, and then solved by the PSO algorithm for the optimum element locations. Three design examples are presented that illustrate the use of the PSO algorithm, and the optimization goal in each example is easily achieved. The results of the P50 algorithm are validated by comparing with results obtained using the quadratic programming method (QPM). [ABSTRACT FROM AUTHOR]

Abstract: This paper introduces an ant colony search algorithm (ACSA) to solve the optimal network reconfiguration problem for power loss reduction. The ACSA is a relatively new and powerful intelligence evolution method for solving optimization problems. It is a population-based approach that uses exploration of positive feedback as well as greedy search. The ACSA was inspired from natural behavior of the ant colonies on how they find the food source and bring them back to their nest by building the unique trail formation. By applying the ACSA, the near-optimal solution to the network reconfiguration problem can be effectively achieved. The ACSA applies the state transition rule, local pheromone-updating rule, and global pheromone-updating rule to facilitate the computation. The network reconfiguration problem of one three-feeder distribution system from the literature and one practical distribution network of Taiwan Power Company (TPC) are, respectively, solved using the proposed ACSA method, the genetic algorithm (GA), and the simulated annealing (SA). Numerical results show that the proposed method is better than the other two methods. [Copyright &y& Elsevier]

An optimization method, such as the steepest gradient methods, could not easily obtain globally optimum solutions for devising antenna design parameters that allow the antenna to simultaneously improve multiple performances such as gain, sidelobe level, and input impedance. The genetic algorithm (GA) is suitable for empirically solving optimization problems and is effective in designing an antenna. In particular, this method can solve the multi- objective optimization problem using various Pareto-optimal solutions in an extremely efficient manner. In this paper, the Pareto GA, by which various Pareto-optimal solutions for each objective function (performance) can be obtained in a single trial of a numerical simulation and which enables the selection of parameters in accordance with the design requirement, is applied to the multiobjective optimization design of the Yagi-Uda antenna. The effectiveness of the Pareto GA was demonstrated by comparing the performances obtained by the Pareto GA with those of the previously reported values, which were obtained by the conventional GA, and with the values of the design benchmark reference. [ABSTRACT FROM AUTHOR]

Abstract: As datasets are becoming larger, a solution to the problem of variable prediction, this problem is becoming harder. The problem is to define which subset of variables produces optimum predictions. The example studied aims to predict the chromatographic retention of 83 basic drugs on a Unisphere PBD column at pH 11.7 using 1272 molecular descriptors. The goal of this paper is to compare the relative performance of recently developed data mining methods, specifically classification and regression trees (CART), stochastic gradient boosting for tree-based models (Treeboost), and random forests (RF), with common statistical techniques in chemometrics; and genetic algorithms on multiple linear regression (GA-MLR), uninformative variable elimination partial least squares (UVE-PLS), and SIMPLS. The comparison will be performed primarily on predictive performance, but also on the variables found to be most important for the predictions. The results of this study indicated that, individually, GA-MLR (R 2=0.93) outperformed all models. Further analysis found that a combination approach of GA-MLR and Treeboost (R 2=0.98) further improved these results. [Copyright &y& Elsevier]

Many departments of transportation have recently started to utilize innovative contracting methods that provide new incentives for improving construction quality. These emerging contracts place an increasing pressure on decision makers in the construction industry to search for an optimal resource utilization plan that minimizes construction cost and time while maximizing its quality. This paper presents a multiobjective optimization model that supports decision makers in performing this challenging task. The model is designed to transform the traditional two-dimensional time-cost tradeoff analysis to an advanced three-dimensional time-cost-quality trade-off analysis. The model is developed as a multiobjective genetic algorithm to provide the capability of quantifying and considering quality in construction optimization. An application example is analyzed to illustrate the use of the model and demonstrate its capabilities in generating and visualizing optimal tradeoffs among construction time, cost, and quality. [ABSTRACT FROM AUTHOR]

The dominating contribution of interconnect to system performance has made it critical to plan the resources of the buffers and routes in the early stage of the layout In this paper, we integrate floorplanning with buffer insertion for performance-driven design processes. We devise a two-step method to evaluate the feasible buffer insertion sites, which can improve the efficiency of the buffer-planning algorithm. By partitioning all empty spaces into blocks in the packing process, the buffer allocation is handled as an integral part of the floorplanning. Our buffer-planning algorithm maps the buffers into tiles with consideration of routing congestion. In this approach, we construct a distribution graph to model the possible routes. The buffer allocation method is performed on the updated distribution graph to find the buffer locations with their respective congestion costs. The method is based on a simulated annealing approach, which is composed of multiple phases to speed up the optimization. Since there is more freedom with floorplan optimization, the empirical results demonstrate better performance. [ABSTRACT FROM AUTHOR]

This paper discusses the design of a parallel genetic algorithm to generate solutions to multi-objective problems. The algorithm uses multiple optimization criteria, independent cross-pollinating populations, and handles multiple hard constraints. Individuals in the population consist of multiple chromosomes. The complexity of the algorithm is the number of generations processed times O(N2) where N is the total number of individuals used for path generation on any of the optimizations. The results of initial empirical studies on the effects of pollination and recommendations for possible future work are presented. [ABSTRACT FROM AUTHOR]

A methodology is presented for the design synthesis of metamaterial ferrites, or metaferrites, that retain their desirable magnetic properties at frequencies above 1 GHz. The design syn- thesis is accomplished by optimizing a high impedance frequency selective surface (HZ-FSS) structure via a genetic algorithm (GA) for the desired effective permeability of an equivalent magnetic substrate backed by a perfect electric conductor ground plane. The ability to optimize the design parameters of these HZ-FSS structures allows for the possibility of synthesizing low-loss dispersive metaferrites with either a positive or a negative real part of the effective permeability at the desired operating frequency band. The results presented in this paper demonstrate five possible metaferrite designs: two with the associated real and imaginary permeabilities for use as low-loss magnetic materials, and three designs for use as absorbing materials. [ABSTRACT FROM AUTHOR]

In this paper, a newly developed optimization algorithm, called the dynamic encoding algorithm for searches (DEAS), is introduced and applied to the parameter identification of an induction motor for vector control and fault detection. Digital simulations are conducted on startup with no load and normal operation with load perturbations. DEAS is compared with the continuous-time prediction error method and the genetic algorithm via identification performance using the startup signals. The capability of onload identification using the proposed technique is also verified with transient signals. Consequently, DEAS is shown to locate more precise parameter values than both the compared methods especially with much faster execution time than the genetical algorithm. [ABSTRACT FROM AUTHOR]

Abstract: This paper presents a two-stage hybrid optimization algorithm based on a modified genetic algorithm. In the first stage, a global search is carried out over the design search space using a modified GA. The proposed modifications on the basic GA includes dynamically changing the population size throughout the GA process and the use of different forms of the penalty function in constraint handling. In the second stage, a local search based on the genetic algorithm solution is executed using a discretized form of Hooke and Jeeves method. The hybrid algorithm and the modifications to the basic genetic algorithm are examined on the design optimization of reinforced concrete flat slab buildings. The objective function is the total cost of the structure including the cost of concrete, formwork, reinforcement and foundation excavation. The constraints are defined according to the British Standard BS8110 for reinforced concrete structures. Comparative studies are presented to study the effect of different parameters of handling genetic algorithm on the optimized flat slab building. It has been shown that the proposed hybrid algorithm can improve genetic algorithm solutions at the expense of more function evaluations. [Copyright &y& Elsevier]

This paper proposes a method of extracting the outline of an arbitrary shape in an image by using a genetic algorithm (GA). The image under consideration is a binary image containing a disconnected outline and noise. The proposed method extracts the outline from such a binary image as visually recognized by a human observer. First, the single outline extraction method is proposed, which extracts a single outline from the image. In the proposed method, Delaunay triangulation is applied to the point set in the binary image, and the graph containing the outline is derived. Then, the points and edges which can be recognized locally as the noise are eliminated. The outline is extracted from the graph after noise elimination using the GA. In the GA, gene coding is applied in which the polygons in the graph correspond to genes. It is shown experimentally that the outline of an arbitrary shape can be extracted by the proposed method. Next, the single outline extraction method is extended to a method by which multiple outlines contained in an image can be extracted. An experimental result is presented in which multiple outlines are extracted from an image. © 2005 Wiley Periodicals, Inc. Electron Comm Jpn Pt 2, 88(2): 32–46, 2005; Published online in Wiley InterScience (www.interscience.wiley.com). DOI 10.1002/ecjb.20146 [ABSTRACT FROM AUTHOR]

Abstract: Power system stability enhancement via STATCOM-based stabilizers is thoroughly investigated in this paper. This study presents a singular value decomposition (SVD)-based approach to assess and measure the controllability of the poorly damped electromechanical modes by STATCOM different control channels. The coordination among the proposed damping stabilizers and the STATCOM internal ac and dc voltage controllers has been taken into consideration. The design problem of STATCOM-based stabilizers is formulated as an optimization problem. For coordination purposes, a time domain-based multiobjective junction to improve the system stability as well as ac and dc voltage regulation is proposed. Then, a real-coded genetic algorithm (RCGA) is employed to search for optimal stabilizer parameters. This aims to enhance both rotor angle stability and voltage regulation of the power system. The proposed stabilizers are tested on a weakly connected power system with different disturbances and loading conditions. The nonlinear simulation results show the effectiveness and robustness of the proposed control schemes over a wide range of loading conditions. It is also observed that the proposed STATCOM-based damping stabilizers extend the critical clearing time (CCT) and enhance greatly the power system transient stability. [Copyright &y& Elsevier]

Abstract: Evolutionary algorithms (EAs) are stochastic search methods that mimic the natural biological evolution and/or the social behavior of species. Such algorithms have been developed to arrive at near-optimum solutions to large-scale optimization problems, for which traditional mathematical techniques may fail. This paper compares the formulation and results of five recent evolutionary-based algorithms: genetic algorithms, memetic algorithms, particle swarm, ant-colony systems, and shuffled frog leaping. A brief description of each algorithm is presented along with a pseudocode to facilitate the implementation and use of such algorithms by researchers and practitioners. Benchmark comparisons among the algorithms are presented for both continuous and discrete optimization problems, in terms of processing time, convergence speed, and quality of the results. Based on this comparative analysis, the performance of EAs is discussed along with some guidelines for determining the best operators for each algorithm. The study presents sophisticated ideas in a simplified form that should be beneficial to both practitioners and researchers involved in solving optimization problems. [Copyright &y& Elsevier]

In this paper, we firstly reformulate the landscape theory of aggregation (Axelrod and Bennett, 1993) in terms of an optimization problem and then straightforwardly propose a fuzzy-set-theoretic based extension for it. To illustrate efficiency of the proposal we make a simulation with the proposed framework for the international alignment of the Second World War in Europe. It is shown that the obtained results are essentially comparable to those given by the original theory. Consequently. the fuzzy-set-theoretic based extension of landscape theory can allow us to analyze a wide variety of aggregation processes in politics, economics, and society in a more flexible manner. [ABSTRACT FROM AUTHOR]

In this paper, an analysis of evolutionary algorithms for multi objective optimization, Non-dominated Sorting Genetic Algorithm (NSGA-II) and Strength Pareto Evolutionary Algorithm (SPEA-II) is presented. For this analysis, is taken as reference an optimization problem in a multicast data network, which has as objective functions the hop count and transmission delay. The algorithms performance is compared in tree different networks. Moreover, the model for two of this topologies using GAMS tool is resolved and results are compared with the NSGA-II and SPEA-II algorithms proposed. Problem results show the algorithms performance in their solution. [ABSTRACT FROM AUTHOR]

The quadratic assignment problem (QAP) is among the hardest combinatorial optimization problems. Very few instances of this problem can be solved in polynomial time. In this paper we address the problem of allocating rooms among people in a suitable shape of corridor with some constraints of undesired neighborhood. We give a linear time algorithm for this problem that we formulate as a QAP. [Copyright &y& Elsevier]

This paper presents an augmented Lagrangian genetic algorithm model for resource scheduling. The algorithm considers scheduling characteristics that were ignored in prior research. Previous resource scheduling formulations have primarily focused on project duration minimization. Furthermore, resource leveling and resource-constrained scheduling have traditionally been solved independently. The model presented here considers all precedence relationships, multiple crew strategies, total project cost minimization, and time-cost trade-off. In the new formulation, resource leveling and resource-constrained scheduling are performed simultaneously. The model presented uses the quadratic penalty function to transform the resource-scheduling problem to an unconstrained one. The algorithm is general and can be applied to a broad class of optimization problems. An illustrative example is presented to demonstrate the performance of the proposed method. [ABSTRACT FROM AUTHOR]

Risk Informed In-Service Inspection (RI-ISI) aims at prioritising the components for inspection within the permissible risk level thereby avoiding unnecessary inspections. Various constraints such as risk level, radiation exposure to the workers and cost of inspections are encountered, while planning the inspection programme. This problem has been attempted to solve using genetic algorithms, which has already established its suitability in optimizing Surveillance and Maintenance activities in Nuclear Power Plants. The paper describes the application of genetic algorithm in optimizing the ISI of feeders, which are large in number and also fall in the same inspection category. [Copyright &y& Elsevier]

Conventional tolerance analysis is tedious and time consuming, which makes engineers resist doing it. Complex assembly problems are generally beyond the capabilities of most design and manufacturing engineers. In this paper, genetic algorithm, a kind of non-traditional optimization technique is used as the basic foundation for optimal tolerance allocation to help design and manufacturing engineers to overcome the shortcomings in the conventional tolerance stack analysis and allocation system. [ABSTRACT FROM AUTHOR]

Typically for a real optimization problem, the optimal solution to a mathematical model of that real problem may not always be the 'best' solution when considering unmodeled or unquantified objectives during decision-making. Formal approaches to explore efficiently for good but maximally different alternative solutions have been established in the operations research literature, and have been shown to be valuable in identifying solutions that perform expectedly well with respect to modeled and unmodeled objectives. While the use of evolutionary algorithms (EAs) to solve real engineering optimization problems is becoming increasingly common, systematic alternatives-generation capabilities are not fully extended for EAs. This paper presents a new EA-based approach to generate alternatives (EAGA), and illustrates its applicability via two test problems. A realistic airline route network design problem was also solved and analyzed successfully using EAGA. The EAGA promises to be a flexible procedure for exploring alternative solutions that could assist when making decisions for real engineering optimization problems riddled with unmodeled or unquantified issues. [ABSTRACT FROM AUTHOR]

In this paper a recently proposed new stochastic method developed to tackle optimization problems with complex design spaces is presented. Called generalized extremal optimization (GEO), it is of easy implementation, does not make use of derivatives and can be applied to unconstrained or constrained problems, non-convex or disjoint design spaces, with any combination of continuous, discrete or integer variables. It is a global search meta-heuristic, as the Genetic Algorithm and the simulated annealing, but with the a priori advantage of having only one free parameter to adjust. In this article the efficacy of the GEO algorithm on dealing with complex design spaces is illustrated through the application of the method to the design of a heat pipe for satellite thermal control. [Copyright &y& Elsevier]

In this paper, four simulated annealing based multiobjective algorithms—SMOSA, UMOSA, PSA and WMOSA have been used to solve multiobjective optimization of constrained problems with varying degree of complexity along with a new PDMOSA algorithm. PDMOSA algorithm uses a strategy of Pareto dominant based fitness in the acceptance criteria of simulated annealing and is improved. In all algorithms, the current solution explores its neighborhoods in a way similar to that of classical simulated annealing. The performance and computational cost for all algorithms have been studied. All algorithms are found to be quite robust with algorithmic parameters and are capable of generating a large number of well diversified Pareto-optimal solutions. The quality and diversification of Pareto-optimal solutions generated by all algorithms are found to be problem specific. The computational cost is least by WMOSA and is followed by PDMOSA. The algorithms are simple to formulate and require reasonable computational time. Hence, the simultaneous use of all algorithms is suggested to obtain a wider spectrum of efficient solutions. [Copyright &y& Elsevier]

This paper describes the methodology and application of a genetic algorithm scheme tailor-made to EPANET, for optimizing the operation of a water distribution system under unsteady water quality conditions. The water distribution system consists of sources of different qualities, treatment facilities, tanks, pipes, control valves, and pumping stations. The objective is to minimize the total cost of pumping and treating the water for a selected operational time horizon, while delivering the consumers the required quantities at acceptable qualities and pressures. The decision variables for each of the time steps that encompass the total operational time horizon include: the scheduling of the pumping units, settings of the control valves, and treatment removal ratios at the treatment facilities. The constraints are: head and concentrations at the consumer nodes, maximum removal ratios at the treatment facilities, maximum allowable amounts of water withdrawals at the sources, and returning at the end of the operational time horizon to a prescribed total volume in the tanks. The model is explored through two example applications. [ABSTRACT FROM AUTHOR]

Genetic algorithms (GAs) have been widely applied for many non-polynomial hard optimisation problems, such as flow shop and job shop scheduling. It is well known that the efficiency and effectiveness of a GA is highly depend on its control parameters, but setting suitable parameters often involves tedious trial and error. Currently, setting optimal parameters is still a substantial problem and is one of the most important and promising areas for GAs. In this paper, the determination of optimal GA control parameters with limited computational effort and simulation replication constraints, namely, population size, crossover and mutation probabilities, is firstly formulated as a stochastic optimisation problem. Then, the ordinal optimisation (OO) and the optimal computing budget allocation (OCBA) are applied to select the optimal GA control parameters, thereby providing a reasonable performance evaluation for hard flow shop scheduling problems. The effectiveness of the methodology is demonstrated by simulation results based on benchmarks. [ABSTRACT FROM AUTHOR]

The computing GRID infrastructure could benefit of techniques that can improve the overall throughput of the system. It is possible that job submission will include different ontology in resource requests due to the generality of the GRID infrastructure. Such flexible resource request could offer the opportunity to optimize several parameters, from network load to job costs in relation to due time, more generally the quality of services. We present the result of the simulation of GRID jobs allocation. The search strategy for this input case does not converge to the optimal case inside the limited number of trial performed, in contrast with previous work on up to 24 jobs [Scheduling in a Grid Computing Environment using Genetic Algorithms, in: Proceedings of the International Parallel and Distributed Processing Symposium: IPDPS 2002 Workshops]. The benefits of the usage of the genetic algorithms to improve the quality of the scheduling is discussed. The simulation has been obtained using an environment GGAS suitable to study the scheduling of jobs in a distributed group of parallel machines. The modular structure of GGAS allows to expand its functionalities to include other first level schedule policy with respect to the FCFS that is considered. The result of this paper suggests the usage of local search strategy to improve the convergence when the number of jobs to be considered is as big as in real world operation. [Copyright &y& Elsevier]

Genetic algorithms are mostly considered to represent the primary class of evolutionary methods that operate by combining solutions to produce better ones. In this paper, a very efficient method based on the concept of the genetic algorithms metaheuristic technique is developed for providing an efficient solution for observing a surveying network using space-based satellites systems. These systems are used to determine the geographical positions of unknown points on and above the earth and its oceans using suitable satellite receiving equipment. When related to satellite technology, a surveying network can be defined as a number of points which are co-ordinated by a series of observation sessions. These sessions are formed by placing receivers on the points of the network. An observation session can be defined as a period of time during which two or more receivers simultaneously record satellite signals. Thus, the schedule of receivers is a sequence of sessions to be observed consecutively. The goal is to select the best order in which these sessions can be organised to give the best possible solution at minimal cost. Several real space-based satellites surveying networks have been used to assess the performance of the proposed technique in terms of the solution quality and computational effort. [Copyright &y& Elsevier]

This paper presents a procedural framework that unifies various mechanisms to look for discrete-neighborhood saddle points in solving discrete constrained optimization problems (DCOPs). Our approach is based on the necessary and sufficient condition on local optimality in discrete space, which shows the one-to-one correspondence between the discrete-space constrained local minima of a problem and the saddle points of the corresponding Lagrangian function. To look for such saddle points, we study various mechanisms for performing ascents of the Lagrangian function in the original-variable subspace and descents in the Lagrange-multiplier subspace. Our results show that CSAEA, a combined constrained simulated annealing and evolutionary algorithm, performs well when using mutations and crossovers to generate trial points and accepting them based on the Metropolis probability. We apply iterative deepening to determine the optimal number of generations in CSAEA and show that its performance is robust with respect to changes in population size. To test the performance of the procedures developed, we apply them to solve some continuous and mixed-integer nonlinear programming (NLP) benchmarks and show that they obtain better results than those of existing algorithms. [ABSTRACT FROM AUTHOR]

This paper describes a methodology based on genetic algorithms (GA) and experiments plan to optimize the availability and the cost of reparable parallel-series systems. It is a NP-hard problem of multi-objective combinatorial optimization, modeled with continuous and discrete variables. By using the weighting technique, the problem is transformed into a single-objective optimization problem whose constraints are then relaxed by the exterior penalty technique. We then propose a search of solution through GA, whose parameters are adjusted using experiments plan technique. A numerical example is used to assess the method. [Copyright &y& Elsevier]

Dantzig, Fulkerson, and Johnson (1954) introduced the cutting-plane method as a means of attacking the traveling salesman problem; this method has been applied to broad classes of problems in combinatorial optimization and integer programming. In this paper we discuss an implementation of Dantzig et al.'s method that is suitable for TSP instances having 1,000,000 or more cities. Our aim is to use the study of the TSP as a step towards understanding the applicability and limits of the general cutting-plane method in large-scale applications. [ABSTRACT FROM AUTHOR]

The application of valid inequalities to provide relaxations which can produce tight bounds, is now common practice in Combinatorial Optimisation. This paper attempts to complement current theoretical investigations in this regard. We experimentally search for "valid" equalities which have the potential of strengthening the problem's formulation. Recently, Martello and Toth [13] included cardinality constraints to derive tight upper bounds for the 0-1 Knapsack Problem. Encouraged by their results, we partition the search space by using equality cardinality constraints. Instead of solving the original problem, an equivalent problem, which consists of one or more 0-1 Knapsack Problem with an exact cardinality bound, is solved. By explicitly including a bound on the cardinality, one is able to reduce the size of each subproblem and compute tight upper bounds. Good feasible solutions found along the way are employed to reduce the computational effort by reducing the number of trees searched and the size of the subsequent search trees. We give a brief description of two Lagrangian-based Branch-and-Bound algorithms proposed in Kruger [9] for solving the exact cardinality bounded subproblems and report on results of numerical experiments with a sequential implementation. Implications for and strategies towards parallel implementation are also given. [ABSTRACT FROM AUTHOR]

Service restoration in distribution systems can be formulated as a combinatorial optimization problem. It is the problem to determine power sources for each load considering various operational constraints in distribution systems. Up to now, the problem has been dealt with using conventional methods such as the branch and bound method, expert systems, neural networks, and fuzzy reasoning. Recently, modern heuristic methods such as genetic algorithms (GA), simulated annealing (SA), and tabu search (TS) have been attracting notice as efficient methods for solving large combinatorial optimization problems. Moreover, reactive tabu search (RTS) can solve the parameter tuning problem, which is recognized as the essential problem of the TS. Therefore, RTS, GA, and SA can be efficient search methods for service restoration in distribution systems. This paper develops an RTS for service restoration and compares RTS, GA, and PSA (parallel SA) for the problem. The feasibility of the proposed methods is shown and compared on a typical distribution system model with promising results. © 2000 Scripta Technica, Electr Eng Jpn, 133(3): 71–82, 2000 [ABSTRACT FROM AUTHOR]

In this paper, we propose a neural network algorithm that uses the expanded maximum neuron model to solve the channel assignment problem of cellular radio networks, which is an NP-complete combinatorial optimization problem. The channel assignment problem demands minimizing the total interference between the assigned channels needed to satisfy all of the communication needs. The proposed expanded maximum neuron model selects multiple neurons in descending order from the neuron inputs in each neuron group. As a result, the constraints will always be satisfied for the channel assignment problem. To improve the accuracy of the solution, neuron fixing, which is a heuristic technique used in the binary neuron model, a hill-climbing term, a shaking term, and an Omega function are introduced. The effectiveness of these additions to the expanded maximum neuron model algorithm is demonstrated. Simulations of benchmark problems demonstrate the superior performance of the proposed algorithm over conventional algorithms in finding the solution. © 2000 Scripta Technica, Electron Comm Jpn Pt 3, 83(11): 11–19, 2000 [ABSTRACT FROM AUTHOR]

The equilibrium network design problem can be formulated as a mathematical program with variational inequality constraints. We know this problem is nonconvex; hence, it is difficult to solve for a globally optimal solution. In this paper we propose a simulated annealing algorithm for the equilibrium network design problem. We demonstrate the ability of this algorithm to determine a globally optimal solution for two different networks. One of these describes an actual city in the midwestern United States. [ABSTRACT FROM AUTHOR]

An immune system has powerful abilities such as memory, recognition, and learning to respond to invading antigens. The concept is expected to be applicable to many engineering applications. This paper proposes an optimization algorithm that imitates the immune system in order to solve multi-optimization problems partly by using a genetic algorithm. Through illustrative examples of multimodal functions such as the Shubert function, the proposed algorithm is shown to be effective in searching for a set of global solutions. © 1998 Scripta Technica. Electr Eng Jpn, 122(2): 30–37, 1998 [ABSTRACT FROM AUTHOR]

Tabu search is a novel technique for solving combinatorial optimization problems. The process in which the tabu search method seeks to transcend local optimality is based on an evaluation function which chooses the highest-evaluation move in terms of objective function and tabu restrictions. This paper presents a tabu search algorithm for finding a minimum-cost partition of the nodes of a directed acyclic graph into subsets of a given size, subject to the constraint that the precedence relations are satisfied. A standard tabu search approach cannot realize good solutions for this problem, because the problem is a complex multiple partitioning problem in which the number of subsets and the number of nodes in each subset are unsettled. For this problem, we use an appropriate data structure for this method and develop effective neighborhood structure and heuristics. We also assess the effectiveness of the developed algorithm. The results show that this algorithm is effective in obtaining a near-optimal solution to this problem. The running time of the procedure is proportional to the number of nodes in the graph. © 1997 Scripta Technica, Inc. Electr Eng Jpn, 119(4): 42–51, 1997 [ABSTRACT FROM AUTHOR]

Crow search algorithm is one of bio-inspired optimization algorithms which is essentially derived for solving continuous based optimization problems. Although many main-frame discrete optimizers are available, they still have some performance challenges. This paper proposes three discrete crow inspired algorithms for enhancing the performance of the original crow search algorithm when it is applied for solving discrete traveling salesman problems. The proposed algorithms are derived based on modular arithmetic, basic operators and dissimilar solutions techniques. Each technique guarantees switching from continuous spaces into discrete spaces without losing information. Such algorithms are called Modular Arithmetic, Basic Operators, and Dissimilar Solutions algorithms. For evaluating their performance, the proposed algorithms are compared with the most state-of-the-art discrete optimizers for solving 111 instances of traveling salesman problems. Simulation results illustrate that, the performance of the proposed algorithms is much better than the performance of most state-of-the-art discrete optimizers in terms of the average optimal solutions accuracy, the average errors from the optimal solutions and the average of computational time. [ABSTRACT FROM AUTHOR]