基于改进粒子群算法的投资组合选择模型

研究了在实际投资决策中存在交易成本(税收和交易费用)和投资数量约束下的投资组合选择问题,并进一步设计了一种求解该问题的改进粒子群算法.最后,给出了一个数值例子,说明该模型和方法的有效性.     

Quadratic programming with transaction costs

We consider the problem of maximizing the mean-variance utility function of n$n$ assets. Associated with a change in an asset's holdings from its current or target value is a transaction cost. These must be accounted for in practical problems. A straightforward way of doing so results in a 3n$3n$-dimensional optimization problem with 3n$3n$ additional constraints. This higher dimensional problem is computationally expensive to solve. We present an algorithm for solving the 3n$3n$-dimensional problem by modifying an active set quadratic programming (QP) algorithm to solve the 3n$3n$-dimensional problem as an n$n$-dimensional problem accounting for the transaction costs implicitly rather than explicitly. The method is based on deriving the optimality conditions for the higher dimensional problem solely in terms of lower dimensional quantities and requires substantially less computational effort than any active set QP algorithm applied directly on a 3n$3n$-dimensional problem.     

旅行商问题(TSP)的一种改进遗传算法

传统的序号编码遗传算法(GA)使用PMX、CX和OX等特殊的交叉算子,这些算子实施起来很麻烦。针对TSP问题的求解,提出了一种新的改进遗传算法：单亲进化遗传算法(PEGA),PEGA是利用父体所提供的有效边的信息,使用保留最小边的方法进行个体的进化。与传统的遗传算法相比,PEGA算法弥补了它们的不足之处,简化了遗传算法。给出了PEGA算法的数值算例,仿真实验表明了该算法对于对称的TSP和非对称的TSP问题,都具有收敛速度快的特点,证明了该算法的有效性。     

SID-GA: An evolutionary approach for improving observability and redundancy analysis in structural instrumentation design

In this paper the core of a genetic algorithm designed to define a sensor network for instrumentation design (ID) is presented. The tool has been incorporated into a decision support system (DSS) that assists the engineer during the ID process. The algorithm satisfactorily deals with non-linear mathematical models, and considers four design objectives, namely observability, cost, reliability and redundancy, exhibiting properties that were either never addressed by existing techniques or partially dealt with in the literature. Its performance was tested by carrying out the ID of an ammonia synthesis industrial plant. Results were statistically analysed. A face validity study on the fitness function’s soundness was also assessed by a chemical engineer with insight and expertise in this problem. The technique performed satisfactorily from the point of view of the expert in ID, and therefore it constitutes a significant upgrading for the DSS.     

Continuous-time mean variance portfolio with transaction costs: a proximal approach involving time penalization

This paper proposes a new continuous-time optimization solution that enables the computation of the portfolio problem (based on the utility option pricing and the shortfall risk minimization). We first propose a dynamical stock price process, and then, we transform the solution to a continuous-time discrete-state Markov decision processes. The market behavior is characterized by considering arbitrage-free and assessing transaction costs. To solve the problem, we present a proximal optimization approach, which considers time penalization in the transaction costs and the utility. In order to include the restrictions of the market, as well as those that imposed by the continuous-time space, we employ the Lagrange multipliers approach. As a result, we obtain two different equations: one for computing the portfolio strategies and the other for computing the Lagrange multipliers. Each equation in the portfolio is an optimization problem, for which the necessary condition of a maximum/minimum is solved employing the gradient method approach. At each step of the iterative proximal method, the functional increases and finally converges to a final portfolio. We show the convergence of the method. A numerical example showing the effectiveness of the proposed approach is also developed and presented.     

An efficient distributed algorithm for maximum matching in general graphs

We present a distributed algorithm for maximum cardinality matching in general graphs. On a general graph withn vertices, our algorithm requiresO(n ^5/2) messages in the worst case. On trees, our algorithm computes a maximum matching usingO(n) messages after the election of a leader.Work on this paper has been supported by the Office of Naval Research under Contract N00014-85-K-0570.     

Genetic algorithm with binary representation of generating unit start-up and shut-down times for the unit commitment problem

An approach for solving the unit commitment problem based on genetic algorithm with binary representation of the unit start-up and shut-down times is presented. The proposed definition of the decision variables and their binary representation reduce the solution space and computational time in comparison to the classical genetic algorithm approach to unit commitment. The method incorporates time-dependent start-up costs, demand and reserve constraints, minimum up and down time constraints and units power generation limits. Penalty functions are applied to the infeasible solutions. Test results showed an improvement in effectiveness and computational time compared to results obtained from genetic algorithm with standard binary representation of the unit states and other methods.     

改进的多模态遗传算法及其在投资组合中的应用

提出用多模态遗传算法求解投资组合的新思路。首先,针对小生境遗传算法搜索结果不稳定的缺点,提出具有“迁徙操作”的新多模态遗传算法,不仅有效地找到了全部优质解,而且无需峰间距的信息。然后,针对传统的投资组合模型存在不能满足不同风险偏好投资者需要的缺点,提出符合中国国情的证券投资组合模型,并给出利用改进的多模态遗传算法求解的方法。最后进行了实证研究,得到了满意的结果。     

面向入侵检测的基于多目标遗传算法的特征选择

针对刻画网络行为的特征集中存在着不相关或冗余特征,从而导致入侵检测性能下降的问题,本文提出了一种基于多目标遗传算法的特征选择方法,将入侵检测中的特征选择问题视为多目标优化问题来处理。实验结果表明,该方法能够实现检测精度与检测算法复杂性的均衡优化,在显著提高检测算法效率的同时,检测精度也有所提高。     

A fuzzy genetic algorithm for automatic orthogonal graph drawing

This paper reflects results of research related to developing a new methodology for automatic graph drawing based on applying genetic algorithms. The methodology has permitted the elaboration of a hybrid technique that combines the most popular, classical, topology-shape-metric approach to orthogonal drawings on the grid and a genetic algorithm that is directed, in its evolutionary process, at multicriteria decision making in a fuzzy environment. In the traditional use of the topology-shape-metric approach, a single fixed planar embedding is obtained in the planarization step. Thereafter this embedding is subjected to the orthogonalization and compaction steps. However, this sequence does not guarantee that the fixed planar embedding will generate a final drawing of a good quality. Moreover, every topology-shape-metric step is classified as a NP-hard problem, and choices as well as heuristics used in previous stages have a direct impact on subsequent ones. Taking this into account, the developed hybrid technique generates a greater number of planar embeddings by varying the order of edges’ insertion when forming the planar embeddings in planarization step. Thus, the problem is formulated as a permutation-based combinatorial optimization problem. The genetic algorithm is applied at the planarization step of the topology-shape-metric. This allows one to generate the population with the corresponding number of planar embeddings. Each planar embedding obtained in the planarization step is submitted to the orthogonalization and compaction. Their results serve for applying the procedures of multicriteria decision making in a fuzzy environment. Thus, in the evolutionary process, the genetic algorithm is able to select individuals, which provide more harmonious solutions (relatively of the solutions obtained with traditional applying the topology-shape-metric approach) from the point of view of the aesthetic criteria that are usually utilized at the three steps of automatic graph drawing. This is convincingly demonstrated by experimental results given in the paper.     

基于遗传算法的进化压力的研究

为了解影响进化压力的因素,在群体大小的选择、选择运算（Selection）、交叉运算（Crossover）三个方面进行了详细的分析。通过在遗传算法的三个阶段,选取不同的方案来解决复杂的函数优化问题的实验方法,得出了不同方案对进化压力的影响差异。时差异进行了比较分析,并对实际运用中方案的选择提出了一些建议。     

Evolutionary algorithms and dynamic programming

Recently, it has been proven that evolutionary algorithms produce good results for a wide range of combinatorial optimization problems. Some of the considered problems are tackled by evolutionary algorithms that use a representation which enables them to construct solutions in a dynamic programming fashion. We take a general approach and relate the construction of such algorithms to the development of algorithms using dynamic programming techniques. Thereby, we give general guidelines on how to develop evolutionary algorithms that have the additional ability of carrying out dynamic programming steps. Finally, we show that for a wide class of the so-called DP-benevolent problems (which are known to admit FPTAS) there exists a fully polynomial-time randomized approximation scheme based on an evolutionary algorithm.     

Approximation algorithms for combinatorial multicriteria optimization problems

The computational complexity of combinatorial multiple objective programming problems is investigated. NP-completeness and # P -completeness results are presented. Using two definitions of approximability, general results are presented, which outline limits for approximation algorithms. The performance of the well-known tree and Christofides' heuristics for the traveling salesman problem is investigated in the multicriteria case with respect to the two definitions of approximability.     

Analysis of Approximation Algorithms for <Emphasis Type="Italic">k</Emphasis>-Set Cover Using Factor-Revealing Linear Programs

We present new combinatorial approximation algorithms for the k-set cover problem. Previous approaches are based on extending the greedy algorithm by efficiently handling small sets. The new algorithms further extend these approaches by utilizing the natural idea of computing large packings of elements into sets of large size. Our results improve the previously best approximation bounds for the k-set cover problem for all values of k≥6. The analysis technique used could be of independent interest; the upper bound on the approximation factor is obtained by bounding the objective value of a factor-revealing linear program. A preliminary version of the results in this paper appeared in Proceedings of the 16th International Symposium on Fundamentals of Computation Theory (FCT ’07), LNCS 4639, Springer, pp. 52–63, 2007. This work was partially supported by the European Union under IST FET Integrated Project 015964 AEOLUS and by the General Secretariat for Research and Technology of the Greek Ministry of Development under programme PENED 2003.     

On the efficiency of maximum-flow algorithms on networks with small integer capacities

The performance of maximum-flow algoirthms that work in phases is studied as a function of the maximum arc capacity,C, of the network and a quantity we call thetotal potential, P, of the network, which is related to the average amount of flow that can be sent through a node. Extending results by Even and Tarjan, we derive a tightO(min{C ^1/3¦V¦^2/3,P ^1/2, ¦V¦}) upper bound on the number of phases. AnO(min{P log¦V¦,C¦V¦^3/2, ¦V¦²¦E¦}) upper bound is derived on the total length of the augmenting paths used by Dinic's algorithm. The latter quantity is useful in estimating the performance of Dinic's method on certain inputs. Our results show that on a natural class of networks, the performance of Dinic's algorithm is significantly better than would be apparent from a bound based on ¦V¦ and ¦E¦ alone. We present an application of our bounds to the maximum subgraph density problem.     

An approximation algorithm for interval data minmax regret combinatorial optimization problems

The general problem of minimizing the maximal regret in combinatorial optimization problems with interval data is considered. In many cases, the minmax regret versions of the classical, polynomially solvable, combinatorial optimization problems become NP-hard and no approximation algorithms for them have been known. Our main result is a polynomial time approximation algorithm with a performance ratio of 2 for this class of problems.