Entorno geométrico eficiente para el modelado de imágenes en 3D

The objective of this paper is exploring implementation of a realistic images reconstruction 3D using geometric algebra (GA). We illustrate the suitability of GA for representing structures and developing algorithms in computer graphics, especially for engineering applications as 3D images modeling. A first consequence is to propose an efficient framework model to be implemented in hardware programmable. The obtained results showed that using GA, the computations are less complex and shows as simple computations geometrical operations. The obtained model to hardware can be implemented as a next step in 3D image reconstruction. We also include the potential of GA for optimizations and highly efficient implementations.     

Standard sensitivity analysis and additive tolerance approach in MOLP

We consider sensitivity analysis of the objective function coefficients in multiple objective linear programming (MOLP). We focus on the properties of the parameters set for which a given extreme solution is efficient. Moreover, we compare two approaches: the standard sensitivity analysis (changing only one coefficient) and the additive tolerance approach (changing all coefficients). We find the connections between these two approaches by giving a theorem describing the upper bound on the maximal additive tolerance.     

A hybrid metaheuristic for the resource-constrained project scheduling problem

This study presents a hybrid metaheuristic ANGEL for the resource-constrained project scheduling problem (RCPSP). ANGEL combines ant colony optimization (ACO), genetic algorithm (GA) and local search strategy. The procedures of ANGEL are as follows. First, ACO searches the solution space and generates activity lists to provide the initial population for GA. Next, GA is executed and the pheromone set in ACO is updated when GA obtains a better solution. When GA terminates, ACO searches again by using a new pheromone set. ACO and GA search alternately and cooperatively in the solution space. This study also proposes an efficient local search procedure which is applied to yield a better solution when ACO or GA obtains a solution. A final search is applied upon the termination of ACO and GA. The experimental results of ANGEL on the standard sets of the project instances show that ANGEL is an effective method for solving the RCPSP.     

A heuristic method for non-homogeneous redundancy optimization of series-parallel multi-state systems

This paper develops an efficient heuristic to solve the non-homogeneous redundancy allocation problem for multi-state series-parallel systems. Non identical components can be used in parallel to improve the system availability by providing redundancy in subsystems. Multiple component choices are available for each subsystem. The components are binary and chosen from a list of products available on the market, and are characterized in terms of their cost, performance and availability. The objective is to determine the minimal-cost series-parallel system structure subject to a multi-state availability constraint. System availability is represented by a multi-state availability function, which extends the binary-state availability. This function is defined as the ability to satisfy consumer demand that is represented as a piecewise cumulative load curve. A fast procedure is used, based on universal generating function, to evaluate the multi-state system availability. The proposed heuristic approach is based on a combination of space partitioning, genetic algorithms (GA) and tabu search (TS). After dividing the search space into a set of disjoint subsets, this approach uses GA to select the subspaces, and applies TS to each selected subspace. The design problem, solved in this study, has been previously analyzed using GA. Numerical results for the test problems from previous research are reported, and larger test problems are randomly generated. These results show that the proposed approach is efficient both in terms of both of solution quality and computational time, as compared to existing approaches.     

多时间窗车辆路径问题的智能水滴算法

研究了多时间窗车辆路径问题,考虑了车容量、多个硬时间窗限制等约束条件,以动用车辆的固定成本和车辆运行成本之和最小为目标,建立了整数线性规划模型。根据智能水滴算法的基本原理,设计了求解多时间窗车辆路径问题的快速算法,利用具体实例进行了模拟计算,并与遗传算法的计算结果进行了对比分析,结果显示,利用智能水滴算法求解多时间窗车辆路径问题,能够以很高的概率得到全局最优解,是求解多时间窗车辆路径问题的有效算法。     

Reliability based assignment in stochastic-flow freight network

Based on the reliability of transportation time, a transportation assignment model of stochastic-flow freight network is designed in this paper. This transportation assignment model is built by mean of stochastic chance-constraint programming and solved with a hybrid intelligent algorithm (HIA) which integrates genetic algorithm (GA), stochastic simulation (SS) and neural network (NN). GA is employed to report the optimal solution as well as the optimal objective function values of the proposed model. SS is used to simulate the value of uncertain system reliability function. The uncertain function approximated via NN is embedded into GA to check the feasibility and to compute the fitness of the chromosomes. These conclusions have been drawn after a test of numerical case using the proposed formulations. System reliability, total system cost and flow on each path would finally reach at their own convergence points. Increase of the system reliability causes increase of the total time cost. The system reliability and the total time cost converge at a possible Nash Equilibrium point.     

Constraint Handling in Genetic Algorithms: The Set Partitioning Problem

In this paper we present a genetic algorithm-based heuristic for solving the set partitioning problem (SPP). The SPP is an important combinatorial optimisation problem used by many airlines as a mathematical model for flight crew scheduling.A key feature of the SPP is that it is a highly constrained problem, all constraints being equalities. New genetic algorithm (GA) components: separate fitness and unfitness scores, adaptive mutation, matching selection and ranking replacement, are introduced to enable a GA to effectively handle such constraints. These components are generalisable to any GA for constrained problems.We present a steady-state GA in conjunction with a specialised heuristic improvement operator for solving the SPP. The performance of our algorithm is evaluated on a large set of real-world problems. Computational results show that the genetic algorithm-based heuristic is capable of producing high-quality solutions.     

Soft computing optimization methods applied to logistic processes

This paper discusses the methodologies that can be used to optimize a logistic process of a supply chain described as a scheduling problem. First, a model of the system based on a real-world example is presented. Then, a new objective function called Global Expected Lateness is proposed, in order to describe multiple optimization criteria. Finally, three different optimization methodologies are proposed: a classical dispatching rule, and two soft computing techniques, Genetic Algorithms (GA) and Ant Colony Optimization (ACO). These methodologies are compared to the dispatching policy in the real-world example. The results show that dispatching heuristics are outperformed by the GA and ACO meta-heuristics. Further, it is shown that GA and ACO provide statistically identical scheduling solutions and from the optimization performance point of view, it is equivalent to use any of the meta-heuristics.     

An all-linear programming relaxation algorithm for optimizing over the efficient set

The problem (P) of optimizing a linear function over the efficient set of a multiple objective linear program has many important applications in multiple criteria decision making. Since the efficient set is in general a nonconvex set, problem (P) can be classified as a global optimization problem. Perhaps due to its inherent difficulty, it appears that no precisely-delineated implementable algorithm exists for solving problem (P) globally. In this paper a relaxation algorithm is presented for finding a globally optimal solution for problem (P). The algorithm finds an exact optimal solution to the problem after a finite number of iterations. A detailed discussion is included of how to implement the algorithm using only linear programming methods. Convergence of the algorithm is proven, and a sample problem is solved.Research supported by a grant from the College of Business Administration, University of Florida, Gainesville, Florida, U.S.A.     

Two genetic algorithms for solving the uncapacitated single allocation p-hub median problem

This paper deals with the Uncapacitated Single Allocation p-Hub Median Problem (USApHMP). Two genetic algorithm (GA) approaches are proposed for solving this NP-hard problem. New encoding schemes are implemented with appropriate objective functions. Both approaches keep the feasibility of individuals by using specific representation and modified genetic operators. The numerical experiments were carried out on the standard ORLIB hub data set. Both methods proved to be robust and efficient in solving USApHMP with up to 200 nodes and 20 hubs. The second GA approach achieves all previously known optimal solutions and achieves the best-known solutions on large-scale instances.     

Optimization over the efficient set

This paper deals with the problem of maximizing a function over the efficient set of a linear multiple objective program. The approach is to formulate a biobjective program with an appropriate efficient set. The penalty function approach is motivated by an auxiliary problem due to Benson.     

锥弱有效解的本质集和本质连通区

对于多目标规划问题,通过引入锥弱有效解集的概念,证明了任何连续有界泛函至少存在一个极小本质集和一个本质连通区.     

Contrast enhancement for image by WNN and GA combining PSNR with information entropy

A new contrast enhancement algorithm for image is proposed combining genetic algorithm (GA) with wavelet neural network (WNN). In-complete Beta transform (IBT) is used to obtain non-linear gray transform curve so as to enhance global contrast for an image. GA determines optimal gray transform parameters. In order to avoid the expensive time for traditional contrast enhancement algorithms, which search optimal gray transform parameters in the whole parameters space, based on gray distribution of an image, a classification criterion is proposed. Contrast type for original image is determined by the new criterion. Parameters space is, respectively, determined according to different contrast types, which greatly shrink parameters space. Thus searching direction of GA is guided by the new parameter space. Considering the drawback of traditional histogram equalization that it reduces the information and enlarges noise and background blur in the processed image, a synthetic objective function is used as fitness function of GA combining peak signal-noise-ratio (PSNR) and information entropy. In order to calculate IBT in the whole image, WNN is used to approximate the IBT. In order to enhance the local contrast for image, discrete stationary wavelet transform (DSWT) is used to enhance detail in an image. Having implemented DSWT to an image, detail is enhanced by a non-linear operator in three high frequency sub-bands. The coefficients in the low frequency sub-bands are set as zero. Final enhanced image is obtained by adding the global enhanced image with the local enhanced image. Experimental results show that the new algorithm is able to well enhance the global and local contrast for image while keeping the noise and background blur from being greatly enlarged.     

Criteria and dimension reduction of linear multiple criteria optimization problems

Two of the main approaches in multiple criteria optimization are optimization over the efficient set and utility function program. These are nonconvex optimization problems in which local optima can be different from global optima. Existing global optimization methods for solving such problems can only work well for problems of moderate dimensions. In this article, we propose some ways to reduce the number of criteria and the dimension of a linear multiple criteria optimization problem. By the concept of so-called representative and extreme criteria, which is motivated by the concept of redundant (or nonessential) objective functions of Gal and Leberling, we can reduce the number of criteria without altering the set of efficient solutions. Furthermore, by using linear independent criteria, the linear multiple criteria optimization problem under consideration can be transformed into an equivalent linear multiple criteria optimization problem in the space of linear independent criteria. This equivalence is understood in a sense that efficient solutions of each problem can be derived from efficient solutions of the other by some affine transformation. As a result, such criteria and dimension reduction techniques could help to increase the efficiency of existing algorithms and to develop new methods for handling global optimization problems arisen from multiple objective optimization.     

Misclassification cost minimizing fitness functions for genetic algorithm-based artificial neural network classifiers

We study three different approaches to formulate a misclassification cost minimizing genetic algorithm (GA) fitness function for a GA-neural network classifier. These three different approaches include a fitness function that directly minimizes total misclassification cost, a fitness function that uses posterior probability for minimizing total misclassification cost and a hybrid fitness function that uses an average value of the first two fitness functions to minimize total misclassification cost. Using simulated data sets representing three different distributions and four different misclassification cost matrices, we test the performance of the three fitness functions on a two-group classification problem. Our results indicate that the posterior probability-based misclassification cost minimizing function and the hybrid fitness function are less prone to training data over fitting, but direct misclassification cost minimizing fitness function provides the lowest overall misclassification cost in training tests. For holdout sample tests, when cost asymmetries are low (less than or equal to a ratio of 1:2), the hybrid misclassification cost minimizing fitness function yields the best results; however, when cost asymmetries are high (equal or greater than a ratio of 1:4), the total misclassification cost minimizing function provides the best results. We validate our findings using a real-world data on a bankruptcy prediction problem.     

Graph Coloring with Adaptive Evolutionary Algorithms

This paper presents the results of an experimental investigation on solving graph coloring problems with Evolutionary Algorithms (EAs). After testing different algorithm variants we conclude that the best option is an asexual EA using order-based representation and an adaptation mechanism that periodically changes the fitness function during the evolution. This adaptive EA is general, using no domain specific knowledge, except, of course, from the decoder (fitness function). We compare this adaptive EA to a powerful traditional graph coloring technique DSatur and the Grouping Genetic Algorithm (GGA) on a wide range of problem instances with different size, topology and edge density. The results show that the adaptive EA is superior to the Grouping (GA) and outperforms DSatur on the hardest problem instances. Furthermore, it scales up better with the problem size than the other two algorithms and indicates a linear computational complexity.     

Further Analysis of an Outcome Set-Based Algorithm for Multiple-Objective Linear Programming

Various difficulties have been encountered in using decision set-based vector maximization methods to solve a multiple-objective linear programming problem (MOLP). Motivated by these difficulties, Benson recently developed a finite, outer-approximation algorithm for generating the set of all efficient extreme points in the outcome set, rather than in the decision set, of problem (MOLP). In this article, we show that the Benson algorithm also generates the set of all weakly efficient points in the outcome set of problem (MOLP). As a result, the usefulness of the algorithm as a decision aid in multiple objective linear programming is further enhanced.     

A hybrid adaptively genetic algorithm for task scheduling problem in the phased array radar

A phased array radar (PAR) is used to detect new targets and update the information of those detected targets. Generally, a large number of tasks need to be performed by a single PAR in a finite time horizon. In order to utilize the limited time and the energy resources, it is necessary to provide an efficient task scheduling algorithm. However, the existing radar task scheduling algorithms can't be utilized to release the full potential of the PAR, because of those disadvantages such as full PAR task structure ignored, only good performance in one aspect considered and just heuristic or the meta-heuristic method utilized. Aiming at above issues, an optimization model for the PAR task scheduling and a hybrid adaptively genetic (HAGA) algorithm are proposed. The model considers the full PAR task structure and integrates multiple principles of task scheduling, so that multi-aspect performance can be guaranteed. The HAGA incorporates the improved GA to explore better solutions while using the heuristic task interleaving algorithm to utilize wait intervals to interleave subtasks and calculate fitness values of individuals in efficient manners. Furthermore, the efficiency and the effectiveness of the HAGA are both improved by adopting chaotic sequences for the population initialization, the elite reservation and the mixed ranking selection, as well as designing the adaptive crossover and the adaptive mutation operators. The simulation results demonstrate that the HAGA possesses merits of global exploration, faster convergence, and robustness compared with three state-of-art algorithms—adaptive GA, hybrid GA and highest priority and earliest deadline first heuristic (HPEDF) algorithm.     

Primal and dual algorithms for optimization over the efficient set

ABSTRACT

Optimization over the efficient set of a multi-objective optimization problem is a mathematical model for the problem of selecting a most preferred solution that arises in multiple criteria decision-making to account for trade-offs between objectives within the set of efficient solutions. In this paper, we consider a particular case of this problem, namely that of optimizing a linear function over the image of the efficient set in objective space of a convex multi-objective optimization problem. We present both primal and dual algorithms for this task. The algorithms are based on recent algorithms for solving convex multi-objective optimization problems in objective space with suitable modifications to exploit specific properties of the problem of optimization over the efficient set. We first present the algorithms for the case that the underlying problem is a multi-objective linear programme. We then extend them to be able to solve problems with an underlying convex multi-objective optimization problem. We compare the new algorithms with several state of the art algorithms from the literature on a set of randomly generated instances to demonstrate that they are considerably faster than the competitors.     

Exploring the trade-off between generalization and empirical errors in a one-norm SVM

We propose a one-norm support vector machine (SVM) formulation as an alternative to the well-known formulation that uses parameter C in order to balance the two inherent objective functions of the problem. Our formulation is motivated by the ?-constraint approach that is used in bicriteria optimization and we propose expressing the objective of minimizing total empirical error as a constraint with a parametric right-hand-side. Using dual variables we show equivalence of this formulation to the one with the trade-off parameter. We propose an algorithm that enumerates the entire efficient frontier by systematically changing the right-hand-side parameter. We discuss the results of a detailed computational analysis that portrays the structure of the efficient frontier as well as the computational burden associated with finding it. Our results indicate that the computational effort for obtaining the efficient frontier grows linearly in problem size, and the benefit in terms of classifier performance is almost always substantial when compared to a single run of the corresponding SVM. In addition, both the run time and accuracy compare favorably to other methods that search part or all of the regularization path of SVM.