A multiobjective optimization solver using rank-niche evolution strategy

A rank-niche evolution strategy (RNES) algorithm has been developed in this paper to solve unconstrained multiobjective optimization problems. A required number of Pareto-optimal solutions can be generated by the algorithm in a single run. In addition to the operations of recombination, mutation and selection used in original evolution strategy (ES), an external elite set which contains a given number of non-dominated elites is updated and trimmed by a clustering technique to maintain a uniformly distributed Pareto front. The fitness function for each individual contains the information of rank and crowding status. The selection operation using this fitness function considers the superiority and distribution simultaneously. Eight test problems illustrated in other papers are used to test RNES. For some test problems the Pareto-optimal solutions obtained by RNES are better than those obtained by GA-based algorithms.     

A 2-tuple fuzzy linguistic representation model for computing withwords

The fuzzy linguistic approach has been applied successfully to many problems. However, there is a limitation of this approach imposed by its information representation model and the computation methods used when fusion processes are performed on linguistic values. This limitation is the loss of information; this loss of information implies a lack of precision in the final results from the fusion of linguistic information. In this paper, we present tools for overcoming this limitation. The linguistic information is expressed by means of 2-tuples, which are composed of a linguistic term and a numeric value assessed in (-0.5, 0.5). This model allows a continuous representation of the linguistic information on its domain, therefore, it can represent any counting of information obtained in a aggregation process. We then develop a computational technique for computing with words without any loss of information. Finally, different classical aggregation operators are extended to deal with the 2-tuple linguistic model     

An offset error compensation method for improving ANN accuracy when used for position control of precision machinery

Artificial Neural Networks (ANNs) have recently become the focus of considerable attention in many disciplines, including robot control, where they can be used as a general class of nonlinear models to solve highly nonlinear control problems. Feedforward neural networks have been widely applied for modelling and control purposes. One of the ANN applications in robot control is for the solution of the inverse kinematic problem, which is important in path planning of robot manipulators. This paper proposes an iterative approach and an offset error compensation method to improve the accuracy of the inverse kinematic solutions by using an ANN and a forward kinematic model of a robot. The offset error compensation method offers potential to generate accurately the inverse solution for a class of problems which have an easily obtained forward model and a complicated solution.Now Lecturing in Taiwan.     

A linear programming based heuristic framework for min-max regret combinatorial optimization problems with interval costs

This work deals with a class of problems under interval data uncertainty, namely interval robust-hard problems, composed of interval data min-max regret generalizations of classical NP-hard combinatorial problems modeled as 0-1 integer linear programming problems. These problems are more challenging than other interval data min-max regret problems, as solely computing the cost of any feasible solution requires solving an instance of an NP-hard problem. The state-of-the-art exact algorithms in the literature are based on the generation of a possibly exponential number of cuts. As each cut separation involves the resolution of an NP-hard classical optimization problem, the size of the instances that can be solved efficiently is relatively small. To smooth this issue, we present a modeling technique for interval robust-hard problems in the context of a heuristic framework. The heuristic obtains feasible solutions by exploring dual information of a linearly relaxed model associated with the classical optimization problem counterpart. Computational experiments for interval data min-max regret versions of the restricted shortest path problem and the set covering problem show that our heuristic is able to find optimal or near-optimal solutions and also improves the primal bounds obtained by a state-of-the-art exact algorithm and a 2-approximation procedure for interval data min-max regret problems.     

Multihierarchical graph search

The use of hierarchical graph searching for finding paths in graphs is well known in the literature, providing better results than plain graph searching, with respect to computational costs, in many cases. This paper offers a step forward by including multiple hierarchies in a graph-based model. Such a multi-hierarchical model has the following advantages: First, a multiple hierarchy permits us to choose the best hierarchy to solve each search problem; second, when several search problems have to be solved, a multiple hierarchy provides the possibility of solving some of them simultaneously; and third, solutions to the search problems can be expressed in any of the hierarchies of the multiple hierarchy, which allows us to represent the information in the most suitable way for each specific purpose. In general, multiple hierarchies have proven to be a more adaptable model than single-hierarchy or non-hierarchical models. This paper formalizes the multi-hierarchical model, describes the techniques that have been designed for taking advantage of multiple hierarchies in a hierarchical path search, and presents some experiments and results on the performance of these techniques     

Polynomial-Time Algorithms for Minimum-Time Broadcast in Trees

Abstract. This paper addresses the minimum-time broadcast problem under several modes of the line model, i.e., when long-distance calls can be placed along paths in the network. It is well known that the minimum-time broadcast problem can be solved in polynomial time under the single-port edge-disjoint paths mode. However, it is equally well known that either relaxing the model to the all-port edge-disjoint paths mode, or constraining the model to the single-port vertex-disjoint paths mode, leads to NP-complete problems; and exact solutions have been derived for specific topologies only (e.g., hypercubes or tori). In this paper we present polynomial-time algorithms for minimum-time broadcast in trees. These algorithms are obtained by application of an original technique called the merging method , which can be applied in a larger context, for instance, to solve the multicast problem or to address the restricted regimen. The merging method requires solving the minimal contention-free matrix problem whose solution presents some interest on its own.     

Effective Linkage Learning Using Low-Order Statistics and Clustering

The adoption of probabilistic models for selected individuals is a powerful approach for evolutionary computation. Probabilistic models based on high-order statistics have been used by estimation of distribution algorithms (EDAs), resulting better effectiveness when searching for global optima for hard optimization problems. This paper proposes a new framework for evolutionary algorithms, which combines a simple EDA based on order 1 statistics and a clustering technique in order to avoid the high computational cost required by higher order EDAs. The algorithm uses clustering to group genotypically similar solutions, relying that different clusters focus on different substructures and the combination of information from different clusters effectively combines substructures. The combination mechanism uses an information gain measure when deciding which cluster is more informative for any given gene position, during a pairwise cluster combination. Empirical evaluations effectively cover a comprehensive range of benchmark optimization problems.      

Enhancing information security with the information resource management approach

Recently, computer security and incidents of computer crime have received considerable attention. Without a doubt, in computer security the risks are high, and the problems and their solutions are complex; nonetheless, the emphasis of this attention has been misplaced. The emphasis should be primarily on the security of information itself and secondarily on the devices that handle information and on any of the other factors that go into information production. The factors of information production should certainly be considered, but only after planning and analysis based on information has been completed. For example, when considering the possibility that a competitor may steal your firm's proprietary information, it is best to consider first what information should be safequarded and what expenditure is warranted for such protection; then one can consider the environments in which this information appears (paper-based, computerized, verbal, etc.) and controls that are appropriate for these environments.This paper explores the application to the information security area of Information Resource Management (IRM), a new and promising approach that concentrates, on information not on computers. This paper explains the concepts underlying IRM, how they are applied, and what general information systems benefits can be obtained. In a more specifically security-oriented sense, it indicates how IRM can help address a few of the pressing problems now encountered by information security practitioners: controls suboptimization, the Maginot Line syndrome, top management understanding and support, disaster recovery planning, security policy-making, consideration of noncomputerized information, and expeditious resolution of security problems.     

Global Optimization through Rotation Space Search

This paper introduces a new algorithmic technique for solving certain problems in geometric computer vision. The main novelty of the method is a branch-and-bound search over rotation space, which is used in this paper to determine camera orientation. By searching over all possible rotations, problems can be reduced to known fixed-rotation problems for which optimal solutions have been previously given. In particular, a method is developed for the estimation of the essential matrix, giving the first guaranteed optimal algorithm for estimating the relative pose using a cost function based on reprojection errors. Recently convex optimization techniques have been shown to provide optimal solutions to many of the common problems in structure from motion. However, they do not apply to problems involving rotations. The search method described in this paper allows such problems to be solved optimally. Apart from the essential matrix, the algorithm is applied to the camera pose problem, providing an optimal algorithm. The approach has been implemented and tested on a number of both synthetically generated and real data sets with good performance. NICTA is funded by the Australian Government’s Backing Australia’s Ability initiative, in part through the Australian Research Council.     

A parallel genetic algorithm to solve the set-covering problem

This work presents a parallel genetic algorithm (PGA) model to solve the set-covering problem (SCP). Experimental results obtained with a binary representation of the SCP, show that—in terms of the number of generations (computational time) needed to achieve solutions of an acceptable quality—PGA performs better than the sequential model. This comportment can be explained principally because, the PGA of p nodes—each one with its corresponding local population P_L—behaves like a sequential GA with a global population, P_G, of the same size, which it—the sequential GA—has the great disadvantage of having to completely evaluate in each generation. Not so the PGA, which only evaluates a pth part of the P_G.Scope and purposeSince classical optimization techniques are inefficient to solve NP-complete problems—in terms of computational complexity—new methods have been developed. The genetic algorithm (GA), is one of such methods proposed to solve combinatorial optimization. Although Genetic Algorithms (GAs) are efficient to solve these kinds of hard problems, during recent years, models of parallel genetic algorithms (PGAs) have been used to improve both quality of solutions and computing time. The aim of using PGAs, is to discover how the interchange of genetic information of separate populations, affects or influences the final solution. The exploration of different solution spaces could optimize the search in terms of both computational time and quality of solution.     

DE/EDA: A new evolutionary algorithm for global optimization

Differential evolution (DE) was very successful in solving the global continuous optimization problem. It mainly uses the distance and direction information from the current population to guide its further search. Estimation of distribution algorithm (EDA) samples new solutions from a probability model which characterizes the distribution of promising solutions. This paper proposes a combination of DE and EDA (DE/EDA) for the global continuous optimization problem. DE/EDA combines global information extracted by EDA with differential information obtained by DE to create promising solutions. DE/EDA has been compared with the best version of the DE algorithm and an EDA on several commonly utilized test problems. Experimental results demonstrate that DE/EDA outperforms the DE algorithm and the EDA. The effect of the parameters of DE/EDA to its performance is investigated experimentally.     

Multicriteria programming in medical diagnosis and treatments

This paper deals with a special case of multicriteria optimization problems. The problems studied come from the medical domain and are of a very important practical relevance. One of the problems refers to the ranking of treatments for the Trigeminal Neuralgia. The second problem refers to a hierarchy of risk factors for Bronchial Asthma. The most common way to deal with a multiobjective optimization problem is to apply Pareto dominance relationship between solutions. But in the cases studied here, a decision cannot be made just by using Pareto dominance. In one of the experiments, all the potential solutions are nondominated (and we need to clearly find a hierarchy of these solutions) and in the second experiment most of the solutions are nondominated between them. We propose a novel multiple criteria procedure and then an evolutionary scheme is applied for solving the problems. Results obtained by the proposed approach in a very simple way are same as the results (or even better) obtained by applying weighted-sum method. The advantage of the proposed technique is that it does not require any additional information about the problem (like weights for each criteria in the case of weighted-sumapproach).     

A recombination‐based matheuristic for mixed integer programming problems with binary variables

This work introduces a heuristic for mixed integer programming (MIP) problems with binary variables, based on information obtained from differences between feasible solutions as well as solutions from the linear relaxation. This information is used to build a neighborhood that is explored as a sub‐MIP problem. The proposed heuristic is evaluated using 45 problems from the MIPLIB repository. Its performance, in terms of solution improvement over the results obtained after exploring 50,000 nodes of the branch‐and‐bound tree, is compared against that of Solution Polishing, which is another recombination‐based heuristic for MIP problems used within the CPLEX solver; as well as against the solution obtained by running the default CPLEX branch‐and‐cut (B&C) method under a same time limit. The computational results indicate that the proposed method is able to yield results that are significantly better than those obtained by the default CPLEX B&C approach and comparable to those of Solution Polishing in terms of the mean solution quality. This equivalence of expected solution quality, coupled with a simpler implementation, suggests the use of the proposed approach as a possible alternative for improving the quality of solutions in MIP problems.     

PGD-Based Computational Vademecum for Efficient Design, Optimization and Control

In this paper we are addressing a new paradigm in the field of simulation-based engineering sciences (SBES) to face the challenges posed by current ICT technologies. Despite the impressive progress attained by simulation capabilities and techniques, some challenging problems remain today intractable. These problems, that are common to many branches of science and engineering, are of different nature. Among them, we can cite those related to high-dimensional problems, which do not admit mesh-based approaches due to the exponential increase of degrees of freedom. We developed in recent years a novel technique, called Proper Generalized Decomposition (PGD). It is based on the assumption of a separated form of the unknown field and it has demonstrated its capabilities in dealing with high-dimensional problems overcoming the strong limitations of classical approaches. But the main opportunity given by this technique is that it allows for a completely new approach for classic problems, not necessarily high dimensional. Many challenging problems can be efficiently cast into a multidimensional framework and this opens new possibilities to solve old and new problems with strategies not envisioned until now. For instance, parameters in a model can be set as additional extra-coordinates of the model. In a PGD framework, the resulting model is solved once for life, in order to obtain a general solution that includes all the solutions for every possible value of the parameters, that is, a sort of computational vademecum. Under this rationale, optimization of complex problems, uncertainty quantification, simulation-based control and real-time simulation are now at hand, even in highly complex scenarios, by combining an off-line stage in which the general PGD solution, the vademecum, is computed, and an on-line phase in which, even on deployed, handheld, platforms such as smartphones or tablets, real-time response is obtained as a result of our queries.     

基于RSS的个性化信息服务研究

由于绝大部分Web信息都是非结构化的,使得现有的个性化服务系统在用户建模时面临着大量的信息预处理工作,并且在个性化推送方式上缺乏动态性和时效性.将个性化技术与RSS技术相结合,首先提出基于RSS技术的个性化信息服务系统的架构,该架构在建立用户兴趣模型和信息推送中揉合了RSS技术;然后给出该架构中几个关键问题的解决方法;最后通过一个试验实例,说明该架构的可行性.     

Robot Motion Planning: A Game-Theoretic Foundation

Analysis techniques and algorithms for basic path planning have become quite valuable in a variety of applications such as robotics, virtual prototyping, computer graphics, and computational biology. Yet, basic path planning represents a very restricted version of general motion planning problems often encountered in robotics. Many problems can involve complications such as sensing and model uncertainties, nonholonomy, dynamics, multiple robots and goals, optimality criteria, unpredictability, and nonstationarity, in addition to standard geometric workspace constraints. This paper proposes a unified, game-theoretic mathematical foundation upon which analysis and algorithms can be developed for this broader class of problems, and is inspired by the similar benefits that were obtained by using unified configuration-space concepts for basic path planning. By taking this approach, a general algorithm has been obtained for computing approximate optimal solutions to a broad class of motion planning problems, including those involving uncertainty in sensing and control, environment uncertainties, and the coordination of multiple robots. Received November 11, 1996; revised March 13, 1998.     

New analytical method for gas dynamics equation arising in shock fronts

This work suggests a new analytical technique called the fractional homotopy analysis transform method (FHATM) for solving nonlinear homogeneous and nonhomogeneous time-fractional gas dynamics equations. The FHATM is an innovative adjustment in Laplace transform algorithm (LTA) and makes the calculation much simpler. The proposed technique solves the nonlinear problems without using Adomian polynomials and He’s polynomials which can be considered as a clear advantage of this new algorithm over decomposition and the homotopy perturbation transform method. In this paper, it can be observed that the auxiliary parameter ?$?$, which controls the convergence of the HATM approximate series solutions, also can be used in predicting and calculating multiple solutions. This is a basic and more qualitative difference in analysis between HATM and other methods. The solutions obtained by the proposed method indicate that the approach is easy to implement and computationally very attractive. The proposed method is illustrated by solving some numerical examples.     

A cooperative parallel meta-heuristic for the vehicle routing problem with time windows

This paper presents a parallel cooperative multi-search method for the vehicle routing problem with time windows. It is based on the solution warehouse strategy, in which several search threads cooperate by asynchronously exchanging information on the best solutions identified. The exchanges are performed through a mechanism, called solution warehouse, which holds and manages a pool of solutions. This enforces the asynchronous strategy of information exchanges and ensures the independence of the individual search processes. Each of these independent processes implements a different meta-heuristic, an evolutionary algorithm or a tabu search procedure. No attempt has been made to calibrate the individual procedures or the parallel cooperative method. The results obtained on an extended set of test problems show that the parallel procedure achieves linear accelerations and identifies solutions of comparable quality to those obtained by the best methods in the literature.     

An effective coding approach for multiobjective integrated resource selection and operation sequences problem

In this paper, we consider an integrated Resource Selection and Operation Sequences (iRS/OS) problem in Intelligent Manufacturing System (IMS). Several kinds of objectives are taken into account, in which the makespan for orders should be minimized; workloads among machine tools should be balanced; the total transition times between machines in a local plant should also be minimized. To solve this multiobjective iRS/OS model, a new two vectors-based coding approach has been proposed to improve the efficiency by designing a chromosome containing two kinds of information, i.e., operation sequences and machine selection. Using such kind of chromosome, we adapt multistage operation-based Genetic Algorithm (moGA) to find the Pareto optimal solutions. Moreover a special technique called left-shift hillclimber has been used as one kind of local search to improve the efficiency of our algorithm. Finally, the experimental results of several iRS/OS problems indicate that our proposed approach can obtain best solutions. Further more comparing with previous approaches, moGA performs better for finding Pareto solutions. Received: May 2005/Accepted: December 2005     

Solving Non-Linear Models with Saddle-Path Instabilities

Economic models derived from optimizing behavior are typically characterized by the properties of non-linearity and saddle-path instability. The typical solution method involves deriving the stable arm of the saddle-path and calculating suitable “jumps” to bring the path of endogenous variables onto this stable arm. The solution for the stable arm can be determined using a range of different approaches. In this paper we examine the extent to which the success of these alternative approaches can be evaluated. Any method of evaluation will be dependent upon the amount of information that is known about a particular model solution. For some deterministic models the only information known with certainty about the path of the model solution are values taken by steady-state solutions; the rest of the path must be approximated in some way based on numerical solutions derived from non-linear ordinary differential equations. In some special cases it is possible to derive a closed-form solution of the entire path. As an example of a model with a closed-form solution, we consider a simple linear model with two stable complex-valued eigenvalues and one unstable real-valued eigenvalue. The model is then employed as a benchmark to compare the properties of model solutions derived using two well-known solution algorithms. Because the model has complex-valued eigenvalues it will have cyclic dynamics and thus problems encountered in solving these dynamics will likely coincide with some of the problems that solution algorithms have in solving non-linear models. Since the entire solution path of the model is known, it is possible to derive deeper insights into the factors that are likely to ensure the success or failure of different solution approaches than would be the case if less information about the solution path was available.An earlier version of this paper was presented to the Ninth International Conference on Computing in Economics and Finance organized by the Society of Computational Economics, University of Washington at Seattle, July 11–13, 2003. Earlier versions of this paper have also been presented at seminars and workshops at the University of Oxford, at the University of Canterbury at Christchurch, and at the University of Melbourne. JEL Classifications: C63, E17